首页 > 其他分享 >The 2022 ICPC Asia Shenyang Regional Contest

The 2022 ICPC Asia Shenyang Regional Contest

时间：2024-07-15 20:29:26浏览次数：14  
标签：Regional const Contest int Shenyang long include RI define

Preface

本来以为今天有多校的，但到了机房发现并没有，索性就随便找了场比赛 VP 了

然后经典开场三线红温，签了3个题后徐神被一个 string 关住了（后面发现他犯了个极其弱智的错误导致坐牢一整场），祁神被构造 F 关了，然后我写 A 的分类讨论写的很红温

中间排名一度经典俯冲铁牌区，但好在最后一段时间连出三题勉强靠题数苟进 Au 区

后面感觉还有 E 和 I 两个可做题没时间写了，鉴定为纯纯的飞舞

A. Absolute Difference

思路不难但如果实现不好的话可能会写成屎山的一个题

首先不难发现计算答案的方式有连续和离散的两种，即若一个人的集合中都是孤立点，则它产生离散的贡献，否则产生连续的贡献

离散的情况比较简单，主要关心连续的情况，对于两个区间严格不交的情况，可以把贡献看作两个区间中点的距离

而两个区间有交的情况乍一看是个不好处理的绝对值积分，但后面祁神发现可以根据把积分符号上下限进行拆解，即将该情况拆为一对完全相同的区间和若干对严格不交的区间的情形

不难发现相交的区间个数不会超过 \(n+m\)，因此可以直接处理

注意实现的时候把离散点和区间统一成一起来做比较方便，通过考虑每一段是被覆盖一次还是两次来讨论贡献

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#define int long long
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=100005;
int n,m,al[N],ar[N],bl[N],br[N],cnt,lena,lenb; pi rst[N*4];
signed main()
{
	RI i; scanf("%lld%lld",&n,&m);
	for (i=1;i<=n;++i)
	{
		scanf("%lld%lld",&al[i],&ar[i]);
		lena+=ar[i]-al[i];
		rst[++cnt]=pi(al[i],0); rst[++cnt]=pi(ar[i],0);
	}
	for (i=1;i<=m;++i)
	{
		scanf("%lld%lld",&bl[i],&br[i]);
		lenb+=br[i]-bl[i];
		rst[++cnt]=pi(bl[i],1); rst[++cnt]=pi(br[i],1);
	}
	sort(rst+1,rst+cnt+1); int a=0,b=0;
	long double ans=0,pa=0,pb=0,sa=0,sb=0;
	for (i=1;i<cnt;++i)
	{
		auto PA=[&](CI len)
		{
			if (lena==0) return 1.0L/n;
			else return 1.0L*len/lena;
		};
		auto PB=[&](CI len)
		{
			if (lenb==0) return 1.0L/m;
			else return 1.0L*len/lenb;
		};
		if (rst[i].se==0) a^=1; else b^=1;
		int len=rst[i+1].fi-rst[i].fi;
		long double mid=(rst[i+1].fi+rst[i].fi)/2.0L;
		if (a&&b) ans+=1.0L/3.0L*len*PA(len)*PB(len);
		if (a)
		{
			ans+=PA(len)*(pb*mid-sb);
		}
		if (b)
		{
			ans+=PB(len)*(pa*mid-sa);
		}
		if (a)
		{
			sa+=mid*PA(len); pa+=PA(len);
		}
		if (b)
		{
			sb+=mid*PB(len); pb+=PB(len);
		}
	}
	return printf("%.12Lf",ans),0;
}

B. Binary Substrings

感觉不简单的一个题，先坑着以后再说

C. Clamped Sequence

不难发现 clamp 的区间长度越大越好，因此可以令 \(r\) 始终为 \(l+d\)

而显然有意义的 \(l,r\) 的取值一定是原来序列中出现过的数，因此直接枚举端点可以做到 \(O(n^2)\) 的复杂度

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
int n,d,a[N],rst[N]; long long ans;
inline long long calc(CI l,CI r)
{
	static int b[N]; RI i;
	for (i=1;i<=n;++i)
	if (a[i]<l) b[i]=l; else
	if (a[i]>r) b[i]=r; else b[i]=a[i];
	long long ret=0;
	for (i=1;i<n;++i) ret+=abs(b[i]-b[i+1]);
	return ret;
}
int main()
{
	RI i; for (scanf("%d%d",&n,&d),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 (i=1;i<=m;++i)
	{
		ans=max(ans,calc(rst[i],rst[i]+d));
		ans=max(ans,calc(rst[i]-d,rst[i]));
	}
	return printf("%lld",ans),0;
}

D. DRX vs. T1

因为之前 VP 过23年的沈阳，发现这种撸批出的题一般都是签到，果不其然开场看一眼还真是

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
char s[10];
int main()
{
	scanf("%s",s+1); int T=0,D=0;
	for (RI i=1;i<=5;++i)
	if (s[i]=='T') ++T; else if (s[i]=='D') ++D;
	if (T==3) puts("T1"); else if (D==3) puts("DRX");
	return 0;
}

E. Graph Completing

徐神好像比赛的时候大概会了这个题，但已经没有机时去写了，坐等徐神补题

F. Half Mixed

挺有意思的一个构造，主要要发现二维的限制是假的只要考虑一维的情况就很简单了

首先总矩形数为 \(\frac{n(n+1)}{2}\times \frac{m(m+1)}{2}\)，若两项均为奇数则显然无解，否则不妨令 \(\frac{n(n+1)}{2}\) 为偶数，构造出一种 \(n\times 1\) 的情况后复制 \(m\) 列即可

不难发现此时序列由若干个同色段组成，不妨设每段的长度为 \(a_1,a_2,\dots,a_k\)，则纯色段的数量为 \(\sum_{i=1}^k \frac{a_i(a_i+1)}{2}\)

要让这个值等于 \(\frac{n(n+1)}{4}\)，并且 \(\sum_{i=1}^k a_i\) 的值为 \(n\)，手玩一下很容易发现一个贪心的构造方法

即每次选择尽可能大的段长，但要注意剩下的部分一个一个的放要能凑出总长为 \(n\)，实现非常简单

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,n,m,p[N],ans[N];
signed main()
{
	RI i,j; for (i=1;i<=1000000;++i) p[i]=i*(i+1)/2LL;
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld",&n,&m);
		if ((n*(n+1)/2LL)%2==1&&(m*(m+1)/2LL)%2==1) { puts("No"); continue; }
		bool swaped=0; if ((n*(n+1)/2LL)%2==1) swap(n,m),swaped=1;
		vector <int> vec; int tar=n*(n+1)/4LL,sum=0;
		while (tar>0)
		{
			int pos=upper_bound(p+1,p+1000000,tar)-p-1;
			while (sum+pos+tar-p[pos]<n) --pos;
			vec.push_back(pos); sum+=pos; tar-=p[pos];
		}
		//for (auto x:vec) printf("%lld ",x); putchar('\n');
		int c=0; i=0; puts("Yes");
		for (auto x:vec)
		{
			for (j=1;j<=x;++j) ans[++i]=c;
			c^=1;
		}
		if (swaped)
		{
			for (i=1;i<=m;++i)
			for (j=1;j<=n;++j) printf("%lld%c",ans[j]," \n"[j==n]);
		} else
		{
			for (i=1;i<=n;++i)
			for (j=1;j<=m;++j) printf("%lld%c",ans[i]," \n"[j==m]);
		}
	}
	return 0;
}

G. Meet in the Middle

感觉挺可做的一个题，但比赛的时候没时间细想了，先坑着再说

H. P-P-Palindrome

徐神开局就秒了，结果因为把字符串长度开成 char 类型挂了好久，导致徐神整场基本就在看这个题

做法就是 PAM+Hash，然后用一些回文串的 border 的性质，只能说徐神伟大，无需多言

#include <bits/stdc++.h>

constexpr int $n = 1'000'006;

namespace HL666 {
	const int mod1=998244353,mod2=1e9+7;
	struct Hasher
	{
		int x,y;
		inline Hasher(const int& X=0,const int& Y=0)
		{
			x=X; y=Y;
		}
		inline int64_t val(void)
		{
			return ((1LL*x)<<31LL)|(1LL*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];
	const Hasher seed=Hasher(31,131);
	void build_hash(const char *s, int n) {
		pw[0]=Hasher(1,1);
		for (int i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
		for (int i=1;i<=n;++i) h[i]=h[i-1]*seed+Hasher(s[i],s[i]);
	}
	
	int64_t get_hash(int l, int r) {
		return (h[r]-h[l-1]*pw[r-l+1]).val();
	}
}

namespace PAM {
	int go[$n][26], len[$n], fail[$n], las, O;
	char s[$n];
	int64_t s_len;
	
	void init() {
		scanf("%s", s + 1); s_len = strlen(s + 1);
		HL666::build_hash(s, s_len);
		len[0] = -1; len[1] = 0; fail[1] = 0;
		memset(go[0], 0, sizeof(go[0]));
		memset(go[1], 0, sizeof(go[1]));
		las = 1, O = 1;
		s[0] = 1;
	}
	
	void insert(int i) {
		int u = s[i] - 'a';
		int p = las;
		while(p && s[i - len[p] - 1] != s[i]) p = fail[p];
		if(go[p][u]) { las = go[p][u]; return ; }
		int np = las = go[p][u] = ++O;
		memset(go[np], 0, sizeof(go[np]));
		
		len[np] = len[p] + 2;
		if(!p) return fail[np] = 1, void(0);
		do p = fail[p]; while(p && s[i - len[p] - 1] != s[i]);
		if(go[p][u]) fail[np] = go[p][u];
		else fail[np] = 1;
		return ;
	}
} // namespace PAM

inline void chkmx(int64_t &a, int64_t b) {
	if(b > a) a = b;
}

int main() {
	//freopen("data.in", "r", stdin);
	//freopen("data.out", "w", stdout);
	int n; scanf("%d", &n);
	std::map<int64_t, int64_t> hkr;
	while(n--) {
		using namespace PAM;
		init();
		for(int i = 1; i <= s_len; ++i) {
			insert(i);
			if(len[las] <= 0) continue;
			int per = len[las] - len[fail[las]];
			int L = (len[las] % per == 0 ? per : len[las]);
			// std::cout << "(" << len[las] << ", " << L << ", get_hash(" << i - L + 1 << ", " << i << ") = " << HL666::get_hash(i - L + 1, i) << ")" << char(10);
			chkmx(hkr[HL666::get_hash(i - L + 1, i)], len[las] / L);
		}
	}
	int64_t ans = 0;
	for(auto [k, v]: hkr) ans += v * v;
	printf("%lld\n", ans); 
	return 0;
}

I. Quartz Collection

快结束的时候看的这个题，当时祁神给的贪心基本就是正确的了，但因为还要维护修改鉴定为肯定写不完，索性直接跑路吃饭去了

做法就是按照 \(a_i-b_i\) 的正负分类，先不妨假设每个人都能拿到 \(sumb=\sum_{i=1}^nb_i\) 的贡献

考虑对于 \(a_i-b_i<0\) 的物品，此时选择它们一定会让答案变优，因此两个人肯定都是先贪心地拿这些物品

将物品按照 \(a_i-b_i\) 的值从小到大排序，则不难发现 Alice 最后拿到的这类物品中一定是排名模 \(4\) 为 \(0,3\) 的那些

对于剩下的 \(a_i-b_i>0\) 的物品，怎么选都会导致亏损，因此首要的就是要避免选择

同时对于之前 \(a_i-b_i<0\) 的物品，还剩下它们对应的第二种物品可以取，因为这些本身就必须都要拿，因此相当于一次避免亏损的轮空操作

手玩后发现所有 \(a_i-b_i\) 的物品对应的第一个和第二个都一定会先被取完，而总数量一定是偶数

因此 Alice 对 \(a_i-b_i\) 的物品的取法要么是先取一个最小的第一个物品；要么是等 Bob 取一个最小的第一个物品后自己取走 Bob 刚取的第二个物品，然后自己取一个次小的第一个物品

根据 \(a_i-b_i<0\) 的物品数量判断 Alice 要取 \(a_i-b_i>0\) 的物品中排名模 \(4\) 为 \(0,2\) 或者 \(1,3\) 的那些

具体实现可以用一个权值线段树，每个节点维护子树内数的个数以及排名模 \(4\) 的数的和，合并的时候转移显然

总复杂度 \(O((n+m)\log n)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
const int N=200005;
int n,m,a[N],b[N],t,x,y; LL sumb;
class Segment_Tree
{
	private:
		int sz[N<<2]; LL sum[N<<2][4];
		inline void pushup(CI now)
		{
			sz[now]=sz[now<<1]+sz[now<<1|1];
			for (RI i=0;i<4;++i) sum[now][i]=sum[now<<1][i];
			int lsz=sz[now<<1];
			for (RI i=0;i<4;++i) sum[now][(lsz+i)%4]+=sum[now<<1|1][i];
		}
	public:
		#define TN CI now=1,CI l=-100000,CI r=100000
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void updata(CI pos,CI mv,TN)
		{
			if (l==r)
			{
				if (mv>0) sum[now][sz[now]%4]+=pos;
				else sum[now][(sz[now]-1)%4]-=pos;
				sz[now]+=mv; return;
			}
			int mid=l+r>>1;
			if (pos<=mid) updata(pos,mv,LS); else updata(pos,mv,RS);
			pushup(now);
		}
		inline LL query(void)
		{
			LL res=sum[2][0]+sum[2][3];
			if (sz[2]*2%4==0) res+=sum[3][0]+sum[3][2];
			else res+=sum[3][1]+sum[3][3];
			return res;
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
int main()
{
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
	scanf("%d%d",&a[i],&b[i]),SEG.updata(a[i]-b[i],1),sumb+=b[i];
	for (printf("%lld\n",sumb+SEG.query()),i=1;i<=m;++i)
	{
		scanf("%d%d%d",&t,&x,&y);
		sumb-=b[t]; sumb+=y;
		SEG.updata(a[t]-b[t],-1);
		a[t]=x; b[t]=y;
		SEG.updata(a[t]-b[t],1);
		printf("%lld\n",sumb+SEG.query());
	}
	return 0;
}

J. Referee Without Red

题都没看，鉴定为寄

K. Security at Museums

同上，没时间看题

L. Tavern Chess

乍一看很吓人，其实仔细分析因为初始时所有怪血和攻击相同，因此每次碰撞至少会死一只怪

因此直接大爆搜计算概率即可，实现的时候需要一些细节和耐心

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

using LD = long double;

int n, m;
int atk[2][10];
LD Awin=0, Bwin=0, Tie=0;

void dfs(vector<int> hp1, vector<int> hp2, int ft, int cur, int nxt, LD p){
//	printf("dfs(ft=%d cur=%d nxt=%d p=%Lf)\n", ft, cur, nxt, p);
//	printf("hp1:"); for (int i=0; i<7; ++i) printf("%d ", hp1[i]); puts("");
//	printf("hp2:"); for (int i=0; i<7; ++i) printf("%d ", hp2[i]); puts("");
	bool ok=false;
	for (int i=0; i<7; ++i){
		if (hp1[(cur+i)%7]>0){ok=true; cur=(cur+i)%7; break;}
	}
	
	int alive=0;
	for (int i=0; i<7; ++i) if (hp2[i]>0) ++alive;
	
	if (!ok && 0==alive){
		Tie+=p; return;
	}else if (0==alive){
		if (0==ft) Awin+=p;
		else Bwin+=p;
		return;
	}else if (!ok){
		if (1==ft) Awin+=p;
		else Bwin+=p;
		return;
	}
	
	for (int i=0; i<7; ++i) if (hp2[i]>0){
		vector<int> nhp1=hp1, nhp2=hp2;
		nhp1[cur] = max(0, nhp1[cur]-atk[ft^1][i]);
		nhp2[i] = max(0, nhp2[i]-atk[ft][cur]); 
		dfs(nhp2, nhp1, ft^1, nxt, (cur+1)%7, p/alive);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cout << setiosflags(ios::fixed) << setprecision(15);
	cin >> n >> m;
	for (int i=0; i<n; ++i) cin >> atk[0][i];
	for (int i=0; i<m; ++i) cin >> atk[1][i];
	vector<int> hp1(7), hp2(7);
	for (int i=0; i<7; ++i) hp1[i]=atk[0][i];
	for (int i=0; i<7; ++i) hp2[i]=atk[1][i];
	
	if (n==m){
		dfs(hp1, hp2, 0, 0, 0, 0.5L);
		dfs(hp2, hp1, 1, 0, 0, 0.5L);
	}else if (n>m) dfs(hp1, hp2, 0, 0, 0, 1.0L);
	else dfs(hp2, hp1, 1, 0, 0, 1.0L);
	
	cout << Awin << '\n' << Bwin << '\n' << Tie << '\n';
	return 0;	
}

M. Vulpecula

还是没看题，由过题人数可知本题十分不可做

Postscript

感觉最近都唐得一批啊，希望明天开始的多校不要被打爆了

标签：Regional,const,Contest,int,Shenyang,long,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/18303925

相关文章

  • Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）
    ⚪题和板题大赛/jk好像能切的样子，但是太菜了，唐了8罚。A-BuyaPen输出除去某个颜色以外，其他颜色代表的最大值。点击查看代码#include<bits/stdc++.h>usingnamespacestd;inta,b,c;strings;signedmain(){cin>>a>>b>>c;cin>>s;if(s[0]=='R')a=103......
  • SMU Summer 2024 Contest Round 2 （7.9）zhaosang
    A-Ahttp://162.14.124.219/contest/1006/problem/A考查用vector画图我枚举到n==5才开始用，浪费40分钟，还是找规律太慢，得多学做题代码如下：一坨#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constllN=1e6+8;charv[1000001];intw[10000001];ll......
  • SMU Summer 2024 Contest Round 3（7.10）zhaosang
    打的最菜一次，最惨一次，题读假了A-Ahttp://162.14.124.219/contest/1007/problem/A签到题要解决这道题，素数对，数据量不是很大，所以我们可以先预处理素数，这个偶数肯定是等于小于它的两个素数，所以只需要遍历到小于它即可，把素数存起来，然后这两个素数的和等于这个偶数，并且要求相差最小......
  • 2023 Henan Provincial Collegiate Programming Contest
    和零时加的队友打了一下，计算几何摆了，最优化摆了，adhoc摆了。A.小水獭游河南枚举前缀，是\(O(|\Sigma|)\)的，然后判断一下是不是回文串即可。B.ArtforRest昨天才做过这个套路的加强版。显然只用判断类似\(\max(a,b)<\min(b+1,c)\)的条件。暴力枚举是调和级数的。C.Toxel......
  • Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）
    这场比赛还是比较水的A,B,C跳过D题dij把点权和边权都转换为边权即可E题DP可以用\(map\)存一下等差数列的差先说\(O(n^4)\),\(f_{len,i,j,t}\)分别表示长度,现在在\(i\),上一个在\(j\)显然动态转移方程就有了\(f_{len,i,j,k}=\sum_{k=1}^{k=j-1}f_{len-1,j,k,t}\)点击查看......
  • AtCoder Beginner Contest 362 补题记录（A~E，G）
    A分三类情况讨论即可。voidsolveqwq(){intr=io.read(),g=io.read(),b=io.read();stringqwq=io.readstring();if(qwq=="Blue")printf("%lld\n",min(r,g));elseif(qwq=="Red")printf("%lld\n",......
  • SMU Summer 2024 Contest Round 3
    1.To3原题链接：http://162.14.124.219/contest/1007/problem/I记录数组中除3余数的种类和个数，以及数组元素总和除3的余数，最后判断（考虑总余数为1，两个元素余数为2和总余数为2，两个元素余数为1的特殊情况）查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespa......
  • SMU Summer 2024 Contest Round 2
    1.MinimumWidth原题链接：http://162.14.124.219/contest/1006/problem/C二分一行最大容量，如果check小于等于总行数就扩大，反之则缩小查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m;inta[1000000],b[1000000];boolcheck(intx){......
  • SMU Summer 2024 Contest Round 3(7.10)
    寻找素数对思路：数的范围为10000，直接筛出所有范围内的质数，n2的枚举所有质数对和的情况#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definePIIpair<int,int>constintN=1e4+5;vector<int>pri;intidx,st[N];voidinit(){for(in......
  • SMU Summer 2024 Contest Round 3
    SMUSummer2024ContestRound3寻找素数对题意给你一个偶数，找到两个最接近的素数，其和等于该偶数。思路处理出1e5以内的素数，然后遍历，更新最接近的答案。代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;vector<int>euler_range(intn){......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99