首页 > 其他分享 >The 2023 ICPC Asia Macau Regional Contest (The 2nd Universal Cup. Stage 15: Macau)

The 2023 ICPC Asia Macau Regional Contest (The 2nd Universal Cup. Stage 15: Macau)

时间：2024-03-02 20:23:04浏览次数：31  
标签：std now 15 Macau Contest int ++ include define

Preface

最幽默的一集

这场开局感觉三个人都有点发昏了，前3h30min就出了两个题，有种要打铁了的感觉

后面想着干脆保个银牌稳扎稳打吧，没想到后面1h连着出了四个题成功冲到银首

最后徐神好像也会G这个博弈了，如果前面不犯病的话感觉还真有机会出7题的说

A. (-1,1)-Sumplete

徐神基本被这题关了一整场，主要刚开始想复杂了一直在想网络流，到后面才发现是个顶针题

不难发现可以把所有的\(-1\)都转化成\(1\)，因此问题变成确定每个格子的值是\(0/1\)来满足行列的限制

考虑一行一行地确定行元素，假设当前行需要有\(x\)个\(1\)，那么不妨找出此时列和最大的\(x\)列，优先把这些位置置为\(1\)即可

直接每次用sort来做的话复杂度是\(O(n^2\log n)\)的，可以用计数排序优化成\(O(n^2)\)，不过没有必要的说

#include <bits/stdc++.h>

int n;
int m[4000][4000], s[4000][4000], r[4000], c[4000];

void select(int i, int j) {
    s[i][j] ^= 1;
    r[i] += m[i][j], c[j] += m[i][j];
    m[i][j] = -m[i][j];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for(int i = 0; i < n; ++i) {
        std::string s; std::cin >> s;
        for(int j = 0; j < n; ++j)
            m[i][j] = (s[j] == '+' ? 1 : -1);
    }
    
    for(int i = 0; i < n; ++i) std::cin >> r[i], r[i] = -r[i];
    for(int i = 0; i < n; ++i) std::cin >> c[i], c[i] = -c[i];

    for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
        if(m[i][j] > 0) select(i, j);

    for(int i = 0; i < n; ++i) if(c[i] < 0 || r[i] < 0)
        return std::cout << "No\n", 0;
    
    // for(int i = 0; i < n; ++i) {
    //     for(int j = 0; j < n; ++j) std::cout << s[i][j];
    //     std::cout << "\n";
    // }

    std::vector<int> rr(n), cc(n);
    for(int i = 0; i < n; ++i) rr[i] = cc[i] = i;
    std::sort(rr.begin(), rr.end(), [](int x, int y) {
        return r[x] > r[y];
    });

    for(int i: rr) {
        std::sort(cc.begin(), cc.end(), [](int x, int y) {
            return c[x] > c[y];
        });
        for(int j: cc) {
            if(r[i] <= 0) break;
            if(c[j] > 0) select(i, j);
        }
    }

    // for(int i = 0; i < n; ++i) {
    //     for(int j = 0; j < n; ++j) std::cout << s[i][j];
    //     std::cout << "\n";
    // }
    // for(int i = 0; i < n; ++i) std::cerr << c[i] << char(i == n - 1 ? 10 : 32); 
    // for(int i = 0; i < n; ++i) std::cerr << r[i] << char(i == n - 1 ? 10 : 32);

    for(int i = 0; i < n; ++i) if(c[i] || r[i]) return std::cout << "No\n", 0;

    std::cout << "Yes\n";
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) std::cout << s[i][j];
        std::cout << "\n";
    }

    return 0;
}

B. Basic Equation Solving

啥玩意，一眼不可做

C. Bladestorm

唉炉批，唉反向亵渎，唉做不来

D. Graph of Maximum Degree 3

纯诈骗题，主要出题人出了个模\(998244353\)直接下了思想钢印让我以为是个Counting Problem，一直到很后面才意识到是个思博题

考虑对于一个\(m\)个点的连通块，显然其中至多有\(\frac{3m}{2}\)条边；如果想要让这个连通块合法，那么其中至少要有\(2(m-1)\)条边（每种颜色至少是棵树）

因此需要满足一个先决条件：\(\frac{3m}{2}\ge 2(m-1)\)，然后就得到了\(m\le 4\)，即符合条件的连通块大小\(\le 4\)

那么这题就很trivial了，首先连通块大小为\(1,2\)的情况很显然，大小为\(3\)时我们需要先找出一条边\((u,v)\)满足这两点之间有两种颜色的边，然后再检验\(u,v\)的另外一个邻点是否相同并且边颜色不同即可

连通块大小为\(4\)的情况画一下会发现只有一种形态，因此我们可以先搜索出所有连通块，然后对大小为\(4\)的暴力检验一下是否合法即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<utility>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,m,x,y,z,ans,vis[N],fa[N]; vector <int> v[N]; set <pi> edges[2]; vector <pi> all[N];
inline int getfa(CI x)
{
    return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline int check(vector <int> pnt)
{
    RI i,j; for (auto x:pnt) fa[x]=x;
    for (i=0;i<pnt.size();++i)
    for (j=1;j<pnt.size();++j)
    if (edges[0].count(pi(pnt[i],pnt[j]))) fa[getfa(pnt[i])]=getfa(pnt[j]);
    for (i=1;i<pnt.size();++i)
    if (getfa(pnt[i])!=getfa(pnt[0])) return 0;
    for (auto x:pnt) fa[x]=x;
    for (i=0;i<pnt.size();++i)
    for (j=1;j<pnt.size();++j)
    if (edges[1].count(pi(pnt[i],pnt[j]))) fa[getfa(pnt[i])]=getfa(pnt[j]);
    for (i=1;i<pnt.size();++i)
    if (getfa(pnt[i])!=getfa(pnt[0])) return 0;
    return 1;
}
inline void DFS(CI now,vector <int>& pnt)
{
    vis[now]=1; pnt.push_back(now);
    for (auto [to,c]:all[now]) if (!vis[to]) DFS(to,pnt);
}
int main()
{
    RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        all[x].push_back(pi(y,z)); all[y].push_back(pi(x,z));
        edges[z].insert(pi(x,y)); edges[z].insert(pi(y,x));
        if (z==0) v[x].push_back(y),v[y].push_back(x);
    }
    for (i=1;i<=n;++i) for (auto j:v[i])
    if (edges[1].count(pi(i,j)))
    {
        ++ans; pi it1=pi(-1,-1),it2=pi(-1,-1);
        for (auto [to,c]:all[i]) if (to!=j) it1=pi(to,c);
        for (auto [to,c]:all[j]) if (to!=i) it2=pi(to,c);
        if (it1.fi==-1||it2.fi==-1) continue;
        if (it1.fi==it2.fi&&it1.se!=it2.se) ++ans;
    }
    for (ans/=2,ans+=n,i=1;i<=n;++i) if (!vis[i])
    {
        vector <int> pnt; DFS(i,pnt);
        if (pnt.size()==4) ans+=check(pnt);
    }
    return printf("%d",ans),0;
}

E. Inverse Topological Sort

感觉这题很像个CF题啊，经典没有证明全靠猜测

首先不难想到对于\(\{a_i\}\)序列，我们找出其所有的逆序对\((a_i,a_j)\)，将所有\(a_i\to a_j\)都连上边即可满足限制；对于\(\{b_i\}\)序列类似

但这样边数会达到\(O(n^2)\)量级显然就炸了，因此考虑优化，不难发现当我们连\(x\to y\to z\)后就天然满足了\(x\to z\)的限制，因此不难想到尽量连近的，即：

  • 对于每个\(a_j\)，找到\(i<j\)且下标最大的\(i\)使得\(a_i>a_j\)，连边\(a_i\to a_j\)
  • 对于每个\(b_j\)，找到\(i<j\)且下标最大的\(i\)使得\(b_i<b_j\)，连边\(b_i\to b_j\)

不难发现这样可以用最少的连边数量构造出满足两个序列要求的图，然后我们对构造出来的图进行检验

如果图中有环则显然不合法，同时如果在生成的图中再求出其字典序最小/最大的拓扑序和原来不同了，则亦无解

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<utility>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,a[N],b[N],pos[N],deg[N]; vector <int> v[N];
int main()
{
    RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]); set <pi> s;
    for (i=1;i<=n;++i) pos[a[i]]=i;
    for (i=n;i>=1;--i)
    {
        auto it=s.lower_bound(pi(pos[i],0));
        if (it!=s.begin()) v[(--it)->se].push_back(i);
        s.insert(pi(pos[i],i));
    }
    for (s.clear(),i=1;i<=n;++i) pos[b[i]]=i;
    for (i=1;i<=n;++i)
    {
        auto it=s.lower_bound(pi(pos[i],0));
        if (it!=s.begin()) v[(--it)->se].push_back(i);
        s.insert(pi(pos[i],i));
    }
    for (i=1;i<=n;++i) sort(v[i].begin(),v[i].end()),v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
    for (i=1;i<=n;++i) for (auto j:v[i]) ++deg[j];
    queue <int> q; for (i=1;i<=n;++i) if (!deg[i]) q.push(i);
    while (!q.empty())
    {
        int now=q.front(); q.pop();
        for (auto to:v[now]) if (!--deg[to]) q.push(to);
    }
    for (i=1;i<=n;++i) if (deg[i]) return puts("No"),0;
    for (i=1;i<=n;++i) for (auto j:v[i]) ++deg[j];
    priority_queue <int,vector <int>,greater <int>> sml;
    for (i=1;i<=n;++i) if (!deg[i]) sml.push(i);
    vector <int> tmp; while (!sml.empty())
    {
        int now=sml.top(); sml.pop(); tmp.push_back(now);
        for (auto to:v[now]) if (!--deg[to]) sml.push(to);
    }
    for (i=1;i<=n;++i) if (a[i]!=tmp[i-1]) return puts("No"),0;
    for (i=1;i<=n;++i) for (auto j:v[i]) ++deg[j];
    priority_queue <int> big;
    for (i=1;i<=n;++i) if (!deg[i]) big.push(i);
    tmp.clear(); while (!big.empty())
    {
        int now=big.top(); big.pop(); tmp.push_back(now);
        for (auto to:v[now]) if (!--deg[to]) big.push(to);
    }
    for (i=1;i<=n;++i) if (b[i]!=tmp[i-1]) return puts("No"),0;
    int cnt=0; for (i=1;i<=n;++i) cnt+=v[i].size();
    puts("Yes"); printf("%d\n",cnt);
    for (i=1;i<=n;++i) for (auto j:v[i]) printf("%d %d\n",i,j);
    return 0;
}

F. Land Trade

做不来，投降捏

G. Parity Game

徐神好像会了但我们前期实在是太唐了没时间写了，坐等徐神赛后补题了

H. Random Tree Parking

本来一点头猪都没有，后面祁神想到一个关键的转化马上就茅塞顿开了

考虑对于某个点\(i\)定义\(val_i\)表示最后选中\(i\)点的次数，则最后只要搞个可重全排列就可以快速得到总方案数

考虑我们需要满足哪些性质，对于每个点\(i\)，设\(sum_i\)表示\(i\)点子树内\(val\)之和，\(sz\)表示\(i\)点子树大小，\(dep_i\)表示\(i\)点深度，则：

  • \(sz_i\le sum_i\)，这是显而易见的，不然最后\(i\)子树就没法被填满了
  • \(sum_i-sz_i\le dep_i\)，这是由于将子树\(i\)填满后，多出的部分会自动向上补，如果溢出的超过了\(dep_i\)那么就会有点飞到外面去了，同样不合法

因此我们得到每个点权值和的范围是\([sz_i,sz_i+dep_i]\)，不难发现这个区间的大小只和\(dep_i\)有关

由于题目中保证给出的树纯随机，因此对于所有点的\(dep_i\)是\(O(\log n)\)级别的，那么我们就可以大力背包转移了

总复杂度算不太清楚，要么是两个还是三个\(\log n\)的来着，总之能跑过去

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int n,x,sz[N],dep[N],fact[N],ifac[N]; vector <int> v[N],f[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
    for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
    RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
    for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline void inc(int& x,CI y)
{
    if ((x+=y)>=mod) x-=mod;
}
inline void DFS(CI now=1)
{
    sz[now]=1; for (auto to:v[now]) dep[to]=dep[now]+1,DFS(to),sz[now]+=sz[to];
    RI i,j; int L=0,R=0; static int g[N],tmp[N]; g[0]=1;
    for (auto to:v[now])
    {
        for (i=L+sz[to];i<=R+sz[to]+dep[to];++i) tmp[i]=0;
        for (i=L;i<=R;++i) for (j=sz[to];j<=sz[to]+dep[to];++j)
        inc(tmp[i+j],1LL*g[i]*f[to][j-sz[to]]%mod);
        for (L+=sz[to],R+=sz[to]+dep[to],i=L;i<=R;++i) g[i]=tmp[i];
    }
    f[now].resize(dep[now]+1);
    for (i=L;i<=R;++i) for (j=sz[now];j<=sz[now]+dep[now];++j)
    if (i<=j) inc(f[now][j-sz[now]],1LL*g[i]*ifac[j-i]%mod);
}
int main()
{
    RI i; for (scanf("%d",&n),i=2;i<=n;++i)
    scanf("%d",&x),v[x].push_back(i);
    return init(n),DFS(),printf("%d\n",1LL*fact[n]*f[1][0]%mod),0;
}

I. Refresher into Midas

虽然这题定位是签到，但也卡了我们队一会的说

注意到\(m\)的范围是有限制的，这就提示我们可能是用\(O(m)\)的做法，因此很容易想到按照时间顺序DP

由于我们不可能记下所有时刻两种道具的状态，因此不妨直接拿一个通用的情形来统计，钦定只考虑这种状态

由于开局我们的操作必然是刷钱——刷新球——刷钱，然后两个都进入CD，因此考虑设\(f_i\)表示到第\(i\)秒且两个道具都恰好进入CD时，最多能刷几次钱

转移的话就分两种情况，一种是刷新球CD一好就马上用；另一种是刷新球CD好了先等到最近的一次刷钱CD也转好，然后一起操作

具体情况看代码，最后不要忘记讨论下不用刷新球的情况来更新答案

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,a,b,m,f[N];
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        RI i; for (scanf("%d%d%d",&a,&b,&m),i=0;i<=m;++i) f[i]=0;
        int ans=0; for (f[0]=2,i=0;i<=m;++i) if (f[i]!=0)
        {
            ans=max(ans,f[i]+(m-i)/a);
            if (i+b<=m) f[i+b]=max(f[i+b],f[i]+(1+b/a));
            if (i+(b+a-1)/a*a<=m) f[i+(b+a-1)/a*a]=max(f[i+(b+a-1)/a*a],f[i]+(1+(b+a-1)/a));
        }
        printf("%d\n",ans*160);
    }
    return 0;
}

J. Teleportation

签到题，但是也腐乳了我们队好久，后面还是徐神想A题的空档给了个思路要再建一排辅助点才通过

考虑将每个点拆成两个\(i,n+i\)，钦定每个点\(i\in[0,n-1]\)只能用传送操作直接走到点\(n+(i+a_i)\bmod n\)，花费\(1\)的代价

然后不妨在所有的\(i\in[n,2n-1]\)这些点之间顺时针连一个环，环上的点边权为\(1\)，在这上面走等价于在传送之前拨动指针

最后给每个点\(n+i\)向\(i\)连边权为\(0\)的边表示回到真实的点，然后跑一个0/1BFS即可

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

using pii = pair<int, int>;

const int N = 2e5+5;
const int INF = (int)1e18+5;
int n, x, dis[N];
vector<pii> G[N];
int que[N*2], fr=N, ed=N-1;
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    for (int i=0; i<n; ++i){
        int a; cin >> a;
        G[i].emplace_back(n+(i+a)%n, 1);
        G[n+i].emplace_back(n+(i+1)%n, 1);
        G[n+i].emplace_back(i, 0);
    }
    for (int i=0; i<n*2; ++i) dis[i]=INF;
    dis[0]=0;
    que[++ed]=0;
    while (fr<=ed){
        int x=que[fr++];
        for (auto [v, w] : G[x]){
            if (dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                if (1==w) que[++ed]=v;
                else que[--fr]=v;
            }
        }
    }
    // puts("dis:"); for (int i=0; i<n; ++i) printf("%lld ", dis[i]); puts("");
    cout << dis[x] << '\n';
    return 0;
}

K. Understand

开场就开到的一个题，但好像是防AK题，寄！

Postscript

感觉THU出的题好劲啊，而且好像和我们队都没什么相性打起来巨难受

希望下赛季别遇到THU出题的场QWQ

标签：std,now,15,Macau,Contest,int,++,include,define
From： https://www.cnblogs.com/cjjsb/p/18049170

相关文章

  • AtCoder Beginner Contest 342
    B-Whichisahead?难度:⭐题目大意给定n个人的位置顺序,现有m次询问,给出a,b两个人,问谁在前面;解题思路模拟就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl......
  • YL 模拟赛总结 15
    ProblemT1感觉是最难的。考虑贪心。首先对牛的按左端点进行排序，然后对于每只鸡去考虑匹配哪头牛。具体地，开一个小根堆，然后对于每只鸡\(t_i\)，将\(a_i\let_i\)的牛放入堆中，此时堆中存放的是候选的牛。然后对于堆中的牛，将\(b_i<t_i\)的牛弹出。此时堆中的牛均是合法的......
  • AtCoder DP Contest vp 记录
    题单。A从\(i-1\)与\(i-2\)转移即可。#include<bits/stdc++.h>usingnamespacestd;intn;inth[100031];intdp[100031];intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>h[i]; memset(dp,0x3f,sizeof(dp)); dp[1]=0; for(inti=1;i<......
  • CF15E
    参考（先看）这个题解最后的式子写错了，看最后（注意一下算层数要n/=2！）这里面关于\(ans\)的用法：为什么是\(2\timesans^2+8\timesans+10\)已经讲得很清楚了。主要补充一下怎么求\(ans\)的部分。如图，三个决策点的所在部分可以视作一个三角形+若干个斜着的梯形。经过这......
  • CF1915D Unnatural Language Processing 题解
    容易发现音节的划分不仅要求子串形如\(\texttt{CV}\)或\(\texttt{CVC}\)，并且接下来的两个字符也必须是\(\texttt{CV}\)，不然会导致无法划分下去。于是我们遍历字符串，找出所有满足上述条件的子串，记录需要输出\(\texttt{.}\)的位置即可。实现：intn;strings,ans,t="";cin>......
  • CF1915E Romantic Glasses 题解
    我们考虑维护\(sum_i\)表示前\(i\)个数中偶数下标的数之和与奇数下标的数之和之差，其中\(sum_0=0\)。若在某一时刻，有\(sum_i=sum_j(j<i)\)，说明\(j\simi\)中偶数下标的数之和与奇数下标的数之和之差为\(0\)。这个使用map判断即可。实现：intn,f=0;cin>>n;m.clear()......
  • 代码随想录算法训练营day11 | leetcode 20. 有效的括号、1047. 删除字符串中的所有相
    目录题目链接：20.有效的括号-简单题目链接：1047.删除字符串中的所有相邻重复项-简单题目链接：150.逆波兰表达式求值-中等题目链接：20.有效的括号-简单题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右......
  • nrf52832蓝牙开发踩过的坑-京鸿通信科技-15507589165
    转自：http://www.manongjc.com/detail/26-htjapkxksqidwuo.html本文章向大家介绍nrf52832蓝牙开发踩过的坑，主要包括nrf52832蓝牙开发踩过的坑使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。接触nrf52832芯片已经有一段时间了......
  • 比特币暴涨逼近历史最高点；阿里云全线降价20%丨 RTE 开发者日报 Vol.155
     开发者朋友们大家好： 这里是「RTE开发者日报」，每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE（RealTimeEngagement）领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」，但内容仅代表编辑的......
  • 洛谷题单指南-二分查找与二分答案-P2678 [NOIP2015 提高组] 跳石头
    原题链接：https://www.luogu.com.cn/problem/P2678题意解读：最短跳跃距离越大，要移走的石头就越多，因此可以根据最短跳跃距离的不同把情况分为两类：移走的石头数<=M、移走的石头数>M，对最短跳跃距离二分即可。解题思路：二分的判定条件如下：对于给定最短跳跃距离，需要计算移走的石头数，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99