sxczf's Blog

题目链接 戳我

先给翻译

A

给你n个点

找出特殊点的个数

特殊点：上下左右都有其他点的点

B

给你n和k

找到一个最小的v使得

v+v/k+v/k^2+v/k^3+……>=n

C

给你一个01串问你多少子串包含恰好k个1

D

貌似是给你一棵树，开始所有的边是黑色

3种操作

xy之间的边染黑

xy之间的边染白

询问2点距离，中间有白边输出-1

E

给你n个数

对于每个数你要在剩下的中间找一个数使得

a&b=0

然后输出

A

暴力

#include <cstdio>
#include <algorithm>
using namespace std;
int a,b,c,d,e,f,g,h,i,j,k,l,m,n;
int x[205],y[205];
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
	for(i=1;i<=n;i++){
		g=0;
		for(j=1;j<=n;j++){
			if(x[i]==x[j]&&y[i]<y[j])g|=1;
			if(x[i]==x[j]&&y[i]>y[j])g|=2;
			if(x[i]<x[j]&&y[i]==y[j])g|=4;
			if(x[i]>x[j]&&y[i]==y[j])g|=8;
		}
		if(g==15)h++;
	}
	printf("%d\n",h);
	return 0;
}

B

二分然后判断

#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,l,r,mid;
bool check(int x){int s=0;while(x>0){s=s+x;x/=k;}return s>=n;}
int main(){
	scanf("%d%d",&n,&k);
	l=1;r=n;mid=(l+r)>>1;
	for(;l<r;mid=(l+r)>>1){
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

C

找到每个1的位置

每连续k个1算一下左右多少0然后计算答案

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[1000005],b,c,d,e,f,g,i,j,k,l,m,n,r;
char s[1000005];
long long h;
int main(){
	scanf("%d",&k);
	scanf("%s",s+1);
	l=strlen(s+1);
	if(k==0){
		for(i=1;i<=l;i++)
		if(s[i]=='0'){
			for(j=i;s[j]=='0';j++);
			h=h+1ll*(j-i)*(j-i+1)/2;
			i=j;
		}
		printf("%I64d",h);
		return 0;
	}
	for(i=1;i<=l;i++)
	if(s[i]=='1'){
		a[++n]=i;
	}
	a[n+1]=l+1;
	if(k>n){printf("0");return 0;}
	for(l=1,r=k;r<=n;l++,r++){
		h=h+1ll*(a[l]-a[l-1])*(a[r+1]-a[r]);
	}
	printf("%I64d\n",h);
	return 0;
}

D

直接树链剖分。。。。。

#include <cstdio>
#include <algorithm>
#define N 200005
using namespace std;
int a,b,c,d,e,g,h,i,j,k,l,m,n,sum,tot;
int f[N],dis[N],T[N],fa[N],top[N],size[N],son[N];
int wa[N],ne[N],la[N];
void make(int a,int b){
	wa[++tot]=b;ne[tot]=la[a];la[a]=tot;
	wa[++tot]=a;ne[tot]=la[b];la[b]=tot;
}
void ch(int a,int b,int c){
	if(dis[a]<dis[b])a=b;
	for(i=T[a];i<=n;i+=i&(-i))f[i]+=c*2-1;
}
int calc(int a,int b){
	int s=0;
	for(i=a;i;i-=i&(-i))s-=f[i];
	for(i=b;i;i-=i&(-i))s+=f[i];
	return s;
}
void dfs(int x){
	size[x]=1;
	for(int i=la[x];i;i=ne[i])
	if(wa[i]!=fa[x]){
		fa[wa[i]]=x;
		dis[wa[i]]=dis[x]+1;
		dfs(wa[i]);
		size[x]+=size[wa[i]];
		if(size[wa[i]]>son[x])son[x]=wa[i];
	}
	
}
void dfs2(int x,int Top){
	top[x]=Top;
	T[x]=++sum;
	if(son[x])dfs2(son[x],Top);
	for(int i=la[x];i;i=ne[i])
	if(wa[i]!=fa[x]&&wa[i]!=son[x]){
		dfs2(wa[i],wa[i]);
	}
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		make(a,b);
	}
	dfs(1);
	dfs2(1,1);
	scanf("%d",&m);
	for(;m;m--){
		scanf("%d",&a);
		if(a==1){
			scanf("%d",&b);
			ch(wa[b*2-1],wa[b*2],0);
		}
		else if(a==2){
			scanf("%d",&b);
			ch(wa[b*2-1],wa[b*2],1);
		}
		else{
			scanf("%d%d",&c,&d);h=0;a=c;b=d;
			for(;top[a]!=top[b];){
				if(dis[top[a]]<dis[top[b]])swap(a,b);
				h=h+calc(T[top[a]]-1,T[a]);
				a=fa[top[a]];
			}
			if(dis[a]>dis[b])swap(a,b);
			h=h+calc(T[a],T[b]);
			if(h)printf("-1\n");
			else printf("%d\n",dis[c]+dis[d]-dis[a]*2);
		}
	}
	return 0;
}

E

定义f[i]表示i的答案

显然对于每个j属于i（j&i=j）

f[j]都是可以=f[i]的

然后从大到小转移一下

#include <cstdio>
#include <algorithm>
#define m 23
using namespace std;
int a[1000005],b,c,d,e,f[10000005],g,h,i,j,k,l,n;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++){
		f[a[i]^((1<<m)-1)]=a[i];
	}
	for(i=(1<<m)-1;i>=0;i--){
		for(j=0;j<m;j++)if(f[i|(1<<j)])f[i]=f[i|(1<<j)];
	}
	for(i=1;i<=n;i++)if(f[a[i]])printf("%d ",f[a[i]]);else printf("-1 ");
	return 0;
}