codeforces

include <bits/stdc++.h> // 万能头文件
ios::sync_with_stdio(false);
cin.tie(0);
加速c++输入输出流

setprecision() 浮点数从做到右一共能输出几个数字，但小数末尾为0则不能输出

fix 保留几位小数 cout.setf(ios::fixed);

showpoint cout.setf(ios::showpoint); 输出小数末尾的0

https://blog.csdn.net/u011321546/article/details/9293547

C：

 1 #include <iostream>
 2 #include <cstdio>
 3  
 4 using namespace std;
 5 int main()
 6 {
 7 double n, sum = 0, tem = 0;
 8 int a[100000] = {0};
 9 int b = 1, k, v;
10 cin >> n >> k;
11 for (int i = 0; i < n; i++)
12 {
13 cin >> a[i];
14 }
15  
16 for (int i = 0; i <= n - k; i++)
17 {
18 b = 0;
19 sum = 0;
20 v = k;
21 for (int j = i; j < k + i; j++)
22 {
23 sum += a[j];
24 }
25 if (sum / (k + b) > tem)
26 {
27 tem = sum / (k + b);
28 }
29 while (v < n)
30 {
31 sum = sum + a[k + i + b];
32 b++;
33 if (sum / (k + b) > tem)
34 tem = sum / (k + b);
35 v++;
36 }
37 }
38 printf ("%.15lf", tem);
39  
40 return 0;
41 }

在程序设计的时候比下一种做法更有技巧：每次从k增加一个数

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 int main() {
 6 ios_base::sync_with_stdio(0);
 7 cin.tie(NULL);
 8 double s = 0;
 9 long long n, k, i, l, r, tmp;
10 cin >> n >> k;
11 vector<long long> a(n);
12 for(i=0;i<n;i++) cin >> a[i];
13  
14 for(l = 0; l < n; l++) {
15 tmp = 0;
16 for(r = l; r < n; r++) {
17 tmp += a[r];
18 if(r-l+1 >= k) {
19 s = max(s, double(tmp /1.0 / (r-l+1)));
20 }
21 }
22 }
23  
24 cout << setprecision(10) << fixed << s;
25 return 0;
26 }

换了个编译器就好使了？？？

D

 1 #include<stdio.h>
 2 #include<map>
 3 using namespace std;
 4 map<int,int> mp;
 5 struct{
 6 int sm;
 7 }st[35];
 8 int mn;
 9 int s[35];
10 void init(){
11 int i,a;
12 a=1;
13 mp[1]=0;
14 st[0].sm=1;
15 for(i=1;i<=31;i++){
16 a=a*2;
17 mp[a]=i;
18 st[i].sm=a;
19 }
20 }
21 int min(int a,int b){
22 if(a<b)
23 return a;
24 return b;
25 }
26 int dfs(int k,int j,int cnt){
27 int i;
28 if(j<0){
29 if(k==0)
30 mn=cnt;
31 return 0;
32 }
33 i=min(k/st[j].sm,s[mp[st[j].sm]]);
34 dfs(k-i*st[j].sm,j-1,cnt+i);
35 return 0;
36 }
37 int main(){
38 init();
39 int n,q;
40 int i,j,a;
41 scanf("%d%d",&n,&q);
42 for(i=0;i<n;i++){
43 scanf("%d",&a);
44 s[mp[a]]++;
45 }
46 while(q--){
47 mn=0;
48 scanf("%d",&a);
49 dfs(a,31,0);
50 if(mn==0)
51 printf("-1
");
52 else
53 printf("%d
",mn);
54 }
55 return 0;
56 }

我的常规DFS做法，中间调试了很久，因为我对这个过程还是不是特别了解。并没有掉到坑里之后永远见到这个坑绕道走。
还是超时了呵呵哒

 1 #include <iostream>
 2 #include <cstdio>
 3  
 4 using namespace std;
 5 int a[1000001];
 6 int n,q,num,best;
 7 void dfs(int i,int count1,int sum) // 第i个硬币选或不选，count为选择硬币个数，sum为硬币的和
 8 {
 9 if (i == n || sum == num)
10 {
11 if (sum==num &&count1 < best)
12 {
13 best = count1;
14 return ;
15 }
16 return ; // 很关键！
17  
18 }
19 if (sum > num)
20 return ;
21 if (sum+a[i] <= num)
22 {
23 // 选择该硬币
24 dfs(i+1,count1+1,sum+a[i]);
25 }
26 // 不选择该硬币
27 dfs(i+1,count1,sum);
28 }
29 int main()
30 {
31  
32 while (scanf("%d%d",&n,&q)!=EOF)
33 {
34 for (int i=0;i<n;i++)
35 scanf("%d",&a[i]);
36 for (int i=0;i<q;i++)
37 {
38 scanf("%d",&num);
39 best = 65515;
40 dfs(0,0,0);
41 if (best == 65515)
42 cout << -1 <<endl;
43 else
44 cout << best << endl;
45  
46 }
47  
48  
49 }
50  
51 return 0;
52 }
53

我重新做了一遍

 1 #include<stdio.h>
 2 #include<map>
 3 #include <iostream>
 4 #include <string>
 5 #include <string.h>
 6 using namespace std;
 7  
 8 map<int,int> mp;
 9 int rmap[32];
10 int s[32];
11 int bst; //最小的
12 void init()
13 {
14 int a = 1;
15 mp[a] = 0;
16 rmap[0] = a;
17 for (int i = 1;i<=31;i++)
18 {
19 a*=2;
20 mp[a] = i;
21 rmap[i]=a;
22 }
23 // for (int i=0;i<32;i++)
24 // cout << i <<' '<<rmap[i] << endl;
25 }
26 void dfs(int sum,int level,int cnt)
27 {
28 if (level < 0)
29 {
30 if (sum==0)
31 {
32 bst = cnt; // 一定是最小的方案
33 }
34 return ;
35 }
36 int i = min(sum/rmap[level],s[level]);
37 dfs(sum-i*rmap[level],level-1,cnt+i);
38 }
39 int main(){
40  
41 int n,q,a,cnt;
42 cin >> n >>q;
43 memset(s,0,sizeof(s));
44 memset(rmap,0,sizeof(rmap));
45 mp.clear();
46 init();
47  
48 for (int i=0;i<n;i++)
49 {
50 cin >> a;
51 s[mp[a]]++;
52 }
53 while (q--)
54 {
55 cin >> a;
56 bst = 0;
57 dfs(a,31,0); // cnt为数字的个数
58 if (bst==0)
59 cout << -1 << endl;
60 else
61 cout << bst << endl;
62 }
63  
64 return 0;
65 }

E

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <string>
  5  
  6 #define all(a) a.begin(), a.end()
  7 #define forn(a, b) for(int a = 0; a < b; a++)
  8 #define from(a, b, c) for(int a = b; a < c; a++)
  9 #define KEK cout << "KEK
";
 10  
 11 using namespace std;
 12  
 13  
 14 int n, d, k;
 15 int ptr = 2;
 16  
 17 vector< vector < int > > tree(1000000);
 18  
 19 int deep[1000000];
 20 int mark[1000000];
 21  
 22 bool first_chek() {
 23 if((n - 1) < d)
 24 return true;
 25  
 26 if(k == 1 && d != (n - 1))
 27 return true;
 28  
 29 return false;
 30 }
 31  
 32 void first_step() {
 33 //KEK
 34 int a, b, top = 1;
 35  
 36 if(k == 1) {
 37 a = 1;
 38 b = 0;
 39 } else {
 40 a = d / 2;
 41 b = (d + 1) / 2;
 42 }
 43  
 44 //cout << " :: " << a << " " << b << endl;
 45 //KEK
 46 forn(i, a) {
 47 tree[top].push_back(ptr);
 48 deep[ptr] = deep[top] + 1;
 49 top = ptr;
 50 ptr++;
 51 }
 52 //KEK
 53 top = 1;
 54 forn(i, b) {
 55 if(d % 2 == 1 && top != 1)mark[top] = 1;
 56 tree[top].push_back(ptr);
 57 deep[ptr] = deep[top] + 1;
 58 top = ptr;
 59 ptr++;
 60  
 61 }
 62 //KEK
 63 }
 64  
 65 void second_step(){
 66 //KEK
 67 for(int i = 1; i < ptr && i <= n; i++) {
 68 //cout << i << endl;
 69 if(deep[i] + 1 > d / 2) {
 70 if(mark[i] == 0)
 71 continue;
 72 else
 73 mark[i] = 0;
 74 }
 75 if(ptr > n)
 76 return;
 77 //cout << "1:: " << i << " " << tree[i].size() << endl;
 78 for(int j = tree[i].size(); j < k - (i != 1 ? 1 : 0); j++) {
 79 if(ptr > n)
 80 return;
 81 tree[i].push_back(ptr);
 82 deep[ptr] = deep[i] + 1;
 83 mark[ptr] = mark[i];
 84 ptr++;
 85 }
 86 }
 87 }
 88  
 89  
 90 int main() {
 91  
 92 cin >> n >> d >> k;
 93  
 94 if(first_chek()){
 95 cout << "NO
";
 96 return 0;
 97 }
 98  
 99 first_step();
100  
101 second_step();
102  
103 //KEK
104  
105 //cout << ptr << endl;
106  
107 if(ptr <= n)
108 cout << "NO
";
109 else {
110 cout << "YES
";
111 for(int i = 1; i <= n; i++) {
112 for(int j = 0; j < tree[i].size(); j++) {
113 cout << i << " " << tree[i][j] << endl;
114 }
115 }
116 }
117  
118 }

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3  
 4 using namespace std;
 5  
 6 int main()
 7 {
 8 int n, d, k;
 9 cin >> n >> k >> d;
10 if(n - 1 < k)return cout << "NO", 0;
11  
12 if(d == 1 || n == 2 || k == 1){
13 if(n == 2 && k == 1 && d >= 1) cout << "YES
1 2";
14 else cout << "NO";
15 return 0;
16 }
17 vector<vector<int> > edges(n);
18 int currNode = 1;
19  
20 for(int i=1;i<=ceil(k * 0.5);i++){
21 edges[i - 1].push_back(i);
22 currNode++;
23 }
24  
25 int stopNode1 = currNode - 1;
26 edges[0].push_back(currNode);
27 currNode++;
28 for(int i=1;i<k/2;i++){
29 edges[currNode - 1].push_back(currNode);
30 currNode++;
31 }
32 int stopNode2 = currNode - 1;
33 queue<int> q;
34 q.push(0);
35 while(!q.empty() && currNode != n){
36 int node = q.front(); q.pop();
37 for(int ch : edges[node]){
38 q.push(ch);
39 }
40 if(node == stopNode1 || node == stopNode2)break;
41 while(edges[node].size() + (node != 0) < d && currNode != n){
42 edges[node].push_back(currNode);
43 q.push(currNode);
44 currNode++;
45 }
46 }
47  
48  
49 if(currNode != n)cout << "NO";
50 else{
51 cout << "YES
";
52 for(int i=0;i<n;i++){
53 for(int ch : edges[i]){
54 cout << i + 1 << " " << ch + 1 << endl;
55 }
56 }
57 }
58 return 0;
59 }

F

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 map<string,int>mp;
 6  
 7 int main() {
 8 int n,id=0;
 9 string tmp;
10 vector<int> a(n+1),b(n+1);
11  
12 cin>>n;
13 // 统计每一个单词的个数，a[i]存放第i个位置的字符串的相同串的个数
14 for(int i=1;i<=n;i++){
15 cin>>tmp;
16 if(mp[tmp]==0) mp[tmp]=++id;
17 a[i]=mp[tmp];
18 b[i]=tmp.length()+b[i-1]; // 统计串的长度
19 }
20  
21 int cnt=b.back()+n-1,ans=cnt; // 字符串中非空格串长度+空格的个数，ans默认为这个
22  
23 for(int i=1;i<=n;i++){
24 for(int j=i;j<=n;j++){
25 int len=1-(b[j]-b[i-1]),ct=0;
26 for(int k=j+1;k+j-i<=n;k++){
27 int flag=1;
28 for(int p=0;p<j-i+1;p++){
29 if(a[i+p]!=a[k+p]){
30 flag=0;break;
31 }
32 }
33 if(flag){
34 ct++;k=k+j-i;
35 }
36 }
37 if(ct){
38 ans=min(ans,cnt+(ct+1)*len);
39 }
40 }
41 }
42  
43 cout<<ans<<endl;
44 }