Codeforces Round 638 (Div. 2)
思路:加的数成等比关系,且第n项大于前n-1项的和,那么最大的一项加上最小的几个即可
#include<bits/stdc++.h> using namespace std; #define int long long int a[110]; deque<int>q; int32_t main(){ int t; cin>>t; while(t--){ int n; cin>>n; int d=n/2; int ans=2; int sum1=0,sum2=0; for(int i=1;i<=n;i++){ if(i<=d-1||i==n){ sum1+=ans; } else{ sum2+=ans; } ans*=2; } cout<<abs(sum1-sum2)<<endl; } return 0; }
思路:可以发现有循环节的数列,且k恰好是循环节的长度一定是成立的
#include<bits/stdc++.h> using namespace std; #define int long long int a[110]; deque<int>q; int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ int n,k; cin>>n>>k; set<int>s; for(int i=1;i<=n;i++){ cin>>a[i]; s.insert(a[i]); } if(s.size()>k){ cout<<"-1\n"; continue; } for(int i=1;;i++){ if(s.size()==k) break; s.insert(i); } cout<<n*k<<"\n"; for(int i=1;i<=n;i++){ for(auto e:s) cout<<e<<" "; } cout<<"\n"; } return 0; }
思路:将原串排序后,若s[k-1]不等于s[0],那么答案为s[k-1],否则,若之后的字符都相等,那均分成k份,s[0]加上最多的那份为答案,否则将之后的所有字符都加在s[0]后为答案;
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n,k;string s; cin>>n>>k>>s; sort(s.begin(),s.end()); if(s[0]!=s[k-1]){ cout<<s[k-1]<<'\n'; }else{ if(s[n-1]!=s[k]){ string ans=s.substr(k-1); cout<<ans<<'\n'; }else{ int c=(n-1)/k; string ans;ans.push_back(s[0]); while(c--)ans.push_back(s[n-1]); cout<<ans<<'\n'; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }
思路:由于要尽可能少的天数,贪心地分裂更多的细胞,每天细胞数为2、4、8...,若最后还剩下细胞为x个,那么可以在某一天后通过增加一天的分裂来得到x(可以发现是一定可以的);那么将所有天数排序后的差分即为每天分裂的细胞数。
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n;cin>>n; vector<int>ans; for(int i=1;i<=n;i*=2){ ans.push_back(i); n-=i; } if(n)ans.push_back(n); sort(ans.begin(),ans.end()); cout<<ans.size()-1<<'\n'; for(int i=1;i<ans.size();++i)cout<<ans[i]-ans[i-1]<<' ';cout<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } return 0; }