ZROI CSP七连测 Day 1

发表于 更新于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

这篇其实早就写好了，只是一直搞忘了放上来。

A

给定一个 nn 行 mm 列的 0101网格图，计算有多少个 hh 行 ww 列的子矩形满足 存在大于等于 KK 对相邻且不同色的格子。

n,m≤2000n,m\leq 2000

二维前缀和即可。

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
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=2005;
int n,m,h,w,K;
int g[maxn][maxn];
int f[maxn][maxn],row[maxn][maxn],line[maxn][maxn];
int ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>h>>w>>K;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<m;j++) g[i][j+1]=s[j]-'0';
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=m;j++)
        {
            row[i][j]=row[i][j-1];
            if(g[i][j]!=g[i][j-1]) row[i][j]++;
        }
    }
    for(int j=1;j<=m;j++)
    {
        for(int i=2;i<=n;i++)
        {
            line[i][j]=line[i-1][j];
            if(g[i][j]!=g[i-1][j]) line[i][j]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            line[i][j]+=line[i][j-1];
            row[i][j]+=row[i-1][j];
        }
    }
    for(int i=1;i<=n-h+1;i++)
    {
        for(int j=1;j<=m-w+1;j++)
        {
            int num=row[i+h-1][j+w-1]-row[i+h-1][j]-row[i-1][j+w-1]+row[i-1][j];
            num+=line[i+h-1][j+w-1]-line[i][j+w-1]-line[i+h-1][j-1]+line[i][j-1];
            if(num>=K) ++ans;
        }
    }
    cout<<ans<<endl;
    return 0;
}

B

给定一个有 nn 个整数的环，每次可以选择相邻的两个并把它们减少 11，问是否存在把所有数都变成 00 的方案

n≤5×105,0≤ai≤109n\leq 5\times 10^5,0\leq a_i\leq 10^9

设 bib_i 为同时在 ii 和 i%n+1i\%n+1 进行操作的次数，那么就可以得到 nn 条限制，每条限制形如 b(i−1)%n+bi=aib_{(i-1)\%n}+b_i=a_i。设 sum=a1−a2+a3−a4+⋯±ansum=a_1-a_2+a_3-a_4+\cdots \pm a_n（最后的正负由 nn 的奇偶性决定）。

我们可以通过上述 nn 条限制把所有 bib_i 用 b1b_1 表示出来，那么可以得到：

bn={b1+sum−a1,n是奇数−b1−sum+a1,n是偶数b_n=\left\{ \begin{aligned} &b_1+sum-a_1, n 是奇数\\ &-b_1-sum+a_1, n 是偶数 \end{aligned} \right.

把这个式子代入到 bn+b1=a1b_n+b_1=a_1 中来，那么若 nn 是奇数，就可以把 b1b_1 解出来，进而解出所有的 bib_i，若满足所有 bi≥0b_i\geq 0，即为合法；若 nn 是偶数，可以发现，当且仅当 sum=0sum=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
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
int t;
const int maxn=5e5+5;
int n;
int a[maxn];
int main()
{
    //freopen("ex_B2.in","r",stdin);
    //freopen("b.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        ll sum=0;
        for(int i=1;i<=n;i++) 
        {
            if(i&1) sum+=a[i];
            else sum-=a[i];
        }
        if(n&1)
        {
            if(sum&1) 
            {
                cout<<0<<endl;
                continue;
            }
            bool flag=true;
            for(int i=1;i<=n;i++)
            {
                sum=2*a[i]-sum;
                if(sum<0)
                {
                    flag=false;
                    break;
                }
            }
            if(sum>=0&&flag) cout<<1<<endl;
            else cout<<0<<endl;
        }
        else
        {
            if(!sum) cout<<1<<endl;
            else cout<<0<<endl;
        }
    }
    return 0;
}

C

给定一条直线上的 nn 个位置，从左到右编号为 00 到 nn，第 ii 个位置里有 ii 个不同的物品。从 00 出发，在每一个时刻都会离开当前所在位置去往下一个位置，若当前位置为 ii，到达的下一个位置 jj 需满足 j−i∈Sj-i\in S，其中 SS 为只包含不大于 1515 的正整数的集合，若 i≥0i\geq 0，离开的同时还会破坏第 ii 个位置中的之多一个物品。

给定一个正整数 nn，若最后到达了 nn 号位置，那么你有多少种破坏物品的方案，答案对 20272027 取模。

n≤1018n\leq 10^{18}

fi=∑j∈S(i−j+1)fi−jf_i=\sum\limits_{j\in S} (i-j+1)f_{i-j}

可以写成矩阵乘法的形式，然后发现转移矩阵存在长为 20272027 的循环节，因此可以先暴力计算一个循环节相乘的结果，再对这个结果做矩阵快速幂，最后乘上不满一个循环节的部分。

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
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxs=16;
const int mod=2027;
struct Matrix
{
    int a[maxs][maxs];
    Matrix() {memset(a,0,sizeof(a));}
    Matrix operator * (const Matrix& x) const
    {
        Matrix res;
        for(int i=1;i<=15;i++)
        {
            for(int j=1;j<=15;j++)
            {
                for(int k=1;k<=15;k++)
                {
                    res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*x.a[k][j])%mod;
                }
            }
        }
        return res;
    }
};
Matrix qpow(Matrix a,ll n)
{
    Matrix res;
    if(n==0) 
    {
        for(int i=1;i<=15;i++) res.a[i][i]=1;
        return res;
    }
    res=a;
    --n;
    while(n)
    {
        if(n&1) res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}

ll n,m;
int s[maxs];
int main()
{
    //freopen("ex_C2.in","r",stdin);
    //freopen("c.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>s[i];
    ll a=n/mod,b=n%mod;
    Matrix x,y;
    for(int i=1;i<=15;i++) x.a[i][i]=1,y.a[i][i]=1;
    for(int i=1;i<=mod;i++)
    {
        Matrix tmp;
        for(int j=1;j<=m;j++) tmp.a[1][s[j]]=(i-s[j]+1+mod)%mod;
        for(int j=2;j<=15;j++) tmp.a[j][j-1]=1;
        x=tmp*x;
        if(b==i) y=x; 
    }
    Matrix ans=y*qpow(x,a);
    cout<<ans.a[1][1]<<endl;
    return 0;
}

D

给定长度为 nn 的序列 aa，要求每次对从 11 到 nn 的 ii，将 aia_i 添加到序列 bb 的开头或结尾。求 max⁡i=1n−1∣bi−bi+1∣\max^{n-1}_{i=1}|b_i-b_{i+1}| 的最小值。

考虑二分答案 kk，然后考虑每次放入一个新的数后，序列两侧可能放下的数的集合。

首先放下 a1a_1 和 a2a_2 后，两侧的集合分别是区间 [a1−k,a1+k][a_1-k,a_1+k] 和 [a2−k,a2+k][a_2-k,a_2+k]；

然后考虑放 a3a_3，如果它只被其中一个区间包含，那么它的放法是唯一的，而没放的那一边的区间不变；如果它被两个区间同时包含，那我们既可以把它放到左边，又可以放到右边，那么没放的那一边可能放下的数的集合即为 [a1−k,a1+k]∪[a2−k,a2+k][a_1-k,a_1+k]\cup [a_2-k,a_2+k]。而由于 a3a_3 被两个区间同时包含，一次这两个区间是有交的，因此这个并集仍然是一个区间。

以此类推，可以归纳证明，当我们放入一个数后，它另一侧能放的数的集合永远是一个区间。若下一个数只被其中一个区间包含，那么下一个数另一侧的区间就是它不能被放入的那个区间；如果被两个包含，另一侧的区间是两者的并；如果都不能包含，则无解。

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
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn=1e6+5;
int n;
int a[maxn];
inline bool check(int k)
{
    int l=a[1]-k,r=a[1]+k;
    int l1,r1;
    for(int i=3;i<=n;i++)
    {
        l1=a[i-1]-k,r1=a[i-1]+k;
        if(a[i]>=l1&&a[i]<=r1&&a[i]>=l&&a[i]<=r) l=min(l1,l),r=max(r1,r);
        else if(a[i]>=l&&a[i]<=r) l=l1,r=r1;
        else if(a[i]<l1||a[i]>r1) return 0;
    }
    return 1;
}
int main()
{
    //freopen("d.in","r",stdin);
    //freopen("d.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=abs(a[1]-a[2]),r=0;
    for(int i=1;i<=n;i++) r=max(r,a[i]);
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}