$NOIP\ 2018\ Day2$ 模拟考试 题解报告

2023-12-17 13:36:51

目录

\(NOIP\ 2018\ Day2\) 模拟考试 题解报告

得分情况

\(T1\) \(84\ Pts\)

\(T2\) \(15\ Pts\)

\(T3\) \(44\ Pts\)

总分: \(143\ Pts\)

考试过程

这次的题确实没做过... 所以人就没了

读完题 从 \(T1\) 开始 分析题目 分测试点 先写了六十分的树 四十分钟 调过大样例 四十分的基环树没写 转 \(T2\) 读完题 稍微分析了二十分钟 感觉不可做 跑路了 转 \(T3\) 分析了一下 发现有四十四分的暴力 写了个 \(O(nm)\) 的 自己跑了几组数据 一共大概半个小时 感觉四十四分没问题 回 \(T1\) 去写剩下的四十分 二十分钟想了一下 写的时候发现不对劲 又改 写了一半 感觉直接枚举环上的边断边 每次跑一个 \(O(n)\) 的会超时 去分析性质 贪了一下 写成 \(O(n)\) 的 常数略大 第一次贪假了 又调 剩四十分钟的时候调过大样例 继续看 \(T3\) 然而并没有什么进展

题解

\(T1\) 旅行

贪心贪假... 挂成 \(84\) 没想出来为什么贪心假了 改了一下 换成 \(O(n^2)\) 的就过了 虽然有点慢 但是确实能够

/*
  Time: 6.6
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#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 = 5e3 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("travel.in", "r", stdin);
	freopen("travel.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, m, ans[A], cnt, d[A][A], s, t, vis2[A], p1, p2, pos, _ans[A];
struct edge {int v, nxt;} e[A << 1];
int head[A], ecnt;
bool vis[A], cl[A];
/*------------------------------------变量定义*/
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 add_edge(int u, int v) {e[++ecnt] = (edge){v, head[u]}; head[u] = ecnt;}
void dfs1(int u, int pre) {
	vis[u] = 1; _ans[++cnt] = u; int tot = 0;
	for(int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
		if(v != pre && !vis[v] && !((u == p1 && v == p2) || (u == p2 && v == p1))) d[u][++tot] = v;
	std::sort(d[u] + 1, d[u] + 1 + tot);
	if(tot) for(int i = 1; i <= tot; i++)
		if(!vis[d[u][i]]) dfs1(d[u][i], u);
}
void work1() {
	dfs1(1, 0);
	for(int i = 1; i < cnt; i++) printf("%d ", _ans[i]);
	printf("%d\n", _ans[cnt]);
}
void dfs2(int u, int pre) {
	vis2[u] = pre;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v; if(v == pre) continue;
		if(vis2[v]) {vis2[v] = u; s = u, t = v; return ;}
		else dfs2(v, u);
		if(s && t) return ;
	}
}
void dfs3(int u, int pre) {
	for(int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
		if(cl[v] && v != pre)
		{
			if(v > pos) {p1 = u, p2 = v; return ;}
			else dfs3(v, u);
		}
}
void up_date() {
	for(int i = 1; i <= cnt; i++)
		if(_ans[i] > ans[i]) return ;
		else if(_ans[i] < ans[i]) break;
	for(int i = 1; i <= cnt; i++) ans[i] = _ans[i];
}
void work2() {
	s = t = 0; dfs2(1, 0); pos = 0; memset(ans, 63, sizeof ans);
	for(int i = s; vis2[i] != s; i = vis2[i])
	{
		p1 = i; p2 = vis2[i]; cnt = 0;
		memset(vis, 0, sizeof vis); dfs1(1, 0);
		up_date();
	}
	for(int i = 1; i < cnt; i++) printf("%d ", ans[i]); printf("%d\n", ans[cnt]);
	
//	for(int i = s; vis2[i] != s; i = vis2[i]) cl[i] = 1; cl[t] = 1;
//	if(cl[1]) t = 1;
//	for(int i = head[t]; i; i = e[i].nxt) if(cl[e[i].v]) pos = Max(pos, e[i].v);
//	dfs3(t, pos); work1();
} 
/*----------------------------------------函数*/
int main() {
	File();
	n = read(); m = read(); p1 = p2 = 0;
	for(int i = 1; i <= m; i++)
	{
		int x = read(), y = read();
		add_edge(x, y); add_edge(y, x);
	}
	if(m == n - 1) work1();
	else work2();
	return 0;
}
/*
6 5
1 3
2 3
2 5
3 4
4 6

10 9
1 3
2 3
2 5
3 4
4 6
5 7
2 8
8 10
2 9
4 6


字典序最小 一定是从一号点开始
一个节点只能被经过两次 入一次 出一次 不会有左右乱窜的情况
所以在每一个点直接比较左右孩子的点的编号 贪一下 
题目保证图联通 不存在自环 不存在重边 
60 分的树
大样例挂了 
四十分钟过 60 分的大样例 
40 分的基环树 
分 1 号点在不在环上进行讨论
略 先不写 去看别的题 
感觉不对劲 可能有坑 
环上有一次回头的机会 
11 11
11 10
10 6
6 8
6 4
8 9
4 3
9 7
7 5
5 3
1 2
1 3

大样例挂了 还有一个小时
12 12
1 10
1 2
2 8
2 3
3 9
3 4
4 5
5 7
7 12
7 6
6 1
6 11

只要把环断开 和 60 的一样
考虑在哪断环 贪 
从一号点进去 找一个大点的 记下来 往另一边搜 找到的第一个比记下来的那个点大的 再往下一个 断开 
二十分钟 过大样例 
*/
/*
贪心挂成84
改成 n 方的 过了
可能这就是这个题只能当 T1 的原因吧
*/

建议加强数据把 n 方卡掉

\(T2\) 填数游戏

真心不可做 输出样例有15分好评

看第一眼以为是状压 毕竟数据范围在那放着 推了一下 发现没法写... 弃了

正解: 推式子 打表 + 找规律

对于一道狗比题就要用狗比的做法

所以...先打个表

枚举所有情况 将经过的数字压成一个二进制数 比较两个路径的字典序 相当于比较两个二进制数的大小

记搜 存一个二元组 记录从每个点出发构成的二进制数(最小值, 最大值) 如果一个点向右走的最小值小于向下走的最大值 就不合法

直接暴力构造棋盘 按照上面的方法进行 \(check\) 每构造完一列就 \(check\) 一下 可能会稍微快一点

/*
  Time: 6.6
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define p1 first
#define p2 second
#define R x, y + 1, mx, my
#define D x + 1, y, mx, my
#define mk std::make_pair
#define pa std::pair <int, int>
#define Mp (mp[x][y] << mx + my - x - y)
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
}
/*----------------------------------------文件*/
int n, m, ans;
bool mp[10][10];
pa f[10][10];
/*------------------------------------变量定义*/
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;
}
/*----------------------------------------快读*/
pa check(int x, int y, int mx, int my) {
	if(f[x][y].p1) return f[x][y];
	if(x == mx && y == my) return f[x][y] = mk(mp[x][y], mp[x][y]);
	if(x == mx) {pa tmp = check(R); return f[x][y] = mk(tmp.p1 + Mp, tmp.p2 + Mp);}
	if(y == my) {pa tmp = check(D); return f[x][y] = mk(tmp.p1 + Mp, tmp.p2 + Mp);}
	pa tmp1 = check(R); if(!~tmp1.p1) return f[x][y] = mk(-1, -1);
	pa tmp2 = check(D); if(!~tmp2.p2 || tmp1.p1 < tmp2.p2) return f[x][y] = mk(-1, -1);
	return f[x][y] = mk(tmp2.p1 + Mp, tmp1.p2 + Mp);
}
void dfs(int x, int y) {
	if(y == 1 && x > 1)
	{
		memset(f, 0, sizeof f);
		if(check(1, 1, x - 1, m).p1 == -1) return ;
		if(x == n + 1) {ans++; return ;}
	}
	if(y == m) mp[x][y] = 0, dfs(x + 1, 1), mp[x][y] = 1, dfs(x + 1, 1);
	else mp[x][y] = 0, dfs(x, y + 1), mp[x][y] = 1, dfs(x, y + 1);
}
void work() {
	memset(mp, 0, sizeof mp); ans = 0; dfs(1, 1);
	printf("n = %d; m = %d : %d\n", n, m, ans);
}
/*----------------------------------------函数*/
int main() {
	int N = read(), M = read();
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
			n = i, m = j, work();
	return 0;
}

实测 \(m = 8\ n = 8\) 的数据跑了大概不太到十分钟的样子 跑完大概是这个样子的

$NOIP\ 2018\ Day2$ 模拟考试 题解报告

$NOIP\ 2018\ Day2$ 模拟考试 题解报告

有点蒙

把数据稍微整理一下

n, m 1 2 3 4 5 6 7 8
1 2 4 8 16 32 64 128 256
2 4 12 36 108 324 972 2916 8748
3 8 36 112 336 1008 3024 9072 27216
4 16 108 336 912 2688 8064 24192 72576
5 32 324 1008 2688 7136 21312 63936 191808
6 64 972 3024 8064 21312 56768 170112 510336
7 128 2916 9072 24192 63936 170112 453504 1360128
8 256 8748 27216 72576 191808 510336 1360128 3626752

手要废了 真不错

看他一下

当 \(n\) 或 \(m\) 为 \(1\) 的时候 \(ans = 2 ^{ \max\{n, m\}}\)

别的呢

看 \(2\) 这一列

很显眼的发现

\[4 \times 3 = 12\\ 12 \times 3 = 36\\ 36 \times 3 = 108 \]

再看

\[108 \times 3 = 324\\ 324 \times 3 = 972\\ 972 \times 3 = 2916\\ 2916 \times 3 = 8718 \]

似乎有规律

再看 \(3\) 这一列

\[8 \times 3 \ne 36\\ 36 \times 3 \ne 112\\ 112 \times 3 = 336\\ 336 \times 3 = 1008\\ 1008 \times 3 = 3024\\ 3024 \times 3 = 9072\\ 9072 \times 3 = 27216 \]

...

上面两个好像出了一点问题

再看第 \(4\) 列

\[16 \times 3 \ne 108\\ 108 \times 3 \ne 336\\ 336 \times 3 \ne 912\\ 912 \times 3 \ne 2688\\ 2688 \times 3 = 8064\\ 8064 \times 3 = 24192\\ ... \]

第 \(4\) 列从第五行开始满足

第 \(5\) 列从第六行开始满足

第 \(6\) 列从第七行开始满足

可以猜测 第 \(7\) 列则应该是第八行了 那么当 \(n = 7\ m = 9\) 的时候答案应该是 \(1360128 \times 3 = 4080384\) 跑一下试试

过了许久...

$NOIP\ 2018\ Day2$ 模拟考试 题解报告

大胆猜:

当 \(m > n + 1\) 的时候 \(ans_{n, m} = ans_{n, m - 1} \times 3\)

推广一下 \(ans_{n, m} = ans_{n, n + 1} \times 3^{m - n - 1}\)

好办了...

只需要再把 \(ans_{8, 9}\) 跑出来就行了 其他的就可以直接算了

代码

/*
  Time: 6.6
  Worker: Blank_space
  Source: P5023 [NOIP2018 提高组] 填数游戏
*/
/*--------------------------------------------*/
#include<cstdio>
#define int long long
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
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(".in", "r", stdin);
	freopen(".out", "w", stdout);
}
/*----------------------------------------文件*/
int n, m;
int a[10][10] = {
	{0},
	{0, 2, 4},
	{0, 0, 12, 36},
	{0, 0, 0, 112, 336},
	{0, 0, 0, 0, 912, 2688},
	{0, 0, 0, 0, 0, 7136, 21312},
	{0, 0, 0, 0, 0, 0, 56768, 170112},
	{0, 0, 0, 0, 0, 0, 0, 453504, 1360128},
	{0, 0, 0, 0, 0, 0, 0, 0, 3626752, 10879488}
};
/*------------------------------------变量定义*/
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;
}
/*----------------------------------------快读*/
int power(int b, int a = 3, int res = 1) {for(; b; a = a * a % mod, b >>= 1) if(b & 1) res = res * a % mod; return res;}
/*----------------------------------------函数*/
signed main() {
	n = read(); m = read(); if(n > m) Swap(n, m);
	if(n == 1) printf("%lld", 1 << m);
	else if(n == m || m == n + 1) printf("%lld", a[n][m]);
	else printf("%lld", a[n][n + 1] * power(m - n - 1) % mod); 
	return 0;
}

\(T3\) 保卫王国

咕了

上一篇：Day2


下一篇：rust学习------[day2]理解ownership的特性