牛客OI周赛7-提高组题解与代码（出题记录）

Posted On 2019年2月22日

A.小睿睿的等式

题目分析

送温暖题

注意不要对每个数暴力拆分算，对于每个数预处理即可

时间复杂度：\(O(n)\)

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int num[]={6,2,5,5,4,5,6,3,7,6},maxn=5e7+100;
int use[maxn];
signed work(int n,int k)
{
	for (int i=0;i<=9;i++)use[i]=num[i];
	for (int i=10;i<=n;i++)
		use[i]=use[i/10]+num[i%10];
	int ans=0,tmp=n/k-4-use[n];
	for (int i=0;i<=n/2;i++)
		if (use[i]+use[n-i]==tmp)++ans;
	return ans;
}
signed main()
{
	int n=read(),k=read();
	printf("%d\n",work(n,k));
}

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int num[]={6,2,5,5,4,5,6,3,7,6},maxn=5e7+100;

int use[maxn];

signed work(int n,int k)

{

for (int i=0;i<=9;i++)use[i]=num[i];

for (int i=10;i<=n;i++)

use[i]=use[i/10]+num[i%10];

int ans=0,tmp=n/k-4-use[n];

for (int i=0;i<=n/2;i++)

if (use[i]+use[n-i]==tmp)++ans;

return ans;

}

signed main()

{

int n=read(),k=read();

printf("%d\n",work(n,k));

}

B.小睿睿的询问

题目分析

送温暖题++

ST表\(O(1)\)即可解决

为了鼓励多种写法，特意在生成数列时限制各数的大小\(<100\)

时间复杂度：\(O(nlogn+m)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<bitset>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
inline int read()
{
	int k=0,f=1;char c=getchar();
	while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=1e5+7;
int mx[maxn][20],pos[maxn][20],lg[maxn];
void generate_array(int n,int seed)
{
	unsigned x = seed;
	for (int i=1;i<=n;++i)
	{
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		mx[i][0]=x%100;
	}
}
inline int query(const int l,const int r)
{
	int len=r-l+1,log=lg[len];
	int ans=pos[l][log];
	if (mx[r-(1<<log)+1][log]>mx[l][log])ans=pos[r-(1<<log)+1][log];
	return ans;
}
void generate_ask(int n,int m,int seedx,int seedy)
{
	unsigned x=seedx,y=seedy,L,R;
	int ans=0,lastans=0;
	for (int i=1;i<=m;++i)
	{
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		y ^= y << 13;
		y ^= y >> 17;
		y ^= y << 5;
		L=(x^lastans)%n+1,R=(y^lastans)%n+1;
		if (L>R)swap(L,R);
		ans^=(lastans=query(L,R));
	}
	printf("%d\n",ans);
}
signed main()
{
	int n=read(),m=read();
	for (int i=1;i<=n;i++)pos[i][0]=i;
	for (int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for (int j=1;j<=lg[n];j++)
		for (int i=1;i+(1<<j)-1<=n;i++)
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]),
			pos[i][j]=mx[i][j-1]>=mx[i+(1<<j-1)][j-1]?pos[i][j-1]:pos[i+(1<<j-1)][j-1];
	generate_array(n,read());
	int seedx=read();
	generate_ask(n,m,seedx,read());
	
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<vector>

#include<bitset>

#include<queue>

#include<cstring>

#include<cstdlib>

#include<map>

#include<cmath>

typedef long long ll;

using namespace std;

inline int read()

{

int k=0,f=1;char c=getchar();

while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=1e5+7;

int mx[maxn][20],pos[maxn][20],lg[maxn];

void generate_array(int n,int seed)

{

unsigned x = seed;

for (int i=1;i<=n;++i)

{

x ^= x << 13;

x ^= x >> 17;

x ^= x << 5;

mx[i][0]=x%100;

}

inline int query(const int l,const int r)

{

int len=r-l+1,log=lg[len];

int ans=pos[l][log];

if (mx[r-(1<<log)+1][log]>mx[l][log])ans=pos[r-(1<<log)+1][log];

return ans;

}

void generate_ask(int n,int m,int seedx,int seedy)

{

unsigned x=seedx,y=seedy,L,R;

int ans=0,lastans=0;

for (int i=1;i<=m;++i)

{

x ^= x << 13;

x ^= x >> 17;

x ^= x << 5;

y ^= y << 13;

y ^= y >> 17;

y ^= y << 5;

L=(x^lastans)%n+1,R=(y^lastans)%n+1;

if (L>R)swap(L,R);

ans^=(lastans=query(L,R));

}

printf("%d\n",ans);

}

signed main()

{

int n=read(),m=read();

for (int i=1;i<=n;i++)pos[i][0]=i;

for (int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;

for (int j=1;j<=lg[n];j++)

for (int i=1;i+(1<<j)-1<=n;i++)

mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]),

pos[i][j]=mx[i][j-1]>=mx[i+(1<<j-1)][j-1]?pos[i][j-1]:pos[i+(1<<j-1)][j-1];

generate_array(n,read());

int seedx=read();

generate_ask(n,m,seedx,read());

}

C. 小睿睿的方案

题目分析

总方案数易求，考虑不合法的方案数：

每对情侣对方案的负贡献：

当两个结点非祖先-后代关系时，两个结点的子树间的路径方案数

当两个结点为祖先-后代关系时，贡献为后代的子树与（整颗树除祖先子树的部分+祖先子树除祖先含后代的子树）间的路径方案数

考虑用一\(n*n\)的矩阵里的三角形来表示方案数，矩阵上\((i,j)\)或\((j,i)\)点表示\(i\)与\(j\)的方案是不合法的，那么用dfs序来映射点，一个点的子树的dfs序连续，每个贡献可以表示为若干矩形区域，那么用线段树+扫描线即可计算出不合法的方案数

注意与矩阵对角线对称的点应同时更新

\(A\)点在\(B\)点的子树内当且仅当\(dfn[B] \leq dfn[A]<dfn[B]+size[B]\)，其中\(dfn\)为dfs序，\(size\)为子树大小

时间复杂度：\(O(nlogn)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<bitset>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<map>
#include<cmath>
#include<vector>
typedef long long ll;
using namespace std;
const int maxn=1e5+100,up=20;
inline int read()
{
	int k=0,f=1;char c=getchar();
	while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
	return k*f;
}
struct mc{int too,nxt;}e[maxn<<1];
struct zmc{int cnt,len;}t[maxn<<4];
int last[maxn],dfn[maxn],siz[maxn],tot;
int f[maxn][22],dep[maxn];
vector<pair<pair<int,int>,int > >store[maxn];
inline int max(const int a,const int b){return a>b?a:b;}
inline void swap(int&x,int&y){int tmp=x;x=y;y=tmp;}
void update(const int l,const int r,const int cur,const int L,const int R,const int delta)
{
	if (L<=l&&r<=R)
	{
		t[cur].cnt+=delta;
		if (t[cur].cnt)t[cur].len=r-l+1;
		else t[cur].len=t[cur<<1].len+t[cur<<1|1].len;
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid)update(l,mid,cur<<1,L,R,delta);
	if (R>mid)update(mid+1,r,cur<<1|1,L,R,delta);
	if (!t[cur].cnt)
		t[cur].len=t[cur<<1].len+t[cur<<1|1].len;
}
void dfs(const int cur)
{
	dfn[cur]=++tot;siz[cur]=1;
	for (int i=1;i<=up;i++)f[cur][i]=f[f[cur][i-1]][i-1];
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=f[cur][0])
			dep[e[i].too]=dep[cur]+1,f[e[i].too][0]=cur,
			dfs(e[i].too),siz[cur]+=siz[e[i].too];
}
inline void UPD(int x,int X,int y,int Y)
{
	store[y].push_back(make_pair(make_pair(x,X),1));
	store[Y+1].push_back(make_pair(make_pair(x,X),-1));
}
bool upd(const int x,const int X,const int y,const int Y)
{
	UPD(x,X,y,Y);
	UPD(y,Y,x,X);
	return 1;
}
signed main()
{
	int n=read(),m=read();
	for (int i=1,a,b;i<n;i++)
		a=read(),b=read(),e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1,
		e[i<<1|1].nxt=last[b],last[b]=i<<1|1,e[i<<1|1].too=a;
	dfs(1);
	for (int T=1;T<=m;T++)
	{
		int i=read(),j=read();
		if ((dfn[i]<=dfn[j]&&dfn[j]<=dfn[i]+siz[i]-1)||(dfn[j]<=dfn[i]&&dfn[i]<=dfn[j]+siz[j]-1))
		{
			int x=i,y=j;
			if (dfn[y]<=dfn[x]&&dfn[x]<=dfn[y]+siz[y]-1)swap(x,y);
			int cur=y;
			for (int k=up;~k;k--)
				if (dep[f[cur][k]]>dep[x])cur=f[cur][k];
			upd(1,dfn[x],dfn[y],dfn[y]+siz[y]-1),
			dfn[cur]+siz[cur]<=dfn[x]+siz[x]-1&&upd(dfn[cur]+siz[cur],dfn[x]+siz[x]-1,dfn[y],dfn[y]+siz[y]-1),
			dfn[x]+1<=dfn[cur]-1&&upd(dfn[x]+1,dfn[cur]-1,dfn[y],dfn[y]+siz[y]-1),
			dfn[x]+siz[x]<=n&&upd(dfn[x]+siz[x],n,dfn[y],dfn[y]+siz[y]-1);
		}
		else upd(dfn[i],dfn[i]+siz[i]-1,dfn[j],dfn[j]+siz[j]-1);
	}
	ll ans=0;
	for (int i=1;i<=n;i++)
	{
		for (vector<pair<pair<int,int>,int > >::iterator it=store[i].begin();it!=store[i].end();++it)
			update(1,n,1,(*it).first.first,(*it).first.second,(*it).second);
		ans+=t[1].len;
	}
	ll sum=1ll*n*n-n-ans;
	printf("%lld\n",(sum>>1));
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<bitset>

#include<queue>

#include<cstring>

#include<cstdlib>

#include<map>

#include<cmath>

#include<vector>

typedef long long ll;

using namespace std;

const int maxn=1e5+100,up=20;

inline int read()

{

int k=0,f=1;char c=getchar();

while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();

return k*f;

}

struct mc{int too,nxt;}e[maxn<<1];

struct zmc{int cnt,len;}t[maxn<<4];

int last[maxn],dfn[maxn],siz[maxn],tot;

int f[maxn][22],dep[maxn];

vector<pair<pair<int,int>,int > >store[maxn];

inline int max(const int a,const int b){return a>b?a:b;}

inline void swap(int&x,int&y){int tmp=x;x=y;y=tmp;}

void update(const int l,const int r,const int cur,const int L,const int R,const int delta)

{

if (L<=l&&r<=R)

{

t[cur].cnt+=delta;

if (t[cur].cnt)t[cur].len=r-l+1;

else t[cur].len=t[cur<<1].len+t[cur<<1|1].len;

return;

}

int mid=(l+r)>>1;

if (L<=mid)update(l,mid,cur<<1,L,R,delta);

if (R>mid)update(mid+1,r,cur<<1|1,L,R,delta);

if (!t[cur].cnt)

t[cur].len=t[cur<<1].len+t[cur<<1|1].len;

}

void dfs(const int cur)

{

dfn[cur]=++tot;siz[cur]=1;

for (int i=1;i<=up;i++)f[cur][i]=f[f[cur][i-1]][i-1];

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=f[cur][0])

dep[e[i].too]=dep[cur]+1,f[e[i].too][0]=cur,

dfs(e[i].too),siz[cur]+=siz[e[i].too];

}

inline void UPD(int x,int X,int y,int Y)

{

store[y].push_back(make_pair(make_pair(x,X),1));

store[Y+1].push_back(make_pair(make_pair(x,X),-1));

}

bool upd(const int x,const int X,const int y,const int Y)

{

UPD(x,X,y,Y);

UPD(y,Y,x,X);

return 1;

}

signed main()

{

int n=read(),m=read();

for (int i=1,a,b;i<n;i++)

a=read(),b=read(),e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1,

e[i<<1|1].nxt=last[b],last[b]=i<<1|1,e[i<<1|1].too=a;

dfs(1);

for (int T=1;T<=m;T++)

{

int i=read(),j=read();

if ((dfn[i]<=dfn[j]&&dfn[j]<=dfn[i]+siz[i]-1)||(dfn[j]<=dfn[i]&&dfn[i]<=dfn[j]+siz[j]-1))

{

int x=i,y=j;

if (dfn[y]<=dfn[x]&&dfn[x]<=dfn[y]+siz[y]-1)swap(x,y);

int cur=y;

for (int k=up;~k;k--)

if (dep[f[cur][k]]>dep[x])cur=f[cur][k];

upd(1,dfn[x],dfn[y],dfn[y]+siz[y]-1),

dfn[cur]+siz[cur]<=dfn[x]+siz[x]-1&&upd(dfn[cur]+siz[cur],dfn[x]+siz[x]-1,dfn[y],dfn[y]+siz[y]-1),

dfn[x]+1<=dfn[cur]-1&&upd(dfn[x]+1,dfn[cur]-1,dfn[y],dfn[y]+siz[y]-1),

dfn[x]+siz[x]<=n&&upd(dfn[x]+siz[x],n,dfn[y],dfn[y]+siz[y]-1);

}

else upd(dfn[i],dfn[i]+siz[i]-1,dfn[j],dfn[j]+siz[j]-1);

}

ll ans=0;

for (int i=1;i<=n;i++)

{

for (vector<pair<pair<int,int>,int > >::iterator it=store[i].begin();it!=store[i].end();++it)

update(1,n,1,(*it).first.first,(*it).first.second,(*it).second);

ans+=t[1].len;

}

ll sum=1ll*n*n-n-ans;

printf("%lld\n",(sum>>1));

}

5 1 vote

Article Rating

5 评论

Oldest

Newest Most Voted

Inline Feedbacks

View all comments

4 年之前

B题标程函数调用写反啦

作者

mczhuang

4 年之前

Reply to 11

请问哪里写反了呢？

123

4 年之前

C题从哪看出来两个结点非祖先-后代关系啊？？？

作者

mczhuang

4 年之前

Reply to 123

已更新描述

tmp

2 年之前

妙