发表更新解题报告

ICPC2023 南京站 个人简要题解

南京，俺仅谋过一次面的第四精神故乡！

单挑 5-688 好想找个队友一起打……单开 too 坐牢。

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

A

大众变态搜索题。

首先我们考虑，对于一只袋鼠来说如何判断是否可以存活？场上想了很多种方法，然后没看到 $n\times m\leq 10^3$ ，所以我们不难提出一个 $O(n^2m^2)$ 的暴力思路，我们对于每一只袋鼠 $i$ ，考虑枚举所有其他袋鼠 $j$ 进行判断是否合法。

具体而言，我们把 $(x_i,y_i,x_j,y_j)$ 这四个量压成一个状态，然后进行搜索，当且仅当存在一个状态 $(x_i^{‘},y_i^{‘},x_j^{‘},y_j^{‘})$ 使得 $(x_i^{‘},y_i^{‘})$ 在场上且 $(x_j^{‘},y_j^{‘})$ 不合法。代码实现里用了一些小技巧，反正可以写成类似记忆化的思想以保证复杂度，具体可以看代码实现。

记得使用 unordered_map，用 map 喜提 +1 难绷。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
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 pll pair<ll,ll>
#define mp make_pair

vector <vector<int> > ma;
vector <vector<int> > vis;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
int n,m,col;
vector <pii> ps;
unordered_map <int,int> sta,viss,rt;

bool valid(int x,int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void dfs1(int x,int y) {
    ps.push_back(mp(x,y));
    vis[x][y] = col;
    for (int i = 0;i < 4;++i) {
        int nx = x + dx[i],ny = y + dy[i];
        if (valid(nx,ny) && !ma[nx][ny]) {
            if (!vis[nx][ny]) {
                dfs1(nx,ny);
            }
        }
    }
}

int zip(pii x,pii y) {
    int a,b,c,d;a = x.first,b = x.second;c = y.first,d = y.second;
    return d + c * m + b * n * m + a * m * n * m;
}

pair<pii,pii> unzip(int x) {
    pii a,b;
    b.second = x % m;
    x /= m;
    b.first = x % n;
    x /= n;
    a.second = x % m;
    x /= m;
    a.first = x;
    return mp(a,b);
}

void bfs(int stt) {
    queue <int> q;
    q.push(stt);
    rt[stt] = stt;
    while (!q.empty()) {
        int nowsta = q.front();q.pop();
        pii s = unzip(nowsta).first,t = unzip(nowsta).second;
        int xx = s.first,yy = s.second;
        int xxx = t.first,yyy = t.second;
        //printf("xx(%d,%d)-(%d,%d)\n",xx,yy,xxx,yyy);
        bool flag = 0;
        for (int i = 0;i < 4;++i){
            int nx = xx + dx[i],ny = yy + dy[i];
            int nxx = xxx + dx[i],nyy = yyy + dy[i];
        //printf("nx(%d,%d)-(%d,%d)\n",nx,ny,nxx,nyy);
            if (!valid(nx,ny) || ma[nx][ny]) continue;
            if (!valid(nxx,nyy) || ma[nxx][nyy]) {
                sta[stt] = sta[nowsta] = 1;
                continue ;
            }
            if (!rt[zip(mp(nx,ny),mp(nxx,nyy))])q.push(zip(mp(nx,ny),mp(nxx,nyy))),rt[zip(mp(nx,ny),mp(nxx,nyy))] = stt;

        }
        //if (!flag) sta[nowsta] = -1;
    }
}

void solve() {
    cin >> n >> m;
    ma.clear();vis.clear();col = 0;
    sta.clear();
    ma.resize(n);
    vis.resize(n);
    rt.clear();
    int siz=  0;
    for (int i = 0;i < n;++i) {
        ma[i].resize(m);
        vis[i].resize(m);
        for (int j = 0;j < m;++j) {
            char c;cin >> c;
            if (c == 79) ma[i][j] = 1;
            else ma[i][j] = 0,++siz;
        }
    }
    int ans = 0;
    //bfs(zip(mp(1,4),mp(1,0)));
    //cout << sta[zip(mp(1,4),mp(1,0))] << "\n";

    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) {
            if (!ma[i][j] && !vis[i][j]) {
                ps.clear();
                ++col;
                dfs1(i,j);
                for (auto p1 : ps) {
                    int cnt = 0;
                    for (int xx = 0;xx < n;++xx) {
                        for (int yy = 0;yy < m;++yy) {
                            pii p2 = mp(xx,yy);
                            if (p2 == p1 || ma[xx][yy]) continue;
                            if (!rt[zip(p1,p2)]) bfs(zip(p1,p2));

                            if (sta[rt[zip(p1,p2)]]== 1) {
                                ++cnt;
                            }   
                        }
                    } 
                    //cout << p1.first << " " << p1.second << "!" << cnt << "\n";
                    if (cnt == siz - 1) {
                        ++ans;
                        //cout << p1.first << " " << p1.second << "!\n";
                    }
                }
            }
        }
    }


    cout << ans << "\n";
}

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

/*
1 
2 5
.OO..
.O.O.
*/

C

本来以为是数学题丢了没开，但是发现同校队伍过了一卡车感觉不对劲，顶真了一下就做完了

我们考虑把柿子转化一下：

$$
g\oplus (P-1)\bmod 1(\bmod P) \
\rightarrow g = (k\times P +1)\oplus (P-1) (k\in \Z)
$$

然后接下来我们不妨考虑一下 $k$ 和 $m$ 的关系，显然 $k \leq \lfloor \frac{m}{p}\rfloor$ ，但是你会发现由于 $\oplus$ 的存在，我们需要对 $[\lfloor \frac{m}{p}\rfloor,\lceil \frac{m}{p}\rceil]$ 这段手动计数一下以防漏了一些答案点，显然这个点数不多直接做就 OK 了。

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
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
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 pll pair<ll,ll>
#define mp make_pair

void solve() {
    ll p,m;cin >> p >> m;
    ll ans = m/p;
    //cout << "l :" << m/p << " r:" <<(m+(p-1))/p -1<<"\n";
    for (ll k = m/p;k <= (m+(p-1))/p;++k) {
        //cout << "now:" << ((k*p+1) ^ (p-1)) << "\n";
        if (((k*p+1LL) ^ (p-1LL)) <= m)++ans;
    }
    cout << ans << "\n";
}

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

F

神秘建图题。

首先我们发现，对于每一个位置 $i$，有用的仅仅只有最后一次修改，其他在这个位置上的修改都可以任意排序。

所以我们不妨记录一个位置最后是哪一次修改，记作 $pos_i$。我们只需要把所有在 $i$ 上的修改 $j$ 建边 $j\rightarrow pos_i$ ，显然搞出来一张 DAG。如何构造方案？有个比较通用的巧妙做法是求字典序最大的拓扑序，再判断是否与排列相同，相同就寄了。代码很好写，+1 是因为最开始想错了，前面哪个先后无所谓的。

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
95
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
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 pll pair<ll,ll>
#define mp make_pair

const int N = 1e5 + 10;
vector <int> G[N],rk[N];
int n,m,lst[N],deg[N];

bool cmp(int x,int y) {
    return x > y;
}

void solve() {
    cin >> n >> m;
    for (int i = 1;i <= m;++i) lst[i] = 0,rk[i].clear();
    for (int i = 0;i <= n;++i) G[i].clear(),deg[i] = 0;
    int cnt = 0;
    for (int i = 1;i <= n;++i) {
        cin >> cnt;
        for (int j = 1;j <= cnt;++j) {
            int x;cin >> x;
            rk[x].push_back(i);
            lst[x] = i;
        }
    }
    for (int i = 1;i <= m;++i) {
        if (!lst[i]) continue;
        for (auto x : rk[i]) {
            if (x != lst[i]) {
                G[x].push_back(lst[i]);
                ++deg[lst[i]];
                //cout << "e:" << x << " " << lst[i] <<"\n";
            }
        }
    }
    int tot = 0;
    queue <int> q;
    for (int i = 1;i <= n;++i) {
        if (!deg[i]) {
            ++tot;
            G[0].push_back(i);
            ++deg[i];
        }
    }
    q.push(0);
    vector <int> ans;
    while (!q.empty()) {
        int x = q.front();q.pop();
        //cout << x << " ";
        if (G[x].size()) sort(G[x].begin(),G[x].end(),cmp);
        if (x) ans.push_back(x);
        for (auto y : G[x]) {
            //cout << "(" << x << "," << y << ")\n";
            if (!--deg[y]) {
                q.push(y);
            }
        }
    }
    bool flag = 0;
    for (int i = 0;i < n;++i) {
        //printf("ans%d:%d i+1 = %d\n",i,ans[i],i+1);
        if (ans[i] != i+1) {
            flag = 1;
        }
    }
    if (!flag) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        for (auto x : ans) 
        cout << x << " ";
        cout << "\n";
    }
}

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

/*
1
1 3
2 2 1
*/

G

巧妙的贪心题！

首先我们考虑，我们对于 $k$ 个免费取的物品显然是必定取 $k$ 个，然后我们应当取的是哪些？显然应该从体积最大的开始选起，所以不难想到先把体积从小到大排序。

但是很快你就会发现这个贪心有点问题，所以我们改进一下，考虑 $dp_i$ 代表前 $i$ 个物品来做背包，后 $n-i$ 个物品类似滑动窗口一样贪心取 $k$ 个价值最大的即可。

还是挺好玩的题

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
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
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 pll pair<ll,ll>
#define mp make_pair

const int N = 1e4 + 10;

int n,W,k;
ll f[10010],t[N];
pll c[10010];

multiset <ll> st;
signed main() {
    ios::sync_with_stdio(false);
    //cin.tie(0);//cout.tie(0);
    cin >> n >> W >> k;
    for (int i = 1;i <= n;++i) {
        cin >> c[i].first >> c[i].second;
    }    
    sort(c+1,c+1+n);
    ll ans = 0;
    
    ll sum = 0;
    if (k) {
        for (int i = n;i >= n - k + 1;--i) {
            sum += c[i].second;
            st.insert(c[i].second);
            t[i] = sum;
        }

        for (int i = n - k;i >= 1;--i) {
            ll now = *st.begin();
            if (c[i].second > now) {
                sum = sum - now + c[i].second;
                st.erase(now);
                st.insert(c[i].second);
            }
            t[i] = sum;
        }
    }
    
    for (int i = 1;i <= n;++i) {
        for (int j = W;j>= 0;--j) {
            if (j >= c[i].first) {
                f[j] = max(f[j],f[j-c[i].first] + c[i].second);
            }
        }
        ans = max(ans,t[i+1] + f[W]);
    }
    
    
    cout << ans << "\n";
    return 0;
}

I

签到题，直接等价于区间覆盖就可以了。

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
/*
Undo the destiny.
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <limits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
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 pll pair<ll,ll>
#define mp make_pair
const int N = 1e5 + 10;
pii p[N];
int n,m;

void solve() {
    cin >> n >> m;
    for (int i = 1;i <= m;++i) cin >> p[i].first >> p[i].second;
    sort(p+1,p+1+m);
    int lsta = 0,lstb = 0;
    bool flag = 0;
    for (int i = 1;i <= m;++i) {
        int cnt = p[i].first - p[i].second;
        if (cnt > lsta || cnt == lstb) {
            lsta = p[i].first;lstb = cnt;
        } else {
            flag = 1;
            break;
        }
    }
    if (flag) puts("No");
    else puts("Yes");
}


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

L

很巧妙的贪心转化……吃个饭回来写

M

小清新 DS，吃个饭回来写

ICPC2023 南京站 个人简要题解

https://doubeecat.cn/post/ICPC2023-南京站-个人简要题解/

作者

Doubeecat

发布于

2024-10-16

更新于

2025-09-18

许可协议

关注我

链接

分类

最新文章

归档

标签

2-SAT1
BFS1
BSGS1
CDQ分治1
CV7
CV , transformer1
CV, 分割1
CV, 多模态1
CV,Transformer1
CV,分割2
CV,机器学习1
DFS序1
DL2
DP20
Dijkstra1
Dirchlet 卷积1
ETT1
Kruskal2
Kruskal 重构树2
LCA1
MST2
NTT1
RMQ1
Tarjan4
Transformer2
bitset1
codeforces1
hash1
nim游戏1
transformer1
二分3
二分图1
二维数点1
位运算2
决策单调性1
凸包1
分块2
分治2
分治NTT1
割点1
区间DP2
单调栈3
博弈论1
图论12
多项式1
字符串1
容斥原理2
差分1
差分约束1
并查集2
思维8
扫描线2
拉格朗日插值1
拓扑排序2
搜索1
数位DP2
数学10
数据结构5
数论5
数论分块1
整体二分1
暴力3
最大流2
最小割2
最小环1
最小费用最大流1
最短路3
杜教筛1
构造3
枚举1
树1
树上问题8
树形DP3
树状数组3
树链剖分2
根号分治2
欧拉函数1
毒瘤1
状压DP1
矩阵1
神经网络1
积性函数1
线性DP3
线性基1
线段树8
线段树分治1
组合数学1
缩点1
网络流2
背包5
莫比乌斯反演1
计数问题2
负环1
贪心1
递归2
闵可夫斯基和1
×