小清新思维题

CF521D shop

Problem

Solution

首先如果确定了执行的操作，执行顺序一定为赋值、加、乘。赋值操作只保留最大的，并可以转化为加法。每个数的加法操作按从大到小顺序排序后可以转化为乘法。最后将所有乘法操作从大到小排序选前𝑚个即可。

先考虑没有赋值操作，此时的想法就是把加法转为乘法，加法肯定是先选大的再选小的，

那么每个加法的使用前提都是前一个加法已经被使用过了。

因此对于每个加法，它的使用前提都是固定的，即对于每个加法操作，都是把某个值为$x$的数变为一个值为$y$的数，于是加法就可以转化为乘法了。

有赋值操作也是一样的，赋值肯定只会用一次，且只用最大的那个。。

考虑两种情况，如果根本没用到这个赋值，那显然没问题。

如果用到这个赋值，那么会发现先赋值和后赋值虽然每次乘的数不一样，但是最后的结果是一样的（都是加了个前缀和）。

这样可以把它看成一个普通加法再转化成乘法。

牛客挑战赛73 E S 老师的礼物

Problem

Solution

将$i$与$a_i$连边，$a[a_i]>i或a_i=i$显然不合法；

CF516D Drazil and Morning Exercise

Problem

Solution

首先一个结论：每个点在树中距离最远的点一定是直径中的一个点。

这样简单处理处$f_i$，有一个trick：只需要把$f_i$从大到小加入，然后two-pointers，维护当前是否联通，联通即将ans对两个指针位置差取max.

CF505E Mr. Kitayuta vs. Bamboos

Problem

Solution

显然可以先二分答案。

先抛开每天砍几次的限制，二分最大的那棵的高度之后，我们可以得知每棵柱子总计要被砍多少长度，进而求出总次数，先把这个判掉，如果总次数之和大于 $mk$，显然不行。

$p$就砍$p$，因此这样把每个竹子在第几轮操作处理好，然后像这样判断（注意是从后往前）：

	sum = 0;
	for(LL i = m;i >= 1;i --){
		sum += val[i];
		if(sum > k * (m - i + 1)) return 0;
	} return 1;

CF516E Drazil and His Happy Friends

Problem

Solution

• 
• 然后现在
  
  于是问题变成了：