首页 > 其他分享 >CSP-S2022题解（T4待填）

CSP-S2022题解（T4待填）

时间：2022-11-06 23:58:37浏览次数：51  
标签：ch min int 题解 T4 S2022 max MAXN mx

闲话

\(\huge{寄}\)

\(\text{T1}\) 极限脑抽，删掉暴搜打错解，\(70pts \to 0pts\)；

\(\text{T2}\) 洛谷 \(100pts\) 但 \(\infin\) \(40pts\)， 很慌；

\(\text{T3}\) 差点想到正解（但确实没想到）暴力 \(40pts\)；

\(\text{T4}\) 甚至一分都拿不到；

期望 \(110\)。

打的模拟赛真的太少了（似乎就打过四五次……），心态真的太容易被影响（又是心态炸裂导致的水平急剧下跌）。

题解

\(\bold{T1}\)

\(n \le 2500\)，可以往 \(O(n^2)\) 考虑。

那么对于这题而言，\(O(n^2)\) 能干什么呢？

  • 对每个点进行一遍 \(\text{BFS}\)，预处理出它能到达的点集
  • 枚举 \(4\) 个点中的 \(2\) 个

突破口也就在第二点中——对于 \(4\) 个点，我们不妨把它们拆成 \(2 + 2\) 个点，预处理出 \(w[i]\)（从 \(1\) 开始走 \(2\) 步到达 \(i\) 点的最大值），然后枚举 \(B, C\) 两点更新答案即可。

\(\large{\text{BUT}}\)

事情真的这么简单吗？

题目：请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

注意所选的四个点是不同的，那么在更新答案时就不能只是简单地取两边的最大值。

那么为什么会出现重复的情况呢？显然是我们没有枚举到 \(A, D\) 导致的。但是现阶段的时间复杂度又不允许我们枚举 \(A, D\)，怎么办呢？

我们要使答案最大，显然最大值选不了就会选次大值，次大值选不了就会选次次大值，次次大值选不了就会选……若最坏情况下 \(A\) 点会和其他点发生 \(n\) 次重复，那么就可以通过维护前 \(n + 1\) 大值来解决重复的问题。

由于图中不存在自环，所以 \(B\) 点势必不会和 \(A\) 点重复，但 \(C, D\) 两点都是可以和 \(A\) 重复的。\(D\) 点情况同理，而对于 \(B\) 点，枚举了 \(C\) 点，所以可以保证 \(C \ne B\)，能与 \(B\) 点重复的点就只剩下 \(D\) 点一个点。\(C\) 点同理。因此，我们可以维护 \(w[i][0/1/2]\)（从 \(1\) 开始走 \(2\) 步到达 \(i\) 点的最大/次大/次次大值），更新答案时分类讨论一下就好啦～

\(Code\)

#include <bits/stdc++.h>

#define MAXN 2600
#define MAXM 100100

using namespace std;

typedef long long ll;

int n, m, p, dis[MAXN], mx[MAXN][4];
int tot, head[MAXN];
ll w[MAXN];
bool vis[MAXN], G[MAXN][MAXN];

struct Edge {
	int to, nxt;
} e[MAXM << 1];

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x *= _f;
}

template<typename _T>
void write(_T _x) {
    if (_x < 0) {
        putchar('-');
        _x = -_x;
    }
    if (_x > 9) write(_x / 10);
    putchar('0' + _x % 10);
}

void add(int u, int v) {
	e[++tot] = Edge{v, head[u]};
	head[u] = tot;
}

void bfs(int s) {
	queue<int> q;
	memset(vis, 0, sizeof(vis));
	vis[s] = 1, dis[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (dis[u] > p) return;
		for (int i = head[u], v; i; i = e[i].nxt) {
			v = e[i].to;
			if (vis[v]) continue;
			vis[v] = 1;
			dis[v] = dis[u] + 1;
			G[s][v] = 1;
			q.push(v);
		}
	}
}

int main() {
	read(n), read(m), read(p);
	for (int i = 2; i <= n; i++) read(w[i]);
	while (m--) {
		int u, v;
		read(u), read(v);
		add(u, v), add(v, u);
	}
	for (int i = 1; i <= n; i++) bfs(i);
	w[0] = -1e18;
	memset(vis, 0, sizeof(vis));
	for (int i = 2; i <= n; i++) {
		if (!G[1][i]) continue;
		for (int j = 2; j <= n; j++) {
			if (!G[i][j]) continue;
			vis[j] = 1;
			if (w[i] > w[mx[j][0]]) {
				mx[j][2] = mx[j][1], mx[j][1] = mx[j][0], mx[j][0] = i;
			} else if (w[i] > w[mx[j][1]]) {
				mx[j][2] = mx[j][1], mx[j][1] = i;
			} else if (w[i] > w[mx[j][2]]) mx[j][2] = i;
		}
	}
	ll ans = 0;
	for (int B = 2; B <= n; B++) {
		if (!vis[B]) continue;
		for (int C = B + 1; C <= n; C++) {
			if (!G[B][C] || !vis[C]) continue;
			ll tmp;
			int i = 0, k = 0;
			if (mx[B][i] == C) i++;
			if (mx[C][k] == B) k++;
			if (mx[B][i] != mx[C][k]) tmp = w[mx[B][i]] + w[mx[C][k]];
			else {
				int j = i + 1, l = k + 1;
				if (mx[B][j] == C) j++;
				if (mx[C][l] == B) l++;
				tmp = max(w[mx[B][i]] + w[mx[C][l]], w[mx[B][j]] + w[mx[C][k]]);
			}
			ans = max(ans, w[B] + w[C] + tmp);
		}
	}
	write(ans);
	return 0;
}

\(\bold{T2}\)

对于特殊条件 \(1\)：小 \(L\) 一定选最大的，小 \(Q\) 一定选最小的。

对于特殊条件 \(2\)（如果有一个人只能选 \(0\)，那么答案一定是 \(0\)，以下分类不包括有一人只能选 \(0\) 的情况）：

  • 若小 \(L\) 只能选一个数
    • 若这个数是正数——小 \(Q\) 一定选最小的数（即 \(min_B\)）。
    • 若这个数是负数——小 \(Q\) 一定选最大的数（即 \(max_B\)）。
  • 若小 \(Q\) 只能选一个数
    • 若这个数是正数——小 \(L\) 一定选最大的数（即 \(max_A\)）。
    • 若这个数是负数——小 \(L\) 一定选最小的数（即 \(min_A\)）。

部分分已经在不断地带着我们往正解走了，再进行更精细的分类其实正解就出来了。

从小 \(L\) 的角度入手。

小 \(Q\) 的选择范围分为以下三种：

\[(1) \left\{ \begin{aligned} max_B \ge 0 \\ min_B \ge 0 \end{aligned} \right. ~~~~ (2) \left\{ \begin{aligned} max_B \le 0 \\ min_B \le 0 \end{aligned} \right. ~~~~ (3) \left\{ \begin{aligned} max_B \ge 0 \\ min_B \le 0 \end{aligned} \right. \]

（分别对应着只有正数、只有负数和既有正又有负）

  • 对于 \((1)\)，小 \(L\) 一定会选 \(max_A\)，但也得分三种情况：

\[(a) max_A < 0 ~~~~ (b) max_A > 0 ~~~~(c) max_A = 0 \]

对于 \((a)\)，小 \(Q\) 会选 \(max_B\)；对于 \((b)\)，小 \(Q\) 会选 \(min_B\)；对于 \((c)\)，小 \(Q\) 会直接摆烂，因为无论怎样都只能得到 \(0\)。

  • 对于 \((2)\)，小 \(L\) 一定会选 \(min_A\)，分三种情况：

\[(a) min_A < 0 ~~~~ (b) min_A > 0 ~~~~(c) min_A = 0 \]

对于 \((a)\)，小 \(Q\) 会选 \(max_B\)；对于 \((b)\)，小 \(Q\) 会选 \(min_B\)；对于 \((c)\)，小 \(Q\) 会随便乱选，因为无论怎样都只能得到 \(0\)。

  • 对于 \((3)\)，小 \(L\) 能选 \(0\) 就一定会选 \(0\)（因为无论小 \(L\) 选什么非零数，小 \(Q\) 都能将其乘成一个负数），加入这类情况后：
    • 如果小 \(L\) 出负数，则小 \(Q\) 会出 \(max_B\)，小 \(L\) 自然清楚这一点，所以他会出最大的非正数（这里将其称为 \(nmax_A\)）。
    • 如果小 \(L\) 出正数，则小 \(Q\) 会出 \(min_B\)，小 \(L\) 自然清楚这一点，所以他会出最小的非负数（这里将其称为 \(pmin_A\)）。
    • 小 \(L\) 会使结果最大，所以答案是上述两种情况的最大值，即 \(\max(nmax_A \times max_B, pmin_A \times min_B)\)。

\(6\) 个 \(\text{ST}\) 表或线段树（此题不带修，建议用常数更小的 \(\text{ST}\) 表）维护 \(max_A, min_A, max_B, min_B, nmax_A, pmin_B\)，\(O(n \log n)\) 预处理，\(O(1)\) 查询，稳稳 \(\text{AC}\)。

\(Code\)

#include <bits/stdc++.h>

#define MAXN 100100
#define MAXK 20

using namespace std;

const int INF = 2e9;

int n, m, q, a[MAXN], b[MAXN];
int lg[MAXN], maxa[MAXN][MAXK], mina[MAXN][MAXK], maxb[MAXN][MAXK], minb[MAXN][MAXK], nmaxa[MAXN][MAXK], pmina[MAXN][MAXK];

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x *= _f;
}

template<typename _T>
void write(_T _x) {
    if (_x < 0) {
        putchar('-');
        _x = -_x;
    }
    if (_x > 9) write(_x / 10);
    putchar('0' + _x % 10);
}

void init() {
    for (int i = 2; i <= n || i <= m; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) maxa[i][0] = mina[i][0] = a[i];
    for (int i = 1; i <= m; i++) maxb[i][0] = minb[i][0] = b[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) nmaxa[i][0] = pmina[i][0] = 0;
        else if (a[i] < 0) nmaxa[i][0] = a[i], pmina[i][0] = INF;
        else nmaxa[i][0] = -INF, pmina[i][0] = a[i];
    }
    for (int k = 1; (1 << k) <= n; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            maxa[i][k] = max(maxa[i][k - 1], maxa[i + (1 << (k - 1))][k - 1]);
            mina[i][k] = min(mina[i][k - 1], mina[i + (1 << (k - 1))][k - 1]);
            nmaxa[i][k] = max(nmaxa[i][k - 1], nmaxa[i + (1 << (k - 1))][k - 1]);
            pmina[i][k] = min(pmina[i][k - 1], pmina[i + (1 << (k - 1))][k - 1]);
        }
    }
    for (int k = 1; (1 << k) <= m; k++) {
        for (int i = 1; i + (1 << k) - 1 <= m; i++) {
            maxb[i][k] = max(maxb[i][k - 1], maxb[i + (1 << (k - 1))][k - 1]);
            minb[i][k] = min(minb[i][k - 1], minb[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int getmaxa(int l, int r) {
    int ln = lg[r - l + 1];
    return max(maxa[l][ln], maxa[r - (1 << ln) + 1][ln]);
}

int getmina(int l, int r) {
    int ln = lg[r - l + 1];
    return min(mina[l][ln], mina[r - (1 << ln) + 1][ln]);
}

int getmaxb(int l, int r) {
    int ln = lg[r - l + 1];
    return max(maxb[l][ln], maxb[r - (1 << ln) + 1][ln]);
}

int getminb(int l, int r) {
    int ln = lg[r - l + 1];
    return min(minb[l][ln], minb[r - (1 << ln) + 1][ln]);
}

int getnmaxa(int l, int r) {
    int ln = lg[r - l + 1];
    return max(nmaxa[l][ln], nmaxa[r - (1 << ln) + 1][ln]);
}

int getpmina(int l, int r) {
    int ln = lg[r - l + 1];
    return min(pmina[l][ln], pmina[r - (1 << ln) + 1][ln]);
}

int main() {
    read(n), read(m), read(q);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= m; i++) read(b[i]);
    init();
    while (q--) {
        int a, b, c, d;
        read(a), read(b), read(c), read(d);
        int amax = getmaxa(a, b), amin = getmina(a, b), bmax = getmaxb(c, d), bmin = getminb(c, d);
        if (bmin >= 0) {
            if (amax < 0) write(1ll * amax * bmax);
            else if (amax > 0) write(1ll * amax * bmin);
            else write(0);
        } else if (bmax <= 0) {
            if (amin < 0) write(1ll * amin * bmax);
            else if (amin > 0) write(1ll * amin * bmin);
            else write(0);
        } else {
            int nmax = getnmaxa(a, b), pmin = getpmina(a, b);
            if (nmax == -INF) write(1ll * pmin * bmin);
            else if (pmin == INF) write(1ll * nmax * bmax);
            else write(max(1ll * nmax * bmax, 1ll * pmin * bmin));
        }
        putchar('\n');
    }
    return 0;
}

\(\bold{T3}\)

题面很长，认认真真读下来后不难发现：如果把每个虫洞看作是一条无向边的话，“绝佳的反攻时刻”时 \(n\) 个点一定会构成基环森林。就着这个性质再读一遍条件，又不难发现每个据点能够“连续穿梭”时势必可以“实现反击”，此时每个点的出度都为 \(1\)。

于是乎，题意简化成了：

给定 \(n\) 个点，\(m\) 条边，有如下操作：

\(1\)：删除一条边。

\(2\)：删除一个点的所有入边。

\(3\)：恢复一条边。

\(4\)：恢复一个点的所有入边。

每一次操作完成后，若每个点的出度都为 \(1\)，输出 YES，否则输出 NO。

对每一个点随机一个点权，然后 \(\text{Hash}\)～

#include <bits/stdc++.h>

#define MAXN 500100

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;

int n, m, q;
int tot, head[MAXN];
ll cur, ok, w[MAXN], s[MAXN], pres[MAXN];

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x *= _f;
}

int main() {
    srand(time(0));
    read(n), read(m);
    for (int i = 1; i <= n; i++) {
        w[i] = rand() % MOD;
        ok = (ok + w[i]) % MOD;
    }
    while (m--) {
        int u, v;
        read(u), read(v);
        s[v] = (s[v] + w[u]) % MOD;
        cur = (cur + w[u]) % MOD;
    }
    for (int i = 1; i <= n; i++) pres[i] = s[i];
    read(q);
    while (q--) {
        int op, u, v;
        read(op), read(u);
        if (op == 1) {
            read(v);
            s[v] = (s[v] - w[u] + MOD) % MOD;
            cur = (cur - w[u] + MOD) % MOD;
        } else if (op == 2) {
            cur = (cur - s[u] + MOD) % MOD;
            s[u] = 0;
        } else if (op == 3) {
            read(v);
            s[v] = (s[v] + w[u]) % MOD;
            cur = (cur + w[u]) % MOD;
        } else {
            cur = (cur + pres[u] - s[u] + MOD) % MOD;
            s[u] = pres[u];
        }
        if (cur == ok) puts("YES");
        else puts("NO");
    }
    return 0;
}

\(\bold{T4}\)

还没想出来……留个坑，等会了再填。

标签：ch,min,int,题解,T4,S2022,max,MAXN,mx
From： https://www.cnblogs.com/chy12321/p/16864664.html

相关文章

  • 2022CSP-S题解
    这次是我第一次参加\(CSP-J/S\)，所以我决定口胡一下这几道题目，由于\(J\)组过于简单，就不再叙述，如有问题请私信我\(/oh/oh/oh\)假期计划（holiday）我们可以先进行\(n\)......
  • 洛谷 P3951 [NOIP2017 提高组] 小凯的疑惑 题解
    LuoguP3951[NOIP2017提高组]小凯的疑惑题解注：设\(A,B\)是两个集合，则\(A\timesB\)表示\(A\)与\(B\)的笛卡儿积（直积）。笛卡儿积的定义为\(S\timesM:=\{(s......
  • 洛谷 P2606 [ZJOI2010]排列计数 题解
    LuoguP2606[ZJOI2010]排列计数题解题目描述称一个\(1\simn\)的排列\(p_1,p_2,\dots,p_n\)是Magic的，当且仅当\[\foralli\in[2,n],p_i>p_{\lfloori/2......
  • CSP-J1、S1 2021 赛后总结+简要题解
    postedon2021-09-1922:34:52|under题解|source人在佛山，考场在南外。学校信息队太强了，不仅租车还包午饭，点赞。来写一下我做题经历吧：S组官方答案：ABACCCCBDACC......
  • CF1685E The Ultimate LIS Problem 题解
    LinkCF1685ETheUltimateLISProblem题意概述给定长为\(2n+1\)的排列，对于\(m\)次交换操作，求出每次操作后一个能使排列\(\text{LIS}\leqn\)的循环移位\(k\)，......
  • 题解 [ABC259Ex] Yet Another Path Counting
    首先，每种颜色互不干扰，因此考虑对每种颜色统计答案。有两种解法：枚举起始格子\((x,y)\)和结尾格子\((z,w)\)，由组合数易知共有\(\binom{z-x+w-y}{z-x}\)种路径。时间......
  • Codeforces-1753B Factorial Divisibility题解
    Codeforces-1753BFactorialDivisibility参考：https://blog.csdn.net/qq_38236082/article/details/127500190题意：问$a_1!+a_2!+a_3!+...+a_n!$能否被$x!$整除。......
  • 题解 [AGC044C] Strange Dance
    这道题启示我们Trie树是可以支持全局下标加\(1\)的。首先把\(3^n\)个人从低位到高位建到三进制Trie树上。类似二叉树的左右儿子，我们称由\(0,1,2\)边连接的儿子......
  • KMP 自动机，孤独的自动机（同时也是CF1721E的题解）
    给定字符串\(s\)，以及\(q\)个串\(t_i\)，求将\(s\)分别与每个\(t_i\)拼接起来后，最靠右的\(|t_i|\)个前缀的border长度。询问间相互独立。\(|s|\leq10^6,q......
  • 【题解】洛谷P2725 [USACO3.1]邮票 Stamps
    从n种邮票中选出不超过k张邮票，使选出来的邮票可以表示1~m之间（含）的所有数。每张邮票在不超过k的前提下，都可以使用无数次，因此可以将问题看成一个完全背包问题。n种邮票就是n......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99