题意就是给你$n$个$01$串，问你是否已经存在两个人相邻的$1$或者可以使某些位置的$0$变成$1$且不出现相邻的$1$，虽是水题实际上有点坑，注意下两边的特判就行。
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include <bits/stdc++.h> using namespace std ;#define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define all(a) (a).begin(),(a).end() #define pb(x) push_back(x) #define clr(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); #define caseT int _T;scanf("%d" ,&_T);for (int q=1; q<=_T; ++q) typedef pair<int , int > pii;typedef long long ll;const double PI = acos (-1.0 );const int N = 1010 ;char s[N];int n;int main (void ) while (~scanf ("%d%s" , &n, s + 1 )) { int i; if (n == 1 ) { puts (s[1 ] == '1' ? "Yes" : "No" ); return 0 ; } for (i = 1 ; i <= n; ++i) { if (s[i] == '1' && s[i + 1 ] == '1' ) { puts ("No" ); return 0 ; } if (i == 1 && i + 1 <= n && s[i] == '0' && s[i + 1 ] == '0' ) { puts ("No" ); return 0 ; } if (i == n - 1 && i + 1 <= n && s[i] == '0' && s[i + 1 ] == '0' ) { puts ("No" ); return 0 ; } if (i - 1 >= 1 && i + 1 <= n && s[i] == '0' && s[i - 1 ] == '0' && s[i + 1 ] == '0' ) { puts ("No" ); return 0 ; } } puts ("Yes" ); } return 0 ; }
题意就是$n$个内向和外向的人先后上公交车，按照一定的规则寻找他们要的座位，输出每个人所在座位的编号。
显然用堆模拟一下就就行了STL水题。
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <bits/stdc++.h> using namespace std ;#define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define all(a) (a).begin(),(a).end() #define pb(x) push_back(x) #define clr(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); #define sf(x) scanf("%d" , &x) #define caseT int _T;scanf("%d" ,&_T);for (int q=1; q<=_T; ++q) typedef pair<int , int > pii;typedef long long ll;const double PI = acos (-1.0 );const int N = 2e5 + 7 ;priority_queue<pii>in, ex; int w[N];int main (void ) int n, i; sf(n); for (i = 1 ; i <= n; ++i) { sf(w[i]); in.push({ -w[i], i}); } string s; cin >> s; for (auto &c : s) { if (c == '0' ) { pii a = in.top(); in.pop(); printf ("%d " , a.second); ex.push({ -a.first, a.second}); } else { pii a = ex.top(); ex.pop(); printf ("%d " , a.second); } } puts ("" ); return 0 ; }
题意就是给你$n$个点的树，求删掉尽量多的边使得剩下的连通块点数全为偶数。输出最多删掉的边数。
显然如果$n$为偶数则一定可以，奇数一定不行（因为不管怎么分总有至少一个连通块会是奇数个点）。然后对这棵树DFS一次统计一下每颗子树的点数，如果子树$v$的大小为偶数则将当前结点$u$连向$v$的边删掉，断开即可。
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <bits/stdc++.h> using namespace std ;#define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define pb(x) push_back(x) #define sf(x) scanf("%d" , &x) #define all(a) (a).begin(),(a).end() #define clr(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); #define caseT int _T;scanf("%d" ,&_T);for (int q=1; q<=_T; ++q) typedef pair<int , int > pii;typedef long long ll;const double PI = acos (-1.0 );const int N = 1e5 + 7 ;vector <int >E[N];int sz[N], ans;void dfs (int u, int f) sz[u] = 1 ; for (auto &v : E[u]) { if (v != f) { dfs(v, u); sz[u] += sz[v]; if (sz[v] % 2 == 0 ) ++ans; } } } int main (void ) int n, i, a, b; sf(n); for (i = 1 ; i < n; ++i) { sf(a), sf(b); E[a].pb(b); E[b].pb(a); } if (n & 1 ) puts ("-1" ), exit (0 ); dfs(1 , -1 ); printf ("%d\n" , ans); return 0 ; }
题意就是给你$n$天鲨鱼的前进距离$d_1…d_n$，规定如果某一天前进的距离$d_i \lt k$，那么这天相当于在原地，否则相当于移动到了新的地方，求在移动到新地方的次数最多且在每段在原地的天数均相同的前提下最小的$k$。
补题的时候题解是俄文的看不懂，别人的代码更看不懂系列，只知道排序+并查集做，在纸上模拟了好一会儿终于想通补掉了。
首先先对移动距离排序，然后遍历这些移动距离，遍历的时候假设$1…i$天是在原地的，那么此时最小的$k’$应是$d_i+1$，然后过程中用并查集维护哪些天可以连成连续的一段和，用集合大小维护段的大小，再用一个数组维护集合大小的出现次数，由于条件是每段在原地的天数均相同 ，那么只能是集合大小均相同的时候才能更新答案$k$，再用一个变量维护不同集合大小的个数即可。遍历过程模拟把当前天激活，并看下左右相邻的日子是否可以合并过去变成连续的一段。中间更新下那几个数组就行了。
代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 #include <bits/stdc++.h> using namespace std ;#define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define pb(x) push_back(x) #define sf(x) scanf("%d" , &x) #define all(a) (a).begin(),(a).end() #define clr(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); #define caseT int _T;scanf("%d" ,&_T);for (int q=1; q<=_T; ++q) typedef pair<int , int > pii;typedef long long ll;const double PI = acos (-1.0 );const int N = 1e5 + 7 ;int pre[N], sz[N], cnt[N], n, lencnt, dx, one;pii a[N]; void init () clr(pre, -1 ); } int fd (int n) return pre[n] == -1 ? n : pre[n] = fd(pre[n]); } void mg (int a, int b) a = fd(a), b = fd(b); if (a != b) { pre[b] = a; sz[a] += sz[b]; sz[b] = 0 ; } } void check (int x) int v = x + 1 ; if (v <= n && sz[fd(v)]) { if (--cnt[sz[fd(v)]] == 0 ) --lencnt; if (--cnt[sz[x]] == 0 ) --lencnt; mg(x, v); if (++cnt[sz[fd(v)]] == 1 ) ++lencnt; } v = x - 1 ; if (v >= 1 && sz[fd(v)]) { if (--cnt[sz[fd(v)]] == 0 ) --lencnt; if (--cnt[sz[fd(x)]] == 0 ) --lencnt; mg(x, v); if (++cnt[sz[fd(v)]] == 1 ) ++lencnt; } one = cnt[sz[fd(x)]]; } int main (void ) int i; init(); sf(n); for (i = 1 ; i <= n; ++i) { sf(a[i].first); a[i].second = i; } sort(a + 1 , a + 1 + n); int ans = 1 ; for (i = 1 ; i <= n; ++i) { sz[a[i].second] = 1 ; if (++cnt[1 ] == 1 ) ++lencnt; check(a[i].second); if (lencnt == 1 && one > dx) { ans = a[i].first + 1 ; dx = one; } } printf ("%d\n" , ans); return 0 ; }