本文共 8878 字,大约阅读时间需要 29 分钟。
A
题目大意
找到到达中心需要的步数
题解
直接与中心坐标作比较即可
#includeusing namespace std;int px,py;int main(){ for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ int x; cin>>x; if(x){ px=i,py=j; } } } cout< <
B
题目大意
想要打败怪兽,给你初始水平n 然后没打败一个怪兽,你可以增加对应的bonus 如果你被打败了就GG
题解
刚开始用map做,wa了几发,然后一想到怪兽的等级是可以相同的,我不能去重,所以改用vector 通过对first值进行从小到大的排序 然后遍历一遍 打得过就一直打 打不过跳出循环输出NO
#includeusing namespace std;vector > vec;int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; while(cin>>n>>m){ for(int i=0;i >x>>y; vec.push_back(make_pair(x,y)); } sort(vec.begin(),vec.end()); int ff=1; for(int i=0;ff&&i vec[i].first) n+=vec[i].second; else ff=0; } if(ff) cout<<"YES"<
C
题目大意
三个人对于某一个问题,如果有两个人以上做出来了,就会写题解,计算题解的个数
题解
直接遍历一遍就是了,判断每一行1的个数是否大于1
#includeusing namespace std;const int maxn=1e3+10;int n,mp[maxn][10];int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin>>n){ int cnt=0; for(int i=0;i >x; if(x) ++ans; if(ans>=2){ ++cnt; ans=0; } } } cout< <
D
题目大意
给出n个点的横纵坐标,问至少再加几个点可以使得所有的点之间可以通过上下左右走互相到达
题解
其实就是看你能求出多少个连通块 需要的点数等于连通块数-1
并查集实现思路:两个点横或纵坐标相同就join,然后统计连通块的个数
dfs搜索思路:从每个点开始搜,直到所有点访问完为止,搜一遍就代表一个连通块 然后结果和并查集是一样的
并查集实现
#includeusing namespace std;const int maxn=100+10;int pre[maxn];int cnt;struct node{ int x,y;}stu[maxn];int find_pre(int x){ if(x!=pre[x]) pre[x]=find_pre(pre[x]); return pre[x];}void join(int x,int y){ int a=find_pre(x); int b=find_pre(y); if(a!=b) pre[a]=b;}int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; while(cin>>n){ cnt=0; for(int i=1;i<=n;i++) pre[i]=i; for(int i=1;i<=n;i++) cin>>stu[i].x>>stu[i].y; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(stu[i].x==stu[j].x||stu[i].y==stu[j].y){ join(i,j); } } } for(int i=1;i<=n;i++){ if(pre[i]==i) ++cnt; } cout< <
dfs实现
#include#define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=100+10;int pre[maxn];int cnt,n;struct node{ int x,y;}stu[maxn];bool vis[maxn];void dfs(int t){ vis[t]=true; for(int i=1;i<=n;i++){ if(!vis[i]&&(stu[t].x==stu[i].x||stu[t].y==stu[i].y)){ dfs(i); } }}int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin>>n){ cnt=0; mst(vis,false); for(int i=1;i<=n;i++) cin>>stu[i].x>>stu[i].y; for(int i=1;i<=n;i++){ if(!vis[i]){ dfs(i); ++cnt; } } cout< <
E
题目大意
让你求从位置1开始是否能到达你想要达到的位置
题解
直接遍历一遍,注意最后一个数要为一个大于0的数
#includeusing namespace std;const int maxn=3e4+10;int a[maxn],n,t;int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>t; for(int i=1;i<=n-1;i++) cin>>a[i]; a[n]=0x3f; int ff=0; int i=1; while(i<=n){ if(i==t){ ff=1; break; } i+=a[i]; } if(ff) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; return 0;}
F
题目大意
有n个boy,m个girl,每个人都有自己的舞蹈技术等级,现规定只有boy和girl的等级相差不大于1才能构成一对舞伴,在每个人都不重复的情况下,问最多能构成多少对?
题解
解法一: 贪心。把两个数组都从小到大排序,再依次用当前最小的去跟对方比,若符合条件,则双方下标都++;若自己太低,则自己下标++,否则对方下标++。
#includeusing namespace std;const int maxn=100+10;int b[maxn],g[maxn];int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n; for(int i=1;i<=n;i++) cin>>b[i]; cin>>m; for(int j=1;j<=m;j++) cin>>g[j]; sort(b+1,b+1+n); sort(g+1,g+1+m); int i=1,j=1; int ans=0; while(i<=n&&j<=m){ if(abs(b[i]-g[j])<=1){ i++; j++; ++ans; } else if(b[i]>g[j]) j++; else i++; } cout< <
解法二: 二分图最大匹配问题。 (匈牙利算法—邻接表+DFS)
#includeusing namespace std;const int MAXN = 100+10; // 点数的最大值const int MAXM = 11000; // 边数的最大值struct Edge{ int to, next;} edge[MAXM];int head[MAXN], tot;void init(){ tot = 0; memset(head, -1, sizeof(head)); return ;}void addedge(int u, int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; return ;}int linker[MAXN];bool used[MAXN];int uN,vN;bool dfs(int u){ for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false;}int hungary(){ int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 0; u < uN; u++) // 点的编号0~uN-1 { memset(used, false, sizeof(used)); if (dfs(u)) { res++; } } return res;}int main(){ init(); int a[MAXN]; int b[MAXN]; cin>>uN; for(int i=0;i >a[i]; cin>>vN; for(int i=0;i >b[i]; for(int i=0;i
解法三: 二分图最大匹配问题。 (匈牙利算法—邻接矩阵+DFS)
#includeusing namespace std;const int maxn=100+10;int uN, vN; // u,v的数目,使用前面必须赋值int g[maxn][maxn]; // 邻接矩阵int linker[maxn];bool used[maxn];int a[maxn];int b[maxn];bool dfs(int u){ for (int v = 0; v < vN; v++) { if (g[u][v] && !used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false;}int hungary(){ int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 0; u < uN; u++) { memset(used, false, sizeof(used)); if (dfs(u)) { res++; } } return res;}int main(){ cin>>uN; for(int i=0;i >a[i]; cin>>vN; for(int i=0;i >b[i]; for(int i=0;i
G
题目大意
个数,就是输入的第一个数,让它变成第二个数最少用几步。可以点红色按钮,蓝色按钮来改变数字,红色:*2,蓝色:-1,如果变成负数,就变成原来的数
题解
贪心的思想:其实如果m比n大 ,n肯定有*2,问题就是先减再乘还是先乘再减。这是正常人的思路
但是反过来推,如果m是奇数,一定是减一造成的,如果是偶数,更快的办法是*2造成的。就这么寻欢做下去知道遇到m=n
#includeusing namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; int ans=0; while(n
H
题目大意
给一个n*m的矩阵,用B和W填充‘.’,且相邻的位置不可以相同
题解
解法一: 规律:若当前位置为’.’,就i + j 时为奇数时输出W,反之输出B;若当前位置为’-’,直接输出
#includeusing namespace std;const int maxn=100+10;char mp[maxn][maxn];int main(){ int n,m; cin>>n>>m; for(int i=0;i >mp[i]; for(int i=0;i
解法二: dfs搜一下,染色法
#includeusing namespace std;const int maxn=100+10;char mp[maxn][maxn];int n,m;bool vis[maxn][maxn];int dx[]={ 1,0,-1,0};int dy[]={ 0,-1,0,1};bool check(int x,int y){ if(x>=0&&x =0&&y >n>>m; memset(vis,false,sizeof(vis)); for(int i=0;i >mp[i]; for(int i=0;i
I
题目大意
地图是一棵树,从根(点1)出发,要到叶子去,路上连续有m个点有猫的路不走,求有多少路可以走
题解
在dfs深搜时,我们记录每个结点的度数,只要能到达叶子结点,那么就是一条可求路径 然后如果出现了连续的m个猫 那么我们就结束搜索 改搜另一条路
#includeusing namespace std;const int maxn=1e5+10;int n,m,cnt;vector vec[maxn];int isleaf[maxn];bool vis[maxn];int iscat[maxn];void init(){ cnt=0; for(int i=0;i<=n;i++) { isleaf[i]=0; vis[i]=false; vec[i].clear(); }}void add_Edge(int u,int v){ isleaf[u]++; isleaf[v]++; vec[u].push_back(v); vec[v].push_back(u);}void dfs(int t,int cat){ if(vis[t]) return; else vis[t]=true; if(iscat[t]) cat++; else cat=0; if(cat>m) return; if(isleaf[t]<2&&t!=1) ++cnt; for(int i=0;i >n>>m; init(); for(int i=1;i<=n;i++) cin>>iscat[i]; for(int i=1;i<=n-1;i++){ int u,v; cin>>u>>v; add_Edge(u,v); } dfs(1,0); cout< <
J
题目大意
n 个学生,每个学生都说是另一个学生做的坏事,老师从第 i 个学生的话开始向下寻找,直到第二次找到这个学生为止
题解
直接模拟就行
#include#define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=1e4+10;int n,a[maxn];int num[maxn];int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ mst(num,0); int tmp=i; while(1){ num[tmp]++; tmp=a[tmp]; if(num[tmp]==2) break; } cout< <<" "; } cout<
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/100702022 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!