【CCF】全国信息学奥林匹克联赛模拟题+解析+代码

全国信息学奥林匹克联赛模拟题+解析+代码

• 一. 选手须知
• 1 指引（guide）
• 2 碎片（fragment）
• 3 寻梦（fantasy）

一. 选手须知

题目名称	指引	碎片	寻梦
题目类型	传统型	传统型	传统型
可执行文件名	guide	fragment	fantasy
输入文件名	guide.in	fragment.in	fantasy.in
输出文件名	guide.out	fragment.out	fantasy.out
每个测试点时限	0.5 秒	0.5 秒	5.0 秒
内存限制	512MB	512MB	512MB
测试点数目	20	20	14
测试点是否等分	是	是	否

提交的源程序文件名

对于 C++语言	guide.cpp	fragment.cpp	fantasy.cpp
对于 C 语言	guide.c	fragment.c	fantasy.c
对于 Pascal 语言	guide.pas	fragment.pas	fantasy.pas

编译选项

对于 C++语言	-O2 –lm	-O2 –lm	-O2 –lm
对于 C 语言	-O2 –lm -	O2 –lm	-O2 –lm
对于 Pascal 语言	-O2	-O2	-O2

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

【样例 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;
}

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 输出】

YES

【样例 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;
}

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 输出】

YES
NO
YES

【样例 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;
}

本文地址：https://blog.csdn.net/Ljnoit/article/details/108931222