Preface

之前有看别人写过每天的做题记录，今天准备写题解时突然想起来了这个。

感觉一题一个题解太占空间了QAQ，不如以后都以这样的形式记录我的训练生活。

今天还是挺开心的，切了三道题，然后愉快地颓了一天。

Content

[CF980D]Perfect Groups

题意：对于一个长度为 \(len\) 的序列 它的答案定义为最小划分的组数（以使得每个组中的数两两乘积为平方数)。

给定一个长为 \(n\) 的序列 \(a\)，求出答案为 \(1\sim n\) 的序列个数。

\(1 \le n \le 5\times 10^3,- 10^8\le a_i \le 10^8\)。

简单题。就是不知道为啥在 DP 题单里（

Lemma：若 \(a \times b,b \times c\) 均为平方数，则 \(a \times c\) 为平方数。

证明：

根据唯一分解定理，分解 \(a,b,c\)，得：

由题知：\(\forall i \in [1,k],a_i+b_i \equiv b_i+c_i \equiv 0\pmod{2}\)

\(\therefore a_i \equiv c_i\pmod{2}\)

\(\therefore a_i+ci \equiv 0\pmod{2}\)

证毕。

那么这题就变得简单了，由于数据范围支持 \(O(N^2)\)，显然可以用并查集维护所有乘积为平方数的数的集合。

统计答案时直接 \(O(N^2)\) 暴力扫一遍即可。

如果你真的这么做了，就会像我一样 Wrong Answer on test#18。

观察数据，会发现是 \(0\) 使得答案不正确。

那么在并查集合并时直接舍去 \(0\)，统计答案时扫到 \(0\) 直接特判一下就行啦 ~。

时间复杂度：\(O(N^2)\)。

Code

// Problem: CF980D Perfect Groups
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF980D
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 5;
int n,ans[maxn],pre[maxn];
ll a[maxn];
bool vis[maxn];
int find(int x) {
    return x == pre[x] ? x : pre[x] = find(pre[x]);
}
int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i)scanf("%lld",&a[i]),pre[i] = i;
    for(int i = 1;i <= n;++ i) {
        for(int j = i - 1;j;-- j) {
            if(a[i] * a[j] <= 0)continue ;
            ll t = sqrt(a[i] * a[j]);
            if(t * t == a[i] * a[j]) {
                pre[i] = find(j);
                break ;
            }
        }
    }
    for(int i = 1;i <= n;++ i) {
        int cnt = 0;
        memset(vis , false , sizeof(vis));
        for(int j = i;j <= n;++ j) {
            if(!a[j]) {
                ++ ans[max(cnt , 1)];
                continue ;
            }
            cnt += !vis[find(j)];
            vis[find(j)] = true;
            ++ ans[cnt];
        }
    }
    for(int i = 1;i <= n;++ i)printf("%d ",ans[i]);
    return 0;
}

[CF213C]Relay Race

初一时就学过的一道题，但重新看到的时候却忘了思路QAQ。

题意：给定一个 \(n\times n\) 的矩阵 \(a\)，一个人从 \((1,1)\) 走到 \((n,n)\) 再走回 \((1,1)\)，收获的价值为路径上所有数的和（一个数最多只被计入一次），求最大价值。

如果按照题目要求设计 DP 显然非常困难，考虑转化为：两个人同时从 \((1,1)\) 走到 \((n,n)\) 收获的最大价值。

显然，这样转化后，重复的问题就很好解决了。

设 \(f(i,j,x,y)\) 表示第一个人走到 \((i,j)\)，另一个人走到 \((x,y)\) 且 \(i+j=x+y\) 的最大价值。

发现这样写的话时空复杂度均为 \(O(N^4)\)，无法承受。

由于 \(i+j=x+y\)，考虑一个较为经典的优化：去掉 \((j,y)\) 两维，新增一维 \(k=i+j=x+y\)。

现在状态转化为：\(f(k,i,x)\) 表示第一个人走到 \((i,k-i)\)，另一个人走到 \((x,k-x)\) 时的最大价值。

初始状态：\(f(2,1,1)=a_{1,1}\)。

状态转移方程：

\(f(k,i,x)=\max(f(k-1,i-1,x),f(k-1,i-1,x-1),f(k-1,i,x),f(k-1,i,x-1))+v(k,i,x)\)。

其中 \(v(k,i,x)\) 表示当前的价值。

目标状态：\(f(2\times n,n,n)\)。

时空复杂度降至 \(O(N^3)\)。

// Problem: CF213C Relay Race
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF213C
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
int n,a[maxn][maxn],f[maxn << 1][maxn][maxn];
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			scanf("%d",&a[i][j]);
		}
	}
	memset(f , -0x3f , sizeof(f));
	f[2][1][1] = a[1][1];
	for(int k = 3;k <= (n << 1);++ k) {
		for(int i = 1;i <= min(k - 1 , n);++ i) {
			for(int x = 1;x <= min(k - 1 , n);++ x) {
				int j = k - i;
				int y = k - x;
				if(j >= 1&&j <= n&&y >= 1&&y <= n) {
					if(i > 1&&x > 1)f[k][i][x] = max(f[k][i][x] , f[k - 1][i - 1][x - 1]);
					if(i > 1&&y > 1)f[k][i][x] = max(f[k][i][x] , f[k - 1][i - 1][x]);
					if(j > 1&&x > 1)f[k][i][x] = max(f[k][i][x] , f[k - 1][i][x - 1]);
					if(j > 1&&y > 1)f[k][i][x] = max(f[k][i][x] , f[k - 1][i][x]);
					f[k][i][x] += a[x][y];
					if(x != i)f[k][i][x] += a[i][j];
				}
			}
		}
	}
	printf("%d\n",f[n << 1][n][n]);
	return 0;
}

[CF731D]80-th Level Archeology

有 \(n\) 个数列 \(a_1\sim a_n\) 和一个数字 \(c\)，一次操作可以让这 \(n\) 个数列中所有小于 \(c\) 的数都加 \(1\)，所有等于 \(c\) 的数变成 \(0\)。最少操作几次可以让这 \(n\) 个数列满足字典序升序排列。

首先会发现：操作的最小次数一定在 \([0,c]\) 间，因为这个操作呈周期性。

考虑相邻的两个数列 \(a_i,a_{i+1}\)，显然决定两者字典序大小的是一个位置 \(j\)，满足 \(\forall k \in [1,j),a_{i,k}=a_{i+1,k}\) 且 \(a_{i,j} \neq a_{i+1,j}\)。

分类讨论一下使得 \(a_{i,j} \lt a_{i+1,j}\) 的操作次数 \(q\)：

• \(a_{i,j} \lt a_{i+1,j}\)，则 \(q \in [0,c-a_{i+1,j}]\cup[c-a_{i,j}+1,c]\)

• \(a_{i,j} \gt a_{i+1,j}\)，则 \(q \in [c-a_{i,j}+1,c-a_{i+1,j}]\)

推导并不算难，可以自己手玩一下。

显然最后的答案要满足 \(i = 2\sim n\) 的所有情况的限制。

那么可以用差分数组 \(sum\) 维护一下上面的一坨式子，最后做个前缀和。

则 \(ans = \min\limits_{q\in [0,c]\land sum_q=n-1} q\)。

时间复杂度 \(O(N)\)。不明白的地方可以参考代码。

（小插曲：第一次写的时候脑抽写了个树状数组跑得巨慢，还以为我实现错了，结果发现是 std::vector 常数巨大，最后才发现完全不用树状数组QAQ）

Code

// Problem: CF731D 80-th Level Archeology
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF731D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 1e6 + 5;
int n,c;
int sum[maxn],len[maxn];
vector<int> G[maxn];
int main() {
	scanf("%d %d",&n,&c);
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&len[i]);
		for(int k = 1;k <= len[i];++ k) {
			int x;
			scanf("%d",&x);
			G[i].pb(x);
		}
	}
	for(int i = 2;i <= n;++ i) {
		bool flag = false;
		for(int k = 0;k < len[i];++ k) {
			if(k >= len[i - 1])break ;
			if(G[i - 1][k] != G[i][k]) {
				if(G[i - 1][k] < G[i][k]) {
					++ sum[0];
					-- sum[c - G[i][k] + 1];
					++ sum[c - G[i - 1][k] + 1];
					-- sum[c + 1]; //这句可以不用加(吧)
				}
				else {
					++ sum[c - G[i - 1][k] + 1];
					-- sum[c - G[i][k] + 1];
				}
				flag = true;
				break ;
			}
			else continue ;
		}
		if(!flag) {
			if(len[i - 1] > len[i]) {
				puts("-1");
				return 0;
			}
			else {
				++ sum[0];
			}
		}
	}
	for(int i = 1;i <= c;++ i)sum[i] += sum[i - 1];
	int ans = -1;
	for(int i = 0;i <= c;++ i) {
		if(sum[i] == n - 1) {
			ans = i;
			break ;
		}
	}
	printf("%d\n",ans);
	return 0;
}

后面还打了场 ABC，成绩太丢人就不放了 /kel