牛客周赛round 43 A~E
A(简单博弈)
如果字符串长度大于1先手必赢。
#include<bits/stdc++.h> using namespace std; using ll = long long; using i64 = long long; using i128 = __int128_t; const ll inf = 1e18; void solve() { string s; cin>>s; if(s.length()==1) cout<<"yukari"<<"\n"; else cout<<"kou"<<"\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll t = 1; //cin >> t; while (t--) solve(); return 0; }
B(模拟)
解释#include<bits/stdc++.h> using namespace std; using ll = long long; using i64 = long long; using i128 = __int128_t; const ll inf = 1e18; void solve() { string s; cin>>s; if(s.length()==1) cout<<"yukari"<<"\n"; else cout<<"kou"<<"\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll t = 1; //cin >> t; while (t--) solve(); return 0; }
C(数学)
俩个素数乘积必为和数,要让极差最小,毫无疑问,就是让所有的数更加平均,只要用最大*最小,次大*次小...
注意n为奇数的时候留最后一位
解释#include<bits/stdc++.h> #define int long long #define y second using namespace std; typedef long long LL; typedef double D; const int N = 2e5 + 10; typedef pair<int, int> Pii; vector<int>s; void solved() { int n; cin>>n; vector<int>a(n); for(int i=0;i<n;i++)cin>>a[i]; sort(a.begin(),a.end()); int l=0,r=n-1; if(n%2==1)r--,s.push_back(a[n-1]); while(l<r){ s.push_back(a[l]*a[r]); l++,r--; } sort(s.begin(),s.end()); cout<<s[s.size()-1]-s[0]<<"\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t=1; while (t--) { solved(); } return 0; }
D(树)
如果n为奇数,肯定是-1
解释#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef double D; const int N = 2e5 + 10; typedef pair<int, int> Pii; vector<int>e[N]; int ans=0; int dfs(int u,int fa){ int res=1; for(auto son :e[u]){ if(son==fa)continue; int k=dfs(son,u); if(k%2==0)ans+=1; else res+=k; } return res; } void solved() { int n;cin>>n; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; e[a].push_back(b); e[b].push_back(a); } if(n&1)cout<<-1; else{ dfs(1,0); if(ans==0){ cout<<-1; } else cout<<ans<<"\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; while (t--) { solved(); } return 0; }
E(组合数)
对于第i位数字,它可以充当k位里面的第j位,如果判断其充当第k位的次数,其贡献就为s[i]*后面n-i个数里面先择k-j位,组合数学
解释#include<bits/stdc++.h> #define int long long #define y second using namespace std; typedef long long LL; typedef double D; const int N = 2e3 + 10; typedef pair<int, int> Pii; int c[N][N]; int mod=1e9+7; int pre[N]; void init(){ for(int i=0;i<=2000;i++){ for(int j=0;j<=i;j++){ if(j==0)c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } } } int qmi(int x,int p){ int res=1; while(p){ if(p&1)res=res*x%mod; x=x*x%mod; p>>=1; } return res; } void solved() { int n,k;cin>>n>>k; string s; cin>>s; int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ int x=n-i; int y=s[i-1]-'0'; if(j==1){ if(k-j>x)continue; ans+=c[x][k-j]*qmi(10,k-j)%mod*y%mod; ans%=mod; } else { x=i-1; int tp=j-1; if(n-i<k-j)continue; if(x<tp)continue; ans+=(c[x][tp]*c[n-i][k-j]%mod)*qmi(10,k-j)%mod*y%mod; ans%=mod; } } } cout<<ans<<"\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t=1; init(); while (t--) { solved(); } return 0; }