Codeforces Round #653 (Div. 3)

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; }