标签：Node int DAY2 long 差分 book MAXN 补题

我补题AK了，但你出言不逊是

非常好的一套题，让我的大脑旋转啊。

不太想开一个文章单独屑，所以扔到随笔里面。

敲字速度有待加强。

说在前面

题目难度单调递减，分数单调递减。果然屑死了。

T1再次读题失误，正确的来说是代码敲得非常抽象。T2DP但没骗到分非常不好，T3场上想出正解了，但推一半搞差分然后还没有过掉，后面跟老师讨论时发现想复杂了。其实T3在推出差分前一步停就是正解，但还是没停下。T4可能是思维难度较小的，敲了个二分拿到15，但同机房有敲if过掉就显得数据很水。

T1-下棋（chess）

看得出来出题人对这个机制的热爱了。

题意一般简单，扔洛谷可能就是红。但为什么没过掉就是一个好问题了。

我现在试图揣测上午的思路，可能是打的时候没有算上进位之后加上来的三星（屑屑屑。

考试的时候成功推出式子，成功打上式子，但没算进位，于是根据有理数乘法法则，搓掉了。

放一下考试的歪解：

#include <bits/stdc++.h> 
#define int long long
using namespace std;
struct Node {
	int x, y;
}book[100005];
bool cmp(Node a, Node b) {
	if(a.x != b.x) return a.x > b.x;
	return a.y < b.y;
}
signed main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		int a,b,c;
		cin >> a >> b >> c;
		int a1 = (a % 3);
		int a2 = (a / 3) + (b % 3);
		int a3 = (a2 + b) / 3 + c;
		int ad = a1 + a2 * 3 + a3 * 18;
		book[i].x = ad;
		book[i].y = i;
	}
	sort(book + 1, book + n + 1, cmp);
	for(int i = 1; i <= n; i ++) {
		cout << book[i].y << " ";
	}
	return 0;
}

老师一开始说可能输入反了，然后转了三回之后发现式子假掉了。于是打式子。

正解：

#include <bits/stdc++.h> 
#define int long long
using namespace std;
struct Node {
	int x, y;
}book[100005];
bool cmp(Node a, Node b) {
	if(a.x != b.x) return a.x > b.x;
	return a.y < b.y;
}
signed main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		int a,b,c;
		cin >> a >> b >> c;
		int a1 = (a % 3);
		int a2 = ((a / 3) + (b % 3)) % 3;
		int a3 = (a / 3 + b) / 3 + c;
		int ad = a1 + a2 * 3 + a3 * 18;
		book[i].x = ad;
		book[i].y = i;
	}
	sort(book + 1, book + n + 1, cmp);
	for(int i = 1; i <= n; i ++) {
		cout << book[i].y << " ";
	}
	return 0;
}

代码个人习惯很重，抱歉（轻轻跪下。

T2-汪洋（BigWater）

当时看到名称的时候惊了，为什么大写就很迷。看题面发现了似乎是出题人藏的彩蛋。

BilibiliWorld 2023，简称BW

正好还是题目名称好哎！彩蛋不错。但 她可以和这些 coser 一起合影，然后发说说羡慕她那可怜的队友，不是集邮之后发给没抢到票的亲友吗？~~（乐我也没抢到票，亲友们也没抢到就很悲~~

闲话见我的珂爱游记，这里不展开说了。

是的这道题又是DP。

又是和昨天一样的问题，想出解法但切不掉。打脸。

希望明天想出解法能切掉。

题目分析后可以发现 Meowowco 走的是矩形，就可以遍历所有边然后求最大值，剪掉四个点就好了（因为是重复计算的所以剪掉

正解：

#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN][MAXN], row[MAXN][MAXN],col[MAXN][MAXN];
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            cin >> a[i][j];
            row[i][j] = row[i][j - 1] + a[i][j];
            col[i][j] = col[i - 1][j] + a[i][j];
        }
    }
    int ans = 0;
    for(int x = 1; x <= n; x ++) {
        for(int y = 1; y <= n; y ++) {
            ans = max(ans, row[1][y] + row[x][y] + col[x][1] + col[x][y] - a[1][1] - a[1][y] - a[x][1] - a[x][y]);
        }
    }
    cout << ans + 100;
    return 0;
}

T3-删数（delnum）

考场想到正解，然后感觉假了就去敲暴力。中间敲了个差分然后发现cnt统计不进去于是骗分。

差分的思路就是设a[0] 为 0，于是后面每一个数的下一个要删的数就是这个数和前一个数的差的绝对值，由于是单调递增的自然数序列，所以差分可以求出来。

很神奇的cnt统计不进去，也就是他无法正确统计一轮而不是一个数字。

不过看了正解之后感受到了差分的麻烦以及时间复杂度高，不优的一个解法还让我敲了最长的时间。

不如退回一步想正解。

正解：

没办法鸭子没法复制又没时间打，只能搞掉图片了。

T4-平分糖果（candy）

这个题一眼枚举，于是Just do it.时间复杂度不算高，但只拿了15哭死。

二分思路很简单，看看代码即可理解（简称太屑了以至于想不出来如何二分切掉这个题

#include <bits/stdc++.h>
#define int long long 
using namespace std;
signed main() {
//	freopen("candy.in", "r",stdin);
//	freopen("candy.out","w",stdout);
	int cnt = 1;
	while(1) {
		int fl = 0;
		int a[20], b[20000];
		for(int i = 1; i <= 6; i ++) {
			cin >> a[i];
			if(a[i] != 0) fl = 1;
		}
		if(fl == 0) return 0;
		cout << "Collection #" << cnt << ":" << endl;
		cnt ++;
		int sum = 0;
		int cnt1 = 0;
		for(int i = 1; i <= 6; i ++) {
			sum += a[i] * i;
			if(a[i] * i != 0) {
			   for(int j = 1; j <= a[i]; j ++) b[++cnt1] = a[i] * i;
			}
		}
//		cout << sum << endl;
//		for(int i = 1; i <= cnt1; i ++) cout << b[i] << endl;
		if(sum % 2 != 0) cout << "Can't be divided.\n\n";
		else {
			sort(b + 1, b + cnt + 1);
			int l = 1, r = cnt1;
	        sum /= 2;
	        int flag = 0;
			while(l < r) {
				int mid = (l + r) / 2;
			//	cout << b[l] << " " << b[r] << " " << b[l] + b[r] << endl;
				if(b[l] + b[r] == sum) {
					cout << "Can be divided.\n\n";
					flag = 1;
					break;
				}
				if(b[l] + b[r] > sum) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			if(flag == 0) cout << "Can't be divided.\n\n";
		}
	}
//	fclose(stdin);
//  	fclose(stdout);
	return 0;
}

很奇怪的是二分最多时间超限，答案错误就很迷惑。老师看到了留个言解释一下罢（摊

昨天二分暴力，今天暴力二分，果然rp守恒。

每个物品的数量有限，所以找出是否存在几个物品的价值与物品总价值的一半相同就可以了，可以抽象成多重背包。

很好的思路。为什么考试写不出来呢？

扔dp正解，思路详细介绍会扔进tj里面的（应该会的吧

#include <iostream>
using namespace std;
const int MAXN = 20005;
int a[10], dp[10][2 * MAXN], col = 0;
int main() {
    while (1) {
		int m = 0;
		for (int i = 1; i <= 6; i++) {
			cin >> a[i];
			m += a[i] * i;
		}
		if (!m) break;
		dp[0][0] = 1;
		for (int i = 1; i <= 6; i++)
			for (int k = 0; k <= a[i]; k++)
				for (int j = k * i; j <= m / 2 + 1; j++)
					dp[i][j] |= dp[i - 1][j - k * i];
		cout << "Collection #" << ++col << ':' << endl;
		if (m % 2 == 0 && dp[6][m / 2] == 1) cout << "Can be divided." << endl;
		else cout << "Can't be divided." << endl;
		cout << endl;
	}
    return 0;
}

赛后总结

总司令不知道什么时候又出现了，大唐盛世如我所愿。

T2出题老师彩蛋非常好，给无聊的做题添加了一点乐子。

这次模拟赛还是不理想啊不理想，究其原因可能是每次推到正解但不打，打一个莫名其妙的代码然后保灵。

希望明天会更好罢。

今天听到好听的神的随波逐流，rp++。

标签：Node,int,DAY2,long,差分,book,MAXN,补题
From： https://www.cnblogs.com/Cherry929/p/18444949

DAY2-补题