首页 > 其他分享 >The 2023 ICPC Asia Regionals Online Contest (2)

The 2023 ICPC Asia Regionals Online Contest (2)

时间：2023-09-25 16:55:44浏览次数：34  
标签：include const Contest int ans Asia 2023 Hasher now

Preface

这场打的有点捞说实话，两个小时出头的时候写完6个题就开始坐牢了

K题由于我习惯性地不写数论就扔给徐神了，徐神也是很有思路写了个看着就很对的东西，但不知道为什么过不去

赛后发现K其实是个很傻逼的题，类似的思路我最近补CF的时候还遇到过，但就是没细想

虽然当时下机的时候和祁神把A题的正解讨论出来了，但因为这题实现还挺恶心的所以决策就是优先保证徐神写K题的时间，因此最后A题场上也就写了一半草草收场了

很奇怪感觉平时训练的时候我们队的后场都还可以的，有一次甚至最后一小时连过四题，但一到正式比赛后面就经常坐牢

唉区域赛在即要再多精进下了，感觉我们队的配合啥的都挺好的，可能还是练的不够多啊，一句话加训就完事

A Evaluation

这题在暑假集训的时候做到过一个类似的题，所以很快有了大致的思路，就是通过根号来构造开关

考虑对于每一对\(f(x_i)=a_i\)，我们希望能构造出一个式子\(W_i\)，使得这个式子在\(x=x_i\)时值为\(a_i\)，在\(x=x_j(i\ne j)\)时值为\(0\)，那么最后把所有的\(W_i\)加起来就是一个符合要求的式子了

考虑把\(W_i\)表示成\((A_i)\times (B_i)\)的形式，其中\(A_i\)是一个无论\(x\)取值为多少其返回值都为\(a_i\)的数，而\(B_i\)实现开关功能，当且仅当\(x=x_i\)时返回\(1\)，否则返回\(0\)

回忆拉格朗日插值的表达式，我们很容易想到把\(B_i\)构造成一个由若干个\((x-1-1-\cdots)\)乘起来的形式，其中每个括号内的\(-1\)个数就等于\(x_j(i\ne j)\)的值

而要得到值为\(1\)的数是很容易的，不管我们遇到的字符是什么，给它开两个根号后最后一定会变成\(1\)

另外插一嘴这题中\(1\)的作用很大，比如在没找到下一个\(x\)的时候就可以通过把式子一直乘上\(1\)来跳过某些无用的数

这样当\(x=x_j\)时其中有一个括号的值为\(0\)，因此整个式子的值为\(0\)，否则当\(x=x_i\)时它们乘起来会得到一个不为\(0\)的值

而我们最后要让\(B_i\)的值为\(1\)，考虑到这个乘积不会很大，因此在外面套若干个根号即可将这个非零值转化为\(1\)

接下来就是考虑怎么构造\(A_i\)了，像这种构造题中一个最常见的思路就是二进制分解

由于这里可以用乘法和加法，因此考虑按二进制下每一位来构造，但这样有个问题就是如果只是找到所有的\(2\)然后乘起来，这样是不够在\(15000\)的随机长度下构造出来的，因此我们考虑提高利用率

不难发现对于\(4\sim 8\)，它们开一次根号后就能得到\(2\)，因此在这一步时把它们也拿过来用即可

然后最后对于剩下的没用完的部分，刚开始我是把它们全部暴力变成\(1\)然后乘起来，但发现这样可能会让总长度超过限制的\(10^5\)

后面徐神指出其实对于多余的这些数，把它们全部加起来后再开若干次根号即可得到\(1\)，就可以减少根号的使用量了

最后代码长度虽然不长，但细节还是有一些的，赛后调了快两个多小时才过，比赛的时候估计也写不出来的说

#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
const int N=15005;
int n,m,x[15],f[15]; char s[N]; string ans;
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	auto get_char=[&](void)
	{
		char ch; while (ch=getchar(),ch==' '||ch=='\n'); return ch;
	};
	RI i,j,k,l; for (scanf("%d",&n),i=1;i<=n;++i) s[i]=get_char();
	for (scanf("%d",&m),i=1;i<=m;++i) scanf("%d%d",&x[i],&f[i]);
	for (ans="(",i=j=1;j<=m;++j)
	{
		ans+="(";
		if (f[j])
		{
			for (k=29;k>=1;--k) if ((f[j]>>k)&1)
			{
				int left=k; while (left>0)
				{
					if (s[i]=='2') ans+="2",--left; else
					if (s[i]>='4'&&s[i]<='8') ans+="s("+string(1,s[i])+")",--left; else
					ans+="s(s("+string(1,s[i])+"))"; ++i;
					if (left) ans+="*"; else ans+="+";
				}
			}
			if (f[j]&1) ans+="s(s("+string(1,s[i])+"))+",++i;
			ans.pop_back();
		} else
		{
			ans+="s(s("+string(1,s[i++])+"))";
			ans+="-";
			ans+="s(s("+string(1,s[i++])+"))";
		}
		ans+=")";
		if (m>1)
		{
			ans+="*s(s(s(s(s(s(";
			int k=1; if (k==j) ++k;
			while (k<=m)
			{
				if (s[i]!='x')
				{
					ans+="s(s("+string(1,s[i++])+"))*"; continue;
				}
				ans+="(x"; ++i;
				for (l=1;l<=x[k];++l) ans+="-s(s("+string(1,s[i++])+"))";
				ans+=")*";
				if (++k==j) ++k;
			}
			ans.pop_back();
			ans+="))))))+";
		}
	}
	if (m>1) ans.pop_back(); ans+=")";
	ans+="*s(s(s(s(s(";
	while (i<=n) ans+=string(1,s[i++])+"+";
	ans.pop_back(); ans+=")))))";
	//cout<<ans.size()<<endl;
	return cout<<ans,0;
}

B Wormholes

做不来的题连题目都没看捏

C Covering

这题核心思想在这道题里出现过，因此比赛的时候看了题目就知道怎么写了

每个位置选或不选，还有各种限制，一眼2-SAT模型，考虑抽象题目中的约数来建图

首先任意两个相邻的位置中要至少选一个，同时所有同类型的pair中只能至多取一个

后者的处理方式很套路，一个集合中，要求其中不能选两个及以上的元素同时为\(1\)，朴素地建边是\(O(n^2)\)的

然后用经典的前后缀优化建图即可，具体建图方式可以看上面的链接

当然这题数据范围不大因此用线段树优化建图也可以通过的说

最后注意\(1,n-1\)这两个位置是必选的，需要当作条件把边连上再跑，不然会出现问题

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
typedef long long LL;
const int N=200005;
int n,m,a[N],tot,nxt[N],pre[N]; LL b[N],c[N]; vector <int> pos[N];
inline int ID(CI x,CI tp)
{
	return x+tp*(n-1);
};
namespace Two_Sat
{
	const int NN=N<<2;
	int dfn[NN],low[NN],stk[NN],col[NN],idx,top,scc; bool vis[NN]; vector <int> v[NN];
	inline void addedge(CI x,CI y)
	{
		v[x].push_back(y);
	}
	inline void Tarjan(CI now)
	{
		dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
		for (auto to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
		else if (vis[to]) low[now]=min(low[now],dfn[to]);
		if (low[now]==dfn[now])
		{
			col[now]=++scc; vis[now]=0;
			while (stk[top]!=now) col[stk[top]]=scc,vis[stk[top--]]=0; --top;
		}
	}
	inline void solve(void)
	{
		RI i; for (i=1;i<=tot;++i) if (!dfn[i]) Tarjan(i);
		for (i=1;i<n;++i) if (col[ID(i,0)]==col[ID(i,1)]) return (void)(puts("NO"));
		vector <int> ans; for (i=1;i<n;++i)
		if (col[ID(i,1)]<col[ID(i,0)]) ans.push_back(i);
		printf("%d\n",ans.size());
		for (auto x:ans) printf("%d ",x);
	}
};
using namespace Two_Sat;
int main()
{
	//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	if (n==1) return puts("NO"),0;
	if (n==2) return puts("1\n1"),0;
	for (i=1;i<n;++i) b[i]=c[i]=1000001LL*a[i]+a[i+1];
	sort(c+1,c+n); m=unique(c+1,c+n)-c-1;
	for (i=1;i<n;++i) pos[lower_bound(c+1,c+m+1,b[i])-c].push_back(i);
	addedge(ID(1,0),ID(1,1)); addedge(ID(n-1,0),ID(n-1,1));
	for (i=1;i<n-1;++i) addedge(ID(i,0),ID(i+1,1)),addedge(ID(i+1,0),ID(i,1));
	for (tot=2*(n-1),i=1;i<=m;++i) if (pos[i].size()>1)
	{
		for (j=0;j<pos[i].size();++j) nxt[j]=++tot,pre[j]=++tot;
		for (j=1;j<pos[i].size();++j) addedge(nxt[j-1],nxt[j]),addedge(pre[j],pre[j-1]);
		for (j=0;j<pos[i].size();++j) addedge(ID(pos[i][j],1),nxt[j]),addedge(ID(pos[i][j],1),pre[j]);
		for (j=1;j<pos[i].size();++j) addedge(nxt[j-1],ID(pos[i][j],0)),addedge(pre[j],ID(pos[i][j-1],0));
		//for (j=0;j<pos[i].size();++j) for (RI k=j+1;k<pos[i].size();++k)
		//addedge(ID(pos[i][j],1),ID(pos[i][k],0)),addedge(ID(pos[i][k],1),ID(pos[i][j],0));
	}
	return solve(),0;
}

D Project Manhattan

首先考虑把所有代价\(\le 0\)的位置都站了，并删去所有已经被覆盖了的行和列，考虑对剩下的仅包含正数的矩形的操作

不难发现最优方案一定是在每行中找一个最小的站人，或者是在每列中找一个最小的站人

因为如果存在某一行没有站人，则一定有某个位置没有被覆盖，对于列的情况也是同理，因此二者取较小的输出即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
int t,n,a[N][N];
int main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		for (j=1;j<=n;++j) scanf("%d",&a[i][j]);
		long long ans=0,ret1=0,ret2=0;
		for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (a[i][j]<=0) ans+=a[i][j];
		for (i=1;i<=n;++i)
		{
			int cur=1e6; for (j=1;j<=n;++j)
			if (a[i][j]<=0) { cur=0; break; } else cur=min(cur,a[i][j]);
			ret1+=cur;
		}
		for (j=1;j<=n;++j)
		{
			int cur=1e6; for (i=1;i<=n;++i)
			if (a[i][j]<=0) { cur=0; break; } else cur=min(cur,a[i][j]);
			ret2+=cur;
		}
		printf("%lld\n",ans+min(ret1,ret2));
	}
	return 0;
}

E Another Bus Route Problem

ORZ祁神，本来我都打算去写各种东西优化建图了，祁神提出只要暴力BFS就行了

但因为我实现的时候一个地方没想清楚导致WA了好多发，实在是罪过罪过

考虑从根节点开始，每次加入所有以当前点为路线端点的点至队列中

不难发现在任意时刻当一个点被访问时，它所有的祖先都一定可以被访问

如果我们暴力向上跳来更新，每次遇到有值的点就直接停下，复杂度是\(O(n)\)的

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,fa[N],x,y,ans[N],vis[N]; vector <int> v[N];
int main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=2;i<=n;++i) scanf("%d",&fa[i]);
	for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	queue <int> q; q.push(1); memset(ans,-1,sizeof(ans)); ans[1]=0; vis[1]=1;
	while (!q.empty())
	{
		auto reset=[&](CI now)
		{
			for (auto to:v[now])
			if (!~ans[to]||ans[to]>ans[now]+1)
			{
				ans[to]=ans[now]+1;
				if (!vis[to]) vis[to]=1,q.push(to);
			}
		};
		int now=q.front(); q.pop(); vector <int> tmp; tmp.push_back(now);
		for (x=fa[now];!~ans[x]||ans[x]>ans[now];x=fa[x]) ans[x]=ans[now],tmp.push_back(x);
		reverse(tmp.begin(),tmp.end()); for (auto x:tmp) reset(x);
	}
	for (i=2;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

F Greedy LCS

开场的时候看错题了，看到E有人过了然后点开了F，还把题意喂给了徐神

后面发现原来是经典不可做题，弃了弃了

G Basic Polynomials

题目都没看的说

H Ballet

中间这些题都是给WF水平的队准备的吗，做不了一点

I Impatient Patient

乍一看和之前做过的一道成环期望DP很像，但后面发现这里的最优策略就是选择在某天进行挑战，而之前的每一天都选择跳过

枚举在哪天进行挑战，稍微推一下式子就可以直接算答案了

#include <bits/stdc++.h>

int t, n;

std::vector<int> a, p;

int main() {
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	std::cin >> t;
	while(t--) {
		std::cin >> n;
		a.resize(n), p.resize(n);
		for(auto &a: a) std::cin >> a;
		for(auto &p: p) std::cin >> p;
		long double ans = n;
		for(int i = 0; i < n; ++i) if(p[i]){
			long double upd = (i + 1) + (long double)(1 - p[i]) * (i - a[i] + 1) / p[i];
			if(upd < ans) ans = upd;
		}
		std::cout << ans << '\n';
	}
	return 0;
}

J Street Quality

题目好长，做不了一点

K Super-knight

被这个全场艹穿的题战俘了，感觉最近很容易把简单题想复杂的说

这题其实很容易发现因为第一步走到的点就是\((a,b)\)，而如果往后跳不经过循环使得某一维减小的话答案一定不会更优

因此每次直接找到第一个能让某一维发生变化的位置，然后模拟着跳就完事

考虑这种做法的复杂度，首先在\(n\)次操作后一定会回到\((0,0)\)这个点，此时我们直接结束这个过程

而每次\(x\)这一维发生变化所需的步数大概是\(\frac{n}{a}\)级别，同理\(y\)发生变化所需的步数也是\(\frac{n}{b}\)级别，因此总操作次数大约为\(\frac{n}{n/a}+\frac{n}{n/b}=a+b\)，可以通过此题，不需要任何数论知识

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,n,a,b;
signed main()
{
	//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld%lld",&a,&b,&n);
		int x=a%n,y=b%n,ans=x*x+y*y;
		while (x||y)
		{
			if (x<=a+b&&y<=a+b) ans=min(ans,x*x+y*y);
			int d=min((n-x+a-1)/a,(n-y+b-1)/b);
			x=(x+d*a)%n; y=(y+d*b)%n;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

L Super-palindrome

ORZ徐神看一眼秒了此题

首先发现super-palindrome长度一定为偶数，因此枚举回文中心然后向两边扩展

考虑记录当前未匹配的位置，每次向两边扩展一位的时候如果可以匹配就直接贪心匹配并使得答案加\(1\)

这样的正确性徐神在场上进行了证明，后面发现原来是个结论还有原题来着，我直接呃呃

（不过据说这题数据造假了把\(O(n^3)\)放过去了也是够抽象的）

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
const int N=5005;
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}h[N],pw[N]; int t,n; char s[N];
const Hasher seed=Hasher(31,131);
inline Hasher get(CI l,CI r)
{
	return h[r]-h[l-1]*pw[r-l+1];
}
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%s",s+1); n=strlen(s+1);
		for (pw[0]=Hasher(1,1),i=1;i<=n;++i)
		pw[i]=pw[i-1]*seed,h[i]=h[i-1]*seed+Hasher(s[i],s[i]);
		int ans=0; for (i=1;i<n;++i)
		for (int l1=i,r1=i,l2=i+1,r2=i+1;l1>=1&&r2<=n;--l1,++r2)
		if (get(l1,r1)==get(l2,r2)) ++ans,r1=l1-1,l2=r2+1;
		printf("%d\n",ans);
	}
	return 0;
}

M Dirty Work

签到题，根据经典结论把所有题按照期望解决时间从小到大排序再算答案即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
typedef long double LDB;
const int N=5005;
int t,n,a,b; LDB p,tim[N];
int main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d%d%Lf",&a,&b,&p),tim[i]=1.0L*a*(1.0L-p)+1.0L*(a+b)*p;
		LDB ans=0; for (sort(tim+1,tim+n+1),i=1;i<=n;++i)
		tim[i]+=tim[i-1],ans+=tim[i]; printf("%.12Lf\n",ans);
	}
	return 0;
}

Postscript

下次正式比赛就是CCPC桂林了，希望RP++别再假赛坐牢了的说

标签：include,const,Contest,int,ans,Asia,2023,Hasher,now
From： https://www.cnblogs.com/cjjsb/p/17728291.html

相关文章

  • 创新数据科学探索：DataSpell 2023，专业数据科学家的首选IDE
    在日新月异的数据科学领域，为专业数据科学家提供先进、便捷的工具有着至关重要的意义。2023年，一个备受瞩目的集成开发环境（IDE）——DataSpell，正以其独特的功能与优势，重新定义数据科学家的“瑞士军刀”。→→↓↓载DataSpell2023mac/win版一、DataSpell的主要特性数据科学全流......
  • MoeCTF2023 wp--pwn篇
    五、Pwn1．Pwn入门指北CHALLENGE:Pwn入门指北DESCRIPTION:建议：萌新朋友不要看完指北交上flag就扔掉！！Tips：本指北附件在“通知栏”内的“比赛客服群”中，请加群了解更多信息2．test_ncCHALLENGE:test_ncDESCRIPTION:你知道nc是什么吗3．baby_caculatorCHALLENGE:baby_calcul......
  • 2023-09-25 配对卡方设计的非劣效检验的SAS实现
    近期的工作过程中，需要对配对设计的数据进行非劣效检验，因为SAS中目前没有现成的模块可以使用，因此负责的同事查询了很多文献资料来进行参考，最后选定的是Tango法来计算置信区间，以实现非劣效检验。对同事提供的培训分享中的参考文献进行了比较粗浅的学习，在此记录分享一下。1示例导入......
  • 2023.9.25——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午上课，下午学习。我了解到的知识点：1.软件设计模式；2.做软件要根据客户需求；明日计划：1.上课；......
  • 20230925 模拟赛总结
    模拟赛连接排名：\(\text{rank1}\)分数：\(100+100+100+100=400\)集训期间第二次AK！T1：灭火/fire题目描述：求出\(n\)个数\(a_1,a_2,\dots,a_n\)的和除以\(m\)向上取整的结果。（\(0<a_i,m<2^{63},0<n\le20\)）思路：直接求和，然后向上取整即可，注意要用高精度，我用的是__int128......
  • 2023年百度之星初赛第三场
    1.BD202317石碑文（状压dp）在历史的长河中，石碑静静地矗立，风雨侵蚀，岁月沧桑，它们见证了历史的变迁，承载了无数的故事和传说。这些石碑，如同历史的见证者，在它们的表面，残留下的文字，似乎在诉说着那一段段遥远的往事。这些文字，犹如古老的诗篇，是历史与文化的交织，是时间的印记，是古人留给我......
  • FlashDuty Changelog 2023-09-21 | 自定义字段和开发者中心
    FlashDuty：一站式告警响应平台，前往此地址免费体验！自定义字段FlashDuty已支持接入大部分常见的告警系统，我们将推送内容中的大部分信息放到了Lables进行展示。尽管如此，我们用户还是会有一些扩展或定制性的需求，比如人工标记一个故障是否为误报。因此我们提供了自定义字段功能，......
  • 【2023-09-22】休息空间
    20:00心太小了，所有的小事就大了。心大了，所有的大事都小了。                                                 ——丰子恺昨晚何太下班晚，也不想她太折腾，就睡酒店了。说......
  • 2023-09-23-周日
    1),今天去骑行成都锦城绿道·天府绿道了所以一天也没干什么..就和ice,tyj,zk一起骑共享单车从早上9:00出发,,,到晚上9:00才骑行完毕..哭死......
  • 【2023-09-23】连岳摘抄
    23:59返照斜初彻，浮云薄未归。江虹明远饮，峡雨落馀飞。凫雁终高去，熊罴觉自肥。秋分客尚在，竹露夕微微。                                                 ——唐·杜甫《晚......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99