目录
- 写在前面
- M 签到
- F 笛卡尔树 or 单调栈,dfs or ST 表,排序
- A 大力讨论,结论
- G 二分答案,前缀和
- C 结论,图论,剩余系,线性代数
- L 图论转化,建图技巧,最短路
- H 括号序列,网络流
- 写在最后
写在前面
补题地址:https://codeforces.com/contest/2005。
以下按个人难度向排序。
复刻 CCPC 网赛开头超顺利但是三个人坐牢同一个题四个小时没出哈哈太唐乐
M 签到
模拟即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll p = 998244353;
const int kN = 1e6 + 10;
int num, cnt[26], solved[kN][26];
std::map <std::string, int> id;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; std::cin >> T;
while (T --) {
for (int i = 0; i < 26; ++ i) cnt[i] = 0;
num = 0;
id.clear();
int n; std::cin >> n;
while (n --) {
std::string s, t;
char name;
std::cin >> s >> name >> t;
if (t[0] != 'a') continue;
if (!id.count(s)) {
id[s] = ++ num;
for (int i = 0; i < 26; ++ i) solved[num][i] = 0;
}
int d = id[s], p = name - 'A';
if (solved[d][p]) continue;
solved[d][p] = 1;
++ cnt[p];
}
int ans = 0, c = 0;
for (int i = 0; i < 26; ++ i) if (cnt[i] > c) ans = i, c = cnt[i];
cout << (char) ('A' + ans) << "\n";
}
return 0;
}
F 笛卡尔树 or 单调栈,dfs or ST 表,排序
场上 wenqizhi 直接高呼笛卡尔树秒了,我一听笛卡尔树就嗯了一看题真就傻逼题直接秒了。
发现最优情况下,每次操作一定仅会操作两个数,且合并的过程一定是每次找到极大的全局最小值的区间,并依次将每个全局最小值与相邻的第一个大于它的值操作,直至全部变成这个值。
发现这个过程直接放到笛卡尔树上,自底向下地根据区间长度统计贡献即可。建树后直接 dfs,总时间复杂度 \(O(n)\) 级别。
当然用单调栈+排序 / ST 表 + dfs 实现也可以,复杂度多一个 \(\log\)。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll p = 998244353;
const int kN = 2e5 + 10;
int n, rt, top, a[kN], st[kN];
int lson[kN], rson[kN];
ll ans;
void dfs(int u_, int L_, int R_) {
if (lson[u_]) {
dfs(lson[u_], L_, u_ - 1);
if (a[lson[u_]] < a[u_]) ans += u_ - 1 - L_ + 1;
}
if (rson[u_]) {
dfs(rson[u_], u_ + 1, R_);
if (a[rson[u_]] < a[u_]) ans += R_ - (u_ + 1) + 1;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> a[i], lson[i] = rson[i] = 0;
st[top = 0] = rt = 0;
for (int i = 1; i <= n; ++ i) {
int k = top;
while (k > 0 && a[st[k]] < a[i]) -- k;
if (k) rson[st[k]] = i;
if (k < top) lson[i] = st[k + 1];
st[++ k] = i;
top = k;
}
rt = st[1];
ans = 0;
dfs(rt, 1, n);
cout << ans << "\n";
}
return 0;
}
A 大力讨论,结论
显然实际的实力值是无用的,仅需考虑有多少队伍比中国队弱即可,称他们为弱弱队。
然后场上和 dztlb 大力模拟讨论下达到每个阶段所需的弱弱队数量就做完了。
一个很天才的地方是发现 8 强进 4 强,和 4 强进 2 强规则是一致的,然后发现 8 强进 4 强所需的弱弱队数变化为 \(13 = 6\times 2 + 1\),于是大胆猜测 4 强进 2 强的变化也类似地有:\(27 = 13\times 2 + 1\)。
Code by dztlb:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll p = 998244353;
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
ll qpow(ll x_, ll y_, ll mod_ = p) {
ll ret = 1;
while (y_) {
if (y_ & 1) ret = ret * x_ % mod_;
x_ = x_ * x_ % mod_, y_ >>= 1ll;
}
return ret;
}
int T;
int a[50];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>T;
while(T--){
for(int i=1;i<=32;++i){
cin>>a[i];
}
int cnt=0;
for(int i=2;i<=32;++i){
if(a[1]>a[i]) ++cnt;
}
if(cnt>=31){
puts("1"); continue;
}
if(cnt>=27){
puts("2"); continue;
}
if(cnt>=13){
puts("4"); continue;
}
if(cnt>=6){
puts("8"); continue;
}
if(cnt>=2){
puts("16"); continue;
}
puts("32");
}
return 0;
}
G 二分答案,前缀和
对于最优化中位数,一个众所周知的套路是考虑二分答案 \(\operatorname{mid}\),仅需检查数列中不小于 \(\operatorname{mid}\) 的数的数量,是否不小于 \(\left\lfloor\frac{\operatorname{len}}{2}\right\rfloor+1\) 即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
const ll p = 998244353;
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2005;
int n, A[N], a[N], d[N], b[N][N];
ll sum1[N][N], sum2[N][N], c[N][N];
bool check(int mid)
{
for(int i = 1; i <= n; ++i) a[i] = (A[i] >= mid);
for(int i = 1; i <= n; ++i) sum1[i][i] = a[i];
for(int i = 1; i <= n; ++i) sum2[i][i] = b[i][i] = a[i];
for(int len = 2; len <= n; ++len)
for(int l = 1, r = l + len - 1; r <= n; ++l, ++r)
{
sum1[l][r] = sum1[l][r - 1] + a[r];
sum2[l][r] = b[l][r] = (len / 2 + 1 <= sum1[l][r]);
}
for(int r = 1; r <= n; ++r)
for(int l = 1; l <= r; ++l)
sum2[l][r] += sum2[l - 1][r];
for(int i = 1; i <= n; ++i) c[i][i] = b[i][i];
for(int len = 2; len <= n; ++len)
for(int l = 1, r = l + len - 1; r <= n; ++l, ++r)
{
c[l][r] = c[l][r - 1] + sum2[r][r] - sum2[l - 1][r];
}
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
ans += (c[i][j] >= (j - i + 1) * (j - i + 2) / 2 / 2 + 1);
return ans >= (n * (n + 1) / 2) / 2 + 1;
}
signed main() {
n = read();
for(int i = 1; i <= n; ++i) A[i] = d[i] = a[i] = read();
sort(d + 1, d + n + 1);
int l = 1, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(d[mid])) l = mid;
else r = mid - 1;
}
printf("%lld\n", d[l]);
return 0;
}
C 结论,图论,剩余系,线性代数
牛逼提!让我想起 ICPC2021 Jinan 的 J(这场补题在 PTA 上),赛后一看也是北大出的题那可以理解了,感觉这两题肯定是一块出出来的。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, fa[kN];
//=============================================================
int find(int x_) {
return fa[x_] == x_ ? x_ : fa[x_] = find(fa[x_]);
}
void merge(int x_, int y_) {
int fx = find(x_), fy = find(y_);
if (fx == fy) return ;
fa[fx] = fy;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 0; i <= n; ++ i) fa[i] = i;
int ans = 1;
for (int i = 1; i <= n; ++ i) {
int l, r; std::cin >> l >> r;
if (find(l - 1) == find(r)) ans = 0;
merge(l - 1, r);
}
std::cout << ans << "\n";
}
return 0;
}
L 图论转化,建图技巧,最短路
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 2010;
//=============================================================
int n, l, q;
int fa[kN][2], into[kN];
std::vector<pr<int, int> > edge[kN];
int dis[kN][kN];
bool vis[kN];
//=============================================================
int get(char a_, char b_) {
int ret = ((int) a_ - 48) * 50 + ((int) b_ - 48);
return ret;
}
int find(int id_, int x_) {
return fa[x_][id_] == x_ ? x_ : fa[x_][id_] = find(id_, fa[x_][id_]);
}
void merge(int id_, int x_, int y_) {
int fx = find(id_, x_), fy = find(id_, y_);
if (fx == fy) return ;
fa[fx][id_] = fy;
}
void addedge(int u_, int v_, int w_) {
edge[u_].push_back(mp(v_, w_));
}
void init() {
for (int i = 1; i <= n; ++ i) edge[i].clear(), fa[i][0] = fa[i][1] = i;
for (int time = 1; time <= l; ++ time) {
std::string s; std::cin >> s;
int flag = 0;
for (int i = 1; i <= n; ++ i) {
vis[i] = 0, into[i] = 0, fa[i][1] = i;
}
for (int i = 0; i < 2 * n; i += 2) {
int x = get(s[i], s[i + 1]);
++ into[x];
if (into[x] == 2) ++ flag;
if (into[x] == 3) flag = kN;
merge(1, i / 2 + 1, x);
}
if (flag >= 2) continue;
if (flag) {
int u = 0, v1 = 0, v2 = 0;
for (int i = 0; i < 2 * n; i += 2) {
int p = i / 2 + 1, x = get(s[i], s[i + 1]);
if (into[p] == 0) u = p;
if (into[x] == 2 && v1 != 0 && v2 == 0) v2 = p;
if (into[x] == 2 && v1 == 0) v1 = p;
}
addedge(v1, u, time), addedge(v2, u, time);
} else {
for (int i = 1; i <= n; ++ i) {
if (find(0, find(1, i)) == find(0, i)) continue;
addedge(i, find(1, i), time), addedge(find(1, i), i, time);
merge(0, find(1, i), i);
}
}
}
}
int query(int a_, int b_, int c_) {
return dis[a_][b_] <= c_;
}
void dijkstra(int s_) {
std::priority_queue <pr <int, int> > q;
for (int i = 1; i <= n; ++ i) vis[i] = 0, dis[s_][i] = kN;
dis[s_][s_] = 0;
q.push(mp(0, s_));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w]: edge[u]) {
if (dis[s_][v] > std::max(dis[s_][u], w)) {
dis[s_][v] = std::max(dis[s_][u], w);
q.push(mp(-dis[s_][v], v));
}
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> l >> q;
init();
for (int i = 1; i <= n; ++ i) dijkstra(i);
while (q --) {
std::string s; std::cin >> s;
int a = get(s[0], s[1]), b = get(s[2], s[3]), c = get(s[4], s[5]);
std::cout << query(a, b, c);
}
std::cout << "\n";
}
return 0;
}
H 括号序列,网络流
见过括号序列转换成差分约束的,这下又见到转换成网络流的了,括号序列真是牛逼。
写在最后
学到了什么:
- C:有特殊的数学限制,考虑转化成数学模型,并考虑数学模型下限制的等价形式。
- G:最优化中位数,套路二分答案;
- H:小范围下,有数量的约束关系,考虑跑网络流确定方案。
然后日常夹带私货: