Codeforces Round #494 (Div. 3) ABCDE B. Binary String Constructing C. Intense Heat D. Coins and Queries E. Tree Constructing
A 签到题
求出现次数最多的数的次数。
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 110; 5 map<int,int> mp; 6 int main() { 7 int n, x, MAX = 0; 8 cin >> n; 9 for(int i = 0; i < n; i ++) { 10 cin >> x; 11 mp[x] ++; 12 MAX = max(MAX, mp[x]); 13 } 14 cout << MAX << endl; 15 return 0; 16 }
You are given three integers si≠si+1. It is guaranteed that the answer always exists.
For example, for the string "01010" there are four indices i=3,5).
Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.
The first line of the input contains three integers 1≤a,b≤100,1≤x<a+b).
Print only one string any binary string satisfying conditions described above. It is guaranteed that the answer always exists.
2 2 1
1100
3 3 3
101100
5 3 6
01010100
All possible answers for the first example:
- 1100;
- 0011.
All possible answers for the second example:
- 110100;
- 101100;
- 110010;
- 100110;
- 011001;
- 001101;
- 010011;
- 001011.
有a个0和b个1，构建a+b个长度的二进制，且有x个位置为xi != xi-1
写的有点恶心，写了很多if，构建0101... 或者 101010...
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 110; 5 char str[N]; 6 int main() { 7 int a, b, x; 8 bool flag = 0; 9 cin >> a >> b >> x; 10 flag = (a>b); 11 for(int i = 1; i <= x; i ++) { 12 if(flag) { 13 if(i&1) { 14 str[i] = '0'; 15 a--; 16 } 17 else { 18 str[i] = '1'; 19 b--; 20 } 21 } else { 22 if(i&1) { 23 str[i] = '1'; 24 b--; 25 } 26 else { 27 str[i] = '0'; 28 a--; 29 } 30 } 31 32 } 33 //printf("%s %d %d ",str+1,a,b); 34 if(flag) { 35 if(x&1) { 36 printf("%s",str+1); 37 for(int i = 0; i < a; i ++) printf("0"); 38 for(int i = 0; i < b; i ++) printf("1"); 39 } else { 40 printf("%s",str+1); 41 for(int i = 0; i < b; i ++) printf("1"); 42 for(int i = 0; i < a; i ++) printf("0"); 43 } 44 } else { 45 if(x&1) { 46 //101 47 printf("%s",str+1); 48 for(int i = 0; i < b; i ++) printf("1"); 49 for(int i = 0; i < a; i ++) printf("0"); 50 } else { 51 //1010 52 printf("%s",str+1); 53 for(int i = 0; i < a; i ++) printf("0"); 54 for(int i = 0; i < b; i ++) printf("1"); 55 } 56 } 57 58 return 0; 59 }
C. Intense Heat
The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have decided to actually calculate some value which would represent how high the temperatures are.
Mathematicians of Berland State University came up with a special heat intensity value. This value is calculated as follows:
Suppose we want to analyze the segment of ai.
We denote the average temperature of a segment of some consecutive days as the arithmetic mean of the temperature measures during this segment of days. So, if we want to analyze the average temperature from day average temperature over these segments).
You have been hired by Berland State University to write a program that would compute the heat intensity value of a given period of days. Are you up to this task?
The first line contains two integers heat intensity value, respectively.
The second line contains n days.
Print one real number — the heat intensity value, i. e., the maximum of average temperatures over all segments of not less than kconsecutive days.
Your answer will be considered correct if the following condition holds: res0 is the answer given by the jury's solution.
4 3
3 4 1 2
2.666666666666667
求大于等于k的连续区间的最大平均值。范围很小，直接两个for。
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 5010; 5 int a[N], sum[N]; 6 7 int main() { 8 int n, k, x; 9 scanf("%d%d",&n,&k); 10 for(int i = 1; i <= n; i ++) { 11 scanf("%d",&a[i]); 12 sum[i] = sum[i-1] + a[i]; 13 } 14 double MAX = 0; 15 for(int i = 1; i <= n-k+1; i ++) { 16 for(int j = k+i-1; j <= n; j ++) { 17 int S = sum[j] - sum[i-1]; 18 MAX = max(MAX, 1.0*S/(j-i+1)); 19 } 20 } 21 printf("%.15lf",MAX); 22 return 0; 23 }
D. Coins and Queries
Polycarp has d).
Polycarp wants to know answers on -1.
The queries are independent (the answer on the query doesn't affect Polycarp's coins).
The first line of the input contains two integers 1≤n,q≤2⋅105) — the number of coins and the number of queries.
The second line of the input contains d).
The next 1≤bj≤109).
Print -1.
5 4
2 4 8 2 4
8
5
14
10
1
-1
3
2
有 n 个数，每个数都是2d，有q次询问，求最少由多少个数组成。
由于每个数都是2d，所以用数组 a[i] 储存 2i 的数量，每次询问数字x，就从231开始直到20，只要小于x，就求下最多可以由多少个2i组成,然后就可以得到答案。
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 2e5+10; 5 int a[40]; 6 map<int,int> mp; 7 int main() { 8 int n, q, x;; 9 scanf("%d%d", &n, &q); 10 for(int i = 1; i <= n; i ++) { 11 scanf("%d", &x); 12 mp[x] ++; 13 } 14 for(int i = 0; i < 32; i ++) { 15 a[i] = mp[1<<i]; 16 } 17 while(q--) { 18 scanf("%d",&x); 19 int ans = 0; 20 for(int i = 31; i >= 0; i --) { 21 int tmp = 1<<i; 22 if(tmp <= x) { 23 int cnt = min(a[i],x/tmp); 24 ans += cnt; 25 x -= cnt*tmp; 26 } 27 } 28 if(x == 0) printf("%d ",ans); 29 else printf("-1 "); 30 } 31 return 0; 32 }
E. Tree Constructing
You are given three integers k.
Your task is to construct an undirected tree on k, or say that it is impossible.
An undirected tree is a connected undirected graph with n−1 edges.
Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.
Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex v is any other vertex of a tree).
The first line of the input contains three integers 1≤n,d,k≤4⋅105).
If there is no tree satisfying the conditions above, print only one word "NO" (without quotes).
Otherwise in the first line print "YES" (without quotes), and then print n. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.
6 3 3
YES
3 1
4 1
1 2
5 2
2 6
6 2 3
NO
10 4 3
YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7
8 5 3
YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3
构建无向图。有n个定点，每个定点最大的度数不能超过k，且直径为d，直径为任意两点直径的距离的最大值。
向构建直径为d的图1-2-3-4-...-d+1,然后从 2 至 d 遍历一遍，第i个顶点可以可以放min(i-1,d+1-i)个，dfs遍历一遍就可以了。
坑了，构建直径为d>1的就说明只是要2个度，没有考虑度数为1的。
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int N = 4e5+10; 5 vector<int> vs[N]; 6 bool vis[N]; 7 int cnt, n, d, k; 8 void dfs(int x, int ans) { 9 if(ans == 0) return; 10 while(vs[x].size() < k && cnt <= n) { 11 vs[x].push_back(cnt); 12 vs[cnt].push_back(x); 13 cnt++; 14 dfs(cnt-1,ans-1); 15 } 16 } 17 int main() { 18 cin >> n >> d >> k; 19 if(d >= n) return 0*printf("NO "); 20 for(int i = 1; i <= d; i ++) { 21 vs[i].push_back(i+1); 22 vs[i+1].push_back(i); 23 } 24 cnt = d+2; 25 for(int i = 2; i <= d; i ++) { 26 dfs(i,min(i-1,d+1-i)); 27 } 28 // cout << cnt << endl; 29 bool flag = true; 30 for(int i = 1; i <= n; i ++) { 31 if(vs[i].size() > k) { 32 flag = false; 33 break; 34 } 35 } 36 if(cnt > n && flag) { 37 printf("YES "); 38 for(int i = 1; i <= n; i ++) { 39 for(int j = 0; j < vs[i].size(); j ++) { 40 if(!vis[i] || !vis[vs[i][j]]) { 41 printf("%d %d ",i,vs[i][j]); 42 vis[i] = vis[vs[i][j]] = 1; 43 } 44 } 45 } 46 } else printf("NO "); 47 return 0; 48 }