2018.10.13队测总结

T3 克卜勒(kepler)<好题(毒瘤题)置顶>

解题思路：

用两个树状数组维护，第一个树状数组按编号插入，维护小圈内各点是否通达（小圈内路径上的点编号相邻，如区间查询的值等于总点数则连通，另外要考虑反着走），第二个树状数组每个小圈开三个点分别记录小圈起始点，起始点和结束点是否连通，和结束点的信息，就可以用区间查询（原理同上）统计是否连通。修改时分别维护两个树状数组信息。

#pragma GCC optimize(2)
#include
#include
#include
#include
#define low(x) (x&(-x))
using namespace std;
typedef long long ll;
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=10010,M=5e5+10;
int n,tot,sum;bool val[M];
int *a[N],st[N],ed[N],siz[N],w[M],belong[M];
struct BIT
{
	int c[M<<1];
	void add(int x,int y,int k){for (;x<=k;x+=low(x)) c[x]+=y;}
	int query(int x){int su=0;while (x) su+=c[x],x-=low(x);return su;}
}bit[2];
bool get(int x,int y)
{
	if (x==y) return 1;
	if (x>y) swap(x,y);
	return (bit[0].query(y)-bit[0].query(x-1)==y-x+1)||
		(bit[0].query(x)-bit[0].query(a[belong[x]][1]-1)+bit[0].query(a[belong[y]][siz[belong[y]]])-bit[0].query(y-1)==siz[belong[y]]-(y-x-1));
}//判小圈两点是否相通
bool get1(int x,int y)
{
	if (x==y) return 1;
	if (x>y) swap(x,y);
	return (bit[1].query(y)-bit[1].query(x-1)==y-x+1)||(bit[1].query(x)+bit[1].query(3*n)-bit[1].query(y-1)==3*n-y+1+x);
}//判大圈两点是否相通
int main()
{
	n=read();a[0]=&w[0];
	for (int i=1;i<=n;++i)
	{
		siz[i]=read();
		a[i]=a[i-1]+siz[i-1];
		for (int j=1;j<=siz[i];++j)val[++sum]=read(),w[sum]=sum,belong[sum]=i;
		st[i]=read(),ed[i]=read();
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=siz[i];++j)bit[0].add(a[i][j],val[a[i][j]],sum);
	for (int i=1,x;i<=n;++i)
	{
		x=i*3;bit[1].add(x-1,get(a[i][st[i]],a[i][ed[i]]),n*3);
		bit[1].add(x-2,val[a[i][st[i]]],n*3);
		bit[1].add(x , val[a[i][ed[i]]],n*3);
	}
	for (int i=0,_=read(),x,y,mode;i<_;++i)
	{
		mode=read();
		if (mode==1)
		{
			x=read();int u=belong[x];
			if (x==a[u][st[u]]) 
				bit[1].add(3*u-2,-val[x],n*3),bit[1].add(3*u-2,val[x]^1,n*3);
			else if (x==a[u][ed[u]]) 
				bit[1].add(3*u,-val[x],n*3),bit[1].add(3*u,val[x]^1,n*3);
			bit[1].add(u*3-1,-get(a[u][st[u]],a[u][ed[u]]),n*3);
			bit[0].add(x,-val[x],sum),bit[0].add(x,val[x]^1,sum);
			bit[1].add(u*3-1,get(a[u][st[u]],a[u][ed[u]]),n*3),val[x]^=1;
		}
		if (mode==2)
		{
			x=read(),y=read();
			int u=belong[x],v=belong[y];
			if
			(
				(get1(3*u,3*v-2)&&get(x,a[u][ed[u]])&&get(y,a[v][st[v]]))||
				(get1(3*v,3*u-2)&&get(x,a[u][st[u]])&&get(y,a[v][ed[v]]))
			)puts("Yes");//先从大圈判，再从小圈判，否则会被卡，见下图
			else if (u==v&&get(x,y)) puts("Yes");else puts("No");
		}
	}
	return 0;
}

下图黑点表示可以通行，白点反之，双边表示大圈边，单边表示小圈边，此时A点和B点仍可连通

T1 我要的幸福（happiness）

解题思路：模拟(考场已A，无心写思路）

#include
#include
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
const int N=1010;
int n,m,top;
int a[N][N];bool bo[N][N];
int sta[N*2];
bool dfs(int x,int y)
{
	if (bo[x][y]||(!a[x][y])) return 0;
	if (x==n&&y==m) return sta[++top]=a[x][y],1;
	if (x==n)
	{
		if (dfs(x,y+1)) return sta[++top]=a[x][y],1;
		else return bo[x][y]=1,0;
	}
	if (y==m)
	{
		if (dfs(x+1,y)) return sta[++top]=a[x][y],1;
		else return bo[x][y]=1,0;
	}
	if (a[x+1][y]1) printf("%d ",sta[top]),--top;
		printf("%d\n",sta[1]);
	}
	return 0;
}

T2 天黑黑(dark)

解题思路：模拟(考场已A，无心写思路）

#pragma GCC optimize(2)
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
const int N=4e5+10;
int a[N],top=1,tot;ll sum;
char s[N];
bool cmp(int x,int y){return x>y;}
int dfs(int i)
{
	if (s[i]=='X') return 1;
	else if (s[i]=='A') return dfs(++tot)+dfs(++tot);
	else return max(dfs(++tot),dfs(++tot));
}
int main()
{
	scanf("%s",s+1);
	while (~scanf("%d",&a[top]))++top;
	sort(a+1,a+top,cmp);
	int q=dfs(++tot);
	for (int i=1;i<=q;++i) sum+=a[i];
	printf("%lld\n",sum);
	return 0;
}