vp的 感觉整场挺智慧
A - Alternately
找有没有连续的男女
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n;cin>>n; string s;cin>>s; int flag=1; for(int i=0;i<s.length();i++){ if(i!=0&&s[i]==s[i-1]) flag=0; } if(flag)cout<<"Yes\n"; else cout<<"No\n"; } int main(){ solve(); }
B - Chessboard
输出*的序号
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; char a[10][10]; int ans1; char ans2; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ for(int i=8;i>=1;i--){ for(int j=1;j<=8;j++){ // char ch; cin>>a[i][j]; if(a[i][j]=='*'){ ans1=i; ans2='a'+j-1; } } } cout<<ans2<<ans1; } int main(){ solve(); }
C - Gap Existence
找是否有两个数满足a-b=x
存map里 然后再遍历一遍每个数+x的情况 看看有没有存在的就行了
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long map<int,int> sz; int a[MAXN]; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n,x;cin>>n>>x; for(int i=1;i<=n;i++){ cin>>a[i]; sz[a[i]]++; } int flag=0; for(int i=1;i<=n;i++){ int k=a[i]+x; if(sz[k]>0) flag=1; } if(flag) cout<<"Yes\n"; else cout<<"No\n"; } signed main(){ solve(); }
D - M<=ab
寻找每个数作为因子,去逼近m的数字 比如m=9 i=2的时候,逼近的值就是2*(9/2+1)=10 以此类推,从1遍历到sqrt(m)+1(+1是防止边界出问题) 然后一个一个遍历 如果没有取到就输出-1
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n,m; cin>>n>>m; int ans=INF; int flag=0; if(n==1&&m==1){ cout<<1; return; } for(int i=2;i<=sqrt(m*1.0)+2;i++){ int k=m/i; if(k*i!=m) k++; if(k>n||i>n) continue; if(k*i<m) continue; ans=min(ans,k*i); flag=1; } if(flag==0) cout<<-1; else cout<<ans; } signed main(){ solve(); }
E - Transition Game
题意就是 第i=(1 to n) 轮 A可以随便在黑板上写一个数字j 你再在黑板上写一个x 然后结经过j轮 把x替换成a[x]的操作,如果能让此时的x为i 那么你+1分 求最后的总分
此时我们不难发现 因为A可以随便写无限大的j 你只有让替换的行为形成一个环才行 也就是强连通 单个的也算 i对应的a[i] 看作i->a[i]
毛了个强连通的板子 自己还没学图论 就不贴代码了
F - Simultaneous Swap
在a串和b串中选 ij和ik 分别交换位置,问能否让两个字串一样
我们直接把a看作标准,然后把b变成a
1.首先 这两个串包含的数字数量必须完全一致
2.其次 如果一致,并且有某个数字出现两次 ,那么一定可以 因为就把那个数字当成temp 可以一直交换 然后i和j全选成这个数字 k自由选 来交换
3.如果以上条件均判断过 那就剩下 每个数字都不同的情况 然后判断 、
把一串需要互相交换的数字当作连通块 比如 123 321 那么 13是连通块 2是连通块 如此
我们不难发现 当连通块大小为奇数的时候 比如 123 与 312 连通块内选择一个不变的i 能通过偶数次的交换让b等于a 意思就是 随便选一个j 进行偶数次操作 是不会改变i 又能把i变成j的
所以 奇数的连通块是不用考虑的
偶数的时候 假如说是 12 21 显然不能通过连通块内偶数次交换 一定是奇数
但是 还有情况 就是 123456 与 321654 的时候 我通过两次变换 i选择1 j随便 k选择3和4 b串就会变成623154 a串仍然是123456 很明显 只有连通块变成奇数了
所以我们得出结论 两个偶数的连通块能变成1个奇数的
因此我们只需要判断偶数大小的连通块的数量 数量是奇数就是no 偶数就是yes
使用并查集维护连通块大小
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int f[MAXN],n,m; int a[MAXN],b[MAXN],ta[MAXN],tb[MAXN],t[MAXN]; //ta a中出现数字的个数 tb b中出现数字个数 //t:以i为祖先的连通块大小 void clean(){ for(int i=1;i<=n;i++) f[i]=i; } int find(int x){ if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void add(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy) f[fx]=fy; } void solve(){ cin>>n; clean(); int flag=0,res=1,flag2=0; for(int i=1;i<=n;i++){ cin>>a[i]; ta[a[i]]++; if(ta[a[i]]==2) flag=1; } for(int i=1;i<=n;i++){ cin>>b[i]; tb[b[i]]++; // if(tb[b[i]]>ta[b[i]]) res=0; if(b[i]!=a[i]) { add(a[i],b[i]); } else flag2=1; } for(int i=1;i<=n;i++){ if(tb[i]!=ta[i]) res=0; } if(res==0){ cout<<"No\n"; } else if(flag){ cout<<"Yes\n"; } else{ for(int i=1;i<=n;i++){ int fa=find(b[i]); t[fa]++; } int cnt=0; for(int i=1;i<=n;i++){ if(t[i]%2==0&&t[i]!=0){//找偶数大小的连通块数量 cnt++; } } if(cnt%2==1) cout<<"No\n"; else cout<<"Yes\n"; } } int main(){ solve(); }
- Beginner AtCoder Contest 296 A-Fbeginner atcoder contest 296 contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 315