A.Bark to Unlock
time limit per test: 2 seconds
题意：
先给出一个长度是2的字符串作为密码，在给出n个长度是2字符串，判断这些字符串的组合可不可以组成密码。
思路：
先处理给出的字符串中是否含有密码，然后两个两个的判断。注意每个字符串可以多次利用。
#include "bits/stdc++.h" using namespace std; const int maxn = 120; char s[maxn][3]; int main(int argc, char const *argv[]) { scanf("%s", s[0]); int n; scanf("%d", &n); for (int i = 1; i <= n ;i++) { scanf("%s", s[i]); } bool flag = false; for (int i = 1; i <= n; i++) { if (strcmp(s[0], s[i]) == 0) flag = true; for (int j = 1; j <= n; j++) { if (flag) break; if (s[0][0] == s[i][1] && s[0][1] == s[j][0]) flag = true; } if (flag) break; } printf("%s ", flag?"YES": "NO"); return 0; }
B.Race Against Time
time limit per test: 2 seconds
题意：
给出现在钟表的时刻，判断从t1到t2是否可以不夸过指针。
思路：
判断每个指针是否在都在t1和t2的同一夹角里。
#include "bits/stdc++.h" using namespace std; const double pc = 1e-3; double arct2, arct1, t; bool judge(double h, double m, double s) { bool flag1 = true, flag2 = true; if (h>arct1&&h<arct2||m>arct1&&m<arct2||s>=arct1&&s<=arct2) flag1 = false; if (h<arct1&&h>0||m<arct1&&m>0||s<arct1&&s>=0) flag2 = false; if (h>arct2&&h<360||m>arct2&&m<360||s>arct2&&s<=360) flag2 = false; // printf("%d %d ", flag1, flag2); return flag1||flag2; } int main(int argc, char const *argv[]) { int h, m, s, t1, t2; scanf("%d%d%d%d%d", &h, &m, &s, &t1, &t2); if (h == 12) h = 0; arct1 = t1*360/12; arct2 = t2*360/12; double arcs = s*360/60; double arcm = ((double)m + (double)s/60)*360.0/60; double arch = ((double)h + (double)s/60)*360.0/12; if (arct1 > arct2) { t = arct1; arct1 = arct2; arct2 = t;} if (judge(arch, arcm, arcs)) printf("YES "); else printf("NO "); return 0; }
C.Qualification Rounds
time limit per test: 2 seconds
题意：
Snark and Philip 要出一套题，但是每个队伍都会都做过这些题里的某些题，为了让比赛更有意思，他们要找出题，使得每个队至少有一半的题没有做过。给出n个题，k个队伍，一个矩阵表示每个队伍对每道题的状态。
思路：
其实只要考虑找到两道题，使得每个队做过1个或者没有做过。把每个题的状态进行状压，然后枚举其中的一道题，二分判断是否有另一种可行的状态。
#include "bits/stdc++.h" using namespace std; const int maxn = 1e5 + 10; bool flag; int N, K; int r[maxn]; void judge(int x) { int ans = 0; int ub = N, lb = 0; while (ub >= lb) { int mid = (ub + lb)/2; if (r[mid] >= x) { ans = mid; ub = mid - 1; } else lb = mid + 1; } if (r[ans] == x) flag = true; } void dfs(int x, int t) { if (t == K) {judge(x);} else { if ((x>>t)&1) dfs(x^(1<<t), t+1); else { dfs(x, t+1); dfs(x^(1<<t), t+1); } } } int main(int argc, char const *argv[]) { scanf("%d%d", &N, &K); flag = false; for (int i = 0; i < N; i++) { int res = 0; for (int j = 0; j < K; j++) { int a; scanf("%d", &a); if (a == 1) res += 1<<j; } if (res == 0) flag = true; r[i] = res; } sort(r, r + N); for (int i = 0; i < N; i++) dfs(r[i], 0); printf("%s ", flag?"YES": "NO"); return 0; }
D题读了读题，然后跑路去刷数分了，以后再补题。。。。。( •̀ ω •́ )✧