【C++】信息学联赛模拟题1+解析+代码_# 碎片(fragment) ## 题目背景 in the ocean, deep down, un

一. 选手须知

提交的源程序文件名

编译选项

1 指引（guide）

【题目背景】

Wake up, dead boy, enter adventureland.
Tricksters, magicians will show you all that’s real.

【题目描述】

N 名迷途的旅者需要小 X 的指引。
初始时， 每一名旅者 i 位于坐标(Ai,Bi)处， 旅者们只能够向右或是向上移动，
也就是说， 他们只能够增加自己的某一维坐标， 而不能减小它们。
这片大地上同样存在者 N 个出口， 每一个出口 i 位于坐标(Ci,Di)处， 一个出
口一旦被某个旅者通过， 它们就会一并消失。
请帮助小 X 计算他至多能够指引多少旅者离开这片大地。

【输入格式】

从文件 guide.in 中读取数据。
第一行一个整数 Num， 表示测试点编号， 以便选手方便地获得部分分， 你可
能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点相同。
接下来一行一个整数 N， 含义见题目描述。
接下来 N 行， 每行两个整数 Ai、 Bi， 表示每一名旅者的坐标。
接下来 N 行， 每行两个整数 Ci、 Di， 表示每一个出口的坐标。

【输出格式】

一行一个整数， 表示答案。

【样例 1 输入】

6 3 2
0
3 1
1 3
4 2
0 4
5 5
1
2
3
4
5
6
7

【样例 1 输出】

2
1

【样例 1 解释】

让位于(2,0)的旅者走到(4,2)处，
让位于(3,1)的旅者走到(5,5)处。

【样例 2】

见下发文件 guide2.in， guide2.ans

【样例 3】

见下发文件 guide3.in， guide3.ans

【样例 4】

见下发文件 guide4.in， guide4.ans

【样例 5】

见下发文件 guide5.in， guide5.ans

【数据范围及子任务】

对于所有测试数据， 保证 1≤N≤105， 0≤Ai、 Bi、 Ci、 Di<2N。
保证 A1,A2,…,AN,C1,C2,…,CN 两两不同。
保证 B1,B2,…,BN,D1,D2,…,DN 两两不同。
特殊性质 1： 保证 Ai=Bi。
特殊性质 2： 保证 Ci=Di。

【解析】

每个旅者可以选的出口就是从他自己的坐标到右上边界的一个矩形。

同时考虑x,y坐标很难下手。我们将旅者和出口的坐标按x坐标排序。

然后从大到小枚举，每个旅者匹配比其y坐标大的第一个出口（y坐标更大的出口可能匹配上一个y坐标大的旅者)，可以使用线段树维护。

【代码】

#pragma GCC optimize(3,"Ofast","inline")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

typedef long long LL;

const int N=2e5+5;

set <int> st;
bool type[N];
int pos[N];

template <typename T> void read(T &x) {
	x=0;
	int f=1;
	char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-f;
	for(; isdigit(c); c=getchar()) x=x*10+c-'0';
	x*=f;
}

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

template <typename T> void writeln(T x) {
	write(x);
	puts("");
}

int main() {
	freopen("guide.in","r",stdin);
	freopen("guide.out","w",stdout);
	int num; 
	read(num);
	int n; 
	read(n); 
	st.clear();
	for(int i=1; i<=n; i++) {
		int x,y; 
		read(x),read(y);
		type[x]=1,pos[x]=y;
	}
	for(int i=1; i<=n; i++) {
		int x,y; 
		read(x),read(y);
		type[x]=0,pos[x]=y;
	}
	int ans=0;
	for(int i=0; i<2*n; i++) {
		if(type[i]) st.insert(pos[i]);
			else {
				set <int>::iterator tmp=st.lower_bound(pos[i]);
				if(tmp==st.begin()) continue;
				tmp--; 
				ans++;
				st.erase(tmp);
			}
	}
	writeln(ans);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

2 碎片（fragment）

【题目背景】

In the ocean, deep down,
Under raging waves, wrapped in memories,
You’ll find wrecks of stately ships,
They all went astray.

【题目描述】

小 X 的记忆中， 有一幅 N * M 的中心对称的图案。
而现在， 他的脑海中只有一幅有所变动的图案， 它同样是 N * M 的， 但却不
一定是中心对称的。
小 X 决定修补这一图案， 他能够进行的操作共有两种： 交换两行， 或者交换
两列。 小 X 想要知道能否通过有限（可能为 0） 次操作让它变得中心对称。
为了保证数据的强度， 一个测试点中可能包含多组测试数据。

【输入格式】

从文件 fragment.in 中读取数据。
第一行两个整数 Num、 T， Num 表示测试点编号， 以便选手方便地获得部分
分， 你可能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点
相同； T 表示该测试点中包含的测试数据的组数。
对于接下来每一组测试数据， 第一行两个整数 N、 M， 表示图案的大小。
接下来一个 N 行 M 列的字符矩阵， 表示图案。

【输出格式】

输出 T 行， 每行一个 YES 或 NO， 表示是否能够使图案中心对称。

【样例 1 输入】

6 1
2 3
ABC
BAC
1
2
3
4

【样例 1 输出】

YES
1

【样例 1 解释】

交换第 2 列和第 3 列， 得到以下图案：
ACB
BCA
它是中心对称的。

【样例 2】

见下发文件 fragment2.in, fragment2.ans

【样例 3】

见下发文件 fragment3.in, fragment3.ans

【数据范围及子任务】

对于所有测试数据， 保证 1≤N、 M≤12， 1≤T≤10， 图案由大写字母组成。
特殊限制： 图案仅由 A 和 B 组成。

【解析】

这些行和列的位置并不重要，只需要考虑相对应的行和列使得合法即可，那么暴力选择第一个未被选择的行，再去找一个匹配，时间复杂度 $O((12!/6!/2^6{)}^{2}t)=O(10^{8}t)$ （然后如果是奇数行或奇数列，需要枚举某一行/列在最中间）

考虑剪枝，很明显两行/列要匹配至少每一种字母个数要相同，因此可以预处理出可以匹配的两个行/列（可能也不需要剪枝），然后再匹配一组后判断当前能否合法。

【代码】

#pragma GCC optimize(3,"Ofast","inline")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N=15;

int n,m;
int rnum[N],cnum[N];
bool solved;
bool visrow[N],viscol[N];
bool row[N][N],col[N][N];
char mp[N][N];

template <typename T> void read(T &x) {
	x=0;
	int f=1;
	char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-f;
	for(; isdigit(c); c=getchar()) x=x*10+c-'0';
	x*=f;
}

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

template <typename T> void writeln(T x) {
	write(x);
	puts("");
}

inline void check() {
	for(int i=1; i<=n; i++)
	for(int j=1; j<=m; j++)
		if(mp[rnum[i]][cnum[j]]!=mp[rnum[n-i+1]][cnum[m-j+1]]) return;
	printf("YES\n");
	solved=1;
}

inline void workc(int pos,int type) {
	if(solved) return;
	if(pos == 0) {
		check();
		return;
	}
	if(type) {
		for(int i=1; i<=m; i++) {
			viscol[i]=1;
			cnum[pos]=i;
			workc(pos-1,0);
			viscol[i]=0;
		}
	} else {
		for(int i=1; i<=m; i++) {
			if(viscol[i]) continue;
			for(int j=i+1; j<=m; j++)
				if(!viscol[j] && col[i][j]) {
					viscol[i]=1;
					viscol[j]=1;
					cnum[pos] = i;
					cnum[m+1-pos]=j;
					workc(pos-1,0);
					viscol[i]=0;
					viscol[j]=0;
				}
			return;
		}
	}
}

void workr(int pos,int type) {
	if(solved) return;
	if(pos==0) {
		workc((m+1)/2,m&1);
		return;
	}
	if(type) {
		for(int i=1; i<=n; i++) {
			visrow[i]=1;
			rnum[pos]=i;
			workr(pos-1,0);
			visrow[i]=0;
		}
	} else {
		for(int i=1; i<=n; i++) {
			if(visrow[i]) continue;
			for(int j=i+1; j<=n; j++)
				if(!visrow[j] && row[i][j]) {
					visrow[i]=1;
					visrow[j]=1;
					rnum[pos]=i;
					rnum[n+1-pos]=j;
					workr(pos-1,0);
					visrow[i]=0;
					visrow[j]=0;
				}
			return;
		}
	}
}

int main() {
	freopen("fragment.in","r",stdin);
	freopen("fragment.out","w",stdout);
	int T,num; 
	read(num),read(T);
	while (T--) {
		read(n),read(m);
		for(int i=1; i<=n; i++)
			scanf("%s",mp[i]+1);
		for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) {
			static char x[N], y[N];
			for(int k=1; k<=m; k++) {
				x[k]=mp[i][k];
				y[k]=mp[j][k];
			}
			sort(x+1,x+m+1);
			sort(y+1,y+m+1);
			row[i][j]=1;
			for(int k=1; k<=m; k++)
				if(x[k]!=y[k]) row[i][j]=0;
		}
		for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) {
			static char x[N], y[N];
			for(int k=1; k<=n; k++) {
				x[k]=mp[k][i];
				y[k]=mp[k][j];
			}
			sort(x+1,x+n+1);
			sort(y+1,y+n+1);
			col[i][j]=1;
			for(int k=1; k<=n; k++)
				if(x[k]!=y[k]) col[i][j]=0;
		}
		solved=0;
		workr((n+1)/2,n&1);
		if(!solved) printf("NO\n");
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

3 寻梦（fantasy）

【题目背景】

A nightingale in a golden cage,
That’s me locked inside reality’s maze.
Come someone make my heavy heart light,
Come undone, bring me back to life ?

【题目描述】

N 名旅者背井离乡， 前往他乡寻梦。
初始时， 旅者 i 位于自己的家乡 i 号城市。
每一天， 位于 i 号城市的所有旅者都会前往 Ai 号城市， 其中 Ai 是一个在整
个过程中保持不变的量， 由于旅者迫切的寻梦欲望， 我们规定 Ai≠ i。
现在小 X 想要知道， 是否存在至少一组满足条件的 Ai， 使得在 K 天后， 所有
旅者会同时重新回到家乡（在这过程中旅者们同样可以途径自己的家乡） 。
为了保证数据的强度， 一个测试点中可能包含多组测试数据。

【输入格式】

从文件 fantasy.in 中读取数据。
第一行两个整数 Num、 T， Num 表示测试点编号， 以便选手方便地获得部分
分， 你可能不需要用到这则信息， 样例中 Num 的含义为数据范围与某个测试点
相同； T 表示该测试点中包含的测试数据的组数。
接下来 T 行， 每一行两个整数 N、 K， 描述每一组数据。

【输出格式】

输出 T 行， 每行一个 YES 或 NO， 表示是否存在至少一组满足条件的 Ai。

【样例 1 输入】

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

【样例 1 输出】

YES
NO
YES
1
2
3

【样例 1 解释】

对于第一组测试数据， 可以令 A={2,3,4,5,6,7,1}。
对于第二组测试数据， 可以证明不存在符合条件的 A。
对于第三组测试数据， 可以令 A={3,4,1,5,2}。

【样例 2】

见下发文件 fantasy2.in, fantasy2.ans

【样例 3】

见下发文件 fantasy3.in, fantasy3.ans

【样例 4】

见下发文件 fantasy4.in, fantasy4.ans

【样例 5】

见下发文件 fantasy5.in, fantasy5.ans

【数据范围及子任务】

对于所有测试数据， 保证 $1\le T\le 10^4，1\le N\le 10^{18}，1\le K\le 10^{1}5$。
保证一个测试点中不同的 K 的个数至多为 50。

【解析】

题意即求是否有一组非负整数解$x_i$，$\sum x_i\ast p_i=n$($p_i$为k的所有质因子）
首先对其质因数分解，对质因子个数分类讨论:

• 1个，即判断$p_1$是否整除n即可;
• 2个，扩欧求出一组解，然后调整将其中一个变为最小的非负数，判断乘积是否小于等于n即可;
• 多于2个，显然最小的质因子不超过10⁵，记作$p_0$，同时如果$n=x$可行，则$n=x+k{p}_0$也可行，因此只需要找到 $\forall 0\le T<p_0$，找到最小的$n=a(mod{p}_0)$ 使得n可行.

具体的，可以看作最短路，将$(i,(i+p_j)mod{p}_0)(j>0)$连边，之后求出0到x的最短路即为最小的n，用dij算法即可。

【代码】

该代码要256MB的内存限制

#pragma GCC optimize(3,"Ofast","inline")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int Q=55;
const int LOG=64;
const int N=1e5+5;
const int P=2e6+5;
const int V=3.2e7+5;
const LL INF=4e18;

template <typename T> void read(T &x) {
	x=0;
	int f=1;
	char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-f;
	for(; isdigit(c); c=getchar()) x=x*10+c-'0';
	x*=f;
}

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

template <typename T> void writeln(T x) {
	write(x);
	puts("");
}

int q,tot;
int prime[Q],f[V],cnt[Q];
LL memk[Q];
LL p[Q][LOG],dist[Q][N];

struct info {
	long long dist; 
	int home; 
};

bool operator < (info a, info b) {
	return a.dist > b.dist;
}

void exgcd(LL a,LL b,LL &x,LL &y) {
	if(b==0) {
		x=1;
		y=0;
		return;
	}
	LL q=a/b,r=a%b;
	exgcd(b,r,y,x);
	y-=q*x;
}

int main() {
	freopen("fantasy.in","r",stdin);
	freopen("fantasy.out","w",stdout);
	int num; 
	read(num);
	for (int i=2; i<V; i++) {
		if(f[i]==0) prime[++tot]=f[i]=i;
		for (int j=1; j<=tot && prime[j]<=f[i]; j++) {
			int tmp=prime[j]*i;
			if(tmp>=V) break;
			f[tmp]=prime[j];
		}
	}
	int T; 
	read(T);
	while(T--) {
		LL n, k;
		read(n),read(k);
		int pos=0;
		for(int i=1; i<=q; i++)
			if(memk[i]==k) pos=i;
		if(pos==0) {
			pos=++q;
			memk[q]=k;
			LL tmp=k;
			for(int i=1; 1LL*prime[i]*prime[i]<=tmp; i++)
				if(tmp%prime[i]==0) {
					p[pos][++cnt[pos]]=prime[i];
					while(tmp%prime[i]==0) tmp/=prime[i];
				}
			if(tmp!=1) p[pos][++cnt[pos]]=tmp;
			if(cnt[pos]>=3) {
				for(int i=0; i<p[pos][1]; i++)
					dist[pos][i]=INF;
				static priority_queue <info> Heap;
				dist[pos][0]=0; 
				Heap.push((info){0,0});
				static bool vis[N];
				memset(vis,0,sizeof(vis));
				while(!Heap.empty()) {
					while(!Heap.empty() && vis[Heap.top().home]) Heap.pop();
					if(Heap.empty()) break;
					info tmp=Heap.top(); Heap.pop();
					for(int i=2; i<=cnt[pos]; i++) {
						int dest=(tmp.home+p[pos][i])%p[pos][1];
						if (dist[pos][dest]>tmp.dist+p[pos][i]) {
							dist[pos][dest]=tmp.dist+p[pos][i];
							Heap.push((info){dist[pos][dest],dest});
						}
					}
				}
			}
		}
		bool flg=0;
		for(int i=1; i<=cnt[pos]; i++)
			if(n%p[pos][i]==0) {
				printf("YES\n");
				flg=1;
				break;
			}
		if(flg) continue;
		if(cnt[pos]<=1) {
			printf("NO\n");
			continue;
		}
		if(cnt[pos]==2) {
			LL x=0,y=0;
			exgcd(p[pos][1],p[pos][2],x,y);
			y=(y%p[pos][1]+p[pos][1])%p[pos][1];
			LL tmp=y*(n%p[pos][1])%p[pos][1]*p[pos][2];
			if(tmp<=n) printf("YES\n");
				else printf("NO\n");
			continue;
		}
		int tmp=n%p[pos][1];
		if(dist[pos][tmp]<=n) printf("YES\n");
			else printf("NO\n");
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146