ICPC2023 济南站 个人题解

Dashboard - The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan) - Codeforces

和队友都干了！5题665罚时银尾（）

A

注意到原题有保证给定的任意括号序列都对应着至少一个合法括号序列，回顾一下判定一个括号序列是否合法的过程：我们发现我们使用一个栈来判定一个括号序列是否可以是一个合法的括号序列。把左括号看成+1，右括号看成-1，那么同一种括号任意位置的前缀和显然都 $\geq 0$。

然后我们考虑，在改变左右方向的括号序列里面，实际上只需要如果连续有四个相同种类的括号，那么就至少有两种方法可以保证合法：(()) 与 ()() 进一步发现，其实只要存在任意三个位置有相同括号就可以了。因为多一种括号只需要考虑形如 (([])) 的情况，这样的情况显然可以通过变成 ()[]() 来判定。

因为这个题目限制保证了你是合法的括号序列，所以在后面肯定也有一个括号可以和多的这个左括号匹配。因此这个题就转变成了是否能找到三个相同的位置有相同类型括号即可。时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 1e5 + 10;
char s[N];
int n;
void solve() {
    cin >> s;
    n = strlen(s);
    for (int i = 0;i < n;++i) {
        if (s[i] == ')') s[i] = '(';
        if (s[i] == ']') s[i] = '[';
    }
    int cnt = 0;
    for (int i = 0;i < n-1;++i) {
        if (s[i] == s[i+1]) ++cnt;
    }
    if (cnt > 2) puts("No");
    else  puts("Yes");
}
signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

B

先考虑一个简单的树形 DP：我们令 $dp[x][k]$ 代表点 $x$ 的子树内切出大小为 $k$ 的子树的方案数，那么这个东西实际上是一个经典的树形背包，可以按照如下方式转移：

$$
dp[x][k] = \sum\limits_{y\in son(x),i+j=k} dp[x][i] \times dp[y][j]
$$

$k$ 较小的时候，我们可以通过直接限制树形背包的转移来让这个 DP 的时间复杂度达到 $O(nk)$ 代码如下:

for (int i = 0;i <= k+1;++i) tmp[i] = 0;
for (int j = 0;j <= min(siz[y],k);++j) {//这一步的上界为k，因为i要占用1个点
    for (int i = min(k+1 - j,siz[x]);i >= 1;--i) {
        tmp[i+j] = (tmp[i+j] + dp[x][i] * dp[y][j] % mod) % mod;
    }
}
siz[x] += siz[y];
for (int i = 0;i <= k+1;++i) dp[x][i] = tmp[i];

$k$ 较大的时候，我们研究一下这个点的转移，发现 $dp[x]$ 中可用的转移点实际上是非常有限的，因为考虑假设切了 $a$ 个大小为 $b$ 的块，那么剩下的为 $siz_x - a\times b \bmod k+1$ 这个东西实际上也是很有限的，所以我们用 unordered_map 来存这个东西。

考虑如何划分这个 $k$ ？ 显然如果取 $k = \sqrt n$ 的时候，总时间复杂度可以认为是 $O(n\sqrt n)$ 在 QOJ 上可以通过，不过好像在 CF 上被卡了，这里建议取 $k = 2\times \sqrt n$ 也就是大概 660 左右，反正 CF 上第二种情况跑的巨慢无比，唉唉 CF。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 1e5 + 10;
const int K = 700;
const ll mod = 998244353;
unordered_map <int,ll> DP[N],ttmp;
ll dp[N][K],n,k,tmp[N],siz[N];
vector <int> G[N];

void dfs1(int x,int fa) {
    dp[x][1] = 1;
    siz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y,x);
        for (int i = 0;i <= k+1;++i) tmp[i] = 0;
        for (int j = 0;j <= min(siz[y],k);++j) {//这一步的上界为k，因为i要占用1个点
            for (int i = min(k+1 - j,siz[x]);i >= 1;--i) {
                tmp[i+j] = (tmp[i+j] + dp[x][i] * dp[y][j] % mod) % mod;
            }
        }
        siz[x] += siz[y];
        for (int i = 0;i <= k+1;++i) dp[x][i] = tmp[i];
    }
    dp[x][0] = (dp[x][k] + dp[x][k+1]) % mod;
    /*cout << "nowpoi:" << x << "\n";
    for (int i = 0;i <= k+1;++i) {
        cout << dp[x][i] << " ";
    }
    cout <<"\n";*/
}

void dfs2(int x,int fa) {
    DP[x][1] = 1;
    siz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs2(y,x);
        ttmp.clear();
        for (auto [j,val2] : DP[y]) {
            for (auto [i,val1] : DP[x]) {
                if (i + j > k+1) continue;
                ttmp[i+j] = (ttmp[i+j] + val1 * val2 % mod) % mod;
            }
        }
        DP[x].clear();
        for (auto [i,val1] : ttmp) DP[x][i] = val1;
        siz[x] += siz[y];
    }
    ll now = 0;
    if (DP[x].count(k)) now = (now + DP[x][k]) % mod;
    if (DP[x].count(k+1)) now = (now + DP[x][k+1]) % mod;
    DP[x][0] = (now % mod + mod )% mod;
    if (!DP[x][0]) DP[x].erase(0);
    /*cout << "nowpoi:" << x <<"\n";
    for (auto [i,j] : DP[x]) {
        cout << i << " " << j << "\n";
    }
    cout <<"\n";*/
    
    for (auto y : G[x]) {
        if (y == fa) continue;
        DP[y].clear();
    }

}

void solve() {
    cin >> n >> k;
    for (int i = 1;i <= n;++i) G[i].clear();
    for (int i = 1;i < n;++i) {
        int x,y;cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int lim = sqrt(n);
    if (k <= lim) {
        for (int i = 1;i <= n;++i) {
            for (int j = 0;j <= k + 1;++j) {
                dp[i][j] = 0;
            }
        }
        dfs1(1,0);
        cout << dp[1][0]  << "\n";
    } else {
        DP[1].clear();
        dfs2(1,0);
        cout << DP[1][0] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}
/*
2
4 3
1 2
1 3
2 4
4 3
1 2
1 3
2 4
*/

D

签到题，我们研究一下容易发现只要存在一个 $r-l \geq 10$ 就可以保证，不论另外一个数 $a$ 是什么，总能找到一个对应的 $b$ 满足 $a+b\bmod 10 = 9$，所以对于这部分答案直接为 9，剩下的暴力判断即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>

int calc(int x) {
    int bit = 0;
    while (x) {
        bit = max(bit,x % 10);
        x /= 10;
    }
    return bit;
}

void solve() {
    int l1,r1,l2,r2;cin >> l1 >> r1 >> l2 >> r2;
    int maxdel = max(r1-l1+1,r2-l2+1);
    int ans = 0;
    if (maxdel >= 10) {
        ans = 9;
    } else {
        for (int i = l1;i <= r1;++i) {
            for (int j = l2;j <= r2;++j) {
                ans = max(ans,calc(i+j));
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

E

先吐槽一下，其实我不明白为什么这个题的范围要给到 $n\leq 10^5$ 感觉在 CF 上还挺容易卡常的，虽然 Dinic 在二分图上跑是 $O(n\sqrt n)$ 的.jpg

我们先考虑对于一组确定的最大匹配，添加哪些边可以使得匹配数恰好 +1？记 $S_1$ 为左部点中没有被匹配的点构成的集合，$S_2$ 为右部点中没有被匹配的点构成的集合，那么显然我们任意找 $x \in S_1,y\in S_2$，那选中 $(x,y)$ 这条边就可以使得匹配数恰好 +1，所以答案就是 $|S_1|\times |S_2|$

那么就考虑如何统计 $S_1,S_2$ 中的点？首先我们肯定需要跑一遍最大流求出最大匹配数，接下来我们研究一下这个流图的性质：对于一条被选中的边 $(x,y)$，残量网络中的边就会变成 $(y,x)$，研究一下发现 $S_1$ 中的点满足的条件显然是此时 $x$ 仍然有剩余未流的边 $(x,y)$，对于 $S_2$ 是同理的。所以 DFS 一遍就做完了捏。

时间复杂度大概是 $O(n\sqrt n)$ 的，边数比较少所以可以跑过去，但是在 CF 上我的做法被卡到只能开 C++23 过，what can i say.

#include <bits/stdc++.h>
using namespace std;

//sb codeforces
#define ll long long
#define pii pair <int,int>
const int M = 1e6 + 10;
const int N = 4e5 + 10;
struct edge {
    int to;
    int cap;
}e[M];

int n,m,s,t,cnt = -1;
vector <int> g[N];
int cur[N],h[N];
bool vis[N];

bool bfs(int s,int t) {
    for (int i = 1;i <= 2*n+2;++i) h[i] = -1;
    //h.assign(2*n+10,-1);
    queue <int> que;
    h[s] = 0;
    que.push(s);
    while (!que.empty()) {
        const int u = que.front();
        que.pop();
        for (int i : g[u]) {
            auto [v,c] = e[i];
            if (c > 0 && h[v] == -1) {
                h[v] = h[u] + 1;
                if (v == t) return 1;
                que.push(v);
            }
        }
    }
    return false;
}

int dfs(int u,int t,int f) {
    if (u == t) {
        return f;
    }
    auto r = f;
    for (int &i = cur[u];i < int(g[u].size());++i) {
        const int j = g[u][i];
        auto [v,c] = e[j];
        if (c > 0 && h[v] == h[u] + 1) {
            auto a = dfs(v,t,min(r,c));
            e[j].cap -= a;
            e[j^1].cap += a;
            r -= a;
            if (!r) return f;
        }
    }
    return f - r;
}

void addedge(int u,int v,int c) {
    g[u].push_back(++cnt);
    e[cnt].to = v,e[cnt].cap = c;
    g[v].push_back(++cnt);
    e[cnt].to = u,e[cnt].cap = 0;
}

int maxflow(int s,int t) {
    int ans = 0;
    while (bfs(s,t)) {
        for (int i = 1;i <= 2 * n + 2;++i) cur[i] = 0; 
        //cout << ans << "\n";
        ans += dfs(s,t,numeric_limits<int>::max());
    }
    return ans;
}

ll ans[2];


void dfs1(int x,int typ) {
    if (typ) {
        if (x <= n) ++ans[0];
    } else {
        if (x > n && x <= 2 * n) ++ans[1];
    }
    vis[x] = 1;
    //cout << x << " " << typ << "\n";
    for (int i : g[x]) {
        auto [v,c] = e[i];
        if (!vis[v] && c == typ) {
            //cout << x << " " << v << endl;
            dfs1(v,typ);
        }
    }
}

void solve() {
    cin >> n >> m;
    cnt = -1;
    for (int i = 1;i <= 2 * n + 2;++i) vis[i] = 0,g[i].clear();
    //vis.assign(2 * n+10,0);
    s = 2 * n + 1,t = 2 * n + 2;
    //g.resize(2*n+10);
    ans[0] = ans[1] = 0;
    //e.clear();
    //g.clear();
    //cur.clear();
    //h.clear();
    for (int i = 1;i <= m;++i) {
        int x,y;cin >> x >> y;
        addedge(x,y+n,1);
    }
    for (int i = 1;i <= n;++i) addedge(s,i,1);
    for (int i = 1;i <= n;++i) addedge(i+n,t,1);
    maxflow(s,t);
    dfs1(s,1);
    dfs1(t,0);
    cout << (ll)ans[0] * ans[1] <<endl;
    //cout << ans[0] << "ans" << ans[1] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

G

分析每一列，显然每一列至多只能有两个 1，否则为非法情况，答案为 0.

接下来考虑维护行和行之间的翻转关系，显然只有两种:

1. $i,j$ 必须一起翻转，此时为 $s_{i,p} = s_{j,c-p+1}$ 即二者有一个位置在对称后都为 1 的情况。
2. $i,j$ 必须一个翻转时，另一个不翻转，也就是 $s_{i,p} = s_{j,p}$，即二者有一个位置都为 1 的情况。

对于每一行，我们考虑使用 $i,i+n$ 来表示不翻转与翻转的情况，那么这里我们可以使用拓展域并查集来维护冲突关系。

对于关系 1，我们让 $x\rightarrow y,x+n\rightarrow y+n$ 也就是二者必须一起翻转/不翻转.

对于关系 2，我们让 $x\rightarrow y+n,y\rightarrow x +n$ 也就是一个翻转另一个就不翻转。

最后当且仅当 $\exist x,(x,x+n)$ 存在，也就是 $x$ 与 $x+n$ 在同一个集合里时为非法情况。对于其他情况，我们考虑一个连通块恰好对应了两种染色情况，答案也就是 $2^\text{连通块个数}$

时间复杂度 $O(rc)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
#define endl '\n'
const int N = 2e6 + 10;
const ll mod=1e9+7;
vector <vector<int> > a;
int r,c;
char s[N];
int ck[N],tmp[N];
int p[N];
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
ll qsm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void U(int a,int b){
    if(a!=b){
        p[a]=b;
    }
}
void solve() {
    cin >> r >> c;
    a.clear();

    for(int i=0;i<=2*r;i++){
        p[i]=i;
    }
    for(int i=0;i<=c;i++){
        ck[i]=tmp[i]=0;
    }
    a.resize(r+1);
    string pz;
    for (int i = 1;i <= r;++i) {
        cin >> s;
        a[i].resize(c+1);
        for (int j = 0;j < c;++j) {
            a[i][j+1] = s[j] - '0';
        }
    }

    for(int i=1;i<=c;i++){
        int cnt=0;
        for(int j=1;j<=r;j++){
            if(a[j][i]==1)cnt++;
            if(a[j][c-i+1]==1)cnt++;
        }
        if(cnt>2){
            cout<<0<<endl;
            return;
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            tmp[j]=ck[j];
        }
        for(int j=1;j<=c;j++){
            int x=j,y=c-j+1;
            if(y!=x&&a[i][j]&&tmp[y]){
                int pd1=tmp[y];
                int px=find(i),py=find(pd1);
                int px1=find(i+r),py1=find(pd1+r);

                if(px==py1||py==px1){
                    cout<<0<<endl;
                    return;
                }
                U(px,py);
                U(px1,py1);
            }else if(a[i][j]&&tmp[j]){
                int pd1=tmp[j];
                int px=find(i),py=find(pd1);
                int px1=find(i+r),py1=find(pd1+r);

                if(px==px1||py==py1||px==py){
                    cout<<0<<endl;
                    return;
                }
                U(px,py1);
                U(py,px1);
            }
            if(a[i][j])ck[j]=i;
        }
    }
    int cnt=0;
    for(int i=1;i<=2*r;i++){
        int pi=find(i);
        if(pi==i)cnt++;
    }
    cnt/=2;
    cout<<qsm(2,cnt)<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve(); 
    return 0;
}

K

神仙队友秒开，被我的对顶堆板子命名给坑了。这并不好笑.jpg

首先，对于题目这种公差为 1 的等差数列，我们有一个经典的处理即 $a_i : a_i - i$。那么符合条件的一个连续子序列就变成 $a$ 相等的一个连续子序列了。

接下来考虑原题就变成了要把 $a_i$ 变为一个相同的值 $x$，在满足代价的情况下，子序列长度最长为多长。根据一个经典的贪心，令 $x$ 为 $a_{l\dots r}$ 的中位数是最优秀的。

所以我们考虑维护一个滑动窗口，每次把 $a_i$ 加进窗口中，求出当前窗口的中位数，然后根据当前代价与 $k$ 的关系决定是否删除 $a_l$。对于动态求中位数，我们可以使用对顶堆来实现，因为这里涉及到删除，我们使用 std::multiset 来维护即可。

时间复杂度 $O(n\log n)$，因为每个数恰好被加入一次，至多被删除一次。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 5e5 + 10;
ll n,k,a[N];

int judge(int x,int y) {
    if (x > y) {
        return x-y;
    }
    else {
        return y-x;
    }
}

void solve() {
    cin >> n >> k;
    multiset <ll> xgd;
    multiset <ll,greater <ll>> bgd;
    for (int i = 1;i <= n;++i) cin >> a[i];
    for (int i = 1;i <= n;++i) a[i] -= i;

    //bgd.insert(0);
    ll s1 = 0,s2 = 0;
    int L = 1;
    int ans = 1;
    for (int i = 1;i <= n;++i) {
        if (bgd.empty()) {
            xgd.insert(a[i]);
            s2 += a[i];
        } else {
            if (a[i] > *bgd.begin()) xgd.insert(a[i]),s2 += a[i];
            else bgd.insert(a[i]),s1 += a[i];
        }
        while (judge(bgd.size(),xgd.size()) > 1) {
            if (bgd.size() > xgd.size()) {
                ll x = *bgd.begin();
                s2 += x;s1 -= x;
                xgd.insert(x);bgd.erase(bgd.begin());
            } else {
                ll x = *xgd.begin();
                s1 += x;s2 -= x;
                bgd.insert(x);xgd.erase(xgd.begin());
            }
        }
        //s1 bgd s2 xgd
        ll val1 = 0;
        if (bgd.size() >= xgd.size()) {
            val1 = *bgd.begin();
        } else {
            val1 = *xgd.begin();
        }
        /*cout <<"bgd:\n";
        for (auto x : bgd) cout << x << " ";
        cout <<"\ndgd:\n";
        for (auto x : xgd) cout << x << " ";
        cout << "\n";

        cout << i << ":" << val1 << "\n";*/
        ll ans1 = s2 - val1 * xgd.size() + val1 * bgd.size() - s1;
        //cout << i << " ans=" << ans1 << "\n";
        if (ans1 > k) {
            bool flag = 0;
            if (bgd.find(a[L]) != bgd.end()) {
                flag = 1;
                bgd.erase(bgd.find(a[L]));
                s1 -= a[L];
            }
            if (!flag) {
                if (xgd.find(a[L]) != xgd.end()) {
                    flag = 1;
                    xgd.erase(xgd.find(a[L]));
                    s2 -= a[L];
                }
            }
            ++L;
        } else {
            ans = max(ans,(int)(bgd.size() + xgd.size()));
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

M

场上开出来的简单计算几何题，可惜机时不太够了。

我们先把凸包求出来，然后考虑枚举不在凸包上的每个点。对于一个点 $P$，我们考虑把剩下 $n-1$ 个点按照极角排序。那么如果 $P$ 满足要求，也就是对于凸包上的每条边 $(p_{i-1},p_i)$ 都有他们的极角序是相邻的。暴力判断一下就可以了。

时间复杂度 $O(n^2\log n)$ 但是用 atan2 被卡了？学习了一个老哥的奇妙极角排序，大概也是利用叉乘但是因为整点，少了很多分类讨论（）

/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e3 + 10;
int dcmp(double a) {return a < -eps ? -1 : (a > eps ? 1 : 0);}
struct point {
    double x,y;point(int X = 0,int Y = 0) {x = X,y = Y;}
    friend point operator - (const point &a,const point &b) {
        point c;
        c.x = a.x - b.x;
        c.y = a.y - b.y;
        return c;
    } 
    friend double operator ^ (const point &a,const point &b) {
        return a.x * b.y - a.y * b.x;
    } 
}p[N],O;

bool cmp1(point a,point b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

int convexhull(point *P,int n,int *cp) {
    sort(P+1,P+n+1,cmp1);
    int t = 0;
    for (int i = 1;i <= n;++i) {
        while (t > 1 && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
        cp[++t] = i;
    }
    int st = t;
    for (int i =n-1;i >= 1;--i) {
        while (t > st && dcmp(((P[cp[t]] - P[cp[t-1]]) ^ (P[i] - P[cp[t-1]]))) <= 0) --t;
        cp[++t] = i;
    }
    return --t;
}

int n,cp[N];
bool vis[N];
double theta(point a) {return atan2(a.y,a.x);}
bool lt(double a, double b) { return a - b < -eps; }     // <
void psort(vector <int> &ps, point c)              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return dcmp((p[p1] - c) ^ (p[p2]-c)) > 0;
        //return lt(theta(p[p1] - c), theta(p[p2] - c));
    });
}
signed main() {
    //FO(test)
    read(n);
    for (int i = 1;i <= n;++i) read(p[i].x,p[i].y);
    int siz = convexhull(p,n,cp);
    /*
    for (int i = 1;i <= siz;++i) {
        cout << p[cp[i]].x << " " << p[cp[i]].y << endl;
    }
    */
    for (int i = 1;i <= siz;++i) vis[cp[i]] = 1;
    ll ans = 1;
    for (int x = 1;x <= n;++x) {
        if (vis[x]) continue;
        vector <int> qwq;
        for (int i = 1;i <= n;++i) {
            if (i != x) qwq.push_back(i);
        }
        psort(qwq,p[x]);
        int sz = qwq.size();
        if (vis[qwq[0]] && vis[qwq[sz-1]])++ans;
        for (int i = 1;i < sz;++i) {
            if (vis[qwq[i]] && vis[qwq[i-1]])++ans;
        }
    }
    cout <<ans;
    return 0;
}