Codeforces Round #368 (Div. 2)
有一个n*m的字符矩阵表示一张图片,每个字符表示一个像素,可能包含'C', 'M', 'Y', 'W', 'G' or 'B'这些字符,每个字符都代表一种颜色,问这张图片是是彩色的还是黑白(只包含黑'B'白'W')的;
水题,但是不明白为什么那么多人被hack了;
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define N 202550 #define PI 4*atan(1.0) #define mod 100000001 #define met(a, b) memset(a, b, sizeof(a)) typedef long long LL; int main() { int n, m, flag = 0; scanf("%d %d", &n, &m); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { char s[5]; scanf("%s", s); if(s[0] != 'W' && s[0]!='B' && s[0]!='G') flag = 1; } } if(flag) puts("#Color"); else puts("#Black&White"); return 0; }
B.Bakery
有n个城市m条路以及k个供货商,m条路是城市a到城市b的距离是L,有k个供应商分布在城市b[i],b[i+1]...b[i+k];
现在要建立一个店,这个店不能建立在有供应商的地方,也不能建立在一个不能到达任何供应商的城市;最后求所需经费最少是多少,经费相当于商店到供应商的距离;
在城市i建商店,那么要想费用最少,那么城市i一定有与i直接相连的供应商,所以只需求最短的既可以了;
直接建图,暴力搜索即可时间复杂度相当于O(n);
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<math.h> #include<vector> using namespace std; #define INF 0x3f3f3f3f #define N 102550 #define PI 4*atan(1.0) #define mod 100000001 #define met(a, b) memset(a, b, sizeof(a)) typedef long long LL; struct node { int v; LL w; node(){}; node(int v, LL w): v(v), w(w){} }; vector<vector<node> >G; int b[N]; LL solve(int s) { LL ans = 10000000000000000; int len = G[s].size(); for(int i=0; i<len; i++) { node p = G[s][i]; if(b[p.v]) { ans = min(ans, p.w); } } if(ans == 10000000000000000)ans = -1; return ans; } int main() { int n, m, k, num; scanf("%d %d %d", &n, &m, &k); G.clear(); G.resize(n+5); met(b, 0); for(int i=1; i<=m; i++) { int u, v; LL w; scanf("%d %d %I64d", &u, &v, &w); G[u].push_back(node(v, w)); G[v].push_back(node(u, w)); } for(int i=1; i<=k; i++) { scanf("%d", &num); b[num] = 1; } LL ans = 10000000000000000;///最大值注意不能用0x3f3f3f3f; for(int i=1; i<=n; i++) { if(b[i]==1)continue;///供应商不能建; LL num = solve(i);///找到与该城市最近的供应商; if(num != -1) ans = min(ans, num);///取最小值; } if(ans == 10000000000000000) ans = -1; printf("%I64d ", ans); return 0; }