Codeforces Round 1004 (Div. 2)(A-E)

题目链接：Dashboard - Codeforces Round 1004 (Div. 2) - Codeforces

A. Adjacent Digit Sums

思路

只有两种情况：n+1之后没有进位，y-x=1。n+1之后进位(y-x-1)%9==0。

代码

void solve(){int x,y;cin>>x>>y;if(y-x==1){cout<<"YES\n";return;}int t=x-y+1;if(t>=0&&t%9==0){cout<<"YES\n";return;}cout<<"NO\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

B. Two Large Bags

思路

设了个1e5没算时间复杂度T了一发。。。。

根据题意的操作，n个x我们可以留下2个分别到两个袋子，n-2个x变成(x+1)，一直往下推直到有一个数只有一个那么就不可能得到两个完全相同的袋子，否则则会得到两个相同的袋子

代码

void solve(){int n;cin>>n;vi a(n+10);vi mp(10001,0);for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}for(int i=1;i<=10000;i++){if(mp[i]>1){mp[i+1]+=(mp[i]-2);}if(mp[i]==1){cout<<"NO\n";return;}}cout<<"YES\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

C. Devyatkino

思路

原来直接暴力就可以了，，，，，

这题是有一定的规律的，首先出现7答案为0，其他我们发现答案最大是7，只要一直加999...，让最高位从0变成7就行对于所有数（题目给定范围n>=10）都成立，剩下的情况我们对每位数变成7要从两个方面考虑，那就是个位的数和其他，

对于个位数变成7，我们只需要一直加9就可将其变为7

对于其他位上的数为x，如果6>=x>=0，那么我们就能加99...使其进位到7，这还与这位数之后的数的大小有关

如果是x=8，例如8002，我们要先将2给消掉加两个9999，变成28000，再加9999变成37999即可

对于x=9我们发现无论怎么操作其结果是>7的

代码

暴力代码（我求求了建议下次把这个给卡掉哈）

bool check(int x){while(x){if(x%10==7) return true;x/=10;}return false;
}
void solve(){int n;cin>>n;int cnt=10;for(int i=1;i<=10;i++){int d=pow(10,i);d--;int x=n;int t=0;while(!check(x)){t++;x+=d;}cnt=min(cnt,t);}cout<<cnt<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){string s;cin>>s;int n=s.size();int ans=7;auto bol=[&](int st)->int{int x=0;for(int i=st+1;i<n;i++){x*=10;x+=(s[i]-'0');}return x;};for(int i=0;i<n;i++){if(s[i]=='7'){ans=0;}}if(s[n-1]=='8') ans=min(ans,1ll);if(s[n-1]=='9') ans=min(ans,2ll);if(s[n-1]=='0') ans=min(ans,3ll);if(s[n-1]=='1') ans=min(ans,4ll);if(s[n-1]=='2') ans=min(ans,5ll);if(s[n-1]=='3') ans=min(ans,6ll);if(s[n-1]=='4') ans=min(ans,7ll);if(s[n-1]=='5') ans=min(ans,8ll);for(int i=0;i<n-1;i++){if(s[i]<='6'&&s[i]>='0'){int t=bol(i);if(t>=('7'-s[i])){ans=min(ans,('7'-s[i])+0ll);}else{ans=min(ans,('7'-s[i])+1ll);}}if(s[i]=='8'){ans=min(ans,bol(i)+1ll);}}cout<<ans<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

D. Object Identification

思路

交互题练的还是少了，赛时没做出来

可以发现如果查询结果出现0那么就一定是A，那么怎么询问能够得到这一结果，因为是有向图，我们只需要找到一个不在a中出现的数x，(x,*)查询如果结果是0则A，否则B。如果a是全排列，即所有数都在a中出现，如果是A的话最多有n条边，那么查询出的结果一定是 <n-1 的，那么我们选择查询（1，n）如果结果 >=n-1 则是B，否则是A

总而言之：

如果a不是全排列，查询（x，*）(其中x是不在a中出现的数，*是除x之外[1,n]的所有数)，如果结果是0则是A，否则B

如果a是全排列，查询（1，n）如果结果>=n-1则是B，否则是A

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;int query(int a,int b){cout<<"? "<<a<<" "<<b<<endl;int res;cin>>res;return res;
}void solve(){int n;cin>>n;vi a(n+1);vb b(n+1);for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]=true;}for(int i=1;i<=n;i++){if(b[i]==false){int t=query(i,i==1?2:1);if(t==0){cout<<"! A"<<endl;}else{cout<<"! B"<<endl;}return;}}int x,y;for(int i=1;i<=n;i++){if(a[i]==1) x=i;if(a[i]==n) y=i;}int t1=query(x,y);int t2=query(y,x);if(t1!=t2){cout<<"! A"<<endl;return;}if(t1>=n-1){cout<<"! B"<<endl;}else{cout<<"! A"<<endl;}
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

E. White Magic

思路

我们可以发现的结论：没有0的序列一定成立，有两个0的序列一定不成立

那么答案显然是n-cnt0+1或n-cnt0，(cnt0是0的个数)

关于是否能够将一个0添加进去，我们只需要看最左边的0加进去是否成立即可，因为右边的0成立的话，左边的0一定是成立的

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;vi a(n+10);int cnt0=0;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==0) cnt0++;mp[a[i]]++;}if(mp[0]){mp[0]=1;}else{cout<<n<<"\n";return;}int mex=0;while(mp[mex]) mex++;int mi=inf;for(int i=1;i<=n;i++){if(a[i]==0&&!mp[a[i]]) continue;mp[a[i]]--;if(!mp[a[i]]) mex=min(mex,a[i]);mi=min(mi,a[i]);if(mi<mex){cout<<n-cnt0<<"\n";return;}}cout<<n-cnt0+1<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}