首页 > 其他分享 >UESTC 2024 寒假集训 - Day4

UESTC 2024 寒假集训 - Day4

时间：2024-02-20 20:56:21浏览次数：29  
标签：CI const int Day4 UESTC 2024 include RI define

Preface

万恶的psk搬的全是Atcoder上的题目，然后理所当然的后面题目全是Counting Problem了

作为计数苦手直接当场暴毙，3h写完前面的8个题然后直接跑路

AtCoder arc148_a mod M

开场差点被签到腐乳了，没发现答案不是\(1\)就是\(2\)直接傻掉了

由于\(M=2\)时答案至多为\(2\)，因此只需考虑什么情况下答案为\(1\)即可

这是个经典问题，对于两个数\(x,y\)，当\(M\mid \operatorname{abs}(x-y)\)时\(x\equiv y\pmod M\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],g,c[2];
int main()
{
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=2;i<=n;++i) g=__gcd(g,abs(a[i]-a[1]));
	return puts(g!=1?"1":"2"),0;
}

AtCoder arc108_a Sum and Product

纯签到题，枚举即可

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int S,P;
signed main()
{
	scanf("%lld%lld",&S,&P);
	for (RI x=1;x*x<=P;++x) if (P%x==0)
	{
		int y=P/x; if (x+y==S) return puts("Yes"),0;
	}
	return puts("No"),0;
}

AtCoder arc148_b dp

顶针题，不难发现从左边开始的第一个p一定要成为操作的左端点，否则一定不优

然后大力枚举右端点大力判断即可，复杂度\(O(n^2)\)

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int n; string s,ans;
int main()
{
	RI i,j; int pos=-1; for (cin>>n>>s,i=0;i<n;++i) if (s[i]=='p') { pos=i; break; }
	if (pos==-1) return cout<<s,0;
	for (ans=s,i=pos+1;i<=n;++i)
	{
		string t=s; reverse(t.begin()+pos,t.begin()+i);
		for (j=pos;j<i;++j) t[j]=(t[j]=='d'?'p':'d');
		ans=min(ans,t);
	}
	return cout<<ans,0;
}

AtCoder arc108_b Abbreviate Fox

顶针题，不难发现遇到fox能删就删一定不劣，因此直接拿个栈模拟一下即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,top; char s[N],stk[N];
int main()
{
	RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
	{
		stk[++top]=s[i];
		while (top>=3&&stk[top-2]=='f'&&stk[top-1]=='o'&&stk[top]=='x') top-=3;
	}
	return printf("%d",top),0;
}

AtCoder arc148_c Lights Out on Tree

找了个感觉很优秀的性质，没想到差点把自己玩没了

不妨把询问包含的点称为黑点，原来的点称为白点

手玩一波会发现操作次数等于两端颜色不同的边数，如果根节点是黑点那么还需要额外加\(1\)（因为其实前面那个条件等价于把整棵树颜色变成相同的）

考虑这个玩意怎么统计，YY了好久也没想到什么好的做法，后面无奈滚去写根号分治了

当询问的点数超过\(\sqrt{200000}\)时，直接把整棵树扫一遍即可；否则我们可以暴力遍历所有黑点点对来算答案

后面一问祁神发现原来有很trivial的做法，顿感我是个傻逼

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,S=400;
int n,x,q,deg[N],col[N]; vector <int> v[N]; unordered_set <int> son[N];
int main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&q),i=2;i<=n;++i)
	scanf("%d",&x),v[x].push_back(i),++deg[x],++deg[i],son[x].insert(i);
	while (q--)
	{
		scanf("%d",&x); vector <int> p(x); int ans=0;
		for (i=0;i<x;++i) scanf("%d",&p[i]); sort(p.begin(),p.end());
		if (x<=S)
		{
			for (i=0;i<x;++i) for (j=i+1;j<x;++j)
			if (son[p[i]].count(p[j])) --deg[p[i]],--deg[p[j]];
			for (i=0;i<x;++i) ans+=deg[p[i]];
			for (i=0;i<x;++i) for (j=i+1;j<x;++j)
			if (son[p[i]].count(p[j])) ++deg[p[i]],++deg[p[j]];
		} else
		{
			for (i=1;i<=n;++i) col[i]=0;
			for (i=0;i<x;++i) col[p[i]]=1;
			for (i=1;i<=n;++i) for (auto j:v[i]) ans+=(col[i]!=col[j]);
		}
		printf("%d\n",ans+(p[0]==1));
	}
	return 0;
}

AtCoder arc108_c Keep Graph Connected

遇到这种给出了一个图但是保证联通性的题目，很容易想到直接把图扔掉放到生成树上做

考虑自顶向下确定每个点的值，首先先随便给根节点搞个颜色，然后枚举每条树边

  • 若当前点颜色和这条边颜色相同，则给其子节点随便找个不同的颜色
  • 若当前点颜色和这条边颜色不同，则直接将其子节点的颜色定为这条边的颜色

不难发现这样总能找到一种保留生成树上所有边的染色方案

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,m,x,y,z,vis[N],col[N]; vector <pi> v[N],nv[N];
inline void DFS1(CI now=1)
{
	vis[now]=1; for (auto [to,c]:v[now])
	if (!vis[to]) nv[now].push_back(pi(to,c)),DFS1(to);
}
inline void DFS2(CI now=1,CI ban=0)
{
	if (!col[now]) col[now]=ban%n+1;
	for (auto [to,c]:nv[now])
	if (c==col[now]) DFS2(to,c); else col[to]=c,DFS2(to,0);
}
int main()
{
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%d",&x,&y,&z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
	for (DFS1(),col[1]=1,DFS2(),i=1;i<=n;++i) printf("%d\n",col[i]);
	return 0;
}

AtCoder arc148_d mod M Game

挺有意思的一个博弈，想到关键的地方就不难了

不妨先倒着考虑，假设此时只剩下两个数\(x,y\)，此时两个人的数之和分别为\(A,B\)

如果此时Bob能获胜，则必须同时满足：

\[A+x\equiv B+y\pmod M\\ A+y\equiv B+x\pmod M \]

即\(2x\equiv 2y\pmod M\)，我们不妨把满足这个等式的\(x,y\)称为配对

显然，两个相同的数总能配对；而另一种配对的情况则是当\(M\)为偶数时，\(|x-y|=\frac{M}{2}\)

不难发现当且仅当可以把\(2n\)个数全部两两配对时Bob才能获胜，\(M\)是奇数的情况很显然，而\(M\)是偶数的情况还需要加一个特判

不妨考虑以下数据

2 4
0 1 1 2

如果直接按照上面的结论，两个\(1\)配对，\(0\)和\(2\)配对会得出Bob获胜的结论，但实际上最后两个数之和差了\(\frac{M}{2}\)

不难发现，我们还需要统计出\(\ge \frac{M}{2}\)的数个数\(cnt\)，当\(cnt\)为偶数时就不会出现上面那种情况了

#include<cstdio>
#include<iostream>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
int n,m,x,cnt; map <int,int> rst;
int main()
{
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=2*n;++i)
	{
		scanf("%d",&x); if (m%2==0&&x>=m/2) x-=m/2,++cnt; ++rst[x];
	}
	if (cnt%2==1) return puts("Alice"),0;
	for (auto [_,c]:rst) if (c%2==1) return puts("Alice"),0;
	return puts("Bob"),0;
}

AtCoder - arc108_c AB

这题明明有\(\log n\)的做法，但出题人给\(n\le 1000\)的迷惑数据范围就很奇怪，不知道是不是有\(O(n^2)\)的直接DP做法

这题的核心就是手玩+分类讨论，只要把Case搞清楚做法其实都很简单，以\(c_{AB}=A\)的情况为例：

  • 当\(c_{AA}=A\)时，此时不管怎么样都只能在中间加\(A\)
  • 当\(c_{AA}=B\and c_{BA}=A\)时，此时开头的\(A\)和结尾的\(AB\)是定死的，而中间的\(n-3\)个位置可以任意放\(A,B\)，但存在限制不能有两个相邻的\(B\)出现
  • 当\(c_{AA}=B\and c_{BA}=B\)时，此时开头的\(A\)和结尾的\(AB\)是定死的，而中间的\(n-3\)个位置可以任意放\(A,B\)

直接手玩的话第三种情况可能会比较模糊，但实际上我们可以写个暴力打个表出来看下就一目了然了

第二种情况的方案数可以简单DP得出（当然很容易发现其实就是斐波那契数列），第三种情况的方案数就是\(2^{n-3}\)

注意特判\(n\le 3\)的情况

#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,mod=1e9+7;
int n,f[N][2]; string AA,AB,BA,BB;
int main()
{
	cin>>n>>AA>>AB>>BA>>BB;
	if (n<=3) return puts("1"),0;
	if ((AA=="A"&&AB=="A")||(BB=="B"&&AB=="B")) return puts("1"),0;
	if ((AA=="B"&&AB=="A"&&BA=="A")||(BB=="A"&&AB=="B"&&BA=="B"))
	{
		f[1][0]=f[1][1]=1; for (RI i=2;i<=n-3;++i)
		f[i][0]=(f[i-1][0]+f[i-1][1])%mod,f[i][1]=f[i-1][0];
		return printf("%d",(f[n-3][0]+f[n-3][1])%mod),0;
	}
	int ans=1; for (RI i=1;i<=n-3;++i) ans=2LL*ans%mod;
	return printf("%d",ans),0;
}

AtCoder - arc148_e ≥ K

经典Atcoder计数题，看到这题就知道我该下班了

排列计数的经典做法就是考虑插入，而一般为了便于统计我们会强制定下插入的顺序，这题的大致思路就是如此

考虑合法序列的形态，发现以下两个条件就是充要的：

  • 不能出现两个\(<\frac{k}{2}\)的数相邻
  • 对于两个相邻的数\(x,y\)，若\(x<\frac{k}{2},y\ge \frac{k}{2}\)则\(|y-\frac{k}{2}|\ge |x-\frac{k}{2}|\)

考虑按照\(|a_i-\frac{k}{2}|\)从大到小插入，并把相同的数放在一起考虑，这样的好处就是保证不会出现第二种不合法情况

因此考虑限制第一种情况，设\(cur\)表示此时可以插入的位置数\(cur\)，则有：

  • 当\(x<\frac{k}{2}\)时，设其出现次数为\(y\)，则插入方法有\(C_{cur}^y\)种，并且之后可用位置数\(cur\)减去\(y\)
  • 当\(x\ge \frac{k}{2}\)时，设其出现次数为\(y\)，此时插入的方法等价于，把\(y\)个数划分成\(cur\)份，并允许为空，利用插板法知道此时方案数为\(C_{cur+y-1}^{cur-1}\)，并且之后可用位置数\(cur\)加上\(y\)

然后这题就做完了，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
#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=200005,mod=998244353;
int n,k,x,fact[N],ifac[N]; map <int,int> rst;
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 int C(CI n,CI m)
{
	if (n<m||n<0||m<0) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&x),++rst[x];
	vector <pi> vec; for (auto it:rst) vec.push_back(it);
	auto cmp=[&](const pi& A,const pi& B)
	{
		return abs(2*A.fi-k)!=abs(2*B.fi-k)?abs(2*A.fi-k)>abs(2*B.fi-k):A.fi>B.fi;
	};
	sort(vec.begin(),vec.end(),cmp); init(n);
	int ans=1,cur=1; for (auto [val,num]:vec)
	if (val*2<k) ans=1LL*ans*C(cur,num)%mod,cur-=num;
	else ans=1LL*ans*C(cur+num-1,cur-1)%mod,cur+=num;
	return printf("%d",ans),0;
}

AtCoder - arc108_f Paint Tree

这题比赛的时候大家都会而我只能干瞪眼，只能说和Counting没有什么相性

这题的核心就是要想到利用直径，不妨先找出原树的一条直径，记其长度为\(d\)，端点为\(x,y\)

显然若\(x,y\)颜色相同则贡献为\(d\)，方案数为\(2\times 2^{n-2}=2^{n-1}\)，接下来考虑这两点颜色不同的情况

不妨尝试枚举答案\(k\)，那么所有到\(x\)距离\(>k\)的点颜色必须和\(y\)一样x，所有到\(y\)距离\(>k\)的点颜色必须和\(x\)一样

而如果某个点到\(x,y\)的距离都\(\le k\)，那么这个点的颜色就可以随便取，因为根据树的直径的性质，这个点到任何一个点的距离都\(\le k\)

很容易由此观察出一个容斥的做法，不妨设\(f(k)\)表示贡献\(\le k\)的树的方案数，显然用\(f(k)-f(k-1)\)即可得出贡献为\(k\)的方案数了

根据上面所说的，我们设\(cnt_k\)表示到\(x,y\)的距离均\(\le k\)的点的个数，则\(f(k)=2^{cnt_k}\)，就可以轻松计算答案了

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
int n,x,y,st,dis1[N],dis2[N],bkt[N],pw[N],ans; vector <int> v[N];
inline void DFS(CI now,int* dis,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa) dis[to]=dis[now]+1,DFS(to,dis,now);
}
int main()
{
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
	for (DFS(1,dis1),x=i=1;i<=n;++i) if (dis1[i]>dis1[x]) x=i;
	for (dis1[x]=0,DFS(x,dis1),y=i=1;i<=n;++i) if (dis1[i]>dis1[y]) y=i;
	DFS(y,dis2); for (i=1;i<=n;++i) if (i!=x&&i!=y)
	st=max(st,min(dis1[i],dis2[i])),++bkt[max(dis1[i],dis2[i])];
	for (i=1;i<=n;++i) bkt[i]+=bkt[i-1];
	for (i=st;i<=dis1[y];++i)
	(ans+=1LL*i*(pw[bkt[i]]-(i>st?pw[bkt[i-1]]:0)+mod)%mod)%=mod;
	return printf("%d",(2LL*ans+1LL*dis1[y]*pw[n-1]%mod)%mod),0;
}

Postscript

这场剩下J题整场没人尝试就拉倒了，而K这个造计算机题被徐神干了一整场干过去了，那我就不管了

你们有没有这样的徐神啊，真是徐徐又神神啊

标签：CI,const,int,Day4,UESTC,2024,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/18024009

相关文章

  • 2024年2月20号题解
    P5594【XR-4】模拟赛解题思路重点是怎么判断是不是同一套模拟题用一个数组来标记是不是同一套题代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#include<stdbool.h>#defi......
  • 2024-02-20-物联网C语言(10-文件)
    10.文件10.1文件的概念文件用来存放程序、文档、音频、视频数据、图片等数据的。文件就是存放在磁盘上的，一些数据的集合。在windows下可以通过写字板或记事本打开文本文件对文件进行编辑保存。写字板和记事本是微软程序员写的程序，对文件进行打开、显示、读写、关闭。作为......
  • 2024-02-20 闲话
    今天学习了\(\displaystyle\int_{-\infty}^{+\infty}\exp(-x^2)dx\)的做法。然后把昨天说的题做掉了，不过有一个性质是\(a<0\)否则\(\exp(ax^2+bx+c)\)不能是概率密度函数。上午的大学物理实在是太难了，量纲学不会一点。于是去知乎上找了一个RAG的文章看，然后吸取经验......
  • 2024年2月18日——KMP算法（未完成
    点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e6+10;intkmp[maxn];intla,lb,j;chara[maxn],b[maxn];intmain(){ cin>>a+1>>b+1; la=strlen(a+1),lb=strlen(b+1); for(inti=2;i<=lb;i++){ while(j&&b[j+1......
  • 2024.2
    一些以前遗留的题如果想起来了也写进这吧，总归要整理的。ARC171B.Chmax600分的ARCB确实有点难度。先理清操作的实际含义：建出\(i\rightarrowp_i\)的置换环结构，在置换环上从点\(i\)开始走，当下一个点的编号大于自身的时候就走，否则就停下来。然后\(B_i\)就代表最后停留......
  • 2024牛客寒假算法基础集训营4
    A.直接计算#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){inta,b,k;cin>>a>>b>>k;if(a>=k*b)cout<<"good";elsecout<&l......
  • 2024.2 模拟赛日志
    题解一篇没写，就是记录一下分数。WC2024（20240201）\(100+44+5=149\)。T1时间：120min。SS240217（20240217）\(60+10+10=80\)。T160分时间：180min。SS240218（20240218）\(100+20+0=120\)。T1时间：180min。SS240219（20240219）\(100+40+40=180\)。T1时间：180min。USACO24......
  • 2024-02-20 随机生成30位字符串
    functiongenerateRandomString(){letspecialChars="`~!@#$%^&*-+=_|{}[]:;'<>,.?/";letlowercaseLetters='abcdefghijklmnopqrstuvwxyz';letuppercaseLetters='ABCDEFGHIJKLMNOPQRSTUVWXYZ';let......
  • 2024-02-19-物联网C语言(9-链表)
    9.链表9.1概念假如:做一个班级信息管理系统，统计班级学生的信息而我们事先不知道班级人数，或者知道人数，但是中间人员可能发生变化:比如有新同学加入，有同学请假，又或者我们需要统计班级的平均成绩等等目标：要做一个类似QQ、飞秋类似的通信软件，其中有一个功能，类似用户上下线检测、......
  • 2024全年放假日历表及调休安排 用手机便签设置放假倒计时
    对于绝大多数的上班族来说，春节长假已经结束，现在要回归到正常的工作和生活中。为了给生活增加一些“盼头”，很多小伙伴不约而同打开手机日历，查看下个法定节假日是什么时候。下面给大家具体讲一下2024全年放假日历表及调休安排！除去元旦、春节之外，清明节是4月4日至6日放假共3天，4月7日......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99