刚好在考完当天有一场div3,就开了个小号打了,打的途中被辅导员喊去帮忙,搞了二十分钟-_-||,最后就出了四题,题解如下:
题目链接:http://codeforces.com/contest/1003
题目:
思路:求众数出现的次数
代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 #define debug(x) cout <<"[" <<x <<"]" <<endl 6 7 const int inf = 0x3f3f3f3f; 8 const int maxn = 1e5 + 7; 9 10 int n; 11 int a[105], vis[105]; 12 13 int main() { 14 cin >>n; 15 int mx = -1; 16 for(int i = 0; i < n; i++) { 17 cin >>a[i]; 18 vis[a[i]]++; 19 if(mx < vis[a[i]]) { 20 mx = vis[a[i]]; 21 } 22 } 23 cout <<mx <<endl; 24 return 0; 25 }
题目:
思路:构造一个01串,其中0的个数为a,1的个数为b,中间刚好有k次01的交替,题目保证有解。模拟即可。
代码实现如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a, b, x, flag; 5 int vis[205]; 6 7 int main() { 8 cin >> a >> b >> x; 9 int flag = x & 1; 10 if(a >= b) { 11 vis[0] = 0; 12 a--; 13 for(int i = 1; i < x; i++) { 14 vis[i] = !vis[i-1]; 15 if(i & 1) b--; 16 else a--; 17 } 18 for(int i = 0; i < x; i++) { 19 cout <<vis[i]; 20 } 21 if(flag) { 22 for(int i = 0; i < a; i++) { 23 cout <<"0"; 24 } 25 for(int i = 0; i < b; i++) { 26 cout <<"1"; 27 } 28 } else { 29 for(int i = 0; i < b; i++) { 30 cout <<"1"; 31 } 32 for(int i = 0; i < a; i++) { 33 cout <<"0"; 34 } 35 } 36 cout <<endl; 37 } else { 38 vis[0] = 1; 39 b--; 40 for(int i = 1; i < x; i++) { 41 vis[i] = !vis[i-1]; 42 if(i & 1) a--; 43 else b--; 44 } 45 for(int i = 0; i < x; i++) { 46 cout <<vis[i]; 47 } 48 if(flag) { 49 for(int i = 0; i < b; i++) { 50 cout <<"1"; 51 } 52 for(int i = 0; i < a; i++) { 53 cout <<"0"; 54 } 55 } else { 56 for(int i = 0; i < a; i++) { 57 cout <<"0"; 58 } 59 for(int i = 0; i < b; i++) { 60 cout <<"1"; 61 } 62 } 63 cout <<endl; 64 } 65 return 0; 66 }
题目:
思路:求长度大于等于k的连续字串的平均值的最大值,因为本题数据小,可以用n^2水过,数据大了需要用二分,这里就只贴比赛时写的n^2的代码了~先用一个前缀和来维护分子,分母用一个循环处理。
代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 2 * 5007; 5 const double eps = 1e-8; 6 int n, k; 7 double ans; 8 int a[maxn], sum[maxn]; 9 10 int main() { 11 scanf("%d%d", &n, &k); 12 sum[0] = 0; 13 for(int i = 1; i <= n; i++) { 14 scanf("%d", &a[i]); 15 sum[i] = sum[i-1] + a[i]; 16 } 17 ans = -1; 18 for(int i = 1; i <= n; i++) { 19 for(int j = k; j <= n; j++) { 20 double t = 1.0 * (sum[i + j - 1] - sum[i-1]) / j; 21 if(t - ans >= eps) { 22 ans = t; 23 } 24 } 25 } 26 printf("%.7f ", ans); 27 return 0; 28 }
题目:
题意:给你n个数,ai保证是2的幂次,q次查询,每次查询给你一个数x,问使用最少的a来组成这个数,如果无法组成就输出-1.
思路:先将ai转换成2^t,用个数组来储存;将x转换成二进制,然后从最大为开始贪心,当题目给的某一次方(t次方)不够时,就用2个t-1次方来构成一个t次方,最后判断0次方是否足够即可。用样例来解释:题目给的2的1次方有2个,2次方有2个,3次方有1个。第一个x的二进制为1000,需要一个2的3次方,题目给的刚好有一个3次方,因此答案为1;第二个x的二进制为101,需要2的2次方1个,0次方1个,2次方足够,但是没有0次方,所以答案为-1;第三个x的二进制为1110,需要1个3次方,1个2次方,1个1次方,均足够,故为3。
代码实现如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 2e5 + 7; 5 int n, q, t; 6 int a[maxn], b[maxn], num[32], p[32]; 7 long long vis[maxn]; 8 9 void prepare() { 10 vis[0] = 1; 11 for(int i = 1; i < 32; i++) { 12 vis[i] = vis[i-1] * 2; 13 } 14 } 15 16 int main() { 17 prepare(); 18 cin >>n >>q; 19 for(int i = 0; i < n; i++) { 20 cin >>a[i]; 21 t = lower_bound(vis, vis + 31, a[i]) - vis; 22 num[t]++; 23 } 24 for(int i = 0; i < q; i++) { 25 cin >>b[i]; 26 int k = 0, ans = 0; 27 while(b[i]) { 28 p[k++] = b[i] % 2; 29 b[i] = b[i] / 2; 30 } 31 for(int j = k - 1; j >= 1; j--) { 32 if(num[j] < p[j]) { 33 ans += num[j]; 34 p[j-1] += 2 * (p[j] - num[j]); 35 } else { 36 ans += p[j]; 37 } 38 } 39 if(num[0] < p[0]) cout <<"-1" <<endl; 40 else cout <<ans + p[0] <<endl; 41 } 42 return 0; 43 }
赛后补题,一定要假装出是自己比赛时A的~
题目:
题意:生成一棵树,树的直径(本题的直径是指两节点间距离的最大值)为d,度数不超过k。
思路:首先生成一条链,此处节点分别为1~d+1,然后以这条链上的节点为根生成树,用dfs处理,此处生成的树的深度为min(i-1,d-i+1)(因为两节点间的距离不能超过d嘛~),注意处理NO的情况。
代码实现如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 4e5 + 7; 5 int n, k, d, cnt; 6 vector<int> G[maxn]; 7 8 void dfs(int u, int deep, int mx) { 9 if(deep == mx) return; 10 for(int i = 0; i < k - 1 - (deep == 0) && cnt < n; i++) { 11 int v = ++cnt; 12 G[u].push_back(v); 13 dfs(v, deep + 1, mx); 14 } 15 } 16 17 int main() { 18 cin >>n >>d >>k; 19 if(k==1){ 20 if(n!=2 || d!=1)printf("NO "); 21 else printf("YES 1 2 "); 22 return 0; 23 } 24 if(d >= n) { 25 cout <<"NO" <<endl; 26 return 0; 27 } 28 for(int i = 1; i <= d; i++) { 29 G[i].push_back(i+1); 30 } 31 cnt = d + 1; 32 for(int i = 1; i <= d + 1; i++) { 33 dfs(i, 0, min(i - 1, d - i + 1)); 34 } 35 if(cnt < n) { 36 cout <<"NO" <<endl; 37 return 0; 38 } 39 cout <<"YES" <<endl; 40 for(int i = 1; i <= n; i++) { 41 for(int j = 0; j < G[i].size(); j++) { 42 cout <<i <<" " <<G[i][j] <<endl; 43 } 44 } 45 return 0; 46 }