A - Sort Left and Right
答案为 0 即已经排序。
考虑答案为 1 的情况：一定是存在一个 \(p\)，使得 \(\min_{i=1}^{p}a_i=p\) 且 \(a_p=p\)，这时只要选择 \(p\) 即可。
考虑答案为 2 的情况：如果 \(a_1\neq n\operatorname{or}a_n\neq 1\)，一定可以通过先操作某个数，把 \(1\) 或者 \(n\) 放到正确的位置，然后进行答案为 1 的操作即可。共操作 2 次。
答案一定不超过 3：如果 \(a_1= n\operatorname{and}a_n=1\)，这时无法通过某种操作直接变成答案为 1 的情况。
所以只能先随便操作一下，就可以变成答案为 2 的情况。共操作 3 次。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, a[N];
bool ok0()
{
for(int i = 1; i <= n; i ++)
if(a[i] != i) return 0;
return 1;
}
bool ok1()
{
int mx = 0;
for(int i = 1; i <= n; i ++)
{
mx = max(mx, a[i]);
if(i == a[i] && mx == a[i]) return 1;
}
return 0;
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
if(ok0()) return cout << 0 << "\n", void();
if(ok1()) return cout << 1 << "\n", void();
cout << 2 + (a[1] == n && a[n] == 1) << "\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
B - Annoying String Problem
注意到如果 \(x\) 和 \(y\) 有公共前缀 \(pre\)，那么可以同时去掉 \(pre\)，答案不变。
不妨设现在的 \(x_0=\texttt{0},y_0=\texttt{1}\)，并且 \(|S|<|T|\)。
因为 \(f(S,T,x)=f(S,T,y)\)，所以可以把每个 \(1\) 拆成 \(01\)，\(T=T'+S\)，用 \(T'\) 替换 \(T\)，然后消去相同前缀，这样答案仍然不变。
感性理解一下，\(S\) 和 \(T\) 存在相同子串 \(P\) 使得 \(S,T\) 都是一些 \(P\) 串在一起得到的。
于是可以设 \(S=aP,T=bP\)。可以通过解方程得到 \(a,b\)。
可以通过 \(x,y\) 列出方程：
\(\sum_{i=1}^{|x|}[x_i=0]a+\sum_{i=1}^{|x|}[x_i=1]b=\sum_{i=1}^{|y|}[y_i=0]a+\sum_{i=1}^{|y|}[y_i=1]b\)
然后移项解方程得出 \(a,b\) 关系，得出 \(k_1a=k_2b(\gcd(k_1,k_2)=1)\)。
于是有 \(\dfrac{a}{k_2}=\dfrac{b}{k_1}\)。因为 \(a\) 要是 \(k_2\) 倍数，于是只要判断是否存在 \(P\) 使得 \(S=k_2P\) 即可。
中间要特判未知数系数为负数，为 0 的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ok(string s, int x)
{
if(s.size() % x) return 0;
int n = s.size(), d = n / x;
for(int i = 0; i < n; i += d)
{
for(int j = 0, k = i; j < d; j ++, k ++)
if(s[j] != s[k])
return 0;
}
return 1;
}
void solve()
{
string s; cin >> s;
string s1, s2;
cin >> s1 >> s2;
int x = 0, y = 0;
for(char c : s1) x += c == '0', y += c == '1';
for(char c : s2) x -= c == '0', y -= c == '1';
y = -y;
if(y == 0)
{
if(x == 0) return cout << "Yes" << "\n", void();
else return cout << "No\n", void();
}
if(x == 0) return cout << "Yes\n", void();
if(1ll * x * y < 0) return cout << "No\n", void();
if(x < 0) x = -x, y = -y;
int d = __gcd(x, y);
x /= d, y /= d;
if(ok(s, y)) cout << "Yes\n";
else cout << "No\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int t;cin >> t;while(t --) solve();
return 0;
}
C - Row and Column Order
令原题的 \(p,q\) 为下文的 \(a,b\)。
令下文的 \(p,q\) 为满足 \(p_{a_i}=i,q_{b_i}=i\) 的排列。
考虑一种思路：
优先满足 \(a\)，尽量捎带上 \(b\)。
考虑对于每个点 \((i,j)\)，填入 \([p_i>q_j]\)。
然后我们发现，这样会满足 \(a\)，并且反着满足了 \(b\)。
所以令 \(q'_{b_i}=n-i+1\)。
对于每个点 \((i,j)\)，填入 \([p_i>q'_j]\) 即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
int n, a[N], b[N];
int p[N], q[N];
int ans[N][N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
for(int i = 1; i <= n; i ++) p[a[i]] = i;
for(int i = 1; i <= n; i ++) q[b[i]] = n - i + 1;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
ans[i][j] = p[i] > q[j];
for(int i = 1; i <= n; i ++, cout << "\n")
for(int j = 1; j <= n; j ++)
cout << ans[i][j];
return 0;
}
D - Prefix Bubble Sort
考虑枚举每个数，考虑什么时候会让逆序对少 1。
观察性质，设 \(c_i=\sum_{j=1}^{i-1}[p_j>p_i]\)。
设 \(k_i\) 为最小的 \(d\) 使得 \(a_d\ge p_i\)。
我们发现，对于 \(p_i\)，它会给从第 \(k_i\) 次开始的连续 \(c_i\) 次操作都贡献 -1 的逆序对数。
于是树状数组计算 \(c_i\)，二分查找 \(k_i\)，复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct bit
{
int a[N];
int lbit(int x) {return x & -x;}
void upd(int x, int v)
{
for(int i = x; i < N; i += lbit(i)) a[i] += v;
}
int qry(int x)
{
if(!x) return 0;
int s = 0;
for(int i = x; i; i -= lbit(i)) s += a[i];
return s;
}
} t;
int n, a[N], m, b[N];
int d[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i ++) cin >> b[i];
ll sum = 0;
for(int i = 1; i <= n; i ++)
{
int p = i - 1 - t.qry(a[i]);
sum += p;
t.upd(a[i], 1);
int l = lower_bound(b + 1, b + m + 1, i) - b;
d[l] ++, d[min(m + 1, l + p)] --;
}
for(int i = 1; i <= m; i ++)
{
d[i] += d[i - 1];
sum -= d[i];
cout << sum << "\n";
}
return 0;
}
还可以枚举二分的答案，这样可以少一半常数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct bit
{
int a[N];
int lbit(int x) {return x & -x;}
void upd(int x, int v)
{
for(int i = x; i < N; i += lbit(i)) a[i] += v;
}
int qry(int x)
{
if(!x) return 0;
int s = 0;
for(int i = x; i; i -= lbit(i)) s += a[i];
return s;
}
} t;
int n, a[N], m, b[N];
int d[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i ++) cin >> b[i];
ll sum = 0;
b[m + 1] = n;
for(int i = 1; i <= m + 1; i ++)
{
for(int j = b[i - 1] + 1; j <= b[i]; j ++)
{
int p = j - 1 - t.qry(a[j]);
sum += p;
t.upd(a[j], 1);
d[i] ++, d[min(m + 1, i + p)] --;
}
}
for(int i = 1; i <= m; i ++)
{
d[i] += d[i - 1];
sum -= d[i];
cout << sum << "\n";
}
return 0;
}