• 8.27 校内模拟赛 题解报告
  • 扯
  • 得分情况
  • 题解
    • T1 数列
    • T2 最短路
    • T3 公交车

8.27 校内模拟赛 题解报告

扯

T1 位运算 map 代桶水了过去

T2 广搜不判重 SB 行为++

T3 当图论题做了 暴力骗分保命

大概这场考试就是这样

关于考试过程以及一些题外话

这次考试的节奏感觉还可以 没有像昨天一样调到崩盘的情况 结论题害人

依旧是开考读题

T1 送了四十的暴力 然后是三十的 01 串 只有暴力的思路

T2 三十分的情况显然可以直接对着贪

T3 看完没什么思路

开 T1

先写的四十分的暴力 然后打算想 01 串的时候 突然想到了疑似正解的东西 写完稍微卡了一下就不管了

开 T2

第一部分直接尝试贪 + 广搜 过了样例卡了一下感觉好像没有问题 虽然最后爆零了

后面一部分感觉可以做的亚子 好像只需要调整一下搜索开始的位置就行了 然后发现那个 a 的位置好难搞 并没有想到 dp

于是就上了二维树状数组加上一波前缀和的瞎搞 于是出现了一个复杂度未知的算法 最后把前面一部分的搜索 粘了过来

写完 T2 还有不是很到一个小时 把 T3 的暴力写了 查了一下文件什么的就差不多了

赛后

Ariel: 我 T2 写的 \(O(n^2)\) 的暴力

BS: 啥? 暴力?

(看了一眼数据范围)

\(1 \leq n \leq 2000\)

BS: 暴力? 这是暴力??????

然而 BS 的广搜没有判重 而且两部分的广搜是一样的 所以 T 飞爆零了

看了一下 大概能跑好久的亚子(雾

加上判重之后 6ms 过了

SB 行为++

然后依旧是毫无用处的题解

前俩题好歹能看 毕竟有字

T3 的题解就没什么好说的了 等于没有 只能卑微的看着代码理解

得分情况

100 + 0 + 60 = 160

其实 T2 当时写的时候是想到了判重的 但是不知道哪里来的自信 反正突然就是感觉不判好像也不会炸的亚子 于是就把判重删掉了 然后就炸了

题解

T1 主要说 BS 的个人做法 并没有详细的看题解 T3 则基本是解释标程的代码 毕竟没有题解

T1 数列

首先比较好像的是暴力 \(n\) 只有 \(10\) 显然可以 \(O(2^n)\) 枚举所有状态 然后 \(O(n^2)\) 的数区间 再 \(O(n)\) 的判断一个区间是否合法

这样就得到了 \(O(2^n \times n^3)\) 的优秀复杂度(约为 \(10^9\)) 可以得到零分的优异成绩

显然可以维护一个前缀异或和让判断优化到 \(O(1)\) 这样四十分就有了

然后在写这一部分的代码的时候有这样的一句

for(int i = 1; i ^ n + 1; i++) for(int j = i; j ^ n + 1; j++) if(_s[j] ^ _s[i - 1]) res++;

这一步的操作时在数合法区间 显然 if 语句里面的是在判断两个位置是否相同 即对于一个位置找与其不同的位置的个数

这里启示 BS 想到了可以通过异或前缀和消去区间的限制 直接考虑不同的数的影响

手玩了一组样例之后 发现是可以的 同时不同的数 即合法的区间比较难找 可以用总区间减去不合法的区间个数

继续手玩样例发现 若是前缀异或和中有 \(cnt\) 个数为 \(x\)

则 \(x\) 这个数对答案的贡献为 \(cnt \choose 2\)

这样的话统计区间的复杂度可以降为线性的

但是这是在数的状态确定的前提下 即是已经搜索出的一种状态

考虑如何确定数的异或状态

显然希望 \(cnt \choose 2\) 中的 \(cnt\) 尽量的小

设 \(S = 2^k - 1\)

对于一个数 \(x \oplus S = y\) 显然 \(x\) 与 \(y\) 为一一对应的 那么可以通过将 \(x\) 转化为 \(y\) 来降低 \(x\) 的数量 再次手玩了几组数据 发现两个数的数量趋向于相等时最好的

那么直接对于原序列维护异或前缀和之后统计每个数的数量再对每个数尝试调整即可 复杂度为 \(O(n)\)

这样就得到了这个题目的复杂度优秀的解法

然后尝试用一开始那个暴力拍了一下 六组数据就挂了 那组数据是这样的

3 1
1 1 1

这么水的数据都会挂?

跑出来的结果是 \(5\) 而可以通过手玩得到答案为 \(4\)

通过调试程序发现 前缀异或和中第二个位置为 \(0\) 也就是前两个数构成的区间不合法 而这一位置并没有被归为不合法的区间

在处理区间的时候 通过差分差出来的左端点为 \(0\) 那个位置 只要预先将 \(0\) 这一位置归进去就行了

代码

/*
  Source: 数列
*/
#include<map>
#include<cstdio>
#include<cstring>
#define int long long
#define pt putchar(' ')
#define pn putchar('\n')
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*----------------------------------------------------------*/
const int A = 1e4 + 7;
const int B = 2e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*----------------------------------------------------------*/
inline void File() {
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
}
/*----------------------------------------------------------*/
int n, K, S, pa[20], a[B], _s[20], ans, sum[B];
std::map <int, int> mp;
std::map <int, bool> vis;
/*----------------------------------------------------------*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------------------------*/
void check() {
	int res = 0;
	for(int i = 1; i ^ n + 1; i++) _s[i] = _s[i - 1] ^ pa[i];
	for(int i = 1; i ^ n + 1; i++) for(int j = i; j ^ n + 1; j++) if(_s[j] ^ _s[i - 1]) res++;
	ans = Max(ans, res);
}
void dfs(int t) {
	if(t == n + 1) {check(); return ;}
	pa[t] = a[t]; dfs(t + 1); pa[t] = a[t] ^ S; dfs(t + 1);
}
void work1() {dfs(1); Print(ans);}
int C2(int x) {return x * (x - 1) >> 1;}
void work2() {
	ans = n * (n + 1) >> 1; mp[0] = 1;
	for(int i = 1; i ^ n + 1; i++) sum[i] = sum[i - 1] ^ a[i], mp[sum[i]]++;
	for(int i = 1; i ^ n + 1; i++) if(mp[sum[i]] > 1)
	{
		int x = sum[i], y = sum[i] ^ S;
		if(mp[x] > mp[y] + 1) mp[x]--, mp[y]++, sum[i] ^= S;
	}
	for(int i = 0; i ^ n + 1; i++) if(!vis[sum[i]]) vis[sum[i]] = 1, ans -= C2(mp[sum[i]]);
	Print(ans);
}
void Main() {
	File();
	n = read(); K = read(); S = (1 << K) - 1;
	for(int i = 1; i ^ n + 1; i++) a[i] = read();
	work2();
}
/*----------------------------------------------------------*/
signed main() {Main(); return 0;}

T2 最短路

考虑最开始的三十分 没有修改操作 只需要贪心的选取即可

从起点开始遍历 只考虑下一层中字典序最小的格子 进行广搜 注意判重即可

然后考虑修改

不难发现前面若干个位置(至少 \(k\) 个)一定是 a 需要考虑这个 a 能铺到什么位置

设 \(f_{i, j}\) 表示在位置 \((i, j)\) 需要经过多少不为 a 的格子

统计经过的数量少于 \(k\) 的格子中距离最远的 将其作为起点开始搜即可

代码

/*
  Source: 最短路
*/
#include<queue>
#include<cstdio>
#include<cstring>
#define pt putchar(' ')
#define pn putchar('\n')
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*----------------------------------------------------------*/
const int A = 2021;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*----------------------------------------------------------*/
inline void File() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
}
/*----------------------------------------------------------*/
int n, K, f[A][A], dep;
char s[A][A], pa[A << 1];
bool vis[A][A];
struct node {
	int dep, x, y;
};
std::queue <node> q1, q2;
/*----------------------------------------------------------*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------------------------*/
void work1() {
	dep = 1; q1.push((node){1, 1, 1}); pa[dep] = s[1][1];
	while(!q1.empty() && dep != 2 * n - 1)
	{
		char min = 123;
		while(!q1.empty() && q1.front().dep == dep)
		{
			int x = q1.front().x, y = q1.front().y;
			q2.push(q1.front()); q1.pop();
			if(y + 1 <= n && s[x][y + 1] < min) min = s[x][y + 1];
			if(x + 1 <= n && s[x + 1][y] < min) min = s[x + 1][y];
		}
		pa[++dep] = min;
		while(!q2.empty())
		{
			int x = q2.front().x, y = q2.front().y; q2.pop();
			if(y + 1 <= n && !vis[x][y + 1])
			{
				vis[x][y + 1] = 1;
				if(s[x][y + 1] == min) q1.push((node){dep, x, y + 1});
			}
			if(x + 1 <= n && !vis[x + 1][y])
			{
				vis[x + 1][y] = 1;
				if(s[x + 1][y] == min) q1.push((node){dep, x + 1, y});
			}
		}
	}
	printf("%s", pa + 1);
}
void work2() {
	f[1][1] = s[1][1] != 'a';
	for(int i = 1; i ^ n + 1; i++) f[0][i] = f[i][0] = INF;
	for(int i = 1; i ^ n + 1; i++) for(int j = 1; j ^ n + 1; j++)
		if(i != 1 || j != 1) f[i][j] = Min(f[i - 1][j], f[i][j - 1]) + (s[i][j] != 'a');
	for(int i = 1; i ^ n + 1; i++) for(int j = 1; j ^ n + 1; j++)
		if(f[i][j] <= K) dep = Max(dep, i + j - 1);
	for(int i = 1; i ^ n + 1; i++) for(int j = 1; j ^ n + 1; j++)
		if(f[i][j] <= K && i + j - 1 == dep) vis[i][j] = 1, q1.push((node){dep, i, j});
	for(int i = 1; i ^ dep + 1; i++) pa[i] = 'a';
	while(!q1.empty() && dep != 2 * n - 1)
	{
		char min = 123;
		while(!q1.empty() && q1.front().dep == dep)
		{
			int x = q1.front().x, y = q1.front().y;
			q2.push(q1.front()); q1.pop();
			if(y + 1 <= n && s[x][y + 1] < min) min = s[x][y + 1];
			if(x + 1 <= n && s[x + 1][y] < min) min = s[x + 1][y];
		}
		pa[++dep] = min;
		while(!q2.empty())
		{
			int x = q2.front().x, y = q2.front().y; q2.pop();
			if(y + 1 <= n && !vis[x][y + 1])
			{
				vis[x][y + 1] = 1;
				if(s[x][y + 1] == min) q1.push((node){dep, x, y + 1});
			}
			if(x + 1 <= n && !vis[x + 1][y])
			{
				vis[x + 1][y] = 1;
				if(s[x + 1][y] == min) q1.push((node){dep, x + 1, y});
			}
		}
	}
	printf("%s", pa + 1);
}

void Main() {
	File();
	n = read(); K = read();
	for(int i = 1; i ^ n + 1; i++) scanf("%s", s[i] + 1);
	if(!K) work1();
	else work2();
}
/*----------------------------------------------------------*/
signed main() {Main(); return 0;}

T3 公交车

暴力就算了 比较显然

总体的思路来说的话 大概是预处理出两个数组

\(f_i\) 表示到 \(i\) 的最晚出发时间

\(g_i\) 表示赶第 \(i\) 趟车的最晚出发时间

从代码来看的话 按照每辆车的出发时间排序

对一个点 到达该点的最晚出发时间为赶上这条线的最晚出发时间中的最晚时间

对一条线 赶上的最晚出发时间为到达该线出发点的最晚出发时间与该线发车时间中的较早时间

特别的 如果一条线的终点为 \(n\) 号点 统计该线的到达时间以及赶上该线的最晚出发时间

按照到达时间排序后 如果一条线的到达时间早于另一条线 且前者的的出发时间更晚 显然可以以前者的出发时间替换后者的出发时间

以此进行答案的更新 使其满足单调性

最后对每次询问进行二分查找 在能到达终点的所有线中找到达时间

代码

/*
  Source: 公交车
*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define pt putchar(' ')
#define pn putchar('\n')
#define mk std::make_pair
#define pr std::pair <int, int> 
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*----------------------------------------------------------*/
const int A = 1e5 + 7;
const int B = 3e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*----------------------------------------------------------*/
inline void File() {
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
}
/*----------------------------------------------------------*/
int n, m, f[A], g[B], Q, cnt;
struct node {int u, v, t1, t2;} a[B];
pr t, ans[B];
std::priority_queue <pr> q;
/*----------------------------------------------------------*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------------------------*/
bool cmp(node x, node y) {return x.t1 < y.t1;}
void solve(int x) {
	int l = 1, r = cnt, tmp = 0; 
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(ans[mid].first <= x) tmp = mid, l = mid + 1;
		else r = mid - 1;
	}
	Print(ans[tmp].second); pn;
}
void Main() {
	n = read(); m = read(); memset(f, -1, sizeof f); f[1] = INF; ans[0] = mk(-1, -1);
	for(int i = 1; i ^ m + 1; ++i) a[i] = (node){read(), read(), read(), read()};
	std::sort(a + 1, a + 1 + m, cmp);
	for(int i = 1; i ^ m + 1; ++i)
	{
		while(!q.empty() && -q.top().first <= a[i].t1) t = q.top(), q.pop(), f[a[t.second].v] = Max(f[a[t.second].v], g[t.second]);
		g[i] = Min(f[a[i].u], a[i].t1); q.push(mk(-a[i].t2, i));
		if(a[i].v == n) ans[++cnt] = mk(a[i].t2, g[i]);
	}
	std::sort(ans + 1, ans + 1 + cnt);
	for(int i = 2; i ^ cnt + 1; ++i) ans[i].second = Max(ans[i].second, ans[i - 1].second);
	Q = read(); while(Q--) solve(read());
}
/*----------------------------------------------------------*/
signed main() {Main(); return 0;}