首页 > 其他分享 >GJ Round

GJ Round

时间：2024-10-20 13:52:55浏览次数：1  
标签：const int Round 咕咕 mathcal GJ define

前言：

GJ Round 为学校内部模拟赛

记 7.13 为 Round 1，在此之前的模拟赛较为混乱以后再说（可能记为 Round 0 或者负数）

目前正在倒序更新

博客园 可能食用更佳

Round 20 (9.18)

\(\mathcal A\)

简单数学题

考虑将每一个 \(a_i\) 分别拆开计算贡献计算对应的 \(a_i=i\) 时所产生的贡献即可

答案即为 \(ans=\sum_{i=1}^{n} ({i-1 \choose a_i-1} \times 2^{n-i}) \pmod {10^9+7}\)

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
const int N=2e5+5,mod=1e9+7;
int n,a[N],fac[N],inv[N],pw2[N];
int fpm(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int C(int n,int k)
{
	return (k>n||n<0||k<0)?0:fac[n]*inv[n-k]%mod*inv[k]%mod;
}
void init()
{
	fac[0]=pw2[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod,pw2[i]=pw2[i-1]*2%mod;
	inv[n]=fpm(fac[n],mod-2);
	for(int i=n;i;i--) inv[i-1]=inv[i]*i%mod;
}
signed main()
{
//	freopen("ex_seq.in","r",stdin);
//	freopen("ex_seq.out","w",stdout);
	scanf("%lld",&n);
	init();
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	sort(a+1,a+1+n);
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans+C(i-1,a[i]-1)*pw2[n-i]%mod)%mod;
	printf("%lld",ans);
	return 0;
}

\(\mathcal B\)

按顺序从 \(1\) 到 \(n\) 拿盘子，对于每个盘子，你可以选择不要，也可以拿走，但拿走盘子需要满足下面三个条件至少一个：

  • 之前没有拿过盘子；

  • 这个盘子的尺寸比之前拿走的盘子的都大，这样你就可以把之前买的盘子叠在它的上面；

  • 这个盘子的尺寸比之前拿走的盘子的都小，这样你就可以把它叠在之前买的盘子的上面。

最后，你想知道，你最多能拿走多少个盘子？

从结尾开始做最长上升和最长下降子序列，二分或线段树优化 dp 即可

#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=1e5+5;
int n,f[N],g[N],a[N],b[N];
struct SGT
{
	int t[N<<2];
	void push_up(int u)
	{
		t[u]=max(t[ls],t[rs]);
	}
	void update(int u,int l,int r,int x,int k)
	{
		if(x<l||r<x) return;
		if(x==l&&r==x)
		{
			t[u]=k;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid) update(ls,l,mid,x,k);
			else update(rs,mid+1,r,x,k);
		push_up(u);
	}
	int query(int u,int l,int r,int x,int y)
	{
		if(y<l||r<x) return 0;
		if(x<=l&&r<=y) return t[u];
		int mid=(l+r)>>1,res=0;
		if(x<=mid) res=max(res,query(ls,l,mid,x,y));
		if(y>mid) res=max(res,query(rs,mid+1,r,x,y));
		return res;
	}	
}T1,T2;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=n;i;i--)
	{
		a[i]=lower_bound(b+1,b+1+len,a[i])-b;
		int x=(1<=a[i]-1?T1.query(1,1,n,1,a[i]-1):0);
		int y=(a[i]+1<=n?T2.query(1,1,n,a[i]+1,n):0);
		f[i]=x+1,g[i]=y+1;
		T1.update(1,1,n,a[i],f[i]);
		T2.update(1,1,n,a[i],g[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1);
	printf("%d",ans);
	return 0;
}

时间复杂度 \(\mathcal O(n \log n)\)

\(\mathcal C\)

CF875F Royal Questions

考虑将平面内的每一行每一列连边

求最大权值基环森林

跟最大生成树差不多，用 Kruskal 跑再稍微改一下就差不多了

时间复杂度 \(O(nm (\log n+\log m))\)

\(\mathcal D\)

天道酬勤，你已经精通了 OI。

你认为 OI 的学习可以分为 \(n\) 个阶段，在经历第 \(i\) 个阶段时，如果自身能力值大于 \(a_i\)，那么就可以得到 \(b_i\) 的进步，也就是能力值累加上 \(b_i\)。

并不是每个 Oler 都会完整的走完 \(n\) 个阶段，你观察了 \(q\) 个 Oler，第 \(i\) 个 Oler 会带着 \(x_i\) 的初始能力值依次经历第 \(l_i,l_{i+1},\dots,r_i\) 个阶段。

他们都还在路上，而你想知道他们最终会变得多强，也就是经历完这些阶段后的能力值。

由于某些原因，有时候你急切的想知道答案。

数据结构（DS）题

咕咕咕

Round 21 (9.19)

\(\mathcal A\)

SB 题，还什么困难卷积

不同的 \(a_i,b_i\) 只有 \(\mathcal O(\sqrt{sum})\) 个，排序去重模拟即可

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5;
int n,a[N],b[N],f[N],g[N];
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",a+i),f[a[i]]++;
	for(int i=1;i<=n;i++) scanf("%lld",b+i),g[b[i]]++;
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	int A=unique(a+1,a+1+n)-a-1,B=unique(b+1,b+1+n)-b-1;
	int ans=0;
	for(int i=1;i<=A;i++)
		for(int j=1;j<=B;j++)
			ans+=(int)sqrt(abs(a[i]-b[j]))*f[a[i]]*g[b[j]];
	printf("%lld",ans);
	return 0;
}
/*
4
1 2 3 4
2 3 3 3

12
*/

\(\mathcal B\)

CF623C Electric Charges

二分答案，预处理前后缀最大最小值，分别对于 \(x\) 和 \(y\) 得到极长段来求答案

\(\mathcal C\)

数论题，不会做

\[ans=\sum_{i=0}^{p-1} a_i \times m^i \pmod p \]

\[p \in {Prime},m \in [1,p),a_0=1,a_1=1,a_2=6 ,\dots \]

\(a_i\) 是杨辉三角中间对称轴的那一列

咕咕咕

\(\mathcal D\)

红茶国有 \(m\) 个部落，为了争夺 \(n\) 个有灵气的矿洞里的资源，部落之间经常发生冲突。矿洞被标号为 \(1\) 到 \(n\)，每个矿洞初始都被至多一个部落所占领。平时的矿洞里没有任何有价值的资源，珍贵之物只有在特定的时候才会出现，具体地，依次会有 \(q\) 次事件发生，每次事件形如：

  • 1 l r x：\(x\) 号部落发起战争，占领了编号为 \(l\) 到 \(r\) 的矿洞，原先占有这些矿洞的部落将会失去它们，转而由 \(x\) 号部落来占领；

  • 2 l r x：编号为 \(l\) 到 \(r\) 的矿洞灵气爆发，都出现了价值为 \(x\) 的宝物。

一旦一个部落占领的矿洞里有宝物，宝物会立即被全部取走。为了知道哪些部落能成为王，你需要求出 \(q\) 次事件发生之后，每个部落分别得到的宝物的价值总和。

数据结构（DS）题

赛时着真做结果因为复杂度写假了T飞了

听说正着写能用 set 维护颜色段，但笔者不会

由于没有强制在线，可以考虑时光倒流，这样就不用考虑正着做部落具有占领权这一问题，那就基本上是区间加、区间覆盖、区间查询的模板线段树题

最后再把一开始部落占有的矿洞再 query \(m\) 次就好了

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=5e5+5;
int a[N],ans[N];
int n,m,Q;
int t[N<<2],tag[N<<2],cov[N<<2];
void push_up(int u)
{
	t[u]=t[ls]+t[rs];
}
void build(int u,int l,int r)
{
	cov[u]=-1;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(u);
}
void push_down(int u,int l,int r)
{
	if(~cov[u])
	{
		cov[ls]=cov[rs]=cov[u];
		tag[ls]=tag[rs]=0;
		t[ls]=t[rs]=cov[u];
		cov[u]=-1;
	}
	if(!tag[u]) return;
	tag[ls]+=tag[u],tag[rs]+=tag[u];
	int mid=(l+r)>>1;
	t[ls]+=tag[u]*(mid-l+1);
	t[rs]+=tag[u]*(r-mid);
	tag[u]=0;
}
void update(int u,int l,int r,int x,int y,int k)
{
	if(y<l||r<x) return;
	if(x<=l&&r<=y)
	{
		t[u]+=(r-l+1)*k;
		tag[u]+=k;
		return;
	}
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,y,k);
	if(y>mid) update(rs,mid+1,r,x,y,k);
	push_up(u);
}
void modify(int u,int l,int r,int x,int y,int k)
{
	if(y<l||r<x) return;
	if(x<=l&&r<=y)
	{
		t[u]=cov[u]=k;
		tag[u]=0;
		return;
	}
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) modify(ls,l,mid,x,y,k);
	if(y>mid) modify(rs,mid+1,r,x,y,k);
	push_up(u);
}
int query(int u,int l,int r,int x,int y)
{
	if(y<l||r<x) return 0;
	if(x<=l&&r<=y) return t[u];
	push_down(u,l,r);
	int mid=(l+r)>>1,res=0;
	if(x<=mid) res+=query(ls,l,mid,x,y);
	if(y>mid) res+=query(rs,mid+1,r,x,y);
	return res;
}
struct dat
{
	int opt,x,y,k;
}p[N];
signed main()
{
//	freopen("king.in","r",stdin);
//	freopen("king.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&Q);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	build(1,1,n);
	for(int i=1;i<=Q;i++) scanf("%lld%lld%lld%lld",&p[i].opt,&p[i].x,&p[i].y,&p[i].k);
	for(int i=Q;i;i--)
	{
		int opt=p[i].opt,x=p[i].x,y=p[i].y,k=p[i].k;
		if(opt&1)
		{
			ans[k]+=query(1,1,n,x,y);
			modify(1,1,n,x,y,0);
			continue;
		}
		update(1,1,n,x,y,k);
	}
	for(int i=1;i<=n;i++) ans[a[i]]+=query(1,1,n,i,i);
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}

Round 22 (9.24)

\(\mathcal A\)

小模拟麻将题

  • 先考虑 \(n=14\)

    若 \(k=2\) 只考虑顺子和雀头

    若 \(k=3,4\) 枚举雀头再检验剩下的牌是刻子还是顺子

  • 在考虑 \(n=13\)

    显然可以枚举最后一张牌，然后就用 \(n=14\) 时的方法做就好

\(\mathcal B\)

人类智慧题

发现 \(0 \leq y_i \leq 10\)，可以先按 \(x_i\) 从小到大排序，然后发动人类智慧，每个点只连它前面的 \(20\) 个点，然后跑最小生成树，做完了

时间复杂度 \(\mathcal O(n \log n)\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,cnt,fa[N],siz[N];
struct dat
{
	int x,y;
}p[N];
bool cmp(const dat &a,const dat &b)
{
	return a.x^b.x?a.x<b.x:a.y<b.y;
}
int dis(int a,int b,int x,int y)
{
	return (a-x)*(a-x)+(b-y)*(b-y);
}
struct Edge
{
	int u,v,w;
}e[M];
bool cmpe(const Edge &a,const Edge &b)
{
	return a.w<b.w;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int Kruskal()
{
	int tot=0,mst=0;
	for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	sort(e+1,e+1+cnt,cmpe);
	for(int i=1;i<=cnt;i++)
	{
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		if(siz[x]<siz[y]) swap(x,y);
		fa[y]=x;
		siz[x]+=siz[y];
		mst+=e[i].w;
		if(++tot==n-1) break;
	}
	return mst;
}
signed main()
{
//	freopen("ant.in","r",stdin);
//	freopen("ant.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=min(i+20,n);j++)
			e[++cnt]=(Edge){i,j,dis(p[i].x,p[i].y,p[j].x,p[j].y)};
	printf("%lld",Kruskal());
	return 0;
}

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round 23 (9.27)

\(\mathcal A\)

求概率题，也就模数换成了 \(147744151\) (还好是质数)

\(\mathcal B\)

类似于是换根 dp

先跑两次 dfs 求一下树的直径，先以 \(1\) 为根跑一次统计转向边的数量，再跑一次 dfs 换根就贡献即可

时间复杂度 \(\mathcal O(n)\)，不知道题解在干什么搞倍增带一只 \(\log\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,D,dis1[N],dis2[N],cst[N],ans,sum;
struct Edge
{
	int v,w,c;
};
vector <Edge> g[N];
void dfs1(int u,int fa)
{
	for(auto [v,w,c]:g[u])
	{
		if(v==fa) continue;
		dis1[v]=dis1[u]+w;
		dfs1(v,u);
	}
}
void dfs2(int u,int fa)
{
	for(auto [v,w,c]:g[u])
	{
		if(v==fa) continue;
		sum+=c;
		dfs2(v,u);
	}
}
void dfs3(int u,int fa,int s)
{
	if(dis1[u]<=D&&dis2[u]<=D) ans=min(ans,s);
	for(auto [v,w,c]:g[u])
	{
		if(v==fa) continue;
		dfs3(v,u,s+(c==1?-1:1));
	}
}
int main()
{
//	freopen("ex_b1.in","r",stdin);
//	freopen("ex_b1.out","w",stdout);
	scanf("%d%d",&n,&D);
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].eb((Edge){v,w,1});
		g[v].eb((Edge){u,w,0});
	}
	int x=0;
	dfs1(1,0);
	for(int i=1;i<=n;i++)
		if(dis1[i]>dis1[x]) x=i;

	dis1[x]=0;
	dfs1(x,0);
	memcpy(dis2,dis1,sizeof(dis1));
	for(int i=1;i<=n;i++)
		if(dis1[i]>dis1[x]) x=i;

	dis1[x]=0;
	dfs1(x,0);
	
	dfs2(1,0);
	
	ans=INF;
	dfs3(1,0,sum);
	printf("%d",ans==INF?-1:ans);
	return 0;
}
/*
6 8
2 1 1
2 3 3
2 4 6
1 5 5
6 1 3
*/

\(\mathcal C\)

神秘题，在序列 \(a\) 的区间 \([l,r]\) 中选 \(k\) 个数，最大化 \(\gcd(b_1,b_2,\dots,b_k)\)

令 \(k^\prime \gets (r-l+1)-k\)，然后不会

\(\mathcal O(n \log^4 V)\) 真能过吗

咕咕咕

\(\mathcal D\)

咕咕咕

Round 24 (9.29)

\(\mathcal A\)

结论题，不过一开始没能立刻看出条件其实推下去就是对于 \(\forall i \in [1,n]\) 都满足

就跟奇偶性有关

\(\mathcal B\)

有点意思，需要选出来的数中 \(\forall i,j \in [L,R],a_i \mid a_j \lor a_j \mid a_i\)

较为简单的数论题，从最大值 \(maxa\) 到 \(1\) 一直枚举，然后进 dfs 剪枝求答案即可

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

\(\mathcal E\)

咕咕咕

Round 25 (10.5)

\(\mathcal A\)

先按 \(l_i\) 从小到大排序，再按 \(r_i\) 从小到大排序

考虑贪心，维护两个小根堆，一个是已匹配的，一个是未匹配的

能匹配的就匹配（废话），不能匹配的从已匹配的中找一个小一点 \(r_j\) 来匹配就好

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define VI vector<int>::iterator
#define PII pair<int,int>
#define mp make_pair
using namespace std;
const int N=4e5+5,INF=0x3f3f3f3f;
int n,ans;
struct dat
{
	int l,r;
}a[N];
bool cmp(dat a,dat b)
{
	return a.l^b.l?a.l<b.l:a.r<b.r;
}
priority_queue<PII,vector<PII>,greater<PII>> X,Y;
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(!Y.empty()&&Y.top().first<a[i].l)
		{
			Y.pop();
			X.push(mp(a[i].r,a[i].l));
		}
		else if(!X.empty()&&X.top().first<a[i].r)
		{
			Y.push(X.top()),X.pop();
			X.push(mp(a[i].r,a[i].l));
		}
		else Y.push(mp(a[i].r,a[i].l));
	}
	printf("%d",X.size());
	return 0;
}

\(\mathcal B\)

咕咕咕

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round 26 (10.6)

\(\mathcal A\)

简单数学题，求方程有整数解 \(x^2-2Bx+C=0,(B,C)\) 的对数

#pragma GCC optimize (3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int T,a[N];
signed main()
{
//	freopen("equation.in","r",stdin);
//	freopen("equation.out","w",stdout);
	for(int i=0;i<=1e6;i++)
		for(int j=i;j>=0;j--)
		{
			if(i*i-j*j>1e6) break;
			a[i*i-j*j]++;
		}
	for(int i=1;i<=1e6;i++) a[i]+=a[i-1];
	scanf("%lld",&T);
	while(T--)
	{
		int L,R;
		scanf("%lld%lld",&L,&R);
		printf("%lld\n",a[R]-a[L-1]);
	}
	return 0;
}
/*
sqrt(B^2-C) = Z
B^2-C=x^2
*/

\(\mathcal B\)

考虑归纳，因为 \(a_i=i\) 会变成不动点，所以在交换的过程中可能需要错排，而错排是有解的

\(\mathcal C\)

洛谷 P6864 [RC-03] 记忆

很好的一道数据结构（DS）题

这题最重要是考虑到如何拆分序列以便于统计与更新答案

发现答案会与某些东西在每个操作都存在一定关系，那么可以试着上矩阵来维护，每次用线段树单点修改、区间查询即可

\(\mathcal D\)

真看不懂给的题解，咕咕咕

Round 27 (10.9)

\(\mathcal A\)

简单数论分块，过

\(\mathcal B\)

确实有点难推出结论

求 \(ax+by=c\) 非负整数对 \((x,y)\) 的个数，其中 \(a \in [0,N],y \in [0,M],x=Fib_{2k+1},y=_{2k+2},k \in \mathbb{N}\)

扩展欧几里得算法(exgcd)即可

用归纳法证明出 \(-Fib_iFib_{i-1}+Fib_{i+1}Fib_{i-2}=1\) 省去 exgcd 的 \(\log\)，笑死，笔者觉得不如观察输出对应的 \((x,y)\) 得出结论简单

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=105;
int T,n,Fib[maxn],X,N,M; 
int solve(int A,int B,__int128 x,__int128 y)
{
	x*=X,y*=X; 
	x-=(-y+A-1)/A*B,y+=(-y+A-1)/A*A;
	if(x<0||y<0) return 0;
	if(x>N) y+=(x-N+B-1)/B*A,x-=(x-N+B-1)/B*B;
	if(y>M) x+=(y-M+A-1)/A*B,y-=(y-M+A-1)/A*A;
	if(x<0||y<0) return 0;
	if(x>N||y>M) return 0;
	return min(x/B,(M-y)/A)+min((N-x)/B,y/A)+1;
} 
signed main()
{
	int T;
	scanf("%lld",&T);
	Fib[1]=Fib[2]=1;
	for(int i=3;i<=100;i++) Fib[i]=Fib[i-1]+Fib[i-2];
	while(T--)
	{
		scanf("%lld%lld%lld",&X,&N,&M);
		if(!X)
		{
			puts("1");
			continue;
		}
		int ans=0;
		for(int i=1;i<=43;i++) ans+=solve(Fib[i*2-1],Fib[i*2],Fib[i*2-1],-Fib[i*2-2]); 
		printf("%lld\n",ans);
	}
    return 0;
}
/*
6
10 6 9
11 9 2
17 7 5
183 54 20
1919 810 114514
1121135 421443 428543
*/

\(\mathcal C\)

AT_joisc2014_e 水筒

先跑一次 bfs 建图，然后跑 Kruskal 最小生成树得到重构树，最后在树上跳倍增 LCA 求答案即可

（思路与 洛谷 P1967 [NOIP2013 提高组] 货车运输 相似，就多了个 bfs 建图个过程）

\(\mathcal D\)

洛谷 P7363 [eJOI2020 Day2] Dots and Boxes

咕咕咕

Round 28 (10.10)

谴责 GJ 今天一开始只放一道题，名字叫做 $ 5$ 道题

\(\mathcal A\)

简单结论题，\(a_1<a_n\) 就符合了，过

\(\mathcal B\)

普通树论题，但是不知道这个结论：划分成大小为 \(k\) 的连通块，当且仅当树上有 \(n/k\) 个点的 \(size\) 是 \(k\) 的倍数

\(\mathcal C\)

思路有点巧妙，暴力是 dp，发现每个物品的价值都很小，考虑大小约为 \(100 \times 100\) 矩阵快速幂加快递推

\(\mathcal D\)

不会，咕咕咕

\(\mathcal E\)

数论题，更加不会，看到答案是对 \(2^{32}\) 取模就知道不简单

挂个柿子以后再来补：

\[\begin{aligned} G(n) &= \prod_{i=1}^{n} (2i-1),G(0)=0 \\ ans &= \sum_{i=0}^{n} \sum_{j=0}^{m} G(i \operatorname{xor} j \operatorname{xor} x) \pmod {2^{32}} \end{aligned} \]

似乎要拆分贡献？

咕咕咕

Round 29 (10.11)

\(\mathcal A\)

傻波一小明就会做亏本买卖是吧

题目在下面写了个 \(u<v\)，才发现是有向无向图 \(DAG\),虽然不一定联通

考虑拓扑排序 + dp，时间复杂度 \(\mathcal O(n+m)\)

\(\mathcal B\)

找规律题，与杨辉三角挂钩

求的就是每一行前 \(a_i+1\) 个数的和，即第 \(a_i\) 列的值

答案为 $ \sum_{i=1}^{n+1} {i+a_i-1 \choose i} $

\(\mathcal C\)

AT_joisc2017_c 手持ち花火 (Sparklers)

所有人都向 \(k\) 号跑最优，考虑时光倒流，二分，check 里贪心，后面不会，咕咕咕

\(\mathcal D\)

有一棵 \(n\) 个点的树，带有边权。现有 \(m\) 个询问如下：在树上选取 \(k_i\) 条路径（树上任意两点的连接通路视为一条路径），其中至少要有一条路径覆盖到点 \(a_i\)，问所有被路径覆盖的边权的和最大是多少。注意重复覆盖的边只会计算一次。

树上问题，不容易发现答案包含直径某一端点，长链剖分，后面不会，咕咕咕

Round 30 (10.14)

\(\mathcal A\)

你作为一名寻宝者，来到了一个古老而神奇的城堡。城堡由多个房间组成，房间之间由墙壁隔开，从一个房间到另一个房间唯一的方法就是任意门传送。

城堡的地图可以由一个 \(n\) 行 \(m\) 列的网格图表示，每个格子可能是空间区域（用 \(1\) 表示）或墙壁区域（用 \(0\) 表示）。任意两个共享一边的空间区域被认为属于同一个房间。

你可以由一个空间区域 \((x_1,y_1)\) 前往另一个空间区域 \((x_2,y_2)\)。

  • 操作 \(1\) - 步行：如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 属于同一个房间，那么你可以花费 \(0\) 体力直接从 \((x_1,y_1)\) 走到 \((x_2,y_2)\)

  • 操作 \(2\) - 任意门传送：如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 不属于同一个房间，那么你可以花费 \(|x_1-x_2|+|y_1-y_2|\) 的体力从 \((x_1,y_1)\) 传送至 \((x_2,y_2)\)

注意，如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 属于同一个房间，你只能选择步行前往，不能通过传送前往。

现在，你计划从位置 \((x_s,y_s)\) 前往位置 \((x_t,y_t)\)，你可以进行任意多次步行和任意门传送。你可以重复经过同一个房间、也可以重复经过同一个空间区域。

为了更好的体验任意门的奇妙感觉，你希望使用传送的次数尽可能多。同时，你所消耗的体力值不能超过直接传送体力值：定义直接传送体力值为至多经过一次传送到达 \((x_t,y_t)\) 的最小体力值消耗。

你想知道，从 \((x_s,y_s)\) 前往任意一个空间区域，在所消耗的体力值不超过直接传送体力值的前提下，最多能够使用多少次传送？

难绷，上来就搞神秘 bfs 题，不会，咕咕咕

\(\mathcal B\)

CF1310E Strange Function

模拟赛上 CF *2900 dp 也是只有 GJ 敢这么干的

（题外话：赛时 puts("1"); 有 \(28\) pts 真不错「伏笔」）

考虑分类讨论

  • \(k=1\) 时，将 \(n\) 个元素划分，上个背包就好

  • \(k=2\) 时，对最终序列从大到小排序，差分再上背包就好

  • \(k>2\) 时，因为答案已经不多了，所以直接搜索剪枝就过了（这就是为啥能总司令了~）

\(\mathcal C\)

构造题

构造每一行形如 $\underline{ryxy} \dots \underline{ryxy} $、大小为 \(40 \times 40\) 的矩阵就好了再把最后一列也这样搞，刚好是 \(2223\) 个，比法定最大 \(n\) 还多 \(1\) 个

然后就交给随机化每次随机更改一个位置求贡献就好了

时间复杂度：\(\mathcal O(Tm^2)\)，其中 \(T=rand(),m=40\)，理论上 \(T ∝ \frac{1}{n}\)

#include<bits/stdc++.h>
#define R 1
#define Y 2
#define X 3
using namespace std;
const int N=45;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
int n,a[N][N],b[N][N];
int query()
{
	int res=0;
	for(int i=1;i<=40;i++)
		for(int j=1;j<=40;j++)
			for(int k=0;k<=6;k+=2)
			{
				if(a[i][j]!=Y) break;
				int A=a[i+dx[k]][j+dy[k]];
				int B=a[i+dx[k+1]][j+dy[k+1]];
				if(A==R&&B==X) res++;
				if(A==X&&B==R) res++;
			}
	return res;
}
mt19937 rd(time(NULL));
int rnd(int l,int r)
{
	return rd()%(r-l+1)+l;
}
void init()
{
	for(int i=1;i<=40;i++)
		for(int j=1;j<=37;j+=4)
			a[i][j]=R,a[i][j+1]=Y,a[i][j+2]=X,a[i][j+3]=Y;
	for(int i=1;i<=37;i+=4)
		a[i][40]=R,a[i+1][40]=Y,a[i+2][40]=X,a[i+3][40]=Y;
}
int main()
{
	scanf("%d",&n);
	init();
	memcpy(b,a,sizeof(a));
	printf("40 40\n");
	while(query()>n)
	{
		int x=rnd(1,40),y=rnd(1,40);
		a[x][y]=X;
		if(query()<n) a[x][y]=b[x][y];
	}
	for(int i=1;i<=40;i++)
	{
		for(int j=1;j<=40;j++)	
			printf("%c",a[i][j]==R?'r':a[i][j]==Y?'y':'x');
		printf("\n");
	}
	return 0;
}

\(\mathcal D\)

对排列 \(\lbrace s_n \rbrace\)，定义 \(g(k,i)=\min(s_i,s_{i+1}, \dots ,s_{i+k-1}),G(k)=\max_{i=1}^{n-k+1} g(k,i)\)

现给出 \(G(1),G(2), \dots ,G(n)\)，求有多少个满足要求的排列。

注：排列 \(\lbrace s_n \rbrace\) 指 \(1\) 到 \(n\) 的 \(n\) 个整数按照任意顺序排成一列后得到的序列，\(s_i\) 表示排在第个位置的数字。例如当 \(n=3\) 时表示长度为 \(3\) 的排列，共有 \(6\) 种可能，分别是：

\(\lbrace1,2,3\rbrace,\lbrace1,3,2\rbrace,\lbrace2,1,3\rbrace,\lbrace2,3,1\rbrace,\lbrace3,1,2\rbrace,\lbrace3,2,1\rbrace\)

咕咕咕

Round 31 (10.17)

我生活在一个绑包的世界里

谴责 GJ 不通知有模拟赛，\(-1.5h\) 打模拟赛时间

\(\mathcal A\)

入机题，模拟即可

一开始还被求最大操作次数给诈骗了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
char st[N];
int main()
{
	scanf("%s",st+1),n=strlen(st+1);
	int ans=0;
	for(int i=2;i<=n;i++)
	{
		int x=st[i-1]-'0'+st[i]-'0';
		if(x<=9) st[i]='0'+x,ans++;
			else st[i-1]='0'+x/10,st[i]='0'+x%10,ans++,i--;
	}
	printf("%d",ans);
	return 0;
}

\(\mathcal B\)

不仅 \(200\) 个点还绑包？

构造题，可参考 AT_abc358_f Easiest Maze，但不是完全一样，还是有点差异的

上下界还是有一定难度想到，毕竟赛后才知道那个 \(2 \mid n, 2 \mid m\) 会使下界 \(+1\)

上界可以考虑直接螺转，下界可以考虑弄一些竖线，然后横着来一刀就差不多了

\(\mathcal C\)

表达式求值的方案数

甚至觉得比 [CSP-J 2022] 逻辑表达式 那题会简单一点，根本不用考虑优先级，全部运算似乎都会用一对 () 包着

开两个栈，一个记 \(0\) 和 \(1\) 的方案数，另一个记运算符，每遇到一个 ) 就计算一次贡献即可

做完了，时间复杂度 \(\mathcal O(n)\)

可以不用像题解那样建表达式树

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+5,mod=998244353;
int n;
char st[N];
stack<PII> ans;
stack<char> opt;
int mul(int x,int y)
{
	return x*y%mod;
}
int add(int x,int y)
{
	return x+y>=mod?x+y-mod:x+y;
}
signed main()
{
	scanf("%s",st+1),n=strlen(st+1);
	for(int i=1;i<=n;i++)
	{
		if(st[i]=='0') ans.push(mp(1,0));
		if(st[i]=='1') ans.push(mp(0,1));
		if(st[i]=='?') ans.push(mp(1,1));
		if(st[i]=='&'||st[i]=='|'||st[i]=='^'||st[i]=='#') opt.push(st[i]);
		if(st[i]==')')
		{
			PII x=ans.top();ans.pop();
			PII y=ans.top();ans.pop();
			char op=opt.top();opt.pop();
			PII res={0,0};
			if(op=='&'||op=='#')
			{
				res.fi=add(add(res.fi,mul(x.fi,y.fi)),add(mul(x.fi,y.se),mul(x.se,y.fi)));
				res.se=add(res.se,mul(x.se,y.se));
			}
			if(op=='|'||op=='#')
			{
				res.fi=add(res.fi,mul(x.fi,y.fi));
				res.se=add(add(res.se,mul(x.fi,y.se)),add(mul(x.se,y.fi),mul(x.se,y.se)));
			}
			if(op=='^'||op=='#')
			{
				res.fi=add(res.fi,add(mul(x.fi,y.fi),mul(x.se,y.se)));
				res.se=add(res.se,add(mul(x.fi,y.se),mul(x.se,y.fi)));
			}
			ans.push(res);
		}
	}
	printf("%lld",ans.top().se);
	return 0;
}

\(\mathcal D\)

在二维平面上有 \(n\) 个点，第 \(i\) 个点 \((x_i,y_i)\) 有权值 \(w_i\)。

可以进行若干次这样的操作：选择两个点 \(u,v\)，将 \(u\) 的权值一部分 \(\Delta w\) 加给 \(v\)，但是要承受 \(d=\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}\) 的损失，即两点间的欧几里得距离。也就是 \(w_u-= \Delta w,w_v+= \max(0,\Delta w-d)\)。

现在你希望所有点中最小的权值的最大，并求出该值。

两点间每操作一次，显然全局点权总和会减少，即 \(\sum w \gets \sum w - \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}\)，那么两点间显然只会操作最多一次

进一步地，操作可以形成一棵树或是森林，且同一个连通块 \(\lvert V \rvert\) 内的最大值为 \(\frac{\sum_{u \in V} w_u - mst}{\lvert V \rvert }\)，其中 \(mst\) 为连通块 \(\lvert V \rvert\) 的最小生成树，上界易证

那么可以先状压求出每个连通块的点权，再 dp 即可

时间复杂度 \(\mathcal O(2^n (n^2+n \log n))\)

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=21,M=N*N;
int n,fa[N];
double dis[N][N],dp[(1<<16)+5];
struct dat
{
	int x,y;
	double w;
}a[N];
int cnt;
struct Edge
{
	int u,v;
	double w;
}e[M];
bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
double distance(dat a,dat b)
{
	return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
double Kruskal()
{
	int tot=0;double mst=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+1+cnt,cmp);
	for(int i=1;i<=cnt;i++)
	{
		int x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		fa[y]=x,mst+=e[i].w;
		if(++tot==n-1) break;
	}
	return mst;
}
int main()
{
//	freopen("desert.in","r",stdin);
//	freopen("desert.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%Lf",&a[i].x,&a[i].y,&a[i].w);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++) dis[i][j]=distance(a[i],a[j]);
	int S=(1<<n)-1;
	for(int i=0;i<=S;i++)
	{
		double sum=0;int siz=0;cnt=0;
		for(int j=1;j<=n;j++)
			if(i&(1<<(j-1))) sum+=a[j].w,siz++;
		for(int j=1;j<n;j++)
			for(int k=j+1;k<=n;k++)
				if(i&(1<<(j-1))&&i&(1<<(k-1)))
					e[++cnt]=(Edge){j,k,dis[j][k]};
		double mst=Kruskal();
		dp[i]=(sum-mst)/siz;
	}
	for(int i=0;i<=S;i++)
		for(int j=i;j;j=(j-1)&i)
			dp[i]=max(dp[i],min(dp[j],dp[j^i]));
	printf("%.10Lf",dp[S]);
	return 0;
}
/*
3
0 0 10
2 0 5
0 5 8
*/

Round 32 (10.18)

又是绑包。。。

\(\mathcal A\)

诈骗题，经过 \(\mathcal O(\log k)\) 次操作之后每个数变为 \(2k\) 或 \(2k+1\)

暴力枚举前 \(50\) 次总和即可，\(m>50\) 的基本都可以看做 \(m=50\)

\(\mathcal B\)

诈骗题，并且成功在赛时把我骗了

因为题目说保证有解且唯一，所以除了 \(s_0\) 会出现奇数次，其他会出现偶数次

所以直接输出出现奇数次的字符，开个桶计数即可

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,len,cnt[31];
char st[N];
int main()
{
//	freopen("history.in","r",stdin);
//	freopen("history.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n<<1;i++)
	{
		scanf("%s",st+1),len=strlen(st+1);
		for(int j=1;j<=len;j++) cnt[st[j]-'a'+1]++;
	}
	scanf("%s",st+1),len=strlen(st+1);
	for(int i=1;i<=len;i++) cnt[st[i]-'a'+1]--;
	for(int i=1;i<=26;i++)
		if(cnt[i]&1) return putchar('a'+i-1),0;
}
/*
2
abcabc
a
abc
b
abcb
*/

\(\mathcal C\)

咕咕咕

\(\mathcal D\)

咕咕咕

Round ? (10.19)

GJ 设成了 IOI 赛制

标签：const,int,Round,咕咕,mathcal,GJ,define
From： https://www.cnblogs.com/lunjiahao/p/18487169

相关文章

  • C语言库函数round函数
    简单使用:把浮点数四舍五入到整数round函数定义在<math.h>头文件中,其原型为doubleround(doublex);round函数用于将浮点数四舍五入到最接近的整数以下的C语言代码用round函数计算了不同浮点数的四舍五入值,并将结果打印出来#include<stdio.h>#include<math.h>intmai......
  • Codeforces Round 977 (Div. 2）
    一万一参赛，赛时排名151A.MeaningMean简单贪心题。显然，排在越后面的数，除以2的次数越少。因此贪心地从小到大计算结果即为答案。#include<bits/stdc++.h>usingnamespacestd;constintN=55;intT,n,a[N];intmain(){ scanf("%d",&T); while(T--){ scanf......
  • GJ Round
    前言：GJRound为学校内部模拟赛记7.13为Round1，在此之前的模拟赛较为混乱以后再说（可能记为Round0或者负数）目前正在倒序更新https://www.luogu.com.cn/article/a30ffmdbRound20(9.18)A......
  • access数据库中的round函数是什么意思
    access数据库中的round函数是内置的四舍五入的函数，主要应用于对带小数位的数据字段进行格式化处理。Round函数的语法如下：Round(number,[numdecimalplaces])，其中，number是要进行四舍五入的数字；numdecimalplaces是可选参数，用于指定要保留的小数位数，如果省略，则默认为0。一、acces......
  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) A-C1
    ​A.MeaningMean2024.10.17算法：模拟，贪心思路：居然时没看题解直接做出来的T^T贪心：题目要求最后剩下的一个数，使得最大那么我们从这个最大的最后一个数思考，最后一个数肯定时由最后两个数进行相加，再除以2，同时上下取整而得到的。方便陈述，我们设最大的最后一个数，也就是最终答案......
  • 软件配置管理活动在 GJB 5000B 评价中的应用
    1 组织机构、角色及职责依据体系要求文件建立两级配置控制委员会：公司配置控制委员会（公司级CCB）和项目配置控制委员会（项目级CCB）。配置管理组为项目级管理配置组（项目级CM）。公司级CCB负责审批产品库的配置项出入库及配置项的Ⅰ类变更。项目级CCB负责审批软件基线建立、受控......
  • 【并查集+dfs】codeforces 1833 E. Round Dance
    题意输入一个正整数\(T(1\leqT\leq10^4)\)，表示接下来输入\(T\)组测试用例，对于每一个测试用例：第一行，输入一个正整数\(n(2\leqn\leq2*10^5)\)第二行，输入\(n\)个正整数\(a_i(1\leqa_i\leqn)\)，表示节点\(i\)到节点\(a_i\)存在一条有向边，保证无自环这\(n......
  • Educational Codeforces Round 166 (Rated for Div. 2) - VP记录
    比赛链接A.VerifyPassword挨个判断即可，秒了。#include<cstdio>#include<cstring>usingnamespacestd;constintN=25;intT,n;charstr[N];boolis_digit(charch){returnch>='0'&&ch<='9';}boolis_lowercase(charch){re......
  • Edu Round 170 Review
    EduRound170ReviewA分析一个很显然的根据前缀划分的贪心，直接指针模拟就好了。Code#include<bits/stdc++.h>usingnamespacestd;intmain(){ intt; cin>>t; while(t--) { stringa,b; cin>>a>>b; intl1=a.length(),l2=b.length(); intp=0; while(p......
  • Codeforces Round 892 (Div. 2)题解记录
    题目链接：https://codeforces.com/contest/1859A.UnitedWeStand选最大的数即可注意题目输出格式 #include<iostream> #include<string.h> #include<map> #include<vector> #include<set> #include<unordered_set> #include<stack> #incl......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99