CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » codeforces_round_638_div._2
2020-2021:teams:namespace:codeforces_round_638_div._2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/05/31 20:36]
serein [D] 		2020-2021:teams:namespace:codeforces_round_638_div._2 [2020/07/10 16:29] (当前版本)
great_designer [分析]
行 1: 行 1:
 +======codeforces round 638 div.2======
  
-======A======+不难的一套题。虽然EF两题还没做出来。 
 + 
 +开始时间：19:​30。坚持了约两个半小时。 
 + 
 +通过情况 4/6 165min 
 + 
 +^  题目 ​ ^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^ 
 +|  通过 ​ |  √  |  √  |  √  |  √  |     ​| ​    | 
 +|  补题 ​ |     ​| ​    ​| ​    ​| ​    ​| ​    ​| ​    | 
 + 
 +=====A===== 
 + 
 +====题面====
  
 菲尼克斯有n个硬币，重2^1，2^2，…，2^n。他知道n是偶数。 菲尼克斯有n个硬币，重2^1，2^2，…，2^n。他知道n是偶数。
行 21: 行 34:
  
 2 2
 +
 2 2
 +
 4 4
  
行 27: 行 42:
  
 2 2
 +
 6 6
  
行 35: 行 51:
 在第二个测试案例中，凤凰有四枚重量分别为2、4、8和16的硬币。菲尼克斯最好把重量为2和16的硬币放在一堆里，把重量为4和8的硬币放在另一堆里。差别是（2+16）－（4+8）=6。 在第二个测试案例中，凤凰有四枚重量分别为2、4、8和16的硬币。菲尼克斯最好把重量为2和16的硬币放在一堆里，把重量为4和8的硬币放在另一堆里。差别是（2+16）－（4+8）=6。
  
-分析与解答+====分析====
  
 这个题很显然。如果将最大的2^n放到一堆，那么剩余所有的硬币加起来也不如2^n大。 这个题很显然。如果将最大的2^n放到一堆，那么剩余所有的硬币加起来也不如2^n大。
  
-因此，差别最小的，一定是最大的2^n和较小的-1+n/​2个硬币放在一起，剩余硬币放在一起。根据等比数列求和，最小的差为2^{1+n/​2}-2个。（赞同）+因此，差别最小的，一定是最大的2^n和较小的-1+n/​2个硬币放在一起，剩余硬币放在一起。根据等比数列求和，最小的差为2^{1+n/​2}-2个。 
 + 
 +====代码==== 
 +<hidden A>
 <code c> <code c>
-#include <bits/stdc++.h> +#​include<​stdio.h> 
-using namespace std;+#​include<​math.h>​
  
-void solve(){+void solve() 
 +{
   int n;   int n;
- cin >> ​n;+ scanf("​%d",&​n);
  n/=2;  n/=2;
- long long int ans = pow(2, n + 1); + long long ans=pow(2,​n+1);​ 
- cout <<ans - 2 << endl;+ printf("​%lld\n",​ans-2);
 } }
  
-int main(){ +int main() 
-  int t; cin>>t; +{ 
-  while (t--) + int t; 
-    solve();+ scanf("​%d",&​t); 
 + while(t--) 
 + { 
 + solve(); 
 + }
 } }
 </​code>​ </​code>​
 +</​hidden>​
  
- +=====B===== 
-======B====== +====题面====
 凤凰喜欢美丽的阵列。如果所有长度为k的子数列具有相同的和，则数组是美丽的。数组的子数列是任何连续元素的序列。 凤凰喜欢美丽的阵列。如果所有长度为k的子数列具有相同的和，则数组是美丽的。数组的子数列是任何连续元素的序列。
  
行 89: 行 113:
  
 4 4
 +
 4 2 4 2
 +
 1 2 2 1 1 2 2 1
 +
 4 3 4 3
 +
 1 2 2 1 1 2 2 1
 +
 3 2 3 2
 +
 1 2 3 1 2 3
 +
 4 4 4 4
 +
 4 3 4 2 4 3 4 2
  
行 101: 行 133:
  
 5 5
 +
 1 2 1 2 1 1 2 1 2 1
 +
 4 4
 +
 1 2 2 1 1 2 2 1
 +
 -1 -1
 +
 7 7
 +
 4 3 2 1 4 3 2 4 3 2 1 4 3 2
  
行 119: 行 157:
 在第四个测试用例中，所示的阵列b是美丽的，并且长度k＝4的所有子阵列具有相同的和10。还有其他的解决办法。 在第四个测试用例中，所示的阵列b是美丽的，并且长度k＝4的所有子阵列具有相同的和10。还有其他的解决办法。
  
-分析+====分析====
  
 如果任意连续k个数都具有相同的和，那么这个数列一定是循环的，循环节为k。 如果任意连续k个数都具有相同的和，那么这个数列一定是循环的，循环节为k。
行 133: 行 171:
 接下来再从头开始读。每当读下一个数字的时候，先判断是不是循环节中下一个数。如果不是，就把后面一整个循环节续进去，直到是为止。这样就构造完了这个冗长的数列。 接下来再从头开始读。每当读下一个数字的时候，先判断是不是循环节中下一个数。如果不是，就把后面一整个循环节续进去，直到是为止。这样就构造完了这个冗长的数列。
  
-（反正题目没有要求最优解，只要可行解就行了）+反正题目没有要求最优解，只要可行解就行了
  
 有c个数字（c<​=k）的话，直接1，2，3，...k，行不？循环几遍到m>​=n，停止？ 有c个数字（c<​=k）的话，直接1，2，3，...k，行不？循环几遍到m>​=n，停止？
行 141: 行 179:
 看了眼数据范围，n<​100；这...直接输出自然数就行，要保证出现过，用个散列表统计一下。 看了眼数据范围，n<​100；这...直接输出自然数就行，要保证出现过，用个散列表统计一下。
  
 +====代码====
 +
 +<hidden B>
 <code c> <code c>
-#include <bits/stdc++.h> +#​include<​stdio.h>
-using namespace std;+
  
-#define maxn 1000000 +int a[1000000]; 
-#define max(a,b) a>​b?​a:​b +int b[1000000]; 
-int a[maxn]; +int ans[1000000]; 
-int b[maxn]; +  
-int ans[maxn];+int t,n,i,j,k;
  
-int t, n, i, j, k; +void solve() 
-void solve(){ +{ 
- cin >> ​n >> ​k; + scanf("​%d%d",&​n,&k); 
- for(i = 0; i < n; i++){+ for(i=0;​i<​n;​i++) 
 + {
  int tmp;  int tmp;
- cin >> ​tmp;+ scanf("​%d",&​tmp);
  a[tmp]++;  a[tmp]++;
  }  }
- int cnt = 0; + int cnt=0; 
- int max = 0; + int max=0; 
- for(i = 1; i <= n; i++){ + for(i=1;​i<​=n;​i++) 
- if(a[i] > 0) b[cnt++] = i;+ { 
 + if(a[i]>​0) 
 + { 
 + b[cnt++]=i; 
 + } 
  }  }
- if(cnt > k){ + if(cnt>​k) 
- cout << ​"​-1" ​<<​endl;+ { 
 + printf("-1\n");
  }  }
- else{ + else 
- cout << ​n*k <<​endl; + { 
- while(n--){ + printf("​%d\n",​n*k); 
- for(i = 0;i < k; i++){ + while(n--) 
- if (b[i]>​0) ​cout<< ​b[i] << ' '; + { 
- else ​cout << ​"1 ";+ for(i=0;​i<​k;​i++) 
 + { 
 + if(b[i]>​0) 
 + { 
 + printf("​%d ",b[i]); 
 + }  
 + else 
 + { 
 + printf("1 "); 
 + } 
  }  }
  }  }
- cout << endl;+ printf("​\n"​);
  }   }
- memset(a,​0,​maxn); + memset(a,​0,​1000000); 
- memset(b,​0,​maxn); + memset(b,​0,​1000000); 
- memset(ans,​0,​maxn);+ memset(ans,​0,​1000000);
 } }
-int main(){ + 
-  int t; cin>>t; +int main() 
-  while (t--) +{ 
-    solve();+ int t; 
 + scanf("​%d",&​t); 
 + while(t--) 
 + { 
 + solve(); 
 + }
 } }
 </​code>​ </​code>​
 +</​hidden>​
  
-======C====== +=====C===== 
 +====题面====
 菲尼克斯有一个由小写拉丁字母组成的字符串s。他想把字符串中的所有字母都分配到k个非空字符串a1，a2，…，ak中，这样s的每个字母都正好指向其中一个字符串ai。字符串ai不需要是s的子字符串。Phoenix可以分发s的字母，并在每个字符串ai中重新排列字母。 菲尼克斯有一个由小写拉丁字母组成的字符串s。他想把字符串中的所有字母都分配到k个非空字符串a1，a2，…，ak中，这样s的每个字母都正好指向其中一个字符串ai。字符串ai不需要是s的子字符串。Phoenix可以分发s的字母，并在每个字符串ai中重新排列字母。
  
行 230: 行 291:
  
 6 6
 +
 4 2 4 2
 +
 baba baba
 +
 5 2 5 2
 +
 baacb baacb
 +
 5 3 5 3
 +
 baacb baacb
 +
 5 3 5 3
 +
 aaaaa aaaaa
 +
 6 4 6 4
 +
 aaxxzz aaxxzz
 +
 7 1 7 1
 +
 phoenix phoenix
  
行 246: 行 319:
  
 ab ab
 +
 abbc abbc
 +
 b b
 +
 aa aa
 +
 x x
 +
 ehinopx ehinopx
  
行 261: 行 339:
 在第六个测试用例中，一个最佳的解决方案是将phoenix分配到ehinopx中。 在第六个测试用例中，一个最佳的解决方案是将phoenix分配到ehinopx中。
  
-分析+====分析====
  
-——以下算法好像出了点问题——+先排序，然后分这几种情况：
  
-逆向考虑。+比较s[0]和s[k-1]，如果不同直接输出s[k-1]，因为这时在首字母中s[k-1]已经是最大的了，后面什么都不加就是最小的，其他的加到别的地方。
  
-首先，把所有的字母全部拆掉，即对于长为n的串，先拆成n个单独的字母，然后不断拼接，直到拼成剩下k个串为止。+如果s[0]和s[k-1]相同，说明首字母相同，注意样例中的aaaaa，这就是一种特殊情况，这个情况a要均分，才是最小，比较s[k]和s[n-1]，相同就是尽量均分。
  
-由于字母顺序可以打乱，那么先将n个字母按照字典序排序。（字母可重复）+s[k]和s[n-1]不同的话，只能把s[k]到s[n-1]全都放在一个的后面，因为如果分给了其他的，一定会导致字典序增大。如abbc变成abc。
  
-每次合并的时候，把字典序最大的合并到字典序最小，并将新串串内排序，再插入原串的排列。这是二分查找加插入的操作。+====代码====
  
-大佬说用STL里面的multiset（元素可重复），本质还是树，每次取最大元和最小元维护就行了。+<hidden C> 
 +<code cpp> 
 +#​include<​iostream>​ 
 +#​include<​algorithm>​
  
-（瑟瑟发抖。至于具体怎么写，感觉有·点·复·杂） 
- 
-——以上是有点问题的算法—— 
- 
-先排序，然后分这几种情况： 
- 
-1. 比较s[0]和s[k-1]，如果不同直接输出s[k-1]，因为这时在首字母中s[k-1]已经是最大的了，后面什么都不加就是最小的，其他的加到别的地方。 
-2. 如果s[0]和s[k-1]相同，说明首字母相同，注意样例中的aaaaa，这就是一种特殊情况，这个情况a要均分，才是最小，比较s[k]和s[n-1]，相同就是尽量均分。 
-3. s[k]和s[n-1]不同的话，只能把s[k]到s[n-1]全都放在一个的后面，因为如果分给了其他的，一定会导致字典序增大。如abbc变成abc 
- 
-<code c> 
-#include <​bits/​stdc++.h>​ 
 using namespace std; using namespace std;
- +  
-void solve(){+void solve() 
 +{
  int n, k;  int n, k;
  cin >> n >> k;  cin >> n >> k;
行 295: 行 365:
  cin >> s;  cin >> s;
  sort(s.begin(),​s.end());​  sort(s.begin(),​s.end());​
- if(s[0]!=s[k-1]){+ if(s[0]!=s[k-1]) 
 + {
  cout<<​s[k-1]<<​endl;​  cout<<​s[k-1]<<​endl;​
  return;  return;
  }  }
  cout<<​s[k-1];​  cout<<​s[k-1];​
- if(s[k]!=s[n-1]){ + if(s[k]!=s[n-1]) 
- for(int i = k; i < n; i++){+ { 
 + int i;  
 + for(i = k; i < n; i++) 
 + {
  cout<<​s[i];​  cout<<​s[i];​
  }  }
  }  }
- else{ + else 
- for(int i = 0; i < (n - 1) / k; i++){+ { 
 + int i; 
 + for(i = 0; i < (n - 1) / k; i++) 
 + {
  cout<<​s[k];​  cout<<​s[k];​
  }  }
  }  }
  cout <<​endl;​  cout <<​endl;​
- return ;+ return;
 } }
-int main(){ + 
- int t;cin >> t; +int main() 
- while(t--) solve();+{ 
 + int t; 
 + cin >> t; 
 + while(t--) 
 + { 
 + solve(); 
 + }
 } }
 </​code>​ </​code>​
 +</​hidden>​
  
- +=====D===== 
-======D====== +====题面====
 菲尼克斯决定成为一名科学家！他目前正在调查细菌的生长。 菲尼克斯决定成为一名科学家！他目前正在调查细菌的生长。
  
行 353: 行 436:
  
 3 3
 +
 9 9
 +
 11 11
 +
 2 2
  
行 360: 行 446:
  
 3 3
 +
 1 0 2  1 0 2 
 +
 3 3
 +
 1 1 2 1 1 2
 +
 1 1
 +
 0  0 
  
行 402: 行 493:
 在第三个测试案例中，细菌在第1天不会分裂，然后在第1天晚上生长到第2块。 在第三个测试案例中，细菌在第1天不会分裂，然后在第1天晚上生长到第2块。
  
-分析+====分析====
  
 因为最后要求的是总质量，显然我们完全不用关心细菌究竟质量多少，只要看总个数就行了。相当于要求每次增加的质量为当前细菌个数，并且只增不减，要求从1开始，最少步骤精确达到给定值n。 因为最后要求的是总质量，显然我们完全不用关心细菌究竟质量多少，只要看总个数就行了。相当于要求每次增加的质量为当前细菌个数，并且只增不减，要求从1开始，最少步骤精确达到给定值n。
行 425: 行 516:
  
 10010 1 1 1 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。 10010 1 1 1 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。
 +
 10011 1 2 0 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。 10011 1 2 0 4——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改23两位。
  
 10100 1 2 1 3——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10100 1 2 1 3——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10101 1 2 2 2——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10101 1 2 2 2——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10110 1 2 3 1——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10110 1 2 3 1——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
 +
 10111 1 2 4 0——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。 10111 1 2 4 0——从初始数列0 1 2 4到最终数列1 2 4 8过渡中，正在修改34两位。
  
行 438: 行 533:
 100000 0 1 2 4 8——以此类推 100000 0 1 2 4 8——以此类推
  
-被修改的两位，和始终保持不变，为2的{位数减一}次幂，前一个数是标红的1后面部分减1。+被修改的两位，和始终保持不变，为2的{位数减一}次幂，前一个数是从左往右数第一个1后面部分减1。
  
 +====代码====
 +
 +<hidden D>
 <code c++> <code c++>
-#include <bits/​stdc++.h> +#​include<​iostream> 
-using namespace std;+#​include<​algorithm>​ 
 +#​include<​vector>​
  
-void solve(){+using namespace std; 
 +  
 +void solve() 
 +{
  vector<​int>​inc;​  vector<​int>​inc;​
  int N;  int N;
  cin >> N;  cin >> N;
- for(int i = 1; i <= N; i*=2){+ int i; 
 + for(i = 1; i <= N; i*=2) 
 + {
  inc.push_back(i);​  inc.push_back(i);​
  N-=i;  N-=i;
  }  }
- if(N>​0) inc.push_back(N);​+ if(N>0) 
 + { 
 + inc.push_back(N);​ 
 + }
  sort(inc.begin(),​inc.end());​  sort(inc.begin(),​inc.end());​
  cout << inc.size()-1<<​endl;​  cout << inc.size()-1<<​endl;​
- for(int i = 1; i<​inc.size();​ i++){+ for(i = 1; i<​inc.size();​ i++) 
 + {
  cout<<​inc[i]-inc[i-1]<<'​ ';  cout<<​inc[i]-inc[i-1]<<'​ ';
  }  }
  cout <<​endl;​  cout <<​endl;​
 } }
-int main(){ + 
- int t; cin >> t; +int main() 
- while(t--) +{ 
 + int t; 
 + cin >> t; 
 + while(t--) 
 + {
  solve();  solve();
 + }
 } }
 </​code>​ </​code>​
-======E====== +</​hidden>​ 
 +=====E===== 
 +====题面====
 菲尼克斯在后院摘浆果。有n灌木，每个灌木有a_i红色浆果和b_i蓝色浆果。 菲尼克斯在后院摘浆果。有n灌木，每个灌木有a_i红色浆果和b_i蓝色浆果。
  
行 482: 行 596:
 输入 输入
  
-第一行包含两个整数n和k（1\le n，k\le 500）-分别是灌木的数量和篮子容量。+第一行包含两个整数n和k（$1\le n，k\le 500$）-分别是灌木的数量和篮子容量。
  
-接下来的n行中的i-th包含两个整数a_i和b_i（$$$0\le a_i，b_i\le 10^9$$）-分别是i-th灌木中红色和蓝色浆果的数量。+接下来的n行中的i-th包含两个整数a_i和b_i（$0\le a_i，b_i\le 10^9$）-分别是i-th灌木中红色和蓝色浆果的数量。
  
 输出 输出
行 495: 行 609:
  
 2 4 2 4
 +
 5 2 5 2
 +
 2 1 2 1
  
行 505: 行 621:
  
 1 5 1 5
 +
 2 3 2 3
  
行 539: 行 656:
 在第二个例子中，菲尼克斯可以用第一个（也是唯一一个）灌木的所有浆果填满一个篮子。 在第二个例子中，菲尼克斯可以用第一个（也是唯一一个）灌木的所有浆果填满一个篮子。
  
-在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于$$$5$$，总红色浆果少于$$$5$$，总蓝色浆果少于$$$5$$。+在第三个示例中，Phoenix无法完全填充任何篮子，因为每个灌木中的浆果少于5，总红色浆果少于5，总蓝色浆果少于5。
  
 在第四个例子中，菲尼克斯可以把所有的红色浆果放进篮子里，留下一个额外的蓝色浆果。 在第四个例子中，菲尼克斯可以把所有的红色浆果放进篮子里，留下一个额外的蓝色浆果。
  
-分析 +====分析====
- +
-（暂无思路）+
  
 大致意思是只能从矩阵同行或同列取值，要求每次取值必须填满篮子（k个），问最多填多少个篮子。 大致意思是只能从矩阵同行或同列取值，要求每次取值必须填满篮子（k个），问最多填多少个篮子。
  
-======F======+$n$棵树每棵树上$a_i$个红果，$b_i$个蓝果，每个篮子容量为$k$，可以装同一棵树上的果实（条件一）或者颜色相同的果实（条件二），问最多使多少篮子恰好填满 
 + 
 +$1 \le n,k \le 500,1\le a_i,b_i\le 1e9$ 
 + 
 +以下搬运自其他页面的本题题解： 
 + 
 +考虑暴力$dp$,​ $dp[i][j][k]$表示考虑到第$i$种物品，红色的篮子还可以放$j$个，蓝色的篮子还可以放$k$个的最大值。 
 + 
 +这样如果直接的转移是$n^5$的，显然不行。可以考虑一下$j$是否能推出$k$。 
 + 
 +发现有$果实总数-dp[i][j]*每框个数=k$ 
 + 
 +转移就是枚举之前红色的框剩几个，现在红色的框剩几个。剩下的差就是本次与蓝色单独装框的即可。 
 + 
 +考虑到对于一棵树如果装在$t$个篮子中，一定可以使大于等于$t-1$个篮子满足条件一，因而所有最优解中存在一种方案使得每棵树最多提供一个满足条件二的篮子 
 + 
 +因而记$f(i,​j)$表示前$i$棵树装完剩余$j$个红果的最大篮子数,​$S_i$表示前$i$棵树果子总和,​可以推得剩余蓝果数量为$S_i-f(i,​j)*k-j$ 
 + 
 +下面只简述存在条件二篮子的转移 
 + 
 +枚举该篮子中红果数量$num_1$，蓝果为$k-num_1$；令$t_1=j-num_1+a_i,​t_2=S_i-f(i,​j)*k-j-k+num_1+b_i$ 
 + 
 +转移方程$f(i+1,​t_1\%k)=max(f(i+1,​t_1\%k),​f(i,​j)+1+t_1/​k+t_2/​k)$
  
 +=====F=====
 +====题面====
 菲尼克斯正在给他的n个朋友拍照，他们的标签是1，2，…，n，按特殊顺序排成一排。但他还没来得及拍照，他的朋友们就被一只鸭子弄得心烦意乱，把秩序搞得一团糟。 菲尼克斯正在给他的n个朋友拍照，他们的标签是1，2，…，n，按特殊顺序排成一排。但他还没来得及拍照，他的朋友们就被一只鸭子弄得心烦意乱，把秩序搞得一团糟。
  
行 574: 行 713:
  
 4 4
 +
 4 4 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
  
行 582: 行 725:
  
 YES YES
 +
 4 1 2 3 4 1 2 3
  
行 587: 行 731:
  
 4 4
 +
 1 3 1 3
 +
 2 4 2 4
 +
 3 4 3 4
 +
 2 3 2 3
  
行 595: 行 743:
  
 NO NO
 +
 1 3 4 2 1 3 4 2
 +
 1 2 4 3 1 2 4 3
  
-分析+====分析====
  
 （这个题也没思路） （这个题也没思路）
2020-2021/teams/namespace/codeforces_round_638_div._2.1590928596.txt.gz · 最后更改: 2020/05/31 20:36 由 serein

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3