全部代码
http://codeforces.com/submissions/hanfei19910908
C题：
cf #143 C
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int N = 100005;
6 int Q[N], num[N];
7 int main(){
8 int n;long long k;
9 cin>>n>>k;
10 for(int i=0;i<n;i++)cin>>num[i];
11 sort(num,num+n);
12 int sum = 1, ans = num[0], head = 0, tail = 1;
13 //for(int i=0;i<n;i++) cout<<num[i]<<" ";cout<<endl;
14 for(int i=1;i<n;i++){
15 k -= 1LL*(num[i]-num[i-1])*(tail - head);
16 while(k < 0) {
17 k +=num[i] - num[Q[head++]];
18 }
19 Q[tail++] = i;
20 if(tail-head>sum) {
21 sum = tail-head;
22 ans = num[i];
23 }
24 }
25 cout<<sum<<" "<<ans<<endl;
26 }
27 A题 略
B题
构造一个长度为n的数列，使每个数在1到l之间，并满足a0-a1+a2-a3+...+ai * (-1)^(i%2) + ... = d
算法分析：
将所有项设成1，然后再分配。
C题
给一个长度为n(n<100,000)的数列，给一个数k(k<1,000,000,000)，你可以让数列中的一些数加1，最多可以使用k次。
现在给你随意分配的权力，问相同的数最多的数是多少？
算法分析：
排序之后，枚举答案。 判定的时候如果暴力往前是n*sqrt(k)，可以二分到达n*logn。
D题
给一个与坐标轴平行的立方体。每个面上有标号。问你在k点可以看见的标号和。
算法分析：
因为是立方体，判断一下坐标范围就可以了。
E题
给一个“点仙人掌”，即强联通分量都是简单环的图。给k此询问，问u和v之间存在几条简单路。
算法分析：
tarjan强联通缩点
倍增法求LCA
posted on 2012-10-08 06:41
西月弦 阅读(208)
评论(0) 编辑 收藏 引用