“信心赛”

T1

给定 a,b 的个数 $n,m$ 问一个为 $\leq n+m$ 的串中满足任意区间中 $a,b$ 的差值小于等于 $k$ 的个数

不妨考虑成后缀中最多有 $x$ 个 $a$ , $y$ 个 $b$ 的方案数,设我们用了$A$ 个 $a$ , $B$ 个 $b$

则有转移

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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

inline void qread(int &x)
{
x=0; int f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}

inline void qread(long long &x)
{
x=0; long long f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}
}

const int modp=1e9+7;
const int maxn=155;

int n,m,_f[maxn][maxn][22][22],k;

int f(int a,int b,int x,int y)
{
if(a==n&&b==m) return 1;
//这里x y的意义与上面相反
if(~_f[a][b][x][y]) return _f[a][b][x][y];
int ans=0;
if(a<n&&x<k) ans=(ans+f(a+1,b,x+1,max(0,y-1)))%modp;
if(b<m&&y<k) ans=(ans+f(a,b+1,max(0,x-1),y+1))%modp;
return _f[a][b][x][y]=ans;
}

int main()
{
int i,j;
mstd::qread(n);
mstd::qread(m);
mstd::qread(k);
memset(_f,-1,sizeof(_f));
printf("%d",f(0,0,0,0));
return 0;
}


T2

$k\leq10$ 因此考虑 $k$ 相关的

记 $f[i][j][k][l][m][n]$ 表示从 $j$ 位置开始接第 $i$ 个人上车后车内人的目的地为 $k,l,m,n$ 的最小值,复杂度为 $O(\text{过不去})$

发现此时一定会有人下车,因此第四维无意义,枚举哪个人下车后记忆化就可以了

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

inline void qread(int &x)
{
x=0; int f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}

inline void qread(long long &x)
{
x=0; long long f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}
}

const int maxn=2020;

int _f[maxn][11][11][11][11];
int n,m,st[maxn],ed[maxn],mans;

int kick(int nowpla,int target)
{
return abs(nowpla-target)+1;
}

int dfs(int dep,int nowpla,int zsx1,int zsx2,int zsx3)
{
if(_f[dep][nowpla][zsx1][zsx2][zsx3]) return _f[dep][nowpla][zsx1][zsx2][zsx3];
int ans=0x3f3f3f3f;
if(zsx1) ans=min(ans,dfs(dep,zsx1,0,zsx2,zsx3)+kick(zsx1,nowpla));
if(zsx2) ans=min(ans,dfs(dep,zsx2,zsx1,0,zsx3)+kick(zsx2,nowpla));
if(zsx3) ans=min(ans,dfs(dep,zsx3,zsx1,zsx2,0)+kick(zsx3,nowpla));
if(dep>n&&!((!zsx1)&&(!zsx2)&&(!zsx3)))
return _f[dep][nowpla][zsx1][zsx2][zsx3]=ans;
if(dep>n) return 0;
if(zsx1&&zsx2&&zsx3)
{
ans=min(ans,dfs(dep+1,ed[dep],zsx1,zsx2,zsx3)+kick(nowpla,st[dep])+kick(st[dep],ed[dep]));
ans=min(ans,dfs(dep+1,zsx1,ed[dep],zsx2,zsx3)+kick(nowpla,st[dep])+kick(zsx1,st[dep]));
ans=min(ans,dfs(dep+1,zsx2,zsx1,ed[dep],zsx3)+kick(nowpla,st[dep])+kick(zsx2,st[dep]));
ans=min(ans,dfs(dep+1,zsx3,zsx1,zsx2,ed[dep])+kick(nowpla,st[dep])+kick(zsx3,st[dep]));
}
else
{
if(!zsx1) ans=min(ans,dfs(dep+1,st[dep],ed[dep],zsx2,zsx3)+kick(nowpla,st[dep]));
if(!zsx2) ans=min(ans,dfs(dep+1,st[dep],zsx1,ed[dep],zsx3)+kick(nowpla,st[dep]));
if(!zsx3) ans=min(ans,dfs(dep+1,st[dep],zsx1,zsx2,ed[dep])+kick(nowpla,st[dep]));
}
_f[dep][nowpla][zsx1][zsx2][zsx3]=ans;
return ans;
}

int main()
{
int i,j;
mstd::qread(n);
mstd::qread(m);
for(i=1;i<=n;i++) mstd::qread(st[i]),mstd::qread(ed[i]);
printf("%d",dfs(1,1,0,0,0));
return 0;
}

T3

折半查找,之前讲过的题

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

inline void qread(int &x)
{
x=0; int f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}

inline void qread(long long &x)
{
x=0; long long f=1;
static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
x*=f;
}
}

const int maxn=500500;

int al[maxn],ar[maxn],a[maxn],n,m,n1,n2;
int tot1,tot2,ans;

int check(int bas,int cas)
{
int ans=0;
for(int j=1;(1<<(j-1))<=cas;j++)
{
if(cas&(1<<(j-1)))
ans=(ans+a[j+bas])>=m?(ans+a[j+bas]-m):(ans+a[j+bas]);
}
return ans;
}

int losbond(int *a,int x,int n)
{
int l=1,r=n;
int mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid]<=x) ans=a[mid],l=mid+1;
else r=mid-1;
}
return ans;
}

int main()
{
int i,j;
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
mstd::qread(n);
mstd::qread(m);
for(i=1;i<=n;i++) mstd::qread(a[i]),a[i]%=m;
n1=n/2,n2=n-n1;
for(i=1;i<=(1<<n1)-1;i++)
{
al[++tot1]=check(0,i);
}
for(i=1;i<=(1<<n2)-1;i++)
{
ar[++tot2]=check(n1,i);
}
al[++tot1]=0;
ar[++tot2]=0;
sort(al+1,al+tot1+1);
sort(ar+1,ar+tot2+1);
for(i=1;i<=tot1;i++)
{
ans=max(ans,al[i]+losbond(ar,m-al[i]-1,tot2));
}
printf("%d",ans);
return 0;
}


T4

还在调试

总结

T1这种题降智了没做出来,T2暴力也没打对,T4题意理解不是很清楚,因此要刷刷 CF div2 的 CD