首页 > 其他分享 >2024.10.13 模拟赛

2024.10.13 模拟赛

时间：2024-10-14 19:49:02浏览次数：6  
标签：2024.10 return int rint 13 lst max 模拟 define

2024.10.13 模拟赛

T1「KDOI-10」商店砍价

赛时直接口胡出一个错误的贪心。一开始的想法是按照 \(v[i]\) 排序，然后假设输入的长度为 \(n\) 位。那么对于排序后 \(n - 5\) 位直接选择操作一。对于剩下的，直接 bdfs 所有情况选答案，复杂度 \(O(n \log n)\)。貌似可行，结果随便一个数据就能 hack。比如数字 \(1\) 的 \(v[i]\) 是 \(9\)，数字 \(9\) 的 \(v[i]\) 是 \(1\)。老实了。

那么 \(dp\)？设 \(f[i]\) 表示考虑到第 \(i\) 的答案，维护的信息好像差一点。那么 \(f[i][j]\) 的第二维又可以表示什么？坏了，根本想不出来。

等等，对于大部分情况，显然操作一更优，那么可以先假设全部执行操作一，然后再去反着找有没有比操作一更优的操作二。\(f[i]\) 表示考虑了 \(i\) 位使答案变得更优的值，那么最终的答案就是 \(\sum v[i] - \max\{f[i]\}\)

至于 \(f[i]\) 的转移也很简单，\(f_j = \max^{n}_{i=1}\{f_{j - 1} + v_{a_i} - a_i \times 10^{j - 1}\}\)

转移的时候要倒着扫保证 \(10^k\) 的意义

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

考虑继续优化，这个时候我们一开始的贪心就有用了，我们发现在枚举 \(j\) 的时候最多只需要枚举 \(5\) 位，就像一开始的贪心一样，枚举多了没有意义因为操作一一定更优秀，所以复杂度为 \(O(nK)\)，\(K<5\)

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 2e1 + 1;

int ans;
int a[N], v[N];
char s[N];
int ten[M], f[M];

signed main() 
{
	int c, T;
	cin >> c >> T;
	ten[0] = 1;
	for (rint i = 1; i <= 20; i++) ten[i] = ten[i - 1] * 10;
	while (T--) 
	{
		cin >> (s + 1); ans = 0;
		int n = strlen(s + 1);
		for (rint i = 1; i <= n; i++) a[i] = s[i] - '0';
		for (rint i = 1; i <= 9; i++) cin >> v[i];
		for (rint i = 1; i <= n; i++) ans += v[a[i]];
		memset(f, 0xcf, sizeof f);
		f[0] = 0;
		for (rint i = n; i >= 1; i--)
		{
			int k = n - i + 1;
			for (rint j = min(5ll, k); j >= 1; j--)
			{
				f[j] = max(f[j], f[j - 1] + v[a[i]] - a[i] * ten[j - 1]);				
			}			
		}
		int dt = 0;
		for (rint i = 1; i <= 5; i++) dt = max(dt, f[i]);
		cout << ans - dt << endl;
	}
	return 0;
}

T2「KDOI-10」水杯降温

PS：已经被 hack 了，老实了，被这篇帖子link直接制裁。

题外话，@estimate_error这个人机赛时无限趋近于正解（指通过原数据）然后反手写了一个充分不必要条件杀死自己拿下 16 pts 高分。est：“样例过了。我这个构造没问题！”大样例一测，第一个都对不上。

首先，est 在赛时提出了两个水温可以变成 0 的条件：

    1. 对于结点 \(x\)，其所有直接儿子 \(y\) ，\(\sum a_i ≤a_x\)
    1. 对于每一个从下往上走的链是单调不减的

貌似这两个条件是具有充分性的，但是并不具有必要性，由于数据很水，代码可以拿到 16pts

我们将原操作进行以下优化从而使必要性更紧，但不能保证必要性，说不定乱搞就过了呢：

    1. 我们不再开树上前缀和数组树上差分维护 \(\sum a_i\) 而是让 \(a_y\) 的信息往 \(a_x\) 加，\(y ∈ x\)，最后累加 \(a[x]\) 得到 \(res\) 与它们的公共父亲比大小
    1. 对于一开始提出的条件一，要注意累加后小于 0 的情况。此时必要性一定不成立。要取个 \(max\)
    1. 不难发现起决定性作用的一定是根节点，因为操作二一定会影响到根节点，所以 a[1] = max(a[1], 0)，最后 a[i]-=a[fa[i]]，但是这个操作倒着处理保证顺序

诶，这样只需要每次执行一次 dfs 就可以，对于赛时数据还是可以轻松通过的。但是被 hack 了。说明该方案是具有错误性的，就比如在根节点下面接一颗完全二叉树并使最后一排全为 0。

（所以是不是在代码里加个check如果最后一排全是零就输出Shuiniao就行了/doge）

当然如果这个题有正解 idea 的欢迎私信教教这个蒟蒻怎么做。。。。

有一篇貌似看起来很对的做法，留个link

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;

int c, T;
int n, a[N], fa[N];
vector<int> vec[N];
bool flag;

void dfs(int x) 
{
	int res = 0;
	for (rint y : vec[x]) 
	{
		if (vec[x].size() == 1) a[y] = max({0ll, a[x], a[x] + a[y]});
		else a[y] = max(0ll, a[x] + a[y]);
		res += a[y];
		dfs(y);
	}
	if (res > a[x]) flag = 0;
}

signed main() 
{
	cin >> c >> T;
	while (T--) 
	{
		cin >> n;
		flag = 1;
		for (rint i = 2; i <= n; i++) 
		{
			int x;
			cin >> x;
			fa[i] = x;
			vec[x].push_back(i);
		}
		for (rint i = 1; i <= n; i++) cin >> a[i];
		for (rint i = n; i >= 1; i--) a[i] -= a[fa[i]];
		a[1] = max(a[1], 0ll);
		dfs(1);
		cout << (flag ? "Huoyu" : "Shuiniao") << endl;
		for (rint i = 1; i <= n; i++) vec[i].clear();
	}
	return 0;
}

T3「KDOI-10」反回文串

“两个特殊性质已经把做法塞你嘴里了。”

好家伙，无敌了，有被冒犯到，像我这种只会写性质 A 的是不是可以一头创死了？

在没看特殊性质之前，我就以为答案是 \(n/2\)。虽然很容易就会发现有问题但是抛开输出方案不谈只输出答案我觉得能骗不少分。

对于特殊性质 A，如果 \(n\) 是偶数，直接 \(i\) 与 \(i+n\) 配对。如果 \(n\) 是奇数就把多出来的那个随便找个地方放就行，答案仍然是 \(n/2\)

对于特殊性质 B，假设只有两种颜色。只能将所有的分在一起。如果此时 \(2 \nmid n\) 并且 \(s _ {\lfloor \frac n 2 \rfloor}\) 为数量少的颜色时无解，或则答案为 \(1\)。当有一堆颜色时候，按照 baa...， ...aab 和 ac ，da 这么分。答案最优为 \(n - cnt[多的那个颜色]\) 的数量。

还有一个显然的，就是不可能有两个以上的颜色同时超过 \(n/2\)，那么确实是两个特殊性质已经把做法塞你嘴里了

不存在最多超过 \(n/2\) 的颜色用 A 性质，否则用 B 做法。

复杂度 \(O(\sum n)\)

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 5;
const int M = 3e1 + 5; //bigger than 26 is ok

int n;
char s[N];
vector<int> v[M], p[N];
int cnt[M], id[N];

void stop_ () 
{
	cout << "Shuiniao" << endl;
}

void solve () 
{
	cin >> n;
	cin >> (s + 1);
	for (rint i = 0; i < 27; i++) v[i].clear(), cnt[i] = 0;
	for (rint i = 1; i <= n; i++) 
	{
		v[s[i] - 'a'].push_back(i); //记录字母位置方便后面的便利
		cnt[s[i] - 'a']++; //计数
	}
	int pos = -1; //特殊性质 A
	for (rint i = 0; i < 27; i++)
	{
		if (cnt[i] > n / 2) 
		{
			pos = i; //记录超越 n / 2 的字母类型
			break;
		}		
	}
	if (pos != -1) //不满足特殊性质 A
	{
		if (cnt[pos] == n) return stop_(); //全是一个字母
		if (cnt[pos] == n - 1) //满足特殊性质 B
		{
			if ((n & 1) && s[n / 2 + 1] != pos + 'a') return stop_();
			cout << "Huoyu" << endl << 1 << endl << n << ' ';
			for (rint i = 1; i <= n; i++) cout << i << ' ';
			cout << endl;
			return ;
		}
	}
	int k;
	if (pos == -1) k = n / 2; //满足特殊性质 A
	else k = n - cnt[pos]; 
	/*
	一定不吹出现第二种超过 n / 2 的字母类型
	所以剩下的字母个数就是答案
	*/
	cout << "Huoyu" << endl << k << endl;
	for (rint i = 1; i <= k; i++) p[i].clear();
	if (pos == -1) //满足特殊性质 A
	{
		int idx = 0;
		for (rint i = 0; i < 27; i++)
			for (rint j : v[i]) 
			    id[++idx] = j;
				// 按照 26 个字母的顺序将输入的字符串存入 id
		for (rint i = 1; i <= k; i++)
		{
			p[i].push_back(id[i]);
			p[i].push_back(id[i + n / 2]);			
		}// 把 (i, i + n / 2) 搭配存
		if (n & 1) //如果是奇数
	    {
			p[1].push_back(id[n]);
		}
	} 
	else 
	// 不满足特殊性质 A
	// 即存在绝对众数
	{
		int idx = 0, check = -1;
		for (rint i = 1; i <= n; i++)
		{
			if (s[i] == pos + 'a') id[++idx] = i;
			else 
			{
				if (check == -1)
				{
					check = 0;
					p[k].push_back(i);
				}
				else
				{
					check++;
					p[check].push_back(i);
				}
			}		
		}
		idx = 0;
		for (rint i = 1; i < k; i++)   p[i].push_back(id[++idx]);
		while (id[idx + 1] < p[k][0])  p[k - 1].push_back(id[++idx]);
		while (idx < cnt[pos])         p[k].push_back(id[++idx]);
	}
	for (rint i = 1; i <= k; i++) sort(p[i].begin(), p[i].end());
	for (rint i = 1; i <= k; i++) 
	{
		cout << p[i].size() << ' ';
		for (rint j : p[i]) cout << j << ' ';
		cout << endl;
	}
	return ;
}

signed main() 
{
	int c, T;
	cin >> c >> T;
	while (T--) solve();
	return 0;
}

T4「KDOI-10」超级演出

首先有个非常好拿的 32pts 部分分可以拿

正解通过向 xxseven 大佬学习已经领会了。%%% xxseven

考虑在线操作，貌似并不好处理。但是可以离线处理。选出来的是连续区间，找出序列中每个位置可以走的最大的左端点，同时维护上一次出现的位置因为会出现重复的情况。同时维护最后出现的位置。没必要开数组维护，这个可以在计算时动态维护。然后计算区间贡献，现在就可以离线处理了，变成离线二维数点问题。

当前算法复杂度为 \(O(n^2)\)，考虑优化算法。

发现可以根号分治一下（话说是怎么做到赛时想出来可以根号分治的）如果一个点的出边数小于等于根号，那么每次暴力找即可。出边数小于等于根号暴力找。大于的话开 vector 记录出度大于根号的前驱。那么，出边在 sqrt(m) 以上的点称为大点 这些点的 lst 值本来应该是在修改其他点的时候顺带维护的。但是我们真正修改它的时候要在树状数组里面把原来的值减掉 因此我们不能直接在维护大点时直接修改 lst，tp[] 数组就是用来临时记录 lst 将要被修改为多少，当碰到某个命令为这个大点时，我们再去真正更新。

最后复杂度为 \(O(n \sqrt n)\)

32pts 代码

void dfs(int x) 
{
	vis[1] = 0;
	if (!vis[root]) return;
	for (rint i = 0; i < g[x].size(); i++) 
	{
		if (g[x][i] == 1) 
		{
			flag = 1;
			vis[root] = 0;
			return ;
		}
		if (!vis[g[x][i]]) dfs(g[x][i]);
	}
}

signed main() 
{
	cin >> c;
	cin >> n >> m >> k >> q;
	for (rint i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
	}
	for (rint i = 1; i <= k; i++) cin >> a[i];
	while (q--) 
	{
		for (rint i = 1; i <= n; i++) vis[i] = 1;
		int ans = n - 1;
		int l, r;
		cin >> l >> r;
		for (rint i = l; i <= r; i++) 
		{
			flag = 0;
			root = a[i];
			dfs(a[i]);
			if (flag) ans--;
		}
		cout << ans << endl;
	}
	return 0;
}

100 pts 代码
#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 5e5 + 5;

int n, m, k, q;
int c[N], tr[N], lst[N], ans[N], out[N], tp[N];
vector<int> e[N], E[N];
vector<pair<int, int> > g[N];
bool flag[N];

int lowbit(int x) {return x & -x;}

void add(int x, int y)
{
	if (!x) return ;
	for (; x < N; x += lowbit(x)) tr[x] += y;
}

int ask(int x)
{
	int ans = 0;
	for (; x; x -= lowbit(x)) ans += tr[x];
	return ans;
}

signed main() 
{
	int C;
	cin >> C >> n >> m >> k >> q;
	for (rint i = 1; i <= m; i++) 
	{
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		if (b == 1) flag[a] = 1; //记录可以一步到位的点
		out[a]++;
	}
	for (rint i = 1; i <= k; i++) cin >> c[i];
	for (rint i = 1; i <= q; i++) 
	{
		int l, r;
		cin >> l >> r;
		g[r].push_back({l, i});
	}
	int t = sqrt(m);
	for (rint i = 1; i <= n; i++) 
	{
		if (out[i] < t) continue;
		for (rint x : e[i]) E[x].push_back(i);
	}
	for (rint i = 1; i <= k; i++) 
	{
		int j = c[i], nxt = 0;
		if (out[j] >= t) nxt = tp[j];
		else 
		{
			for (rint x : e[j]) 
			    nxt = max(nxt, lst[x]);
		}
		if (flag[j]) nxt = i; //一步到位
		add(lst[j], -1), lst[j] = nxt;
		add(lst[j], 1);
		for (rint u : E[j]) tp[u] = max(tp[u], lst[j]);
		for (auto e : g[i]) ans[e.second] = ask(k) - ask(e.first - 1);
	}
	for (rint i = 1; i <= q; i++)
	{
		cout << n - 1 - ans[i] << endl;
	} 
	return 0;
}

标签：2024.10,return,int,rint,13,lst,max,模拟,define
From： https://www.cnblogs.com/spaceswalker/p/18464891

相关文章

  • [47] (CSP 集训) CSP-S 模拟 11
    因为有人想看T3\(nk^2\)所以先发一下A.玩水注意到只有在形如下面这样的地方才会发生分叉?aa?所以\(f_{i,j}\)表示从\((1,1)\)到\((i,j)\)的矩阵中的最大路径方案数，考虑转移普通的转移是\(f_{i,j}=\max(f_{i,j-1},f_{i-1,j})\)如果\(a_{i-1,j}=a_{i,j-1}\)，则有......
  • 2024/10/13 模拟赛总结
    人机体检，\(0+0+0+0=0\)，打代码源去了#A.一般图最小匹配下次看到这种范围一定要想到dp啊，令\(dp_{i,j}\)为前\(i\)个元素选了\(j\)对点的最小代价由于边权是绝对值，可以对原数组排一遍序，选取的两个点就一定在排序后数组的相邻节点那么就可以得出式子：\(dp_{i,j}=\min\{dp_......
  • 2024.10.14 test
    B平面上有\(n\)个点以及\(k\)条未知的平行线，每个点都分属一条线，每条线都有至少\(2\)点。给出一种方案。\(n\le4e4,k\le50\)。每个点分属一条线的条件非常重要。考虑利用鸽巢原理。考虑取出\(k+1\)个没有两对点同斜率的点，那么，至少有两个点在一条线上，那么就可以确定斜......
  • 题解：P11132 【MX-X5-T4】「GFOI Round 1」epitaxy
    ProblemLink【MX-X5-T4】「GFOIRound1」epitaxy题目描述给你两个正整数\(n,m\)。定义一个\(1\simn\)的排列\(p\)的价值为所有的\(n-m+1\)个长度为\(m\)的连续子串内最大值的最大公因数。（规定单个数的最大公因数为其自身。）请你求出一个在所有\(1\simn\)......
  • 题解：P9137 [THUPC 2023 初赛] 速战速决
    ProblemLink[THUPC2023初赛]速战速决题目描述题意清晰，不再过多赘述。Solution每张不同的卡是等效的。小\(J\)手上的卡牌只有\(2\)种情况：手上没有相同的牌和有相同的牌。情况\(1\)：小\(J\)手上的牌等价于\(1\simn\)（但其实没用），令其手上的牌为\(b_1,b_2,\ldo......
  • 洛谷P1373：小 a 和 uim 之大逃离
    洛谷P1373：小a和uim之大逃离题意略思路DP：记dp[i][j][c][0/1]表示走到\(i\)行\(j\)列时，两人容量之差为\(c\)的方案数，\(0\)表示\(\rm小a\)走的最后一步，\(1\)表示\(\rmuim\)走的最后一步。容易得出转移方程：dp[i][j][l][0]+=dp[i-1][j][l-a[i][j]+k][1];dp[......
  • 省选模拟赛
    认为只有k个位置有值的序列差分之后会形成k个颜色段，建议送回普及组重学差分与前缀和A考虑把硬币序列异或差分，操作变成选两个距离为\(a_i\)的位置翻转，差分完序列上只有\(2k\)个\(1\)，对其中任意两个\(1\)预处理出把它们同时变为\(0\)的最小操作数，状压BFS即可。B......
  • 13.3寸工业三防平板数字化工厂产线数采手持终端
    在数字化工厂的建设浪潮中，高效可靠的数据采集终端至关重要。尤其在水处理、食品加工等特殊工业环境下，设备的耐用性和数据安全性面临严峻挑战。传统的平板电脑难以应对复杂的工业现场，而一款性能卓越、坚固耐用的工业三防平板则成为提升生产效率和数据准确性的关键。这款13.3寸......
  • csp-s模拟11
    csp-s模拟11\(T1\)T2203.玩水(water)\(100pts\)定义一个点\((i,j)\)是分点当且仅当\(s_{i,j+1}=s_{i+1,j}\)，而一个点\((i,j)\)是合点当且仅当\((i-1,j-1)\)是分点。先考虑若只有两个人时，只要存在一个分点就一定有解。扩展到三个人时，若存在一个合点可以通过......
  • DSP视频教程第13期：汇编浮点库qfplib性能媲美TI的IQmath和硬件FPU，强于C库的math和ARM D
    视频教程汇总帖：https://www.armbbs.cn/forum.php?mod=viewthread&tid=110519 本期专题视频给大家分享一个qfplib浮点库，这个库早期周报给大家分享过，后来部分网友测试非常给力，所以我们DSP视频教程也给大家分享一期【视频】https://www.bilibili.com/video/BV1Te2DY1Edx/【......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99