winter week3 day3
2024牛客寒假算法基础集训营3
A 智乃与瞩目狸猫、幸运水母、月宫龙虾
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { string a,b; cin>>a>>b; int c='a'-'A'; if(a[0]>='A'&&a[0]<='Z')a[0]+=c; if(b[0]>='A'&&b[0]<='Z')b[0]+=c; if(a[0]==b[0])cout<<"Yes\n"; else cout<<"No\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
B智乃的数字手串
思路：好像说是直接判n奇偶就行，刚开始有猜过但是没敢这样写hh。
要求相邻数和为偶数才能操作，那把所有数分两类奇和偶。当奇偶交替出现，且有偶数个数时是败局。那就要尽可能消除连续的奇偶性相同的数，记要消除的总个数为a。
交换的话，若两个数奇偶相同，交换的话没有意义。若不同，枚举所有情况可发现最后的可操作相邻对数只会偶数倍增减，增减偶数次操作相当于结果没变，那就没必要交换。
消除完后剩下的数，判断是否需要再操作一次使得个数为偶，需要的话消除总个数再加一
最后在判断a的奇偶性即可
（qwq奇是qcjj啦
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n,c=0; cin>>n; vector<int>ve(n); for(int i=0;i<n;++i){ cin>>ve[i]; if(i&&ve[i]==ve[i-1])c++; } if((n-c)%2)c++; if(c%2)cout<<"qcjj\n"; else cout<<"zn\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
Dchino's bubble sort and maximum subarray sum(easy version)
思路：k最大为2，那就狠狠暴力啦
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n,k; cin>>n>>k; vector<int>ve(n),s; for(int i=0;i<n;++i)cin>>ve[i]; s=ve; int ans=0; if(k==1){ for(int i=0;i<n-1;++i){ swap(ve[i],ve[i+1]); int x=0; for(int j=0,c=0;j<n;++j){ if(c+ve[j]>0)c+=ve[j]; else c=0; x=max(x,c); } ans=max(ans,x); ve=s; } }else{ int x=0; for(int i=0,c=0;i<n;++i){ if(c+ve[i]>0)c+=ve[i]; else c=0; x=max(x,c); } ans=max(ans,x); } if(ans==0){ int x=ve[0]; for(int i=1;i<n;++i)x=max(x,ve[i]); ans=x; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } return 0; }
G智乃的比较函数(easy version)
思路：n最大为2，直接判就可以。
判断下给定条件的相反条件是否成立即可。
若x<y成立，那x>=y和y<x就不能成立
若x>=y成立，那x<y就不能成立
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n; cin>>n; bool ok=true; vector<vector<int>>ve(4,vector<int>(4)); for(int i=0;i<n;++i){ int x,y,z; cin>>x>>y>>z; if(x==y&&z==1)ok=false; if(x==y)continue; if(z==0)z=-1; if(z==-1){ if(ve[x][y]!=0&&ve[x][y]==1)ok=false; }else{ if(ve[y][x]!=0&&ve[y][x]==1)ok=false; if(ve[x][y]!=0&&ve[x][y]==-1)ok=false; } ve[x][y]=z; } if(ok)cout<<"Yes\n"; else cout<<"No\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
H智乃的比较函数(normal version)
思路：n最大为50，但是点数只有3，还是判断所有的相反条件是否成立
若x<y成立，那x>=y和y<x就不能成立；有另一点z，x>=z&&z>=y、y<z&&z<x不能成立
若x>=y成立，那x<y就不能成立；有另一点z，x<z&&z<y不能成立
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; struct E{ int x,y,z; }; void solve() { int n; cin>>n; bool ok=true; vector<E>g(n); vector<vector<int>>ve(4,vector<int>(4)); for(int i=0;i<n;++i) { cin >> g[i].x >> g[i].y >> g[i].z; int x,y,z; x=g[i].x,y=g[i].y,z=g[i].z; if(z==0)z=-1; ve[x][y]=z; } for(int i=0;i<n;++i){ int x,y,z; x=g[i].x,y=g[i].y,z=g[i].z; if(x==y&&z==1)ok=false; if(x==y)continue; if(z==0)z=-1; int zz=6-x-y; if(z==-1){ if(ve[x][y]==1)ok=false; if(ve[x][zz]==1&&ve[zz][y]==1)ok=false; }else{ if(ve[y][x]==1)ok=false; if(ve[x][y]==-1)ok=false; if(ve[x][zz]==-1&&ve[zz][y]==-1)ok=false; if(ve[y][zz]==1&&ve[zz][x]==1)ok=false; } // ve[x][y]=z; } if(ok)cout<<"Yes\n"; else cout<<"No\n"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
J智乃的相亲活动
思路：期望=第i个人被选上的概率*1=（1-第i个人没有被选上的概率pi）*1
记bij为第i个人的第j个心动对象（相互心动），第j个心动对象有cnt[bij]个心动对象，那么pij为第j个心动对象不选i的概率，pij=（cnt[bij]-1）/cnt[bij]，那么pi=pi1*pi2*...*pij...
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n,m,k; cin>>n>>m>>k; vector<vector<int>>ve(n+m+1); for(int i=0;i<k;++i){ int u,v; cin>>u>>v; v+=n; ve[u].push_back(v); ve[v].push_back(u); } double ans1=0,ans2=0; for(int i=1;i<=n;++i){ double s=1; for(auto v:ve[i]){ double c=ve[v].size(); s*=(c-1)/c; } ans1+=1-s; } for(int i=n+1;i<=n+m;++i){ double s=1; for(auto v:ve[i]){ double c=ve[v].size(); s*=(c-1)/c; } ans2+=1-s; } cout<<"float\n"; cout<<fixed<<setprecision(8)<<ans1<<' '<<ans2; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } return 0; }
L智乃的36倍数(easy version)
思路：这个数据范围，当然先暴力
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n; cin>>n; vector<string>ve(n); int ans=0; for(int i=0;i<n;++i)cin>>ve[i]; for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ if(i==j)continue; string c=ve[i]+ve[j]; int cc= stoi(c); if(cc%36==0)ans++; } } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } return 0; }
M 智乃的36倍数(normal version)
思路：
酱酱，看完这些公式应该就比较好想了，记cnt[v]为v的位数，要找到f（x，y）%36==0，其实就是（x*10cnt[y]+y）%36==0，由上面的公式推得（x*10cnt[y]%36+y%36）%36==0，简化为（a+b）%36==0
可以预处理出f[i][j]表示乘上10j后对36取模为i的数的个数，那么对于每个y，可以直接求出b和a的个数，统计总的a的个数即为答案
#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=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int MAXN=1e8+5; const double eps=1e-12; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void solve() { int n; cin>>n; vector<int>ve(n); for(int i=0;i<n;++i)cin>>ve[i]; vector<vector<int>>f(40,vector<int>(25)); vector<int>g(30); g[0]=1; for(int i=1;i<=20;++i)g[i]=g[i-1]*10%36; for(int j=0;j<n;++j){ for(int i=0;i<=19;++i){ int x=((ve[j]%36)*g[i])%36; f[x][i]++; } } int ans=0; auto P=[](int x){ int c=0; while(x){ c++,x/=10; } return c; }; for(int i=0;i<n;++i){ int c=(36-ve[i]%36)%36; int cnt=P(ve[i]); int x=(((ve[i]%36)*g[cnt])%36+ve[i]%36)%36; if(x==0)ans--; ans+=f[c][cnt]; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; // cin>>t; while(t--){ solve(); } return 0; }