首页 > 其他分享 >CSP-S 2022 题解

CSP-S 2022 题解

时间：2022-10-31 18:57:24浏览次数：109  
标签：infty return int 题解 ll maxn 2022 include CSP

感觉不如校内模拟赛。

但是保持状态和不挂分是很难的。

希望明年可以做到不挂分并且至少拿满暴力。

T1 假期计划

签到。

发现 \(n \leq 2.5 \times 10^3\)，于是考虑一些 \(O(n^2)\) 做法。

考虑枚举中间的两个顶点 \(B, C\)。假设有一对合法的 \(B, C\)，考虑把可能合法的 \(A\) 和可能合法的 \(D\) 用 bfs \(O(n^2)\) 预处理出来。

注意到 \(A, D\) 中至少有一个顶点取到可能的最优值，于是分讨 \(A, D\) 取最优值的情况，然后取较优解即可。

这样做的好处在于分讨没有讨论前三大的做法复杂，但是复杂度多一只 \(\log\)

复杂度 \(O(n^2 \log n)\)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 2.5e3 + 5;
const int maxm = 2e4 + 5;

struct node
{
	int to, nxt;
} edge[maxm];

int n, m, k, cnt;
int head[maxn], dis[maxn][maxn];
ll w[maxn];
bool vis[maxn];
vector<int> to[maxn];

bool cmp(int a, int b) { return (w[a] > w[b]); }

void add_edge(int u, int v)
{
	cnt++;
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

void bfs(int st)
{
	queue<int> q;
	memset(dis[st], -1, sizeof(dis[st]));
	memset(vis, false, sizeof(vis));
	vis[st] = true;
	dis[st][st] = 0;
	q.push(st);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (!vis[v])
			{
				dis[st][v] = dis[st][u] + 1;
				vis[v] = true, q.push(v);
			}
		}
	}
}

int main()
{
// 	freopen("holiday.in", "r", stdin);
// 	freopen("holiday.out", "w", stdout);
	ll ans = 0;
	scanf("%d%d%d", &n, &m, &k); k++;
	for (int i = 2; i <= n; i++) scanf("%lld", &w[i]);
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	for (int i = 1; i <= n; i++) bfs(i);
	for (int i = 2; i <= n; i++)
		for (int j = 2; j <= n; j++)
			if ((dis[i][j] >= 1) && (dis[i][j] <= k) && (dis[j][1] >= 1) && (dis[j][1] <= k)) to[i].push_back(j);
	for (int i = 1; i <= n; i++) sort(to[i].begin(), to[i].end(), cmp);
	for (int b = 2; b <= n; b++)
		for (int c = 2; c <= n; c++)
		{
			if ((dis[b][c] <= 0) || (dis[b][c] > k) || (to[b].empty()) || (to[c].empty())) continue;
			int a = -1, d = -1;
			for (int i = 0; i < to[b].size(); i++)
				if (to[b][i] != c) { a = to[b][i]; break; }
			if (a != -1)
			{
				for (int i = 0; i < to[c].size(); i++)
					if ((to[c][i] != a) && (to[c][i] != b)) { d = to[c][i]; break; }
				if (d != -1) ans = max(ans, w[a] + w[b] + w[c] + w[d]);
			}
			d = -1, a = -1;
			for (int i = 0; i < to[c].size(); i++)
				if (to[c][i] != b) { d = to[c][i]; break; }
			if (d != -1)
			{
				for (int i = 0; i < to[b].size(); i++)
					if ((to[b][i] != c) && (to[b][i] != d)) { a = to[b][i]; break; }
				if (a != -1) ans = max(ans, w[a] + w[b] + w[c] + w[d]);
			}
		}
	printf("%lld\n", ans);
	return 0;
}

T2 策略游戏

真·签到。

考虑分讨：

  1. 先手取正数。

    1. 后手有负数
      此时后手取最小负数，先手取最小正数
    2. 后手有 \(0\)
      此时后手取 \(0\)
    3. 后手只有正数
      此时后手取最小正数，先手取最大正数

  2. 先手取负数

    1. 后手有正数
      此时先手取最大负数，后手取最大正数
    2. 后手有 \(0\)
      此时后手取 \(0\)
    3. 后手只有负数
      此时先手取最小负数，后手取最大负数

  3. 先手取 \(0\)
    贡献为 \(0\)

由于先手足够聪明，因此会在三种情况中取最优值。用 RMQ 维护区间最值即可。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;
const int lg_sz = 20;
const ll inf = 1e18;

int q;
int lg[maxn];
int pre1[maxn], pre2[maxn];

int get_max(int a, int b)
{
	if (a == 0) return b;
	if (b == 0) return a;
	return max(a, b);
}

int get_min(int a, int b)
{
	if (a == 0) return b;
	if (b == 0) return a;
	return min(a, b);
}

struct seq
{
	int n;
	int val[maxn];
	int mxv1[maxn][lg_sz], mxv2[maxn][lg_sz], mnv1[maxn][lg_sz], mnv2[maxn][lg_sz];
	
	void init()
	{
		for (int i = 1; i <= n; i++)
			if (val[i] > 0) mxv1[i][0] = mnv1[i][0] = val[i];
			else if (val[i] < 0) mxv2[i][0] = mnv2[i][0] = val[i];
			else mxv1[i][0] = mxv2[i][0] = mnv1[i][0] = mnv2[i][0] = 0;
		for (int j = 1; (1 << j) <= n; j++)
			for (int i = 1; i + (1 << j) - 1 <= n; i++)
			{
				mxv1[i][j] = get_max(mxv1[i][j - 1], mxv1[i + (1 << (j - 1))][j - 1]);
				mnv1[i][j] = get_min(mnv1[i][j - 1], mnv1[i + (1 << (j - 1))][j - 1]);
				mxv2[i][j] = get_max(mxv2[i][j - 1], mxv2[i + (1 << (j - 1))][j - 1]);
				mnv2[i][j] = get_min(mnv2[i][j - 1], mnv2[i + (1 << (j - 1))][j - 1]);
			}
	}
	
	int query_mxv1(int l, int r)
	{
		int k = lg[r - l + 1];
		return get_max(mxv1[l][k], mxv1[r - (1 << k) + 1][k]);
	}
	
	int query_mnv1(int l, int r)
	{
		int k = lg[r - l + 1];
		return get_min(mnv1[l][k], mnv1[r - (1 << k) + 1][k]);
	}
	
	int query_mxv2(int l, int r)
	{
		int k = lg[r - l + 1];
		return get_max(mxv2[l][k], mxv2[r - (1 << k) + 1][k]);
	}
	
	int query_mnv2(int l, int r)
	{
		int k = lg[r - l + 1];
		return get_min(mnv2[l][k], mnv2[r - (1 << k) + 1][k]);
	}
} a, b;

ll solve1(int l, int r, int s, int t)
{
	int mxv1 = a.query_mxv1(l, r);
	if (mxv1 == 0) return -inf;
	int mnv1 = a.query_mnv1(l, r);
	int tmp = b.query_mnv2(s, t);
	if (tmp != 0) return 1ll * mnv1 * tmp;
	if (pre2[t] - pre2[s - 1] > 0) return 0;
	tmp = b.query_mnv1(s, t); 
	if (tmp != 0) return 1ll * mxv1 * tmp;
	return 0;
}

ll solve2(int l, int r, int s, int t)
{
	int mxv2 = a.query_mxv2(l, r);
	if (mxv2 == 0) return -inf;
	int mnv2 = a.query_mnv2(l, r);
	int tmp = b.query_mxv1(s, t);
	if (tmp != 0) return 1ll * mxv2 * tmp;
	if (pre2[t] - pre2[s - 1] > 0) return 0;
	tmp = b.query_mxv2(s, t);
	if (tmp != 0) return 1ll * mnv2 * tmp;
	return 0;
}

int main()
{
// 	freopen("game.in", "r", stdin);
// 	freopen("game.out", "w", stdout);
	scanf("%d%d%d", &a.n, &b.n, &q);
	for (int i = 2; i <= max(a.n, b.n); i++) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= a.n; i++)
	{
		scanf("%d", &a.val[i]);
		pre1[i] = pre1[i - 1] + (a.val[i] == 0);
	}
	for (int i = 1; i <= b.n; i++)
	{
		scanf("%d", &b.val[i]);
		pre2[i] = pre2[i - 1] + (b.val[i] == 0);
	}
	a.init(), b.init();
	while (q--)
	{
		int l, r, s, t;
		scanf("%d%d%d%d", &l, &r, &s, &t);
		ll ans1 = solve1(l, r, s, t);
		ll ans2 = solve2(l, r, s, t);
		ll ans = max(ans1, ans2);
		if (pre1[r] - pre1[l - 1] > 0) ans = max(ans, 0ll);
		printf("%lld\n", ans);
	}
	return 0;
}

T3 星战

玄妙哈希乱搞。

一开始想的是数据结构一类的东西维护，没想到正解是哈希。

条件 2 的含义是 \(n\) 个点 \(n\) 条有向边，且每个点的出度为 \(1\)，显然是此时图是一个内向基环树森林，于是必然满足条件 1。

可以考虑维护一个可重集，表示当前图中存在的所有的边的起点。

对于操作 1，3，直接修改哈希值即可。

对于操作 2，4，可以考虑先维护出每个点初始时对哈希值的贡献，然后再动态维护每个点当前对哈希值的贡献。

哈希可以用一次方和还有异或和直接草。

时间复杂度 \(O(n + m)\)

#include <cstdio>
using namespace std;

typedef long long ll;

const int maxn = 5e5 + 5;
const int maxm = 5e5 + 5;

int n, m, q;
int u[maxm], v[maxm];
ll val1[maxn], res1[maxn];
int val2[maxn], res2[maxn];

int main()
{
    ll cur1 = 0;
    int cur2 = 0;
    scanf("%d%d", &n, &m);
    ll hs1 = 1ll * n * (n + 1) / 2;
    int hs2 = 0;
    for (int i = 1; i <= n; i++) hs2 ^= i;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        cur1 += u, cur2 ^= u;
        val1[v] += u, val2[v] ^= u;
    }
    for (int i = 1; i <= n; i++) res1[i] = val1[i], res2[i] = val2[i];
    scanf("%d", &q);
    while (q--)
    {
        int opt, u, v;
        scanf("%d", &opt);
        if (opt == 1)
        {
            scanf("%d%d", &u, &v);
            val1[v] -= u, val2[v] ^= u;
            cur1 -= u, cur2 ^= u;
        }
        else if (opt == 2)
        {
            scanf("%d", &v);
            cur1 -= val1[v], cur2 ^= val2[v];
            val1[v] = val2[v] = 0;
        }
        else if (opt == 3)
        {
            scanf("%d%d", &u, &v);
            val1[v] += u, val2[v] ^= u;
            cur1 += u, cur2 ^= u;
        }
        else
        {
            scanf("%d", &v);
            cur1 += (res1[v] - val1[v]), cur2 ^= (res2[v] ^ val2[v]);
            val1[v] = res1[v], val2[v] = res2[v];
        }
        puts(((hs1 == cur1) && (hs2 == cur2)) ? "YES" : "NO");
    }
    return 0;
}

T4 数据传输

76 pts 一眼提取树链 dp，考虑优化。

你发现这是静态的，于是考虑倍增。

然而不好维护答案，考虑把提取树链做法改成直接在树上做。

此时我们需要向下枚举若干结点，可以直接矩乘优化。

假设提取树链序列，令 \(f_i\) 为前 \(i\) 个顶点的答案。

那么当前矩阵为：

\[\left[ \begin{array}{1} f_{i - 1} &f_{i - 2} & f_{i - 3} \end{array} \right] \]

目标矩阵为：

\[\left[ \begin{array}{1} f_i &f_{i - 1} & f_{i - 2} \end{array} \right] \]

由于转移是取 \(\min\)，所以这里放的不是系数而是要加上的常数。由此得到转移矩阵：

\[\left[ \begin{array}{1} a_i & 0 & \infty \\ a_i & \infty & 0 \\ a_i & \infty & \infty \\ \end{array} \right] \]

初始矩阵为：

\[\left[ \begin{array}{1} 0 & \infty & \infty \\ \infty & 0 & \infty \\ \infty & \infty & 0 \\ \end{array} \right] \]

然后这东西上倍增优化就行。

复杂度 \(O(3^3 n \log n)\)

#include <cstdio>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for(int i = a; i <= b; i++)

typedef long long ll;

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;
const int lg_sz = 20;
const ll inf = 1e18;

struct node
{
    int to, nxt;
} edge[maxm];

struct mat
{
    int n, m;
    ll w[3][3];

    mat operator * (const mat& rhs)
    {
        mat res;
        res = {n, rhs.m, {0}};
        for (int i = 0; i < res.n; i++)
            for (int j = 0; j < res.m; j++)
                res.w[i][j] = inf;
        for (int i = 0; i < res.n; i++)
            for (int j = 0; j < res.m; j++)
                for (int k = 0; k < m; k++)
                    res.w[i][j] = min(res.w[i][j], w[i][k] + rhs.w[k][j]);
        return res;
    }
} B, val[maxn], up[maxn][lg_sz], dn[maxn][lg_sz];

int n, q, k, cnt;
int head[maxn], w[maxn], dep[maxn], f[maxn][lg_sz];

void add_edge(int u, int v)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    if (k == 3)
    {
        for (int i = head[u]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            val[u].w[1][1] = min(val[u].w[1][1], 1ll * w[v]);
        }
    }
    up[u][0] = val[fa], dn[u][0] = val[u];
    for (int i = 1; i <= 19; i++)
    {
        f[u][i] = f[f[u][i - 1]][i - 1];
        up[u][i] = up[u][i - 1] * up[f[u][i - 1]][i - 1];
        dn[u][i] = dn[f[u][i - 1]][i - 1] * dn[u][i - 1];
    }
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (v != fa) dfs(v, u);
    }
}

mat solve(int u, int v)
{
    mat a = B, b = B;
    if (dep[u] > dep[v])
        for (int i = 19; i >= 0; i--)
            if (dep[f[u][i]] >= dep[v])
            {
                a = a * up[u][i];
                u = f[u][i];
            }
    if (dep[v] > dep[u])
        for (int i = 19; i >= 0; i--)
            if (dep[f[v][i]] >= dep[u])
            {
                b = dn[v][i] * b;
                v = f[v][i];
            }
    if (u == v) return a * b;
    for (int i = 19; i >= 0; i--)
        if (f[u][i] != f[v][i])
        {
            a = a * up[u][i];
            b = dn[v][i] * b;
            u = f[u][i], v = f[v][i];
        }
    return a * up[u][0] * dn[v][0] * b;
}

int main()
{
    scanf("%d%d%d", &n, &q, &k);
    B = {k, k, {{0, inf, inf}, {inf, 0, inf}, {inf, inf, 0}}};
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        val[i] = {k, k, {{inf, inf, inf}, {inf, inf, inf}, {inf, inf, inf}}};
        for (int j = 0; j <= k - 1; j++) val[i].w[j][0] = w[i];
        for (int j = 1; j <= k - 1; j++) val[i].w[j - 1][j] = 0;
    }
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, 0);
    while (q--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        mat tmp = {1, k, {w[u], inf, inf}};
        printf("%lld\n", (tmp * solve(u, v)).w[0][0]);
    }
    return 0;
}

标签：infty,return,int,题解,ll,maxn,2022,include,CSP
From： https://www.cnblogs.com/lingspace/p/csps-2022.html

相关文章

  • 2022祥云杯 leak
    2022祥云杯leak今年VNCTF的时候碰到过一种写法，方式不会，没写的出来。没想到这次祥云杯leak这题可以用那种写法写，但是我依旧比赛时没写出来。赛后记录一下。主要是利用hou......
  • 10月29号 CSP-S 赛后有感）
     //第一次写博客，可能不是很好，后续比赛的失误也将写入其中，当然首先说明原因，写博客是因为教练的要求qwq 这次的比赛我考的不是很理想，原因如下（望后人引以为戒）：......
  • CSP-S 2022 假期计划&trick
    https://www.luogu.com.cn/blog/tsukimaru/csp-s-2022-jia-ji-ji-hua-di-yi-ge-jian-dan-sui-ji-hua-zuo-fahttps://ac.nowcoder.com/acm/contest/40649/D倘若你遇到选取......
  • 2022极客大挑战
    目录WebbabyuploadezrceWebbabyupload最基础的文件上传（虽然我还没刷完upload-labs，别骂了传一个伪造png头的图片马，抓个包，改个后缀连黑名单都没设。。直接就传上去了......
  • CSP-S 2022 T2 策略游戏题解
    T2比T1简单？可以发现，讨论的情况数不是很多。可以直接用线段树查询然后暴力讨论就好了。（写的好丑）#include<bits/stdc++.h>usingnamespacestd;#defineN1000010#......
  • CSP游记
    ~呜嗷啊嗷嗷嗷~~~嗷啊啊嗷嗷啊嗷啊嗷~啊呜嗷呜~~~呜嗷啊啊嗷~啊啊呜呜~嗷~啊呜~啊嗷嗷~~啊~呜啊嗷啊呜啊啊呜呜~嗷~呜~啊啊呜嗷嗷嗷呜嗷啊~呜呜嗷呜呜呜啊嗷呜~~呜~呜啊嗷~......
  • 2022.10.21----vscode-自定义事件
     vscode预览模式关闭，就能打开新标签页(43条消息)vscode新窗口打开文件-CSDN (43条消息)如何在vscode中打开新文件夹不覆盖上一个窗口标签_发呆的薇薇°的博客-......
  • 第四届全国大学生算法设计与编程挑战赛（秋季赛）正式赛题解
    没时间写题解了，随便写两笔吧，看不懂可以联系QQ160042137901（Easy）直接暴力枚举每个状态及其所有转移，时间复杂度\((T2^nn^2)\)。02（Easy）二分答案，用一个单调队列或者优先......
  • CSP-S 2022 游记
    初赛就不写了，\(92\text{pts}\)，计数排序都不认识了是我属实想不到的。Day-1下午模拟赛爆炸了，见过类似套路的T2直接想假了挂成\(20\)。Day0上午\(\text{Vp}\)CF，一......
  • 2022-10-31 删除无法删除的文件夹or文件
    新建.txt文件，复制下面代码：DEL/F/A/Q\\?\%1RD/S/Q\\?\%1把.txt文件改名为.bat，保存。拖动该文件到你想要的文件夹or文件上面，松开鼠标。然后再删除。我试了，没用！......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99