ZR 七连测

2023-09-28 08:34:56 # Note #Train

Day 1

T1

一道二维前缀和。

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int mp[N][N];
int sum[N][N];
int sumRigh[N][N],sumDown[N][N];
char a[N][N];
string s[N];
int main()
{
    // freopen("E:/下载/Compressed/problem_2633/ex_A2.in","r",stdin);
    int n, m, h, w, k;
    scanf("%d%d%d%d%d",&n,&m,&h,&w,&k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s\n", a[i] + 1);
        s[i] = a[i];
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) // 每个点只看它的右边和下边
        {
            // if(i - 1 >= 1) a[i][j] += (a[i-1][j]!=a[i][j]);
            // if(j - 1 >= 1) a[i][j] += (a[i][j-1]!=a[i][j]);
            if(i + 1 <= n) mp[i][j] += (a[i + 1][j] != a[i][j]);
            if(j + 1 <= m) mp[i][j] += (a[i][j + 1] != a[i][j]);
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) // 每个点只看它的右边和下边
        {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mp[i][j]; // printf("sum[%d][%d] = %d\n", i, j, sum[i][j])
            if(a[i][j] != a[i + 1][j] && i + 1 <= n) sumDown[i][j] = sumDown[i][j - 1] + 1; // 下面总和
            else sumDown[i][j] = sumDown[i][j - 1];
        }
    for(int j = 1; j <= m; ++j)
        for(int i = 1; i <= n; ++i)
        {
            if(a[i][j] != a[i][j + 1] && j + 1 <= m) sumRigh[i][j] = sumRigh[i - 1][j] + 1; // 右边总和
            else sumRigh[i][j] = sumRigh[i - 1][j];
            // printf("sum[%d][%d] = %d\n",i,j,sumRigh[i][j]);
        }
    int now = 0,ans = 0;
    int x1, y1, x2, y2;
    for(int i = 1; i + h - 1 <= n; ++i)
        for(int j = 1; j + w - 1 <= m; ++j)
        {
            x1 = i;
            y1 = j;
            x2 = i + h - 1;
            y2 = j + w - 1;
            now = sum[x2][y2] + sum[x1 - 1][y1 - 1] - sum[x1 - 1][y2] - sum[x2][y1 - 1];
            // for(int l = y1; l <= y2; l++) // 最后一行
            //     if(a[x2][l] != a[x2 + 1][l] && x2 + 1 <= n) now--;
            now -= sumDown[x2][y2] - sumDown[x2][y1 - 1];
            now -= sumRigh[x2][y2] - sumRigh[x1 - 1][y2];
            // for(int l = x1; l <= x2; l++)
            //     if(a[l][y2] != a[l][y2 + 1] && y2 + 1 <= m) now--;
            if(now >= k) ans++;
        }
    printf("%d", ans);
    return 0;
}

T2

记 $b_i$ 为 $a_{i}$ 和 $a_{i-1}$ 之间需要共同减掉的次数，那么就要满足 $b_{i-1}+b_i=a_i$ 。

然后考虑每个 $b_i$ ，把它变成一个 $\pm b_0+c$ 的形式，如果 $n$ 是奇数，那么 $b_{n-1}=b_0+c$ ，然后 $b_0+b_{n-1}=k$ ，这样就可以解出 $b_0$ ，然后求其它的 $b_i$ ，如果算出有结果小于零或者是小数，那就是无解，否则有解。

如果 $n$ 是偶数，这时候 $b_{n-1}=-b_0+c$ ， $b_0+b_{n-1}=k$ ，这时候如果带入的话就会都消掉什么也解不出来，这时候 $c$ 和 $k$ 是相同的，

$\pm b_i=b_0+c,b_i\ge0$ 这样就可以把 $b_0$ 解出一个范围，如果这个范围内有非负整数解的话，那就满足条件，否则无解。

考场就写了个 $sum$ 是否为偶数的特判🤣。

T3

$f_i=\sum_{j\in S} f_{i-j}\times (i-j+1)$ ，可以用矩阵乘法维护这个十五行的矩阵。

考虑构造左边的矩阵，

比如 1 存在的话，那么第一行第一列就是 $i$ ，因为 $f_i=f_{i-1}\times i$ 。

然后存在的话就填 $i-k+1$ ，不然就填 0，然后下面几行该位存在就往后填一位 1，这样就可以保证递推。

这时候可以尝试使用矩阵快速幂，但是这里的每次要乘的矩阵都不相同，所以不可以通过矩阵乘法来维护，但是这个模数非常特殊，比较小，如果在矩阵里把每个数都模一个 2027，这个矩阵第一行其实是循环的，下面是不变的， $n$ 很大的情况下会形成很多个循环节，每个对应一个矩阵乘法，然后后面可能会剩一些，但也不会超过 2027。

09XDUSI%$7_RX3%Y1K2(NYS.png

由于矩阵乘法满足结合律，所以可以先处理一段循环节，然后再处理矩阵快速幂，最后再加上多出来的矩阵。

递推式也可以写成：

$f_i=i\times{\sum f_{i-j}}$

如果这样递推出来的话就是 $\dfrac{f_{n}}{n}$ ，因为最后一个不需要考虑，

但是如果 $n$ 是 2027 的倍数的话，就不能直接推到第 $n$ 项，需要求出 $n-1$ 项再求第 $n$ 项。

考场代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 2027;
const int N = 1e8 + 3e7;
ll f[N];
vector<int> s;
int main()
{
    // freopen("E:/下载/Compressed/problem_2635/ex_C2.in","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i)
    {
        int a;
        scanf("%d",&a);
        s.emplace_back(a);
    }
    sort(s.begin(),s.end());
    f[0] = 1;
    for(int i = 0; i <= n; ++i)
    {
        for(auto &j : s)
        {
            int v = i + j;
            if(v > n) continue;
            f[v] += f[i] * (i + 1) % mod;
        }
    }
    printf("%lld", (f[n] % mod));
    return 0;
}

我这样递推最后就不用乘以一个 $n$ 。

T4

二分答案

往里放数，使得每两个数之间的差都小于等于 $k$ 是否可行。

每个数可以往左放和往右放，肯定是把这个序列分成好多段，一些是往左放一些是往右放，所以每一段就可以用 RMQ 求一个差的最大值，由于分界点的位置知道，剩下的东西就很好维护，而且相邻两个分界点的数差也不能超过 $k$ 。

记 $dp_i$ 表示以 $i$ 和 $i+1$ 为一个分界点时是否可行。

它可以从前面最远的一个 $j$ 满足 $f_j=1$ 转移而来，

这个 $j$ 要满足 $j\sim{i}$ 这些数的差的最大值小于等于 $k$ 。

并且 $a_j-a_{i+1}\le{x}$ ，这是因为可以把原序列分为若干段，要么是左要么是右，两个相邻的分界点由于是放在同一端，所以它们的端点之间也需要满足条件。

满足条件的 $a_j$ 是一段区间，也就是 $a_{i+1}-k\sim{a_{i+1}+k}$ 。

而满足以 $i$ 为右端点的后缀且满足这段后缀最大差小于等于 $k$ 可以用倍增求出最小的 $j$ ，然后用线段树维护合法的分界点，查询 $a_j$ 在某段区间中 $j$ 的最大值即可。

但是由于常数问题，会被卡到 80 分。

一百分：

实际上就是没有放，只是不断扩展这两段区间，每次判断一下范围即可。

不会编了。

考场代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

int n;
int a[N];

bool check(int x)
{
    deque<int> q;
    q.push_back(a[1]);
    for(int i = 2; i <= n; ++i)
    {
        if(a[i] - q.front() <= a[i] - q.back())
        {
            if(a[i] - q.back() <= x) q.push_back(a[i]);
            else if(a[i] - q.front() <= x) q.push_front(a[i]);
            else return false;
        }
        else if(a[i] - q.front() > a[i] - q.back())
        {
            if(a[i] - q.front() <= x) q.push_front(a[i]);
            else if(a[i] - q.back() <= x) q.push_back(a[i]);
            else return false;
        }
    }
    return true;
}
int main()
{
    // freopen("E:/下载/Compressed/problem_2636/ex_D2.in","r",stdin);
    scanf("%d", &n);
    int l = 0,r = 0;
    int minn = 0x3f3f3f3f,maxn = -1;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        minn = min(minn, a[i]);
        maxn = max(maxn, a[i]);
    }
    r = maxn - minn;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", r);
    return 0;
}

用了一个 deque 进行贪心模拟，甚至有 55 分。

Day2

T1

题意简化：

给你一个序列，问有多少对数在模 200 意义下相等。

那就对 $0\sim200$ 内每一个数建一个桶，答案就是 $\sum_{i=1}^n {i\choose2}$ 。

记得开 long long。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
typedef long long ll;

int a[N];
ll ans;
int sum[N][205];
ll c[N][3];

void init()
{
    for(int i = 2; i <= 200000; ++i)
        c[i][2] = 1ll * i * (i - 1) / 2;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        if(a[i] < 0) a[i] += ((-a[i]/200)+1)*200;
        a[i] %= 200;
        sum[i][a[i]]++;
    }
    init();
    for(int j = 0; j < 200; j++)
        for(int i = n; i >= 1; --i) 
            sum[i][j] += sum[i + 1][j];
    for(int i = 0; i < 200; ++i)
        ans += c[sum[1][i]][2];
    printf("%lld\n", ans);
    return 0;
}

T2

考虑贪心做法：

最小：

从左往右考虑，这个人如果左边右边还有自己的位置都没有人，那么肯定是往右会更优，因为往右可能会与下一个人相遇，而往左或者不动概率就会小。

而对于周围有人的情况，那就直接过去即可。

最多：

最少的时候我们尽量让一个周围都没人的人往右靠，那么最多与他相反，在不与他人重合的情况下，优先往左靠。

DP 的话那就令 $f_{i,0/1/2}$ 代表考虑完了前 $i$ 个位置并且第 $i$ 个位置是向左/不动/向右，的最小/最大房屋数，本人当时就这么写的但是转移方程看上去很麻烦就没有信心推下去，写了一半 DP 一半贪心，光荣挂分。

T3

CF1735C

有两个串 $S$ 和 $T$ ，存在 $S\to T$ 的一个映射关系，映射关系为字母之间的一个环，大小为 26。

现在给定 $T$ ，求字典序最小的 $S$ 。

可以考虑贪心的做法，从前往后遍历，对于每个第一次出现的字母，寻找它对应的合法的且字典序最小的一个映射。

这里合法指的是不能提前形成环，也就是不能在大小 $<26$ 之前就形成了环，比如 $\text{ab}$ 不能与 $\text{ba}$ 建立一个映射关系，因为如果这样 $a$ 就是 $b$ 的下一个， $b$ 也是 $a$ 的下一个，这样就构成了一个二元环，其它元素没有办法插入，也就不合法。

当前环的大小可以每次向前跳统计长度，也可以通过并查集维护大小。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

char s[N];
map<char,char> mp, az;

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		scanf("%s", s + 1);
		mp.clear();
		az.clear();
		for(int i = 1; i <= n; i++) // 为每个字符寻找映射
		{
			if(mp[s[i]]) printf("%c", mp[s[i]]);
			else
			{
				for(char t= 'a' ; t <= 'z'; t++)
				{
					if(t == s[i]) continue;
					if(!az[t]) // t还没有映射对象
					{
						char tt = t;
						int cnt = 0; 
						while(tt && tt != s[i])
						{
							cnt++;
							tt=mp[tt]; 
						}
						if(tt == s[i] && cnt < 25) continue; // 判断不合法情况
						printf("%c", t); // 可以的话那么t就是字典序最小的映射
						mp[s[i]] = t;
						az[t] = mp[s[i]];
						break;
					}
				}
			}
		}
		printf("\n");
	}
	return 0;
}

T4

首先暴力可以想到跑 Floyed 全源最短路，枚举一个中间点，复杂度 $O(n^3)$

$1\to u$ 的路径其实分为两段， $1\to p+u\to p$ ，我们要求这个路径的最小值，

由于后半部分边是反向的，所以我们可以建反向图（分层图），然后在原图和反向图之间两个编号相同的点之间建立一条边权为 0 的边，然后以原图的 1 号点为原点，以反向图中的每一个点为终点跑最短路即可。

复杂度就是 Dijkstra 的复杂度。

2023-09-28 08:34:56 # Note #Train