A

构造一个长度为a的数可以被b整除 1<=b<=10
b<10 时 a个b 即可
b=10 时候 1+(a-1)个0 即可
注意a=1 b=10时不存在

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
//freopen("test.txt","r",stdin);
int a,b;
scanf("%d%d",&a,&b);
if(a == 1 && b==10)
{
puts("-1");
return 0;
}
if(b == 10)
{
printf("%d",1);
for(int i=1;i<a;++i) printf("%d",0);
}
else
for(int i=0;i<a;++i) printf("%d",b);
puts("");
return 0;
}

B

3n个点围城一圈,每个点的权值为1 or 2 or 3
问存在 $a_i + a_{i+n} + a_{i+2n} \neq 6 (0 \geq i < n)$ 的情况
我们知道所有情况有$3^{3n}$种,而不存在上述情况的有 $7^n$ 种(1+2+3,1+3+2,2+1+3,2+3+1,3+1+2,3+2+1,2+2+2)
答案即 $3^{3n} - 7^n$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL mod = 1e9 + 7;

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
LL res = 1,dec = 1;
for(int i=0;i<n;++i) res = res*27 %mod;
for(int i=0;i<n;++i) dec = dec*7 %mod;
printf("%d\n",(int)(((res - dec)%mod + mod)%mod));
return 0;
}

C

定义$f(a,b)$ 为字符串a,b有几个位置的字符不同
给出s1,s2题目要求找到一个串s3使得
$f(s_1,s_2) = f(s_2,s_3) = t$
若不存在输出 -1

我们转化为构造相同的个数即n-t
我们首先考虑s1[i] != s2[i] 的情况,设有cnt个,我们各构造一半与s1[i] 和 s2[i] 相同最多可以有cnt/2个相同
再考虑s1[i] == s2[i] 的情况,有n - cnt个,我们最多可以构造n-cnt个与相同

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e5 + 10;
char s1[maxn],s2[maxn];

void print(char c1,char c2)
{
for(int i=0;i<26;++i)
{
if('a'+i != c1 && 'a'+i != c2)
{
putchar('a'+i);
return;
}
}
}

int main()
{
//freopen("test.txt","r",stdin);
int n,t;
scanf("%d %d",&n,&t);
scanf("%s %s",s1,s2);
int cnt = 0;
for(int i=0;i<n;++i)
if(s1[i]!=s2[i]) ++cnt;
t = n-t;
if((cnt/2+(n-cnt)) < t) puts("-1");
else
{
int rem = cnt/2;
rem = min(rem,t);
t -= rem;
rem*=2;
for(int i=0;i<n;++i)
{
if((s1[i] != s2[i]) && rem)
{
if(rem&1) putchar(s1[i]);
else putchar(s2[i]);
--rem;
continue;
}
if((s1[i] == s2[i]) && t)
{
putchar(s1[i]);
--t;
continue;
}
print(s1[i],s2[i]);
}
puts("");
}
return 0;
}

D

给定一个奇数,把它拆成1-3个素数,输出一种方案

哥德巴赫猜想: 任一大于2的偶数,都可表示成两个素数之和
n>5时,我们找到一个偶数 n - 3,然后将它暴力拆成两个素数

我的做法
勒穆瓦纳猜想(李维猜想): 任一大于5的奇数,都可表示成一个质数及偶半质数之和
其中偶半素数即 一个素数*2
我枚举一个素数,然后再判断另一个偶半素数
其中判断较大时用Miller_Rabin,较小时暴力(直接Miller_Rabin不知为何会误判…)。

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
#include<bits/stdc++.h>
using namespace std;

typedef unsigned int UI;
typedef long long LL;

const int maxn = 1e6 + 2;

UI vis[(maxn+31)/32 + 5];
int pri[100000];
int n,tot;

void init()
{
int n = maxn;
tot = 0;
memset(vis,0,sizeof vis);
for(int i=2;i<n;++i)
{
if(!(vis[i/32]&(1<<(i%32)))) pri[tot++] = i;
for(int j=0;j<tot;++j)
{
LL t = (LL)i*pri[j];
if(t > n) break;
vis[t/32] |= (1<<(t%32));
if(i % pri[j] == 0) break;
}
}
// printf("%d\n",tot);
}

bool witness(LL a,LL n)
{
LL t,d,x;
d=1;
int i=ceil(log(n-1.0)/log(2.0)) - 1;
for(;i>=0;i--)
{
x=d; d=(d*d)%n;
if(d==1 && x!=1 && x!=n-1) return true;
if( ((n-1) & (1<<i)) > 0)
d=(d*a)%n;
}
return d==1? false : true;
}

bool miller_rabin(LL n)
{
if(n==2) return true;
if(n==1 || ((n&1)==0)) return false;
for(int i=0;i<50;i++){
LL a=rand()*(n-2)/RAND_MAX +1;
if(witness(a, n)) return false;
}
return true;
}

bool judge(int n)
{
for(int i=2;i*i<=n;++i)
if(n%i==0) return false;
return true;
}

int main()
{
init();
while(scanf("%d",&n)==1)
{
if(n==3) puts("1\n3");
else if(n==5) puts("1\n5");
else
{
puts("3");
for(int i=1;i<tot;++i)
{
int t = (n - pri[i])/2;
if(t>maxn)
{
if(miller_rabin(t))
{
printf("%d %d %d\n",pri[i],t,t);
break;
}
}
else
{
if(judge(t))
{
printf("%d %d %d\n",pri[i],t,t);
break;
}
}
}
}
}
return 0;
}

E

给定两个排列,交换位置i,j元素的开销为abs(i-j),求从一个排列移到另一个排列的最小开销,输出移动步骤
贪心
我们发现,把一个数从p移到正确的位置q上(不考虑与p之前q之后的元素交换),开销总是abs(p-q)
我们将一个数从p移到q移动过程中,可以将更接近其原来位置的数换过来,而且这样不会增加开销
预处理直接处理成 p[p中第i个位置的数] = 在s中的位置 ,这样等价于将排列移为 1-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
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 2010;
int p[maxn],s[maxn];
int id[maxn];
vector<pair<int,int> > out;

int dfs(int a[],int n)
{
if(n == 1) return 0;
int pos,res = 0;
for(int i=1;i<=n;++i)
if(a[i] == n)
{
pos = i;
break;
}
res += n - pos;
for(int i=pos+1;i<=n;++i)
{
if(a[i] <= pos)
{
out.push_back(make_pair(pos,i));
swap(a[pos],a[i]);
pos = i;
}
}
return res+dfs(a,n-1);
}

int main()
{
//freopen("test.txt","r",stdin);

int n;
scanf("%d",&n);

for(int i=1;i<=n;++i) scanf("%d",p+i);
for(int i=1;i<=n;++i) scanf("%d",s+i),id[s[i]]=i;
for(int i=1;i<=n;++i) p[i] = id[p[i]];

//for(int i=1;i<=n;++i) printf("%d ",p[i]);


printf("%d\n",dfs(p,n));
printf("%d\n",out.size());
for(int i=0;i<out.size();++i) printf("%d %d\n",out[i].first,out[i].second);
return 0;
}