BZOJ 4603 平凡的骰子

发表于 2017-01-15 | 更新于 2018-06-18

Link

省选的时候连题意都没读懂的题。。

Solution

~~按照要求模拟即可~~

混合积三个向量的混合积是以它们为棱的平行六面体的有向体积。 ,为单位向量
多面体重心先考虑多边形重心。首先，三形的重心是三个点相加 $/3$ 。把多边形分成很多个互不相交的三角形，分别求出它们的重心，多边形的重心 $G=\dfrac {\sum G_iS_i}S$ 多面体的重心也相似，只是把多面体剖成四面体，四面体的重心就是四点座标相加 $/4$ 。把上式的 $S$ 换成 $V$ ，即可。
二面角数学老师讲课的时候说二面角的是锐角还是钝角只能自己感受，我是拒绝的。思考了很长时间，我终于找到了可以形式化的求法：用右手定则可以判断叉积的方向，让两个向量叉积朝向同侧（内/外），然后再用反余弦，再用 $180^{\circ}$ 减即可。（一眼秒掉这个做法的大神请不要D我。。）

然后这个题就可做了。。Orz考场A掉这道题的zff。。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100+10;
using std::vector;
typedef double ld;
const ld eps=1e-5,pi=acos(-1.0);
int fcmp(ld x)
{
	if(-eps<x && x<eps) return 0;
	return x<0?-1:1;
}
template <class T> T abs(T x){return x<0?-x:x;}
struct vec
{
	ld x,y,z;
	vec(){x=y=z=0;}
	vec(ld _x,ld _y,ld _z):x(_x),y(_y),z(_z){}
	ld norm(){return sqrt(x*x+y*y+z*z);}
	vec& operator +=(vec a){x+=a.x,y+=a.y,z+=a.z;return *this;}
	vec& operator -=(vec a){x-=a.x,y-=a.y,z-=a.z;return *this;}
	vec& operator *=(ld t){x*=t,y*=t,z*=t;return *this;}
	vec& operator /=(ld t){x/=t,y/=t,z/=t;return *this;}
};
typedef vec point;
//二维向量z座标为0，所以含有z的维都为零，只剩下一维，就成了叉积的模。
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y,a.z+b.z);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y,a.z-b.z);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t,a.z*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t,a.z/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y+a.z*b.z;}
vec outer(vec a,vec b){return vec(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
point plane[MAXN][MAXN],p[MAXN],gc;int pac[MAXN],n,fn;
point GC(point a,point b,point c,point d){return (a+b+c+d)/4;}
ld volume(point a,point b,point c,point d){return abs(inner(outer(b-a,c-a),d-a))/6;}
point GC()
{
	point O,C;
	for(int i=1;i<=n;i++)
		O+=p[i];
	O/=n;
	ld v=0;
	for(int i=1;i<=fn;i++)
	{
		point *sur=plane[i];
		for(int j=2;j<=pac[i]-1;j++)
		{
			ld subv=volume(sur[1],sur[j],sur[j+1],O);
			C+=GC(sur[1],sur[j],sur[j+1],O)*subv;
			v+=subv;
		}
	}
	C/=v;
	return C;
}
ld dihe(point l,point m1,point m2,point r)
{
	vec lv=l-m2,mv=m1-m2,rv=r-m2;
	vec n1=outer(mv,rv),n2=outer(lv,mv);
	ld cosine=inner(n1,n2)/(n1.norm()*n2.norm());
	return pi-acos(cosine);
}
ld area(int x)
{
	ld res=0;point *sur=plane[x];
	for(int i=2;i<=pac[x]-1;i++)
		res+=dihe(sur[i+1], sur[1],gc,   sur[i])+
			 dihe(sur[1],   sur[i],gc,   sur[i+1])+
			 dihe(sur[i],   sur[i+1],gc, sur[1])-pi;
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	red(n),red(fn);
	for(int i=1;i<=n;i++)
		fred(p[i].x),fred(p[i].y),fred(p[i].z);
	for(int i=1;i<=fn;i++)
	{
		int t;red(pac[i]);
		for(int j=1;j<=pac[i];j++)
			red(t),plane[i][j]=p[t];
	}
	gc=GC();
	for(int i=1;i<=fn;i++)
		printf("%.7lf\n",area(i)/(4*pi));
	return 0;
}

BZOJ 2741 L

发表于 2017-01-15 | 更新于 2018-06-17

Link

Solution

当然首先把XOR前缀和，转换成在 $[l-1,r]$ 中找两个元素使它们的XOR最大。这种分块的套路好像都差不多啊。对于每个块 $b$ 的块首元素 $head[b]$ ， $f[b][i]$ 表示点 $i$ 和区间 $[head[b],i]$ 中元素的XOR最大值，用可持久化Trie。对于每个询问 $[l-1,r]$ ，分成两部分 $[l-1,head[b]-1],[head[b],r]$ ，其中 $head[b]$ 是 $l$ 后面的第一个块首元素。后半部分已经预处理，前半部分只需要枚举每个数，查找它在区间 $[l,r]$ 中的最大XOR值。

Tips

分块思想一种套路。 把int右移32位会爆炸，会出来1!!切记！！

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=12000+10,MAXB=200;
typedef long long LL;
using std::max;
using std::min;
namespace iTrie
{
	const int LEN=31;//32 各种错误？？？？
	const int SIZE=LEN*MAXN<<1;
	struct Node
	{
		Node *son[2];
		int cnt;
		Node(){son[0]=son[1]=0,cnt=0;}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++)Node,*root[MAXN];
	int rc;
	Node *newNode(){return new(ME++) Node;}
	Node *newNode(Node *old)
	{
		static Node *cur;cur=new(ME++) Node;
		*cur=*old;return cur;
	}
	void Insert(Node *&rt,int x)
	{
		Node *cur=rt=newNode(rt);cur->cnt++;
		for(int i=LEN;~i;i--)
		{
			int c=(x>>i)&1;
			cur=cur->son[c]=newNode(cur->son[c]);
			cur->cnt++;
		}
	}
	bool next(Node *pl,Node *pr,int c){return pr->son[c]->cnt-pl->son[c]->cnt;}
	int Query(Node *pl,Node *pr,int x)
	{
		int res=x;
		for(int i=LEN;~i;i--)
		{
			int c=(x>>i)&1;
			if(next(pl,pr,c^1)) 
				pl=pl->son[c^1],pr=pr->son[c^1],res|=(1<<i);
			else 
				pl=pl->son[c],pr=pr->son[c],res&=~(1<<i);//没把这一位清零
		}
		return res;
	}
	int Query(int l,int r,int x)//maxxorsumofx with num in [l,r]
	{
		return Query(root[l],root[r+1],x);
	}
}using namespace iTrie;
int main()
{
	null->son[0]=null->son[1]=root[0]=null;Insert(root[rc=1]=root[0],0);
	static int a[MAXN],f[MAXB][MAXN],bn[MAXN],bhe[MAXN],xorsum[MAXN];
	int n,m;get(n),get(m);
	int bsz=(int)sqrt(n+1),bc=n/bsz+(bool)(n%bsz);
	for(int i=1;i<=n;i++)
	{
		get(a[i]);xorsum[i]=xorsum[i-1]^a[i];
		++rc;Insert(root[rc]=root[rc-1],xorsum[i]);
		bn[i]=(i-1)/bsz+1;
		if(bn[i]!=bn[i-1]) bhe[bn[i]]=i;
	}
	for(int b=bc;b;b--)
		for(int i=bhe[b];i<=n;i++)
			f[b][i]=max(f[b][i-1],Query(bhe[b]-1,i,xorsum[i]));
	int last=0;
	for(int i=1;i<=m;i++)
	{
		int l,r,x,y;get(x),get(y);
		l=min(((LL)x+last)%n+1,((LL)y+last)%n+1);
		r=max(((LL)x+last)%n+1,((LL)y+last)%n+1);
		if(bn[l]==bn[r])
		{
			last=0;
			for(int p=l;p<=r;p++) chkmx(last,Query(l-1,r,xorsum[p]));
		}
		else
		{
			last=f[bn[l]+1][r];
			for(int p=l-1;p<bhe[bn[l]+1];p++)	chkmx(last,Query(l-1,r,xorsum[p]));
		}
		printf("%d\n",last);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof array to small
 * WA
 * * * * * * * * * */

BZOJ 3198 Spring

发表于 2017-01-15 | 更新于 2018-06-18

Link

Solution

两行对应相等的情况总共有 $2^6$ 种，那就枚举这 $64$ 种情况，用Hash统计。每次边查询边插入。要求恰好为 $K$ ，用容斥。注意到公共序列长度为 $L$ 一对序列对答案的贡献是 $C_L^K$ ，所以容斥的时候要乘上 $C_L^K$ 。对数组的Hash可以仿照字符串Hash，而因为这道题是枚举出 $64$ 种情况的，所以不需要考虑没有被选中的位，可以直接跳过去。即序列 $10,10,10,10,10,10$ 的两个状态 $000011$ 和 $001100$ 算出来的Hash值可以是相等的，不会有影响的。这样可以让Hash值存储更多有用信息。

Tips

暴力枚举，一次答案只会增加1，所以复杂度肯定不会比答案更优。--lct1999

而暴力的优化策略常常把信息分类地存在数据结构里，让答案每次增加一类的总数。(我太弱了这么显然的东西还要记下来。。)

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10;
using std::sort;
using std::unique;
using std::lower_bound;
typedef long long LL;
typedef unsigned long long UL;
namespace iHash
{
	const int SIZE=MAXN*64;
	const int P=1e5+7;
	struct Node
	{
		UL key;int val;Node *pre;
		Node(UL key,int val,Node* pre):key(key),val(val),pre(pre){}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	//struct Hash{
	Node *id[P];
	void Insert(UL key)
	{
		int h=key%P;
		for(Node *ptr=id[h];ptr;ptr=ptr->pre)
			if(ptr->key==key) {ptr->val++;return;}
		id[h]=new(ME++) Node(key,1,id[h]);
	}
	int Count(UL key)
	{
		int h=key%P;
		for(Node *ptr=id[h];ptr;ptr=ptr->pre)
			if(ptr->key==key) {return ptr->val;}
		return 0;
	}
	void Clear(){memset(id,0,sizeof(id));ME=POOL;}
	//}H;
}using namespace iHash;
const int BASE=1e9+7;
UL ArrayHash(int *a,int S)
{
	UL res=0;
	for(int i=0;i<=5;i++)
		if(S&(1<<i)) //(res*=(UL)a[i]*primes[i];
			(res*=BASE)+=a[i];
	return res;
}
int main()
{
	static int lis[MAXN*6],lc,a[MAXN][6],C[10][10];
	C[0][0]=1;
	for(int i=1;i<=6;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	int n,K;get(n),get(K);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=5;j++)
			get(a[i][j]),lis[++lc]=a[i][j];
	sort(lis+1,lis+1+lc);lc=unique(lis+1,lis+1+lc)-lis-1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=5;j++)
			a[i][j]=lower_bound(lis+1,lis+1+lc,a[i][j])-lis;
	LL ANS=0;
	for(int S=0;S<=63;++S)
	{
		int cnt=__builtin_popcount(S);if(cnt<K) continue;
		Clear();
		for(int i=1;i<=n;i++)
		{
			UL code=ArrayHash(a[i],S);
			ANS+=C[cnt][K]*Count(code)*((cnt-K)&1?-1:1);
			Insert(code);
		}
	}
	printf("%lld\n",ANS);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 1046 上升序列

发表于 2017-01-15 | 更新于 2018-06-18

Link

读错题了。。NAIVE。要求得是下标字典序最小，以为是值字典序最小。不过看看Discuss区，好像不少人也被坑了。。

Solution

字典序受靠前的影响最大，所以就可以贪心，贪心出来一定是最优的。就类似01串在可持久化Trie上匹配最大的异或值一样。给了一个长度 $L$ ，如何判断可行并构造一组在原序列中“最靠前”的可行解？也就是说，从前向后枚举，如何判断第 $i$ 个位置的数字能否被加入答案？显然，如果以这个点为起点可以构成一个长度为 $L$ 的LIS，那这个点就可以取，而且由于是从前向后枚举，取这个字典序肯定是最小的。倒过来求出来LDS，然后从前向后构造最优解。

Tips

一定要把题目读对。。把给的条件中每个量的含义都弄清。。不能想当然

Code

不过话说，我只引入了upper_bound，为什么也可以用lower_bound而不会报错？？

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=10000+10;
using std::upper_bound;
using std::greater;
int main()
{
	freopen("input","r",stdin);
	static int f[MAXN],a[MAXN],next[MAXN],lis[MAXN];
	int n,ANS=0;get(n);
	for(int i=1;i<=n;i++) get(a[i]);
	for(int i=n;i;i--)
	{
		int p=lower_bound(lis+1,lis+1+n,a[i],greater<int>())-lis;
		f[i]=p;
		chkmx(lis[p],a[i]);
		chkmx(ANS,f[i]);
	}
	int m;get(m);
	for(int i=1;i<=m;i++)
	{
		int x;get(x);
		if(x>ANS) puts("Impossible");
		else
		{
			for(int j=1,p=0;j<=n && x;j++)
				if(f[j]>=x && a[j]>a[p])
					printf("%d%s",a[p=j],--x?" ":"\n");
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 1922 大陆争霸

发表于 2017-01-15 | 更新于 2018-06-18

Link

毫无头绪。。保护着N的必须摧毁，挡着N的可以选择一个摧毁？有保护关系的必须摧毁，挡着的可以选择一个摧毁？处理出摧毁某个点的最短时间？？取max？各个点的摧毁是互不影响的？？先把环去掉？？

Solution

性质

限制一个点 $p$ 的最早到达时间 $t$ 的有

经过图上的点，消灭掉沿途的各种阻挡它的，然后到达它的时间;
保护它的所有点集 $S$ 中, $max(t_u|u \in S)$
方法
对这两个量跑Dijstra。每次更新要更新相邻点的最早到达时间，和被保护点的最早不被保护的时间。每次循环，选择一个没有被保护，且真实时间最小的点来进行松弛。

以下内容纯属一个蒟蒻的自言自语！！求打脸！！

Dijstra算法正确性

设用过的点集为 $S$ ，则需要证明每次选出 $V-S$ 中 $dist_u$ 最小的那个点 $u$ 的 $dist_u==sp_u$ 。假设，那 $sp_u$ 的路径一定是从 $s$ 走到 $S$ 中的一个点 $x$ ，从 $x$ 走到 $V-S$ 中的点 $y$ ，再从 $y$ 走到 $u$ 。则一定有 $sp_y==dist_y$ 。

假如说， $dist_y$ 还可以被 $w(w\in V-S)$ 松弛，那到 $u$ 的最短路就是从 $s\rightarrow p(p \in S)\rightarrow w(w\in V-S)\rightarrow y\rightarrow u$ ，到 $u$ 的最短路就不会来源于 $y$ 而是来源于 $w$ 了。

而 $sp_y\ge dist_u$ 又要 $sp_y+D(y,u)< dist_u$ 这是不可能的。所以 $dist_u==sp_u$ 。

对于这道题

假设 $S$ 中的点的答案已经最优，且 $V-S$ 中的点 $p$ 能优化新选出的 $u$ 。那么 $p$ 没被加入 $S$ 一定是因为受到了限制。而限制它的那个点的值都 $\ge max(dist[u],limit[u])$ ，所以 $p$ 不可能去优化 $u$ 。

总结

Dijstra解决的问题可以明确地划分出阶段来，采用Dijstra的变形必须要满足每次迭代选出的点的答案已经最优。这虽然限制它的灵活性，但有时候也是优势。对于这个题目，因为涉及到最小值中取最大，就必须保证用来更新一个点的最小值的确是最小的，否则如果变小之后，更新也没有意义了。相反，SPFA在转移的时候不需要保证当前最优，可以用队列来反反复复地修改松弛，所以更加灵活，但就解决不了这种鬼畜的问题了。关于SPFA的转移作用，参见TA爷的神文 OK。。不得不说这是一道好题。。

Tips

这类鬼畜的最优化问题怎么想到正解？寻找限制最优解的量，根据其特点转化成DP/最大流/最小割/最短路之类的。建模能力还在分析问题的能力之后。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int MAXN=3000+10,MAXM=70000+10;
const LL INF=LLONG_MAX;
using std::max;
using std::pair;
using std::vector;
using std::greater;
using std::priority_queue;
//SPFA在转移的时候不需要保证当前最优，所以如果当前点不是最优的答案会影响到结果，就不能用SPFA
//相反,DIJSTRA在转移的时候当前点已经是最优的了，所以。
int proc[MAXN],edge[MAXN][MAXN],n;bool prot[MAXN][MAXN];
LL SP(int s,int t)
{
	static LL dist[MAXN],limit[MAXN];
	static bool ud[MAXN];	
	memset(dist,31,sizeof(dist));
	limit[s]=dist[s]=0;
	for(int i=1;i<=n;i++)//n-1
	{
		LL rv=INF;int cur;
		for(int u=1;u<=n;u++)
			if(!ud[u] && !proc[u] && chkmn(rv,max(dist[u],limit[u])))
				cur=u;	
		for(int u=1;u<=n;u++)
		{
			if(prot[cur][u])
			{
				proc[u]--;
				chkmx(limit[u],rv);
			}
			chkmn(dist[u],rv+edge[cur][u]);
		}
		ud[cur]=1;
	}
	return max(dist[t],limit[t]);
}
int main()
{
	freopen("input","r",stdin);
	int m;get(n),get(m);
	memset(edge,31,sizeof(edge));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;get(u),get(v),get(w);
		chkmn(edge[u][v],w);
	}
	for(int i=1;i<=n;i++)
	{
		int x;get(proc[i]);
		for(int j=1;j<=proc[i];j++) 
			get(x),prot[x][i]=1;
	}
	printf("%lld\n",SP(1,n));
	return 0;
}
/* AC Record(Bugs) *
 *
 * * * * * * * * * */

BZOJ 3531 旅行

发表于 2017-01-15 | 更新于 2018-06-18

Link

Solution

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10,NLOGN=MAXN*30,INF=0x1f1f1f1f;
using std::max;
using std::min;
using std::swap;

struct Edge{int to,pre;}e[MAXN<<1];int id[MAXN],ec;
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
struct Data
{
	int maxv,sumv;
	Data(){maxv=-INF,sumv=0;}
	Data(int _maxv,int _sumv):maxv(_maxv),sumv(_sumv){}
};
Data Merge(Data a,Data b){return Data(max(a.maxv,b.maxv),a.sumv+b.sumv);}
struct SegNode
{
	SegNode *son[2];
	Data v;int cnt;
	void up()
	{
		v=Merge(son[0]?son[0]->v:Data(),son[1]?son[1]->v:Data());
		cnt=(son[0]?son[0]->cnt:0)+(son[1]?son[1]->cnt:0);
	}
};
namespace SegOpt
{
	SegNode *ME=new SegNode[NLOGN];
	//有了这一句就高亮不了了。。。
    //SegNode *newNode(Data v=Data())
	{
		static SegNode* cur;
		cur=ME++;cur->v=v;cur->son[0]=cur->son[1]=0;cur->cnt=1;
		return cur;
	}
	void Edit(SegNode *&pos,int L,int R,int goal,Data dv,int dc)
	{
		if(!pos) pos=newNode();
		if(L==R)
		{
			pos->v=dv;
			pos->cnt=dc;
		}
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,dv,dc);
			else Edit(pos->son[1],MID+1,R,goal,dv,dc);
			pos->up();
		}
	}
	Data Access(SegNode *&pos,int L,int R,int l,int r)
	{
		if(!pos || pos->cnt==0) return Data();
		if(L==l && R==r) return pos->v;
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID) return Access(pos->son[0],L,MID,l,r);
			else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
			else return Merge(Access(pos->son[0],L,MID,l,MID),Access(pos->son[1],MID+1,R,MID+1,r));
		}
	}
}
using namespace SegOpt;
struct TreapNode
{
	TreapNode *son[2];
	SegNode *root;int v,py;
};
namespace TreapOpt
{
	const int P=1e5+7;
	TreapNode *ME=new TreapNode[NLOGN];
	TreapNode *newNode(int v)
	{
		static TreapNode *cur;
		cur=ME++;cur->v=v;cur->root=0;cur->py=rand()%P;
		cur->son[0]=cur->son[1]=0;
		return cur;
	}
	void trans(TreapNode *&pos,int d)
	{
		TreapNode *s=pos->son[d];
		pos->son[d]=s->son[!d];
		s->son[!d]=pos;
		pos=s;
	}
	int adjust(TreapNode *&pos)
	{
		int d=(pos->son[0]?pos->son[0]->py:P)>(pos->son[1]?pos->son[1]->py:P);
		if(pos->son[d] && pos->son[d]->py<pos->py) trans(pos,d),d^=1;
		else d=-1;
		return d;
	}
	TreapNode *Insert(TreapNode *&pos,int v)
	{
		if(!pos)
			return pos=newNode(v);
		else
		{
			int jud=pos->v<v;
			TreapNode *p=Insert(pos->son[jud],v);
			adjust(pos);
			return p;
		}
	}
	TreapNode *Find(TreapNode *pos,int v)
	{
		while(pos)
		{
			if(pos->v==v)
				return pos;
			else pos=pos->son[pos->v<v];
		}
		return 0;
	}
	void out(TreapNode *pos)
	{
		if(!pos) return;
		out(pos->son[0]);
		printf("%d ",pos->v);
		out(pos->son[1]);
	}
	void print(TreapNode *pos)
	{
		puts("BEGIN");
		out(pos);
		puts("\nEND");
	}
}
using namespace TreapOpt;
struct Part
{
	TreapNode *root;
	int sz,top;
}part[MAXN],*cn[MAXN];
int rc,dep[MAXN],sz[MAXN],rnk[MAXN],fa[MAXN];
void DFS(int pos)
{
	int mx=-1;sz[pos]=1;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(fa[pos]==u) continue;
		fa[u]=pos;dep[u]=dep[pos]+1;
		DFS(u);
		sz[pos]+=sz[u];
		if(mx==-1 || sz[u]>sz[mx]) mx=u;
	}
	if(!pos) mx=-1;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(fa[pos]==u) continue;
		if(u==mx)
		{
			cn[pos]=cn[u];
			rnk[pos]=rnk[u]+1;
		}
		else
		{
			cn[u]->top=u;
			cn[u]->sz=rnk[u];
		}
	}
	if(pos && !cn[pos])
	{
		cn[pos]=part+ ++rc;
		rnk[pos]=1;
	}
}
int val[MAXN],color[MAXN];
void Change(int pos,int w,int c)
{
	TreapNode *po=Find(cn[pos]->root,color[pos]),
			  *pn=Find(cn[pos]->root,c);
	if(po) Edit(po->root,1,cn[pos]->sz,rnk[pos],Data(),0);
	if(!pn) pn=Insert(cn[pos]->root,c);
	Edit(pn->root,1,cn[pos]->sz,rnk[pos],Data(w,w),1);
	val[pos]=w,color[pos]=c;
}
Data Query(int p1,int p2)
{
	Data res=Data();int c=color[p1];//val..
	while(cn[p1]!=cn[p2])
	{
		if(dep[cn[p1]->top]<dep[cn[p2]->top]) swap(p1,p2);
		TreapNode *p=Find(cn[p1]->root,c);
		if(p)
			res=Merge(res,Access(p->root,1,cn[p1]->sz,rnk[p1],cn[p1]->sz));
		p1=fa[cn[p1]->top];//if(!p1) p1=1;
	}
	if(rnk[p1]>rnk[p2]) swap(p1,p2);
	TreapNode *p=Find(cn[p1]->root,c);
	if(p)
		res=Merge(res,Access(p->root,1,cn[p1]->sz,rnk[p1],rnk[p2]));//cn[p1]->sz
	if(res.maxv==-INF) res=Data(val[p1],val[p1]);
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	static int w[MAXN],c[MAXN];
	int n,m;get(n),get(m);
	for(int i=1;i<=n;i++) get(w[i]),get(c[i]);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;get(x),get(y);
		Adde(x,y);
	}
	Adde(0,1);
	DFS(0);
	for(int i=1;i<=n;i++) Change(i,w[i],c[i]);
	for(int i=1;i<=m;i++)
	{
		char opt[5];int x,y,w,c;
		scanf("%s",opt);
		switch(opt[1])
		{
			case 'C':
				get(x),get(c);
				Change(x,val[x],c);//val[i]
				break;
			case 'W':
				get(x),get(w);
				Change(x,w,color[x]);
				break;
			case 'S':
				get(x),get(y);
				printf("%d\n",Query(x,y).sumv);
				break;
			case 'M':
				get(x),get(y);
				printf("%d\n",Query(x,y).maxv);
				break;
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * WA  psz
 * WA  1
 * WA p1==p2
 *
 * * * * * * * * * */

BZOJ 2738 矩阵乘法

发表于 2017-01-15 | 更新于 2018-06-18

Link

Solution

看道题，整体二分嘛。然后很开心地写。每次执行的值域是 $[low,high]$ 把矩阵中当前 $\le (low+high)/2$ 的点插入BIT，查询个矩阵和就好了。然后T飞了。。然后发现我每次将值插入BIT，是暴力遍历整个矩阵。。每次遍历都是 $O(n^2)$ ，而每次不管值域多小都有 $O(n^2)$ ，所以仅仅遍历矩阵的复杂度就是 $O(n^3)$ 。。不T才怪。。然后把所有数都提取出来排个序，每次在排序的区间内把元素插入BIT，复杂度就有保障了，但是WA？？为什么WA？？对拍之后，发现我在求子矩阵和的时候把左上角的那个矩阵加了两次。。真不知道怎么想的。。写的时候还觉得很有道理=_=。

Code

把scanfdefine成get就是为了在卡常数的时候原地把get的实现换成fread优化就行了。。

//Code by Lucida
#include<bits/stdc++.h>
//#define get(x) scanf("%d",&x)
namespace IO
{
	const int IN=1e7;
	char inbuf[IN],*iptr=inbuf,*iend=inbuf;
	#define getc() (iptr==iend && (iend=(iptr=inbuf)+fread(inbuf,1,IN,stdin),iptr==iend)?EOF:*iptr++)
	inline void get(int &x)
	{
		static int f,ch;f=1;
		while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
		x=ch-'0';
		while(isdigit(ch=getchar())) (x*=10)+=ch-'0';
		x*=f;
	}
}using namespace IO;
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=500+10,MAXQ=60000+10;
using std::copy;
using std::unique;
using std::sort;
using std::lower_bound;

struct BIT
{
	int a[MAXN][MAXN],us[MAXN][MAXN],ut,n,m;
	void Clear(){++ut;}
	#define lowbit(x) (x & -x)
	void Add(int x,int y,int v)
	{
		for(int i=x;i<=n;i+=lowbit(i))
		{
			int *pa=a[i],*pu=us[i];
			for(int j=y;j<=m;j+=lowbit(j))
			{
				if(pu[j]!=ut) pu[j]=ut,pa[j]=0;
				pa[j]+=v;
			}
		}
	}
	int Sum(int x,int y)
	{
		if(!x || !y) return 0;
		int res=0;
		for(int i=x;i;i-=lowbit(i))
		{
			int *pa=a[i],*pu=us[i];
			for(int j=y;j;j-=lowbit(j))
			{
				if(pu[j]!=ut) pu[j]=ut,pa[j]=0;
				res+=pa[j];
			}
		}
		return res;
	}
	int Sum(int x1,int y1,int x2,int y2)
	{
		return Sum(x2,y2)-Sum(x1-1,y2)-Sum(x2,y1-1)+Sum(x1-1,y1-1);
	}
	#undef lowbit
}bit;
struct Num
{
	int x,y,v;
	bool operator <(const Num &a) const
	{
		return v<a.v;
	}
}nums[MAXN*MAXN];
struct Query
{
	int x1,x2,y1,y2,K,id;
}p[MAXQ],t[MAXQ];int a[MAXN][MAXN],ANS[MAXQ],n;
void DC(int low,int high,int L,int R)
{
	if(low==high)
	{
		for(int i=L;i<=R;i++) ANS[p[i].id]=nums[low].v;
		return;
	}
	bit.Clear();
	int mid=(low+high)>>1;
	for(int i=low;i<=mid;i++)
		bit.Add(nums[i].x,nums[i].y,1);
	int pl=L,pr=R;
	for(int i=L;i<=R;i++)
	{
		int res=bit.Sum(p[i].x1,p[i].y1,p[i].x2,p[i].y2);
		if(p[i].K<=res) t[pl++]=p[i];
		else p[i].K-=res,t[pr--]=p[i];
	}
	copy(t+L,t+R+1,p+L);
	DC(low,mid,L,pl-1);DC(mid+1,high,pr+1,R);
}
int main()
{
	int Q;
	get(n),get(Q);bit.n=bit.m=n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			get(a[i][j]);
	for(int i=1;i<=Q;i++)
	{
		get(p[i].x1),get(p[i].y1),get(p[i].x2),get(p[i].y2),get(p[i].K);
		p[i].id=i;
	}
	
	int nc=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			nums[++nc].v=a[i][j];
			nums[nc].x=i,nums[nc].y=j;
		}
	sort(nums+1,nums+1+nc);
	
	DC(1,nc,1,Q);
	for(int i=1;i<=Q;i++) printf("%d\n",ANS[i]);
	return 0;
}
/* AC Record(Bugs) *
 * TLE Naive
 * WA 2DBIT
 * * * * * * * * * */

BZOJ 2733 永无乡

发表于 2017-01-15 | 更新于 2018-06-18

Link

Solution

很模板的题目了。。想试试能不能以最快的速度写出来并且A掉。20min写完之后RE了，结果发现是数组开小了。。线段树只有建立一棵树的时候节点数才能用 $n<<2$ ，否则即使不可持久化也可能是 $n \log n$ 。多么显然。。我居然没想到。。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10;
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
namespace Seg
{
	const int SIZE=MAXN*25,TL=1;
	int TR;
	struct Node
	{
		Node *son[2];
		int cnt,id;
		Node(){son[0]=son[1]=0;cnt=id=0;}
		void up(){cnt=son[0]->cnt+son[1]->cnt;}
		bool isleaf(){return son[0]==son[1];}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node;
	Node *newNode()
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;
		cur->cnt=cur->id=0;return cur;
	}
	void Edit(Node *&pos,int L,int R,int goal,int cnt,int id)
	{
		if(pos==null) pos=newNode();
		if(L==R) pos->cnt=cnt,pos->id=id;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,cnt,id);
			else Edit(pos->son[1],MID+1,R,goal,cnt,id);
			pos->up();
		}
	}
	int Access(Node *pos,int L,int R,int K)
	{
		if(pos==null) return -1;//assert(1);
		if(L==R) return pos->id;
		else
		{
			int MID=(L+R)>>1;
			if(K<=pos->son[0]->cnt) return Access(pos->son[0],L,MID,K);
			else return Access(pos->son[1],MID+1,R,K-pos->son[0]->cnt);
		}
	}
	Node *Merge(Node *p1,Node *p2)
	{
		if(p1==null) return p2;
		if(p2==null) return p1;
		//merge leaf is not in need
		p1->son[0]=Merge(p1->son[0],p2->son[0]);
		p1->son[1]=Merge(p1->son[1],p2->son[1]);
		p1->up();
		return p1;
	}
}using namespace Seg;
Seg::Node *root[MAXN];
namespace DJU
{
	int fa[MAXN];
	int Root(int x){return fa[x]?fa[x]=Root(fa[x]):x;}
}using namespace DJU;
void Join(int p1,int p2)
{
	p1=Root(p1),p2=Root(p2);
	if(p1==p2) return;
	if(root[p1]->cnt<root[p2]->cnt) swap(p1,p2);//把p2并到p1
	root[p1]=Merge(root[p1],root[p2]);fa[p2]=p1;
}
int main()
{
	static int a[MAXN],t[MAXN];
	int n,m;get(n),get(m);TR=n;
	for(int i=1;i<=n;i++) get(a[i]),t[i]=a[i];
	sort(t+1,t+1+n);
	for(int i=1;i<=n;i++)
		Edit(root[i]=null,TL,TR,a[i]=lower_bound(t+1,t+1+n,a[i])-t,1,i);
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Join(x,y);
	}
	int Q;get(Q);
	for(int i=1;i<=Q;i++)
	{
		char opt;while(!isalpha(opt=getchar()));
		int x,y;get(x),get(y);
		if(opt=='Q') printf("%d\n",Access(root[Root(x)],TL,TR,y));
		else Join(x,y);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof array too small;;
 *		n log n->n*4 只有一棵树的时候才能用n<<2，
 *		否则即使不可持久化也可能是n log n
 * * * * * * * * * */

BZOJ 1923 外星千足虫

发表于 2017-01-15 | 更新于 2018-06-18

Link

一看到奇偶性，立刻想到了2-SAT。发现2-SAT要建出图枚举出各种情况的复杂度好象是指数级别。想了会儿，没办法，看题解，发现居然是这种神奇的东西。

Solution

给定 $m$ 个形如的方程，问最少要到用到前几个方程就能判断出每个量的奇偶性。这个转化技巧要记得。很好理解，有奇数个奇数和就是奇数，否则和就是偶数。这道题到这就可以解决了。在Gauss-Jordan的时候，依次解每个变量，记录向下找找到 $A_{j,i}==1$ 的最大的 $j$ 就是答案了。

Tips

奇偶 $\rightarrow$ 2-SAT/XOR方程组。 以下纯属一个蒟蒻的自言自语 ~~其实部分2-SAT问题也可以用XOR方程组解的？True\False对应奇偶？~~但应该应用范围很小吧

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::bitset;
const int N=1000+1,MAXN=N+10,MAXM=2000+10;
bitset<N> a[MAXM];
int Gauss(int n,int m)
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		
		for(int j=i;j<=m;j++)
		{
			if(a[j][i])
			{
				swap(a[i],a[j]),chkmx(res,j);
				break;
			}
			else if(j==m) return -1;
		}
		for(int j=1;j<=m;j++)
			if(a[j][i] && j!=i) a[j]^=a[i];
	}
	return res;
}
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n,m;get(n),get(m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		for(char *ptr=s;*ptr;++ptr)
			a[i][ptr-s+1]=*ptr-'0';
		scanf("%s",s);
		a[i][0]=*s-'0';
	}
	int ANS=Gauss(n,m);
	if(~ANS)
	{
		printf("%d\n",ANS);
		for(int i=1;i<=n;i++)
			puts(a[i][0]?"?y7M#":"Earth");
	}
	else puts("Cannot Determine");
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 2462 矩阵模板

发表于 2017-01-15 | 更新于 2018-06-18

Link

Solution

枚举每个小矩阵，依次把每行加入Trie，建立AC自动机。用大矩阵的每一行去匹配小矩阵，如果匹配成功了，就可以计算出相应矩阵左上角的座标。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1000+10;
using std::vector;

namespace AC
{
	const int SIZE=MAXN*MAXN;	
	struct Node
	{
		Node *son[2],*fail,*last;
		vector<int> match;
		Node *&next(char c){return son[c-'0'];}
	}*root,POOL[SIZE],*ME=POOL;//[MAXN];
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->match.clear();cur->son[0]=cur->son[1]=cur->fail=cur->last=0;
		return cur;
	}
	void Insert(char *s,int l)
	{
		if(!root) root=newNode();
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->match.push_back(l);
	}
	void Build()
	{
		static Node *Q[SIZE];
		static int hd,ta;
		hd=1,ta=0;
		for(char c='0';c<='1';++c)
		{
			Node *&son=root->next(c);
			if(!son) son=root;
			else
			{
				son->fail=root;
				son->last=0;
				Q[++ta]=son;
			}
		}
		while(hd<=ta)
		{
			Node *cur=Q[hd++];
			for(char c='0';c<='1';c++)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->match.size()?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}
using namespace AC;
int A[MAXN][MAXN],a,b;
void Clear()
{
	ME=POOL;
	root=0;
	memset(A,0,sizeof(A));
}
void DFS(Node *pos,int x,int y)
{
	for(int i=0;i<pos->match.size();i++)
	{
		int u=pos->match[i];
		if(x-u+1>=1 && y-b+1>=1) A[x-u+1][y-b+1]++;
	}
	if(pos->last) DFS(pos->last,x,y);
}
int main()
{
	static char mtrx[MAXN][MAXN],str[MAXN];
	int n,m;get(n),get(m),get(a),get(b);
	for(int i=1;i<=n;i++)
		scanf("%s",mtrx[i]+1);
	int Q;get(Q);
	while(Q--)
	{
		Clear();
		for(int i=1;i<=a;i++)
		{
			scanf("%s",str+1);
			Insert(str,i);
		}
		Build();
		for(int i=1;i<=n;i++)
		{
			Node *cur=root;
			for(int j=1;j<=m;j++)
			{
				cur=cur->next(mtrx[i][j]);
				if(cur->match.size()) DFS(cur,i,j);
				else if(cur->last) DFS(cur->last,i,j);
			}
		}
		int matched=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(A[i][j]>=a)
				{
					matched=1;
					break;
				}
		printf("%d\n",matched);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof queue is to small 
 * * * * * * * * * */

Lucida

It's been a while.

222 日志

127 标签

Solution

Code

Solution

Tips

Code

Solution

Tips

Code

Solution

Tips

Code

Solution

性质

方法

Dijstra算法正确性

对于这道题

总结

Tips

Code

Code

Solution

Code

Solution

Code

Solution

Tips

Code

Solution

Code