前言

这场比赛是真的离谱，做了一道题目就可以上分了。

比赛链接

只会三道题目，第二道题目会个思路，不会卡常。

我这个分Div1比Div2还好上分

A

一个合格的子矩阵要求除了四个角以外，四条边是 1 ，中间为 0 ，且子矩阵长宽至少是多少（题目给出限制），然后问题目给出矩阵的哪个子矩阵只需要最少的操作次数便能合格，并输出操作次数。

考虑枚举子矩阵的最低行和最高行以及最高列，然后最低列在枚举的时候直接在前面取最小值即可，具体看代码。

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
#include<cstdio>
#include<cstring>
#define N 410
using namespace std;
int a[N][N],n,m;
char st[N][N];
inline int fuck(int l,int r,int lie){return a[r][lie]-a[l-1][lie];}
inline int pd(int x,int y){return st[x][y]=='0';}
inline int mymin(int x,int y){return x<y?x:y;}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)scanf("%s",st[i]+1);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)a[i][j]=a[i-1][j]+(st[i][j]=='1');
		}
		int ans=999999999;
		for(int l=n-4;l>=1;l--)
		{
			for(int r=l+4;r<=n;r++)
			{
				int now=0,minsum=(r-l-1)-fuck(l+1,r-1,1);
				for(int i=2;i<=3;i++)now+=fuck(l+1,r-1,i)+pd(l,i)+pd(r,i);
				for(int i=4;i<=m;i++)
				{
					ans=mymin(ans,now+minsum+(r-l-1)-fuck(l+1,r-1,i));
					int x=fuck(l+1,r-1,i-2)+pd(l,i-2)+pd(r,i-2);
					now-=x;now+=fuck(l+1,r-1,i)+pd(l,i)+pd(r,i);
					minsum=mymin(minsum+x,(r-l-1)-fuck(l+1,r-1,i-2));
					
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)a[i][j]=0;
		}
		printf("%d\n",ans);
	}
	return 0;
}

B

如果一个排列中包含下标为 $i$ 的子区间的有 $m$ 个不同的最大值，则称 $i$ 为 $m$ 好数。

现在要统计有多少个排列恰好含有 $k$ 个 $m$ 好数。

感觉思路很像鹰蛋，不知道是不是我的错觉。

$f[i][j][k]$ 表示长度为 $i$ ，刚好有 $k$ 个 $j$ 好数的排列数量。

考虑排列最大值在哪个位置，然后左边右边的 $k$ 好数同时变成 $k+1$ 好数。

时间复杂度：$O(n^2mk^2)$ （官方复杂度也是这个）

想不到竟然是这么离谱的时间复杂度吧

当然，因为我是 for 循环 DP ，所以比较容易 DP 出很多无用状态，而且我常数不够优秀，T 了，100 100 100 本机跑了个 15.74s，懒得优化了。

官方给出的代码是类似记忆化搜索的DP。

RNM卡常题

我的代码（TLE12）：

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<cstdio>
#include<cstring>
#define N 110
using namespace std;
typedef long long LL;
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
LL n,m,K,mod;
LL dp[N][N][N],C[N][N],fc[N];
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&K,&mod);
	dp[0][0][0]=dp[1][0][0]=1;dp[1][1][1]=dp[0][1][0]=1;for(int j=2;j<=m;j++)dp[1][j][0]=dp[0][j][0]=1;
	C[0][0]=1;fc[0]=1;
	for(int i=1;i<=n;i++)
	{
		C[i][0]=1;fc[i]=fc[i-1]*i%mod;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	for(int i=2;i<=n;i++)
	{
		dp[i][0][0]=dp[i][1][1]=fc[i];
		for(int k=2;k<=m;k++)
		{
			for(int j=1;j<=i;j++)
			{
				for(int l=mymin(j-1,K);l>=0;l--)
				{
					for(int r=mymin(i-j,K-l);r>=0;r--)(dp[i][k][l+r]+=dp[j-1][k-1][l]*dp[i-j][k-1][r]%mod*C[i-1][j-1])%=mod;
				}
			}
		}
	}
	printf("%lld\n",dp[n][m][K]);
	return 0;
}

官方代码：

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

using namespace std;

const int MAX_N = 100 + 5;

int n, m, k, P;
int fac[MAX_N], c[MAX_N][MAX_N], f[MAX_N][MAX_N][MAX_N];

int add(int a, int b) {
    return a + b < P ? a + b : a + b - P;
}

void dp(int sz, int cnt, int dep) {
    if (f[dep][sz][cnt] != -1) return ;
    register int &F = f[dep][sz][cnt] = 0;
    if (!sz) {
        F = 1;
        return ;
    }
    if ((m - dep < 7 && (1 << (m - dep)) < cnt) || (cnt && sz < m - dep)) return ;
    if (dep == m) {
        F = (cnt == 1 ? fac[sz] : 0);
        return ;
    }
    for (int i = 0; i < sz; i ++) {
        register int fi = 0;
        register int *fl = f[dep + 1][i], *fr = f[dep + 1][sz - i - 1];
        for (int j = max(0, cnt + i + 1 - sz); j <= min(cnt, i); j ++)
            if (fl[j] && fr[cnt - j]) {
                dp(i, j, dep + 1);
                dp(sz - i - 1, cnt - j, dep + 1);
                fi = (fi + 1ll * fl[j] * fr[cnt - j]) % P;
            }
        F = (F + 1ll * fi * c[sz - 1][i]) % P;
    }
}

int main() {
    cin >> n >> m >> k >> P; m --;
    for (int i = c[0][0] = fac[0] = 1; i <= n; i ++) {
        c[i][0] = c[i][i] = 1;
        fac[i] = 1ll * fac[i - 1] * i % P;
        for (int j = 1; j < i; j ++) c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);
    }
    memset(f, -1, sizeof(f));
    dp(n, k, 0);
    cout << f[0][n][k] << endl;
    return 0;
}

C

每辆车运作 $xi$ 的时间，维修 $yi$ 的时间如此往复，有 $n$ 种车，一开始没有车，每次操作会加入车（原本没有这种车），或者删除车（有这种车），然后问每次操作后有多少个车在维修。

应该是在操作后吧，因为我赛后五天才写的总结，所以忘题了

考虑根号分治。

先把答案差分一下。

然后题目可以拆成从 $x$ 修改，每隔 $y$ 个修改一次，最多改 $k$ 次。

具体就是每次在维修开始时 +1 ，在运作开始时 -1 ，然后最后前缀和即可。

而这个可以修改又可以拆成两个修改，一个 $+1$ ，一个 $-1$ ，把最多改 $k$ 次这个限制取消，改成只要 $y$ 不超过 $m$ 即可。

然后考虑如果 $y≥\sqrt{m}$ 时，暴力修改，$y<\sqrt{m}$ 时，则存下此次修改，在最后遍历 $\sqrt{m}$ 遍数组暴力修改。

时间复杂度：$O(n\sqrt{m})$

空间复杂度：$O(n+m)$

然后有些细节字节想想吧。

这道题目难倒是不难，但是我一开始以为过不了，而且我 B 题还没做出来，于是最后四十分钟才开始码这道题，然后没调出来光荣GG。码力是真的差

但是还好能上分。

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
#include<cstdio>
#include<cstring>
#include<cmath>
#define SN 510
#define N 210000
#define NN 410000
using namespace std;
struct node
{
	int id,k,next;
}a[NN];int len,last[SN];
inline void ins(int x,int id,int k){len++;a[len].id=id;a[len].k=k;a[len].next=last[x];last[x]=len;}
struct car
{
	int x,y;
}c[N];
int sum[N],n,sn,m;
inline void change1(int id,int y,int k){while(id<=m)sum[id]+=k,id+=y;}
inline void change2(int id,int y,int k)
{
	if(id>m)return ;
	if(y>sn)change1(id,y,k);
	else ins(y,id,k);
}
inline void change3(int id,int y,int k,int limit)//左闭右开 
{
	if(limit<=id || id>m)return ;
	limit=((limit-id-1)/y+1)*y+id;
	change2(id,y,k);change2(limit,y,-k);
}
int NM[N];
void solve(int id)
{
	if(!last[id])return ;
	for(int k=last[id];k;k=a[k].next)NM[a[k].id]+=a[k].k;
	for(int i=1;i<=m;i++)
	{
		sum[i]+=NM[i];
		if(i+id<=m)NM[i+id]+=NM[i];
		NM[i]=0;
	}
}
int pre[N];
int main()
{
	scanf("%d%d",&n,&m);sn=sqrt(m);
	for(int i=1;i<=n;i++)scanf("%d%d",&c[i].x,&c[i].y);
	for(int i=1;i<=m;i++)
	{
		int op,k;scanf("%d%d",&op,&k);
		if(op==1)pre[k]=i;
		else
		{
			change3(pre[k]+c[k].x,c[k].x+c[k].y,1,i);
			change3(pre[k]+c[k].x+c[k].y,c[k].x+c[k].y,-1,i);
			int fuck=(i-pre[k])%(c[k].x+c[k].y)+1;
			if(fuck>c[k].x+1 || fuck==1)sum[i]--;
			pre[k]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(pre[i])
		{
			change3(pre[i]+c[i].x,c[i].x+c[i].y,1,m+1);
			change3(pre[i]+c[i].x+c[i].y,c[i].x+c[i].y,-1,m+1);
		}
	}
	for(int i=1;i<=sn;i++)solve(i);
	for(int i=1;i<=m;i++)
	{
		sum[i]+=sum[i-1];
		printf("%d\n",sum[i]);
	}
	return 0;
}