CSP模拟赛题解

Aewrxuk / 2023-08-20 / 原文

CSP模拟16
- T1 : 糖果
CSP模拟17
- T1：弹珠游戏
- T2：晚会
CSP模拟18
- T1：The Third Letter
- T2：Ina of the Mountain
CSP模拟19
- T1：Strange Function
- T2：DZY Loves Modification
CSP模拟21
- T1：[CEOI2016] kangaroo
- T2：[JOI 2023 Final] Advertisement 2
- T3：Your
CSP模拟22
- T1：The Child and Toy

CSP模拟16

T1 : 糖果

这道题的思路很巧妙，明白了思路之后可以轻松切掉。既然这是求异或和，那根据异或的性质，如果是分为奇数段，那最后就会消为3段；如果是偶数段，最后会消为2段。特别要注意的是如果最后是两段的话，总的异或和一定为0。对于奇数段，先找到一个前缀的异或和，让它等于总的异或值，然后找到存不存在一个后缀异或和等于前缀（也就是总的异或和），然后这道题就可以轻松的切掉了……
代码实现：

点击查看代码

int n, temp1, temp2, T;
int a[100010], sum1[100010], sum2[100010];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		memset(sum1, 0, sizeof(sum1));
		memset(sum2, 0, sizeof(sum2));
		temp1 = 100010; temp2 = 0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum1[i] = sum1[i-1] ^ a[i];
		}
		for (int i = n; i >= 1; i--)
			sum2[i] = sum2[i+1] ^ a[i];
		if (!sum1[n]) cout << "YES" << '\n';
		else {
			for (int i = 1; i <= n; i++)
				if (sum1[i] == sum1[n]) {
					temp1 = i;
					break;
				}
			for (int i = n; i >= 1; i--)
				if (sum2[i] == sum1[n]) {
					temp2 = i;
					break;
				}
			if (temp1 < temp2) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
	return 0;
}

CSP模拟17

T1：弹珠游戏

这道题要求最大值和最小值的和最小的情况，于是我们考虑贪心，也就是我们尽量让能拿全的人先全部拿全，这样才可以让当前发的弹珠发挥最大的作用，因此我们在考虑当前弹珠发挥的作用时，不需要考虑已经含有这种弹珠的人。
举个例子:
当前要发的弹珠是 \(R\) ，那么我们只需要去考虑 \(G,B,GB\) 和没有弹珠的人，优先考虑 \(GB\) ，其次是剩余的有弹珠的，最后是没有弹珠的。分类讨论即可。记得开 \(long\ long\)。
代码实现：

点击查看代码

#define int long long
#define R 1
#define G 2
#define B 3
#define RB 4
#define RG 5
#define BG 6
using namespace std;
const int mod = 998244353;
int n, ans = 1;
int cnt[10];
char op;
signed main() {
	// freopen("../cin/a.txt","r",stdin);
	cin >> n; cnt[0] = n;
	for (int i = 1; i <= n*3; i++) {
		cin >> op;7
		if (op == 'R') {
			if (cnt[BG]) {
				ans = ans * cnt[BG] % mod;
				cnt[BG]--;
			} else if (cnt[G]) {
				ans = ans * cnt[G] % mod;
				cnt[G]--;
				cnt[RG]++;4/..0516602
			} else if (cnt[B]) {
				ans = ans * cnt[B] % mod;
				cnt[B]--;
				cnt[RB]++;
			} else {
				ans = ans * cnt[0] % mod;
				cnt[R]++;
				cnt[0]--;
			}
		}
		if (op == 'B') {
			if (cnt[RG]) {
				ans = ans * cnt[RG] % mod;
				cnt[RG]--;
			} else if (cnt[R]) {
				ans = ans * cnt [R] % mod;
				cnt[R]--;
				cnt[RB]++;
			} else if (cnt[G]) {
				ans = ans * cnt[G] % mod;
				cnt[G]--;
				cnt[BG]++;
			} else{
				ans = ans * cnt[0] % mod;
				cnt[0]--;
				cnt[B]++;
			}
		}
		if (op == 'G') {
			if (cnt[RB]) {
				ans = ans * cnt[RB] % mod;
				cnt[RB]--;
			} else if (cnt[R]) {
				ans = ans * cnt[R] % mod;
				cnt[R]--; cnt[RG]++;
			} else if (cnt[B]) {
				ans = ans * cnt[B] % mod;
				cnt[B]--; cnt[BG]++;
			} else {
				ans = ans * cnt[0] % mod;
				cnt[0]--; cnt[G]++;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

T2：晚会

题目说的是让你去判断能否满足不存在“不友好”的关系，如果能满足，则输出所有人的之间的 \(C(i,j)\) 的和；不满足则输出 \(-1\) 。题目定义“不友好”的关系是不让两个人之间的关系小于另外一个人与两人分别的关系，关键就在于想到怎么判断。
答案是用类似于 \(Kruskal\) 建最大生成树的思想，去实现这一过程。具体的，先将已知的边权按从大到小排序，然后一条条去判断，如果边连的两个点均出现在同一个连通块中（可以用并查集实现），需要判断这条边的权值是不是小于当前连通块的最小边权（主要是对于存在相同权值的边考虑），如果小于最小边权，那么就可以输出 \(-1\) 了（因为是从大到小去加边，如果在一个连通块那么一定会出现“不友好”的关系）。如何求最后的答案，在从大到小判断时，如果是没在连通块里的点，那么连上这条边后，相当于给两连通块里的点都连了一条边， \(ans+=size[i]*size[j]*w(size 是连通块的大小，w 是加的权值)\)，最后判断一下连通块之间的关系和即可（具体看代码实现）。记得开 \(long\ long\)。
代码实现：

点击查看代码

struct node {
	int from, to, val;	
	friend bool operator <(node x1, node x2) {
		return x1.val > x2.val;
	}
} edge[M];
int n, m, ans, cnt;
int fa[M], vis[M], minn[M], size[M], bel[M];
int Find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = Find(fa[x]);
}
signed main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		fa[i] = i, size[i] = 1, minn[i] = 0x7f7f7f7f;
	for (int i = 1; i <= m; i++)
		edge[i].from = read(), edge[i].to = read(), edge[i].val = read();
	sort(edge + 1, edge + 1 + m);
	for (int i = 1; i <= m; i++) {
		int fx = Find(edge[i].from), fy = Find(edge[i].to), z=edge[i].val;
		if (fx != fy) {
			fa[fy] = fx;
			ans += size[fx] * size[fy] * z;
			minn[fx] = min(min(minn[fx], z), minn[fy]);
			size[fx] += size[fy];
		} else {
			if (z < minn[fx]) {
				write(-1); putchar('\n');
				return 0;
			}
			minn[fx] = min(minn[fx], z);
		}
	}
	for (int i = 1; i <= n; i++) {
		int fx = Find(i);
		if (vis[fx]) continue;
		bel[++cnt] = fx;
		vis[fx] = 1;
		for (int j = 1; j <= cnt - 1; j++)
			ans += size[bel[cnt]] * size[bel[j]];
	}
	write(ans); putchar('\n');
	return 0;
}

CSP模拟18

T1：The Third Letter

这是带权并查集的模板题，但是我不会。你可以让在前面的是在后面的祖先，也可以反过来，这都无所谓，主要是并查集的权值传递，我们用一个 \(d[i]\) 来存 \(i\) 到其祖先的距离，这个距离我们可以在查找祖先时递归更新实现，主要需要注意的就是两个连通块合并的时候，更新两个连通块祖先的距离（自己思考一下其实很简单）。对于出现环的情况，就需要判断存不存在重边不同权值，如果存在，记录一下，最后输出 \(NO\) ；否则，输出 \(YES\) 即可。记得开 \(long\ long\)。
代码实现：

点击查看代码

int n, m, x, y, z, p, T;
int d[300010], f[300010];
int Find(int x) {
    if (x == f[x])
        return x;
    else {
        int fx = Find(f[x]);
        d[x] += d[f[x]];
        f[x] = fx;
        return f[x];
    }
}
signed main() {
    cin >> T;
    while (T--) {
        p = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            d[i] = 0, f[i] = i;
        for (int i = 1; i <= m; i++) {
            cin >> x >> y >> z;
            if (p == 1)
                continue;
            int fx = Find(x), fy = Find(y);
            if (fx != fy) {
                f[fy] = fx;
                d[fy] = d[x] + z - d[y];
            } else {
                if (d[y] - d[x] != z) {
                    p = 1;
                }
            }
        }
        if (!p)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}

T2：Ina of the Mountain

先咕了，放个代码先。
代码实现：

点击查看代码

priority_queue <int> q;
const int maxn = 1e9+10;
int n, k, ans, sum, T;
int a[200010];
signed main() {
	cin >> T;
	while (T--) {
		while (!q.empty()) q.pop();
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		sum = 0; ans = 0;
		for (int i = 1; i <= n; i++) {
			int A, B = (a[i] - a[i-1] + k) % k;
			if (!B) continue;
			A = B - k;
			if (sum + A >= 0) {
				sum += A;
				q.push(-B);
			} else {
				int mn;
				if (!q.empty()) mn = -q.top();
				else mn = maxn;
				if (mn < B) {
					sum += k + A; ans += mn;
					q.pop(); q.push(-B);
				} else {
					sum += B; ans += B;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

CSP模拟19

T1：Strange Function

先观察数据范围，显然 \(O(nT)\) 复杂度会炸，那我们就考虑如何才能降低时间复杂度，我们来思考这个 \(f(i)\) 的性质，发现：如果 \(f(i)=k\) 说明 \(k\) 之前的数都可以整除 \(i\) ， \(k\) 不可以整除 \(i\) ，那也就是说， \(lcm(1,2,...,k-1)\mid i\) ， \(k\nmid i\) ，那我们就可以通过枚举 \(k\) 的个数，来降低时间复杂度，使复杂度降到 \(O(T\log n)\) 。

T2：DZY Loves Modification

这道题就是利用了贪心的思想，可以使用优先队列存每一行和每一列的和，先分别对行和列进行处理，考虑到最后的答案是和选行或列的顺序无关的，行与行或列与列之间前后选择，互相没有影响，最后只需要减去选行选列的交点的个数乘 \(p\) 即可。具体实现方法就是在分别考虑完行和列的方案贡献后，最后枚举一次 \(k\) ，计算 \(i\) 次选行和 \(k-i\) 次选列得出的答案，最后取最大值为 \(ans\) ，记得开 \(long\ long\) 。
代码实现：

点击查看代码

const int maxn = 1e18;
priority_queue<int>line, row;
int n, m, k, p, res, cntl, cntr, ans = -maxn;
int a[1010][1010], suml[1000010], sumr[1000100];
signed main() {
    cin >> n >> m >> k >> p;
    for (int i = 1; i <= n; i++) {
        res = 0;
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            res += a[i][j];
        }
        line.push(res);
    }
    for (int j = 1; j <= m; j++) {
        res = 0;
        for (int i = 1; i <= n; i++) {
            res += a[i][j];
        }
        row.push(res);
    }
    for (int i = 1; i <= k; i++) {
        int x = line.top();
        line.pop();
        suml[i] = suml[i - 1] + x;
        x -= m * p;
        line.push(x);
    }
    for (int j = 1; j <= k; j++) {
        int y = row.top();
        row.pop();
        sumr[j] = sumr[j - 1] + y;
        y -= n * p;
        row.push(y);
    }
    for (int z = 0; z <= k; z++) {
        ans = max(ans, suml[z] + sumr[k - z] - p * (k - z) * z);
    }
    cout << ans << '\n';
    return 0;
}

CSP模拟21

T1：[CEOI2016] kangaroo

思路我想不到，就是将一个数看成一个块，相当于将 \(1 \sim n\) 当作一个一个的块去插到当前有的块之间 \(j-1\) 个块，所以有 \(j\) 个空，还要判断 \(s\) 和 \(t\) 是否已经插入，如果插入那么空应该减少，最后合并块即可。合并 \(s\) 和 \(t\) 的时候有点特殊，因为只能放在左边或右边，特判一下即可。具体 \(dp\) 转移：

插入新块：\(f[i][j]=f[i-1][j-1]*j\)

合并块：\(f[i][j+1]=f[i-1][j+1]*j\)

起（终）点的合并相当于在块中加一个元素：\(f[i][j]=f[i-1][j]\)

具体看代码即可，我觉得应该可以明白吧。

代码实现：

点击查看代码

#define int long long
using namespace std;
const int mod=1e9+7;
int n,s,t;
int f[2010][2010];
signed main()
{
    cin >> n >> s >> t;
    f[1][1]=1;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (i==s || i==t)
            {
                f[i][j]+=f[i-1][j]+f[i-1][j-1];
                f[i][j]%=mod;
                continue;
            }
            int res=(i>s)+(i>t);
            f[i][j]+=f[i-1][j-1]*(j-res);
            f[i][j]+=f[i-1][j+1]*j;
            f[i][j]%=mod;
        }
    }
    cout << f[n][1] << '\n';
    return 0;
}

T2：[JOI 2023 Final] Advertisement 2

当我们做题遇到绝对值的时候，应该考虑将绝对值拆开，\(\mid X_i-X_j\mid \leqslant E_i-E_j\) ，我们就可以转化为 \(X_i-X_j\leqslant E_i-E_j\ and \ X_j-X_i\leqslant E_i-E_j\) ，简单移项，使相同下标的变量放在同一侧，就可以得出这样的一个式子：

\[\begin{cases}E_j-X_j\leqslant E_i-X_i\\E_j+X_j\leqslant E_i+X_i\end{cases} \]

那么，我们就可以化简一下这个式子，设 \(x_i=E_i-X_i\ ,y_i=E_i+X_i\) ，那么式子就可以变得简单，我们先算出 \(x\ ,y\) ，然后可以先将 \(x\) 进行排序，这样我们只需满足 \(y\) 的条件即可，这里我们可以用一个单调栈来维护一个递减栈（可以画图理解一下，比较好理解），最后栈里的所有元素就是我们要求的个数。注意排序 \(x\) 的时候，要将 \(y\) 作为第二关键词排序，否则最后的答案可能会偏大。
代码实现：

点击查看代码

struct node {
    int x, y;
    friend bool operator<(node x1, node x2) {
        if (x1.x == x2.x)
            return x1.y < x2.y;

        return x1.x < x2.x;
    }
}
a[500010];
int n, o, p, top;
int sta[500010];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> o >> p;
        a[i].x = o + p;
        a[i].y = p - o;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        while (top && a[sta[top]].y <= a[i].y)
            top--;

        sta[++top] = i;
    }
    cout << top << '\n';
    return 0;
}

T3：Your

先考虑点的数量，题目说不存在三条及以上条的线过某一点，那么在⚪中四个点会有一个交点，所以交点的总数为 \(C_n^4\) ，那么总的点数就是 \(C_n^4+n\) ；然后考虑边的数量，肯定不能直接套欧拉定理，因为要先满足是平面图，这时就应该利用一种方法：两条相交的线，可以认为是交点是一个新的点，将一条直线分为两半，那么总的边数就相当于增加了 \(2\) ，不要忘了圆弧也是线，所以最终得到的总边数为 \(C_n^2+2\cdot C_n^4+n\) ，最后套题目给的式子就可以了，减去最外面的无穷平面就可以得出总的面数了。自己算一算，应该是 \(C_n^4+C_n^2+1\) 。记得开 \(long\ long\) 。

代码实现：

点击查看代码

#define int long long
using namespace std;
const int mod = 998244353;
int a, b, n, x, y;
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
signed main() {
    cin >> n;
    x = qpow(24, mod - 2);
    y = qpow(2, mod - 2);
    a = (n % mod * (n - 1) % mod * (n - 2) % mod * (n - 3) % mod) % mod * x % mod;
    b = (n % mod * (n - 1) % mod) % mod * y % mod;
    cout << a % mod << '\n';
    cout << (a + b + 1) % mod << '\n';
    return 0;
}

CSP模拟22

T1：The Child and Toy

要求最后的答案值最小，考虑贪心，我们不难发现，删去一个点，其实就是删去和这个点相连的边，那么我们要想最终答案最小，就必须将点权小的边删去，大的留下，这样才能得出最优方案，所以我们直接在建边的时候删边，将两点之间较小的点权减去，加入答案中，最后输出答案即可。

代码实现：

点击查看代码

#define int long long
using namespace std;
int n, m, a, b, ans;
int val[1000010];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> val[i];
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		ans += min(val[a], val[b]);
	}
	cout << ans << '\n';
	return 0;
}