首页 > 其他分享 >230925校内赛

230925校内赛

时间：2023-09-28 15:44:43浏览次数：41  
标签：校内 int 230925 sum cin re 题解 define

T1 开挂

我卢本伟没有开挂

pPbEt6U.jpg

题解

挺简单的，不过我写的比较麻烦

因为我们需要让多的尽可能多来让少的尽可能少，所以会想到用栈来存储需要更改的数，

靠近栈底就需要更多次数来更改，栈顶则更少

最后只用记录下来所有的次数并按从多到少依次分配从小到大的修改代价

#include<bits/stdc++.h>
#define int unsigned long long
#define N 1000010
using namespace std;
int n，a[N]，b[N]，ans;
vector<int>g;
stack<int>stk;
bool cmp(int x，int y){
	return x>y;
}
signed main(){
	freopen("openhook.in"，"r"，stdin);
	freopen("openhook.out"，"w"，stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	bool flag = true;
	sort(a+1，a+n+1);
	for(int i = 1;i<=n;i++)
		if(a[i]==a[i-1]) flag = false;
	if(flag){
		cout<<"0";
		return 0;
	}
	for(int i = 1;i<=n;i++)
		cin>>b[i];
	sort(b+1，b+n+1);
	for(int i = 1;i<=n;i++){
		if(a[i]==a[i-1]) stk.push(a[i]);
		else{
			int tmp = a[i-1]+1;
			while(stk.size()&&tmp!=a[i]){
				g.push_back(tmp-stk.top());
				stk.pop();tmp++;
			}
		}
	}
	int tmp = a[n]+1;
	while(stk.size()){
		g.push_back(tmp-stk.top());
		stk.pop();tmp++;
	}
	sort(g.begin()，g.end()，cmp);
	for(int i = 0;i<g.size();i++)
		ans+=b[i+1]*g[i];
	cout<<ans;
	return 0;
}

T2 叁仟柒佰万

陈刀仔!

pPbELng.jpg

题解

\(dp\) 题，设 \(f_i\) 表示以 \(i\) 为分界点的方案数有转移方程式别问为什么，问就是不会

\(f_i = \sum f_j [mex([i，j])==K]\)

对于同一个右端点其对应的左端点的 \(mex\) 是单调的，我们可以直接用一个双指针+桶，维护区间的 \(mex\) 是否为 \(K\)

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

#include<bits/stdc++.h>
#define mod 1000000007
#define N 37000010
using namespace std;
int n，a[N]，f[N]，sum[N];
int main(){
	freopen("clods.in"，"r"，stdin);
	freopen("clods.out"，"w"，stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i = 0;i<=n;i++)
			f[i] = 0;
		if(n!=N-10){
			for(int i = 1;i<=n;i++){
				cin>>a[i];
				sum[i] = 0;
			}
		}else{
			int x，y;
			cin>>x>>y;
			for(int i = 0;i<=262144;i++)
				sum[i] = 0;
			for(int i = 2;i<=n;i++)
				a[i] = (1ll*a[i-1]*x+y+i)&262143;
		}
		for(int i = 2;i<=n;i++)
			sum[a[i]] = 1;
		int tmp = 0;
		while(sum[tmp]) tmp++;
		int s = 0;
		for(int i = 0;i<=n;i++)
			sum[i] = 0;
		int p = 1;
		if(tmp){
			for(int i = 1;i<=n;i++){
				if(a[i]<=tmp){
					if(!sum[a[i]]) s++;
					sum[a[i]]++;
					if(s==tmp){
						p = i;
						break;
					}
				}
			}
		}
		int o = 1;
		s = 1;
		for(int i = p;i<=n;i++){
			if(i^p) sum[a[i]]++;
			while(o<i&&(a[o]>tmp||sum[a[o]]>1)){
				sum[a[o]]--;
				s = (s+f[o])%mod;
				o++;
			}
			f[i] = s;
		}
		cout<<f[n]<<"\n";
	}
	return 0;
}

T3 超级加倍

pPbZEM8.jpg

题解

我们先思考对于链的情况

假设我们选出的 \(x\) 在 \(y\) 左边，可以维护 \(L_i,R_i\) 表示 \(i\) 左边第一个 $ > p_i$ 的数，以及 \(i\) 右边第一 个 \(<p_i\) 的数可以单调栈预处理

两个点合法当且仅当 \(R_x>y\) 且 \(L_y<x\)，可以看成一个三维偏序问题做到 \(\mathcal O(n\log^2n)\)

但是可以忽略 \(x<y\) 这个条件， 这样会把所有的 \(x>y\) 统计为合法，最后减去即可， 时间复杂 度 \(\mathcal O(n\log n)\)

我们再思考对于树的问题

可以考虑点分治，每次处理过分治中心的点对， 一个点合法需要满足是到根的最小值或最大值，另外需要求出路径最小值或最大值来和路径的另外一边合并

合并时仍存在二维偏序的限制，必定会带一 个 \(\log\)， 无法优化， 时间复杂度 \(\mathcal O(n\log^2n)\)

对比前面两个算法发现毫不相关， 且点分治本身并没有利用到太多性质

再来看一看前面的东西，\(R_x>y\) 这类性质可以联想到笛卡尔树， 而笛卡尔树在树上的一个很类似的形态是 \(Kruskal\) 重构树

按点权从小到大建树建成 \(T_1\)，从大到小建成 \(T_2\) (满足任意两点 \(x,y\) 在 \(T_1\) 中的 \(lca\) 是路径最小值， 在 \(T_2\) 中是路径最大值)

以上部分可以用并查集实现， 那么两点 \(x,y\) 满足条件当且仅当 \(x\) 在 \(T_1\) 中是 \(y\) 的祖先， \(y\) 在 \(T_2\) 中是 \(x\) 的祖先

这是一个朴素的偏序问题， 在 \(T_1\) 中求出 \(DFS\) 序， 在 \(T_2\) 上 \(DFS\)， 用一个树状数组维护可行答案

时间复杂度 \(\mathcal O(n \log n)\)，由于复杂度瓶颈在树状数组，常数非常小

#include<bits/stdc++.h>
#define N 2000010
using namespace std;
int n，tim，cnt，p[N]，h[N]，dfn[N]，t[N]，siz[N];
long long ans;
struct edge{
	int v，ne;
}e[N<<2];
struct tree{
	edge e1[N];
	int cnt，h1[N]，fa[N];
	bool vis[N];
	int find_(int x){
		return x==fa[x]?x:fa[x] = find_(fa[x]);
	}
	void add(int u，int v){
		e1[++cnt].v = v;
		e1[cnt].ne = h1[u];
		h1[u] = cnt;
	}
	void build(){
		for(int i = 1;i<=n;i++) fa[i] = i;
		for(int i = 1;i<=n;i++){
			vis[p[i]] = 1;
			for(int j = h[p[i]];j;j = e[j].ne){
				int v = e[j].v;
				if(vis[v]){
					v = find_(v);
					add(p[i]，v);
					fa[v] = p[i];
				}
			}
		}
	}
}T1，T2;
void add(int u，int v){
	e[++cnt].v = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int ask(int x){
	int res = 0;
	for(;x;x-=x&(-x))
		res+=t[x];
	return res;
}
void change(int x，int v){
	for(;x<=n;x+=x&(-x))
		t[x]+=v;
}
void dfs(int x){
	dfn[x] = ++tim;
	siz[x] = 1;
	for(int i = T1.h1[x];i;i = T1.e1[i].ne){
		dfs(T1.e1[i].v);
		siz[x]+=siz[T1.e1[i].v];
	}
}
void calc(int x){
	ans+=ask(dfn[x]+siz[x]-1)-ask(dfn[x]);
	change(dfn[x]，1);
	for(int i = T2.h1[x];i;i = T2.e1[i].ne)
		calc(T2.e1[i].v);
	change(dfn[x]，-1);
}
signed main(){
	freopen("charity.in"，"r"，stdin);
	freopen("charity.out"，"w"，stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
		p[i] = n-i+1;
	for(int i = 1;i<=n;i++){
		int x;
		cin>>x;
		if(x){
			add(x，i);add(i，x);
		}
	}
	T1.build();
	reverse(p+1，p+n+1);
	T2.build();
	dfs(1);
	calc(n);
	cout<<ans;
	return 0;
}

T4 欢乐豆

你们觉得我像是会的样子吗？

pPbDAqU.jpg

题解

pPbDuGR.jpg

#include<bits/stdc++.h>
#define re register
using namespace std;
char rbuf[20000002];
int pt=-1;
inline int read(){
	re int t=0;re char v=rbuf[++pt];
	while(v<'0')v=rbuf[++pt];
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=rbuf[++pt];
	return t;
}
int mn[12002],pos[12002],n,m,head[100002],cnt,fa[100002],a[100002],tg[12002],inf=1e9,X,Y,Z,sum[12002],dis[3002],pp[100002],pmn[100002],smn[100002];
struct edge{int to,next,w;}e[3002];
struct node{int x,y;bool operator <(const node A)const{return x<A.x;};};
long long ans;
inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
vector<int>v[100002];
vector<node>E[3002];
inline void pu(re int p){
	if(!sum[p]){mn[p]=inf;return;}
	if(mn[p<<1]<mn[p<<1|1])mn[p]=mn[p<<1],pos[p]=pos[p<<1];
	else mn[p]=mn[p<<1|1],pos[p]=pos[p<<1|1];
}
inline void CG(re int x,re int y){
	if(!sum[x])return;
	tg[x]=min(tg[x],y);
	mn[x]=min(mn[x],y);
}
inline void pd(re int p){
	if(tg[p]^inf){
		CG(p<<1,tg[p]),CG(p<<1|1,tg[p]);
		tg[p]=inf;
	}
}
inline void del(re int p,re int l,re int r){
	--sum[p];
	if(l==r){pos[p]=0,mn[p]=inf;return;}
	pd(p);
	re int mid=l+r>>1;
	if(X<=mid)del(p<<1,l,mid);
	else del(p<<1|1,mid+1,r);
	pu(p);
}
inline void cg(re int p,re int l,re int r){
	if(!sum[p])return;
	if(l>=X&&r<=Y)return CG(p,Z);
	pd(p);
	re int mid=l+r>>1;
	if(X<=mid)cg(p<<1,l,mid);
	if(Y>mid)cg(p<<1|1,mid+1,r);
	pu(p);
}
inline void build(re int p,re int l,re int r){
	sum[p]=r-l+1,tg[p]=inf;
	if(l==r){mn[p]=inf-1,pos[p]=l;return;}
	re int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pu(p);
}
inline void work(re int x){
	for(re int i=0;i<v[x].size();++i)pp[v[x][i]]=i+1;
	re int S=v[x].size();
	for(re int i=1;i<=S;++i)E[i].clear();
	for(re int i=0;i<S;++i)for(re int j=head[v[x][i]];j;j=e[j].next)E[i+1].push_back((node){pp[e[j].to],e[j].w});
	for(re int i=1;i<=S;++i)sort(E[i].begin(),E[i].end());
	for(re int i=1;i<=S;++i){
		build(1,1,S),X=Y=i,Z=0,cg(1,1,S);
		for(re int j=1;j<=S;++j){
			re int z=pos[1];dis[z]=mn[1];
			X=z,del(1,1,S);
			re int lst=0;
			for(re int k=0;k<E[z].size();++k){
				if(E[z][k].x-1>lst)X=lst+1,Y=E[z][k].x-1,Z=dis[z]+a[v[x][z-1]],cg(1,1,S);
				X=Y=E[z][k].x,Z=dis[z]+min(a[v[x][z-1]]+min(pmn[x-1],smn[x+1]),E[z][k].y),cg(1,1,S),lst=E[z][k].x;
			}
			if(lst^S)X=lst+1,Y=S,Z=dis[z]+a[v[x][z-1]],cg(1,1,S);
		}
		re int mn=a[v[x][i-1]];
		for(re int j=1;j<=S;++j)if(j^i)ans+=dis[j],mn=min(mn,dis[j]+a[v[x][j-1]]);
		ans+=1ll*mn*(n-v[x].size());
	}
}
signed main(){
	freopen("happybean.in","r",stdin);
	freopen("happybean.out","w",stdout);
	fread(rbuf,1,20000000,stdin);
	n=read(),m=read();
	for(re int i=1;i<=n;++i)a[i]=read(),fa[i]=i;
	for(re int i=1,x,y,z;i<=m;++i){
		x=read(),y=read(),z=read();
		e[++cnt]=(edge){y,head[x],z},head[x]=cnt;
		fa[root(x)]=root(y);
	}
	for(re int i=1;i<=n;++i)v[root(i)].push_back(i);
	pmn[0]=inf;
	for(re int i=1;i<=n;++i){
		pmn[i]=pmn[i-1];
		if(i==root(i))for(re int j=0;j<v[i].size();++j)pmn[i]=min(pmn[i],a[v[i][j]]);
	}
	smn[n+1]=inf;
	for(re int i=n;i;--i){
		smn[i]=smn[i+1];
		if(i==root(i))for(re int j=0;j<v[i].size();++j)smn[i]=min(smn[i],a[v[i][j]]);
	}
	for(re int i=1;i<=n;++i)if(i==root(i))work(i);
	printf("%lld",ans);
}

标签：校内,int,230925,sum,cin,re,题解,define
From： https://www.cnblogs.com/cztq/p/17735946.html

相关文章

  • 230927校内赛
    T1集合题解很明显的一道树形\(dp\)题我也没看出来dalao们说有一道\(ddp\)的题转移方式一模一样于是都切了，就我是sb首先有一个非常明显的性质在于所有的被选的点一定是可以构成一颗连通子树的最终选取的\(k\)个点一定是从这颗子树中最远点对的一个点沿着这颗子树直......
  • 20230925
    //charge,designate,duration,duty,gross,guarantee,invoice,net,penalty,refund,specification,statement,stipulation,supplier,tare,billofladingcharge-费用Ingeneral,achargereferstotheamountofmoneythatisrequiredtobepaidforap......
  • 校内互测第一周(East!XI~East!XV)总结(窝还是退役吧QAQ
    ==真是不想说啥了。。。像我这种沙茶蒟蒻还是早点滚粗的好。。。Day1East!XI出题人：18357打开题瞬间傻了。。。三道树上问题。。。三道。。。T1：给定一棵N个节点的无根树，求每个节点到其它的节点的∑(路径长度xorM)。M<=15TM这傻逼题我写了个0~15的Trie树。。。明明记录个0~15的数......
  • 20230925打卡
    今天我参加了传统工程实训，并学习了Java中的类与对象。在传统工程实训中，我们通过实践来加强实际操作能力和问题解决能力。另外，我还学习了Java中的类与对象，这是构建Java应用程序的基础。通过学习类与对象的概念、属性和方法等基本知识，我能够了解如何在Java中创建和使用类与对象，并运......
  • 230729校内赛
    回文一句话题意：从左上角到右下角的路径上的字母能组成回文串的路径有几条题解暴力做法是从左上角和右下角分别往对方\(dp\)，复杂度为\(\mathcalO(n^4)\)因为状态只有在\(x1+x2+y1+y2=n+m+2\)时合法，则确定三个变量即可推出剩下一个变量，复杂度为\(\mathcalO(n^3)\)......
  • 每日总结20230925
    代码时间（包括上课）5h代码量（行）：400行博客数量（篇）：1篇相关事项：1、今天上午进行的是相关大数据的测试，老师具体讲了讲相关题目的注意事项。2、今天上午没有完成该题目的编程，只能下午继续努力了。3、晚上问了问编程大佬，对具体的代码的使用有了新的认识，对该题目也就编的差不多了，剩下的......
  • 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.9.9\)）（本来是不想写的，但是看到学长以及身边人都写，思考了一下，感觉有点用，于是也写了）（里面也写了一些闲话）（以前的比赛我就记个排名得了，懒得补了）7.20~7.22CSP模拟1~3没考7.24CSP模拟4(rk6)7.25CSP模拟5(rk3)7.26CSP模拟6(rk23)7.27......
  • 230722校内赛
    T1CF576D题解我们根据边的出现时间分成\(m\)段对于每一段，设\(f_{T,i}\)表示\(T\)时刻，\(i\)节点能否走到，那么走一步就是个矩阵乘法对于某一段，我们从终点开始bfs可以就可以求出答案，矩阵乘法用bitset优化复杂度\(\mathcal{O}(m^2+\frac{ω}{mn^3}logT)\)#includ......
  • 230719校内赛
    T1usaco20febEquilateralTrianglesP题面我就不描述了题解首先我们是不可能暴力计算每一对点距离的我们可以想一想如何将斜着的数个点转换为横着或竖着的数个点，这样会使我们的计算方便许多不难想到的是切比雪夫距离，当然考场上也容易推出这玩意（我就是考场现推的）然后就是如......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99