全部代碼
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題
構(gòu)造一個(gè)長(zhǎng)度為n的數(shù)列，使每個(gè)數(shù)在1到l之間，并滿足a0-a1+a2-a3+...+ai * (-1)^(i%2) + ... = d
算法分析：
將所有項(xiàng)設(shè)成1，然后再分配。
C題
給一個(gè)長(zhǎng)度為n(n<100,000)的數(shù)列，給一個(gè)數(shù)k(k<1,000,000,000)，你可以讓數(shù)列中的一些數(shù)加1，最多可以使用k次。
現(xiàn)在給你隨意分配的權(quán)力，問(wèn)相同的數(shù)最多的數(shù)是多少？
算法分析：
排序之后，枚舉答案。 判定的時(shí)候如果暴力往前是n*sqrt(k)，可以二分到達(dá)n*logn。
D題
給一個(gè)與坐標(biāo)軸平行的立方體。每個(gè)面上有標(biāo)號(hào)。問(wèn)你在k點(diǎn)可以看見(jiàn)的標(biāo)號(hào)和。
算法分析：
因?yàn)槭橇⒎襟w，判斷一下坐標(biāo)范圍就可以了。
E題
給一個(gè)“點(diǎn)仙人掌”，即強(qiáng)聯(lián)通分量都是簡(jiǎn)單環(huán)的圖。給k此詢問(wèn)，問(wèn)u和v之間存在幾條簡(jiǎn)單路。
算法分析：
tarjan強(qiáng)聯(lián)通縮點(diǎn)
倍增法求LCA
posted on 2012-10-08 06:41
西月弦 閱讀(228)
評(píng)論(0) 編輯 收藏 引用