BZOJ 3523 Bricks

发表于 2017-03-11 | 更新于 2018-06-18

Link

Solution

贪心+模拟，每次取剩下的个数最大的，在最大的里面如果有 $end$ ，就先取 $end$ 。被priority_queueFunctor的奇葩规则坑了一会儿。

Code

#include "lucida"
using std::pair;
using std::make_pair;
using std::priority_queue;
using std::vector;
const int MAXN=1000000+11;
int ed;
struct CmpFunctor {
	bool operator () (const pair<int,int> &a,const pair<int,int> &b) {
		return (a.first!=b.first)?a.first<b.first:(b.second==ed);	
	}//按照这个排序方式，排到后面的 优先级高 先弹出来
};
int main() {
	freopen("input","r",stdin);
	static int s[MAXN],a[MAXN];
	priority_queue<pair<int,int>,vector<pair<int,int> >,CmpFunctor> Q;
	int n,st,m=0;is>>n>>st>>ed;
	pair<int,int> pred,now;
	bool tak=1;
	for(int i=1;i<=n;++i) {
		is>>a[i];m+=a[i];
		//tak&=(i==st || i==ed)?(bool)a[i]:1;
		//写在else里面 直接排掉了st==ed的情况
		if(i==ed)
			a[i]--;
		if(i==st)
			pred=make_pair(--a[i],i);
		else 
			Q.push(make_pair(a[i],i));
		if(a[i]<0) {
			tak=0;
			break;
		}
	}
	if(n==1 && m!=1)
		tak=0;
	s[1]=st;s[m]=ed;
	for(int i=2;i<=m-1 && tak;++i) {
		now=Q.top();Q.pop();
		//os<<'<'<<now.first<<','<<now.second<<'>'<<'\n';
		if(now.first<=0) {
			tak=0;
			break;
		} else {
			s[i]=now.second;
			now.first--;
			Q.push(pred);
			pred=now;
		}
	}
	for(int i=2;i<=m && tak;++i)
		tak&=(s[i]!=s[i-1]);
	if(tak)
		for(int i=1;i<=m;++i)
			os<<s[i]<<(i==m?'\n':' ');
	else
		os<<0<<'\n';
	return 0;
}

BZOJ 3526 Card

发表于 2017-03-10 | 更新于 2018-06-18

Link

为什么这么简单的做法还是想不出来

Solution

先考虑暴力：修改一个位置之后，从这个数字开始向后递推能否构成单调数列。每次是 $O(n)$ 的，但是可以看出，做了很多无用功，因为每次转移的行为都是一样的，只要知道起点的值后面的值就都知道了。考虑一下每个单调数列的来源，是 $i-1$ 的单调数列加上一个满足不降且最小的数字。修改了一个位置之后，不能 $O(1)$ 知道对于它后面的某个数字，它所转移过来的那个位置还是不是合法，也就是说，不能知道的传递路径是否被阻断，也不能知道是否还有别的路径。但是可以发现，对于一段整体的数列，开头的两个数字是否合法就直接决定了后面所有点是否合法，即知道了的起始点，就能固定的路径。这样就可以看出子结构了，进一步想一下，发现可以用线段树维护。

Tips

根据暴力的无用功，寻找问题子结构，寻找合法的状态和转移，从而套数据结构维护。

Code

#include "lucida"
using std::swap;
using std::pair;
const int MAXN=200000+11;
namespace _SegTree_ {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		pair<int,int> st,ed;
		Node(pair<int,int> v):st(v),ed(v) {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
			return Me++;
		}
		void Modify(pair<int,int> v) {
			st=ed=v;
		}
		void Up() {
			st=son[0]->st;
			if(son[0]->ed.first<=son[1]->st.first)
				ed.first=son[1]->ed.first;
			else if(son[0]->ed.first<=son[1]->st.second)
				ed.first=son[1]->ed.second;
			else
				ed.first=INT_MAX;
			if(son[0]->ed.second<=son[1]->st.first)
				ed.second=son[1]->ed.first;
			else if(son[0]->ed.second<=son[1]->st.second)
				ed.second=son[1]->ed.second;
			else
				ed.second=INT_MAX;
		}
	};
	struct SegTree {
	//private:
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R,pair<int,int> arr[]) {
			pos=new Node(arr[L]);
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,arr);
				Build(pos->son[1],Mid+1,R,arr);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,pair<int,int> v) {
			if(L==R)
				pos->Modify(v);//st=pos->ed=v;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal,v);
				else 
					Edit(pos->son[1],Mid+1,R,goal,v);
				pos->Up();
			}
		}
	//public:
		SegTree(int L,int R,pair<int,int> arr[]):L(L),R(R) {
			Build(root,L,R,arr);
		}
		Node *&operator ->() {
			return root;
		}
		void Modify(int pos,pair<int,int> v) {
			Edit(root,L,R,pos,v);
		}
	};
}using _SegTree_::SegTree;
int main() {
//	freopen("input","r",stdin);
	static pair<int,int> cd[MAXN];
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		is>>cd[i].first>>cd[i].second;
		if(cd[i].first>cd[i].second)
			swap(cd[i].first,cd[i].second);
	}
	SegTree seg(1,n,cd);
	int m;is>>m;
	for(int i=1;i<=m;++i) {
		int x,y;
		is>>x>>y;
		swap(cd[x],cd[y]);
		seg.Modify(x,cd[x]);
		seg.Modify(y,cd[y]);
		os<<((seg->ed.first!=INT_MAX || seg->ed.second!=INT_MAX)?"TAK":"NIE")<<'\n';
	}
	return 0;
}

BZOJ 3831 Little Bird

发表于 2017-03-10 | 更新于 2018-06-17

Link

233居然没有想出单调队列的做法觉得用线段树妥妥T飞，单调队列没法维护再一次被教育了

Solution

$f[i]=\min\left\{f[j]+(h[j]\le h[i])|j+k\le i\right\}$ 如果是 $f[j]$ 加一个常数，显然维护一个 $f[]$ 递增的单调队列加的不是常数，但也可以看到加的数字非 $0$ 即 $1$ 。也就说，原本有 $f[u]< f[v]$ ，转移过来的DP值 $u$ 至少不会比 $v$ 大。所以按照这个结论就可以维护了 DP值不相同，按照DP值从小到大排序否则，按照高度从大到小排序

Tips

用类似贪心策略的分析来得到优化DP转移的结论

Code

#include "lucida"

const int MAXN=1e6+11;

int n;
struct Node {
	int val,h;
	bool operator <(const Node &a) const {
		return val!=a.val?val<a.val:h>a.h;
	}
}f[MAXN];
int Q[MAXN],he,ta;
int DP(int k) {
	f[1].val=0;
	Q[he=ta=1]=1;
	for(int i=2;i<=n;++i) {
		while(he<=ta && Q[he]+k<i)
			he++;
		f[i].val=f[Q[he]].val+(f[Q[he]].h<=f[i].h);
		while(he<=ta && f[i]<f[Q[ta]])
			ta--;
		Q[++ta]=i;
	}
	return f[n].val;
}
int main() {
//	freopen("input","r",stdin);
	is>>n;
	for(int i=1;i<=n;++i)
		is>>f[i].h;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		int K;is>>K;
		os<<DP(K)<<'\n';
	}
	return 0;
}

BZOJ 3521 Salad Bar

发表于 2017-03-10 | 更新于 2018-06-18

Link

Solution

条件等价于选出一个子序列 $[l,r]$ ，使得对于 $\forall i\in [l,r],count(p)[l,i]\ge \dfrac {i-l+1}2,count(p)[i,r]\ge \dfrac {r-i+1}2$ 然后化简 $pref[i]-pref[l-1]\ge \dfrac {i-l+1}2,2pref[i]-i\ge 2pref[l-1]-(l-1)$ 对于后缀的情况同理根据这个式子，可以 $O(n\log n)$ 地求出以每个点为开头，向左\右延伸，最远的位置 $lnl,lnr$ 。得到了这个之后，问题就转化为选出一对 $l,r$ ，使得 $lnr(l)\ge r,lnl(r)\le l$ 也可以 $O(n\log n)$ 做

看到数据范围和时限，一开始觉得应该是一个很短的纯思路题。在题解的搜索页面上，看到了“树状数组”的字样，才往 $O(n\log n)$ 上想。网上的解法都是 $2O(n)+O(n\log n)$ ，我的做法是 $3O(n\log n)$ ，感觉很虚。果然写完之后T了。但是本着n方过百万，卡常出奇迹的心态，开始用gprof卡常。最后把ST的写法改了一下，更好地利用了cache缓存，然后就A了。

Tips

卡常出奇迹 ST表要写cache友好的版本

Code

#include "lucida"
int __a,__b;
#define min(x,y) ( ((__a=(x))<(__b=(y)))?__a:__b )
//using std::min;
int __swap;
#define swap(x,y) (__swap=x,x=y,y=__swap)
using std::reverse;
const int MAXN=1000000+11,MAXLOG=22;

int log_2[MAXN],f[MAXLOG][MAXN];
void ST(int a[],int n) {
	for(int i=1,*fp=&f[0][1];i<=n;++i,++fp)
		*fp=a[i];
	for(int lg=1,endlg=log_2[n];lg<=endlg;++lg)
		for(int i=1,endi=n-(1<<lg)+1,*fp=&f[lg][i],*gp1=&f[lg-1][i],*gp2=&f[lg-1][i+(1<<lg>>1)];i<=endi;++i,++fp,++gp1,++gp2) {//endi=n-(1<<i)+1..
			*fp=min(*gp1,*gp2);
		}
}
int rgmn(int l,int r) {
	if(l>r) swap(l,r);
	int lg=log_2[r-l+1],*fp=f[lg];
	return min(fp[l],fp[r-(1<<lg)+1]);
}
void Calc(int n,char s[],int d[]) {
	static int pref[MAXN];
	for(int i=1;i<=n;++i)
		pref[i]=pref[i-1]+(s[i]=='p');
	for(int i=1;i<=n;++i)
		(pref[i]*=2)-=i;
	//找到最后一个连续的比他大的值
	ST(pref,n);
	for(int i=1;i<=n;++i) {
		int L=i,R=n;
		if(s[i]=='p') {
			while(L!=R) {
				int Mid=(L+R+1)>>1;
				if(rgmn(L,Mid)<pref[i-1]) 
					R=Mid-1;
				else
					L=Mid;
			}
			d[i]=L-i+1;
		} else
			d[i]=1;
	}
}
int main() {
	static char s[MAXN];
	static int pref[MAXN],suf[MAXN];
//	freopen("input","r",stdin);
	int n;is>>n>>(s+1);
	log_2[0]=-1;
	for(int i=1;i<=n;++i)
		log_2[i]=log_2[i>>1]+1;
	int Ans=0;
	Calc(n,s,pref);
	for(int i=1;i<=n;++i)
		pref[i]=i+pref[i]-1;
	reverse(s+1,s+1+n);
	Calc(n,s,suf);
	reverse(suf+1,suf+1+n);
	reverse(s+1,s+1+n);
	for(int i=1;i<=n;++i)
		suf[i]=i-suf[i]+1;
	ST(suf,n);
	for(int i=1;i<=n;++i) {
		if(s[i]=='p') {
			int L=i,R=pref[i];	
			while(L!=R) {	
				int Mid=(L+R+1)>>1;
				if(rgmn(Mid,R)>i)
					R=Mid-1;
				else
					L=Mid;
			}
			chkmx(Ans,L-i+1);
		}
	}
	os<<Ans<<'\n';
	return 0;
}

BZOJ 4386 Wycieczki

发表于 2017-03-09 | 更新于 2018-06-17

Link

Solution

为什么大家都一看这道题就是矩阵乘法。。为什么我就从来没听说过。。不过用矩阵乘法的求法是很好理解的吧如果边权为 $1$ ，那就给邻接矩阵的 $a[0][u]$ 赋值为 $1$ ，表示以 $u$ 为终点，走 $0$ 步，有一种路径。矩阵乘一下相当于走了一步，可以看一下矩阵乘法的式子，就是统计方案的DP。这样的话，二分需要走多少步，然后矩阵快速幂，用方案数目跟 $K$ 比较，最后可以得到答案。然而会T。这样的话，就可以用类似倍增LCA的做法，处理出邻接矩阵的 $2$ 的 $k$ 次方，然后从大到小试乘，如果可以的话就加入答案。边权不为 $1$ ，那就把每个点拆成三个，表示边权为 $1,2,3$ 的时候所到的点的分身。因为拆了点，本来有些点是不会成为路径的终点的却可以成为路径的终点，这种方案不能算进去。于是就在矩阵上乘上这个点的出度，相当于矩阵里是路径的倒数第二个点的方案数目，乘上一个出度才是完整的路径。所以条件需要是 $< K$ ，最后再 $Ans++$

另外

本题需要卡常数尽量减少运算+有理有据的底层优化

Tips

矩阵乘法求路径数目？感觉很喵的样子

Code

#include "lucida"

const int MAXN=40+11,MAXP=120+11,MAXLOG=63+5;
int64 INF;
int64 add(int64 x,int64 y) {
	return x+y<INF?x+y:INF;
}
int64 mul(int64 x,int64 y) {
	return (x==0) || (y==0) || (x<INF/y)?x*y:INF;
}
struct Square {
	int64 a[MAXP][MAXP];
	int n;
	Square(){}
	Square(int n):n(n) {
		memset(a,0,sizeof(a));
	}
	int64 *operator [](int x) {
		return a[x];
	}
	friend Square operator *(Square &a,Square &b) {
		assert(a.n==b.n);
		static Square res;
		int n=a.n;
		new (&res) Square(n);
		for(int i=0;i<=n;++i)
			for(int k=0;k<=n;++k)
				if(a[i][k]) {
					bool inf=a[i][k]==INF;
					for(int j=0;j<=n;++j)
						if(b[k][j]) {
							if((!inf) && b[k][j]!=INF)
								res[i][j]=add(res[i][j],mul(a[i][k],b[k][j]));
							else
								res[i][j]=INF;
							}
				}
		res.n=n;
		return res;
	}
	Square &operator *=(Square &b) {
		return *this=*this*b;
	}
}f[MAXLOG];
int id[MAXN][3],noc,oud[MAXP];
int64 Count(Square &tran) {
	int64 temp=0;
	for(int i=1;i<=noc;++i) { 
		temp=add(temp,mul(oud[i],tran[0][i]));
	}
	return temp;
}
int main() {
//	freopen("input","r",stdin);
	int n,m;int64 K;
	is>>n>>m>>K;
	INF=K*3;
	new (&f[0]) Square(n*3);
	for(int i=1;i<=n;++i) { 
		for(int d=0;d<=2;++d)
			id[i][d]=++noc;
		f[0][0][id[i][0]]=f[0][id[i][0]][id[i][1]]=f[0][id[i][1]][id[i][2]]=1;
	}
	f[0][0][0]=1;
	for(int i=1;i<=m;++i) {
		int u,v,c;
		is>>u>>v>>c;
		oud[id[u][c-1]]++;
		f[0][id[u][c-1]][id[v][0]]++;
	}
	int log2=0;
	while((1ll<<(log2+1))<=INF)
		log2++;
	for(int i=1;i<=log2;++i)
		f[i]=f[i-1]*f[i-1];
	int64 Ans=0;
	Square cur(n*3),temp;
	cur[0][0]=1;
	for(int lg=log2;~lg;--lg) {
		temp=cur*f[lg];
		if(Count(temp)<K) {
			Ans|=(1ll<<lg);
			cur=temp;
		}
	}
	++Ans;
	os<<(Ans<=INF?Ans:-1)<<'\n';
	return 0;
}

BZOJ 4382 Podział naszyjnika

发表于 2017-03-09 | 更新于 2018-06-18

Link

看到题，转化了一番，搞出了一个类似"选出不与别的边相交的边"之类的东西。。然后感觉非常复杂不会做其实正解的思路也差不多，只是没有刻意去套那么鬼畜的模型。。

Solution

对于每种颜色，断点只能在相邻的两个珠子之间。如果两条边能满足对于每种颜色，都在这种颜色相邻同一对珠子之间，就可以取。所以！对每种颜色，把相邻的两个珠子中间的片段都编上号。这样，如果两条边的每种颜色的编号都相同，就可以取。这一步用哈希实现。这样，对于一段哈希值相同的点，用乘法原理算方案数，用双指针算最优解。

Tips

坑点如果在算哈希的时候碰上了每种颜色在链上的第一个珠子，需要把 $1..first,last..n$ 都标上同一个号。双指针的时候，右指针必须在解开始变差之前停下，否则可能影响左指针移动之后的计算。 so 要格外小心拆环的边界情况双指针要如上地写 and 如果做题的时候套的模型太鬼畜导致不会处理，不一定是想法错了。。可以回归本质，用正常一些的模型试试

Code

#include "lucida"

typedef unsigned long long qword;
using std::partial_sum;
using std::pair;
using std::make_pair;
using std::sort;

const int MAXN=1000000+11,MAXM=MAXN;
int main() {
//	freopen("input","r",stdin);
	static int pre[MAXN],c[MAXN],last[MAXM];
	static qword hcode[MAXN];
	static pair<qword,int> hi[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i) {
		is>>c[i];
		pre[i]=last[c[i]];
		last[c[i]]=i;
	}
	qword BASE=9999929,POW=1;
	//n--[n th]--1--[1 st]--2--[2 nd]--
	for(int col=1;col<=m;POW*=BASE,++col) {
		qword HASH=POW;
		for(int i=last[col];i;HASH+=POW,i=pre[i]) {
			//当前处理的边的区间是[pre[i],i)
			if(pre[i]) {
				hcode[pre[i]]+=HASH;
				hcode[i]-=HASH;
			} else {
				hcode[last[col]]+=HASH;
				hcode[1]+=HASH;
				hcode[i]-=HASH;
			}
		}
	}
	partial_sum(hcode+1,hcode+1+n,hcode+1);
	for(int i=1;i<=n;++i)
		hi[i]=make_pair(hcode[i],i);
	sort(hi+1,hi+1+n);
	qword Ans=0;
	int mind=n;
	#define dist(i,j) ((i)<=(j)?(j)-(i):(n-((i)-(j))))
	#define calc(i,j) (abs(dist((i),(j))-dist((j),(i))))
	for(int l=1,r=l;r<=n;l=r=r+1) {
		while(hi[l].first==hi[r+1].first) 
			r++;
		Ans+=1ULL*(r-l+1)*(r-l)/2;
		for(int i=l,j=i+1;i+1<=r;++i) {
			j=(i==j)?i+1:j;
			int diff=calc(hi[i].second,hi[j].second);
			chkmn(mind,diff);
			while(j+1<=r && chkmn(diff,calc(hi[i].second,hi[j+1].second))) {
				chkmn(mind,diff);
				j++;
			}
		}
	}
	os<<Ans<<' '<<mind<<'\n';
	return 0;
}

uoj126 快餐店

发表于 2017-03-09 | 更新于 2018-06-18

Link

Solution

如果在树上的话，答案显然就是树的直径 $\div 2$ 。然后发现这道题的距离可以是实数，似乎不好设计状态DP，于是思考如何向树上转化。基环树，处理的最常见的思路也就是拆环了(一个LCT好题)。那么把这个图的环枚举边拆掉，是不是直接求直径就行了？然后观察一下，发现不管把点放在哪里，环上一定有一条边是不会被经过的。所以只要枚举断点拆环，得到的直径的最小值 $\div 2$ 就是答案了。至于直径，一定是来源于环上挂着的子树的直径，或者是一个子树的一条链，经过环走到另一个子树。第一种可以预处理至于第二种，感觉做法挺有意思的。设当前断点为 $p$ ，其它所有点 $u$ 到 $p$ 的距离为 $d[u]$ ，每个子树中的最长链为 $ch[u]$ ，那么这个答案就是把变量分离开，发现就是个 $max\{d[v]+ch[v]+(-d[u]+ch[u])\}$ 只需要维护 $d[u]+ch[u]$ 的最大值，和 $-d[u]+ch[u]$ 的最小值即可！所以建立两个线段树分别维护着两个量，那么当枚举的断边改变的时候该如何实时修改线段树的信息呢？发现，如果硬是要维护到断点的距离的话，那么 $d[]$ 就会这样变化： $0,d[2],d[3],d[4]..\rightarrow d[n]+dist(n,1),0,d[3]-d[2],d[4]-d[2]\rightarrow...$ 似乎比较麻烦的样子？然而本来这个 $d[]$ 就是个前缀和，需要的只是它两项的差值。只要维护相对大小正确就行了。于是修改断边，只需要修改一个点的值就可以，直接把它的 $d$ 设置为它的前驱 $pred$ 的 $d[pred]+dist(pred,this)$ 即可。。虽然比较显然，但我还是感觉比较有意思。。

Tips

维护前缀和数组，可以只需要维护值的差正确基环树先想拆环

Code

//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long int64;
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::pair;
using std::partial_sum;
using std::swap;
using std::make_pair;
using std::max;

const int MAXN=1e5+11;
struct Info
{
	pair<int64,int> fmx,smx;
	Info(){fmx=smx=make_pair(LLONG_MIN,-1);}
	Info(pair<int64,int> mx):fmx(mx),smx(LLONG_MIN,-1){}
	Info(pair<int64,int> fmx,pair<int64,int> smx):fmx(fmx),smx(smx){}
	friend Info operator +(Info a,Info b)
	{
		if(a.fmx<b.fmx) swap(a,b);
		return Info(a.fmx,max(a.smx,b.fmx));
	}
};
namespace _SegTree_
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		Node *son[2];
		Info mx;
		Node();
		void *operator new(size_t);
		void Up();
	}*Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool,*null=new Node;
	void *Node::operator new(size_t){return Me++;}
	Node::Node(){son[0]=son[1]=null;}
	void Node::Up(){mx=son[0]->mx+son[1]->mx;}
	struct SegTree
	{
		int L,R;
		Node *root;
		SegTree(int L,int R):L(L),R(R),root(null){}
		void Edit(Node *&,int,int,int,pair<int64,int>);
		void Insert(int pos,pair<int64,int> mark){Edit(root,L,R,pos,mark);}
	};
	void SegTree::Edit(Node *&pos,int L,int R,int goal,pair<int64,int> mark)
	{
		if(pos==null)
			pos=new Node;
		if(L==R)
			pos->mx=mark;
		else
		{
			int Mid=(L+R)>>1;
			if(goal<=Mid)
				Edit(pos->son[0],L,Mid,goal,mark);
			else
				Edit(pos->son[1],Mid+1,R,goal,mark);
			pos->Up();
		}
	}
}using _SegTree_::SegTree;
struct Edge
{
	int to,v;Edge* pre,*rev;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre),rev(0){}
}*Edge_Me=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Edge_Pool=Edge_Me,*id[MAXN];
int n;
void Adde(int f,int t,int v)
{
	id[f]=new(Edge_Me++) Edge(t,v,id[f]);
	id[t]=new(Edge_Me++) Edge(f,v,id[t]);
	id[f]->rev=id[t];id[t]->rev=id[f];
}
struct CirclePoint
{
	int id;
	int64 longch;
}circle[MAXN];
int cc,ref[MAXN];
int64 pref[MAXN],len[MAXN];
bool DFS(int pos,int fa)
{
	static int pred[MAXN]={0,-1};
	for(Edge *e=id[pos];e;e=e->pre)
	{
		int u=e->to;
		if(u==fa) continue;
		if(pred[u])
		{
			while(pos!=pred[u])
			{
				circle[++cc].id=pos;
				pos=pred[pos];
			}
			return 1;
		}
		pred[u]=pos;
		if(DFS(u,pos)) return 1;
	}
	return 0;
}
bool ban[MAXN];
int BFS(int pos,int64 *dist)
{
	static int us[MAXN],ut,Q[MAXN],he,ta;
	dist[pos]=0;
	us[Q[he=ta=1]=pos]=++ut;
	int64 mxd=LLONG_MIN;int res=0;
	while(he<=ta)
	{
		int cur=Q[he++];
		for(Edge *e=id[cur];e;e=e->pre)
		{
			int u=e->to;
			if(us[u]==ut || ban[u]) continue;
			dist[u]=dist[cur]+e->v;//dist[pos]..
			Q[++ta]=u;us[u]=ut;
			if(chkmx(mxd,dist[u])) res=u;
		}
	}
	return res;
}
int64 Prep()
{
	DFS(1,0);
	static int64 dist[MAXN];
	for(int i=1;i<=cc;++i)
	{
		int pos=circle[i].id;
		ref[pos]=i;
		ban[pos]=1;
	}
	int64 res=LLONG_MIN;
	for(int i=1;i<=cc;++i) 
	{
		int pos=circle[i].id;
		int p=BFS(pos,dist);
		circle[i].longch=dist[p];
		ban[pos]=0;
		int f=BFS(p,dist);
		ban[pos]=1;
		chkmx(res,dist[f]);
	}
	return res;
}
int main()
{
	get(n);
	for(int i=1;i<=n;++i)
	{
		int a,b,l;get(a),get(b),get(l);
		Adde(a,b,l);
	}
	int64 Temp=Prep();
	#define pred(x,C) (x!=1?x-1:C)
	#define succ(x,C) (x!=C?x+1:1)
	for(Edge *e=Edge_Pool;e!=Edge_Me;++e)
	{
		int t=e->to,f=e->rev->to;
		if(ref[f] && ref[t] && succ(ref[f],cc)==ref[t])
			len[ref[t]]=e->v;
	}
	partial_sum(len+2,len+1+cc,pref+2);
	SegTree seg1(1,cc),seg2(1,cc);
	#define Updata(i) seg1.Insert(i,make_pair(circle[i].longch+pref[i],i)),seg2.Insert(i,make_pair(circle[i].longch-pref[i],i))
	for(int i=1;i<=cc;++i)
		Updata(i);
	int64 Ans=LLONG_MAX;
	for(int i=1;i<=cc;++i)
	{
		Info mx1=seg1.root->mx,mx2=seg2.root->mx;
		chkmn(Ans,mx1.fmx.second==mx2.fmx.second?max(mx1.fmx.first+mx2.smx.first,mx1.smx.first+mx2.fmx.first):mx1.fmx.first+mx2.fmx.first);
		pref[i]=pref[pred(i,cc)]+len[i];
		Updata(i);
	}
	chkmx(Ans,Temp);
	printf("%.1lf\n",(double)Ans/2);
	return 0;
}

BZOJ 4377 Kurs szybkiego czytania

发表于 2017-03-09 | 更新于 2018-06-18

Link

一看到这个式子，可以找循环节啊！再一看互质……2333

Solution

一个等差数列膜掉一个数字之后再和另一个数字比较假设小串出现在了大串的位置 $p|p\in[1,n]$ ，那么有 $...$ 每个条件都可以转化为一个不等式，发现每个不等式可以看成对 $a(p-1)$ 的限制，也就是对在大串中匹配上的第一个位置的数值的限制。因为 $n,a$ 互质，所以与每个位置 $p$ 是一一对应的。那就要解得到的这一堆不等式，找到满足要求的值的个数。每个不等式形如可能在膜意义下移项之后 $l>r$ ，那也无所谓，只需要添加两个不等式即可。因为的值可以看成一个环，每个不等式限制了必须取环的一段。显然， $l>r$ 添加两个不等式是符合意义的。发现区间交集并不好求，那就转化一下，求不合法位置的并集，用总个数减去即可。

Tips

区间操作不好做，考虑补集转化膜的不等关系可以类比在环上区间的限制

Code

#include "lucida"
using std::sort;
const int MAXN=1e9+11,MAXM=1e6+11;
struct Limit {
	int l,r;
	Limit(){}
	Limit(int p):l(p),r(p){}
	Limit(int l,int r):l(l),r(r){}
	bool operator <(const Limit &a)const {
		return l<a.l || (l==a.l && r<a.r);
	}
}lim[(MAXM<<1)+MAXM];int limc;
int Union() {
	sort(lim+1,lim+1+limc);
	int l=lim[1].l,r=lim[1].r,res=0;
	for(int i=2;i<=limc;++i) {
		if(lim[i].l>r) {
			res+=r-l+1;
			l=lim[i].l;
			r=lim[i].r;
		} else
			chkmx(r,lim[i].r);
	}
	res+=r-l+1;
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,a,b,p,m;
	is>>n>>a>>b>>p>>m;
	for(int i=1;i<=m;++i) {
		char digit;is>>digit;
		int64 l,r,d=(int64)a*(i-1)%n;
		if(digit=='1') {
			l=-d;
			r=p-1-d;
		} else {
			l=p-d;
			r=n-1-d;
		}
		((l%=n)+=n)%=n;((r%=n)+=n)%=n;
		if(l<=r) 
			new(&lim[++limc]) Limit(l,r);
		else {
			new(&lim[++limc]) Limit(l,n-1);
			new(&lim[++limc]) Limit(0,r);
		}
	}
	for(int i=n-m+1;i<n;++i)
		new(&lim[++limc]) Limit(((int64)a*i%n+b)%n);
	int Ans=n-Union();
	os<<Ans<<'\n';
	return 0;
}

BZOJ 3524 Couriers

发表于 2017-03-09 | 更新于 2018-06-18

Link

Solution

我想出的优秀做法：外层区间线段树，内层值域线段树，查询的时候线段树合并，在合并出的线段树上查询最大值与 $\dfrac {r-l+1}2$ 比较想出来之后，一看Solved：700+？POI的题有这么多人做？有那么好写吗？当我看到正解之后惊呆了一切尽在代码中

Tips

给了这样的限制也许就可以得到有用的性质啊。。不分析限制直接暴力想对于所有的范围不可取啊。。

Code

#include "lucida"
const int MAXN=500000+11;
namespace _ChmTree_ {
	const int SIZE=1e7;
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node() {
			son[0]=son[1]=null;
			cnt=0;
		}
		Node(Node* old) {
			*this=*old;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
		void *operator new(size_t) {
			static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
			return Me++;
		}
	}*_null=null=new Node;
	struct ChmTree {
	//private:
		Node *root[MAXN];
		int minv,maxv,rc;
		int Access(Node *rl,Node *rr,int L,int R,int c) {
			if(L==R)
				return rr->cnt-rl->cnt>=c?L:0;
			else {
				int Mid=(L+R)>>1;
				if(rr->son[0]->cnt-rl->son[0]->cnt>=c)
					return Access(rl->son[0],rr->son[0],L,Mid,c);
				else
					return Access(rl->son[1],rr->son[1],Mid+1,R,c);
			}
		}
		void Edit(Node *&pos,int L,int R,int goal) {
			pos=new Node(pos);
			if(L==R)
				pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal);
				else
					Edit(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
	//public:
		ChmTree(int minv,int maxv):minv(minv),maxv(maxv) {
			root[rc=0]=null->son[0]=null->son[1]=null;
		}
		void Insert(int x) {
			++rc;
			Edit(root[rc]=root[rc-1],minv,maxv,x);
		}
		int Query(int l,int r,int k) {
			return Access(root[l-1],root[r],minv,maxv,k);
		}
	};
}using _ChmTree_::ChmTree;
int main() {
//	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	ChmTree seg(1,n);
	for(int i=1;i<=n;++i) {
		int x;is>>x;
		seg.Insert(x);
	}
	for(int i=1;i<=m;++i) {
		int l,r;
		is>>l>>r;
		os<<seg.Query(l,r,(r-l+1)/2+1)<<'\n';
	}
	return 0;
}

BZOJ 4345 Korale

发表于 2017-03-09 | 更新于 2018-06-18

Link

Solution

K非常大。。由这个条件

先按权值从小到大排序，对于权值相同的，根据所用珠子集合的标号的字典序从小到大排序

可以启发得到一种想法：先找到第K大的权值，再构造相应字典序的解。所以第一步需要找到第K大的权值，常用的思路是把选出的数字集合按照一些性质分类、扩展，用一个堆来维护(K个串)。对于这道题来说，有这样一种构造方法：首先把整个序列排序堆的每个节点维护一个数对 $< a,b >$ ，表示和为 $a$ ，编号的最大值为 $b$ 。扩展的时候，扩展出 $< a+v[b+1],b+1 >$ 和 $< a-v[b]+v[b+1],b+1 >$ ~~为什么这样就能不重不漏地取到前 $K$ 大的权值和呢？~~为什么不能呢。。不会严格证明，但是可以感受到这样确实是可以不重不漏地取到的。。一个集合，根据倒数第二个点取或者没取，只有一个前驱；不停地递归下去，肯定会回到状态 $< v[1],1 >$ 在计算第 $K$ 大的权值和 $sum$ 的同时，还要记录前 $K$ 大的权值和中有多少个和第 $K$ 大的权值和相同，设为 $c$ 。那么就需要构造出权值和为 $sum$ ，字典序第 $c$ 大的集合。让我万万想不到的是，构造的方法就是深搜。。每次找到最靠左的且小于当前总和的数字，减掉之后搜下去。。想不明白复杂度？

Tips

如果能像这样先把权值搞掉只搜字典序，就大大简化了问题。。字典序是有可能需要搜的。。。

Code

#include "lucida"
using std::pair;
using std::greater;
using std::vector;
using std::sort;
using std::make_pair;
using std::priority_queue;
//using std::min;
#define min(x,y) ( (x)<(y)?(x):(y) )
typedef pair<int64,int> HeapNode;
const int MAXN=1000000+11,MAXK=1000000+11,INF=1e9+1e5,LOG=23;
int n;
struct SparseTable {
	int f[MAXN][LOG],log_2[MAXN];
	SparseTable(){}
	SparseTable(int*,int);
	int operator ()(int,int);
}RMQ;
SparseTable::SparseTable(int *a,int n) {
	log_2[0]=-1;
	for(int i=1;i<=n;++i) {
		f[i][0]=a[i];
		log_2[i]=log_2[i>>1]+1;
	}
	for(int j=1,endj=log_2[n];j<=endj;++j) {
		for(int i=1,endi=n-(1<<j)+1;i<=endi;++i) {
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int SparseTable::operator ()(int l,int r) {
	if(l>r) return -INF;
	int lg=log_2[r-l+1];
	return min(f[l][lg],f[r-(1<<lg)+1][lg]);
}
int Leftmost(int lbd,int64 x) {
	//找lbd右边最靠左的<=x的数字的位置
	int L=lbd,R=n+1;
	while(L!=R) {
		int Mid=(L+R)>>1;
		if(RMQ(lbd,Mid)<=x) {
			R=Mid;
		} else {
			L=Mid+1;
		}
	}
	return L==n+1?-1:L;
}
int s[MAXN],a[MAXN],res[MAXN],rc,stack[MAXN],top;
bool DFS(int l,int64 rem,int& rep) {
	
	//os<<l<<' '<<rem<<'\n';

	if(rem==0) {
		if(--rep==0) {
			while(top)
				res[++rc]=stack[top--];
			return 1;
		}
		else 
			return 0;
	}
	else {
		for(;l<=n;++l) {
			//l只需要枚举关键点！
			l=Leftmost(l,rem);
			if(l==-1)
				break;
			else {
				stack[++top]=l;
				if(DFS(l+1,rem-s[l],rep))
					return 1;
				top--;
			}
		}
	}
	return 0;
}
int main() {
//	freopen("input","r",stdin);
	int K;is>>n>>K;
	K--;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		s[i]=a[i];
	}
	sort(a+1,a+1+n);
	//从n个数字选出若干个构成一个集合
	//集合按照1.元素值之和 2.元素标号字典序 比较大小
	//求第K大的集合
	priority_queue<HeapNode,vector<HeapNode>,greater<HeapNode> > Q;
	int64 Ans=0;int rep=0;
	Q.push(make_pair(a[1],1));
	while(K--) {
		HeapNode cur=Q.top();Q.pop();
		if(chkmx(Ans,cur.first)) {
			rep=1;
		} else {
			rep++;
		}
		if(cur.second!=n) {
			int p=cur.second,s=cur.second+1;
			Q.push(make_pair(cur.first+a[s],s));
			Q.push(make_pair(cur.first-a[p]+a[s],s));
		}
	}
	os<<Ans<<'\n';
	new(&RMQ) SparseTable(s,n); 
	DFS(1,Ans,rep);
	for(int i=rc;i>=1;--i)
		os<<res[i]<<' ';//(i==1?'\n':' ');
	return 0;
}

Lucida

It's been a while.

222 日志

127 标签