赞
踩
传送门
这题在一开始做了一个不必要的担心,我怕数据太多调用dfs会超时;自作聪明”另辟蹊径“,自创了一个简短的判断,其实逻辑是很不严谨的,这里把错误的代码贴上来,作为错误示范。
#include<iostream> #include<algorithm> #include<queue> #include<vector> using namespace std; int n, m, k; int att[505];//att[i]=x->攻击城市x int done[505];//done[i]=1->城市i已失去 vector<int> e[505]; int main(){ scanf("%d%d", &n, &m); while(m--){ int a, b; scanf("%d%d", &a, &b); e[a].push_back(b); e[b].push_back(a); } scanf("%d", &k); for (int i = 0; i < k; i++) scanf("%d", att + i); for (int i = 0; i < k; i++){ int u = att[i]; int flag = 0;//flag=1->打破连通性 done[u] = 1; for (int j = 0; j < e[u].size(); j++){ if(e[u].size()==1) continue;//城市u本来也只联系着一个城市,攻占了以后并不影响连通性 int v = e[u][j]; if(!done[v]){ int jud = 0;//jud=0->城市v失去连通性 for (int k = 0; k < e[v].size(); k++){ int tem = e[v][k]; if(!done[tem]){ jud= 1; } } if(!jud) flag = 1; } } if(flag) printf("Red Alert: City %d is lost!\n", u); else printf("City %d is lost.\n", u); } if(n==k) printf("Game Over.\n"); return 0; }
其实就是每攻占一个城市之后,重新统计一下连通分块,暴力就完事了。
#include<iostream> #include<algorithm> using namespace std; int n, m, k; int cnt, pre; int dis[505][505]; int vis[505]; int att[505]; void dfs(int u){ vis[u] = 1; for (int i = 0; i < n; i++) if(!att[i] && !vis[i] && dis[u][i]) dfs(i); } int count(){ int c = 0; for (int i = 0; i < 505; i++) vis[i] = 0; for (int i = 0; i < n; i++){ if(!att[i] && !vis[i]){ dfs(i); c++; } } return c; } int main(){ scanf("%d%d", &n, &m); for (int i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); dis[u][v] = dis[v][u] = 1; } scanf("%d", &k); pre = count(); for (int i = 0; i < k; i++){ int x; scanf("%d", &x); att[x] = 1; cnt = count(); if(cnt > pre) printf("Red Alert: City %d is lost!\n",x); else printf("City %d is lost.\n", x); pre = cnt; } if(k==n) printf("Game Over.\n"); return 0; }
传送门
很快就读懂了题目,于是去找一共能分出几个上升子序列,第一次提交,两个测试点超时。想了一下数据的极端情况,就是列车序号有可能刚好颠倒过来,所以我又加了一个判断,提交之后还剩一个测试点超时。我就知道我这个笨方法是不行的,虽然拿了一部分的分数。
#include<iostream> #include<algorithm> using namespace std; int n, p, cnt, minn; int en[100005]; int vis[100005]; int main(){ scanf("%d", &n); minn = 1; for (int i = 0; i < n; i++) scanf("%d", en + i); for (int i = 0; i < n; i++){ if(!vis[i]){ cnt++; p = i; vis[i] = 1; if(en[i]==minn){ minn++; continue; } for (int j = i + 1; j < n; j++){ if(en[j]<en[p] && !vis[j]){ vis[j] = 1; p = j; if(en[j]==minn){ minn++; break; } } } } } printf("%d\n", cnt); return 0; }
!!!我翻了一些题解,这是我见过最厉害的。利用set来解决。大致思路:在遍历列车序号的时候,如果某趟列车的序号小于当前队列中的队尾序号,那就将该列车加入对尾;如果不行,就需要再加一条轨道。当然,每条轨道,我们只要记录队尾列车的序号即可,当一个新的列车加入时,我们可以把之前的序号删除,加入这个新的序号。利用set,遍历时如果有某趟列车的序号,小于set末的序号(最大值),则将set末的序号删除,加入这个新序号。否则则将这个序号插入到set中(按从小到大的顺序)。这样在所有列车遍历完的时候,set中还剩几个序号,即需要几条轨道。
#include<iostream> #include<set> using namespace std; int n, t; set<int> s; int main(){ scanf("%d", &n); s.insert(0); for (int i = 0; i < n; i++){ scanf("%d", &t); if(t<*s.rbegin()) s.erase(*(s.upper_bound(t))); s.insert(t); } printf("%d\n", s.size()-1); return 0; }
传送门
甚至都不用结构体,每次计算好加权平均值之后存放到一个数组里,然后都数组排序就行。
#include<iostream> #include<algorithm> using namespace std; int n, k, m; double goal[12]; double ans[10004]; int main(){ scanf("%d%d%d", &n, &k, &m); for (int i = 0; i < n; i++){ for (int j = 0; j < k; j++) scanf("%lf", goal + j); sort(goal, goal + k); for (int j = 1; j < k - 1; j++) ans[i] += goal[j]; ans[i] /= (k - 2); } sort(ans, ans + n); printf("%.3lf", ans[n - m]); for (int i = n - m + 1; i < n; i++) printf(" %.3lf", ans[i]); return 0; }
传送门
一道dfs,被我用bfs折腾了半天,而且被我忽略的时没有标记父母的性别(这话好像有点怪,但在记录每个人的父母的时候,电脑确实时不知道这两个人的性别的,虽然我很清楚)。以后做题,一定一定要先想好,到底用dfs还是bfs,不要一开始就选错了方向。
补题时犯的错:要给父母数组初始化-1,不然月老来了两个人也走不到一起。
#include<iostream> #include<algorithm> using namespace std; const int N = 100005; int n, k; int ba[N], ma[N]; char sex[N]; int jud(int a, int b, int cnt){ if(a==-1 && b==-1) return 1; if(ma[a]!=-1&&ma[a]==ma[b] || ba[a]!=-1&&ba[a]==ba[b]) return 0; cnt++; if(cnt >= 4) return 1; return jud(ma[a], ma[b], cnt) && jud(ba[a], ba[b], cnt) && jud(ba[a], ma[b], cnt) && jud(ma[a], ba[b], cnt); } int main(){ scanf("%d", &n); for (int i = 0; i < N; i++) ba[i] = ma[i] = -1; for(int i=0; i<n; i++){ int id; scanf("%d", &id); getchar(); scanf("%c%d%d", sex + id, ba + id, ma + id); sex[ba[id]] = 'M'; sex[ma[id]] = 'F'; } // printf("\n"); // for (int i = 0; i < n; i++) // printf("%c %d %d\n",sex[i], ba[i], ma[i]); scanf("%d", &k); while(k--){ int a, b; scanf("%d%d", &a, &b); if(sex[a]==sex[b]) printf("Never Mind\n"); else{ if(jud(a,b,0)) printf("Yes\n"); else printf("No\n"); } } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。