链接：https://codeforces.com/gym/101606
A - Alien Sunset
暴力枚举小时即可。
#include<bits/stdc++.h> using namespace std; const int maxn=23; int n; int h[maxn],r[maxn],s[maxn]; inline bool dark(int id,int time) { if(r[id]<s[id]) { if(r[id]<time && time<s[id]) return 0; else return 1; } if(r[id]>s[id]) { if(s[id]<=time && time<=r[id]) return 1; else return 0; } } int main() { cin>>n; int mx=0; for(int i=1;i<=n;i++) cin>>h[i]>>r[i]>>s[i], mx=max(h[i],mx); for(int time=0;time<mx*1825;time++) { bool ok=1; for(int i=1;i<=n;i++) if(!dark(i,time%h[i])) ok=0; if(ok) { cout<<time<<endl; return 0; } } cout<<"impossible"<<endl; }
B - Breaking Biscuits - (Undone)
C - Cued In - [水]
#include<bits/stdc++.h> using namespace std; int n; string s; map<string,int> mp; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); mp["red"]=1, mp["yellow"]=2, mp["green"]=3, mp["brown"]=4, mp["blue"]=5, mp["pink"]=6, mp["black"]=7; cin>>n; int red=0, sum=0, mx=0; for(int i=1;i<=n;i++) { cin>>s; mx=max(mx,mp[s]); if(s=="red") red++; else sum+=mp[s]; } if(red==n) cout<<"1 "; else if(red==0) cout<<sum<<' '; else cout<<red*(mx+1)+sum<<' '; }
D - Deranging Hat - (Undone)
E - Education - [贪心]
$O(n^2)$ 时间复杂度的贪心。
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> P; #define fi first #define se second const int maxn=5e3+10; int n,m; P s[maxn]; int ans[maxn]; struct F{ int id; int capa,rent; bool operator<(const F& o) { return capa>o.capa; } }f[maxn]; bool vis[maxn]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&s[i].fi), s[i].se=i; sort(s+1,s+n+1,greater<P>{}); //for(int i=1;i<=n;i++) printf("%d %d ",s[i].fi,s[i].se); for(int i=1;i<=m;i++) f[i].id=i; for(int i=1;i<=m;i++) scanf("%d",&f[i].capa); for(int i=1;i<=m;i++) scanf("%d",&f[i].rent); sort(f+1,f+m+1); //for(int i=1;i<=m;i++) printf("%d: %d %d ",f[i].id,f[i].capa,f[i].rent); memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { int mn=1e3+50, mnid=0; for(int j=1;j<=m && f[j].capa>=s[i].fi;j++) { if(vis[j]) continue; if(f[j].rent<mn) { mn=f[j].rent; mnid=j; } } vis[mnid]=1; ans[s[i].se]=f[mnid].id; } bool ok=1; for(int i=1;i<=n;i++) if(ans[i]==0) ok=0; if(ok) for(int i=1;i<=n;i++) printf("%d ",ans[i]); else printf("impossible"); cout<<endl; }
F - Flipping Coins - [概率DP]
H - Hiking - (Undone)
I - I Work All Day - (Undone)
J - Just A Minim - [水]
#include<bits/stdc++.h> using namespace std; int n; double t[20]; int main() { t[0]=2.0; t[1]=1.0; t[2]=1.0/2.0; t[4]=1.0/4.0; t[8]=1.0/8.0; t[16]=1.0/16.0; cin>>n; double res=0.0; for(int i=1,x;i<=n;i++) { scanf("%d",&x); res+=t[x]; } printf("%.7f ",res); }