首页 > 其他分享 >The 2024 ICPC Asia East Continent Online Contest (I)

The 2024 ICPC Asia East Continent Online Contest (I)

时间：2024-09-23 16:51:25浏览次数：9  
标签：CI const Contest int Asia ICPC include RI define

Preface

打的一坨，直接被 Div.2 学弟吊起来打

这场主要是中期的 Easy~mid 写的太慢，导致中后期题没时间写

同时封榜后的决策也有点问题，没有全队 All-in 一个题而是让徐神去写当时 1/27 的 K，虽然可能徐神来想 H 我们也出不来但感觉还是跟榜适合我们队的 level

赛后发现 H 反着填右括号就是很典的 Flow 了，B 根据学长说是个很典的 Min_25 筛，这下被干烂了

A. World Cup

祁神开场写的，我题目都没看，好像是个手玩打表题

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

void solve(){
    vector<int> A(32);
    for (int i=0; i<32; ++i) cin >> A[i];
    int val = A[0];
    sort(A.begin(), A.end());
    int pos = lower_bound(A.begin(), A.end(), val) - A.begin();
    if (pos >= 31) cout << "1\n";
    else if (pos >= 27) cout << "2\n";
    else if (pos >= 13) cout << "4\n";
    else if (pos >= 6) cout << "8\n";
    else if (pos >= 2) cout << "16\n";
    else cout << "32\n";
}

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

B. Graph

首先要注意到，题目中的要求等价于对于所有 \(d\in[1,n]\)，所有 \(d\) 的倍数对应的点形成的导出子图连通

从大到小考虑每个 \(d\)，并将所有 \(d\) 的倍数对应的点重编号为 \(1\sim m\)，考虑将这些点连通

由于要求用最少的边因此一定是连成生成树，生成树计数首先考虑 prufer 序列

假设此时图中共有 \(k\) 个连通块，每个连通块大小为 \(x_1,x_2,\dots,x_k\)，则连通它们的方案数为 \((\sum x_i)^{k-2}\times \prod x_i\)

因此现在的问题在于计算连通块的数量（即之前有多少个点已经连通）

推一下会发现重标号的点编号如果是合数则之前一定连通了，同时对于 \(\le \frac{m}{2}\) 的素数 \(p\)，它之前一定通过 \(2p\) 与 \(2\) 连通了

因此我们只要知道 \([\frac{m}{2}+1,m]\) 中的素数个数，它们都是独立的孤点；同时还有 \(1\) 作为孤点；剩下的所有点在一个连通块中；此时很容易计算方案数

不难发现最后计算答案可以除法分块，而求区间素数个数可以用 Min_25 筛解决，复杂度 \(O(\frac{n^{\frac{3}{4}}}{\log n})\)

#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int mod=998244353;
namespace Min25_Sieve
{
	const int N=1e6+5;
	int n,lim,pri[N],cnt,vis[N],id1[N],id2[N],g[N],w[N],idx;
	inline int ID(CI x)
	{
		return x<=lim?id1[x]:id2[n/x];
	}
	inline void init(CI nn)
	{
		n=nn; lim=(int)sqrt(n); 
		for (RI i=2;i<=lim;++i)
		{
			if (!vis[i]) pri[++cnt]=i;
			for (RI j=1;j<=cnt&&i*pri[j]<=lim;++j)
			if (vis[i*pri[j]]=1,i%pri[j]==0) break;
		}
		for (RI l=1,r;l<=n;l=r+1)
		{
			r=n/(n/l); w[++idx]=n/l;
			if (n/l<=lim) id1[n/l]=idx;
			else id2[n/(n/l)]=idx;
			g[idx]=w[idx]-1;
		}
		for (RI j=1;j<=cnt;++j)
		for (RI i=1;i<=idx;++i)
		{
			if (pri[j]*pri[j]>w[i]) break;
			g[i]-=g[ID(w[i]/pri[j])]-(j-1);
		}
	}
	inline int work(CI n)
	{
		return n<=1?0:g[ID(n)];
	}
};
using namespace Min25_Sieve;
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 int solve(CI m)
{
	if (m<=2) return 1;
	if (m==3) return 3;
	int tot=work(m)-work(m/2);
	return quick_pow(m%mod,tot)*(m%mod-(tot+1)%mod+mod)%mod;
}
signed main()
{
	int n; scanf("%lld",&n);
	init(n); int ans=1;
	for (RI l=1,r;l<=n;l=r+1)
	r=n/(n/l),(ans*=quick_pow(solve(n/l),r-l+1))%=mod;
	return printf("%lld",ans),0;
}

C. Permutation Counting 4

这题感觉真没那么简单吧，不知道为啥比赛的时候被过穿了，最后还得靠徐神发力

考虑定义一个 \(n\times n\) 的行列式，其中第 \(i\) 行第 \([l_i,r_i]\) 列为 \(1\)，其余位置为 \(0\)

考虑对于原题方案数的计数，比如我们要确定第 \(i\) 个位置填什么，其方案数等价于将第 \(i\) 行所有 \(1\) 的位置删去，并删去与其同行同列的元素后的子行列式方案数之和

不难发现这个式子和行列式的定义只差了个符号，而在模意义下 \((-1)^{i+j}\) 的系数可以视为加法，因此原题的方案数的奇偶性等价于行列式的值的奇偶性

由于这个行列式有性质，可以用一些数据结构来优化高斯消元求解行列式的过程，复杂度 \(O(n\log^2 n)\)

#include <bits/stdc++.h>

int work() {
    int n; std::cin >> n;
    static std::set<int> hkr[1000001];
    
    for(int i = 1; i <= n; ++i) hkr[i].clear();

    int flag = true;
    for(int i = 1, l, r; i <= n; ++i) {
        std::cin >> l >> r;
        // std::cerr << "l, r = " << l << ", " << r << char(10);
        if(hkr[l].find(r) != hkr[l].end()) flag = false;
        hkr[l].insert(r);
    }
    if(!flag) return 0;

    for(int i = 1; i <= n; ++i) {
        if(hkr[i].empty()) return 0;
        auto front = hkr[i].begin(); int val = *front; hkr[i].erase(front);
        if(val == n) continue;
        #define nxt hkr[val + 1]
        if(nxt.size() < hkr[i].size()) std::swap(hkr[i], nxt);
        for(auto r: hkr[i]) {
            if(nxt.find(r) == nxt.end()) nxt.insert(r);
            else return 0;
        }
        #undef nxt
    }

    return 1;
}

int main() {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t; while(t--) std::cout << work() << char(10);
    return 0;
}

F. Make Max

思路很简单，考虑从小到大将每个同色段的值进行变化

对于当前 \([l,r]\) 的同色段，求出其左右两侧的值 \(L,R\)，手玩一下会发现将其变为较小的一方一定最优

用并查集维护同色段，模拟整个过程即可，注意当 \(L=R\) 时要特别处理一下

后面发现好像直接单调栈求一下两边第一个大于该位置的元素然后递推就行，怪不得比赛的时候这题过得这么快

#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=2e9;
int t,n,a[N],rst[N],L[N],R[N]; set <int> pos[N];
inline int getL(CI x)
{
    return L[x]==x?x:L[x]=getL(L[x]);
}
inline int getR(CI x)
{
    return R[x]==x?x:R[x]=getR(R[x]);
}
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d",&n); long long ans=0;
        for (RI i=1;i<=n;++i) scanf("%d",&a[i]),rst[i]=a[i];
        sort(rst+1,rst+n+1); int m=unique(rst+1,rst+n+1)-rst-1;
        for (RI i=1;i<=n;++i) a[i]=lower_bound(rst+1,rst+m+1,a[i])-rst;
        for (RI i=0;i<=n+1;++i) L[i]=R[i]=i;
        for (RI i=1;i+1<=n;++i) if (a[i]==a[i+1]) L[i+1]=getL(i);
        for (RI i=n-1;i>=1;--i) if (a[i]==a[i+1]) R[i]=getR(i+1);
        for (RI i=1;i<=n;++i) if (getL(i)==i) pos[a[i]].insert(i);
        for (RI i=1;i<=m;++i)
        {
            for (auto x:pos[i])
            {
                int l=getL(x),r=getR(x),vl=INF,vr=INF;
                if (l-1>=1) vl=a[l-1];
                if (r+1<=n) vr=a[r+1];
                //printf("x = %d\n",x);
                //printf("l = %d; r = %d\n",l,r);
                //printf("vl = %d; vr = %d\n",vl,vr);
                if (vl==vr)
                {
                    if (vl==INF) continue;
                    R[l-1]=getR(l); L[l]=getL(l-1);
                    L[r+1]=getL(r); R[r]=getR(r+1);
                    ans+=r-l+1; pos[vl].erase(r+1);
                } else if (vl<vr)
                {
                    R[l-1]=getR(l); L[l]=getL(l-1);
                    ans+=r-l+1;
                } else
                {
                    L[r+1]=getL(r); R[r]=getR(r+1);
                    ans+=r-l+1;
                }
            }
            pos[i].clear();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

G. The Median of the Median of the Median

刚开始犯病了一直想着直接算答案，而没有想到中位数的经典 trick 二分

考虑直接二分答案 \(x\)，不妨把 \(\le x\) 的位置都置为 \(1\)，\(>x\) 的位置置为 \(-1\)

此时求 \(b_{l,r}\) 的值就只用维护前缀和即可，此时得到每个 \(b_{l,r}\) 和 \(x\) 的大小关系

同理，求 \(c_{l,r}\) 时就等价于一个二维前缀和的过程，此时得到每个 \(c_{l,r}\) 和 \(x\) 的大小关系

最后再求 \(c_{l,r}\) 的中位数即可得到检验 \(x\) 的方法，总复杂度 \(O(n^2\log n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int n,r[N],a[N],pfx[N],sum[N][N];
inline bool check(CI x)
{
    for (RI i=1;i<=n;++i) a[i]=(r[i]<=x);
    for (RI i=1;i<=n;++i) pfx[i]=pfx[i-1]+a[i];
    for (RI i=1;i<=n;++i) for (RI j=i;j<=n;++j)
    {
        int ones=pfx[j]-pfx[i-1];
        sum[i][j]=(ones*2>=j-i+1);
    }
    for (RI i=n;i>=1;--i) for (RI j=1;j<=n;++j)
    sum[i][j]+=sum[i+1][j]+sum[i][j-1]-sum[i+1][j-1];
    int cnt=0;
    for (RI i=1;i<=n;++i) for (RI j=i;j<=n;++j)
    if (sum[i][j]*2>=(j-i+1)*(j-i+2)/2) ++cnt;
    return cnt*2>=n*(n+1)/2;
}
int main()
{
    scanf("%d",&n);
    for (RI i=1;i<=n;++i) scanf("%d",&r[i]);
    int l=1,r=1e9,mid,ret; while (l<=r)
    if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
    return printf("%d",ret),0;
}

H. Rainbow Bracket Sequence

直接考虑填左括号的话就不太容易，比赛的时候也想了发现需要上下界费用流，但由于我根本不会这玩意就没继续想，赛后看题解发现真有这种做法

不过其实我们有本质更简单的做法，即先假设所有位置都填了左括号，此时需要选出 \(n\) 个位置将其变为右括号

用经典 trick，合法括号序列的充要条件为：

  • 后 \(2i-1\) 个位置中至少要有 \(n\) 个右括号；
  • 最后 \(2n\) 个位置中恰好要有 \(n\) 个右括号；

同时由于我们预设了每个位置都填左括号，则下界的要求初始时一定是满足的（特判掉显然无解的情况后）

此时每个颜色就有了一个将左括号转为右括号数的上界，此时就可以用传统的费用流模型来处理了

将每个颜色拆出一个虚点，并求出每个颜色 \(j\) 最多只能转化的右括号个数 \(lim_j\)

  • \(S\) 向 \(2n\) 连 \((n,0)\) 的边；
  • 点 \(i+1\) 向点 \(i\) 连 \((\lfloor\frac{i}{2}\rfloor,0)\) 的边；
  • 点 \(i\) 向点 \(n+c_i\) 连 \((1,v_i)\) 的边；
  • 点 \(n+j\) 向 \(T\) 连 \((lim_j,0)\) 的边；

最后用 \(\sum v_i\) 减去该图的最小费用最大流即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=205,INF=1e18;
int T,n,m,l[N],c[N],v[N];
namespace MinCost_MaxFlow
{
	const int NN=405,MM=5e6;
	struct edge
	{
		int to,nxt,v,c;
	}e[MM<<1]; int head[NN],cur[NN],s,t,cnt=1,dis[NN]; bool vis[NN];
	inline void addedge(CI x,CI y,CI v,CI c)
	{
		//printf("%d %d %d %d\n",x,y,v,c);
		e[++cnt]=(edge){y,head[x],v,c}; head[x]=cnt;
		e[++cnt]=(edge){x,head[y],0,-c}; head[y]=cnt;
	}
	#define to e[i].to
	inline bool SPFA(CI s,CI t)
	{
		RI i; for (i=0;i<=t;++i) dis[i]=INF; dis[s]=0;
		queue <int> q=queue <int>(); q.push(s);
		while (!q.empty())
		{
			int now=q.front(); q.pop(); vis[now]=0;
			for (i=head[now];i;i=e[i].nxt)
			if (e[i].v&&dis[now]+e[i].c<dis[to])
			if (dis[to]=dis[now]+e[i].c,!vis[to]) q.push(to),vis[to]=1;
		}
		return dis[t]!=INF;
	}
	inline int DFS(CI now,CI tar,int tmp,int& flow,int& cost)
    {
        if (now==tar) return flow+=tmp,tmp;
		int ret=0; vis[now]=1;
        for (RI& i=cur[now];i&&dis;i=e[i].nxt)
        if (!vis[to]&&e[i].v&&dis[to]==dis[now]+e[i].c)
        {
            int dist=DFS(to,tar,min(tmp-ret,e[i].v),flow,cost);
            ret+=dist; e[i].v-=dist; e[i^1].v+=dist; cost+=dist*e[i].c;
            if (ret==tmp) break;
        }
        vis[now]=0; return ret;
    }
	#undef to
	inline void Dinic(CI s,CI t,int& flow,int& cost)
	{
		flow=cost=0; while (SPFA(s,t)) memcpy(cur,head,(t+1)*sizeof(int)),DFS(s,t,INF,flow,cost);
	}
	inline void clear(void)
	{
		memset(head,0,(t+1)*sizeof(int)); cnt=1;
	}
};
using namespace MinCost_MaxFlow;
signed main()
{
	for (scanf("%lld",&T);T;--T)
	{
		scanf("%lld%lld",&n,&m); n<<=1; int sum=0;
		for (RI i=1;i<=m;++i) scanf("%lld",&l[i]),l[i]=-l[i];
		for (RI i=1;i<=n;++i) scanf("%lld",&c[i]),++l[c[i]];
		for (RI i=1;i<=n;++i) scanf("%lld",&v[i]),sum+=v[i];
		s=n+m+1; t=s+1; addedge(s,n,n/2,0);
		for (RI i=n;i>1;--i) addedge(i,i-1,(i-1)/2,0);
		for (RI i=1;i<=n;++i) addedge(i,n+c[i],1,v[i]);
		bool flag=1; for (RI i=1;i<=m;++i)
		{
			if (l[i]<0) { flag=0; break; }
			addedge(n+i,t,l[i],0);
		}
		if (flag)
		{
			int flow,cost; Dinic(s,t,flow,cost);
			if (flow==n/2) printf("%lld\n",sum-cost); else puts("-1");
		} else puts("-1");
		clear();
	}
	return 0;
}

L. Bull Farm

很有意思的一个题，基本纯靠观察

考虑将空格所在的位置看作点，边用来刻画空格的变换方式，此时询问等价于有向图上两点是否可达

首先将询问离线，每次多出一种操作后会在图中加上一些边，因此考虑每个操作的贡献：

  • 若该操作为排列，则形成了若干个置换，此时相当于在图中加入 \(n\) 条双向边；
  • 若该操作形成的 \(i\to p_i\) 结构为链套环，此时手玩一下会发现多出来两条有向边 \(x\to z,y\to z\)；

动态维护有向图的连通性可以考虑 bitset，加入一条 \(x\to y\) 的边时，我们枚举所有可以到达 \(x\) 的点 \(i\)，将其对于的 bitset 或上 \(y\) 的 bitset 即可

加入一条有向边的复杂度为 \(\frac{n^2}{\omega}\)，对于第二种情况还好；对于第一种情况加的边数就会爆掉

不过我们注意到连通性问题其实加入一个生成树就足以将图连通了，因此我们用并查集维护下所有无向边构成的生成树，只有生成树上的点才转化为单向边加入 bitset 中

总复杂度 \(O((n+l)\times \frac{n^2}{\omega})\)，手写 bitset 后跑得飞快

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#include<array>
#define RI register int
#define CI const int&
using namespace std;
typedef unsigned long long u64;
const int N=2005,M=1e6+5;
int t,n,l,q,trs[N][N],to[N],fa[N],ans[M]; vector <array <int,3>> ques[N]; char s[M];
const int L=(N>>6)+5;
struct Bitset
{
    u64 a[L];
    inline void init(void)
    {
        for (RI i=n>>6;i>=0;--i) a[i]=0;
    }
    inline void set(CI x)
    {
        a[x>>6]|=(1ull<<(x&63));
    }
    inline int test(CI x)
    {
        return (a[x>>6]>>(x&63))&1ull;
    }
    inline void OR(const Bitset& ots)
    {
        for (RI i=n>>6;i>=0;--i) a[i]|=ots.a[i];
    }
}F[N];
inline int getfa(CI x)
{
    return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d%d%d",&n,&l,&q);
        auto decode=[&](const char& a,const char& b)
        {
            return (a-48)*50+(b-48);
        };
        for (RI i=1;i<=l;++i) 
        {
            scanf("%s",s);
            for (RI j=0;j<n;++j)
            trs[i][j+1]=decode(s[j<<1],s[j<<1|1]);
        }
        for (RI i=0;i<=l;++i) ques[i].clear();
        for (RI i=1;i<=q;++i)
        {
            scanf("%s",s);
            int a=decode(s[0],s[1]),b=decode(s[2],s[3]),c=decode(s[4],s[5]);
            ques[c].push_back({a,b,i});
        }
        for (RI i=1;i<=n;++i) F[i].init(),F[i].set(i);
        for (RI i=1;i<=n;++i) fa[i]=i;
        for (RI i=0;i<=l;++i)
        {
            if (i!=0)
            {
                for (RI j=1;j<=n;++j) to[j]=trs[i][j];
                static int indeg[N];
                for (RI j=1;j<=n;++j) indeg[j]=0;
                for (RI j=1;j<=n;++j) ++indeg[to[j]];
                int T,Z,cntT=0,cntZ=0,cntO=0;
                for (RI j=1;j<=n;++j)
                if (indeg[j]==2) ++cntT,T=j;
                else if (indeg[j]==0) ++cntZ,Z=j;
                else if (indeg[j]==1) ++cntO;
                auto link=[&](CI x,CI y)
                {
                    for (RI i=1;i<=n;++i) if (F[i].test(x)) F[i].OR(F[y]);
                };
                if (cntO==n)
                {
                    for (RI j=1;j<=n;++j)
                    {
                        int x=getfa(j),y=getfa(to[j]);
                        if (x!=y) fa[x]=y,link(x,y),link(y,x);
                    }
                } else if (cntT==1&&cntZ==1&&cntO==n-2)
                {
                    int x=-1,y=-1;
                    for (RI j=1;j<=n;++j)
                    if (to[j]==T)
                    {
                        if (x==-1) x=j;
                        else if (y==-1) y=j;
                    }
                    link(x,Z); link(y,Z);
                }
            }
            for (auto [a,b,id]:ques[i]) ans[id]=F[a].test(b);
        }
        for (RI i=1;i<=q;++i) putchar(ans[i]+'0'); putchar('\n');
    }
    return 0;
}

M. Find the Easiest Problem

纯签，徐神开场直接在 PTA 的 IDE 上写的，因此代码就没存

Postscript

明天就是最后一场网络赛了，能不能别犯病了来点 Highlight

标签：CI,const,Contest,int,Asia,ICPC,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/18427326

相关文章

  • AtCoder Regular Contest 184 D Erase Balls 2D
    转化计数对象。直接数最终剩下的球的集合似乎并不好做。考虑数选择的球的集合（显然选择的顺序不重要，只有选择了哪些球重要）。先把所有球按\(x\)坐标从小到大排序。设我们选择的球的下标为\(i_1<i_2<\cdots<i_k\)。那么能选择这些球当且仅当\(y_{i_1}>y_{i_2}>\cdots......
  • 2024ICPC网络赛2
    赛时5题，G题思路对的不知道为啥没过，对辗转相除法还有递推理解太低是这样的。F，I队友切的签到，I似乎是简单构造A模拟这题离谱的一个地方就是我用unordered_map会报错所以改map了。查了一下语法发现是因为没有自定义哈希函数，所以key值不是常规类型的时候必须自定义哈希函数。（当然......
  • 2024ICPC网络赛第二场题解(部分)
    前言这场相对作用大一点，最后顶着队友的怀疑压力乱搞出了C，但是后面看题解发现似乎是数据弱了跑过去，其实复杂度是队友分析的那样，是不正确的，但是毕竟是打名额的比赛，过了就是过了，这里分享一下C题的乱搞做法，以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)......
  • AtCoder Beginner Contest 372 补题记录
    A-delete题意：输出删除字符串中.后的字符串思路：只输出字符串中不是.的字符voidsolve(){strings=sread();for(autoit:s)if(it!='.')cout<<it;cout<<endl;}B-3^A题意：给出M,求将M拆分成N个3的\(A_i\)次方相加思路：贪心，从大到小用......
  • icpc网络赛2024-1
    M-FindtheEasiestProblem给定一些提交记录，问哪道题被通过的最多intT=next();while(T--){intn=next();set<string>st[30];rep(i,0,n){stringteam,problem,stat;cin>>team>>problem>>stat;if(st......
  • AtCoder Beginner Contest 372（A - F）
    A：直接输出。B：把\(M\)三进制拆分，最多10位，每位最多为2，\(N\le20\)足够了。C：暴力修改，每次只产生\(O(1)\)影响。D：预处理st表，二分每个\(j\)会断哪些\(i\)产生贡献，差分一下。E：启发式合并平衡树，\(k\)更大也能做。F：只保留有特殊边经过的点，把\(i,j\)之间的\(j-i......
  • The 2024 ICPC Asia EC Regionals Online Contest (II) - Problem H. Points Selectio
    注意到如果$\text{query}(a,b,c)$为真，那么$\text{query}(\geqa,\geqb,c)$一定为真。从小到大枚举询问中$a$的值，按横坐标从小到大依次加入每个点，维护$f_c$表示最小的$b$满足$\text{query}(a,b,c)$为真。假设当前正在加入点$(x,y,w)$，有$f_{(c+w)\bmodn}=\min(f_{......
  • The 2024 ICPC Asia EC Regionals Online Contest (II) - Problem B. Mountain Bookin
    从$1$到$m$依次考虑每个日期。假设当前正在考虑第$i$天，那么只有第$i$天来访的游客以及指定第$i$天的查询是有用的。将这些游客和查询都提取出来，通过Kruskal重构树可以很方便地在$O(n\logn)$的时间内计算出这些查询的答案。不幸的是，本题还有加边删边操作，无法轻易地......
  • 2024ICPC网络赛（2）-K.Match——匹配、奇妙的n4 DP
    题目：https://qoj.ac/contest/1799/problem/9380题意：给两个长度为\(n\)的序列\(a,b\)，若\(a_i\oplusb_j\geqk\)则连一条左侧\(i\)到右侧\(j\)的边，这样得到一张二分图。对于每个\(x=1,\dots,n\)，询问大小为\(x\)的匹配的数量。\(1\leqn\leq200\).首先要知道一般二......
  • Atcoder Beginner Contest 372
    AtcoderBeginnerContest372A模拟即可。#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){charch;while(cin>>ch){if(ch!='.'){cout<<ch;}}}......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99