首页 > 代码库 > Codeforces Round #261 (Div. 2)
Codeforces Round #261 (Div. 2)
A. Pashmak and Garden
题意：给你两个正方形的顶点坐标，让你求出另两个顶点的坐标
题解：分情况讨论即可
代码：
1 var x1,x2,y1,y2:longint; 2 begin 3 readln(x1,y1,x2,y2); 4 if x1=x2 then writeln(x1+abs(y2-y1),‘ ‘,y1,‘ ‘,x1+abs(y2-y1),‘ ‘,y2) 5 else if y1=y2 then writeln(x1,‘ ‘,y1+abs(x1-x2),‘ ‘,x2,‘ ‘,y1+abs(x1-x2)) 6 else 7 begin 8 if abs(x1-x2)<>abs(y1-y2) then writeln(‘-1‘) 9 else writeln(x1,‘ ‘,y2,‘ ‘,x2,‘ ‘,y1);10 end;11 end.
B. Pashmak and Flowers
题意：给你一个数列，如果从中选2个数，那么这两个数最大差值为多少？有多少种取法可以取到这个最大值？n (2 ≤ n ≤ 2·105).
题解：考场上扫了一遍数列，记录了4个临时变量mx，mi，w1，w2分别表示当前遇到的最大值，最小值，最大值有几个，最小值有几个
因为没处理好边界，就是刚开始的2个，结果fst了。。。也可以排一下序，直接输出a[n]-a[1]，并且把最大值的个数*最小值的个数输出即可
1 var n,x,y,w1,w2,t,mx,mi:int64; 2 i:longint; 3 begin 4 readln(n); 5 mx:=-1;mi:=1000000000; 6 for i:=1 to n do 7 begin 8 read(x); 9 if x>mx then begin mx:=x;w2:=1;end10 else if x=mx then inc(w2);11 if x<mi then begin mi:=x;w1:=1;end12 else if x=mi then inc(w1);13 end;14 if mx-mi<>0 then writeln(mx-mi,‘ ‘,w1*w2)15 else writeln(0,‘ ‘,n*(n-1)>>1);16 end.
D. Pashmak and Parmida‘s problem
题意：给你一个数列，定义f(l,r,ax)为 满足 l<=k<=r 并且 a[k]=x 的数量，求这个数列中有多少个二元组i,j是的 i<j 并且满足 f(1,i,a[i])>f(j,n,a[j]) n<=10^6 a[i]<=10^9
题解：因为数很大，数的个数很少，我们可以离散化，这样我们就可以类似桶排从前往后和从后往前各扫一遍求出 f(1,i,a[i])和f(j,n,a[j])
然后有限制条件 i<j,所以我们使用树状数组求前缀和 从后往前扫 扫到 j 的时候 j之后的g[j]都加上了，我们求 f[i-1]-1的前缀和就是i 对答案的贡献
代码：
1 const maxn=1000000+100; 2 var a,b,rk,s,f,g,ss:array[0..maxn] of int64; 3 i,n,tot:longint; 4 ans:int64; 5 procedure sort(l,r:longint); 6 var i,j,x,y:longint; 7 begin 8 i:=l;j:=r;x:=a[(i+j)>>1]; 9 repeat10 while a[i]<x do inc(i);11 while a[j]>x do dec(j);12 if i<=j then13 begin14 y:=a[i];a[i]:=a[j];a[j]:=y;15 y:=rk[i];rk[i]:=rk[j];rk[j]:=y;16 inc(i);dec(j);17 end;18 until i>j;19 if i<r then sort(i,r);20 if j>l then sort(l,j);21 end;22 procedure init;23 begin24 readln(n);25 for i:=1 to n do begin read(a[i]);rk[i]:=i;end;26 sort(1,n);27 end;28 procedure add(x:longint);29 begin30 while x<=n do31 begin32 inc(ss[x]);33 inc(x,x and (-x));34 end;35 end;36 function sum(x:longint):int64;37 var t:longint;38 begin39 t:=0;40 while x>0 do41 begin42 inc(t,ss[x]);43 dec(x,x and (-x));44 end;45 exit(t);46 end;47 procedure main;48 begin49 tot:=0;50 for i:=1 to n do51 begin52 if (i=1) or (a[i]<>a[i-1]) then inc(tot);53 b[rk[i]]:=tot;54 end;55 fillchar(s,sizeof(s),0);56 for i:=1 to n do57 begin58 inc(s[b[i]]);59 f[i]:=s[b[i]];60 end;61 fillchar(s,sizeof(s),0);62 for i:=n downto 1 do63 begin64 inc(s[b[i]]);65 g[i]:=s[b[i]];66 end;67 ans:=0;68 //for i:=1 to n do writeln(f[i],‘ ‘,g[i]);69 for i:=n downto 2 do70 begin71 add(g[i]);inc(ans,sum(f[i-1]-1));//writeln(f[i-1]-1,‘ ‘,sum(f[i-1]-1));72 end;73 writeln(ans);74 end;75 76 begin77 init;78 main;79 end.
C. Pashmak and Buses
题意：有k辆车，有n个学生，问能否给这n个学生安排d天坐车，是的没有两个同学d天都在同一辆车上。 n, k, d (1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 109).
不会捉。。。
E. Pashmak and Graph
题意：n个点，m条边的无向图，请你找出一条最长的路径（可以有环），使的这条路径上的边权严格递增n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ min(n·(n - 1), 3·105))
不会捉。。。