A

给定字符串 00 01 10 11 的个数,构造一个字符串满足他们的个数关系,(很显然长度是他们的个数和+1

DP
用 d[00][01][11][10] 预处理出选择情况,记录的是每个时刻该选的是哪个串,然后打印的时候倒推回去

(其实题解做法很简单。。只需要判断一下不可构造情况然后构造一下(先构造01和10然后11和00添在两边)就行了。。而我蠢蠢地写了dp

复杂度$O(20^4 + tn)$

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

#define rep(i,n) for(int i=0;i<=n;++i)

char s[4][3] = {"00","01","10","11"};
const int maxn = 21;

int d[maxn][maxn][maxn][maxn][2];

void init()
{
d[1][0][0][0][0] = 1;
d[0][1][0][0][1] = 2;
d[0][0][1][0][0] = 3;
d[0][0][0][1][1] = 4;
rep(i,20)
{
rep(j,20)
{
rep(k,20)
{
rep(l,20)
{
if(i && d[i-1][j][k][l][0]) d[i][j][k][l][0] = 1;
if(j && d[i][j-1][k][l][0]) d[i][j][k][l][1] = 2;
if(k && d[i][j][k-1][l][1]) d[i][j][k][l][0] = 3;
if(l && d[i][j][k][l-1][1]) d[i][j][k][l][1] = 4;
}
}
}
}
}


int main()
{
//freopen("test.txt","r",stdin);
init();
int T;
scanf("%d",&T);
while(T--)
{
int a[4];
for(int i=0;i<4;++i) scanf("%d",a+i);
vector<int> ans;
if(d[a[0]][a[1]][a[2]][a[3]][0] || d[a[0]][a[1]][a[2]][a[3]][1])
{
int t;
if(d[a[0]][a[1]][a[2]][a[3]][0]) t = 0;
else t = 1;
while(d[a[0]][a[1]][a[2]][a[3]][t])
{
int p = d[a[0]][a[1]][a[2]][a[3]][t]-1;
ans.push_back(p);
--a[p];
t = p>1?1:0;
}
printf("%s",s[ans[ans.size()-1]]);
for(int i=ans.size()-2;i>=0;--i)
{
putchar(s[ans[i]][1]);
}
puts("");
}
else puts("impossible");
}
return 0;
}

B

一列火车,有n节不同长度的车厢,一些亮灯,一些不亮,现在要通过一个长为h的隧道,
要使得在每个时刻,所有有一部分在隧道里的车厢中至少有一个亮灯。
问如何点亮最少的等使满足条件

贪心
我们模拟这个过程就行了。。首先第一节和最后一节肯定要开灯。。
然后每次从开灯了的车后面开始,如果若干节没有开灯的车厢的长度刚好大于等于h,则他们当中的最后一列需要开灯。。
因为这样对后面的决策也是更有利的。

复杂度 $O(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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
typedef long long LL;
int n,h;
int a[maxn],on[maxn];

int main()
{
freopen("02","r",stdin);
freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&h);
for(int i=0;i<n;++i) scanf("%d",a+i);
int r,res = 0,len = 0;
for(int i=0;i<n;++i) scanf("%d",on+i);
if(!on[0]) ++res,on[0] = 1;
if(!on[n-1]) ++res,on[n-1] = 1;
for(r=0;r<n;++r)
{
if(on[r])
{
len = 0;
continue;
}
len += a[r];
if(len >= h && !on[r]) ++res,len = 0;
}
printf("%d\n",res);
}
return 0;
}

C

将一组自然数分为两组,要求使得他们两组当中最小的gcd最大

暴力
枚举其中一个数的因子,把所有可以被其因子整除的数作为第一组,剩下的作为第二组。
第一组gcd就是因子,第二组gcd计算一下就行了。

我要吐槽测评姬。。和标程一样的写法竟然T掉了

复杂度 $O(1344n)$

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>
using namespace std;

const int maxn = 5e4 + 10;
const int INF = 0x3f3f3f3f;
int a[maxn];

int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}

int main()
{
freopen("10","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int t = INF,res = 1;
for(int i=0;i<n;++i) scanf("%d",a+i),t = min(t,a[i]);
for(int i=1;i*i<=t;++i)
{
if(t%i == 0)
{
int cur=INF,fi=1;
for(int j=1;j<n;++j)
if(a[j]%i)
{
if(fi)
{
cur = a[j];
fi = 0;
}
else
{
cur = gcd(cur,a[j]);
}
}
res = max(res,min(i,cur));
if(t/i == i) continue;
int k = t/i;
cur=INF;
fi = 1;
for(int j=1;j<n;++j)
if(a[j]%k)
{
if(fi)
{
cur = a[j];
fi = 0;
}
else
{
cur = gcd(cur,a[j]);
}
}
res = max(res,min(k,cur));
}
}
printf("%d\n",res);
}
return 0;
}