模拟赛记录
23CSP7连测
9.2 day1
260->100+100+5+10=225
C暴力写寄了。
A
tag : 二维前缀和
前缀和记录一下左边和上面跟自己不一样的数量，暴力查询每一个矩形。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e3 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, h, w, k, res;
int a[N][N], up[N][N], L[N][N];
int sum(int s[][2005], int x1, int y1, int x2, int y2) {
if(!(x1 <= x2 && y1 <= y2)) return 0;
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> h >> w >> k;
for(int i = 1; i <= n; i ++) {
string s;
cin >> s;
for(int j = 1; j <= m; j ++) {
a[i][j] = s[j - 1] - '0';
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
if(i != 1) up[i][j] = (a[i][j] != a[i - 1][j]);
if(j != 1) L[i][j] = (a[i][j] != a[i][j - 1]);
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
up[i][j] += up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1];
L[i][j] += L[i - 1][j] + L[i][j - 1] - L[i - 1][j - 1];
}
}
for(int i = 1; i + h - 1 <= n; i ++) {
for(int j = 1; j + w - 1 <= m; j ++) {
int ni = i + h - 1, nj = j + w - 1;
int tot = sum(up, i + 1, j + 1, ni - 1, nj - 1);
tot += sum(L, i + 1, j + 1, ni - 1, nj - 1);
tot += sum(up, ni, j + 1, ni, nj - 1);
tot += sum(L, ni, j + 1, ni, nj - 1);
tot += sum(up, i + 1, j, ni - 1, j);
tot += sum(up, i + 1, nj, ni - 1, nj);
tot += sum(L, i + 1, nj, ni - 1, nj);
tot += sum(L, i, j + 1, i, nj - 1);
tot += sum(up, ni, j, ni, j);
tot += sum(L, i, nj, i, nj);
tot += sum(up, ni, nj, ni, nj) + sum(L, ni, nj, ni, nj);
if(tot >= k) res ++;
}
}
cout << res << '\n';
return 0;
}
B
tag : 我也不知道
乱搞？
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
void solve() {
int n;
LL sum = 0;
cin >> n;
vector<int> a(n);
int f = 1;
LL s = 0;
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
for(int i = n - 1; i >= 0; i --) {
s += a[i] * f;
f *= -1;
}
if(n % 2 == 0) {
if(s == 0) cout << 1 << '\n';
else cout << 0 << '\n';
}
else if(s & 1 || s < 0) {
cout << 0 << '\n';
}
else {
s >>= 1;
for(int i = 0; i < n; i ++) {
s = a[i] - s;
if(s < 0) {
cout << 0 << '\n';
return;
}
}
cout << 1 << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t;
cin >> t;
while(t --) {
solve();
}
return 0;
}
C
tag : 矩阵加速递推
一眼矩阵快速幂，但是系数是会变的赛时没想出来。
模数 2027 比较小， \(f_i，f_{i+2027}\) 的转移矩阵是一样的，可以预处理。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 2027;
LL n;
int m;
int a[20];
struct Matrix {
int n, m;
int c[20][20];
void init(int _n, int _m) {
n = _n, m = _m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) c[i][j] = 0;
}
Matrix operator *(const Matrix t) const {
static Matrix res;
res.init(n, t.m);
for(int i = 1; i <= res.n; i ++)
for(int j = 1; j <= res.m; j ++)
for(int k = 1; k <= m; k ++) {
res.c[i][j] = (res.c[i][j] + c[i][k] * t.c[k][j]) % mod;
}
return res;
}
} base, ans, cur[N];
Matrix power(Matrix a, LL b) {
Matrix res;
res.init(15, 15);
for(int i = 1; i <= 15; i ++) {
res.c[i][i] = 1;
}
for(; b; a = a * a, b >>= 1) if(b & 1) res = res * a;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
cin >> a[i];
}
ans.init(1, 15), base.init(15, 15);
ans.c[1][1] = 1;
for(int i = 1; i <= 15; i ++) {
base.c[i][i] = 1;
}
for(int i = 1; i <= 2027; i ++) {
Matrix &t = cur[i];
t.init(15, 15);
for(int j = 1; j <= 14; j ++) {
t.c[j][j + 1] = 1;
}
for(int j = 1; j <= m; j ++) {
t.c[a[j]][1] = (i - a[j] + 1 + mod) % mod;
}
base = base * t;
}
ans = ans * power(base, n / 2027);
for(int i = 1; i <= n % 2027; i ++) {
ans = ans * cur[i];
}
cout << ans.c[1][1] << '\n';
return 0;
}
D
tag : 二分
待补。
23NOIP10连测
8.27 day1
100+100+15=215
A
tag : 我也不知道。
乱猜就过了。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n;
string s;
LL a[N], sum[N], need[N];
// 狠狠的猜结论过大样例
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
cin >> s;
for(int i = 0; i < n; i ++) {
if(s[i] == '(') a[i + 1] = 1;
else a[i + 1] = 0;
}
for(int i = 1; i <= n; i ++) {
sum[i] = sum[i - 1] + a[i];
need[i] = (i + 1) / 2;
}
LL res = 0;
for(int i = 1; i <= n; i ++) {
res += max(need[i] - sum[i], 0ll);
}
cout << res << '\n';
return 0;
}
B
tag : 暴力？
暴力枚举每个操作能不能进行，判下是否合法。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 25, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m;
string s;
set<PII> ans;
int down_x, down_y, up_x, up_y, r, c;
int id(int x, int y) {
x -= down_x - 1, y -= down_y - 1;
return c * (x - 1) + y;
}
void check(int state) {
map<int, int> mp;
int now_x = 0, now_y = 0;
mp[id(0, 0)] = 2;
for(int i = 1; i <= n; i ++) {
int nx = now_x, ny = now_y;
if(s[i] == 'L') {
nx --;
}
else if(s[i] == 'R') {
nx ++;
}
else if(s[i] == 'D') {
ny --;
}
else {
ny ++;
}
if(state >> (i - 1) & 1) {
if(mp[id(nx, ny)] == 1) {
return;
}
now_x = nx, now_y = ny;
mp[id(nx, ny)] = 2;
}
else {
if(mp[id(nx, ny)] == 2) {
return;
}
mp[id(nx, ny)] = 1;
}
}
ans.insert({now_x, now_y});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> s;
s = " " + s;
for(int i = 1; i <= n; i ++) {
if(s[i] == 'L') {
down_x --;
}
else if(s[i] == 'R') {
up_x ++;
}
else if(s[i] == 'D') {
down_y --;
}
else {
up_y ++;
}
}
r = up_x - down_x + 1, c = up_y - down_y + 1;
for(int i = 0; i < 1 << n; i ++) {
check(i);
}
cout << ans.size() << '\n';
for(auto v : ans) {
cout << v.first << ' ' << v.second << '\n';
}
return 0;
}
C
tag : 线性基
没学，待补。
D
tag : 计算几何，凸包，闵科夫斯基和
没学，待补。
23NOIP赛前20连测
还没开始。