1.29 vp Educational Codeforces Round 142 (Rated for Div. 2)

A - GamingForces

题意

有n只怪兽，每个怪的血量是\(a_i\)，有两种操作：
1.直接消灭这只怪
2.消灭两只血量为1的怪
问最少需要多少次操作可以将怪全部杀死

思路

可以想到，操作二只有在血量为1的怪的数量大于1的情况下才有贡献，血量为1的怪数量越多，用操作二的收益就越大。故而统计血量为1的怪数目除2，剩下的都用操作1即可

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1);
	int t = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		if (a[i] == 1) t ++;
	}
	
	t /= 2;
	int ans = t + n - t * 2;
	cout << ans << endl;
}

B - Stand-up Comedian

题意

有四种笑话，每种笑话数量分别为a1,a2,a3,a4。现在有两个观众x, y，他们的愉悦值初始都为0，如果有一个人的值为负数则游戏结束，或者所有可以讲的笑话都讲完了游戏也结束。
第一种笑话两个人值都+1
第二种笑话x + 1, y - 1
第三种笑话x - 1, y + 1
第四种笑话x - 1, y - 1
问在游戏结束的时候最多讲了多少个笑话

思路

首先答案肯定包括整个a1,因为愉悦值是增加的
然后a2,a3相互抵消，相当于两人愉悦值不减的情况下可以多听的笑话数量，多听的数量就是2 * min(a2, a3)
最后若想结束游戏，一是将a1变成负数也就是需要a1 + 1个减愉悦值的笑话，若没有足够数量，那就是max(a2, a3) - min(a2, a3) + a4

void solve() {
	int a1, a2, a3, a4;
	cin >> a1 >> a2 >> a3 >> a4;
	int ans = 0;
	if (!a1) {
		cout << 1 << endl;
	}else {
		ans = a1 + 2 * min(a2, a3);
		
		if (a2 > a3) swap(a2, a3);
		
		ans += min(a1 + 1, a3 - a2 + a4);
		
		cout << ans << endl;
	}
}

C - Min Max Sort

题意

给出一个长度为n的排列，你可以进行操作：任选两个元素，然后将其中小的放在排列最前面，大的放在排列最后面。问最少需要多少次操作可以使序列严格单调递增

思路

经过观察我们可以得知，我们可以将操作理解成每次操作一对儿有序的组合
例如排列165324
若是要操作，首先需要挑出3,4放在两端，然后是2,5,最后是1,6
这样一定是有序的，且最多操作这么多次，也就是n / 2次
什么情况下我们不用进行操作呢？
就是623451，此时3,4有序，2 < 3, 4 > 5,这种情况是可以不需要操作的，只需要操作最外层即可。但若是124356，那么要操作3次，因为它从最里面是错的，后面就都是错的

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1), p(n + 1);            //p用来记录数字下标
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		p[a[i]] = i;                    
	}
	
	int ans = n / 2;
	int l, r, lastl, lastr, lnum, rnum;           //l, r分别为lnum，rnum的下标位置
                                                      //lnum，rnum代表当前操作的数字是哪两个
                                                      //lastl, lastr代表上一次操作的数字下标，用来和现在操作的数字下标进行对比
	
	if (n == 1) {
		cout << 0 << endl;
		return ;
	}
	
	if (n % 2 == 1) {                                                     //奇偶有所不同，奇数开始位置为最中间的元素
		l = p[n / 2], r = p[n / 2 + 2];
		lastl = lastr = p[n / 2 + 1];
		lnum = n / 2, rnum = n / 2 + 2;
	} else {
		l = lastl = p[n / 2], r = lastr = p[n / 2 + 1];
		lnum = n / 2, rnum = n / 2 + 1;
	}
	
	while (lnum >= 1 && rnum <= n) {
		
		if (l > r) {
			break;
		}
		
		if (l <= lastl && r >= lastr) {          //如果符合要求可以减少操作数
			lastl = l, lastr = r;
			lnum --, rnum ++;
			ans --;
		} else break;
		
		if (lnum >= 1 && rnum <= n) l = p[lnum], r = p[rnum];
	}
	
	cout << ans << endl;
}

D - Fixed Prefix Permutations

题意

给出n个排列，每个排列有m个元素。
设美丽度为k，若某个排列p，p1 = 1, p2 = 2, p3 = 3 ... pk = k，则称该排列有k的美丽度
现在有操作：若p，q为排列，则p * q 等于新排列\(r_j\) = \(q_{p_j}\)
问对于n个排列，它和这n个排列操作过最大的k为多少

思路

将每个排列中所有数字的下标记录下来，用trie保存即可，然后对于每个排列查找最大前缀即可

const int N = 500000 + 10, M = 500, INF = 2e9, MOD = 1e9 + 7;
int tr[N][15], idx;
void solve() {
	for (int i = 0; i <= idx; i ++)
		memset(tr[i], 0, sizeof(tr[i]));
	idx = 0;
	
	int n, m;
	cin >> n >> m;
	vector<vector<int> > a(n + 1, vector<int> (m + 1));
	for (int i = 1; i <= n; i ++) {
		vector<int> p(m + 1);                             //保存下标
		
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
			p[a[i][j]] = j;
		}
		
		int x = 0; 
		for (int j = 1; j <= m; j ++) {                        //trie树的保存
			int t = p[j];
			if (!tr[x][t]) tr[x][t] = ++ idx;
			x = tr[x][t];
		}
	}
	
	for (int i = 1; i <= n ; i ++) {
		int ans = m, x = 0;
		for (int j = 1; j <= m; j ++) {
			int t = a[i][j];
			if (!tr[x][t]) {                       //查找最大前缀在哪
				ans = j - 1;
				break;
			}
			x = tr[x][t];
		}
		
		cout << ans << ' ';
	}
	
	cout << endl;
}

总结

思路有时很接近正确答案，但是就差一点点还是写不出来，然后算法部分遗忘的比较多