[赛记] 暑假集训CSP提高模拟17
符号化方法初探 100pts
签到题？做了得有1.5h+；
考虑全是正数或全是负数的情况，那么我们可以对其做一次类似于前缀和或后缀和的操作，需要 $ n - 1 $ 次；
所以我们只需将数列中的数全部转化成正数或负数即可，具体地，找出所有正数的和和所有负数的和，如果前者比后者要大，那么就将所有正数加起来，然后让所有负数加它，反之同理，然后做一遍上一步的类似于前缀和或后缀和的操作即可；
总操作数：$ 2n - 2 $ 次；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int n, m;
long long a[500005];
struct sss{
long long i, j;
}e[2000005];
long long sumz, sumf;
vector<int> z, f;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > 0) {
sumz += a[i];
z.push_back(i);
} else {
sumf += a[i];
f.push_back(i);
}
}
if (sumz >= abs(sumf)) {
for (int i = 1; i < z.size(); i++) {
e[++m] = {z[i], z[0]};
}
for (int i = 0; i < f.size(); i++) {
e[++m] = {z[0], f[i]};
}
for (int i = 2; i <= n; i++) {
e[++m] = {i - 1, i};
}
} else {
for (int i = 1; i < f.size(); i++) {
e[++m] = {f[i], f[0]};
}
for (int i = 0; i < z.size(); i++) {
e[++m] = {f[0], z[i]};
}
for (int i = n - 1; i >= 1; i--) {
e[++m] = {i + 1, i};
}
}
cout << m << endl;
for (int i = 1; i <= m; i++) {
cout << e[i].i << ' ' << e[i].j << endl;
}
return 0;
}
无标号 Sequence 构造 0pts
原题：Luogu P10102 [GDKOI2023 提高组] 矩阵
暴力 $ \Theta(n^3) $ 很好打，然后就挂了。。。
主要是优化；
应该可以算是套路吧？当然也是随机化；
把左右两边同时乘一个 $ 1 * n $ 的矩阵，这样我们就可以在 $ \Theta(n^2) $ 的时间里判断是否相等；
这个矩阵随一个就行；
只要不乘出来变成 $ 0 $，那么这个东西就是对的；
正确率应该是 $ \frac{1}{998244353} $（貌似是秩-零化定理，我不会）；
当然，你也可以让它最后变成 $ 1 * 1 $ 的矩阵，但时间复杂度是一样的，而且最后的正确率也会变低；
注意空间；
点击查看代码
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
#define int long long
const int mod = 998244353;
int t;
int n;
long long a[3005][3005], b[3005][3005], c[3005][3005], d[3005], e[3005], f[3005], g[3005];
main() {
srand(time(0));
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> b[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> c[i][j];
}
}
for (int i = 1; i <= n; i++) {
d[i] = (rand() + mod) % mod;
}
for (int i = 1; i <= n; i++) {
e[i] = 0;
f[i] = 0;
g[i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
e[i] = (e[i] + a[j][i] * d[j] % mod) % mod;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i] = (f[i] + b[j][i] * e[j] % mod) % mod;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i] = (g[i] + c[j][i] * d[j] % mod) % mod;
}
}
bool vis = false;
for (int i = 1; i <= n; i++) {
if (f[i] != g[i]) {
vis = true;
break;
}
}
if (vis) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
return 0;
}