Codeforces Round #739 (Div. 3) ABCDEF1 解题思路
2021/8/19 6:07:49
本文主要是介绍Codeforces Round #739 (Div. 3) ABCDEF1 解题思路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces Round #739 (Div. 3)
可能是一开始大佬都写F1去了,我在D写完后发现F过的人数比E多了好多(个位数与十位数),以为F1比较简单,就直接开F1了,但自己分类讨论老是考虑不完整,导致罚时直接垮掉
本来已经不想开E了,结果发现延长了15分钟,尝试着开一开,结果发现很水……现在在怀疑人生了嗯。
A - Dislike of Threes
思路
数据范围小(\(k\le 1000\)),暴力预处理后输出即可。
代码
// URL: https://codeforces.com/contest/1560/problem/0 // Problem: A. Dislike of Threes // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 1000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} vector<int> vec; int ck(int a) { if(a%10==3||a%3==0)return 0; return 1; } void init() { int p=1; while(vec.size()<1000) { if(ck(p)) vec.pb(p); p++; } } void solve() { int n; cin>>n; cout<<vec[n-1]<<'\n'; } int main() { closeSync; init(); multiCase { solve(); } return 0; }
B - Who's Opposite?
思路
根据题意,\(|a-b|\times 2\)可以得出这个环的点数\(n\)
那么两点在环内相互对视的充分必要条件就是\(a\pm\frac n 2=b\)
最后只需要\(c\le n\),便能得出\(c\)对视的点
代码
// URL: https://codeforces.com/contest/1560/problem/B // Problem: B. Who's Opposite? // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 1000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} void solve() { ll a,b,c; cin>>a>>b>>c; if(a>b) swap(a,b); ll n=(b-a)*2; if(b!=(a+n/2-1)%n+1||c>n) { cout<<"-1\n"; return; } cout<<(c+n/2-1)%n+1<<'\n'; } int main() { closeSync; multiCase { solve(); } return 0; }
C - Infinity Table
思路
假设数字\(1\)位于第\(1\)层,数字\(2,3,4\)位于第\(2\)层,……
发现第\(i\)层的数字个数为\(i\times 2-1\)
那么假设当前求的数字\(k\)位于第\(x+1\)层,那么前\(x\)层的总数便是\(x^2\)
由于数字\(k\)比较大,其位于的层数可以直接\(\sqrt {k-1}+1\)得出,或是通过二分得出(二分比较靠谱)
于是我们发现\(k=10^9\)时,其所在层的编号也只有几万,并且数据组数\(T\le 100\),所以这里直接上笨方法,循环处理即可
代码
// URL: https://codeforces.com/contest/1560/problem/C // Problem: C. Infinity Table // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 1000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} void solve() { ll k; cin>>k; ll l=1,r=100000; while(l<=r) { ll mid=l+r>>1; ll t=mid*2-1; ll sum=(1+t)/2*mid; if(sum<k) l=mid+1; else r=mid-1; } //二分出k位于第l层,这种二分方式最终状态为l==r+1 //cout<<r<<' '; k-=(1+r*2-1)/2*r; //也就是r*r k--; int x=1,y=l; if(k==0) { cout<<x<<' '<<y<<'\n'; return; } repp(i,1,l) { k--; x++; if(k==0) { cout<<x<<' '<<y<<'\n'; return; } } repp(i,1,l) { k--; y--; if(k==0) { cout<<x<<' '<<y<<'\n'; return; } } } int main() { closeSync; multiCase { solve(); } return 0; }
D - Make a Power of Two
思路
做法是先找出与\(2^i\)的前缀相同的最长子序列,那么原长度减去最长子序列长度就是要删除的字符个数,最后再加上\(2^i\)减去匹配上的前缀后的长度,也就是需要添加的字符个数
例如对于\(1052\),令其与\(2^{10}=1024\)进行匹配,得出与\(1024\)的前缀相同的最长子序列为\(102\),则说明原数字里的\(5\)需要删除,删除后需要再加一个\(4\)在末尾才能得到\(1024\)
猜想是对\(i=0\sim 62\)(long long最大值为\(2^{63}-1\))的每个\(2^i\)都做一遍匹配,找最小值就是答案——由于\(2^{62}\)次方已经是一个\(19\)位数,所以这个幂次如果再大也只会徒增删除次数
代码
// URL: https://codeforces.com/contest/1560/problem/D // Problem: D. Make a Power of Two // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 1000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} int ar[20],br[20]; int ck(ll a,ll b) { int pa=0,pb=0; while(a) //先按位将a,b倒置在数组中,并求出长度pa,pb { ar[pa++]=a%10; a/=10; } while(b) { br[pb++]=b%10; b/=10; } int j=pb-1,r=0; //j+1为待添加的数量,r为待删除的数量 per(i,pa-1,0) { if(j>=0&&ar[i]==br[j]) j--; else r++; } return j+1+r; } void solve() { int n; cin>>n; int ans=INF; repp(i,0,62) ans=min(ans,ck(n,1LL<<i)); cout<<ans<<'\n'; } int main() { closeSync; multiCase { solve(); } return 0; }
E - Polycarp and String Transformation
思路
发现如果只看每种字符最后一次出现的所在位置,拼接起来后一定就是删除顺序
例如\(haaha\)这个例子,从后往前看,只在每种字符第一次出现时记录下来(或是从前往后看,只在最后一次出现时记录),于是得到删除顺序为\(ha\)
于是根据删除顺序,开始检查是否存在一个原串是按照这个顺序操作得到
由题意得,原串一定是给定字符串的某个前缀,并且最小长度是\(\max\{L[ch_i]\}\),其中\(L[ch_i]\)为每种字符第一次出现的位置
由于长度有\(5\times 10^5\),我们没法枚举每种长度的前缀,再去\(O(n)\)检查这个前缀是否合法
但发现,可以在枚举每种长度的前缀时,只看每种字符出现的次数,模拟删除顺序后便能够得到最终长度,此时只有在得到的长度与输入的字符串长度相同时,再去进行\(O(n)\)检查其合法性,发现这样只需要\(O(26)\)就可以做完一次粗略的check
代码
// URL: https://codeforces.com/contest/1560/problem/E // Problem: E. Polycarp and String Transformation // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 3000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} int l[26],r[26]; int vis[26]; int cnt[26]; string s,t; bool finalcheck(int right) { int pos=right+1; mst(vis,0); for(char c:t) { vis[c-'a']=1; //表示这种字符已经被删除 rep(i,0,right) { if(vis[s[i]-'a']) //如果已经被删除就跳过 continue; if(s[i]==s[pos]) { pos++; } else { return false; } } } return true; } void solve() { cin>>s; int len=s.size(); mst(vis,0); t=""; per(i,len-1,0) //从后向前,第一次出现就记录下这个字符,得到删除序列t { if(!vis[s[i]-'a']) { vis[s[i]-'a']=1; t=s[i]+t; } } mst(l,-1); mst(r,-1); repp(i,0,len) //记录每种字符第一次出现位置与最后一次出现位置 { if(l[s[i]-'a']==-1) l[s[i]-'a']=i; r[s[i]-'a']=i; } int st=0; repp(i,0,26) { if(l[i]!=-1) //对于每种出现过的字符,取第一次出现位置的最大值作为原串的最小长度 st=max(st,l[i]); } mst(cnt,0); repp(i,0,st) //记录前缀每种字符出现的次数 cnt[s[i]-'a']++; while(st<len) { cnt[s[st]-'a']++; int sum=0; repp(i,0,26) sum+=cnt[i]; //第一次是将原串全部拼接上 int r=sum; for(char c:t) { sum-=cnt[c-'a']; //按删除顺序去除该字符的影响 r+=sum; //继续拼接 } if(r==len&&finalcheck(st)) //只要长度对的上,再进行最终检查 { rep(i,0,st) cout<<s[i]; cout<<' '<<t<<'\n'; return; } st++; } cout<<-1<<'\n'; } int main() { closeSync; multiCase { solve(); } return 0; }
F1. Nearest Beautiful Number (easy version)
思路
想的情况有点多,代码写得又臭又长,别人都想得很简单的样子,所以就放个代码在这吧……
待会补补这里的思路
代码
// URL: https://codeforces.com/contest/1560/problem/F1 // Problem: F1. Nearest Beautiful Number (easy version) // Contest: Codeforces - Codeforces Round #739 (Div. 3) // Time Limit: 1000 ms // Memory Limit: 256 MB // Author: StelaYuri // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) #define all(a) (a).begin(),(a).end() #define mst(a,b) memset(a,b,sizeof(a)) #define pb push_back #define eb emplace_back #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF=0x3f3f3f3f; const ll LINF=0x3f3f3f3f3f3f3f3f; const double eps=1e-12; const double PI=acos(-1.0); const ll mod=998244353; const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1}; void debug(){cerr<<'\n';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);} mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count()); ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);} ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;} ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;} ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;} ll ans; ll n; void ck1(int x) { ll d=x; if(d>=n) { ans=min(ans,d); return; } rep(i,1,10) { d=d*10+x; if(d>=n) { ans=min(ans,d); return; } } } int d[15]; void solve() { int k; cin>>n>>k; bool v[10]; mst(v,false); int len=0,m=n,t=0; while(m) { int i=m%10; if(!v[i]) { v[i]=true; t++; } m/=10; d[len++]=i; } if(t<=k) { cout<<n<<'\n'; return; } ans=LINF; if(k==1) { rep(i,1,9) ck1(i); } else { ans=1; rep(i,1,len) ans*=10; rep(i,1,9) ck1(i); int a=d[len-1],b=-1; per(i,len-2,0) { if(d[i]!=a) { b=d[i]; int mn=min(a,b),mx=max(a,b); per(j,i-1,0) { if(d[j]!=a&&d[j]!=b) { if(mn>d[j]) { d[j]=mn; per(k,j-1,0) d[k]=mn; ll ansd=0; per(k,len-1,0) ansd=ansd*10+d[k]; ans=min(ans,ansd); cout<<ans<<'\n'; return; } else if(mx>d[j]) { d[j]=mx; per(k,j-1,0) d[k]=mn; ll ansd=0; per(k,len-1,0) ansd=ansd*10+d[k]; ans=min(ans,ansd); cout<<ans<<'\n'; return; } else { ll ansd=0; repp(k,j,len) { if(d[k]==mn) { per(uu,len-1,k+1) ansd=ansd*10+d[uu]; ansd=ansd*10+mx; per(uu,k-1,0) ansd=ansd*10+mn; ans=min(ans,ansd); break; } } d[i]++; b++; mn=min(a,b); if(a==b)mn=0; per(k,i-1,0) d[k]=mn; ansd=0; per(k,len-1,0) ansd=ansd*10+d[k]; ans=min(ans,ansd); cout<<ans<<'\n'; return; } } } break; } } } cout<<ans<<'\n'; } int main() { closeSync; multiCase { solve(); } return 0; }
这篇关于Codeforces Round #739 (Div. 3) ABCDEF1 解题思路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享