A.Required Remainder

二分

#include<iostream> #include<algorithm> using namespace std; int main() {int T;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;int x,y,n;while(T--){cin>>x>>y>>n;int l=0,r=(n-y)/x;while(l<r){int mid=l+r+1>>1;if(mid*x+y<=n) l=mid;else r=mid-1;}cout<<l*x+y<<endl;}return 0; }

B. Multiply by 2, divide by 6

這題兩個操作：①$?2$②$?6$，那么我們可以發現只要能夠$?3$我們就可以讓他$?6$，每一步操作$?2$就是為了能夠讓該數$?6$，也就是只要進行一步$?2$就應該可以進行一步$?6$，否則就不能滿足題意

#include<iostream> #include<algorithm> #include<string> using namespace std; typedef long long ll; int main() {int T;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--){ll n;cin>>n;if(n==1) cout<<0<<endl;else{int cnt1=0,cnt2=0;bool flag=0;while(n!=1){if(n%6==0) {n/=6;cnt1++;}else{n*=2;cnt2++;}if(cnt2>cnt1+1) break;}if(cnt2>cnt1+1)cout<<-1<<endl;else cout<<cnt1+cnt2<<endl;}}return 0; }

C. Move Brackets

括號題一般都和棧有關，開個棧就解決了

#include<iostream> #include<algorithm> #include<stack> using namespace std; int main() {int T;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--){int n;cin>>n;string a;cin>>a;stack<char> stk;for(int i=0;i<n;i++){if(stk.size()&&stk.top()=='('&&a[i]==')') stk.pop();else stk.push(a[i]);}cout<<stk.size()/2<<endl;}return 0; }

過了上面三個題

D. Zero Remainder Array

這題真dt，小白打cf不知道不能開unordered_map一直tle，我想我$O(n)$的算法為啥tle真的服了
先對原數組取個模(mod)，然后重復最多余數的那個數決定最終答案。

#include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long ll; map<int,int> mp; int main() {int T;scanf("%d",&T);while(T--){int n,k,a,b;scanf("%d%d",&n,&k);mp.clear();ll mmax=0,x=k;for(int i=0;i<n;i++) {scanf("%d",&b);a=b%k;mp[a]++;if(a){if(mmax<mp[a]||(mmax==mp[a]&&a<x)){x=a;mmax=mp[a];}}}ll res=0;if(mmax) res=ll(1ll*mmax*k-x+1);printf("%lld\n",res);}return 0; }

E1.Reading Books (easy version)

直接開三個數組，分情況討論一下就可以了（這題感覺比D還簡單要是D題知道unordered_map被卡，可能能做5個題 。）

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int N=200010; int n,m; int a[N],cnt1,b[N],cnt2,c[N],cnt3; int main() {cin>>n>>m;for(int i=0;i<n;i++){int t,x,y;cin>>t>>x>>y;if(x&&y) c[cnt3++]=t;else if(x==1&&y==0) a[cnt1++]=t;else if(x==0&&y==1) b[cnt2++]=t;else continue;}sort(a,a+cnt1);sort(b,b+cnt2);sort(c,c+cnt3);if(min(cnt1,cnt2)+cnt3<m) cout<<-1<<endl;else{int res=0;int i=0,j=0,k=0;while(m){if(k==cnt3){res+=a[i++]+b[j++];m--;}else if(i==cnt1||j==cnt2){res+=c[k++];m--;}else{if(c[k]<a[i]+b[j]) res+=c[k++];else res+=a[i++]+b[j++];m--;}}cout<<res<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #653 (Div. 3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。