Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

P5042 丢失的题面

题解

发布于：Apr 30, 2022

更新于：Aug 15, 2024

次浏览

P5042 丢失的题面

顺序：10 - 1 - 7 - 8 - 9 - 4 - 5 - 6 - 2 - 3

Point 10

读入，特判，输出。

读入的英文意思是让选手输出自己的程序本身，这个题的确存在，但是这题并没有 SPJ ，所以特判一下输出输出文件就好了。

C++ 的atoi函数可以让读入的字符串变成数字以完成其他点的任务。

Point 1

我和其他聚铑做这个点的过程就十分有趣了。

开始，我们使用了大眼观察法观察了一下这个输出，不知道怎么我就看出了将序列每四个字符划分，然后变成若干以0110开头的长度为 4 的 01 串组。发现这些组的大小都在 3 以内，于是我们在 OEIS 上搜了一下这个序列，居然真的找到了：A007413

它的递推方式是三个元素，每次操作 a->abc b->ac c->b 。这道题中这三个字母分别代表 0110 01101001 和 011010011001 。做了一下，发现是对的。

然后观察文件大小发现输出的字符串长度是 \(2^{22}\) 。没细想，写完就过了。

但是为什么是 \(2^{22}\) 呢？

我回头看了一眼，发现输出好像是初始一个 0 字符，每次操作将当前串取反拼接到后面，做 22 次的结果……（鬼知道我当初为啥直接就想每 4 个分组）

然后又看了下 OEIS，发现这个输出本身就是一个数列：A010060。这个序列还有个名字叫做

Thue-Morse Sequence

在wikihow中，叙述了这个序列的几种构造方法，除了上述的两种构造方式之外，还可以直接每次操作 0->01 1->10 来构造。

真有趣

但是代码还是用的第一次写的，懒得改了。（by a___)

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
namespace subtask1{
	int n=22;
    vector<vector<int>>vec,tmp;
    string s[4],ans;
	vector<int>to[4];
    inline void main(){
        int n=20;
        to[1]=vector<int>({1,2,3});
        to[2]=vector<int>({1,3});
        to[3]=vector<int>({2});
        vec.push_back(std::vector<int>({1}));
        while(n--)
        {
            for(auto p:vec)
            for(auto q:p)tmp.push_back(to[q]);
            swap(vec,tmp);tmp.clear();
        }
        s[1]="0110";
        s[2]="01101001";
        s[3]="011010011001";
        for(auto p:vec)ans+=s[p.size()];
        ans.resize(1<<22);
        std::cout<<ans<<std::endl;
    }
}

Point 7

因为 2~6 个点都没有什么思路，直接来看第 7 个点。

观察了一下输入，发现是一个图，而且边没有边权。观察了一下输出，发现输出只有 0 和 INF 两种数字。于是几乎可以确定是判断图上两点间连通性了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace subtask7{
	int fa[100005];
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	inline void onion(int x,int y){
		x=find(x),y=find(y);
		if(x!=y) fa[x]=y;
	}
	inline void main(int n,int m){
		int q=read();
		while(n) fa[n]=n,n--;
		while(m--) onion(read(),read());
		while(q--) puts(find(read())==find(read())?"0":"2139062143");
	}
}

Point 8

切完了上面的点，一看这个点也是个图，而且边有边权。大概扫了一下发现这是个随机生成的树，边权也是随的。询问格式是两个点。

再观察输出，发现输出的答案大多都大于 90000。说明是一个答案期望较大的询问。两点间路径和或者乘积不可能，试验了一下异或发现答案溢出 100000，那么或也顺便排除。

傻了吧唧地想了半天，突然有一位聚铑想到，为啥不是最大值呢？

试了一下果然没错。

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
namespace subtask8{
	const int maxn=1e5+10;
	int fa[maxn][21],mx[maxn][21],Q,n=100000;
	int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1],v[maxn<<1],dep[maxn];
	inline void addedge(int a,int b){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;v[ecnt]=v[ecnt-1]=read();
	}
	void dfs(int x,int f){
		fa[x][0]=f;dep[x]=dep[f]+1;
		for(int i=0;i<18;i++) fa[x][i+1]=fa[fa[x][i]][i],mx[x][i+1]=max(mx[x][i],mx[fa[x][i]][i]);
		for(int i=head[x];i;i=nxt[i]){
			int u=to[i];
			if(u==f)continue;
			mx[u][0]=v[i];
			dfs(u,x);
		}
	}
	inline int solve(int x,int y){
		if(dep[x]<dep[y])swap(x,y);
		int ans=0;
		for(int i=18;~i;i--) if(dep[fa[x][i]]>=dep[y]) ans=max(ans,mx[x][i]),x=fa[x][i];
		if(x==y)return ans;
		for(int i=18;~i;i--) if(fa[x][i]!=fa[y][i]) ans=max(ans,max(mx[x][i],mx[y][i])),x=fa[x][i],y=fa[y][i];
		ans=max(ans,max(mx[x][0],mx[y][0]));
		return ans;
	}
	inline void main(){
		Q=read();
		for(int i=1;i<n;i++) addedge(read(),read());
		dfs(1,0);
		while(Q--) printf("%d\n",solve(read(),read()));
	}
}

Point 9

观察了一下输入，发现是个图。

观察了一下输出，发现有 INF 的存在，那么询问可能是让答案尽量小，所以盲猜最小瓶颈路。试了一下，果然是。

kruskal 的并查集和路径最大值都可以用前面的板子。（出题人真良心）

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
namespace subtask9{
	const int maxn=100005,INF=2139062143;
	int Fa[100005],fa[maxn][21],mx[maxn][21];
	int find(int x){return Fa[x]==x?x:Fa[x]=find(Fa[x]);}
	struct edge{
		int u,v,val;
		inline bool operator < (const edge& zp) const {return val<zp.val;}
	}e[maxn<<1];
	int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1],v[maxn<<1],dep[maxn];
	inline void addedge(int a,int b,int c){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;v[ecnt]=c;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;v[ecnt]=c;
	}
	void dfs(int x,int f){
		fa[x][0]=f;dep[x]=dep[f]+1;
		for(int i=0;i<18;i++) fa[x][i+1]=fa[fa[x][i]][i],mx[x][i+1]=max(mx[x][i],mx[fa[x][i]][i]);
		for(int i=head[x];i;i=nxt[i]){
			int u=to[i];
			if(u==f)continue;
			mx[u][0]=v[i];
			dfs(u,x);
		}
	}
	inline int solve(int x,int y){
		if(dep[x]<dep[y])swap(x,y);
		int ans=0;
		for(int i=18;~i;i--) if(dep[fa[x][i]]>=dep[y]) ans=max(ans,mx[x][i]),x=fa[x][i];
		if(x==y)return ans;
		for(int i=18;~i;i--) if(fa[x][i]!=fa[y][i]) ans=max(ans,max(mx[x][i],mx[y][i])),x=fa[x][i],y=fa[y][i];
		ans=max(ans,max(mx[x][0],mx[y][0]));
		return ans;
	}
	inline void main(){
		read();int Q=read();
		for(int i=1;i<=100000;i++) Fa[i]=i,e[i].u=read(),e[i].v=read(),e[i].val=read();
		sort(e+1,e+100001);
		for(int i=1;i<=100000;i++){
			int u=find(e[i].u),v=find(e[i].v);
			if(u!=v){
				Fa[u]=v;
				addedge(e[i].u,e[i].v,e[i].val);
			}
		}
		for(int i=1;i<=50000;i++) if(!dep[i]) dfs(i,0);
		while(Q--){
			int x=read(),y=read();
			if(find(x)!=find(y))printf("%d\n",INF);
			else printf("%d\n",solve(x,y));
		}
	}
}

Point 4

后面的全做完了，回头看一眼 01 串和 012 串，没啥思路，直接看第四个。

观察了一下输入输出，发现输入输出都是回文

什么玩意是回文的？

第一个字符大概是 n，发现第一项是 1，第二项是 n。于是有个聚铑很自然地想到是组合数，然后发现输出也是对应的 n 的一行组合数，于是就切了。

拆了一下数，发现模数是 104857601，一个 NTT 模数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
namespace subtask4{
	const int maxn=3e5;
	int mul[maxn],inv[maxn],n;
	inline int C(int n,int m){return 1ll*mul[n]*inv[m]%mod*inv[n-m]%mod;}
	inline void pre(){
		mul[0]=inv[0]=1;
		for(int i=1;i<=n;i++) mul[i]=1ll*mul[i-1]*i%mod;
		inv[n]=fpow(mul[n],mod-2);for(int i=n-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	}
	inline void main(){
		n=262144;
		pre();
		printf("%d\n",n);
		for(int i=0;i<=n;i++) printf("%d\n",C(n,i));
	}
}

PS

后来思考了一下为什么输入把 131072 的一行组合数也全给了，根据二项式定理，输入给出的是 \((x+1)^n\)，然后输出的 n 恰好是输入的两倍。所以实际上是让我们算 \((x+1)^{2n}\)。也就是做一遍多项式乘法。

会有人写这玩意吗，还是为了给没看出来是组合数的选手分？

Point 5

刚才切了第四个点的聚铑趁热打铁，瞬间就看出来了是每一项乘上了一个 \((-1)^i\) 。于是又切了。

当然，如果您想写多项式开根也可以。

因为和前面一个点比较像，就放在一起了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
namespace subtask4{
	const int maxn=3e5;
	int mul[maxn],inv[maxn],n;
	inline int C(int n,int m){return 1ll*mul[n]*inv[m]%mod*inv[n-m]%mod;}
	inline void pre(){
		mul[0]=inv[0]=1;
		for(int i=1;i<=n;i++) mul[i]=1ll*mul[i-1]*i%mod;
		inv[n]=fpow(mul[n],mod-2);for(int i=n-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	}
	inline void main2(){
		n=131072;
		pre();
		printf("%d\n",n);
		for(int i=0;i<=n;i++) printf("%d\n",i&1?mod-C(n,i):C(n,i));
	}
}

Point 6

刚才那位聚铑乘胜追击，观察了一下输入输出的项数，发现输出刚好是输入的 \(\frac{1}{3}\) 。

什么东西能减少项数，而且刚好减到 \(\frac{1}{3}\)？

只有聚铑知道答案。他一眼就看出来这似乎是一个多项式三次剩余，然后确实是对的。

然而珂爱似乎有更好的方法，因为这个 \(5e5\) 的数据范围，还是用的多项式快速幂真的太勉强了，加了快读快输开优化才能过。用珂爱的方法或者多项式三次方根或许能更好（更短）地通过此题。

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
namespace subtask6{
	const int maxn=533000<<2,mod=104857601,g=3,gi=104857602/3,n=177147,p=63776689;
	struct NTT{
		int r[maxn],lim;
		inline void getr(int li){
			lim=li;
			for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
		}
		inline void operator () (int *a,int type) const {
			for(int i=0;i<lim;i++) if(i<r[i]) swap(a[i],a[r[i]]);
			for(int mid=1;mid<lim;mid<<=1){
				int rt=fpow(type==1?g:gi,(mod-1)/(mid<<1));
				for(int r=mid<<1,j=0;j<lim;j+=r){
					int p=1;
					for(int k=0;k<mid;k++,p=1ll*p*rt%mod){
						int x=a[j+k],y=1ll*p*a[j+k+mid]%mod;
						a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;
					}
				}
			}
			if(type==-1) for(int p=fpow(lim,mod-2),i=0;i<lim;i++) a[i]=1ll*a[i]*p%mod;
		}
	}ntt;
	void inv(const int *a,int *ans,int n){
		if(n==1) return ans[0]=fpow(a[0],mod-2),ans[1]=0,void();
		static int res[maxn];
		inv(a,ans,n>>1);
		int lim=n<<1;
		ntt.getr(lim);
		for(int i=0;i<n;i++) res[i]=a[i];
		for(int i=n;i<lim;i++) res[i]=ans[i]=0;
		ntt(res,1),ntt(ans,1);
		for(int i=0;i<lim;i++) ans[i]=ans[i]*(2-1ll*ans[i]*res[i]%mod+mod)%mod;
		ntt(ans,-1);
		for(int i=n;i<lim;i++) ans[i]=0;
	}
	inline void deri(const int *a,int *ans,int n){for(int i=1;i<n;i++) ans[i-1]=1ll*a[i]*i%mod;ans[n-1]=0;}
	inline void inte(const int *a,int *ans,int n){for(int i=1;i<n;i++) ans[i]=1ll*a[i-1]*fpow(i,mod-2)%mod;ans[0]=0;}
	inline void ln(const int *a,int *ans,int n){
		static int res[maxn];
		deri(a,res,n);
		inv(a,ans,n);
		int lim=n<<1;
		ntt.getr(lim);
		ntt(res,1),ntt(ans,1);
		for(int i=0;i<lim;i++) res[i]=1ll*res[i]*ans[i]%mod,ans[i]=0;
		ntt(res,-1);
		inte(res,ans,n);
		for(int i=0;i<lim;i++) res[i]=0;
	}
	void exp(const int *a,int *ans,int n){
		if(n==1) return ans[0]=1,ans[1]=0,void();
		static int res[maxn];
		exp(a,ans,n>>1);
		ln(ans,res,n);
		int lim=n<<1;
		ntt.getr(lim);
		res[0]=(1+a[0]-res[0]+mod)%mod;
		for(int i=1;i<n;i++) res[i]=(a[i]-res[i]+mod)%mod;
		ntt(ans,1),ntt(res,1);
		for(int i=0;i<lim;i++) ans[i]=1ll*ans[i]*res[i]%mod,res[i]=0;
		ntt(ans,-1);
		for(int i=n;i<lim;i++) ans[i]=0;
	}
	inline void fpow(int const *a,int *ans,int k,int n){
		static int f[maxn],g[maxn];
		for(int i=0;i<n;i++)g[i]=f[i]=ans[i]=0;
		int d=0;
		while(!a[d]&&d<n) ++d;
		int u=::fpow(a[d],mod-2),v=22131490;
		for(int i=0;i<n-d;i++)g[i]=1ll*a[i+d]*u%mod;
		for(int i=n-d;i<n;i++)g[i]=0;
		ln(g,f,n);
		for(int i=0;i<n;i++)f[i]=1ll*f[i]*k%mod;
		exp(f,ans,n);
		d*=k;
		for(int i=n-1;i>=d;i--)ans[i]=1ll*ans[i-d]*v%mod;
		for(int i=0;i<d;i++)ans[i]=0;
	}
	int a[maxn],ans[maxn];
	inline void main(){
		for(int i=0;i<=n;i++) a[i]=read();
		fpow(a,ans,::fpow(3,mod-2),1<<18);
		out(n);
		for(int i=0;i<=n;i++) out(ans[i]);
	}
}

Point 2

终于要直面 01 串了。（由第一个点就可以知道我 01 串相关有多菜）

首先，一位聚铑通过观察文件大小发现字符个数恰好是斐波那契数列的第 33 项。

发现除了前三项，后面几项都符合斐波那契串。而一个斐波那契串内确实有这样的规律。

写了一下，发现是对的。

顺便模一下这位聚铑写得真可爱。

1
2
3
4
5
6
7
namespace subtask2{
	string s[2]={"0","1"};
	inline void main(){
		for(int i=2;i<33;i++) s[i&1]=s[i&1]+s[i&1^1];
		puts(s[0].c_str());
	}
}

Point 3

这个点是最艰难的点了。

使劲找规律，先发现字符个数是 \(3^{12}+11\) ，然后思考有什么规律。

除去第一个 0，每 12 个数分开，看起来好像是三进制数每次 +1 再 +2 。

往后看了看，什么玩意

经过艰苦的奋斗，最终还是没找出来，于是去膜拜的珂爱的题解。感觉就是个找规律。因为是抄别人的，所以写出来也没啥意思。贴一下别人的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
namespace subtask3{
	using namespace std;
	void main()
	{
		unordered_set<string>st;
		string s="000000000001",output="";
		while(1）{
			output+=s[0];
			st.insert(s);
			s+=s[0];
			s.erase(0,1);
			while(st.count(s)&&s!="000000000000"){
				++s[11];
				for(int i=11;~i&&s[i]=='3';--i){
					s[i]='0';
					if(i)++s[i-1];
				}
			}
			if(s=="000000000000")break;
		}
		cout<<0<<output<<"00000000000\n";
	}
}

代码

都在上面了。贴一下我的主函数（包括第十个点的特判）和用到的全局函数和变量。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<unordered_set>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
const int mod=104857601;
char O_[999999],*OU=O_,*OV=OU+999991,OS[21],*OT=OS;
#define F fwrite(O_,1,OU-O_,stdout)
#define O(x) (*(OU=(OU==OV?(F,O_):OU))++=(x))
void out(int x){for(;*OT++=x%10+48,x/=10;);for(;OT!=OS;O(*--OT));O(10);}
inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;return ans;}
int n;
//------------------------------------------------------------
signed main(){
	char s[10];
	scanf("%s",s);
	if(strcmp(s,"Maybe")==0) return puts("Your program should output itself here.\nSounds very difficult, yeah?\nAnyway, good luck!"),0;
	n=atoi(s);
	if(n==22)subtask1::main();
	if(n==33)subtask2::main();
	if(n==12)subtask3::main();
	if(n==531441)subtask6::main();
	if(n==131072)subtask4::main();
	if(n==262144)subtask4::main2();
	if(n==100000){
		int m=read();
		if(m==100000) subtask7::main(n,m);
		else subtask8::main();
	}else if(n==50000) subtask9::main();
	return F,0;
}

更新于：Aug 15, 2024

博客园

OI

模拟

给小狼留言