【题解】牛客寒假集训营第三场
Happy New Year！
https://ac.nowcoder.com/acm/contest/9983/D
level 0 Happy New Year！
对标cf难度：900
知识点：模拟
直接从n往后遍历即可，找到第一个数字和相等的break。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int f(int x){
int cnt=0;
while(x){
cnt+=x%10,x/=10;
}
return cnt;
}
int main(){
ll n,t,i,j,k;
cin>>n;
for(i=n+1;i<=1e5;i++){
if(f(i)==f(n))break;
}
cout<<i;
}
level 1 加法和乘法
对标cf难度：1300
知识点：博弈
如果只有一个数，那么这个数是奇数则牛牛赢，否则牛妹赢。
如果不止一个数，那么假设有奇数个数，显然是牛妹赢。因为剩余2个数的时候，牛妹做最后一次操作，无论什么情况一定都能生成两个偶数（如果剩两个奇数就做加法，如果存在偶数就做乘法）。
假设有偶数个数，牛妹要做的就是让最后剩余2个偶数即可。牛牛每次最多可以消除一个偶数，牛妹每次最多可以生成一个偶数。所以如果初始状态的偶数不小于2个，则牛妹赢；否则牛牛赢。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n,x=0,y=0,i,j,k;
cin>>n;
for(i=0;i<n;i++)
{
cin>>k;
if(k%2) x++;
else y++;
}
if(n==1&&k%2){cout<<"NiuNiu";return 0;}
if(n%2||y>1) cout<<"NiuMei";
else cout<<"NiuNiu";
return 0;
}
level 1 糖果
对标cf难度：1400
知识点：并查集
互为朋友的人拿到的糖果数量应该一样，且为这个并查集size的最大值。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll fa[1000100];
ll a[1000100];
int f(int x){
if(x==fa[x])return x;
return fa[x]=f(fa[x]);
}
int main(){
ll n,m,i;
cin>>n>>m;
for(i=1;i<=n;i++)cin>>a[i],fa[i]=i;
for(i=0;i<m;i++){
int x,y;
cin>>x>>y;
int p=f(x),q=f(y);
fa[p]=q;
a[p]=a[q]=max(a[p],a[q]);
}
ll res=0;
for(i=1;i<=n;i++)res+=a[f(i)];
cout<<res;
}
level 1 数字串
对标cf难度：1400
知识点：字符串、模拟、贪心
我们不妨这样想，先将给定的字母串转化为数字串，然后用两种不同的贪心方法：
- 优先一一对应的转化（不使用10以上的数字）
- 优先使用两位数
这样如果两种方案构造出的字母串相等，则无解。否则一定有解，输出和初始串不等的任意字符串即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,i,j,k,t;
string s;
cin>>s;
string temp1="",temp2="";
for(i=0;i<s.length();i++){
int t=(s[i]-'a')+1;
if(t/10>0&&t%10!=0){
temp1+=t/10+'a'-1;
temp1+=t%10+'a'-1;
}
else temp1+=s[i];
}
if(temp1!=s){cout<<temp1;return 0;}
for(i=0;i<s.length()-1;i++){
int t1=(s[i]-'a')+1,t2=(s[i+1]-'a')+1,p=t1*10+t2;
if(t2<10&&p<=26){
temp2+=p+'a'-1;
i++;
}
else temp2+=s[i];
}
if(i==s.length()-1)temp2+=s[i];
if(temp2!=s)cout<<temp2;
else cout<<-1;
}
level 2 序列的美观度
对标cf难度：1700
知识点：dp
我是这样做的：先预处理每个数出现在哪些角标，数值为的角标放入vector：
里，并开一个temp数组，
用来记录数值为
的数遍历到了
中的位置。
设为前
个数删掉部分数后能达到的最大美观度。
然后就可以得dp方程：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000100],tong[1000100];
vector<ll>g[1000100];
ll dp[1000100],temp[1000100];
int main(){
ll n,m,i,cnt=0;
cin>>n;
for(i=1;i<=n;i++)scanf("%lld",&a[i]),g[a[i]].push_back(i);
// cout<<g[1][0]<<" "<<g[1][1]<<endl;
for(i=1;i<=n;i++){
if(temp[a[i]]==0){
temp[a[i]]++;
dp[i]=dp[i-1];
continue;
}
dp[i]=max(dp[i-1],dp[g[a[i]][temp[a[i]]-1]]+1);
// cout<<i<<" "<<a[i]<<" "<<g[a[i]][temp[a[i]]-1]<<endl;
temp[a[i]]++;
}
cout<<dp[n];
}
level 2 匹配串
对标cf难度：1600
知识点：字符串、贪心
由于每个字符串都包含井号，所以最终答案要么是0，要么是无穷大。因为井号可以代替任何串。
最终答案是0的充要条件是：存在某个串的前缀包含所有串前缀，存在某个串的后缀包含所有串后缀。注意这里“前后缀”的定义是直到第一次遇到井号位置的全部子串。
（由于刚开始读错题了，没有看到“每个字符串至少包含一个井号”，所以写了个kmp，大家忽略就好）
（假设存在不包含井号的字符串，这道题的难度直接上升到2100+）
（不过读错题也并不是没有好处，至少让我把不熟的kmp又练习了一遍ww）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//只关心前缀和后缀
string s[1000100];
int nex[1000100];
vector<string>v,qz,hz;
void get(string a){
int k=-1,i;
nex[0]=-1;
for(i=0;i<a.length();){
if(k==-1||a[i]==a[k]){
i++,k++;
nex[i]=k;
}
else k=nex[k];
}
}
int jud(string a,string b){
// cout<<a<<" "<<b<<endl;
string s,t;
int i,j=0,k=b.length()-1;
for(i=0;i<a.length()&&a[i]!='#';i++){
if(a[i]!=b[j])return 0;
j++;
}
for(i=a.length()-1;i>=j&&k>=j&&a[i]!='#';i--){
if(a[i]!=b[k])return 0;
k--;
}
int op=j,ed=i;
// cout<<op<<" "<<ed<<" "<<k<<endl;
//在op和ed之间找子串
int ek=op;
for(i=op;i<ed;i=j){
while(i<ed&&a[i]=='#')i++;
if(i>=ed)break;
// cout<<i<<" "<<j<<endl;
string temp="";
for(j=i;j<ed&&a[j]!='#';j++)temp+=a[j];
memset(nex,0,sizeof(int)*(temp.length()+10));
// cout<<temp;
get(temp);
// for(int z=0;z<temp.length();z++)cout<<nex[z]<<" ";
int tempi=0;
// cout<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
while(tempi<(int)(temp.length())&&ek<=k){
// cout<<"!"<<endl;
// if(tempi!=-1)cout<<"!"<<tempi<<" "<<ek<<" "<<temp[tempi]<<" "<<b[ek]<<endl;
if(tempi==-1||temp[tempi]==b[ek]){
tempi++,ek++;
}
else tempi=nex[tempi];
// cout<<"debug:"<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
}
// cout<<"jj:"<<tempi<<" "<<temp.length()<<" "<<ek<<" "<<k<<endl;
// cout<<tempi<<" "<<ek<<" "<<k<<endl;
if(tempi<(int)(temp.length()))return 0;
}
// cout<<i<<" "<<ed<<endl;
return i>=ed;
}
int main(){
ll n,i,j,k,t;
cin>>n;
for(i=0;i<n;i++){
cin>>s[i];
for(j=0;j<s[i].length();j++){
if(s[i][j]=='#')break;
}
if(j==s[i].length())v.push_back(s[i]);
}
if(v.size()!=0){ //假设存在至少一个无#串
for(i=0;i<v.size()-1;i++){
if(v[i]!=v[i+1]){
cout<<0;
return 0;
}
}
string temp=v[0];
//cout<<temp<<endl;
// get(temp);
// for(i=0;i<temp.length();i++)cout<<nex[i]<<" ";
// cout<<endl;
//cout<<"!"<<endl;
for(i=0;i<n;i++){ //每个串井号之间必须是temp的子序列
if(!jud(s[i],temp)){
cout<<0;
return 0;
}
}
cout<<1;
}
else{//判断所有前后缀是否全部匹配
string ma1="",ma2="";
for(i=0;i<n;i++){
for(j=0;j<s[i].length();j++){
if(s[i][j]=='#')break;
if(j==ma1.length())ma1+=s[i][j];
}
for(j=s[i].length()-1;j>=0;j--){
if(s[i][j]=='#')break;
if(s[i].length()-1-j==ma2.length())ma2+=s[i][j];
}
}
// cout<<ma1<<endl<<ma2<<endl;
for(i=0;i<n;i++){
for(j=0;j<s[i].length()&&s[i][j]!='#';j++){
if(j==ma1.length()||s[i][j]!=ma1[j]){
// cout<<s[i][j]<<endl;
cout<<0;return 0;
}
}
int tt=0;
for(j=s[i].length()-1;j>=0&&s[i][j]!='#';j--,tt++){
if(tt<0||s[i][j]!=ma2[tt]){
// cout<<s[i][j]<<" "<<ma2[tt]<<endl;
cout<<0;return 0;
}
}
}
cout<<-1;
}
}level 3 内卷
对标cf难度：1800
知识点：贪心
不妨让所有人最开始都取E等，然后能改变max-min的值的唯一方法显然是让最小成绩的那个人取到D。然后继续找当前最小成绩，不断重复这个过程，直到A等的人即将超过k；或者某个人的A等都是所有人最小为止。
可以用优先队列（最小堆）维护这一过程。
#include<bits/stdc++.h>
using namespace std;
struct node{
int id,i,val;
node(int id,int i,int val){this->id=id,this->i=i,this->val=val;}
bool operator < (const node &b)const
{
return val>b.val;
}
};
priority_queue<node>q;
int a[100010][5];
int main(){
int n,k,i,j,cnt=0,ma=0;
cin>>n>>k;
for(i=0;i<n;i++){
for(j=0;j<5;j++)scanf("%d",&a[i][j]);
node temp(i,4,a[i][4]);
q.push(temp);
ma=max(ma,a[i][4]);
}
int res=ma-q.top().val;
while(1){
node temp=q.top();
// cout<<temp.id<<" "<<temp.i<<" "<<temp.val<<endl;
q.pop();
if(temp.i==0)break;
node ne(temp.id,temp.i-1,a[temp.id][temp.i-1]);
q.push(ne);
ma=max(ma,a[temp.id][temp.i-1]);
if(temp.i==1)k--;
if(k<0)break;
res=min(res,ma-q.top().val);
}
cout<<res;
}level 3 模数的世界
对标cf难度：1900
知识点：数学
如果a,b都是0，那么显然答案为0。
否则一定能构造出gcd为p-1的结果。构造方法如下：
(p-1)(p-a)=p(p-a-1)+a
但是，直接输出(p-1)(p-a)和(p-1)(p-b)有可能造成gcd大于p-1的情况，对p取模后反而小于p-1。
我的方法是不断加p*(p-1)，直到找到第一个gcd为p-1为止（有可能被叉掉，这个方法复杂度没有上限）
不过数据不是很强所以还是卡过去了ww（这道题给了3s，我跑了600ms，说明出题人没特地卡这种做法）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i,j,k,t;
scanf("%d",&t);
while(t--){
int a,b,p;
scanf("%d%d%d",&a,&b,&p);
if(a==0&&b==0)
printf("0 0 0\n");
else{
long long x=(p-1-a)*p+a,y=(p-1-b)*p+b;
while(__gcd(x,y)!=p-1)x+=p*p-p;
printf("%d %lld %lld\n",p-1,x,y);
}
}
}
level 3 重力坠击
对标cf难度：1900
知识点：搜索
观察到数据很小，所以直接搜索即可。
我的方法是：
首先预处理出每个点能击杀不同敌人的方案数，并状压去重：假设某种方案能击杀1号、3号和7号敌人，那么计该方案的状压值为
下一步，对去重之后的方案直接dfs搜索。维护所有情况的最大值（两个方案一起选，带来的状压值应该是位或运算，例如第一种方案击杀1、3、7，第二种方案击杀2、7，那么两个一起选则是击杀1、2、3、7）。
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,r;
};
node a[11];
set<int>s;
vector<int>v;
int ma=0,kk;
int gao(int x){
int cnt=0;
while(x)cnt+=x%2,x/=2;
return cnt;
}
void dfs(int i,int temp,int x){
if(temp==kk){
ma=max(ma,gao(x));
return;
}
if(i==v.size())return;
dfs(i+1,temp+1,x|v[i]);
dfs(i+1,temp,x);
}
int main(){
int n,i,j,k,r;
cin>>n>>kk>>r;
for(i=0;i<n;i++){
cin>>a[i].x>>a[i].y>>a[i].r;
}
for(i=-17;i<=17;i++){
for(j=-17;j<=17;j++){
int temp=0;
for(k=0;k<n;k++){
if((a[k].x-i)*(a[k].x-i)+(a[k].y-j)*(a[k].y-j)<=(r+a[k].r)*(r+a[k].r)){
temp+=1<<k;
}
}
s.insert(temp);
}
}
for(set<int>::iterator it=s.begin();it!=s.end();it++)v.push_back(*it);
dfs(0,0,0);
cout<<ma;
}level 4 买礼物
对标cf难度：2000
这道题没做出来，数据结构还是太弱了。。
贴一下我队友的题解吧：
数据结构题我就不补了，抱队友大腿
查看16道真题和解析
投递中国农业发展银行等公司10个岗位 >