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

231110校内赛

时间：2023-11-10 20:24:50浏览次数：30  
标签：tmp 校内 231110 int pos mathcal now mxdep

T1 拼图

首先一点需要明白的是横向移动和纵向移动并无关联

接着我们可以花费 \(\mathcal O (k)\) 的时间来枚举左右最长长度和上下最长长度

我们只需要在两次循环时分别排个序，左右和上下分别排序

对于左右移动时，我们枚举每一个点在最左或最右的情况，计算出当前最小的长度，并更新最小步数

最小长度可以 \(\mathcal O(1)\) 计算，因为排完序后在它的左右的就是移到一段后最远的点

可以自己手模一下

对于上下同理

代码很史，建议自己写，有两个循环其实可以省

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct node{
	int x,y;
}a[N];
int n,h,w,mnl,mnr,ans1,ans2;
long long ans;
bool cmp(node x,node y){
	return x.x<y.x;
}
bool cmp1(node x,node y){
	return x.y<y.y;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>h>>w>>n; 
	for(int i = 1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	mnl = mnr = 0x3f3f3f3f;
	sort(a+1,a+n+1,cmp);
	mnl = a[n].x-a[1].x+1;
	for(int i = 2;i<=n;i++){
		int tmp = h+a[i-1].x-a[i].x+1;
		if(mnl>tmp){
			ans1 = h-a[i].x+1;
			mnl = tmp;
		}else if(mnl==tmp)
			ans1 = min(ans1,h-a[i].x+1);
	}
	for(int i = 1;i<n;i++){
		int tmp = h+a[i].x-a[i+1].x+1;
		if(mnl>tmp){
			ans1 = a[i].x;
			mnl = tmp;
		}else if(mnl==tmp)
			ans1 = min(ans1,a[i].x);
	}
	sort(a+1,a+n+1,cmp1);
	mnr = a[n].y-a[1].y+1;
	for(int i = 2;i<=n;i++){
		int tmp = w+a[i-1].y-a[i].y+1;
		if(mnr>tmp){
			ans2 = w-a[i].y+1;
			mnr = tmp;
		}else if(mnr==tmp)
			ans2 = min(ans2,w-a[i].y+1);
	}
	for(int i = 1;i<n;i++){
		int tmp = w+a[i].y-a[i+1].y+1;
		if(mnr>tmp){
			ans2 = a[i].y;
			mnr = tmp;
		}else if(mnr==tmp)
			ans2 = min(ans2,a[i].y);
	}
	cout<<1ll*mnl*mnr<<" "<<ans1+ans2;
	return 0;
}

T2 小凯的疑惑

我也挺疑惑的

临时加的题，专门为某位大神准备的，就不说了

我也没写

T3 时间复杂度

有人乱搞搞到了 \(80\) 分，狠狠羡慕了

对于正解来说其实就是 \(\mathcal O(n\sqrt n)\) 的一个优化

\(\mathcal O(n\sqrt n)\) 就是先处理出假设选整个序列后每一个没有达到颜色要求的点的位置

按照这些点的位置划分为一些区间，然后进行同样步骤递归求解

对于正解来说我们先从两边向中找到一个分割点，区间肯定是一大一小，先处理大区间再处理小区间

处理一个区间时记得先在 \(cnt\) 数组中除去另一个区间的点，最后再加回来

每一次复杂度只有 \(\mathcal O(小区间)\) 的，所以理论上是 \(\mathcal O(n \log n)\) 的

如果没有分割点就统计答案，依然递归实现

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,cnt[N],a[N],b[N],ans;
void dfs(int x,int y){
	if(y<x) return ;
	int l = x,r = y;
	int lim = b[y-x+1];
	while(cnt[a[l]]>=lim&&l<r&&cnt[a[r]]>=lim){
		l++;r--;
	}
	if(cnt[a[l]]<lim){
		for(int i = x;i<=l;i++) cnt[a[i]]--;
		dfs(l+1,y);
		for(int i = x;i<l;i++) cnt[a[i]]++;
		dfs(x,l-1);
	}else if(cnt[a[r]]<lim){
		for(int i = r;i<=y;i++) cnt[a[i]]--;
		dfs(x,r-1);
		for(int i = r+1;i<=y;i++) cnt[a[i]]++;
		dfs(r+1,y);
	}else{
		ans = max(ans,y-x+1);
		for(int i = x;i<=y;i++) cnt[a[i]]--;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i = 1;i<=n;i++)
		cin>>b[i];
	dfs(1,n);
	cout<<ans;
	return 0;
}

T4 一些情报

相当于是支持：断开一条边，查询距离一个点的最远点

不妨设现在要求的点为 \(x\)，断开的是 \(y\) 到他父亲的边，我们来考虑三种情况：

  1. \(x\) 在 \(y\) 的子树内
  2. \(y\) 在 \(x\) 的子树内
  3. \(x,y\) 的 \(lca\) 在他们两个点的上方

对于情况 1 ，我们维护一个点在子树内的最长链，次长链，以及 \(x\) 到 \(y\) 的路径上往外延伸的最长路径

对于情况 2 ，我们维护 \(y\) 到 \(x\) 的路径上往外延伸的最长路径（这里不同于情况 1，这里维护的最长路径是到根最长），以及 \(x\) 子树内的最长链, 次长链, 次次长链, 还有 \(x\) 到根路径上往外延伸的最长路径

对于情况 3 ，跟前面两种情况类似，相当于结合起来多考虑几种情况

最长链，次长链，次次长链都可以在 \(\mathcal O(n)\) 的时间内预处理出，往外延伸的最长路径可以通过倍增预处理每次 \(\mathcal O(\log n)\) 的时间内求出

所以总复杂度 \(\mathcal O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
}
const int Maxn=2e5+50;
int n,m,ind,rt=1,powG[50],fa[Maxn][23],dis[Maxn],mxdep[Maxn][3],from[Maxn][2],depfa[Maxn][23],depfa2[Maxn][23],dfn[Maxn],in[Maxn],out[Maxn];
vector<int>edge[Maxn];
inline void dfs(int now,int f){
    fa[now][0]=(f?f:now);dis[now]=dis[f]+1;
    dfn[now]=++ind;in[now]=dfn[now]+1;
    for(int i=1;i<=20;i++){fa[now][i]=fa[fa[now][i-1]][i-1];}
    for(int e=edge[now].size()-1;e>=0;e--){
        int v=edge[now][e];
        if(v==f)continue;
        dfs(v,now);
        if(mxdep[v][0]+1>mxdep[now][0]){
            mxdep[now][2]=mxdep[now][1];
            mxdep[now][1]=mxdep[now][0];
            from[now][1]=from[now][0];
            mxdep[now][0]=mxdep[v][0]+1;
            from[now][0]=v;
        }else if(mxdep[v][0]+1>mxdep[now][1]){
            mxdep[now][2]=mxdep[now][1];
            mxdep[now][1]=mxdep[v][0]+1;
            from[now][1]=v;
        }else if(mxdep[v][0]+1>mxdep[now][2]){
            mxdep[now][2]=mxdep[v][0]+1;
        }
    }
    out[now]=ind;
}
inline void dfs2(int now,int f){
    if(now!=1){
        depfa[now][0]=(from[f][0]==now)?(mxdep[f][1]+1):(mxdep[f][0]+1);
        depfa2[now][0]=(from[f][0]==now)?(mxdep[f][1]+dis[f]):(mxdep[f][0]+dis[f]);
    }
    for(int i=1;i<=20;i++){
        depfa[now][i]=max(depfa[now][i-1],depfa[fa[now][i-1]][i-1]+dis[now]-dis[fa[now][i-1]]);
        depfa2[now][i]=max(depfa2[now][i-1],depfa2[fa[now][i-1]][i-1]);
    }
    for(int e=edge[now].size()-1;e>=0;e--){
        int v=edge[now][e];
        if(v==f)continue;
        dfs2(v,now);
  #include<bits/stdc++.h>
#define int long long 
#define N 200010
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
struct node{
	int l,r;
}t[N<<2],ans;
int n,m,cnt,dfncnt,dep[N],f[N<<1][20],fa[N][20],dis[N],dfn[N];
int siz[N],id[N],pos[N<<1],lg[N<<1];
vector<int>g[N];
inline int min(int x,int y){
	return (dep[x]<=dep[y])?x:y;
}
inline int lca(int l,int r){
	l = dis[l];r = dis[r];
	if(l>r) swap(l,r);
	int k = lg[r-l+1];
	return min(f[l][k],f[r-(1<<k)+1][k]);
}
inline int dist(int x,int y){
	int l = lca(x,y);
	return dep[x]+dep[y]-2*dep[l];
}
node operator+(node x,node y){
	if(!x.l) return y;
	if(!y.l) return x;
	node tmp;tmp.l = x.l;tmp.r = x.r;
	int res = -1,c[4] = {x.l,x.r,y.l,y.r};
	sort(c,c+4);
	int tot = unique(c,c+4)-c;
	for(int i = 0;i<tot;i++){
		for(int j = i+1;j<tot;j++){
			int idx = dist(c[i],c[j]);
			if(idx>res){
				res = idx;
				tmp.l = c[i];tmp.r = c[j];
			}
		}
	}
	return tmp;
}
inline int jump(int x,int y){
	for(int i = 17;i>=0;i--)
		if((y>>i)&1) x = fa[x][i];
	return x;
}
inline void dfs(int x,int father){
	fa[x][0] = father;
	for(int i = 1;i<=17;i++)
		fa[x][i] = fa[fa[x][i-1]][i-1];
	dep[x] = dep[father]+1;
	pos[++cnt] = x;dis[x] = cnt;
	dfn[x] = ++dfncnt;
	id[dfncnt] = x;siz[x] = 1;
	for(int v : g[x]){
		if(v==father) continue;
		dfs(v,x);
		pos[++cnt] = x;
		siz[x]+=siz[v];
	}
}
inline void pushup(int p){
	t[p] = t[lc]+t[rc];
}
inline void build(int p,int l,int r){
	if(l==r){
		t[p].l = t[p].r = id[l];
		return ;
	}
	int mid = (l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
inline void query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		ans = ans+t[p];
		return ;
	}
	int mid = (l+r)>>1;
	if(ql<=mid) query(lc,l,mid,ql,qr);
	if(qr>mid) query(rc,mid+1,r,ql,qr);
}
inline void init(){
	lg[0] = -1;
	for(int i = 1;i<=cnt;i++)
		lg[i] = lg[i>>1]+1;
	for(int i = 1;i<=cnt;i++)
		f[i][0] = pos[i];
	for(int i = 1;(1<<i)<=cnt;i++)
		for(int j = 1;j+(1<<i)-1<=cnt;j++)
			f[j][i] = min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<n;i++){
		int x,y;cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	init();
	build(1,1,n);
	cin>>m;
	int rt = 0;
	for(int i = 1;i<=m;i++){
		char opt;int x,y;
		cin>>opt;
		if(opt=='C') cin>>rt;
		else{
			cin>>x>>y;
			int tmp = lca(x,rt);
			int len = dep[x]-dep[tmp];
			ans.l = ans.r = 0;
			int pos = 0;
			if(y<=len) pos = jump(x,y-1);
			else{
				int idx = dep[rt]-dep[tmp]-(y-len);
				if(idx<0) pos = 1;
				else pos = jump(rt,idx);
			}
			if(dfn[x]<=dfn[pos]+siz[pos]-1&&dfn[x]>=dfn[pos])
				query(1,1,n,dfn[pos],dfn[pos]+siz[pos]-1);
			else query(1,1,n,1,dfn[pos]-1),query(1,1,n,dfn[pos]+siz[pos],n);
			int res = max(dist(ans.l,x),dist(ans.r,x));
			cout<<res<<"\n";
		}
	}
	return 0;
}

标签：tmp,校内,231110,int,pos,mathcal,now,mxdep
From： https://www.cnblogs.com/cztq/p/17824947.html

相关文章

  • 20231110_stack_queue
    课程笔记https://www.cnblogs.com/hellohebin/p/15677386.html上课代码//1-10/*//test1#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intsta[N],head=0;intn,x;intmain(){cin>>n;for(inti=1;i<=n;i++){ci......
  • 231110练习赛总结
    231110练习赛总结T1Alchemy几点反思：对最大不敏感，确定了题目涉及\(DAG\)之后只知道盲目用\(topsort\)处理，而没有想到二分,积累经验。想复杂了，其实根本不用\(topsort\),因为限制了边的起点一定小于终点，且制造每个金属只有一种方案，也就是说所有指向该点的边同属于一种......
  • 20231110打卡
    早上，我按照计划开始了新一轮的学习。我花了一些时间复习之前学过的算法知识，并解决了一些算法练习题。通过不断思考和练习，我巩固了自己对算法的理解，并且提升了解决问题的能力。下午，由于天气很冷，我和一些同学相约去打球放松一下。尽管天气寒冷，但是打球的过程中我们感到温暖和快乐。......
  • 231108校内赛
    T1最大公约数数据极水，啥都能过第一种方法，暴力剪枝，直接飞过，\(\mathcalO(N^2\logn)\)过\(30\)万不解释玛德有人在提交时不写输出直接爆零#include<bits/stdc++.h>#defineN300010usingnamespacestd;intn,k,ans,a[N];intgcd(inta,intb){ returnb==0?a:gcd(b,......
  • 231106校内赛
    T1点分树很简单的思路，暴力跳父亲，就是去除当前数最后一个\(1\)再计算当前子树的答案，记得减去已经算过的子树的答案#include<bits/stdc++.h>#defineN10000010#definemod998244353#defineintlonglongusingnamespacestd;intn,q,ans,fac[N],inv[N];vector<int>g;......
  • 231105校内赛
    T1构造题没啥好说的，大样例一眼出规律#include<bits/stdc++.h>#defineN310usingnamespacestd;intn,l[N][N],r[N][N],a[N][N];intmain(){ freopen("squ.in","r",stdin); freopen("squ.out","w",stdout); ios::sync_with_stdio(0......
  • 231101校内赛
    T1茵蒂克丝模拟题，用一个栈模拟就完了，挺简单的有人没看见是非负数#include<bits/stdc++.h>#definepiipair<int,int>#definefifirst#definesesecond#defineN1000010usingnamespacestd;intn,k,a[N],ans[N],cnt,top,tot;piistk[N],b[N];boolcmp(piix,piiy){......
  • 231030校内赛
    T1新的阶乘有三种做法，第一种也就是我写的这种容易被评测机波动坑，复杂度玄学考虑处理出每个数的质因数，然后就暴力除每个数的质因数的种类次非常的简单，也容易被卡第二种是与第一种差距不大，就是在线性筛中处理出质因数之后，再对每个数除以线筛中处理的质因数，将它的答案加到除数和......
  • 231023校内赛
    T1区间题解很容易想到的一点是如果\(k\)足够大，那么把区间单独放到一个组里总比多个区间在一个组优对于多个区间来说，区间之间如果两两不包含的话这道题会是比较好做的就可以注意到如果一个大区间包含了一个小区间，那么大区间要么单独一组，要么和小区间同一组，这样会是比较优的......
  • 231019校内赛
    T1机器人题解傻逼题，但是有人\(90\)分一开始十分想直接暴力\(2^n\)判断每一步选不选求出所有可能性但是会发现它有制约关系有些步走了之后，有些就必须走了所以需要用一个数组记录当前位置走没走过，或者是不是障碍注意走没走过不能直接赋值\(1,0\)因为回溯时会直接将前......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99