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

单挑 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 难绷。

/*
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 了。

/*
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 是因为最开始想错了，前面哪个先后无所谓的。

/*
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 个价值最大的即可。

还是挺好玩的题

/*
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

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

/*
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，吃个饭回来写