【题解】2021年牛客寒假集训营第一场题解
Updated:B（括号）的数据已经加强，大家可以再次提交试试（不影响rating和排名）
Level 0 对答案一时爽
对标cf难度：900
知识点：贪心
签到题。最小值显然是0。最大值只需要找到有多少答案牛妹和牛牛是一样的，用题目总数加上这个数即可。
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
int n;
int main(){
int i,j;
string a,b;
cin>>n;
cin.get();
getline(cin, a, '\n');
getline(cin, b, '\n');
a.erase(remove_if(a.begin(), a.end(), ::isspace), a.end());
b.erase(remove_if(b.begin(), b.end(), ::isspace), b.end());
int cnt=0;
for(i=0;i<n;i++)if(a[i]==b[i])cnt++;
cout<<n+cnt<<" "<<0;
}
level 1 括号
对标cf难度：1300
知识点：构造、贪心
注意到题目要求字符串长度不超过，而
大概是三万多不到4万，所以可以在8万以内完成构造。
一种简单的构造方式是这样：找到一个数，求出
的商
和余数
，那么则有
。所以先用
个左括号，再用
个右括号，构成的字符串有
个括号对。之后在第
个左括号的后面插入一个右括号，就正好增加了
个括号对，符合题目要求。
大概长这个样子：
(((....((()((((...((())))....)))))
注意要特判k=0的情况，不要输出空串。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i;
cin>>n;
if (n == 0) {
cout << ")(" << endl;
}
else {
int p=sqrt(n);
int c=n/p,y=n%p;
for(i=0;i<y;i++)printf("(");
printf(")");
for(;i<p;i++)printf("(");
for(i=0;i<c;i++)printf(")");
}
}
level 2 限制不互素对的排列
对标cf难度：1500
知识点：构造、数学
观察到不超过
的一半，那么就简单了。
由于不大于的所有正整数***有
个偶数（向下取整），那么如果k<n/2的话，直接取出k+1个偶数依次排列，再从开始从小到大即可。可以证明，后面的部分一定是相邻两两互素的。
如果k=n/2，那么有一个方法是，先取出所有的偶数，除了6以外依次排列，然后6后面接一个3（6和3显然不互素），然后3后面接1、5、7...依次从小到大。
举个例子，当n=10，k=5时，构造的结果是这样的：
2 4 8 10 6 3 1 5 7 9
要注意特判的情况，因为n=5，k=2的时候无法在6后面接一个3了（不存在正整数6），所以无解。
ps:如果 的时候怎么构造？
#include<bits/stdc++.h>
using namespace std;
int tong[100010];
int main(){
// freopen("13.in","r",stdin);
// freopen("13.out","w",stdout);
int n,k,i;
cin>>n>>k;
if(n<6){
if(k==n/2)cout<<-1;
else{
cout<<2;
tong[2]=1;
int i=4;
while(k--)cout<<" "<<i,tong[i]=1,i+=2;
for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i;
}
}
else{
if(k==n/2){
for(i=2;i<=n;i+=2){
if(i!=6)cout<<i<<" ",tong[i]=1;
}
cout<<6<<" "<<3<<" ";
tong[6]=tong[3]=1;
for(i=1;i<=n;i+=2){
if(!tong[i])cout<<i<<" ",tong[i]=1;
}
}
else{
cout<<2;
tong[2]=1;
int i=4;
while(k--)cout<<" "<<i,tong[i]=1,i+=2;
for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i;
}
}
}
level 2 一群小青蛙呱蹦呱蹦呱
对标cf难度：1500
知识点：数论
我们可以发现，到最后剩余的数一定是不能表示为素数幂形式的数。
因此可以对每个素数对最终答案的贡献分别计算。
对于素数2而言，最大的贡献是（后面无法找到有
个2的贡献）。
对于大于2的素数p而言，最大的贡献是（后面无法找到有
个p的贡献）。
先线性筛出7.5e7以内的所有素数，然后统计每个素数的贡献后相乘即可。
#include<bits/stdc++.h>
using namespace std;
#define N 80010000
#define ll long long
int num[N], prim[5000060];
int pn = 0;
void table(){
memset(num, -1, sizeof(num));
for(int i = 2;i < N;i++){
if(num[i]) prim[pn++] = i;
for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){
num[i*prim[j]] = 0;
if(i % prim[j] == 0) break;
}
}
}
int main(){
table();
int i;
int n;
ll res=1,mod=1e9+7;
cin>>n;
if(n<6){cout<<"empty";return 0;}
for(i=1;prim[i]<=n/2;i++){
ll p=prim[i],temp=1;
while(temp*p<=n/2)temp*=p;
res=res*temp%mod;
}
ll temp2=1;
while(temp2*2<=n/3)temp2*=2;
res=res*temp2%mod;
cout<<res;
}
level 3 点一成零
对标cf难度：1700
知识点：并查集
假设连通块数量为n，那么总方案数就是
每次操作有可能增加或减少连通块的数量，并改变连通块的大小，用并查集维护即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int fa[250010];
int kdm[250020];
string a[505];
int n;
int mod=1e9+7;
ll power(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll inv(ll x){
return power(x,mod-2);
}
int f(int x){
if(fa[x]==x)return x;
return f(fa[x]);
}
void uni(int x,int y){
int p=f(x),q=f(y);
if(p==q)return;
if(kdm[p]<kdm[q]){
fa[p]=q;
kdm[q]+=kdm[p]+1;
}
else {
fa[q]=p;
kdm[p]+=kdm[q]+1;
}
}
int visited[505][505];
void dfs(int x,int y){
visited[x][y]=1;
if(x>0&&!visited[x-1][y]&&a[x-1][y]=='1')dfs(x-1,y);
if(x<n-1&&!visited[x+1][y]&&a[x+1][y]=='1')dfs(x+1,y);
if(y>0&&!visited[x][y-1]&&a[x][y-1]=='1')dfs(x,y-1);
if(y<n-1&&!visited[x][y+1]&&a[x][y+1]=='1')dfs(x,y+1);
}
int main(){
// freopen("10.in","r",stdin);
// freopen("10.out","w",stdout);
int i,j;
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
for(i=0;i<n*n;i++)fa[i]=i;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(j<n-1&&a[i][j]=='1'&&a[i][j+1]=='1'){
uni(i*n+j,i*n+j+1);
}
if(i<n-1&&a[i][j]=='1'&&a[i+1][j]=='1'){
uni(i*n+j,(i+1)*n+j);
}
}
}
int cnt=0;
ll res=1;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]=='1'&&!visited[i][j]){
cnt++;
// cout<<kdm[f(n*i+j)]+1<<endl;
res=res*(kdm[f(n*i+j)]+1)%mod;
dfs(i,j);
}
}
}
// cout<<cnt<<endl;
for(i=1;i<=cnt;i++)res=res*i%mod;
// cerr<<"RES:"<<res<<endl;
int q;
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(a[x][y]=='1'){
cout<<res<<endl;
}
else{
int temp=1;
cnt++;
res=res*cnt%mod;
// cerr<<"RES:"<<res<<endl;
a[x][y]='1';
if(x>0&&a[x-1][y]=='1'&&f(n*(x-1)+y)!=f(n*x+y)){
res=res*inv(kdm[f(n*(x-1)+y)]+1)%mod;
temp+=kdm[f(n*(x-1)+y)]+1;
uni(n*(x-1)+y,n*x+y);
res=res*inv(cnt)%mod;
cnt--;
}
// cerr<<"RES:"<<res<<endl;
if(x<n-1&&a[x+1][y]=='1'&&f(n*(x+1)+y)!=f(n*x+y)){
res=res*inv(kdm[f(n*(x+1)+y)]+1)%mod;
// cout<<kdm[f(n*(x+1)+y)]+1<<endl;
temp+=kdm[f(n*(x+1)+y)]+1;
uni(n*(x+1)+y,n*x+y);
res=res*inv(cnt)%mod;
cnt--;
}
// cerr<<"RES:"<<res<<endl;
if(y>0&&a[x][y-1]=='1'&&f(n*x+y-1)!=f(n*x+y)){
res=res*inv(kdm[f(n*x+y-1)]+1)%mod;
temp+=kdm[f(n*x+y-1)]+1;
uni(n*x+y-1,n*x+y);
res=res*inv(cnt)%mod;
cnt--;
}
// cerr<<"RES:"<<res<<endl;
if(y<n-1&&a[x][y+1]=='1'&&f(n*x+y+1)!=f(n*x+y)){
res=res*inv(kdm[f(n*x+y+1)]+1)%mod;
temp+=kdm[f(n*x+y+1)]+1;
uni(n*x+y+1,n*x+y);
res=res*inv(cnt)%mod;
cnt--;
}
// cout<<temp<<" "<<kdm[f(x*n+y)]+1<<endl;
res=res*temp%mod;
cout<<res<<endl;
}
}
}level 3 红和蓝
对标cf难度：1700
知识点：树、搜索、dp
可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：
- 若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。
- 若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。
#include<bits/stdc++.h>
using namespace std;
vector<int>g[200020];
int dp[200020];
int su(int x,int pr){
int i,sum=1;
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pr){
sum+=su(g[x][i],x);
}
}
return dp[x]=sum;
}
char out[200020];
int jud=0;
char f(char c){
if(c=='R')return 'B';
return 'R';
}
void dfs(int x,int pr,char c){
if(jud)return;
out[x]=c;
int cnt=0,i;
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pr){
cnt+=dp[g[x][i]]&1;
}
}
if(out[x]==out[pr]){
if(cnt!=0){jud=1;return;}
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pr){
dfs(g[x][i],x,f(c));
}
}
}
else {
if(cnt!=1){jud=1;return;}
for(i=0;i<g[x].size();i++){
if(g[x][i]!=pr){
if(dp[g[x][i]]&1)dfs(g[x][i],x,c);
else dfs(g[x][i],x,f(c));
}
}
}
}
int main(){
int n,i;
cin>>n;
for(i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dp[1]=su(1,-1);
// for(i=1;i<=n;i++)cout<<dp[i]<<endl;
out[0]='B';
dfs(1,0,'R');
if(jud)cout<<-1;
else for(i=1;i<=n;i++)cout<<out[i];
}
/*
6
1 2
2 3
3 4
3 5
5 6
*/
level 4 幂塔个位数的计算
对标cf难度：2100
知识点：找规律、欧拉降幂（划掉）
计算a↑↑n
- 当n为1时，直接输出a的个位数即可。
- 当n=2时，如果a的个位数是2、3、7、8，那么需要观察a的十位数是奇数还是偶数。因为
，而2、3、7、8的幂的个位数是4个一循环，所以只用观察a模4是2还是0就行。
如果a的个位数是其他的，那么可以直接输出答案：a的个位数是0 1 5 6 9输出本身即可。a个位数是4则输出6。 - 当n大于2时，由于
，而如果a是偶数，
模4的值是确定的，所以
的个位数也是确定的。而如果a是奇数（特指个位数是3和7），那么
模4的值。如果
a的个位数是{0,1,2,3,4,5,6,7,8,9}时，对应的
不过这道题也可以欧拉降幂直接秒掉，但由于我欧拉降幂不是很熟，所以这里就不讲解了，想学习的同学可以自行百度。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int out[10]={0,1,6,7,6,5,6,3,6,9};
int main(){
ll a,b;
string A,B;
cin>>A>>B;
if(B.length()==1&&B[B.length()-1]=='1'){
cout<<A[A.length()-1];
return 0;
}
a=(A[A.length()-1]-'0')%10;
if(A[A.length()-1]=='3'||A[A.length()-1]=='7'){
if(A.length()==1||(A[A.length()-2]-'0')%2==0){
cout<<out[a];
}
else{
cout<<a;
}
return 0;
}
if((a!=2&&a!=8)||(B.length()>1||B[B.length()-1]!='2')){
cout<<out[a];
}
else{
if(a==2){
if(A.length()==1||(A[A.length()-2]-'0')%2==0){
cout<<4;
}
else cout<<6;
}
else{
if(A.length()==1||(A[A.length()-2]-'0')%2==0){
cout<<6;
}
else cout<<4;
}
}
}
level 4 串
对标cf难度：2000
知识点：dp
定义dp[i]为长度为i且包含子序列"us"的字符串的数量。
那么对于长度i+1而言，包含子序列"us"的字符串有两类：
①前i个字符已经包含了子序列"us"，后面接任意一个字符。数量为dp[i]*26
②前i个字符包含字母u，但不包含子序列"us"。后面再接一个字符's'即可。数量为26^i-25^i-dp[i]。
两者相加即为dp[i+1]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll dp[1000100]={0};
int main(){
dp[1]=0;
dp[2]=1;
int n,i;
cin>>n;
for(i=3;i<=1e6;i++)dp[i]=(power(26,i-1)-power(25,i-1)+25*dp[i-1]+mod)%mod;
ll res=0;
for(i=1;i<=n;i++)res=(res+dp[i])%mod;
cout<<res;
return 0;
}
level 4 三棱锥之刻
对标cf难度：2000
知识点：计算几何
根据r和a的关系一共分4类情况：
①染色面积为0
②染色面积为4个圆形
③染色面积为三棱锥的内表面减去12个小三角（不是三角形，而是一个三角形往内刨掉一个弓形）
④染色面积为三棱锥的内表面全体
分类讨论分别计算即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
double pi=acos(-1);
double a,r=1;
cin>>a>>r;
double ma=sqrt(6)/4*a,mi=ma/3;
double allar=sqrt(3)*a*a;
double dd=sqrt(2)/4*a;
// cout<<"debug:"<<ma<<" "<<mi<<" "<<dd<<endl;
if(r<mi)cout<<0<<endl;
else if(r<dd){
printf("%.5f\n",4*pi*(r*r-mi*mi));
}
else if(r<ma){
//小等边三角形+小等腰三角形-扇形
double temp=sqrt(r*r-mi*mi);
double th=pi-asin(sqrt(3)/6*a/temp);
double ntr=pi-th-pi/6;
// cout<<ntr<<endl;
double d=sin(ntr)*temp*2;
// double d2=sin(ntr)*sqrt(3)/3*a/sin(th);
// cout<<d<<endl;
double h=sqrt(temp*temp-d*d/4);
double ar=sqrt(3)/4*d*d+d*h/2-ntr*temp*temp;
printf("%.5f\n",allar-12*ar);
}
else{
printf("%.5f\n",allar);
}
}
level ？ 好玩的数字游戏
对标cf难度：？
知识点：模拟
这道题并没有什么算法，模拟就完事了。
考验的是大家的码力和debug能力。
#include<bits/stdc++.h>
using namespace std;
long long f(long long x,int p){
long long r=(x%p)*(x%p)/10%p;
return (r^(1LL<<17)^(1LL<<57))%p;
}
int a[10][10];
int pp;
int cnt=0;
void gaow(int x){ //先移动，再合并，最后移动
int i,j;
for(i=1;i<4;i++){
for(j=i-1;j>=0;j--){
if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1;
else break;
}
}
for(i=0;i<3;i++){
if(a[i][x]==a[i+1][x]&&a[i+1][x]){
pp=1;
cnt+=a[i][x]*2;
a[i][x]*=2;
a[i+1][x]=0;
}
}
for(i=1;i<4;i++){
for(j=i-1;j>=0;j--){
if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1;
else break;
}
}
}
void gaoa(int x){ //先移动，再合并，最后移动
int i,j;
for(i=1;i<4;i++){
for(j=i-1;j>=0;j--){
if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1;
else break;
}
}
for(i=0;i<3;i++){
if(a[x][i]==a[x][i+1]&&a[x][i]){
pp=1;
cnt+=a[x][i]*2;
a[x][i]*=2;
a[x][i+1]=0;
}
}
for(i=1;i<4;i++){
for(j=i-1;j>=0;j--){
if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1;
else break;
}
}
}
void gaos(int x){ //先移动，再合并，最后移动
int i,j;
for(i=2;i>=0;i--){
for(j=i+1;j<4;j++){
if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1;
else break;
}
}
for(i=2;i>=0;i--){
if(a[i][x]==a[i+1][x]&&a[i][x]){
pp=1;
cnt+=a[i][x]*2;
a[i+1][x]*=2;
a[i][x]=0;
}
}
for(i=2;i>=0;i--){
for(j=i+1;j<4;j++){
if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1;
else break;
}
}
}
void gaod(int x){ //先移动，再合并，最后移动
int i,j;
for(i=2;i>=0;i--){
for(j=i+1;j<4;j++){
if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1;
else break;
}
}
for(i=2;i>=0;i--){
if(a[x][i]==a[x][i+1]&&a[x][i]){
pp=1;
cnt+=a[x][i]*2;
a[x][i+1]*=2;
a[x][i]=0;
}
}
for(i=2;i>=0;i--){
for(j=i+1;j<4;j++){
if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1;
else break;
}
}
}
void out(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int jud(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(a[i][j]==0)return 0;
if(i<3&&a[i][j]==a[i+1][j])return 0;
if(j<3&&a[i][j]==a[i][j+1])return 0;
}
}
return 1;
}
int main(){
srand(time(0));
int i,j,k,y;
int x=10201,p,q;
cin>>x>>p>>q;
for(i=0;i<4;i++){
for(j=0;j<4;j++){
cin>>a[i][j];
}
}
string s="";
// cout<<s<<endl;
cin>>s;
for(i=0;i<q*2;i+=2){
pp=0;
s[i+1]--;
switch(s[i]){
case 'W':gaow(s[i+1]-'0');break;
case 'A':gaoa(s[i+1]-'0');break;
case 'S':gaos(s[i+1]-'0');break;
case 'D':gaod(s[i+1]-'0');break;
}
if(pp){
while(1){
// cout<<x%16/4<<" "<<x%4<<endl;
if(a[x%16/4][x%4]==0){a[x%16/4][x%4]=2;x=f(x,p);break;}
x=f(x,p);
}
}
// out();
if(jud())break;
}
// out();
cout<<cnt<<endl;
if(i==q*2)cout<<"never die!";
else cout<<i/2+1;
}
/*
10007 1000001 1
0 0 0 0
0 0 0 0
0 0 0 0
8 4 2 2
D4
*/
