首页 > 代码库 > 日照学习提高班day3测试 x
日照学习提高班day3测试 x
思路:
一看到‘#‘‘.‘什么的就想到搜索怪我怪我。。。
这道题勉强说是搜索别打我qwq
1）因为不重复，所以首先要判断是否%5==0，若不满足，直接输出NO
2）弄个vis数组记录是否被搜过，如果该处是‘#’并且没有被搜索过，就搜索他正下，左下，右下，以及下下是否都为#，若不是，输出NO
3）如果是就进行标记（5个点都进行标记，因为只能使用一次），最终如果成功的渡劫，输出YES
坑点:
搜索下方是x+1而不是x-1（吃亏了qwq）
上代码:
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std;int n,cnt,tot;char w[110][110];bool vis[110][110];int dx[4] = {0, 0,1,-1}, dy[4] = {1,-1,0, 0};bool check(int x,int y){ if(x>n || x<1 || y>n || y<1 || vis[x][y]) return false; return true;}void dfs(int x,int y){ for(int i=0;i<4;++i) { int xx=x+dx[i],yy=y+dy[i]; if(!check(xx,yy)) continue; if(w[xx][yy]==‘#‘) tot++; }}void dfs2(int x,int y){ for(int i=0;i<4;++i) { int xx=x+dx[i],yy=y+dy[i]; vis[xx][yy]=true; }}bool orz(int x,int y){ vis[x+1][y]=true; tot=0; dfs(x+1,y); if(tot==4) { dfs2(x+1,y); return true; } return false;}int main(){ freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",w[i]+1); for(int j=1;j<=n;++j) if(w[i][j]==‘#‘) ++cnt; } if(cnt%5) { printf("NO"); return 0; } else if(!cnt) { printf("YES"); return 0; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(w[i][j]==‘#‘ && !vis[i][j]) { if(!orz(i,j)) { printf("NO"); return 0; } } printf("YES"); return 0;}
思路:
题目大整容!!!
luoguP2816宋荣子搭积木
贪心。
1）先将所有的盒子按照承载量从小到大排序
2）然后我们开一个数组，记录一下当前一共有多少列，每一列一共有多少个盒子。
3）接着从小到大扫描所有的盒子，找到能放下的数量最多的列，把它放进去。
4）如果没有任何一列能放下，则建一个新列。
上代码:
#include <algorithm>#include <iostream>#include <cstdio>using namespace std;const int Maxn = 5e3 + 233;int n,tot;int a[Maxn],b[Maxn];inline void works(){ for(int i=1;i<=n;++i) if(!tot)///创造新列 b[++tot]=1; else {///Maxx用来记录上面放了多少块积木 int Maxx=0,flag=0; for(int j=1;j<=tot;++j) if(a[i]>=b[j] && b[j]>Maxx) Maxx=b[j],flag=j; if(!flag)///若积木不高兴了 b[++tot]=1;///再建一个列 else///装入该列 b[flag]++; } cout<<tot;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+1+n);///记住一定要进行排序!!毕竟贪心嘛,,, works(); return 0;}
思路:
题目大整容！
luoguP1525关押罪犯
三种做法
1)普通并查集:
i表示第i个学生，i+n为虚拟节点，表示不能和i在一个宿舍的人
若两个点在同一并查集中，说明它们必须被分到同一个宿舍楼
然后将所有的爱慕关系从大到小排序
若a和b在同一并查集中，则此时c为答案
若不在同一并查集，令a与b+n所在并查集合并，b与a+n所在并查集合并
2)加权并查集：
同样将所有爱慕关系从大到小排序
每个点存储额外信息type，type为0表示和父亲结点在同一个宿舍楼，1表示和父亲结点不在同一个宿舍楼
合并与查询的方式类似食物链
3)二分+dfs：
二分答案
对于比二分答案大的爱慕关系，建图，
显然若该图可以黑白染色，该答案可行，反之不可行
上代码:
给出普通并查集做法哦~
#include <algorithm>#include <iostream>#include <cstdio>using namespace std;int n,m,dad[40010];struct node { int a,b,c; bool operator < (const node &qwq)const {///重载运算符 return c > qwq.c; }}e[100010];int getdad(int x){return x == dad[x] ? x : dad[x]=getdad(dad[x]);}int main(){ freopen("love.in","r",stdin); freopen("love.out","w",stdout); scanf("%d %d",&n,&m); for(int i=1;i<=n*2;i++) dad[i]=i;///构建虚拟点 for(int i=1;i<=m;i++) scanf("%d %d %d",&e[i].a,&e[i].b,&e[i].c); sort(e+1,e+1+m); for(int i=1;i<=m;i++) { int f1=getdad(e[i].a),f2=getdad(e[i].b); if(f1==f2) { printf("%d",e[i].c); return 0; } ///与虚拟点进行合并，表示不再一个宿舍中 dad[f1]=getdad(e[i].b+n);///将f1与 b的补集合并 dad[f2]=getdad(e[i].a+n);///将f2与 a的补集合并 } ///若合法: printf("0"); return 0;}
日照学习提高班day3测试 x