目录
写在前面
比赛地址：https://codeforces.com/gym/104901。
以下按个人向难度排序。
SUA 的题确实牛逼，把我这种只会套路的沙比狠狠腐乳了。
D
签到。
直接枚举 \([L, \min(R, L + 10)]\) 检查即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
LL check(LL x_) {
LL ret = 0;
while (x_) {
ret = std::max(ret, x_ % 10);
x_ /= 10;
}
return ret;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
LL la, ra, lb, rb; std::cin >> la >> ra >> lb >> rb;
LL L = la + lb, R = ra + rb, ans = 0;
for (LL i = L; i <= std::min(L + 10, R); ++ i) {
ans = std::max (check(i), ans);
}
std::cout << ans << "\n";
}
return 0;
}
I
构造。
一个显然的想法是每次找到最小的无序的数值，设其位置为 \(p\)，将其调整到第一个无序的位置 \(q\)。显然有 \(q<p,q < a_q\) 且 \((q, p)\) 一定构成逆序对。
然而直接这样做会被形如 5 1 2 3 4 这样的数据卡掉，原因是仅能保证每次只有最小的无序的数值被调整到有序位置，操作次数上限为 \(O(n)\) 级别。
于是考虑优化一下上述过程，考虑能否至少一次排两个位置，发现仅需将寻找最小的无序的数值改成寻找 \(a_{q} - 1\) 即可保证每次使前缀 \([1, a_{q}]\) 变为有序的，至少新增 \([q, a_{q}]\) 中至少两个有序位置，操作次数上限变为 \(O(\left\lfloor\frac{n}{2}\right\rfloor)\) 级别。
数据范围小的一批随便实现。
Code by hjxddl
//Coded by hjxddl
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const int N=2e5+5;
int t,n,a[105],ans1[105],ans2[105];
int x,x1,y,y1;
bool check(){
for(int i=1;i<=n;i++){
if(a[i]!=i){
x=a[i],x1=i;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
while(check()){
for(int i=x1;i<=n;i++)
if(x>a[i])
y1=i;
ans1[++ans]=x1;
ans2[ans]=y1;
sort(a+x1,a+y1+1);
}
cout<<ans<<'\n';
for(int i=1;i<=ans;i++)
cout<<ans1[i]<<" "<<ans2[i]<<"\n";
}
}
A
思维。
以下是赛时的杀软做法。
发现一个括号串存在二义性等价于存在四个位置 \(i, j, k, l\)：
- \(i, j, k, l\) 为同种括号。
- \([i + 1, j - 1], [j + 1, k - 1], [k + 1, l - 1]\) 均可转化为合法括号串。
则可以将这四个位置进行如下转换：
\[(\cdots(\cdots)\cdots) \iff (\cdots)\cdots(\cdots) \]保证给定的括号串一定存在一种合法构造，于是先考虑用栈按照最左优先匹配搞出一种来，则若存在满足上述条件的四个位置 \(i, j, k, l\)，它们对应的区间一定被构造成了 \((\cdots)\cdots(\cdots)\) 的形式。
若位置 \(i\) 在构造方案中为右括号，则记位置 \(i\) 匹配的括号位置为 \(p_i\)，考虑枚举每一对匹配的括号 \((p_i, i)\)：
- 检查 \((p_{p_i - 1}, i - 1)\) 是否存在，若存在检查其类型。若为同种则可构成 \((\cdots)(\cdots)\) 的形式说明有二义性。
- 若不同种，检查 \((p_{p_{p_i - 1}}, p_{i - 1} - 1)\) 是否存在，若存在检查其类型。若与 \((p_i, i)\) 同种则可构成 \((\cdots)[\cdots](\cdots)\) 的形式说明有二义性；若不同种则可构成 \([\cdots][\cdots](\cdots)\) 的形式，这种情况同样有二义性，且一定会在枚举到 \((p_{p_{i} - 1}, p_{i} - 1)\) 的时候被检查到。
按照上述过程讨论即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 1e6 + 10;
//=============================================================
std::map <char, int> type;
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
type['('] = type[')'] = 0;
type['['] = type[']'] = 1;
int T; std::cin >> T;
while (T --) {
std::string s;
int flag = 0;
std::cin >> s;
std::stack<int> st1, st2;
std::map <int,int> m;
m.clear();
for (int i = 0, len = s.length(); i < len; ++ i) {
int key = type[s[i]];
if (st1.empty()) {
st1.push(i), st2.push(key);
} else if (key != st2.top()) {
st1.push(i), st2.push(key);
} else {
m[i] = st1.top();
m[m[i]] = i;
st1.pop(), st2.pop();
}
}
for (int i = 0, len = s.length(); i < len; ++ i) {
int p = m[i];
if (p > i) continue;
if (p - 1 < 0) continue;
int q = m[p - 1];
if (q > p - 1) continue;
if (type[s[p - 1]] == type[s[i]]) {
flag = 1;
break;
}
if (q - 1 < 0) continue;
int l = m[q - 1];
if (l > q - 1) continue;
if (type[s[q - 1]] == type[s[i]]) {
flag = 1;
break;
}
}
std::cout << (flag ? "No" : "Yes") << "\n";
}
return 0;
}
赛后看了题解妈的场上太暴力了。
手玩发现有唯一构造的括号串实际上均形如 ([([...])]) 这样两种括号交替嵌套，或者为两个外层括号不同的上述括号串 ([(...)])[([...])]。
- 若有两个外层括号相同的上述括号串，如
([...])([...])显然有二义性。 - 若有两个以上的上述括号串，如
([...])[(...)]([...])显然可以构成上述(...)...(...)的二义性形式。
发现只要有相邻的两个位置 \(s_i, s_{i + 1}\) 为同种括号，说明出现了一个两种括号交替嵌套的子串（此类子串的最内层括号），或者有两个上述子串最外层括号相同。
于是仅需检查相邻的两个位置 \(s_i, s_{i + 1}\) 为同种括号的情况是否出现不大于 2 次即可。
G
图论转化，连通性问题，计数
挺典的套路呃呃，然而学艺不精场上恼弹只建了单倍节点的图导致传递性爆炸了一直 WA 呃呃太飞舞
写在最后
学到了什么：
- I：考虑每次操作至少影响的位置口牙
- A：大力手玩口瓜
- G：命题为真假的依赖关系的图论转化口也
听忍术研究部角色歌上头了，咕，可爱至极口牙！