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

230719校内赛

时间：2023-08-28 17:46:31浏览次数：47  
标签：rt tmp 校内 int t2 tot 230719 ans

T1 usaco20feb Equilateral Triangles P

题面我就不描述了

题解

首先我们是不可能暴力计算每一对点距离的

我们可以想一想如何将斜着的数个点转换为横着或竖着的数个点，这样会使我们的计算方便许多

不难想到的是切比雪夫距离，当然考场上也容易推出这玩意（我就是考场现推的）

然后就是如何统计

对于一个点对，我们只需要知道这两个点间的距离，并这个距离的两倍分别作两个正方形，两个正方形的中心点分别是你所选的两个点

不难发现对于两个正方形会有重叠的部分（只考虑边，不考虑面积），在重叠部分上面的点与两个点的距离是相等的

那么上面的点与这两个点都可以构成正方形

统计前缀和数组来维护一下就好了（注意边界点）

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,a[610][610],ans,suma[610][610],sumb[610][610];
int main(){
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
		string s;cin>>s;
		for(int j = 1;j<=n;j++)	if(s[j-1]=='*') a[i+j][i-j+n] = 1;
	}
	n*=2;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			suma[i][j] = suma[i][j-1]+a[i][j];
			sumb[i][j] = sumb[i-1][j]+a[i][j];
		}
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			if(a[i][j]==0) continue;
			for(int k = j+1;k<=n;k++){
				if(a[i][k]==0) continue;
				int tmp = i+k-j;
				if(tmp<=n)ans+=suma[tmp][k]-suma[tmp][j-1];
				tmp = i-k+j;
				if(tmp>0)ans+=suma[tmp][k]-suma[tmp][j-1];
			}
		}
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			if(a[j][i]==0) continue;
			for(int k = j+1;k<=n;k++){
				if(a[k][i]==0) continue;
				int tmp = i+k-j;
				if(tmp<=n)ans+=sumb[k-1][tmp]-sumb[j][tmp];
				tmp = i-k+j;
				if(tmp>0)ans+=sumb[k-1][tmp]-sumb[j][tmp];
			}
		}
	}
	printf("%d",ans);
	return 0;
}

T2 换公路

image-20230828161551238

题解

首先很明显的是这一定是两棵树

如果两条边 \(e_1,e_2\) 在两棵树 \(T_1,T_2\) 中可以互相替代，则 \(e_2\) 在 \(T_2\) 中 \(e_1\) 两端点的路径上，\(e_1\) 在 \(T_1\) 中 \(e_2\) 两端点的路径上

那么先把 \(T_2\) 的每条边在 \(T_1\) 上差分，也就是在两端点处插入这条边, 在 \(lca\) 处删除这条边

考虑每条边时只考虑在子树中有的边，现在只需要考虑支持诸如加入/删除一个点到集合中，查询一条路径能覆盖集合中的几个点即可

查询可利用利用 dfs 序 + 线段树，合并子树采用线段树合并

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

码量挺大

#include<bits/stdc++.h>
#define N 500100
using namespace std;
struct node{
	int l,r,s;
}t[N<<6];
vector<int>ve[N];
int n,tot,sz,in[N],out[N],rt[N],ans[N];
struct Tree{
	struct edge{
		int v,ne;
	}e[N<<1];
	int cnt,h[N],fa[N],dep[N],siz[N],top[N];
	void add(int u,int v){
		e[++cnt].v = v;
		e[cnt].ne = h[u];
		h[u] = cnt;
		e[++cnt].v = u;
		e[cnt].ne = h[v];
		h[v] = cnt;
	}
    void dfs1(int x){
    	dep[x] = dep[fa[x]]+1;
    	siz[x] = 1;
    	for(int i = h[x];i;i = e[i].ne){
    		int v = e[i].v;
    		if(v==fa[x]) continue;
    		fa[v] = x;
    		dfs1(v);
    		siz[x]+=siz[v];
		}
	}
	void dfs2(int x,int ch){
		top[x] = ch;
		int k = 0;
		for(int i = h[x];i;i = e[i].ne){
			int v = e[i].v;
			if(v!=fa[x]&&siz[v]>siz[k]) 
				k = v;
		}
		if(k) dfs2(k,ch);
		for(int i = h[x];i;i = e[i].ne){
			int v = e[i].v;
			if(v!=fa[x]&&v!=k)
				dfs2(v,v);
		}
	}
	void dfs3(int x){
		in[x] = ++tot;
		for(int i = h[x];i;i = e[i].ne){
			int v = e[i].v;
			if(v!=fa[x])
				dfs3(v);
		}
		out[x] = ++tot;
	}
	int get_lca(int x,int y){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])	
				swap(x,y);
			x = fa[top[x]];
		}
		return dep[x]<dep[y]?x:y;
	} 
}t1,t2;
int newnode(){
	sz++;
	t[sz].l = t[sz].r = t[sz].s = 0;
	return sz;
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	t[x].s+=t[y].s;
	t[x].l = merge(t[x].l,t[y].l);
	t[x].r = merge(t[x].r,t[y].r);
	return x;
}
void modify(int &d,int l,int r,int x,int y){
	if(!d) d = newnode();
	t[d].s+=y;
	if(l==r) return ;
	int mid = (l+r)>>1;
	if(x<=mid) modify(t[d].l,l,mid,x,y);
	else modify(t[d].r,mid+1,r,x,y);
}
int query(int d,int l,int r,int x,int y){
	if(!d||(x<=l&&r<=y)) return t[d].s;
	int mid = (l+r)>>1,res = 0;
	if(x<=mid) res+=query(t[d].l,l,mid,x,y);
	if(y>mid) res+=query(t[d].r,mid+1,r,x,y);
	return res;
}
void solve(int x){
	for(int i = t2.h[x];i;i = t2.e[i].ne){
		int v = t2.e[i].v;
		if(v==t2.fa[x]) continue;
		solve(v);
		rt[x] = merge(rt[x],rt[v]);
	}
	for(int i = 0;i<(int)ve[x].size();i++){
		int y = ve[x][i];
		if(y>0){
			modify(rt[x],1,tot,in[y],1);
			modify(rt[x],1,tot,out[y],-1); 
		}else{
			modify(rt[x],1,tot,in[-y],-2);
			modify(rt[x],1,tot,out[-y],2);
		}
	}
	if(x==1) return ;
	int lca = t1.get_lca(x,t2.fa[x]);
	ans[x] = query(rt[x],1,tot,1,in[x])+query(rt[x],1,tot,1,in[t2.fa[x]])-2*query(rt[x],1,tot,1,in[lca]);
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		t2.add(x,y);
	}
	for(int i = 1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		t1.add(x,y);
	}
	t1.dfs1(1);
	t1.dfs2(1,1);
	t1.dfs3(1);
	t2.dfs1(1);
	t2.dfs2(1,1);
	for(int i = 1;i<n*2-1;i+=2){
		int x = t1.e[i].v,y = t1.e[i+1].v,lca = t2.get_lca(x,y);
		if(t1.dep[x]<t1.dep[y]) swap(x,y);
		ve[x].push_back(x);
		ve[y].push_back(x);
		ve[lca].push_back(-x);
	}
	solve(1);
	for(int i = 1;i<n*2-1;i+=2){
		int x = t2.e[i].v,y = t2.e[i+1].v;
		if(t2.dep[x]<t2.dep[y])
			swap(x,y);
		printf("%d ",ans[x]);
	} 
	return 0;
}

T3 cf1335f

同样自己看题意

题解

洛谷题解已经讲的很好了，我就不献丑了

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m,t,ne[30][N];
char dis[N],col[N];
bool have[3][N];
string s;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i = 1;i<=n*m;i++)
			have[1][i] = have[0][i] = false;
		for(int i = 1;i<=n;i++){
			cin>>s;
			for(int j = 1;j<=m;j++)
				col[(i-1)*m+j] = s[j-1];
		}
		for(int i = 1;i<=n;i++){
			cin>>s;
			for(int j = 1;j<=m;j++)
				dis[(i-1)*m+j] = s[j-1];
		}
		for(int i = 1;i<=n*m;i++){
			switch(dis[i]){
				case'U':ne[0][i] = i-m;break;
				case'D':ne[0][i] = i+m;break;
				case'L':ne[0][i] = i-1;break;
				case'R':ne[0][i] = i+1;break;
			}
		}
		for(int i = 1;i<=20;i++)
			for(int j = 1;j<=n*m;j++)
				ne[i][j] = ne[i-1][ne[i-1][j]];
		for(int i = 1;i<=n*m;i++){
			int tmp = i;
			for(int j = 20;~j;j--){
				if((n*m>>j)&1) tmp = ne[j][tmp];
			}
			have[col[i]^48][tmp] = true;
		}
		int bla = 0,ans = 0;
		for(int i = 1;i<=n*m;i++){
			if(have[0][i]) ans++,bla++;
			else if(have[1][i]) ans++;
		}
		printf("%d %d\n",ans,bla) ;
	}
	return 0;
}

T4 找宝藏

t4

题解

有点迷糊，就不误导大家了

image-20230828172919904

#include<bits/stdc++.h>
#define N 100010
#define ll long long
#define INF (ll)(0x3f3f3f3f3f3f3f3f)
using namespace std;
int n,m,deg[N],v[N][40];
ll cnt,siz[N],s[N][40];
vector<int>son[N],fa[N];
vector<ll>sum[N];
queue<int>q;
int getson(int u,int d){
	if(!d) return u;
	for(int i = 30;~i;i--)
		if((v[u][i])&&(siz[v[u][i]]+s[u][i]>=d)&&(s[u][i]<=d))
			return getson(v[u][i],d-s[u][i]);
	int p = (--lower_bound(sum[u].begin(),sum[u].end(),d))-sum[u].begin();
	return getson(son[u][p+1],d-(~p?sum[u][p]:0)-1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		deg[x]++;
		son[x].push_back(y);
		fa[y].push_back(x);
	}
	for(int i = 1;i<=n;i++)
		if(!deg[i]) q.push(i);
	while(q.size()){
		cnt++;
		int u = q.front();q.pop();
		for(int i = 0;i<son[u].size();i++){
			siz[u]+=(siz[son[u][i]]+1);
			siz[u] = min(siz[u],INF);
			sum[u].push_back(siz[u]);
		} 
		if(son[u].size()){
			int p = 0;
			for(int i = 1;i<son[u].size();i++)
				if(siz[son[u][i]]>siz[son[u][p]]) p = i;
			s[u][0] = 1;
			v[u][0] = son[u][p];
			for(int i = 0;i<p;i++){
				s[u][0]+=siz[son[u][i]]+1;
				s[u][0] = min(s[u][0],INF);
			}
			for(int i = 1;i<=30;i++){
				v[u][i] = v[v[u][i-1]][i-1];
				if(!v[u][i]) break;
				s[u][i] = s[u][i-1]+s[v[u][i-1]][i-1];
				s[u][i] = min(s[u][i],INF);
			}
		}
		for(int i = 0;i<fa[u].size();i++){
			int v = fa[u][i];
			if(!(--deg[v])) q.push(v);
		}
	}
	int q;
	scanf("%d",&q);
	for(int i = 1;i<=q;i++){
		int x,k;
		scanf("%d%d",&x,&k);
		if(siz[x]<k) puts("-1");
		else printf("%d\n",getson(x,k));
	}
	return 0;
}

标签：rt,tmp,校内,int,t2,tot,230719,ans
From： https://www.cnblogs.com/cztq/p/17662945.html

相关文章

  • [校内]极端题
    0811T1计数练习题意作为一名普及组选手，小\(A\)喜欢数数。一天，小\(A\)学习了排列相关的知识。定义一个长度为\(n\)的序列\(p_{1...n}\)是一个\(n\)阶排列，当且仅当\(p_{1...n}\)都是\([1,n]\)中的正整数且它们两两不同。小\(A\)想数排列。为了让数排列更有趣，......
  • [校内] 计数练习
    0811T1计数练习题意作为一名普及组选手，小\(A\)喜欢数数。一天，小\(A\)学习了排列相关的知识。定义一个长度为\(n\)的序列\(p_{1...n}\)是一个\(n\)阶排列，当且仅当\(p_{1...n}\)都是\([1,n]\)中的正整数且它们两两不同。小\(A\)想数排列。为了让数排列更有趣，......
  • YTEZ校内数学集训笔记
    计数原理例题1：用一个大写的英文字母或一个阿拉伯数字给教室里的一个座位编号，总共能编出多少种不同的号码？或：\(a\wedgeb\)有\(a\)无\(b\)有\(b\)无\(a\)有\(a\)有\(b\)且：\(a\veeb\)有\(a\)有\(b\)非：\(┐a\)无\(a\)答案：英文字母共有26个，阿拉伯数......
  • 7.23 校内 test
    T1题面：给一个由A,B组成的操作序列，A代表全部取反，B代表+1，每次给出操作区间l,r和一个01串，问经过操作序列中\([l,r]\)的操作后的01串，强制在线。观察性质，发现一次取反会使后面的所有+1变成-1，随便用前缀和维护即可。T2给一个网格图，每个格子有权值，切割一次的代价是被......
  • 剑指offer_20230719
    剑指Offer24.反转链表题目说明定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。解题思路1：栈解题思路2：递归如果从后往前看的话，其实可以这样理解。如果当前处于nk，那么就另nk.next.next=nk，并且将nk.next指向空即可。处理完之后，以nk为头节点的链表其......
  • 20230719-动态规划DP
    20230719数位DPP4127[AHOI2009]同类分布题目描述传送门求出[a,b]中各位数字之和能整除原数的数的个数\(a,b≤1e18\)Solution对于这种求是否能整除的题我们只有在最后才能得到答案这道题很明显是数位DP考虑用记忆化搜索来实现对于每一位我们需要维护前面的数字之......
  • SSO2.0 28-20230719
                      ......
  • 20230719巴蜀暑期集训测试总结
    T1赛时打了一个\(O(n^3)\)\(16pts\)暴力和一个似乎可以过一个\(20pts\)特殊性质但其余无正确性的贪心。结果出来发现特殊性质挂了一个点，另一个地方还莫名其妙对了。说明特殊性质挂掉了，如果运气不好可能就挂到\(16pts\)了。考后看题解发现\(O(n^2)\)其实也是不难想的，有点......
  • 230715校内赛
    T1串背景形貌昳丽的西克是風子国王嫡系军队的general,同时也兼任風子王国驻绿鸟国的外交官。西克喜欢在蕉含流群里与其它王国的使者蕉含流,但前段时间由于说怪话被来自绿鸟国意识形态不完全的国王驱含逐出境。西克非常愤怒,想要说出一句最怪的话,但他却忙于敢览求社的......
  • 230713校内赛
    MC党狂喜系列比赛T1命令方块题目描述实际上这道题与命令方块没有什么关系。给定\(n\)个字符串\(s_i\),将它们按给出的顺序排开。你每次可以交换任意两个字符串的位置。通过交换,这些字符串最终需要满足如下的性质:对于任意的\(i<j<k\),必须有:\(lcp(s_i,s_j)\gel......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99