GJ Round

标签：return log int res Round ans mathcal GJ

前言：

GJ Round 为学校内部模拟赛

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

目前正在倒序更新

https://www.luogu.com.cn/article/a30ffmdb

Round 20 (9.18)

A \mathcal A A

简单数学题

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

答案即为 a n s = ∑ i = 1 n ( ( i − 1 a i − 1 ) × 2 n − i ) ( m o d 1 0 9 + 7 ) ans=\sum_{i=1}^{n} ({i-1 \choose a_i-1} \times 2^{n-i}) \pmod {10^9+7} ans=∑i=1n((ai−1i−1)×2n−i)(mod109+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;
}

B \mathcal B B

按顺序从 1 1 1 到 n n 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;
}

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

C \mathcal C C

CF875F Royal Questions

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

求最大权值基环森林

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

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

D \mathcal D D

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

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

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

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

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

数据结构（DS）题

咕咕咕

Round 21 (9.19)

A \mathcal A A

~~SB 题，还什么困难卷积~~

不同的 a i , b i a_i,b_i ai,bi 只有 O ( s u m ) \mathcal O(\sqrt{sum}) O(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
*/

B \mathcal B B

CF623C Electric Charges

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

C \mathcal C C

数论题，不会做

a n s = ∑ i = 0 p − 1 a i × m i ( m o d p ) p ∈ P r i m e , m ∈ [ 1 , p ) , a 0 = 1 , a 1 = 1 , a 2 = 6 , … 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 ans=i=0∑p−1ai×mi(modp)p∈Prime,m∈[1,p),a0=1,a1=1,a2=6,…

a i a_i ai 是杨辉三角中间对称轴的那一列

咕咕咕

D \mathcal D D

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

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

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

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

数据结构（DS）题

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

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

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

最后再把一开始部落占有的矿洞再 query m m 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)

A \mathcal A A

小模拟麻将题

先考虑 n = 14 n=14 n=14

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

若 k = 3 , 4 k=3,4 k=3,4 枚举雀头再检验剩下的牌是刻子还是顺子
在考虑 n = 13 n=13 n=13

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

B \mathcal B B

人类智慧题

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

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

#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;
}

C \mathcal C C

咕咕咕

D \mathcal D D

咕咕咕

Round 23 (9.27)

A \mathcal A A

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

B \mathcal B B

类似于是换根 dp

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

时间复杂度 O ( n ) \mathcal O(n) O(n)，不知道题解在干什么搞倍增带一只 log ⁡ \log 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
*/

C \mathcal C C

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

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

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

咕咕咕

D \mathcal D D

咕咕咕

Round 24 (9.29)

A \mathcal A A

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

就跟奇偶性有关

B \mathcal B B

有点意思，需要选出来的数中 ∀ i , j ∈ [ L , R ] , a i ∣ a j ∨ a j ∣ a i \forall i,j \in [L,R],a_i \mid a_j \lor a_j \mid a_i ∀i,j∈[L,R],ai∣aj∨aj∣ai

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

C \mathcal C C

咕咕咕

D \mathcal D D

咕咕咕

E \mathcal E E

咕咕咕

Round 25 (10.5)

A \mathcal A A

先按 l i l_i li 从小到大排序，再按 r i r_i ri 从小到大排序

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

能匹配的就匹配（废话），不能匹配的从已匹配的中找一个小一点 r j r_j rj 来匹配就好

#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;
}

B \mathcal B B

咕咕咕

C \mathcal C C

咕咕咕

D \mathcal D D

咕咕咕

Round 26 (10.6)

A \mathcal A A

简单数学题，求方程有整数解 x 2 − 2 B x + C = 0 , ( B , C ) x^2-2Bx+C=0,(B,C) x2−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
*/

B \mathcal B B

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

C \mathcal C C

洛谷 P6864 [RC-03] 记忆

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

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

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

D \mathcal D D

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

Round 27 (10.9)

A \mathcal A A

简单数论分块，过

B \mathcal B B

确实有点难推出结论

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

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

用归纳法证明出 − F i b i F i b i − 1 + F i b i + 1 F i b i − 2 = 1 -Fib_iFib_{i-1}+Fib_{i+1}Fib_{i-2}=1 −FibiFibi−1+Fibi+1Fibi−2=1 省去 exgcd 的 log ⁡ \log log，笑死，笔者觉得不如观察输出对应的 ( x , y ) \sout{(x,y)} (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
*/

C \mathcal C C

AT_joisc2014_e 水筒

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

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

D \mathcal D D

洛谷 P7363 [eJOI2020 Day2] Dots and Boxes

咕咕咕

Round 28 (10.10)

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

A \mathcal A A

简单结论题， a 1 < a n a_1<a_n a1<an 就符合了，过

B \mathcal B B

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

C \mathcal C C

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

D \mathcal D D

不会，咕咕咕

E \mathcal E E

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

挂个柿子以后再来补：

G ( n ) = ∏ i = 1 n ( 2 i − 1 ) , G ( 0 ) = 0 a n s = ∑ i = 0 n ∑ j = 0 m G ( i xor ⁡ j xor ⁡ x ) ( m o d 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} G(n)ans=i=1∏n(2i−1),G(0)=0=i=0∑nj=0∑mG(ixorjxorx)(mod232)

似乎要拆分贡献？

咕咕咕

Round 29 (10.11)

A \mathcal A A

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

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

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

B \mathcal B B

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

求的就是每一行前 a i + 1 a_i+1 ai+1 个数的和，即第 a i a_i ai 列的值

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

C \mathcal C C

AT_joisc2017_c 手持ち花火 (Sparklers)

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

D \mathcal D D

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

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

Round 30 (10.14)

A \mathcal A A

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

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

你可以由一个空间区域 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 前往另一个空间区域 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)。

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

操作 2 2 2 - 任意门传送：如果 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 不属于同一个房间，那么你可以花费 ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1−x2∣+∣y1−y2∣ 的体力从 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 传送至 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)

注意，如果 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 属于同一个房间，你只能选择步行前往，不能通过传送前往。

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

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

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

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

B \mathcal B B

CF1310E Strange Function

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

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

考虑分类讨论

k = 1 k=1 k=1 时，将 n n n 个元素划分，上个背包就好
k = 2 k=2 k=2 时，对最终序列从大到小排序，差分再上背包就好
k > 2 k>2 k>2 时，因为答案已经不多了，所以直接搜索剪枝就过了（这就是为啥能总司令了~）

C \mathcal C C

构造题

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

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

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

#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;
}

D \mathcal D D

对排列 { s n } \lbrace s_n \rbrace {sn}，定义 g ( k , i ) = min ⁡ ( s i , s i + 1 , … , s i + k − 1 ) , G ( k ) = max ⁡ i = 1 n − k + 1 g ( k , i ) 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(k,i)=min(si,si+1,…,si+k−1),G(k)=maxi=1n−k+1g(k,i)

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

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

{ 1 , 2 , 3 } , { 1 , 3 , 2 } , { 2 , 1 , 3 } , { 2 , 3 , 1 } , { 3 , 1 , 2 } , { 3 , 2 , 1 } \lbrace1,2,3\rbrace,\lbrace1,3,2\rbrace,\lbrace2,1,3\rbrace,\lbrace2,3,1\rbrace,\lbrace3,1,2\rbrace,\lbrace3,2,1\rbrace {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}

咕咕咕

Round 31 (10.17)

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

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

A \mathcal A 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;
}

B \mathcal B B

不仅 200 200 200 个点还绑包？

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

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

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

C \mathcal C C

表达式求值的方案数

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

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

做完了，时间复杂度 O ( n ) \mathcal O(n) 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;
}

D \mathcal D D

在二维平面上有 n n n 个点，第 i i i 个点 ( x i , y i ) (x_i,y_i) (xi,yi) 有权值 w i w_i wi。

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

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

两点间每操作一次，显然全局点权总和会减少，即 ∑ w ← ∑ w − ( x u − x v ) 2 + ( y u − y v ) 2 \sum w \gets \sum w - \sqrt{(x_u-x_v)^2+(y_u-y_v)^2} ∑w←∑w−(xu−xv)2+(yu−yv)2 ，那么两点间显然只会操作最多一次

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

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

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

#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)

又是绑包。。。

A \mathcal A A

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

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

B \mathcal B B

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

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

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

#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
*/

C \mathcal C C

咕咕咕

D \mathcal D D

咕咕咕

Round ? (10.19)

GJ 设成了 IOI 赛制

标签：return,log,int,res,Round,ans,mathcal,GJ
From： https://blog.csdn.net/lunjiahao/article/details/143029117

Round 20 (9.18)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 21 (9.19)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 22 (9.24)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 23 (9.27)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 24 (9.29)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

E \mathcal E E

Round 25 (10.5)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 26 (10.6)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 27 (10.9)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 28 (10.10)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

E \mathcal E E

Round 29 (10.11)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 30 (10.14)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 31 (10.17)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round 32 (10.18)

A \mathcal A A

B \mathcal B B

C \mathcal C C

D \mathcal D D

Round ? (10.19)

相关文章

赞助商

阅读排行