提交答案题选做

发表于 分类于

被提答吊着打，这里是我用来存一些提答题输出代码的。

「十二省联考2019」骗分过样例

表面传统，实质提答。

简要题意

给一堆输入文件和对应的输出文件，再给一些提示，让你猜每个测试点是干什么的。代码长度限制 100 KB100\texttt{ KB}。

题解

咕咕咕。

Code

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#include <cstdio>
#include <iostream>
#include <cmath>
#define il inline
#define ll long long
using namespace std;
const ll mod[4]={0,998244353,1145141,5211600617818708273},phi[4]={0,998244352,1145140,5211600617818708272};
const ll A=55245,B=45699,base=1e6;
const ll pr[3]={0,2,3};

string s;
ll P[base+1];
int mu[base+1],ok[base+1];
ll u[base+1],zyz[base+1];
ll sp[base+1],sze;
int pos[20000001],vis[20000001];

il ll read()
{
    ll res=0,sign=1;
    char c;
	
    while ((c=getchar())<'0'||c>'9') if (c=='-') sign=-1;
	
    res=c-'0';
    while ((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	
    return res*sign;
}

il void print(ll x)
{
    if (x<0) 
	putchar('-'),x=-x;
    if (x>9) print(x/10);
    putchar(x%10+'0');
}

il void ksc(ll &a,const ll b,const ll p)
{
    ll c=(ll)((1.0L*a*b)/(1.0L*p)),res=a*b-c*p;
    res-=p;
    while (res<0) res+=p;
    a=res;
}

il ll ksm(ll a,ll b,ll p)
{
    ll res=1;
    while (b)
    {
	if (b%2==1) ksc(res,a,p);
	ksc(a,a,p),b/=2;
    }
	
    return res;
}

il bool Miller_Rabin(ll x)
{
    if (x==2) return true;
    if (!(x&1LL)||x==1) return false;
    ll i,j,now,next;
    for (i=1; i<=2; i++)
    {
        if (x==pr[i]) return true;
    }

    ll b=x-1,t=0,nn;
    while (!(b&1LL)) b>>=1LL,t++;

    for (i=1; i<=2; i++)
    {
        next=now=nn=ksm(pr[i],b,x);
        for (j=1; j<=t; j++)
        {
            ksc(nn,nn,x),next=nn;
            if (next==1&&now!=x-1&&now!=1) return false;

            now=next;
        }

        if (now!=1) return false;
    }

    return true;
}

il void Div(ll x)
{
    sze=0;
    ll i;
    for (i=2; i*i<=x; i++)
    {
	if (x%i==0)
	{
	    sp[++sze]=i;
	    while (x%i==0) x/=i;
	}
    }
	
    if (x>1) sp[++sze]=x;
}

il bool check_G(ll x,ll p)
{
    int i;
    for (i=1; i<=sze; i++)
    {
	if (ksm(x,(p-1)/sp[i],p)==1) return false;
    }
	
    return true;
}

il void sub_1_5(ll id)
{
    ll n,res;
    char c;
    n=read();
    while (n--)
    {
	res=0;
	while ((c=getchar())<'0'||c>'9');
	    res=c-'0';
	while ((c=getchar())>='0'&&c<='9') res=(res*10+c-'0')%phi[id];
	
	print(ksm(19LL,res,mod[id])),puts("");
    }
}

il void sub_6_7()
{
    ll n,i,x;
    int a[A+B+1];
    a[0]=1;
    for (i=1; i<=A+B; i++) a[i]=a[i-1]*19%mod[1];
	
    n=read();
    while (n--)
    {
	x=read();
	if (x<=A) print((ll)a[x]);
	else print((ll)a[(x-A)%B+A]);
	puts("");
    }
}

il void sub_8_10()
{
    ll n,i,l,r;
    n=read();
    while (n--)
    {
	l=read(),r=read();
	for (i=l; i<=r; i++)
	{
	    if (Miller_Rabin(i)) putchar('p');
	    else putchar('.');
	}
	puts("");
    }
}

il void sub_11_13()
{
    ll n,i,j,l,r,zs=0,len,x,xx;
    ok[1]=mu[1]=1;
    for (i=2; i<=base; i++)
    {
	if (!ok[i])
	    P[++zs]=i,mu[i]=-1;
	for (j=1; j<=zs&&i*P[j]<=base; j++)
	{
	    ok[i*P[j]]=1;
	    if (i%P[j]==0) break;
	    else mu[i*P[j]]=-mu[i];
	}
    }
	
    n=read();
    while (n--)
    {
	l=read(),r=read();
	if (r<=base)
	{
	    for (i=l; i<=r; i++)
	    {
		if (mu[i]<0) putchar('-');
		else if (mu[i]==0) putchar('0');
		else putchar('+');
	    }
	}
	else
	{
	    len=r-l+1;
	    for (i=1; i<=len; i++)
		u[i]=zyz[i]=1;
	    for (i=1; i<=zs; i++)
	    {
		for (j=P[i]*((l-1)/P[i]+1)-l+1; j<=len; j+=P[i])
		{
                    if ((l+j-1)/P[i]%P[i]==0) u[j]=0;
                    else 
			u[j]=-u[j],zyz[j]*=P[i];
                }
	    }
			
	    for (i=1; i<=len; i++)
	    {
                x=(l+i-1)/zyz[i];
                if (u[i]&&x>1)
	        {
                    xx=sqrt(x);
                    if (xx*xx==x) u[i]=0;
                    else if (Miller_Rabin(x)) u[i]=-u[i];
                }
                
                if (u[i]<0) putchar('-');
                else if (u[i]==0) putchar('0');
                else putchar('+');
            }
        }
        puts("");
    }
}

il void sub_14_16()
{
    ll n,T,i,j,k,l,r,m,t;
    char c;
    n=read();
    for (T=1; T<=n; T++)
    {
	l=read(),r=read();
	if (s=="2g?"&&T==n)	
	    cin>>c,m=1515343657;
	else m=read();
	if (m==998244353||m==1515343657)
	{
	    Div(m-1);
	    for (i=l; i<=r; i++)
	    {
		if (check_G(i,m)) putchar('g');
		else putchar('.');
	    }
	}
	else
	{
	    Div(m-1);
	    for (i=1; i<=sze; i++)
	    {
		for (j=1; j<=(m-1)/sp[i]; j++) vis[sp[i]*j]=1;
	    }
	    t=2;
            while (!check_G(t,m)) t++;
            for (i=1,k=t; i<m; k=k*t%m,i++) pos[k]=i;
            
            for (i=l; i<=r; i++)
            {
            	if (vis[pos[i]]) putchar('.');
            	else putchar('g');
	    }
	}
	puts("");
    }
}

signed main()
{
    freopen("software.in","r",stdin),freopen("software.out","w",stdout);

    cin>>s;
    if (s=="1_998244353") sub_1_5(1);
    if (s=="1?") sub_1_5(2);
    if (s=="1?+") sub_1_5(3);
    if (s=="1wa_998244353") sub_6_7();
    if (s=="2p") sub_8_10();
    if (s=="2u") sub_11_13();
    if (s=="2g"||s=="2g?") sub_14_16();
	
    return 0;
}

「eJOI2018」互素树

加强版。

简要题意

给定一个 nn 的点的数，第 ii 条边连接的是 ui,viu_i,v_i 两个点。对于一条边 (u,v)(u,v)，如果有 gcd⁡(u,v)>1\gcd(u,v)>1，则称这条边为坏边。现在你要给树的节点重标号，让坏边的数量变为 00。

T×n≤105T\times n\le 10^5。评分细则与输入文件可以点上面的链接直接去 Loj 上看。

题解

下面的程序原题 11 小时左右可以跑出结果，加强版 1.51.5 小时左右可以跑出结果。

Code

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
#include <bits/stdc++.h>
#define il inline
const int N=2e5+5;

int tt,n,nw,mn,a[N],c[N],d[N],to[N],nx[N],hd[N],sze; std::set<int> s;

namespace IO
{
    const int S=1<<20|500; char iuf[S+5],*s,*t,ouf[S+5],*o; int p[40],P;
    il char gc(){if (t==s){t=(s=iuf)+fread(iuf,1,1<<20,stdin); if (t==s) return EOF;} return *s++;}
    template<class T=int>il T read()
    {
	T x; char c;
	while ((c=gc())<48||c>57); x=c^48;
	while ((c=gc())>47&&c<58) x=(x<<3)+(x<<1)+(c^48);
	return x;
    }
    il void fs(){if (o-ouf) fwrite(ouf,1,o-ouf,stdout); o=ouf;} il void pc(char c){*o++=c; if (o-ouf==S) fs();}
    template<class T=int>il void print(T x){T y; do y=x/10,p[P++]=x-10*y;while (x=y); while (P) pc(p[--P]^48);}
    struct fsr{fsr(){o=ouf;} ~fsr(){fs();}}FF;
}
using IO::read; using IO::print; using IO::pc;

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}

il void dfs(int u,int p)
{
    for (int x:s) if (!p||std::__gcd(d[p],a[x])<2)
    {d[u]=a[x],s.erase(x); break;} int i,v;
    if (!d[u]) nw++,d[u]=a[*s.begin()],s.erase(s.begin());
    for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=p) dfs(v,u);
}

int main()
{
    freopen("X","r",stdin),freopen("X.out","w",stdout);
	
    tt=read(); int i,u,v;
    while (tt--)
    {
	n=read(),memset(hd,0,4*n+4),sze=0;
	for (i=1; i<=n; i++) a[i]=i;
	for (i=1; i<n; i++) u=read(),v=read(),add(u,v),add(v,u);
		
	for (mn=n; mn; )
	{
	    std::random_shuffle(a+1,a+n+1),s.clear();
	    for (i=1; i<=n; i++) s.insert(i); memset(d,0,4*n+4);
	    nw=0,dfs(1,0); if (nw<mn) mn=nw,memcpy(c,d,4*n+4);
	}
	for (i=1; i<=n; i++) print(c[i]),pc(' '); pc('\n');
    }
	
    return 0;
}

「JOISC 2020 Day4」传奇团子师傅

简要题意

有一个 n×mn\times m 的网格图，点分为 P,W,G 三种类型。可以横着竖着斜着共四种方式把网格图中的三个连续格子穿成一个团子，满足从前往后或者从后往前的类型是 P,W,G。每个格子至多属于一个团子，最大化团子的数量。

n,m≤500n,m\le 500。评分细则与输入文件可以点上面的链接直接去 Loj 上看。

题解

我们考虑将每一个可以穿成团子的地方建一个点，而不能同时穿成团子的两个点之间两边，问题就变成了求最大独立集。这个直接随机化。

模拟退火的时候，发现温度非常小的时候反而答案越来越优，所以其实本质上是个爬山，退火是多余的。（只不过本菜逼还是写了退火，因为输出后才发现温度小的时候优秀/kk）

下面这个程序 66 个测试点加起来不到 55 分钟可以出结果。

Code

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
#include <bits/stdc++.h>
#define il inline
#define db double
#define pb push_back
std::mt19937 rnd(time(0));
const int N=505,M=N*N,dx[]={0,-1,-1,-1,0,1,1,1},dy[]={1,1,0,-1,-1,-1,0,1},Z=?; const db T=10,dT=0.9999999;

int n,m,ans,tot,id[N][N][10]; bool o[M]; char mp[N][N]; std::vector<int> g[M];

il void add(int u,int v){if (u&&v) g[u].pb(v),g[v].pb(u);}

il bool ck(int x,int y,char c){return x>=0&&x<n&&y>=0&&y<m&&mp[x][y]==c;}

il void SA()
{
    int i,u,d; db t;
    for (t=T; ans<Z; t*=dT)
    {
	while (o[u=rnd()%tot+1]); d=1;
	for (int v:g[u]) d-=o[v];
	if (d>=0||exp(d/t)*RAND_MAX>rand())
	{
	    ans++,o[u]=1;
	    for (int v:g[u]) if (o[v])
		o[v]=0,ans--;
	}
    }
}

int main()
{
    freopen("input_0X.txt","r",stdin),freopen("output_0X.txt","w",stdout);
	
    scanf("%d%d",&n,&m); int i,j,k,w;
    for (i=0; i<n; i++) scanf("%s",mp[i]);
    for (i=0; i<n; i++) for (j=0; j<m; j++) if (mp[i][j]=='W') for (k=0; k<8; k++)
	if (ck(i+dx[k],j+dy[k],'P')&&ck(i-dx[k],j-dy[k],'G')) id[i][j][k]=++tot;
    for (i=0; i<n; i++) for (j=0; j<m; j++)
    {
	if (mp[i][j]=='W'){for (k=0; k<8; k++) for (w=k+1; w<8; w++) add(id[i][j][k],id[i][j][w]);}
	if (mp[i][j]=='P')
	{
	    for (k=0; k<8; k++) if (ck(i-dx[k],j-dy[k],'W')&&ck(i-2*dx[k],j-2*dy[k],'G'))
		for (w=k+1; w<8; w++) if (ck(i-dx[w],j-dy[w],'W')&&ck(i-2*dx[w],j-2*dy[w],'G'))
		    add(id[i-dx[k]][j-dy[k]][k],id[i-dx[w]][j-dy[w]][w]);
	}
	if (mp[i][j]=='G')
	{
	    for (k=0; k<8; k++) if (ck(i+dx[k],j+dy[k],'W')&&ck(i+2*dx[k],j+2*dy[k],'P'))
		for (w=k+1; w<8; w++) if (ck(i+dx[w],j+dy[w],'W')&&ck(i+2*dx[w],j+2*dy[w],'P'))
		    add(id[i+dx[k]][j+dy[k]][k],id[i+dx[w]][j+dy[w]][w]);
	}
    }
	
    SA();
    for (i=0; i<n; putchar('\n'),i++) for (j=0; j<m; j++)
	if (mp[i][j]=='W')
	{
	    for (w=k=0; !w&&k<8; k++) if (o[id[i][j][k]])
		putchar("-/|\\-/|\\"[k]),w=1;
	    if (!w) putchar('W');
	}
	else putchar(mp[i][j]);
	
    return 0;
}

两个数

比较特殊的题目，故不给链接。

这题表面提答实质传统呢，只不过是提答的话就可以用 python 什么的了，不用高精度了。

简要题意

给定两个正整数 n,φ(n)n,\varphi(n)，求 nn 的质因数分解形式，多组数据。T≤10,n≤22048T\le 10,n\le 2^{2048}。

Subtask #1 (9 points)：保证 n<232n<2^{32}。
Subtask #2 (8 points)：保证 n<1012n<10^{12}。
Subtask #3 (7 points)：保证 n<1018n<10^{18}。
Subtask #4 (6 points)：保证 n<1024n<10^{24}。
Subtask #5 (13 points)：保证 ω(n)=1\omega(n)=1。
Subtask #6 (16 points)：保证 ω(n)=2,mu(n)=1\omega(n)=2,mu(n)=1。
Subtask #7 (16 points)：保证 ω(n)=2\omega(n)=2。
Subtask #6 (25 points)：没有特殊的约束。
其中 ω(n)\omega(n) 表示 nn 的质因数个数。

题解

前四个子任务直接 Pollard-Rho 就可以了。

第五个子任务我们发现其实有：{n=pkφ(n)=pk−pk−1\begin{cases}n=p^k\\\varphi(n)=p^k-p^{k-1}\end{cases}，所以有：p=nn−φ(n)p=\dfrac{n}{n-\varphi(n)}，再把 kk 求出来就好了。

第六个子任务可列方程：{n=abφ(n)=(a−1)(b−1)=ab−a−b+1\begin{cases}n=ab\\\varphi(n)=(a-1)(b-1)=ab-a-b+1\end{cases}，所以：{ab=n−φ(n)+1a+b=n−2φ(n)+2\begin{cases}ab=n-\varphi(n)+1\\a+b=n-2\varphi(n)+2\end{cases}，再用韦达定理解一个二次方程就可以了。

正解和上面的做法都没有什么关系，它可以一份程序包办所有测试点。

「2021 集训队互测」交朋友

第一次用纯调整法做提答。

简要题意

给出一张无向图，找到一个包含尽量少的团的集合使得这些团并起来是这张图。

n≤1000n\le 1000，1≤m≤n(n−1)21\le m\le \frac{n(n-1)}{2}。评分细则与输入文件可以点上面的链接直接去 Loj 上看。

题解

考虑调整法，维护一个团的集合 AA，初始时 AA 为 mm 条边（两个点的团）。不断重复以下调整：

  • 以随机顺序考虑 AA 中的每个团 CC，以随机考虑每个不在 CC 中的点 xx，如果把 xx 加入 CC 中，AA 集合依然合法，则将 xx 加入 CC。
  • 以随机顺序考虑 AA 中的每个团 CC，如果把 CC 从 AA 中删去，AA 集合依然合法，则将 CC 从 AA 中删去。
  • 以随机顺序考虑 AA 中的每个团 CC，以随机考虑每个在 CC 中的点 xx，如果把 xx 从 CC 中删去，AA 集合依然合法，则将 xx 从 CC 中删去。

注意：

  • 「以随机顺序」，如果每次都顺序考虑陷入全局次优解的概率将大大增加。
  • 要用多样的调整方法，有时候限制加入和删除团中点的数量，有时又不限制，并每调整若干次就换一种调整方式。尽可能防止调整方式单一导致陷在全局次优解出不来的情况。

下面的程序 1010 个点加起来跑了 66 小时。（如果巧妙利用四舍五入半个小时就可以满分）

Code

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
#include <bits/stdc++.h>
#define il inline
#define lf double
#define Ve std::vector<int>
#define pb push_back
const int N=1005;

int n,m,M,p[N],a[N][N],id,Z0,T; std::vector<Ve> s; char S[50];

int main()
{
    scanf("%d%d%d",&id,&Z0,&T),
    sprintf(S,"friends%d.in",id),freopen(S,"r",stdin),
    sprintf(S,"friends%d.out",id),freopen(S,"w",stdout);

    scanf("%d%d",&n,&m),std::iota(p+1,p+n+1,1); int i,u,v,C=0,D=0; lf t; Ve y;
    for (i=1; i<=m; i++) scanf("%d%d",&u,&v),y.clear(),y.pb(u),y.pb(v),s.pb(y),a[u][v]=a[v][u]=1;

    for (M=m; m>Z0; M=m)
    {
        if (++C%10==0) fprintf(stderr,"%d %d\n",D,m);
        for (Ve &x:s)
        {
            for (std::shuffle(p+1,p+n+1,std::mt19937(time(0))),i=1; i<=n; i++)
            {
                u=1; for (int v:x) if (v==p[i]||!a[v][p[i]]){u=0; break;}
                if (u){for (int v:x) a[v][p[i]]++,a[p[i]][v]++; x.pb(p[i]); if (D/T%4==0||D/T%4==3) break;}
            }
        }
        std::shuffle(s.begin(),s.end(),std::mt19937(time(0)));
        for (auto I=s.begin(); I!=s.end(); )
        {
            i=1; for (int u:*I){for (int v:*I) if (u!=v&&a[u][v]<2){i=0; break;} if (!i) break;}
            if (i)
            {
                for (int u:*I) for (int v:*I) if (u!=v) a[u][v]--;
                I=s.erase(I),m--;
            }
            else I++;
        }
        for (Ve &x:s)
        {
            std::shuffle(x.begin(),x.end(),std::mt19937(time(0)));
            for (auto I=x.begin(); I!=x.end(); )
            {
                u=1; for (int v:x) if (v!=*I&&a[v][*I]<2){u=0; break;}
                if (u)
                {
                    for (int v:x) if (v!=*I) a[v][*I]--,a[*I][v]--;
                    I=x.erase(I); if (D/T%4==0||D/T%4==2) break;
                }
                else I++;
            }
        }
        if (m<M) D=0; else D++;
    }
    printf("%d\n",m); for (Ve &x:s){printf("%u ",x.size()); for (int v:x) printf("%d ",v); puts("");}

    return 0;
}