水题收割机(不是
A.Stopwatch
题意：
有一个计时器，初始状态为暂停。只有一个按钮，按下可以开始或暂停计时。给出长度为n的序列a i
表示在时刻为a i的时候按下计时器。问执行完n个操作后计时器显示的情况。
思路：
如果n为奇数，说明此时正在计时。
否则，计时器的时间为偶数项减去奇数项的和。
代码：
ll a[1100]; int main() { int n=read; for(int i=1;i<=n;i++) a[i]=read; if(n%2) puts("still running"); else{ ll ans=0; for(int i=2;i<=n;i+=2) ans+=a[i]-a[i-1]; cout<<ans; } return 0; }
B.Arithmetic Decoding
思路：
n很小，考虑直接状压枚举或d f s出所有的情况，判断计算出的数是否和给定的数相等。
大概考点就是如何把二进制的小数转化为十进制的小数吧，参考
代码：
double cul(string str,int j,int len){ int k=j+1; int cetz=0,cetx=-1; long Sumz=0; double Sumx=0; for( ;j>0;j--) { Sumz+=(str[j-1]-'0')*pow(2,cetz); cetz++; } for( ;k<len;k++) { Sumx+=(str[k]-'0')*pow(2,cetx); cetx--; } return Sumz+Sumx; } int main(){ int n=read,d=read; string s;cin>>s; int len=s.size(),j; for(j=0;j<len;j++) if(s[j]=='.') break; double x=cul(s,j,len); double pa=d*1.0/8,pb=1.0-pa; for(int i=0;i<(1<<n);i++){ double a=0,b=1; string res; for(int j=0;j<n;j++){ double c=a+pa*(b-a); if(i&(1<<j)) b=c,res+="A"; else a=c,res+="B"; } if(a==x){ cout<<res<<endl; return 0; } } return 0; }
D.Forced Choice
思路：
每次判断猜测的数是否在给出的数里，在的话输出K E E P，否则输出R E M O V E
代码：
int main() { int n=read,p=read,m=read; rep(i,1,m){ bool flag=0; int k=read; rep(j,1,k){ int x=read; if(x==p) flag=1; } if(flag) puts("KEEP"); else puts("REMOVE"); } return 0; }
F.Conquest
题意：
给出一个图，每个点有点权。从1开始扩张，如果当前扩张到的点的邻接点的值小于当前的总权值和，则可以扩张过去。问能够得到的最大权值。
思路：
优先队列瞎搞的，将每个点的邻接点按照点权从小到大排序，对于不能扩张到的点先存在优先队列里。
感觉写的假的一批，最开始样例1没过都96。
代码：
const int maxn=2e5+100; int n,m,a[maxn]; vector<int>g[maxn]; bool vis[maxn]; priority_queue <PII,vector<PII>,greater<PII> > q; bool cmp(int x,int y){ return a[x]<a[y]; } ll bfs(){ ll ans=a[1]; q.push({a[1],1}); vis[1]=1; while(!q.empty()){ PII u=q.top();q.pop(); int w=u.first,ne=u.second; //cout<<w<<" "<<ne<<endl; if(!vis[ne]&&ans<=w) break; else if(!vis[ne]) ans+=w; for(auto t:g[ne]){ if(vis[t]) continue; if(!vis[t]&&ans>a[t]){ vis[t]=1;ans+=a[t]; } q.push({a[t],t}); } } return ans; } int main() { n=read,m=read; rep(i,1,m){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } rep(i,1,n) a[i]=read; rep(i,1,n) sort(g[i].begin(),g[i].end(),cmp); printf("%lld\n",bfs()); return 0; }
G.Distance
题意：
给出n个点，求曼哈顿距离之和
思路：
经典题了，考虑每个点的x坐标对答案的贡献，y坐标对答案的贡献。
比如x坐标，从小到大排序后，+ x的贡献为x ∗ ( i − 1 )（这个点之前的点）,− x的贡献为− x ∗ ( n − i )（这个点之后的点）
代码：
const int maxn=2e5+100,inf=0x3f3f3f3f; const double eps=1e-5; ll x[maxn],y[maxn]; int main() { int n=read; rep(i,1,n) x[i]=read,y[i]=read; sort(x+1,x+1+n); sort(y+1,y+1+n); ll ans=0; rep(i,1,n){ // cout<<x[i]<<"****"<<y[i]<<endl; ans=ans-x[i]*(n-i)+x[i]*(i-1); //cout<<ans<<" "; ans=ans-y[i]*(n-i)+y[i]*(i-1); //cout<<ans<<endl; } write(ans); return 0; }
I.Vaccine Efficacy
思路：
模拟，好像没有啥细节。
代码：
int sumy,sumn; int y[4],n[4]; int main() { int m=read; rep(i,1,m){ string s;cin>>s; if(s[0]=='Y'){ sumy++; for(int j=1;j<=3;j++){ if(s[j]=='Y') y[j]++; } } else{ sumn++; for(int j=1;j<=3;j++){ if(s[j]=='Y') n[j]++; } } } for(int i=1;i<=3;i++){ double ty=y[i]*1.0/sumy; double tn=n[i]*1.0/sumn; if(ty>=tn) puts("Not Effective"); else printf("%.6f\n",100*(1-ty/tn)); } return 0; }
K Train Boarding
思路：
反正n才100，跑个n 2的不过分吧
代码：
int pos[110],cnt[110]; int main(){ int n=read,l=read,p=read; for(int i=1;i<=n;i++) pos[i]=(2*i-1)*l/2;//,cout<<pos[i]<<endl; int res=0,tmp=0; rep(i,1,p){ int x=read; int minn=inf,t=-1; for(int j=1;j<=n;j++){ int now=abs(pos[j]-x); if(minn>now) minn=now,t=j; else if(minn==now) t=max(t,j); } cnt[t]++; tmp=max(tmp,cnt[t]); res=max(res,minn); } cout<<res<<endl; cout<<tmp<<endl; return 0; }
