A. Balanced Substring
题意
从给定的$ab$串中找到任意一个$a,b$数量相等的子串并输出。如果找不到输出$-1 -1$.
分析
如果一个较大的子串符合要求,则其中必然出现”$ab$”或者”$ba$”,故只找这两种串即可。
另外$n\leq 50$,随便你怎么暴力。
代码
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
| #include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll;
using namespace std;
signed main() { DDLC_ESCAPE_PLAN_FAILED; int t; cin >> t; while(t--) { int n; cin >> n; string s; cin >> s; bool flag = 0; for(int i = 0; i < s.size() - 1; ++i){ if(s[i] != s[i + 1]){ cout << i + 1 << ' ' << i + 2 << endl; flag = 1; break; } } if(!flag) cout << -1 << ' ' << -1 << endl; } }
|
B. Chess Tournament
题意
有$n$个人两两比赛,他们分两种人,第一种人不能够有败绩,第二种人希望赢至少一局,存在平局。
问有没有可能构造出满足所有人的最终结果,如果有,输出任意一个结果。
分析
对于第一种人,他们不能有败绩,所以他们对局直接全部设为平局即可。
对于第二种人,他们要在内部赢其他人至少一次。对于第 $i$ 个人,可以贪心地选取当前剩余未比场次最多的人 $j$ 来让 $i$ 赢 $j$。也可以直接让所有第二种人构成一个环,环上箭头尾部赢,头部输,除环以外剩下的对局随便填满即可。总之$n\leq 50$,随便怎么搞
代码(贪心)
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
| #include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll;
using namespace std; struct node { int id, s, type; }a[55]; char m[55][55]; bool vis[55][55]; signed main() { int t; cin >> t; while(t--) { int n; cin >> n; mem(vis); fors(i, 1, n){ a[i].id = i; scanf("%1d", &a[i].type); a[i].s = n; } vector<int> v; fors(i, 1, n){ if(a[i].type == 2) v.pb(i); else{ fors(j, 1, n){ if(i == j) continue; m[i][j] = m[j][i] = '='; vis[i][j] = vis[j][i] = 1; a[j].s--, a[i].s--; } } } bool flag = 1; for(int i = 0; i < v.size(); ++i){ int mx = 0, mxi; for(int j = 0; j < v.size(); ++j){ if(i == j) continue; if(mx < a[v[j]].s && !vis[v[i]][v[j]]){ mx = a[v[j]].s; mxi = v[j]; } } if(mx == 0){ flag = 0; break; } a[v[i]].s--, a[mxi].s--; m[v[i]][mxi] = '+', m[mxi][v[i]] = '-'; vis[v[i]][mxi] = vis[mxi][v[i]] = 1; } fors(i, 1, n){ fors(j, 1, n){ if(!vis[i][j]){ m[i][j] = '+', m[j][i] = '-'; vis[i][j] = vis[j][i] = 1; } } } if(!flag) cout << "NO" << endl; else{ cout << "YES" << endl; fors(i, 1, n){ fors(j, 1, n){ if(i == j){ cout << 'X'; continue; } cout << m[i][j]; } cout << endl; } } } return 0; }
|
C. Jury Meeting
题意
有$n$个数,你需要把他们进行排列,排列完后,从左至右,每个数依次减去1。当一个数减为0后,它就会被跳过,不再减去。然后再从1开始,重复这个步骤,直到所有数都变成0。
你需要保证在这个过程中,不会有一个位置被连续减了两次,求满足条件的排列数。
分析
一个位置被连续减了两次当且仅当除了它以外全都是0.
剩下的这个被连续减去的肯定也只可能是最大值了。
显然可以知道:
- 数列中所有数都相同时,全部排列都符合条件
- 数列中最大值与次大值相差大于1,且最大值只有1个时,无论如何都不会满足条件
- 数列中最大值出现次数超过1时,全部排列都符合条件(和情况1相似)
故我们只需要讨论的情况只剩下:数列中最大值与次大值相差1,且最大值只出现一次的情况。
要不使最大值被连续减去多次,当且仅当排列中最大值的后面存在次大值。
例如$3,3,4$最后会被减成$0,0,1$,再减一次$0,0,0$,第三个位置就被连续减了两次。但是$3,4,3$的话,最后减成$0,1,0$,最后减去第二个位置,但是第二个位置上一个减去的是第三个位置,不连续。
所以我们找到一种排列,最大值的后面有次大值即可。
为了稍微简化计算,不妨考虑其互斥情况:最大值后面没有次大值。
那么我们利用高中排列组合的“插空法”。假设$n$个数中,有$1$个最大值,$c2$个次大值。从$n$个位置中选择$c2+1$个位置,然后选出位置的最后一个放上最大值,其余位置用次大值进行全排列,剩下的$n-c2-1$个位置再用其余数全排列,得到$C_{n}^{c2+1}·A_{c2}^{c2}·A_{n-c2-1}^{n-c2-1}$,所以最终答案是
(当然,正向考虑并不比这个互斥情况复杂,直接$ans=C_n^{c2+1}·C_{c2}^1·A_{c2}^{c2}·A_{n-c2-1}^{n-c2-1}$,昨晚有点多此一举)
具体实现上使用了Lucas定理,复杂度$O(nlogn)$,注意最后做减法的时候取模。
代码
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 93 94
| #include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll;
using namespace std; const int maxn = 2e5 + 10; int pi[maxn]; const int mod = 998244353LL; int qpow(int a, int b) { int ans = 1; a %= mod; while(b) { if(b & 1){ ans = ans * a % mod; } b >>= 1; a = a * a % mod; } return ans; } int C(int n, int m) { if(m > n) return 0; int ans = 1; fors(i, 1, m){ int a = (n + i - m) % mod; int b = i % mod; ans = ans * (a * qpow(b, mod - 2) % mod) % mod; } return ans % mod; } void prework() { pi[0] = 1; pi[1] = 1; fors(i, 1, maxn - 1){ pi[i] = (pi[i - 1] * i) % mod; } } int a[maxn]; signed main() { DDLC_ESCAPE_PLAN_FAILED; int t; cin >> t; prework(); while(t--) { int n; cin >> n; fors(i, 1, n) cin >> a[i]; int mx = 0; fors(i, 1, n) mx = max(mx, a[i]); int tmx = 0; fors(i, 1, n){ if(a[i] > tmx && a[i] != mx) tmx = a[i]; } int c1 = 0, c2 = 0; fors(i, 1, n){ if(a[i] == mx) c1++; else if(a[i] == tmx) c2++; } if(c2 == 0 || c1 > 1){ cout << pi[n] << endl; } else if(mx - tmx > 1){ cout << 0 << endl; } else{ int ans = C(n, c1 + c2); ans = (ans * pi[c1]) % mod; ans = (ans * pi[c2]) % mod; ans = (ans * pi[n - c1 -c2]) % mod; ans = pi[n] - ans; ans += 2 * mod; ans %= mod; cout << ans << endl; } } return 0; }
|
D. Inconvenient Pairs
题意
在一个坐标从$(0,0)$到$(1e6,1e6)$的正方形框里,有$n$条横直线,$m$条纵直线。输入保证边界也是直线之一。现在有$k$个点分布在各个确定的直线上,只能通过已经画出的线移动,当一对点之间的最短路大于他们之间的曼哈顿距离时,这对点称为inconvenient,问有多少对inconvenient的点。
分析
当一个点在横线竖线的交点上时,它肯定不做贡献,到任意其他的点的最短路程都是曼哈顿距离。
但当两个点同在横线上但不是同一个横线上时,就有可能做贡献了。竖线同理。
如果两个点在横线上,且不在同一横线上,而且他们都被夹在相邻的两竖线之间,那么肯定就是inconvenient pair了,竖线同理。
我们需要算出,任意两相邻竖线之间有多少条在横线上的点,并排除掉在同一横线上的情况,然后计算答案。
具体就是用map存有哪些横(纵)边,然后对每个纵(横)边上的点用二分查找查出它在哪两个横(纵)边之间,答案先加上目前已统计的这两条横边之间的点的数目,再减去点所在纵边上原来有的点的数目。
代码
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
| #include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll;
using namespace std; const int maxn = 2e5 + 10; int v[maxn], h[maxn]; signed main() { DDLC_ESCAPE_PLAN_FAILED; int t; cin >> t; while(t--) { map<int, bool> verti, horiz; map<pair<int, int>, int> onY, onX; map<int, int> cntx, cnty; int n, m, k; cin >> n >> m >> k; fors(i ,1, n) cin >> v[i], verti[v[i]] = 0; fors(i, 1, m) cin >> h[i], horiz[h[i]] = 0; int x, y; int ans = 0; fors(i, 1, k){ cin >> x >> y; if(verti.count(x) && horiz.count(y)) continue; else{ int px = lower_bound(v + 1, v + 1 + n, x) - v; int py = lower_bound(h + 1, h + m + 1, y) - h; if(verti.count(x)){ ans += cnty[py] - onX[{py, x}]; cnty[py]++, onX[{py, x}]++; } else{ ans += cntx[px] - onY[{px, y}]; cntx[px]++, onY[{px, y}]++; } } } cout << ans << endl; } return 0; }
|