\(\text{Preface}\)
我觉得殷教说的很对。如果说强行让我写之前咕掉的总结我觉得意义不大，而且我大多数题也都忘了再写思路不一定对而且有亿点敷衍，所以我就写其中一部分吧
CSP-S模拟15
\(网格图\)
这个题我咕了一周多，后来花了整整一个上午调试+下午的一小会时间终于 \(\text{A}\) 掉
首先考虑暴力怎么打，显然是枚举这个 K*K 矩阵的右下角，然后扫一遍他的四周和内部统计答案，最后取最大值。时间复杂度大概是 \(O(N^4)\)，显然超时。有 \(\text{50pts}\) 的好成绩。但是sandom就这样A了，我不理解
当然了你得先预处理一下联通块的大小和每个点的 belong。
考虑如何优化这个过程。首先明确答案的组成：对于一个 K*K 矩形，他的答案可以分为 [①]『\(K \times K\) 块内 x 的个数』\(+\) [②]『完全被包含在 \(K \times K\) 块内的联通块大小』\(+\) [③]『\(K \times K\) 块四周的联通块大小』。
画个图理解：
那个黑框框框住的就是 K*K 矩形。
在这个图里边我按照刚才的标号给他重新标一下，就是这个样子：
在同一行中，发现当矩阵右移时并不需要整个的扫一遍，相反可以继承上一个状态的一些答案。因为③的答案可以直接两个 \(O(n)\) 的 \(\text{for}\)循环扫出来，所以考虑维护①和②的答案。
整三个答案变量分别算三个部分的答案。我给他们命名的分别是 xans isdans outans
isdans 指的就是 inside ans
具体地，先弄一个 used 数组标识一下当前这个联通块是否已经贡献过答案了，避免重复贡献。再整一个 isd 数组(inside)标识这个联通块是否被完全包含在 K*K 矩形中。
对于每一行，先爆扫第一个矩形，记录一下答案，然后开始移动。
在移动之前首先把左边那一列对块内部的贡献删去，显然的当左边这一列被删的时候出现了 . 就说明这个 . 所属的联通块不完全被包含在块内了。更新相关信息。
然后移动矩形，将 used 清空(因为重新统计即可，不用费劲继承上一个)，先扫矩形的四周，记录谁已经贡献过了。
最后再扫新加进来的这一列。因为刚才已经记录了谁被用过了，如果说当前新加进来的这一列中有个 . 的 used 为 false，这说明他是完全被包含在块内的了。记得更新他的 isd 数组。
如此移动即可。细节还行，不是特别多，调试时间这么长的原因是之前的思路太麻烦了，而且后来听新的思路又理解错了一次。。
不过代码还是自己写的，没有贺。
建议也别贺我的，我估计看了我写的代码得吐，不删注释有将近五百行(
Code
#include <iostream>
#include <bitset>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 505
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
找到问题了，是used[]的锅，检查在往右扫的时候used数组的变化是否正确，应该是这里挂了
锐评今日多校：一个题都不会改(
我又来改这个题了(
两百多行烂码
最终A掉已经接近五百行了。。。
*/
int n, K, L, R, kuainum, final_ans, isdans, outans, xans;
int belong[N*N], sz[N*N];
bitset<N*N> used, isd;
char s[N][N];
struct Poi{int x, y;};
struct Poi q[N*N*2];
inline void bfs(int x, int y, int ID){
L = 0, R = -1;
q[++ R] = (Poi){x, y}; belong[(x-1)*n + y] = ID; sz[ID] = 1;
struct Poi fw;
while (L <= R){
fw = q[L ++], x = fw.x, y = fw.y;
// 往左拓展
if (s[x][y-1] == '.' and belong[(x-1)*n + (y-1)] == 0 and y > 1)
q[++ R] = (Poi){x, y-1}, belong[(x-1)*n + (y-1)] = ID, sz[ID] ++;;
// 往右
if (s[x][y+1] == '.' and belong[(x-1)*n + (y+1)] == 0 and y < n)
q[++ R] = (Poi){x, y+1}, belong[(x-1)*n + (y+1)] = ID, sz[ID] ++;
// 往上
if (s[x-1][y] == '.' and belong[(x-2)*n + y] == 0 and x > 1)
q[++ R] = (Poi){x-1, y}, belong[(x-2)*n + y] = ID, sz[ID] ++;
// 往下
if (s[x+1][y] == '.' and belong[x*n + y] == 0 and x < n)
q[++ R] = (Poi){x+1, y}, belong[x*n + y] = ID, sz[ID] ++;
}
}
/*
5 2
..xxx
xx.xx
x.xxx
x...x
xxxx.
md，继续hack
嗯？！还是对的？！
我找正确代码对拍灞
我囸，大样例都过了
好吧我自己造数据
5 2
..xxx
x..xx
.xx..
..x.x
xxxx.
5 2
xxxx.
x.x..
.....
xxx.x
x..xx
5 2
.x..x
xx.xx
.xxxx
xxxxx
xxx.x
5 2
xx.xx
.xxxx
.xx.x
.x.xx
.xx..
好了这一组有锅：
5 2
..x..
xxxxx
xxxxx
xx..x
x.x.x
答案是方格右下角处于(3, 4)时 (3, 3)
还过不了
又来一组数据
5 2
x..x.
.xxxx
.x.xx
x.x..
.x.xx
答案在(3, 3)
*/
/*inline void Debug(){
cerr << "used: ";
for (re i = 1 ; i <= 6 ; ++ i)
cerr << used[i] << _;
Dl;
cerr << "still: ";
for (re i = 1 ; i <= 6 ; ++ i)
cerr << still[i] << _;
Dl;
cerr << "dld: ";
for (re i = 1 ; i <= 6 ; ++ i)
cerr << dld[i] << _;
Dl;
}*/
inline int id(int x, int y){return (x-1)*n+y;}
inline void work(){
cin >> n >> K;
for (re i = 1 ; i <= n ; ++ i)
cin >> s[i]+1;
/*cerr << n << _ << K << '\n';// 实在没办法了，这题拖了一周多了(套WA的数据点)
for (re i = 1 ; i <= n ; ++ i)
cerr << s[i]+1 << '\n';*/
for (re i = 1 ; i <= n ; ++ i){
for (re j = 1 ; j <= n ; ++ j){
if (s[i][j] == '.' and belong[(i-1)*n+j] == 0)
kuainum ++, bfs(i, j, kuainum);
}
}
/*for (re i = 1 ; i <= n ; ++ i){// 无锅
for (re j = 1 ; j <= n ; ++ j)
cerr << belong[(i-1)*n+j] << _;
Dl;
}
cerr << kuainum << '\n';
for (re i = 1 ; i <= kuainum ; ++ i)
cerr << sz[i] << _;
Dl; Dl;*/
// 核心思想又出错了！我囸！
// 完全在块内 + 四周 + 块内x的个数
// 好家伙样例WA了
for (re x = K, i, ii, j, jj ; x <= n ; ++ x){
// 先爆扫第一个
outans = isdans = xans = 0;
used = 0; isd = 0;
// 先扫边界并打上标记
// 右边
j = K+1;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
outans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 上边和下边
i = x-K, ii = x+1;
for (j = 1 ; j <= K ; ++ j){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
outans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
if (s[ii][j] == '.' and used[belong[id(ii, j)]] == false)
outans += sz[belong[id(ii, j)]], used[belong[id(ii, j)]] = true;
}
// 扫块内
for (i = x-K+1 ; i <= x ; ++ i){
for (j = 1 ; j <= K ; ++ j){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false and isd[belong[id(i, j)]] == false)// 完全被包含在块内
isdans += sz[belong[id(i, j)]], isd[belong[id(i, j)]] = true;
else if (s[i][j] != '.')
xans ++;
}
}
/*if (x == 3){
cerr << isdans << _ << outans << _ << xans << '\n';
cerr << "used: ";
for (re i = 1 ; i <= 5 ; ++ i)
cerr << used[i] << _;
Dl;
cerr << "isd: ";
for (re i = 1 ; i <= 5 ; ++ i)
cerr << isd[i] << _;
Dl;
}*/
final_ans = MAX(final_ans, isdans+outans+xans);
// 然后先把左边一列的isdans和xans删去
j = 1;
for (i = x-K+1 ; i <= x ; ++ i){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false and isd[belong[id(i, j)]] == true)
isdans -= sz[belong[id(i, j)]], isd[belong[id(i, j)]] = false;
else if (s[i][j] != '.')
xans --;
}
// 往右移
for (re y = K+1 ; y <= n ; ++ y){
used = 0; outans = 0;
// 先把外边一层标记上
// 左边和右边
j = y-K, jj = y+1;
for (i = x-K+1 ; i <= x ; ++ i){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
outans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
if (s[i][jj] == '.' and used[belong[id(i, jj)]] == false)
outans += sz[belong[id(i, jj)]], used[belong[id(i, jj)]] = true;
}
// 上边和下边
i = x-K, ii = x+1;
for (j = y-K+1 ; j <= y ; ++ j){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
outans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
if (s[ii][j] == '.' and used[belong[id(ii, j)]] == false)
outans += sz[belong[id(ii, j)]], used[belong[id(ii, j)]] = true;
}
// 搜新加入的列
j = y;
for (i = x-K+1 ; i <= x ; ++ i){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false and isd[belong[id(i, j)]] == false)
isdans += sz[belong[id(i, j)]], isd[belong[id(i, j)]] = true;
else if (s[i][j] != '.')
xans ++;
}
final_ans = MAX(final_ans, isdans+outans+xans);
// 把左边那一列的贡献给删掉
j = y-K+1;
for (i = x-K+1 ; i <= x ; ++ i){
if (s[i][j] == '.' and used[belong[id(i, j)]] == false and isd[belong[id(i, j)]] == true)
isdans -= sz[belong[id(i, j)]], isd[belong[id(i, j)]] = false;
else if (s[i][j] != '.')
xans --;
}
}
}
cout << final_ans << '\n';
// 仅仅需要把移动一格之后被删的边的点给加上，新加的边的点给减去，然后扫一遍四个框统计外部答案即可。我。。。
/*for (re x = K, i, j ; x <= n ; ++ x){// 右下角在第几行
// 直接暴扫第一个
isdans = 0; tmpans = 0; used = 0;
for (i = x-K+1 ; i <= x ; ++ i){
for (j = 1 ; j <= K ; ++ j){// 当前块内的
if (s[i][j] == '.')
isdans --;// insideans记录里边有几个是'.'，之后减去这个就好了
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
}
}
// 扫右边
j = K + 1;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 扫上边
i = x - K;
for (j = 1 ; j <= K ; ++ j)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 扫下边
i = x + 1;
for (j = 1 ; j <= K ; ++ j)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
final_ans = MAX(final_ans, tmpans+isdans+K*K);
if (x == 3)
cerr << "begin: " << isdans << _ << tmpans << '\n';
// 块向右移动
for (re y = K+1 ; y <= n ; ++ y){
// 扫左边变为相邻的边
used = 0; tmpans = 0;
j = y - K;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.')
isdans ++;
// 扫右边新加入的边
j = y;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.')
isdans --;
// 暴力扫块的四个边
// 左边
j = y - K;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 右边
j = y + 1;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 上边
i = x - K;
for (j = y-K+1 ; j <= y ; ++ j)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
// 下边
i = x + 1;
for (j = y-K+1 ; j <= y ; ++ j)
if (s[i][j] == '.' and used[belong[id(i, j)]] == false)
tmpans += sz[belong[id(i, j)]], used[belong[id(i, j)]] = true;
if (x == 3)
cerr << "y = " << y << " 時，ループ内: " << isdans << _ << tmpans << '\n';
final_ans = MAX(final_ans, tmpans+isdans+K*K);
}
cerr << x << _ << "真ん中のfinal_ans: " << final_ans << '\n';
}*/
/*for (re x = K ; x <= n ; ++ x){
used = 0;
tmpans = K*K;// 先暴力扫第一个
for (re i = x-K ; i <= x+1 ; ++ i){
for (re j = 0 ; j <= K+1 ; ++ j){
if ((i == x-K and j == 0) or (i == x-K and j == K+1) or (i == x+1 and j == 0) or (i == x+1 and j == K+1))
continue;
ider = (i-1)*n + j;
/*if (x == 3)
cerr << "遍历到了点(" << i << ", " << j << "):" << '\n' << "before-tmpans: " << tmpans << '\n';*//*
if (s[i][j] == '.' and used[belong[ider]] == false)
tmpans += sz[belong[ider]], used[belong[ider]] = true;
/*if (x == 3)
cerr << "Mid-tmpans: " << tmpans << '\n';*//*
if (s[i][j] == '.' and i <= x and j <= K and i >= x-K+1 and j >= 1)
tmpans --;
/*if (x == 3)
cerr << "after-tmpans: " << tmpans << '\n';*//*
// Dl; Dl;
}
}
/*if (x == 3)
Debug();*/
/*if (x == 3)
cerr << tmpans << '\n';*/// 没问题
/*
final_ans = MAX(final_ans, tmpans);
// cerr << "x: " << x << '\n';
// cerr << "大before-ans: " << tmpans << _ << final_ans << '\n';
for (re y = K+1, i, j ; y <= n ; ++ y){// 类似莫队地向右移
// 我觉得我重构一遍比较好，细节太多了
// 我听sandom说了一嘴，我人傻了
// 对阿，我直接扫一遍四个边不就行了，复杂度是对的
// 我囸！
// 仅仅需要把移动一格之后被删的边的点给加上，新加的边的点给减去，然后扫一遍四个框统计外部答案即可
/*dld = 0;
// 最左边被删除的边
j = y - K - 1;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and dld[belong[id(i, j)]] == false and used[belong[id(i, j)]] == false)
dld[belong[id(i, j)]] = true, tmpans -= sz[belong[id(i, j)]];
// 稍微靠左的边
// 首先他变成了自由边之后原来扣掉的要加上
j = y-K;
for (i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.')
tmpans ++;
*/
/*still = 0; dld = 0;
j = y - K;// 稍微靠左的边
for (re i = x-K+1 ; i <= x ; ++ i){
if (s[i][j] == '.')
tmpans ++, still[belong[(i-1)*n + j]] = true;
}
if (x == 3)
cerr << "稍微靠左的边 " << tmpans << '\n', Debug();
// 新的左上角
if (s[x-K][y-K+1] == '.' and
j = y - K - 1;// 被淘汰的左边
for (re i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and still[belong[(i-1)*n + j]] == false)
tmpans -= sz[belong[(i-1)*n + j]], used[belong[(i-1)*n + j]] = false, dld[belong[(i-1)*n + j]] = true;
if (x == 3)
cerr << "被淘汰的左边 " << tmpans << '\n', Debug();
// 左上角
if (s[x-K][y-K] == '.' and still[belong[(x-K-1)*n + y-K]] == false and dld[belong[(x-K-1)*n + y-K]] == false)
tmpans -= sz[belong[(x-K-1)*n + y-K]], used[belong[(x-K-1)*n + y-K]] = false, dld[belong[(x-K-1)*n + y-K]] = true;
if (x == 3)
cerr << "左上角 " << tmpans << '\n', Debug();
// 左下角
if (s[x+1][y-K] == '.' and still[belong[x*n + y-K]] == false and dld[belong[x*n + y-K]] == false)
tmpans -= sz[belong[x*n + y-K]], used[belong[x*n + y-K]] = false, dld[belong[x*n + y-K]] = true;
if (x == 3)
cerr << "左下角 " << tmpans << '\n', Debug();
// 处理好左边了
// 稍微靠右的边
j = y;
for (re i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.')
tmpans --, used[belong[(i-1)*n+j]] = true;
if (x == 3)
cerr << "稍微靠右的边 " << tmpans << '\n', Debug();
// 右上角
if (s[x-K][y] == '.' and used[belong[(x-K-1)*n + y]] == false)
tmpans += sz[belong[(x-K-1)*n + y]], used[belong[(x-K-1)*n + y]] = true;
if (x == 3)
cerr << "右上角 " << tmpans << '\n', Debug();
// 右下角
if (s[x+1][y] == '.' and used[belong[x*n + y]] == false)
tmpans += sz[belong[x*n + y]], used[belong[x*n + y]] = true;
if (x == 3)
cerr << "右下角 " << tmpans << '\n', Debug();
// 最靠右的边
j = y+1;
for (re i = x-K+1 ; i <= x ; ++ i)
if (s[i][j] == '.' and used[belong[(i-1)*n + j]] == false)
tmpans += sz[belong[(i-1)*n + j]], used[belong[(i-1)*n + j]] = true;
if (x == 3)
cerr << "最靠右的边 " << tmpans << '\n', Debug();
// 终于都处理完了
final_ans = MAX(final_ans, tmpans);
Dl; Dl; Dl; Dl; Dl;*//*
}
// cerr << "大after-ans: " << tmpans << _ << final_ans << '\n';
// Dl; Dl; Dl; Dl; Dl;
}*/
// cerr << '\n' << "Final: " << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
国庆のsurprise
\(\text{Su_Zipei is always here}\)
大力分块差分即可。没啥好讲的，但是在出现次数上开数组，挺妙的。
然后查询出现次数的时候直接边更新边查，也比较妙(也可能是因为我比较菜所以觉得妙(
有点卡常，加个火车头
Code
%:pragma GCC target("avx")
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
马八∑
我囸，被卡常了
大样例跑了三秒多
*/
int n, Q, Opt, blocklen=3300, blocknum, final_ans;
int w[N], t[N];
int cnt[33][N];
int a[33][33][N];
inline void Block_Divide(){
blocknum = (n+blocklen-1) / blocklen;
// sleep(10);
// cerr << blocklen << _ << blocknum << '\n';
for (re i = 1 ; i <= blocknum ; ++ i){
int Lf = (i-1) * blocklen + 1, Rt = MIN(n, blocklen*i);
cerr << Lf << _ << Rt << '\n';
for (re j = 1 ; j <= n ; ++ j)
cnt[i][j] = cnt[i-1][j];
for (re j = Lf ; j <= Rt ; ++ j)// 差分
cnt[i][w[j]] ++;
}
for (re l = 1 ; l <= blocknum ; ++ l){
for (re r = l ; r <= blocknum ; ++ r){
for (re col = 1 ; col <= n ; ++ col)
a[l][r][cnt[r][col]-cnt[l-1][col]] ++;
for (re col = 1 ; col <= n ; ++ col)
a[l][r][col] += a[l][r][col-1];
}
}
}
inline int Query(int l, int r, int K){
int res = 0, bl = (l+blocklen-1) / blocklen, br = (r+blocklen-1) / blocklen;
if (br - bl <= 1){
for (re i = l ; i <= r ; ++ i)
t[w[i]] ++, res += (t[w[i]] == K);// 好方法，直接在加入桶的时候查询，不用再扫整个值域了
for (re i = l ; i <= r ; ++ i)
t[w[i]] = 0;
}
else {
res = a[bl+1][br-1][n] - a[bl+1][br-1][K-1];// 差分
int Rtl = bl * blocklen, Lfr = (br-1) * blocklen + 1;
for (re i = l ; i <= Rtl ; ++ i)
t[w[i]] ++, res += ((t[w[i]] + cnt[br-1][w[i]] - cnt[bl][w[i]]) == K);
for (re i = Lfr ; i <= r ; ++ i)
t[w[i]] ++, res += ((t[w[i]] + cnt[br-1][w[i]] - cnt[bl][w[i]]) == K);
for (re i = l ; i <= Rtl ; ++ i)
t[w[i]] = 0;
for (re i = Lfr ; i <= r ; ++ i)
t[w[i]] = 0;
}
return res;
}
inline void work(){
cin >> n >> Q >> Opt;
for (re i = 1 ; i <= n ; ++ i)
cin >> w[i];
Block_Divide();
int l1, r1, K1, l, r, K;
while (Q --){
cin >> l1 >> r1 >> K1;
l = MIN((l1 + final_ans*Opt - 1) % n + 1, (r1 + final_ans*Opt - 1) % n + 1);
r = MAX((l1 + final_ans*Opt - 1) % n + 1, (r1 + final_ans*Opt - 1) % n + 1);
K = (K1 + final_ans*Opt - 1) % n + 1;
if (l > r)
swap(l, r);
// cerr << l << _ << r << _ << K << '\n'; sleep(4);
final_ans = Query(l, r, K);
cout << final_ans << '\n';
}
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(suzipei, a);
#endif
Fastio_setup();
work();
return GMY;
}
CSP-S模拟16
猜道路
这个题大佬们都基本场切了，但是有一个部分分我想说一下。
考虑到他给出的这个矩阵中一部分肯定是作为原边权出现的，那么可以对于上三角矩阵枚举哪些边是作为原边权出现的，选出来跑个 \(\text{Floyd}\)，跑出来再和整个矩阵比较判断是否最短路都一致，相应选择是否更新答案。
考虑到时限有 \(\text{2000ms}\)，可以跑一个随机选边，就不爆搜了。数据小的时候随便跑就行。配合输出 \(-1\) 可以拿到 \(\text{56pts}\) 的好成绩。
正解就不说了。
随机化·$\text{56pts}$
#include <iostream>
#include <ctime>
#include <cstring>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 305
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
不会找环的屑ch_p来写T1
差分约束desu
in fact
这最短路，肯定有一些边是本来就被选上了的
那么就随机选边，跑Floyd验证
但是极限数据下似乎只能随机十次
不对，别说是极限数据了，29%的数据也是n<=300吧
我囸
打这么随机的玩意...真的能行吗...
样例能过，笑死我了((
震惊！大样例跑了甚至80次+！
能拿多少分捏？大约有零分灞
*/
int n;
long long final_ans(1145141145141919810), tmpans;
long long tim;
long long a[N][N], dis[N][N];
inline void Floyd(){
for (re i = 1 ; i <= n ; ++ i){
for (re j = 1 ; j <= n ; ++ j){
if (i == j)
continue;
for (re k = 1 ; k <= n ; ++ k){
if (i == k or j == k)
continue;
if (dis[i][j] > dis[i][k]+dis[k][j])
dis[i][j] = dis[i][k]+dis[k][j];
}
}
}
}
/*
3
0 1 3
1 0 2
3 2 0
*/
inline void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
for (re j = 1 ; j <= n ; ++ j)
cin >> a[i][j];
while (true){
if ((clock()-tim) * 1000 >= 1900 * CLOCKS_PER_SEC)
break;
tmpans = 0; memset(dis, 0x3f, sizeof(dis));
for (re i = 1 ; i <= n ; ++ i)
for (re j = i+1 ; j <= n ; ++ j)
if ((rand() & 3) == 0)
dis[i][j] = dis[j][i] = a[i][j], tmpans += a[i][j];// cerr << i << _ << j << '\n';
Floyd();
/*for (re i = 1 ; i <= n ; ++ i){
for (re j = 1 ; j <= n ; ++ j)
cerr << dis[i][j] << _;
Dl;
}*/
for (re i = 1 ; i <= n ; ++ i)
for (re j = i+1 ; j <= n ; ++ j)
if (dis[i][j] != a[i][j])
{tmpans = 1145141145141919810; break;}
final_ans = MIN(final_ans, tmpans);
// Dl; Dl; Dl;
// cerr << "胡萝贝" << '\n';
}
if (final_ans == 1145141145141919810)
cout << -1 << '\n';
else
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
tim = clock();
srand(time(0));
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
正解
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 305
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
*/
int n;
long long final_ans;
char deleted[N][N];
long long a[N][N];
inline void Floyd(){
for (re k = 1 ; k <= n ; ++ k){
for (re i = 1 ; i <= n ; ++ i){
if (i == k)
continue;
for (re j = 1 ; j <= n ; ++ j){
if (j == i or j == k)
continue;
if (a[i][j] > a[i][k]+a[k][j])
goto CANT;
if (a[i][j] == a[i][k]+a[k][j])
deleted[i][j] = deleted[j][i] = true;
}
}
}
return ;
CANT:{cout << -1 << '\n'; exit(0);}
}
inline void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
for (re j = 1 ; j <= n ; ++ j)
cin >> a[i][j];
Floyd();
for (re i = 1 ; i <= n ; ++ i)
for (re j = i+1 ; j <= n ; ++ j)
if (deleted[i][j] == false)
final_ans += a[i][j];
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
2022NOIPA层联测3 10月5日
\(\text{C}\)
整个歪解，从低到高依次确定答案。
首先任何数异或 \(0\) 等于他本身，所以第一位答案就直接找到整个序列中字典序最小的字母，然后把这个字母所在的所有位置作为『候选的 \(k\)』扔到一个数组里。
然后确定第二位，把候选的 \(k\) 们依次异或出的位置中，选出该位置字符字典序最小的那一个，并将所有能得到这个字符的 \(k\) 们再次扔到数组里，类似的确定更高位直到『候选的 \(k\)』只剩一个或答案已经确定完毕。(应该等到『候选的 \(k\)』只剩一个了就可以 break 了？)
Code
#pragma GCC optimize(2)
#include <iostream>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define DMARK cerr << "###"
#define _ ' '
#define Endl cout << '\n'
#define Dl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define NN 262155
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
一个一个地选，选出“值得我枚举的k”，一直选直到只剩一个k。
*/
int n, mn;
char str[NN], ans[NN];
int a[NN], tmp[NN], s[NN];
/*
2
acba
3
bcbaaabb
*/
inline void work(){
cin >> n; n = (1 << n) - 1;
cin >> str;
for (re i = 0 ; i <= n ; ++ i)
s[i] = (int)str[i];
// 第一次选是0，0^k = k，所以第一次只需要找出来整个序列里字典序最小的字母即可
mn = 1145141919;
for (re i = 0 ; i <= n ; ++ i)
if (s[i] < mn)
mn = s[i];
for (re i = 0 ; i <= n ; ++ i)
if (s[i] == mn)
a[++ a[0]] = i;
/*cerr << (char)mn << _ << a[0] << '\n';
cerr << "a[i]: ";
for (re i = 1 ; i <= a[0] ; ++ i)
cerr << a[i] << _;
Dl;*/
for (re i = 1 ; i <= n ; ++ i){
if (a[0] == 1)
break;
// cerr << i << '\n';
mn = 1145141919; tmp[0] = 0;
for (re j = 1 ; j <= a[0] ; ++ j)// cerr << "s[a[j]^i]: " << (char)s[a[j]^i] << '\n';
if (s[a[j] ^ i] < mn)
mn = s[a[j] ^ i];
for (re j = 1 ; j <= a[0] ; ++ j)
if (s[a[j] ^ i] == mn)
tmp[++ tmp[0]] = a[j];
// cerr << "repmn:|" << (char)mn << '\n';
a[0] = tmp[0];
for (re j = 1 ; j <= tmp[0] ; ++ j)
a[j] = tmp[j];
// Dl; Dl; Dl;
}
// cerr << a[0] << _ << a[1] << '\n';
for (re i = 0 ; i <= n ; ++ i)
ans[i] = str[i^a[1]];
cout << ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}