Codeforces Round #606(B-D)
Dashboard – Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4) – Codeforces
B. Make Them Odd
題意: 一個數組，每次選擇一個數，將數組中的這個數都減半，問多少次數組就所有數字都是奇數
題解：將最後變成的奇數相同的數組分成一組，然後答案加上最大的呢個數需要多少次變成奇數即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=5e5+5; const ll inf=1e18; const ll mod=998244353; ll a[N]; unordered_map<ll,ll> mp,maxn; ll solve(ll x){//求出這個數組最後變成的奇數是幾 ll pt=1; ll maxn=-inf; while(pt<x){ pt*=2; if(x%pt==0) maxn=max(maxn,pt); } return x/maxn; } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ ll n;cin>>n; vector<ll> q; for(ll i=1;i<=n;i++){ cin>>a[i]; if(a[i]%2) continue; ll res=solve(a[i]); if(!mp[res]){ mp[res]=1;q.push_back(res); } maxn[res]=max(maxn[res],a[i]); } ll ans=0; for(ll i=0;i<q.size();i++){ ll pt=maxn[q[i]]/q[i]; while(pt>1){ pt/=2;ans++; } mp[q[i]]=maxn[q[i]]=0; } cout<<ans<<endl; } }
C. As Simple as One and Two
題意：給出一個字元串，每次選擇一個字元刪除，最後保證字元串中不出現「one”和」two”,問最少刪除幾個字元。
題解：分情況討論
- one和two單獨出現的時候，刪除中間的，這樣可以防止出現」oneeee「這種情況。
- one和two一起出現，一種特殊情況，twone，這個時候我們刪除中間的”o”。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=5e5+5; const ll inf=1e18; const ll mod=998244353; ll a[N]; unordered_map<ll,ll> mp,maxn; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ string s;cin>>s; ll sum=0; vector<ll> ans; if(s.size()==1){ cout<<"0"<<endl<<endl; continue; } for(ll i=0;i<s.size()-2;){ if(s[i]=='o'&&s[i+1]=='n'&&s[i+2]=='e'){//單獨出現 sum++;ans.push_back(i+1);i+=3; } else if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'){//一起出現的特殊情況 if(i+4<s.size()){//確定好邊界，防止訪問越界 if(s[i+3]=='n'&&s[i+4]=='e'){ sum++;ans.push_back(i+2);i+=5; } else{ sum++;ans.push_back(i+1);i+=3; } } else{ sum++;ans.push_back(i+1);i+=3; } } else i++; } cout<<sum<<endl; for(ll i=0;i<ans.size();i++) cout<<ans[i]+1<<" "; cout<<endl; } }
D. Let’s Play the Words?
題意：給出n個01字元串，將他們按照某種順序排序，要求如果前一個字元串是什麼結尾，後一個字元串就是什麼開頭。比如：前一個是001，1結尾後一個也要是1開頭，可以選擇將其中的一些字元串翻轉，要求翻轉後的字元串不能與原有的相同，問最少翻轉幾次
題解：分成幾種類型的字元串，01，10，0，1，00，11，將其中00，0分為一類，11，1分為一類，首先，只要存在01，或者10，那麼00，0，11，1一定能找到位置，所以我們只需要判斷01和10即可，如果如果不存在01和10那麼 {00，0}和{11，1}只能存在一個，如果存在01，10就判斷能不能有正確答案即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=5e5+5; const ll inf=1e18; const ll mod=998244353; ll a[N]; string s[N]; ll sum[3][3],le[3]; unordered_map<string,ll> mp; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ ll n;cin>>n; memset(sum,0,sizeof(sum));//清零 memset(le,0,sizeof(le)); mp.clear(); vector<ll> p,q; for(ll i=1;i<=n;i++){ cin>>s[i]; mp[s[i]]=1; if(s[i].size()==1) le[s[i][0]-'0']++;//存儲0出現的位置 else sum[s[i][0]-'0'][s[i][s[i].size()-1]-'0']++;//存儲1出現的位置 if(s[i][0]=='0'&&s[i][s[i].size()-1]=='1'&&s[i].size()>1) p.push_back(i);//存儲01出現的位置 else if(s[i][0]=='1'&&s[i][s[i].size()-1]=='0'&&s[i].size()>1) q.push_back(i);//存儲10出現的位置 } ll flag=0;//用來判斷{00,0}，和{11,1}出現的個數 ll pt=0; if(le[0]||sum[0][0]) flag++; if(le[1]||sum[1][1]) flag++; vector<ll> ans; if(sum[0][1]||sum[1][0]){ if(sum[0][1]>sum[1][0]){ ll px=(sum[0][1]+sum[1][0])/2; ll x=abs(sum[1][0]-px); ll cnt=0; for(ll i=0;i<p.size(),cnt<x;i++){ string st=s[p[i]]; reverse(st.begin(),st.end()); if(mp[st]) continue;//判斷翻轉後是否存在 ans.push_back(p[i]); cnt++; } if(cnt!=x){ pt=1; } } else{ ll px=(sum[0][1]+sum[1][0])/2; ll x=abs(sum[0][1]-px); ll cnt=0; for(ll i=0;i<q.size(),cnt<x;i++){ string st=s[q[i]]; reverse(st.begin(),st.end()); if(mp[st]) continue; ans.push_back(q[i]); cnt++; } if(cnt!=x){ pt=1; } } } else if(flag==2){//如果01，10一個也沒有但是{00.0},{11,1}都存在則不可以 pt=1; } if(pt) cout<<"-1"<<endl; else { cout<<ans.size()<<endl; for(ll j=0;j<ans.size();j++) cout<<ans[j]<<" "; cout<<endl; } } }
