2020-2021 Winter Petrozavodsk Camp, Day 5 Almost Retired Dandelion Contest

写个暴力过了某题，完成绝杀。

感觉实际水平还是不够。

[A Assignment Problem]

solution

题面：个人，有种属性，告诉你这些人的这些属性的排序，但不知道属性值。现在要选择个人，每个人挑出一种属性，且不能相同，想让这个属性值总和最大，问哪些人有可能被选？

做法：猜一猜就知道肯定暴力一个个选过来都是有可能的（就是每次选最大的，按某种属性顺序），证明也很容易，反证一下，如果不是，那就必然有一个是冲突的。然后选择那个冲突的，前面一路退回去，则一定更劣，所以证毕。

然后咋办捏，我直接写了个大暴力，就是枚举了排列，一个个找就过了。时间复杂度，可能常数比较小，就直接过了？

[B Lockout vs tourist]

solution

题面：你和 tourist 一起比赛做题，每道题有不同的分值，你们两个每轮同时决策做哪道题，如果选择相同的题目，那么你不得分，比赛继续进行，如果选择了不同的题目，那么你能拿下你选择的这道题的全部分数，比赛结束，tourist 想让你得分最少，你想让得分最多，问在双方均采取最优决策的情况下你的期望得分。

做法：

[C Multiple?]

solution

题面：求一个值域在的长度的序列，使得没有一个子序列（可以不连续）之和是的倍数，其中 .

做法：打了个表，不会证，直接猜答案是。然后分段打表就能过哩。

[D Output Limit Exceeded]

solution

题面：

做法：

[E Smol Vertex Cover]

solution

题面：

做法：

[F Thanks to MikeMirzayanov]

solution

题面：

做法：

[G Remove the Prime]

solution

题面：堆石子，每轮是对某个区间的石子同除一个质数（必须能除），谁不能动谁输。

做法：对每一维质数来看这个游戏，那就是一个个区间段，每次区间减一。归纳法可以证明每个区间的是区间长度，那么根据定理，答案就是全部异或起来。分解质因数我们队直接用的，时间复杂度。

[H Excluded Min]

solution

题面：

做法：

[I Trade]

solution

题面：件商品，每件有一个初始价格，以及你每买一件其他商品它要升的价格。你现在有元，问最多能买几件商品？

数据特殊性：每件商品所会升的价格不同。

做法：肯定是升值越大的越先买，然后表示买前件共买了件的所花费用。注意到数据的特殊，是的级别的，所以最多也就的级别，那就可以暴力背包了。时间复杂度。

[J Increasing or Decreasing]

solution

题面：两个长度为的排列，每次能将某个区间升序或降序，问最多步让第一个排列变成第二个排列的方案。

做法：是容易的，先对第一个排列整个排个序，那从前往后一个个搞，每次将那个数降序来扔到对应位置，然后再对后面整个升序即可。

发现这个过程每次的升序部分都有点蠢，可以证明对应位置的数要么是最小要么是最大，所以不用升序了，每次直接看看是最大还是最小就好了。

时间复杂度。

这题倒是可以看下代码，不然不太好讲清楚。

const int N=500+10;
int n;
int a[N],b[N];
struct P{
	int l,r,op;
	P() {}
	P(res l,res r,res op):l(l),r(r),op(op) {}
}ans[N*N];
int main(){
	n=read();
	for(res i=1;i<=n;i++)a[i]=read();
	for(res i=1;i<=n;i++)b[i]=read();
	res s=0;
	ans[++s]=P(1,n,0),sort(a+1,a+n+1);
	for(res i=1;i<=n;i++){
		if(a[i]==b[i])continue;
		ans[++s]=P(i,b[i],1),ans[++s]=P(i+1,n,0);
	}
	printf("%d\n",s);
	for(res i=1;i<=s;i++)printf("%d %d %c\n",ans[i].l,ans[i].r,ans[i].op?'D':'I');
	return 0;
}