cf edu31
A
题目要求
给出需要读书的总时间 以及每天剩余的时间 问多少天能读完
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| using namespace std; int main(){ // freopen("input.txt","r",stdin); int n,t,i; scanf("%d%d",&n,&t); for(i=1;i<=n;i++){ int x; scanf("%d",&x); int free=86400-x; t-=free; if(t<=0) break; } printf("%d\n",i); return 0; }
|
思路
直接模拟
B
题目要求
定义一串字符的encode为多个连续1的个数
给出encode的数字和解码前的大小n 问能否存在一种解码前的数字使得解码后是给出的数字
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| using namespace std; int main(){ // freopen("input.txt","r",stdin); int n,len; scanf("%d%d",&n,&len); int sum=0; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); if(i==1) sum+=x; else sum+=1+x; } if(sum==len) puts("YES"); else puts("NO"); return 0; }
|
思路
直接模拟
C
题目要求
有n个车站(车站编号为1~n) 满足Bertown Transport Law:
1.对于每个车站i 一定有目的地车站pi(允许pi=i)
2.对于每个车站i 存在唯一的pj=i
舒适度是有序数对(x, y)的数量 使得从车站x出发能够到达车站y(允许x=y)
总统即将来访 市长想要提升舒适度 便试图改造线路
他能够改变某些车站的pi值 但他最多调整两个 且调整后的车站仍满足Bertown Transport Law 求最大舒适度
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| using namespace std; int n; int p[maxn],vis[maxn]; int main(){ // freopen("input.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); mm(vis,0); LL max1=0,max2=0; LL ans=0; for(int i=1;i<=n;i++){ if(vis[i]) continue; LL cnt=1; vis[i]=1; int x=p[i]; while(x!=i){ cnt++; vis[x]=1; x=p[x]; } ans+=cnt*cnt; if(cnt>=max1){ max2=max1; max1=cnt; } else if(cnt>max2 && cnt<max1) max2=cnt; } ans+=2LL*max1*max2; printf("%lld\n",ans); return 0; }
|
思路
可以看出每次操作会最多会改变2个环 假设原本环分别为a和b
那么合并后(a+b)²-(a²+b²)=2ab
所以我们只要找到最大的2个环把她们合并起来即可 对结果合并的影响就是增加2ab
D
题目要求
有n种颜色的球和n个箱子 每种颜色的球有ai个 一开始所有球都在第一个箱子里
最后要满足的状态为:箱子i里包含所有颜色为i的球 问消耗的最小总代价
可以进行如下操作：
每次从一个非空箱子中取出所有球 代价为球的数量 把他们分成2(3)份放到2(3)个非空箱子中
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| using namespace std; int n; priority_queue<ll,vector<ll>,greater<ll> >Q; int main(){ // freopen("input.txt","r",stdin); ll res=0; scanf("%d",&n); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); Q.push(x); } if(n%2==0) Q.push(0); while(Q.size()>1){ ll t1=Q.top(); Q.pop(); ll t2=Q.top(); Q.pop(); ll t3=Q.top(); Q.pop(); res+=t1+t2+t3; Q.push(t1+t2+t3); } printf("%lld\n",res); return 0; }
|
思路
类似于哈夫曼树
贪心可以发现 排序后要使小的数字尽量多的来回取出
由于这里的k=2/3 相当于一个二叉+三叉哈夫曼树 为了简化 如果n是偶数 我们加一个0 不影响结果
每次取三个数字 代价为他们的颜色对应的数量和 直到合并成1个数字 输出结果
F
转跳链接
