winter week3 day1
2024牛客寒假算法基础集训营2
ATokitsukaze and Bracelet
#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 a,b,c; cin>>a>>b>>c; int ans=0; if(a==150)ans++; else if(a==200)ans+=2; if(b>=34&&b<=40)ans+=1; else if(b==45)ans+=2; if(c>=34&&c<=40)ans+=1; else if(c==45)ans+=2; 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; }
B Tokitsukaze and Cats
思路：枚举，看猫的4个方向有多少没有围栏
#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+2,vector<int>(m+2)); // vector<PII>g(k); int ans=0; for(int i=0;i<k;++i){ int u,v; cin>>u>>v; ve[u][v]=1; int c=0; for(int j=0;j<4;++j){ int x=u+dx[j],y=v+dy[j]; if(ve[x][y]==0)c++; } ans+=c; } 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; }
CTokitsukaze and Min-Max XOR
思路：
DTokitsukaze and Slash Draw
思路：由于nm范围不大，可以操作每个位置使用每种卡片，跑最短路即可，就是求从0到n-k（位置从上到下为0、n-1、...2、1）
#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=1e5+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<PII>>g(n); vector<PII>ve(m); vector<int>dis(n,1e17),vis(n); for(int i=0;i<m;++i)cin>>ve[i].first>>ve[i].second; for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ int a=ve[j].first,b=ve[j].second; int to=(i+a)%n; g[i].push_back({to,b}); } } dis[0]=0; priority_queue<PII,vector<PII>,greater<PII>>q; q.push({dis[0],0}); while(q.size()){ auto t=q.top(); q.pop(); int u=t.second,dist=t.first; if(vis[u])continue; vis[u]=1; for(auto [v,w]:g[u]){ if(w+dist<dis[v]){ dis[v]=w+dist; q.push({dis[v],v}); } } } if(dis[n-k]==1e17)cout<<"-1\n"; else cout<<dis[n-k]<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; // init(); while(t--){ solve(); } return 0; }
ETokitsukaze and Eliminate (easy)
思路：同hard
#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]; } int ans=0; for(int i=n-1;i>=0;--i){ int c=0,r=ve[i]; while(i>=0&&ve[i]==r)i--,c++; if(i==-1)ans+=c; else ans++; } 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; }
FTokitsukaze and Eliminate (hard)
思路：从后往前枚举，找到要操作的颜色。其实就是统计每个颜色的最后一个的位置的最小值即为操作的颜色，再更新每个颜色的最后一个的位置
#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+1),l(n+1),st(n+1); for(int i=1;i<=n;++i){ cin>>ve[i]; l[i]=st[ve[i]]; st[ve[i]]=i; } vector<int>now; st=vector<int>(n+1,0); int mi=n; for(int i=n;i>=1;--i){ if(!st[ve[i]])now.push_back(i),mi=i; st[ve[i]]=1; } int ans=0; while(mi>0){ ans++; if(mi==1)break; int s=n; vector<int>p; for(auto &v:now){ if(v==0)continue; while(v>=mi&&v!=0)v=l[v]; if(v!=0){ s=min(s,v); p.push_back(v); } } mi=s; now=p; } 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; }
GTokitsukaze and Power Battle (easy)
ITokitsukaze and Short Path (plus)
思路：由权值计算式子可以看出路径长度越长权值越大，那么dist（i，j）最小即为i到j
#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,ans=0; cin>>n; vector<int>ve(n+1),pre(n+1); for(int i=1;i<=n;++i){ cin>>ve[i]; ans+=ve[i]*(2*n-2); } sort(ve.begin()+1,ve.end()); for(int i=1;i<=n;++i)pre[i]=pre[i-1]+ve[i]; for(int i=1;i<=n;++i){ ans+=pre[n]-pre[i]-(n-i)*ve[i]+(i-1)*ve[i]-pre[i-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; }
JTokitsukaze and Short Path (minus)
思路：由权值计算式子可以看出wij为2*min（ai，aj），那么dist（i，j）有两种情况，一种为2*min（ai，aj），另一种为找到权值最小的点q，dist（i，j）= dist（i，q）+ dist（q，j）=4*aq，取较小值即可
#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]; } sort(ve.begin(),ve.end()); int mi=ve[0]; int ans=(n-1)*2*mi,p=4*mi; for(int i=1;i<n;++i){ if(2*ve[i]<p)ans+=2*ve[i]*(n-i-1); else ans+=p*(n-i-1); } cout<<ans*2<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
KTokitsukaze and Password (easy)
思路：n不大，暴力枚举
#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=1e5+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,y; set<int>ans; string s; cin>>n>>s>>y; char a,b,c,d,e; for(a='0';a<='9';++a){ for(b='0';b<='9';++b){ for(c='0';c<='9';++c){ for(d='0';d<='9';++d){ for(e='0';e<='9';++e){ if(a==b||b==c||c==d||a==d||a==c||b==d)continue; string t=s; for(int i=0;i<t.size();++i){ if(t[i]=='a')t[i]=a; else if(t[i]=='b')t[i]=b; else if(t[i]=='c')t[i]=c; else if(t[i]=='d')t[i]=d; else if(t[i]=='_')t[i]=e; } if(n>1&&t[0]=='0')continue; int x=stoi(t); if(x%8==0&&x<=y)ans.insert(x); } } } } } cout<<ans.size()<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; // init(); while(t--){ solve(); } return 0; }