东北林业大学ACM实验室清明个人赛总结

这次比赛不是很理想应该说除了G题都会写但是最后还是只过了3个题我认为还是心态有问题第一题出题人数据出错了导致心态就有点爆炸以后不能这样了。。。#includebits/stdc.h using namespace std; const int N1e510; int a[N]; int res1,res2; int n; int main() { cinn; int mi1e9,ma0; int pos1,pos2; for(int i1;in;i) { cina[i]; if(maa[i]) { maa[i]; pos1i; } if(mia[i]) { pos2i; mia[i]; } } res1ma-mi; if((pos11pos2n)||(pos1npos21)) { mi1e9,ma0; for(int i2;in;i) { mamax(ma,a[i]); mimin(mi,a[i]); } res2ma-mi; mi1e9,ma0; for(int i1;in;i) { mamax(ma,a[i]); mimin(mi,a[i]); } res2max(res2,ma-mi); } else res2res1; coutres1 res2endl; return 0; }这应该是一个动态规划问题不知道为什么我一开始看错了以为能像贪吃蛇那样转弯用BFS写了半天气死了气死了总的来说动态规划还是太菜了还得练。这个题的状态划分就是col[i][j]表示末尾在第i行第j列的线段的最大长度row[i][j]就是行.....看代码吧#includebits/stdc.h using namespace std; const int N1010; int a[N][N]; int col[N][N],row[N][N]; int n,m; int main() { cinnm; for(int i1;in;i) { for(int j1;jm;j)cina[i][j]; } int res1; for(int i1;in;i) { for(int j1;jm;j) { col[i][j]1; row[i][j]1; if(i1a[i][j]a[i-1][j]) { row[i][j]row[i-1][j]1; resmax(res,row[i][j]); } if(j1a[i][j]a[i][j-1]) { col[i][j]col[i][j-1]1; resmax(res,col[i][j]); } } } coutresendl; return 0; }想要明氏距离与p的值无关只能是两个绝对值其中有一个为零或者两个都为零但是题目中说不存在两个相同的点所以只存在一个一个绝对值为零的情况用cnt数组存一下就能轻松解决了而且还有一点需要注意cnt数组并不能直接用数组因为x和y能到1e9会爆掉所以要用unordered_map存还有就是x,y要初始化为longlong看代码吧#includebits/stdc.h using namespace std; typedef long long LL; unordered_mapLL,LLcnt1; unordered_mapLL,LLcnt2; int n; LL res; int main() { cinn; for(int i1;in;i) { LL x,y; cinxy; rescnt1[x]cnt2[y]; cnt1[x]; cnt2[y]; } coutresendl; return 0; }这个题乍一看很吓人但是仔细一看R-L10000,那么算上步骤1000也只有1e7的复杂度完全是够用的哈哈哈坑没有认真读题的人但是注意的是数据最好还是有用longlong不然就又又又又又又WA了#includebits/stdc.h using namespace std; typedef long long LL; int main() { LL l,r; cinlr; int resl; int step0; for(LL ir;il;i--) { LL xi; int sp0; while(x!1) { if(x%2)xx*31; else x/2; sp; } //coutspendl; if(spstep) { stepsp; resi; } } //coutstependl; coutresendl; return 0; }这个题我比赛时用的是树的一个广搜如果搜到相同的节点自身除外那么就可以返回true了但是但是我现在回想起来代码写的非常不好都已经3e10的复杂度了居然过了#includebits/stdc.h using namespace std; const int N1e501,M2e510; int e[M],ne[M],h[N],idx; int n,m; bool st[N]; void add(int a,int b) { e[idx]b,ne[idx]h[a],h[a]idx; } bool f(int x) { queueintq; q.push(x); while(q.size()) { int tq.front(); q.pop(); for(int ih[t];i!-1;ine[i]) { int je[i]; if(st[j])return false;//存在多条路从一个点通向另一个点 if(jx)continue; st[j]true; q.push(j); } } return true; } int main() { cinnm; memset(h,-1,sizeof h); for(int i1;im;i) { int a,b; cinab; add(a,b); } bool flagtrue; for(int i1;in;i) { memset(st,false,sizeof st); if(f(i)) { continue; } else { flagfalse; break; } } if(!flag)coutYesendl; else coutNoendl; return 0; }因此我修改了一下并提供了多种解决方案BFS版#includebits/stdc.h using namespace std; const int N2e510; int e[N],ne[N],h[N],idx; int n,m; bool st[N]; void add(int a,int b) { e[idx]b,ne[idx]h[a],h[a]idx; } bool bfs(int u) { queuepairint,intq; q.push({u,-1}); st[u]true; while(q.size()) { auto tmpq.front(); q.pop(); int ttmp.first,fatmp.second; for(int ih[t];i!-1;ine[i]) { int je[i]; if(jfa)continue; if(st[j])return true; st[j]true; q.push({j,t}); } } return false; } int main() { cinnm; memset(h,-1,sizeof h); for(int i1;im;i) { int a,b; cinab; add(a,b),add(b,a); } bool flagfalse; for(int i1;in;i) { if(!st[i]bfs(i)) { flagtrue; break; } } if(flag)coutYesendl; else coutNoendl; return 0; }DFS版#includebits/stdc.h using namespace std; const int N2e510; int e[N],ne[N],h[N],idx; int n,m; bool st[N]; void add(int a,int b) { e[idx]b,ne[idx]h[a],h[a]idx; } bool dfs(int u,int fa) { st[u]true; for(int ih[u];i!-1;ine[i]) { int je[i]; if(jfa)continue; if(st[j])return true; if(dfs(j,u))return true; } return false; } int main() { cinnm; memset(h,-1,sizeof h); for(int i1;im;i) { int a,b; cinab; add(a,b),add(b,a); } bool flagfalse; for(int i1;in;i) { if(!st[i]dfs(i,-1)) { flagtrue; break; } } if(flag)coutYesendl; else coutNoendl; return 0; }并查集版我突然发现用并查集写其实是最简单的hh只要判断是不是同一个跟节点就可以了。#includebits/stdc.h using namespace std; const int N1e510; int p[N],n,m; int find(int x) { if(x!p[x]) p[x]find(p[x]); return p[x]; } int main() { cinnm; for(int i1;in;i)p[i]i; bool flagfalse; while(m--) { int a,b; cinab; int xfind(a),yfind(b); if(xy) { flagtrue; break; } p[x]y; } if(flag)coutYesendl; else coutNoendl; return 0; }剩下的F题其实就是最简单的了#includebits/stdc.h using namespace std; int main() { int cnt0; int n; cinn; for(int i1;in;i) { string s; cins; if(spush)cnt; if(stopcnt0) { coutNoendliendl; return 0; } if(spop) { if(cnt0) { coutNoendliendl; return 0; } cnt--; } if(sclear)cnt0; } coutYesendlcntendl; return 0; }