首页 > 其他分享 >CSP模拟赛题解

CSP模拟赛题解

时间：2023-08-20 15:23:31浏览次数：38  
标签：cnt int 题解 long -- ans CSP 模拟 mod

目录

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;
}

标签：cnt,int,题解,long,--,ans,CSP,模拟,mod
From： https://www.cnblogs.com/Aewrxuk/p/17644036.html

相关文章

  • JS习题解析
    1、页面有一个id为button1的按钮，如何通过原生的js禁用？(IE考虑IE8.0以上版本)A、document.getElementById("button1").readonly=true;B、document.getElementById("button1").setAttribute('readonly','true');C、document.getElementById("button1&quo......
  • FEMU模拟器学习笔记
     QEMU参数解析  QEMU的main函数进来后，首先要进行参数解析。一个启动模拟器的命令行如下：x86_64-softmmu/qemu-system-x86_64-name"FEMU-ZNSSD-VM"-enable-kvm-cpuhost-smp2-m4G-devicevirtio-scsi-pci,id=scsi0-devicescsi-hd,drive=hd0-drivefile=/home......
  • 题解 Cow and Snacks
    被黄题创死了2333题目链接首先肯定有一个贪心的想法：尽量使得人们拿的花重复，即尽量使得每个人都拿一束花。当然第一个人必须拿两束。接着思考：如何找出有几个人是必须拿两束花的。其实很简单，当\(A,B\)两人不能通过其他人使得他们的花有联系，比如\(A\)喜欢\(1,2\)，\(B\)喜欢......
  • 8.20题解
    T1sun暴力枚举即可时间复杂度分析：\((lnx)'=\frac{1}{x}\)根据牛顿-莱布尼茨公式可得：\(\sum_{x=1}^{n}{\frac{1}{x}}=\int_{1}^{n}{\frac{1}{x}}=ln(n)-ln{1}=ln(n)\)令\(ln(n)=k\)可得：\(n=e^{k}<=e^{15}\approx3269017\)T2order首先需要理解题意......
  • [HZOJ普及模拟2]
    \(\Huge\color{7ff77f}{打了一场模拟赛，又垫底了。qwq}\)\(\Huge\color{12f4ff}{快}\)\(\Huge\color{f9f98f}{V}\)\(\Huge\color{ff1256}{本}\)\(\Huge\color{ff4514}{蒟}\)\(\Huge\color{7ffff7}{蒻}\)\(\Huge\color{3f3f3f}{5}\)\(\Huge\color{f54321......
  • CSP模拟25
    炒币、凑数、同构、最近公共祖先A.炒币举个栗子，对于序列\[1,4,5\]在\(1\)处买进，在\(5\)处卖出是最优的选择。为什么不选择在\(4\)处买，因为\(4\)处成本更高，所以我们可以把一段递增或递减的序列缩成几个互不相同的点。例如\[1,3,5,3,2,7\]变成\[5,2,7\]只有这......
  • CF1656D K-good 题解
    CF1656DK-good题解题目大意给出\(t\)个整数\(n\)，对于每一个\(n\)找出一个大于等于\(2\)的整数\(k\)，使得\(n\)可以表示成\(k\)个mod\(k\)的结果互不相同的正整数之和。\(1\let\le10^5,2\len\le10^{18}\)。题解我们先将题意再次化简，可以得到，我们实际......
  • P9571 Horizon Blue 题解
    P9571HorizonBlue题解这个题拿平衡树写是不是小题大做了咳咳咳进入正题。首先转化一下题意。第一个操作是加入直线，第二个操作就是求所有斜率不等于\(k\)的直线的数量，第三个操作就是删掉所有斜率不等于\(k\)的和所有与该直线重合的直线。感觉这题完全就是FHQ_Treap的......
  • 普及模拟2 +【LGR-155-Div.3】洛谷基础赛 #3 &「NnOI」Round 2
    普及模拟2\(T1\)地址\(0pts\)简化题意：判断一个\(IP\)地址是否合法（数据保证字符串中存在且仅存在4个被字符分开的整数）#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definesortstable_sort#defineendl'\n'chars[100];intmain(){ freope......
  • P9572 Colorful Days♪ 题解
    原题链接题目大意：有两个数组\(S\),\(T\)，你可以把\(S\)进行复制并接到其后面形成\(S^k\)，如\(S\)=123,则\(S^2\)=123123,\(S^3\)=123123123。让你求出\(S^k\)与\(T\)的最长公共子序列以及在最长公共子序列最长时\(k\)的最小值。首先思考如果无视\(k\)最小的要求，最......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99