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

231004校内赛

时间：2023-10-05 17:02:49浏览次数：32  
标签：getpos int siz son 231004 校内 size define

T1 水管

pPXuw4S.jpg

题解

很简单的一道题，别想复杂了

只要一边 \(dfs\) 即可

先将当前点的所有水量给出去，如果缺水就给出去负数

那么等到最后一个节点如果不是刚好合适，那么就把剩余水量回溯回来，无论正负

再如此给下一个连边的点

如果最后一个点刚好合适那么给下一个点的就是 \(0\)

实现很简单

诅咒不给SPJ的出题人!

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define N 200010
using namespace std;
int n,m,a[N],sum,f[N<<1],u[N<<1],v[N<<1];
bool vis[N];
vector<pii>g[N];
int dfs(int x,int fl){
	vis[x] = true;
	fl-=a[x];
	int tmp = fl;
	for(pii i : g[x]){
		if(!vis[i.fi]){
			tmp = dfs(i.fi,fl);
			if(u[i.se]==x) f[i.se] = fl-tmp;
			else f[i.se] = -(fl-tmp);
			fl = tmp;
		}
	}
	return fl;
}
int main(){
	freopen("flow.in","r",stdin);
	freopen("flow.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];
		sum+=a[i];
	}
	if(sum){
		cout<<"Impossible";
		return 0;
	}
	cin>>m;
	for(int i = 1;i<=m;i++){
		cin>>u[i]>>v[i];
		g[u[i]].push_back({v[i],i});
		g[v[i]].push_back({u[i],i});
	}
	for(int i = 1;i<=n;i++)
		if(!vis[i])
			if(dfs(i,0)){
				cout<<"Impossible";
				return 0;
			}
	cout<<"Possible\n";
	for(int i = 1;i<=m;i++)
		cout<<f[i]<<"\n";
	return 0;
}

T2 宝藏

pPXu6un.jpg

题解

两种做法，第一种是 \(\mathcal O(nm^2)\) ，第二种 \(\mathcal O(nm\log m)\)

第一种需要处理一个二阶前缀和，然后暴力遍历所有列的区间并用桶存下

每当桶里有值时花费 \(\mathcal O(n)\) 来用双指针计数处理行对应的个数

如下为第一种代码

#include<bits/stdc++.h>
#define N 100010
#define M 110
#define ll long long
using namespace std;
int n,m,k,suml[N],sumr[M],t[N*M];
ll ans;
ll query(int k){
	ll res = 0,j = 1,l = 1;
	for(int i = 1;i<=n;i++){
		while(suml[i]-suml[l-1]>k&&l<=i) l++;
		while(suml[i]-suml[j-1]>=k&&j<=i) j++;
		res+=j-l;
	}
	return res;
}
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i = 1;i<=n;i++){
		string s;
		cin>>s;
		for(int j = 0;j<m;j++){
			suml[i]+=(s[j]=='$');
			sumr[j+1]+=(s[j]=='$');
		}
	}
	for(int i = 1;i<=n;i++)
		suml[i]+=suml[i-1];
	for(int i = 1;i<=m;i++)
		sumr[i]+=sumr[i-1];
	for(int i = 1;i<=m;i++)
		for(int j = i;j<=m;j++)
			t[sumr[j]-sumr[i-1]]++;
	for(int i = 0;i<=k;i++){
		if(!t[i])continue;
		ans+=query(k-i)*t[i];
	}
	cout<<ans;
	return 0;
}

第二种做法

对于原矩阵维护一个二维前缀和和后缀和，这样宝藏的数目就可以在两个点对上统计贡献

枚举其中一个点对，用数据结构寻找另一个点即可

#include<cstdio>
#define N 100005
#define M 105
#define K 100005
using namespace std;
int n,m,k,cnt,f[N][M],g[N][M],a[N][M];
long long ans;
struct BIT
{
	int v[M];
	void modify(int x)
	{
		if (!x) ++v[0]; 
		for (;x<M && x;x+=x&-x) ++v[x];
	}
	int query(int x)
	{
		int res=0;
		for (;x;x-=x&-x) res+=v[x];
		return res+v[0];
	}
} s[K*3];
int main()
{
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	scanf("%d%d%d\n",&n,&m,&k);
	for (int i=1;i<=n;++i,scanf("\n"))
		for (int j=1;j<=m;++j)
			if (getchar()=='$')
				++f[i][j],++g[i][j],++cnt;
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j)
		f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
	for (int i=n;i;--i) for (int j=m;j;--j)
		g[i][j]+=g[i+1][j]+g[i][j+1]-g[i+1][j+1];
	for (int i=0;i<=n;++i) for (int j=0;j<=m;++j)
		a[i][j]=f[i][j]-g[i+1][j+1];
	//if (cnt>100000) return printf("?"),0;
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<m;++j) 
			s[a[i-1][j]+2*cnt].modify(j);
		for (int j=1;j<=m;++j)
			ans+=s[a[i][j]-k+2*cnt].query(j-1);
	}
	printf("%lld",ans);
}

T3 梦色之乡

pPXuf4U.jpg

题解

这题总共有三种做法

第一种，通过点分树来加速找重心的过程从而做到 \(\mathcal O(n\log^2 n)\) 的复杂度

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define N 1000010
using namespace std;
int n,m,now,dfn[N],siz[N],sz[N],weight[2],f[N],x,y,cnt,tot,dfncnt,dep[N],fa[N][20],que[N];
bool vis[N];
vector<int>g[N];
unordered_map<int,int>mp[N];
set<pii>s[N];
bool check(int x,int y){//判断x是否在y的子树内 
	return dfn[x]>=dfn[y]&&(dfn[x]<=dfn[y]+siz[y]-1);
}
void dfs(int x,int father){
	siz[x] = 1;
	dfn[x] = ++dfncnt;
	dep[x] = dep[father]+1;
	fa[x][0] = father;
	for(int i = 1;i<=17;i++)
		fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int i : g[x]){
		if(i==father) continue;
		dfs(i,x);
		siz[x]+=siz[i];
		s[x].insert({siz[i],i});
	}
	if(father) s[x].insert({n-siz[x],father});
}
int jump(int x,int y){
	for(int i = 17;i>=0;i--)
		if(dep[fa[x][i]]>=y)
			x = fa[x][i];
	return x;
}
int gt(int p){
	if(check(p,x)||check(p,y))
		return fa[p][0];
	int u = 0,v = 0,newv = 0,r = 0,t = 0,newt = 0;
	if(!check(x,p)){
		u = fa[p][0];
		v = n-siz[p];
		newv = v-siz[x];
	}else{
		u = jump(x,dep[p]+1);
		v = siz[u];
		newv = siz[u]-siz[x];
	}
	if(!check(y,p)){
		r = fa[p][0];
		t = n-siz[p];
		newt = t-siz[y];
	}else{
		r = jump(y,dep[p]+1);
		t = siz[r];
		newt = siz[r]-siz[y];
	}
	if(r==u) newv-=siz[y],r = 0;
	if(u){
		s[p].erase({v,u});
		s[p].insert({newv,u});
	}
	if(r){
		s[p].erase({t,r});
		s[p].insert({newt,r});
	}
	int tmpwei = 0;auto tmp = s[p].end();
	tmp--;
	if((*tmp).fi<=(now/2)){
		weight[tot++] = p;
		if(((*tmp).fi==(now/2))&&(now%2==0))
			weight[tot++] = (*tmp).se;
	}else tmpwei = (*tmp).se;
	if(u){
		s[p].erase({newv,u});
		s[p].insert({v,u});
	}
	if(r){
		s[p].erase({newt,r});
		s[p].insert({t,r});
	}
	return tmpwei;
}
void ddfs(int x,int father){
	sz[x] = 1;f[x] = 0;
	que[++cnt] = x;
	for(int i : g[x]){
		if(i==father||vis[i]) continue;
		ddfs(i,x);
		sz[x]+=sz[i];
		f[x] = max(f[x],sz[i]);
	}
}
int getrt(int x){
	cnt = 0;
	ddfs(x,0);
	int tmp = que[1];
	for(int i = 1;i<=cnt;i++){
		int p = que[i];
		f[p] = max(f[p],cnt-sz[p]);
		if(f[p]<f[tmp]) tmp = p;
	}
	return tmp;
}
int build(int x){
	int u = getrt(x);
	vis[u] = 1;
	for(int i : g[u]){
		if(vis[i]) continue;
		int v = build(i);
		mp[u][i] = v;
	}
	return u;
}
signed main(){
	freopen("dream.in","r",stdin);
	freopen("dream.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	int rt = build(1);
	for(int i = 1;i<=m;i++){
		cin>>x>>y;
		if(dfn[y]<dfn[x]) swap(x,y);
		if(check(y,x)) y = 0;
		if(x==1){
			cout<<"0\n";
			continue;
		}
		now = n-(siz[x]+siz[y]);
		weight[0] = weight[1] = tot = 0;
		int pos = rt;
		while(1){
			int u = gt(pos);
			if(!u) break;
			pos = mp[pos][u];
		}
		if(tot==2&&weight[0]>weight[1])
			swap(weight[0],weight[1]);
		for(int i = 0;i<tot;i++)
			cout<<weight[i]<<" ";
		cout<<"\n";
	}
	return 0;
}

剩下两种做法不是很熟悉，截个图看看就行

pPXu4CF.jpg

#include<bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
using i64 = long long;
constexpr int _N = 1e5 + 5;
int n, m, len;
vector<int> e[_N];
mt19937 rnd(114514);
#define rand(l, r) uniform_int_distribution<int>(l, r)(rnd)
int siz[_N], id[_N], dep[_N], dfn, fa[_N];
set<pair<int, int>> fmx[_N];
vector<int> cr;
bool isc[_N];
void Dfs(int x, int F) {
	siz[x] = 1, id[x] = ++dfn, dep[x] = dep[F] + 1, fa[x] = F;
	auto Add = [&x](int s, int siz) {
		fmx[x].insert({ siz, s });
		if (fmx[x].size() > 3)
			fmx[x].erase(fmx[x].begin());
	};
	for (int v : e[x]) if (v ^ F) {
		Dfs(v, x);
		siz[x] += siz[v];
		Add(v, siz[v]);
	}
}
inline bool In(int x, int y) { return id[y] >= id[x] && id[y] < id[x] + siz[x]; }
vector<int> ans;
void Ask(int x, int y) {
	ans.clear();
	if (dep[x] > dep[y]) swap(x, y);
	if (In(x, y)) y = 0;
	int p = 1, tot = n - siz[x] - siz[y];
	auto GetSiz = [](int x, int dx, int dy) {
		if (In(dx, x) || In(dy, x)) return 0;
		int sum = siz[x];
		if (In(x, dx)) sum -= siz[dx];
		if (In(x, dy)) sum -= siz[dy];
		return sum;
	};
	for (int c : cr)
		if (GetSiz(c, x, y) > tot / 2 && dep[c] > dep[p])
			p = c;
	while (tot - GetSiz(p, x, y) <= tot / 2) {
		int nxt = 0, mx = 0;
		for (auto pr : fmx[p])
			if (GetSiz(pr.second, x, y) > mx)
				mx = GetSiz(pr.second, x, y), nxt = pr.second;
		if (mx <= tot / 2) ans.push_back(p);
		p = nxt;
	}
	sort(ans.begin(), ans.end());
	for (int r : ans) cout << r << ' ';
	cout << '\n';
}
signed main() {
	string file = "dream";
	freopen((file + ".in").c_str(), "r", stdin);
	freopen((file + ".out").c_str(), "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	len = max(1, (int)(sqrt(n) * 1.5));
	For(i, 1, len) isc[rand(1, n)] = 1;
	For(i, 1, n) if (isc[i]) cr.push_back(i);
	For(i, 2, n) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	Dfs(1, 0);
	For(i, 1, m) {
		int x, y;
		cin >> x >> y;
		if (x == 1 || y == 1) cout << 0 << '\n';
		else Ask(x, y);
	}
}

pPXuOUK.jpg

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int inf=0x3f3f3f3f;
struct node{int size,id,iid;};
struct edge{int last,en,next;} e[200010];
int n,x,y,son[100010],size[100010],dfn[100010],dep[100010];
int st[100010][18],tot,cnt,cs[100010],q,u,v,ccs[100010];
int f[100010][18],val[100010],g[100010][18],leave[100010],ans,w,sum;
void add(int x,int y)
{
	e[++tot].en=y;
	e[tot].next=e[x].last;
	e[x].last=tot;
}
inline int read()
{
	int s=0;
	char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s; 
}
void dfs(int x,int fa)
{
    f[x][0]=fa;dep[x]=dep[fa]+1;size[x]=1;
	dfn[x]=++cnt;son[x]=0;
    for(int i=e[x].last;i;i=e[i].next) 
	    if (e[i].en!=fa)
		{
			dfs(e[i].en,x);
			if (size[son[x]]<size[e[i].en])
			{
				ccs[x]=cs[x];
				cs[x]=son[x];
				son[x]=e[i].en;
			}
			else if (size[cs[x]]<size[e[i].en]) 
			{
				ccs[x]=cs[x];
				cs[x]=e[i].en;
			}
			else if (size[ccs[x]]<size[e[i].en]) ccs[x]=e[i].en;
			size[x]+=size[e[i].en];
		}
	val[x]=size[son[x]]-size[cs[x]];
	if (!cs[x]) val[x]=0x3f3f3f3f; 
	st[x][0]=val[x];g[x][0]=son[x];
    leave[x]=++tot;
}
int lca(int x,int y)
{
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=17;i>=0;i--)
		if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (int i=17;i>=0;i--)
		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int calc(int z,int x)
{
	if (dfn[u]>=dfn[x]&&leave[u]<=leave[x]) z-=size[u];
	if (dfn[v]>=dfn[x]&&leave[v]<=leave[x]) z-=size[v];
	return z;
}
bool getpos(int x,int y)
{
	if (dfn[x]>=dfn[y]&&leave[x]<=leave[y]) return true;
	return false;
}
void sort3(node &a,node &b,node &c)
{
	if (a.size<b.size) swap(a,b);
	if (a.size<c.size) swap(a,c);
	if (b.size<c.size) swap(b,c);
}
void sort3(int &a,int &b,int &c)
{
	if (a<b) swap(a,b);
	if (a<c) swap(a,c);
	if (b<c) swap(b,c);
}
bool get(int x)
{
	int a,b,c;
	a=calc(size[son[x]],son[x]);
	b=calc(size[cs[x]],cs[x]);
	c=calc(size[ccs[x]],ccs[x]);
	sort3(a,b,c);
	if (a<=sum/2) return true;
	return false;
}
void getans(int x)
{
	for (int i=17;i>=0;i--)
		if (f[x][i]&&get(f[x][i])) x=f[x][i];
	int y=0;
	node a,b,c;
	a=(node){calc(size[son[x]],son[x]),getpos(u,son[x])?u:getpos(v,son[x])?v:0,son[x]};
	if (son[x]==u||son[x]==v) a.size=-inf;
	b=(node){calc(size[cs[x]],cs[x]),getpos(u,cs[x])?u:getpos(v,cs[x])?v:0,cs[x]};
	if (son[x]==u||son[x]==v) a.size=-inf;
	c=(node){calc(size[ccs[x]],ccs[x]),getpos(u,ccs[x])?u:getpos(v,ccs[x])?v:0,ccs[x]};
	if (son[x]==u||son[x]==v) a.size=-inf;
	sort3(a,b,c);
	if (sum-a.size<=sum/2&&a.size!=-inf) y=a.iid;
	if (x>y) swap(x,y);
	if (x) printf("%d %d\n",x,y);
	else printf("%d\n",y);
}
void solve(int x)
{
	bool bj=getpos(w,x);
	if (!bj)
	{
		for (int i=17;i>=0;i--)
			if (g[x][i]) x=g[x][i];
		getans(x);
		return;
 	} 
	else
	{	
		for (int i=17;i>=0;i--)
		{
			int y=g[x][i];
			if (!y||!getpos(w,y)&&y!=w||getpos(y,u)||getpos(y,v)) continue;
			if (calc(st[x][i],y)>=0) x=y;
		}
	}
	node a,b,c;
	if (x==u||x==v) x=f[x][0];
	a=(node){calc(size[son[x]],son[x]),getpos(u,son[x])?u:getpos(v,son[x])?v:0,son[x]};
	if (son[x]==u||son[x]==v||!son[x]) a.size=-inf;
	b=(node){calc(size[cs[x]],cs[x]),getpos(u,cs[x])?u:getpos(v,cs[x])?v:0,cs[x]};
	if (cs[x]==u||cs[x]==v||!cs[x]) b.size=-inf;
	c=(node){calc(size[ccs[x]],ccs[x]),getpos(u,ccs[x])?u:getpos(v,ccs[x])?v:0,ccs[x]};
	if (ccs[x]==u||ccs[x]==v||!ccs[x]) c.size=-inf;
	sort3(a,b,c);
	if (a.size==-inf)
	{
		getans(x);
		return;
	}
	if (getpos(a.iid,w)) w=a.id;
	solve(a.iid);
}
int main()
{
	freopen("dream.in","r",stdin);
	freopen("dream.out","w",stdout);
	n=read();q=read(); 
	for (int i=1;i<n;i++)
		x=read(),y=read(),add(x,y),add(y,x),st[i][0]=inf;
	st[0][0]=inf;	
	dfs(1,0);
	for (int j=1;j<=17;j++)
		for (int i=1;i<=n;i++)
		{
			f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[g[i][j-1]][j-1];
			st[i][j]=min(st[i][j-1],st[g[i][j-1]][j-1]);
		}
	dfn[0]=leave[0]=size[0]=0;
	while (q--)
	{
		
		scanf("%d%d",&u,&v);ans=0;
		if (u==1||v==1)
		{
			printf("0\n");
			continue;
		}
		w=lca(u,v);
		if (u==w) v=0;
		else if (v==w) u=0;
		sum=n-size[u]-size[v];
		solve(1);
	}
	return 0;
}

T4

你在期待什么？

标签：getpos,int,siz,son,231004,校内,size,define
From： https://www.cnblogs.com/cztq/p/17743540.html

相关文章

  • 231002校内赛
    T1数独题解十分简单的一道模拟题有sb少打了一个换行挂50分#include<bits/stdc++.h>#defineN15usingnamespacestd;structnode{ inta[N][N],be;}t[N*10];intT,n=9,q;intferror(intcnt,intx,inty,intk){ for(inti=1;i<=n;i++) if(t[cnt].a[x][i]==k)......
  • 230930校内赛
    T1洛阳怀题解首先非常容易求出的是所有的\(\gcd\)对于\(\gcd\)而言，如果它的分数是负数，那么将它除去一定会使这个数列得分变大所以只用求出所有的\(\gcd\)的分数并判断正负以及是否除过当前答案了就可以了还有一点是因为\(\gcd\)是单调不降的，所以可以从后往前查保证......
  • 231004.md
    2023/10/04模拟赛总结时间安排07:40-08:20看题，写A,B，感觉会C。08:20-08:40写C暴力。08:40-09:10写换根部分，思考怎么不用平衡树。09:10-10:10写平衡树，调代码。拍C。10:10-10:20写D暴力。10:20-10:40拍A,B。10:40-11:20写D40分。11:20-1......
  • 20231004
    20231004NOIP#15总结时间安排7:40~8:00看题，\(A,B\)会第一档爆搜，别的不会。8:00~9:30写完\(A,B\)的爆搜。9:30~11:00会了\(C\)的暴力还加了点优化，一下写了\(1.5h\)，不过有点难写。（我是真没想到连个菊花图都没有直接\(AC\)了11:00~11:40\(D\)能看出是线段树但一点......
  • 2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛)
    A.AXorBProblem（计数）输入511223输出9说明点击查看代码#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false);cin.tie(0),cout.tie(0)#defineintlonglongusingnamespacestd;constintN=2e5+10;unordered_map<int,int>......
  • 230925校内赛
    T1开挂我卢本伟没有开挂题解挺简单的，不过我写的比较麻烦因为我们需要让多的尽可能多来让少的尽可能少，所以会想到用栈来存储需要更改的数，靠近栈底就需要更多次数来更改，栈顶则更少最后只用记录下来所有的次数并按从多到少依次分配从小到大的修改代价#include<bits/stdc++.h......
  • 230927校内赛
    T1集合题解很明显的一道树形\(dp\)题我也没看出来dalao们说有一道\(ddp\)的题转移方式一模一样于是都切了，就我是sb首先有一个非常明显的性质在于所有的被选的点一定是可以构成一颗连通子树的最终选取的\(k\)个点一定是从这颗子树中最远点对的一个点沿着这颗子树直......
  • 校内互测第一周(East!XI~East!XV)总结(窝还是退役吧QAQ
    ==真是不想说啥了。。。像我这种沙茶蒟蒻还是早点滚粗的好。。。Day1East!XI出题人：18357打开题瞬间傻了。。。三道树上问题。。。三道。。。T1：给定一棵N个节点的无根树，求每个节点到其它的节点的∑(路径长度xorM)。M<=15TM这傻逼题我写了个0~15的Trie树。。。明明记录个0~15的数......
  • 230729校内赛
    回文一句话题意：从左上角到右下角的路径上的字母能组成回文串的路径有几条题解暴力做法是从左上角和右下角分别往对方\(dp\)，复杂度为\(\mathcalO(n^4)\)因为状态只有在\(x1+x2+y1+y2=n+m+2\)时合法，则确定三个变量即可推出剩下一个变量，复杂度为\(\mathcalO(n^3)\)......
  • 校内模拟赛赛后总结
    前记（开始写于\(2023.9.9\)）（本来是不想写的，但是看到学长以及身边人都写，思考了一下，感觉有点用，于是也写了）（里面也写了一些闲话）（以前的比赛我就记个排名得了，懒得补了）7.20~7.22CSP模拟1~3没考7.24CSP模拟4(rk6)7.25CSP模拟5(rk3)7.26CSP模拟6(rk23)7.27......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99