高端题解：你见过带无聊日志的题解吗（）
2026-03-01 12:10:27
发布于：浙江
16阅读
0回复
0点赞
/*
题目：洛谷P10379 [GESP202403 七级] 俄罗斯方块
日志：
一开始我就卡在了一个问题上：存连通块该如何存。主要原因是我就算只拿30%的分最大5*5的俄罗斯方块也有31亿种（搜的），so卡住了qwp。老师问我：“what are you thinking about？”，
我很降智的回答说“I'am thinking about how to do this question”。老师was very angry，和我辩驳七七四十九世纪（），最终我猛然发觉我回答了一句废话给老师74了（）
实际情况是最大20*20的图撑死就400种选项，根本不会有31亿种......
然后我开始思考如何存这份联通图awa，我一开始认为应该直接用二维数组硬存整个图，然后猛然醒悟（被点了）（悲）根本不好存（谁家好人存在下标负数格awa），主要原因是无法确定存在最左上角的每个值的下标（悲）
因为搜连通图我们会awa，so我们要解决的核心问题是两点：1.能存下整个连通块的信息 2.能快速比较两个连通块
然后画了图后又猛然发觉（还是被点了）（悲）拿dfs搜同样的连通块肯定是一个顺序qwp，按遍历顺序存块内每个点的下标即可awa，最后对比时将两个块每个块内首个点的的下标一二互减求出差值即可实现大家小学二年级
就学过的平移对比效果awa（例：样例中6号块的下标各自为[2,4][3,4][2,5][1,5]（我存的方法）,7号块为[4,4][5,4][4,5][3,5]，由两者第一个可求出x差为2，y差为0，后面的x-2，y-0后值相等即可）
再会发现，以这种方法存按每个和前面的每个对比会发现时间复杂度在n,m为最大500的情况下最大需要遍历nm即500^2次，而每次对比还要最多对比其中的500个元素，还要再乘上500，则时间复杂度为最大
O(500nm)(不省去常数awa)，nm最大为500，则可得最大时间复杂度会飙到500^3，及其的离谱（qwp），所以可以优化一下awa
结合上面dfs搜连通块一定是按照同样的顺序搜的awa，可以得出在搜同样的连通块时dfs按序遍历的方向是一定一样的，但也不一定，如样例中的6号连通块的遍历顺序如果从最上面一层最左侧（2,4）的位置开始按我的顺序
遍历则为下，左，右（可以猜猜什么顺序awa），而同样的顺序T字型从最中间的最上层搜也是同样的结果（我知道实际情况不回从那里开始搜，只是举个例子qwp），而单单换顺序无法解决这个问题awa，所以我们还要应用一种dfs
的运算逻辑：回溯-在遍历完以后会按一定顺序回溯回去，而不难求证（并非不难qwp），加上回溯的逆顺序后结合其顺序是绝对不会出现不同连通块顺序重复的问题的qwp，即可氢悚通过存在一个string类型中记录（例如左上右
下对应0123），然后利用无序set（unordered_set，我还忘了这叫啥去搜了一下）相同值只有一个的特性每次搜索完后存入无序set中保证相同顺序只有一个，最后用size()搜索set中的类型数量即可解决这道氢悚舰丹的
题目awa，无序set O（1）的搜索时间复杂度可以支持最大500的平方的时间复杂度qwp，代码如下：
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
int n,m,a[N][N],cnt,c1,c2;
bool vis[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
string s;
unordered_set<string> um;
void dfs(int sx,int sy,int num,int l){
if(vis[sx][sy]==1){
return;
}
if(sx<1||sx>n||sy<1||sy>m||a[sx][sy]!=num){
return;
}
vis[sx][sy]=1;
for(int i=0;i<4;i++){
int f;
switch(i){
case 0:f=0;
case 1:f=1;
case 2:f=2;
case 3:f=3;
}
s+='0'+f;
dfs(sx+d[i][0],sy+d[i][1],num,f);
}
int f=(l+2)%4;
s+='0'+f;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]){
s="";
dfs(i,j,a[i][j],-1);
um.insert(s);
}
}
}
cout<<um.size();
}
有帮助，赞一个