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;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
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)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
struct node
{
int id, s, type;
}a[55];
char m[55][55];
bool vis[55][55];
signed main()
{
// DDLC_ESCAPE_PLAN_FAILED;
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. 数列中所有数都相同时,全部排列都符合条件
  2. 数列中最大值与次大值相差大于1,且最大值只有1个时,无论如何都不会满足条件
  3. 数列中最大值出现次数超过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;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
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;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
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;
}