BZOJ 3188 Upit

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

Link

Solution

裸，练模板。。

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define getc() getchar()
#define putc(x) putchar(x)
#define getl(x) scanf("%lld",&x)
#define putl(x) printf("%lld",x)
#define foreach(it,x) for(typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())

typedef long long ll;

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::max;
using std::min;

const int INF=0x1f1f1f1f,MAXN=100000+11;

struct Sequence
{
	ll a,d;
	Sequence(ll a=0,ll d=0):a(a),d(d){}
	ll operator [](ll x){return a+d*(x-1);}
	ll operator ()(ll l,ll r){return ((a-d)*2+(l+r)*d)*(r-l+1)>>1;}
};
namespace Splay
{
	const int SIZE=MAXN<<1;
	const ll NOCOV=LLONG_MAX;
	struct Node
	{
		Node *son[2],*fa;
		Sequence add;
		ll cov,v,isum;
		int sz;
		int kind(){return fa->son[1]==this;}
		bool isrt(){return fa->son[0]!=this && fa->son[1]!=this;}
		Node()
		{
			sz=0;cov=NOCOV;
			v=isum=0;
			fa=son[0]=son[1]=0;
			add.a=add.d=0;
		}
		void Add(Sequence s)
		{
			if(!sz) return;
			add.a+=s.a;
			add.d+=s.d;
			isum+=s(1,sz);
			v+=s[son[0]->sz+1];
		}
		void Cover(ll cv)
		{
			if(!sz) return;
			cov=v=cv;
			isum=cv*sz;
			add.a=add.d=0;
		}
		void up()
		{
			sz=son[0]->sz+son[1]->sz+1;
			isum=son[0]->isum+son[1]->isum+v;
		}
		void down()
		{
			if(cov!=NOCOV)
			{
				son[0]->Cover(cov);
				son[1]->Cover(cov);
				cov=NOCOV;
			}
			if(add.a|add.d)
			{
				son[0]->Add(Sequence(add.a,add.d));
				son[1]->Add(Sequence(add[son[0]->sz+2],add.d));
				add.a=add.d=0;
			}
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null;
	Node *newNode(ll v)
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=cur->fa=null;
		cur->cov=NOCOV;cur->v=cur->isum=v;
		cur->sz=1;
		cur->add.a=cur->add.d=0;
		return cur;
	}
	void Append(ll x)
	{
		static Node *cur;cur=newNode(x);
		cur->son[0]=root;root->fa=cur;
		root=cur;root->up();
	}
	void Trans(Node *pos)
	{
		static Node *f,*grf;
		static int d;
		f=pos->fa,grf=f->fa;
		f->down(),pos->down();
		d=pos->kind();
		if(!f->isrt())
			grf->son[f->kind()]=pos;
		pos->fa=grf;
		f->son[d]=pos->son[!d],pos->son[!d]->fa=f;
		pos->son[!d]=f,f->fa=pos;
		f->up(),pos->up();
	}
	void SplayTo(Node *pos,Node *goal=null)
	{
		static Node *f;
		while((f=pos->fa)!=goal)
		{
			if(f->fa!=goal)
				Trans(pos->kind()==f->kind()?f:pos);
			Trans(pos);
		}
		if(goal==null)
			root=pos;
	}
	Node *Kth(int K)
	{
		static Node *pos;
		static int sz;
		++K;
		pos=root;
		while(pos!=null)
		{
			if((sz=pos->son[0]->sz+1)==K)
				return pos;
			else if(K<sz)
				pos=pos->son[0];
			else
				K-=sz,pos=pos->son[1];
		}
		return pos==null?0:(SplayTo(pos),pos);
	}
	Node *Split(int l,int r)
	{
		static Node *p1,*p2;
		p1=Kth(l-1),p2=Kth(r+1);
		SplayTo(p1,null);
		SplayTo(p2,p1);
		return p2->son[0];
	}
	void Insert(int pos,ll x)
	{
		static Node *cur,*p1,*p2;
		cur=newNode(x);
		p1=Kth(pos-1),p2=Kth(pos);
		SplayTo(p1,null);
		SplayTo(p2,p1);
		p2->son[0]=cur;cur->fa=p2;
		SplayTo(cur,null);
	}
}
int main()
{
	freopen("input","r",stdin);
	int n,m;get(n),get(m);
	Splay::Append(0);
	for(int i=1;i<=n;++i)
	{
		ll x;getl(x);
		Splay::Append(x);
	}
	Splay::Append(0);
	for(int i=1;i<=m;++i)
	{
		int opt,a,b,c;ll x;
		Splay::Node *rt;
		get(opt);
		switch(opt)
		{
			case 1:
				get(a),get(b),getl(x);
				rt=Splay::Split(a,b);
				rt->Cover(x);
				break;
			case 2:
				get(a),get(b),getl(x);
				rt=Splay::Split(a,b);
				rt->Add(Sequence(x,x));
				break;
			case 3:
				get(c),getl(x);
				Splay::Insert(c,x);
				break;
			case 4:
				get(a),get(b);
				rt=Splay::Split(a,b);
				putl(rt->isum),putc('\n');
				break;
		}
	}
	return 0;
}
/* AC Record(Bugs)
RE null down
RE size of arr to small
*/

CF414E Mashmokh's Designed Problem

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

Link

神题。。（哦应该是因为我太弱了。。）

Solution

一直不明白DFS序到底是怎么定义的那种记录每个点第一次访问的位置的，总共 $n$ 个点，有人叫它DFS序还有那种记录DFS的路径的，总共 $2n-1$ 个点，有人也叫它DFS序。。于是各种题解随便一混用就能把我转很久(应该是我太弱了) 好吧，这个用的是第二种DFS序。。那我叫它multiDFS序好了。首先求出树的multiDFS序 $=\mathcal{S}$ 那么求点对距离就是求出LCA然后计算，即为区间最小值然后求最后一个深度为 $dep$ 的节点，只要在序列上二分然后判存在性就行了，判存在的条件是。不要漏掉第二个条件！！ 要求把一棵子树移动到它的第 $k$ 个祖先上，首先这个第 $k$ 个祖先也可以在序列上二分得到，而移动在 $\mathcal{S}$ 中就对应区间的移动。转化为的基本操作。这样两个二分就转化为在上走。 But。。

Tips

关于的用法

says ydc

的区间操作一直让我感到云里雾里。普通的，一般是自顶向下操作(如维修数列)，需要一个来在中定位。这样，就可以一路下去，没有问题。但是在一些直接定位到节点的应用中，比如，它祖先的标记就访问不到了。学习的时候，看到Po姐的做法是一直递归到根节点，然后一路下放标记。因为也没学会势能分析，也不知道这样复杂度是否有保障，但也就一直这样写了。在Summer Camp上问了下gty大神，他表示他一直只是在的时候下放一下标记，从来没出现问题。问起关于祖先的标记，他表示没有考虑过。向gty大神要来代码，最后也没有完全弄明白。那天晚上跑到省队的实验室去问swh（之前他学的也是类似的写法，只是写hzwer的代码，用手工栈），他说因为操作以后会把节点到根。当时觉得挺有道理的样子，但也没再深究。写这道题，又用到了直接定位节点需要处理祖先标记的问题。思考了以下，发现只要按照ydc所讲的，在一个点停下就上去就行了。在中，需要把父节点的标记下传，然后把当前节点的标记下传，遵循的原则就是：在出子树之前下传防止多传给其它子树，在进入子树之前下传让防止漏传给其它子树。 对于，读取之前本来是可以不需要到根的。(修改也可以在之后) 但现在的话就对读写都一视同仁，都到根，就解决了标记的问题，也让思维更清晰一些。（特殊情况：提取区间之后对区间进行修改，不能到跟节点，那就修改之后再）切记对节点进行修改之后要更新区间信息！

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define getc() getchar()
#define putc(x) putchar(x)
#define puts(x) printf("%s",x)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())
#define foreach(it,x) for(iter(x) it=(x).begin();it!=(x).end();++it)
typedef long long ll;
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
using std::swap;
using std::pair;
using std::make_pair;
using std::vector;

const int INF=0x1f1f1f1f,MAXN=1e5+11;
namespace Splay
{
	const int SIZE=MAXN<<2;
	typedef pair<int,int> Data;
	struct Node
	{
		Node *son[2],*fa;
		int add,ssz,isz;
		Data self,imin,imax; 
		Node()
		{
			imin=make_pair(INF,0);
			imax=make_pair(-INF,0);
			son[0]=son[1]=fa=0;
			add=isz=ssz=0;
		}
		bool kind(){return fa->son[1]==this;}
		bool isRoot(){return fa->son[0]!=this && fa->son[1]!=this;}
		void Add(int);
		void up();
		void down()
		{
			if(add)
			{
				son[0]->Add(add);
				son[1]->Add(add);
				add=0;
			}
		}
		void uptoroot()
		{
			up();
			if(!isRoot()) fa->uptoroot();
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node,*root=null,*lnull,*rnull;
	void Node::Add(int v)
	{
		if(this!=null)
		{
			add+=v;
			self.first+=v;
			imin.first+=v;
			imax.first+=v;
		}
	}
	void Node::up()
	{
		assert(this!=null);
		if(this==lnull || this==rnull)
			imin=make_pair(INF,0),imax=make_pair(-INF,0);
		else
			imin=imax=self;
		chkmn(imin,min(son[0]->imin,son[1]->imin));
		chkmx(imax,max(son[0]->imax,son[1]->imax));
		isz=ssz+son[0]->isz+son[1]->isz;
	}
	Node *newNode(Data v)
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=cur->fa=null;
		cur->imin=cur->imax=cur->self=v;
		cur->add=0;cur->isz=cur->ssz=1;
		return cur;
	}
	Node *Append(Node *&pos,Node *nw)
	{
		nw->son[0]=pos;
		if(pos!=null)
			pos->fa=nw;
		pos=nw;pos->up();
		return pos;
	}
	
	void Trans(Node *pos)
	{
		static Node *f,*grf;
		static int d;
		f=pos->fa,grf=f->fa;
		d=pos->kind();
		
		f->down();//here
		pos->down();

		if(!f->isRoot())
			grf->son[f->kind()]=pos;
		pos->fa=grf;
		f->son[d]=pos->son[!d];pos->son[!d]->fa=f;
		pos->son[!d]=f;f->fa=pos;
		f->up();
		pos->up();
		assert(pos->son[0] && pos->son[1] && f->son[0] && f->son[1]);
	}
	void SplayTo(Node *pos,Node *goal=0)
	{
		bool flag=0;
		if(goal==0)
			goal=null,flag=1;
		while(pos->fa!=goal)
		{
			Node *f=pos->fa;
			if(f->fa!=goal)
				Trans(pos->kind()==f->kind()?f:pos);
			Trans(pos);
		}
		if(goal==null && !flag)
			root=pos;
	}
	Node *Adjace(Node *pos,int dir=0)
	{
		SplayTo(pos,null);
		pos=pos->son[dir];
		while(pos->son[!dir]!=null)	
			pos=pos->son[!dir];
		SplayTo(pos,null);
		return pos;
	}
	Node *Split(Node *p1,Node *p2)
	{
		p1=Adjace(p1,0);
		p2=Adjace(p2,1);
		SplayTo(p1,null);
		SplayTo(p2,p1);
		return p2->son[0];
	}
	int Rank(Node *pos)
	{
		SplayTo(pos,null);
		return pos->son[0]->isz;
	}
}using namespace Splay;
vector<int> son[MAXN];
struct SubTree
{
	Splay::Node *lbound,*rbound,*trfa;
}sub[MAXN];
void DFS(int pos,int dep,Splay::Node* &s)
{
	sub[pos].lbound=Append(s,newNode(make_pair(dep,pos)));
	foreach(it,son[pos])
	{
		Append(s,newNode(make_pair(dep,pos)));
		sub[*it].trfa=s;
		DFS(*it,dep+1,s);
	}
	sub[pos].rbound=Append(s,newNode(make_pair(dep,pos)));
}
int FindPar(int p,int acn)
{
	SplayTo(sub[p].lbound,null);
	Splay::Node *pos=root->son[0];
	int dep=root->self.first-acn;
	for(;;)
	{
		pos->down();
		if(pos->son[1]->imin.first<=dep && dep<=pos->son[1]->imax.first)
			pos=pos->son[1];
		else if(pos->self.first==dep)
			return pos->self.second;
		else
			pos=pos->son[0];
	}
}
void Move(int pos,int acn)
{
	int par=FindPar(pos,acn);
	
	Splay::Node *rt=Split(sub[pos].trfa,sub[pos].rbound);
	rt->fa->son[0]=null,rt->fa->uptoroot();
	rt->fa=null;

	SplayTo(sub[pos].trfa);
	sub[pos].trfa->self.second=par;sub[pos].trfa->up();//..
	sub[pos].trfa->Add(1-acn);
	
	Splay::Node *last=Adjace(sub[par].rbound,0);
	SplayTo(last,null);
	SplayTo(sub[par].rbound,last);
	sub[par].rbound->son[0]=sub[pos].trfa;sub[par].rbound->uptoroot();
	sub[pos].trfa->fa=sub[par].rbound;
}
int Dist(int p1,int p2)
{
	if(Rank(sub[p1].lbound)>Rank(sub[p2].lbound))
		swap(p1,p2);//no judge swap
	Splay::Node* rt=Split(sub[p1].lbound,sub[p2].lbound);
	return sub[p1].lbound->self.first+sub[p2].lbound->self.first-2*rt->imin.first;
}
int DepLast(int dep)
{
	++dep;
	Splay::Node* pos=root;
	for(;;)
	{
		pos->down();
		if(pos->son[1]->imin.first<=dep && dep<=pos->son[1]->imax.first) 
			pos=pos->son[1];
		else if(pos->self.first==dep)
			return pos->self.second;
		else
			pos=pos->son[0];
	}
}
int main()
{
	freopen("input","r",stdin);
	int n,m;get(n),get(m);
	for(int i=1;i<=n;++i)
	{
		int sc;get(sc);
		for(int j=1;j<=sc;++j)
		{
			int s;get(s);
			son[i].push_back(s);
		}
	}
	root=lnull=newNode(make_pair(INF,INF));
	rnull=newNode(make_pair(INF,INF));;
	DFS(1,1,root);
	Append(root,rnull);
	for(int i=1;i<=m;++i)
	{
		int opt,v,u,h,k;
		get(opt);
		switch(opt)
		{
			case 1:get(v),get(u);put(Dist(v,u)),putc('\n');break;
			case 2:get(v),get(h);Move(v,h);break;
			case 3:get(k);put(DepLast(k)),putc('\n');break;
		}
	}
	return 0;
}

SRM 706 div 1

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

p1

Limak is a little bear. He is currently planning a walk on a rectangular grid. Each cell of the grid is either empty or it contains a single candy. Empty cells are denoted '.', cells with a candy are denoted '#'. Limak wants to go from the top-left corner to the bottom-right corner of the grid. Since he loves sweets, there should be a candy in each cell he visits, including the starting and the final cell. He can only move in the four cardinal directions. In other words, he can move from cell A directly to cell B if and only if A and B share a side. You are given the vector t: the current state of the grid. Limak's journey may be impossible on the current grid. Your task is to make it possible by moving as few candies as you can. Moving a candy means picking it up and placing it into any empty cell. Return the smallest number of candies that have to be moved in order to make Limak's journey possible. If there is no solution, return -1 instead.

Solution

好吧，又不会做了，棋盘上可以从左上到右下DP。然而这个是各个方向都能走的，所以好像可以求最短路？但也不会建图发现正解是按照走的步数划分阶段的这个很厉害啊，棋盘上的最优新解法get。还有一点，这个题拿哪些不需要管，只要走就行了，最后肯定能构造出一组可行解来

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define foreach(it,x) for(typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define iter(x) typeof((x).begin())
#define riter(x) typeof((x).rbegin())
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::vector;
using std::string;
const int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},MAXN=30;
struct MovingCandies
{
	int minMoved(vector<string> t)
	{
		static int f[MAXN][MAXN][MAXN<<1];
		int res=0;
		static char map[MAXN][MAXN];
		int n=t.size(),m=t[0].size(),cct=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
			{
				map[i][j]=t[i-1][j-1];
				if(map[i][j]=='#') ++cct;
			}
		if(cct<n+m-1) return -1;
		memset(f,31,sizeof(f));res=0x1f1f1f1f;
		f[1][1][0]=map[i][j]=='.';
		for(int st=1;st<=cct-1;++st)
		{
			for(int x=1;x<=n;++x)
				for(int y=1;y<=m;++y)
				{
					int cost=map[x][y]=='.';
					for(int d=0;d<4;++d)
					{
						int nx=x+dx[d],ny=y+dy[d];
						if(!(1<=nx && nx<=n && 1<=ny && ny<=m)) continue;
						chkmn(f[x][y][st],f[nx][ny][st-1]+cost);
					}
				}
			chkmn(res,f[n][m][st]);
		}	
		return res;
	}
};

SRM 706 div 2

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

p1

Bear Limak has three boxes arranged in a row. The first box currently contains a candies, the second one contains b candies, and the third one contains c candies. Limak thinks that the three boxes would look nice if they had the following two properties: Each box should contain at least one candy. The numbers of candies should form a strictly increasing sequence. In other words, the first box should contain fewer candies than the second box, and the second box should contain fewer candies than the third one. Limak can only modify the current content of the boxes in one way: he can eat some of the candies. You are given the ints a, b, and c. Compute and return the smallest possible number of candies Limak should eat in order to make his three boxes look nice. If he has no way to make his boxes look nice, return -1 instead.

Code

struct ThreeIncreasing
{
public:
	int minEaten(int a,int b,int c)
	{
		int res=0;
		if(b>=c) res+=b-c+1,b-=b-c+1;
		if(a>=b) res+=a-b+1,a-=a-b+1;
		if(a<1 || b<1) res=-1;
		return res;
	}
};

p2

Little Limak wants to show his parents that he's responsible and independent. He decided to move out and live on his own, at least for some time. While living alone, he has to eat every day. Living alone comes with some other expenses as well. More precisely, Limak will eat 1 fruit and spend x dollars each day he lives on his own. Currently Limak has f fruits and d dollars. Limak can buy more pieces of fruit in the local store. The store sells 1 fruit for p dollars, and Limak can purchase arbitrarily many pieces of fruit there. You are given the ints x, f, d, and p. Compute and return the largest possible number of days Limak can live on his own.

Code

typedef long long ll;
class SellingFruits
{
public:
	int maxDays(ll x,ll f,ll d,ll p)
	{
		int res;
		if(x!=0 && d/x<=f) res=d/x;
		else res=(d+p*f)/(x+p);
		return res;
	}
};

p3

The lotteries you know are probably quite boring. You just buy a lottery ticket with some numbers and then you hope that the organizers announce the same set of numbers. As you will discover below, the lottery in Bearland is way more fun! In the Bearland lottery, you win if you have a ticket that matches the goal string. The goal string is a string of length N chosen by the organizers. Each character of the string will be 'A', 'B', or 'C'. Additionally, it is guaranteed that the goal string will contain "ABC" as a subsequence. For example, "AABAC" and "BBABC" are two possible goal strings of length 5, but "CBAAA" is not a goal string. However, the lottery tickets do not contain any strings at all. Instead, each Bearland lottery ticket contains some sequence of N (not necessarily distinct) integers. You win the lottery if you can transform your sequence into the goal string. Transformation rules: Each element of the sequence should be replaced by a single character: 'A', 'B', or 'C'. All occurrences of the same number must be replaced by the same letter. For example, the sequence {5, 8, 5, 2} can be transformed into "ABAC" or "BABB" but not into "ABBB". Limak got a lottery ticket for his birthday. You are given the vector t: the sequence of the N numbers on the the ticket. Count the number of different goal strings for which Limak can win the lottery. Return that count modulo 10^9+7.

Solution

好吧这就不会做了，，太弱了，一开始还把题都看错了。。对一个数字序列，相同的数字替换成A,B,C中相同的字母，问有多少种方案可以让产生的字符串中含有子序列A...B...C。首先枚举三个不相同的a[i],a[j],a[k]，考虑钦定这三个分别为A,B,C对答案能产生的贡献。对于x..x..x..y.y...z...zz这种情况好说，只要确保当前枚举的x1,y1,z1是同类数字中的第一个，即x1之前没有x，x1与y1之间没有y，依次类推。

那对于ijkxyz ixjkyz之类的情况，可能换出ABCABC AABCBC，只能算一次。这样就限定当前枚举的ABC左边不存在ABC，就可以了。

Code

#include<bits/stdc++.h>
using std::vector;
using std::sort;
using std::unique;
using std::lower_bound;
using std::set;

const int P=1e9+7;
const int MAXN=100;
#define iter(x) typeof((x).begin())
typedef long long ll;
class MappingABC2
{
public:
	int countStrings(vector <int> t)
	{
		static int a[MAXN],b[MAXN];
		int n=t.size();
		if(n<3) return 0;
		ll res=0;
		for(int i=0;i<n;++i)
			a[i+1]=b[i+1]=t[i];
		sort(b+1,b+1+n);int cc=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++)
			a[i]=lower_bound(b+1,b+1+cc,a[i])-b;
		#define differ(x,y,z) (x!=y && x!=z && y!=z)
		set<int> kcnt[MAXN];
		for(int i=1;i<=n-2;i++)
		{
			for(int j=i+1;j<=n-1;j++)
			{
				for(int k=j+1;k<=n;k++)
				{
					if(!differ(a[i],a[j],a[k])) continue;
					for(int c=1;c<=cc;++c) kcnt[c].clear();
					ll temp=1;
					for(int p=1;p<=n;p++)
					{
						if(p<i) kcnt[a[p]].insert(1);
						if(i<p && p<j) kcnt[a[p]].insert(2);
						if(j<p && p<k) kcnt[a[p]].insert(3);
					}
					if(kcnt[a[i]].count(1) || kcnt[a[j]].count(2) || kcnt[a[k]].count(3))
						continue;
					for(int c=1;c<=cc;++c)
					{
						if(a[i]==c || a[j]==c || a[k]==c) continue;
						(temp*=(3-kcnt[c].size()))%=P;
					}
					(res+=temp)%=P;
				}
			}
		}
		((res%=P)+=P)%=P;
		return (int)res;
	}
};

胡扯单纯形

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

由于过于蒟蒻，文中的一切结论均不会证明 上图来自srOSengxianOrz的博客

一些说法是自己的理解，可能有些naive，还望指教写的很Low，大白话，省略了很多概念可以在这里看到更高大上一些的解说

Problem

给定目标函数 $y=\sum c_ix_i$ 和若干限制形如 $\sum {a_{ij}}x_j\le b_i$ 要求

Solution

根据数学必修五的解题经验，可以发现最优解一定出现在可行域的边界或者顶点。单纯形的做法，就是不停地变换整个线性规划让取值从一个顶点走到令一个顶点，直到可以判定当前解最优为止。

标准型与松弛型

所谓标准型，即把约束条件写成形如 $\sum a_{ij}x_j\le b_i$ 所谓松弛型，即加入一个松弛变量 $x'$ ，把约束调节写成 $x'_i=b_i-\sum a_{ij}x_j,x'_i\ge 0$ 标准型转化到松弛型是很显然的，非标准型也容易通过同乘 $-1$ 什么的转化到标准型。可以发现，对于一个松弛型，当 $b_i$ 均 $\ge 0$ 的时候，令 $x'_i=b_i$ ，其它变量都为 $0$ ，就是一组可行解(而对于存在 $b_i< 0$ ，可以通过一些构造方法生成一组可行解)。所以接下来就在这个可行解的基础上逼近最优解。

Simplex

$y=\sum c_ix_i$ ，可以发现，如果变换之后，仍然有某个 $c_i> 0$ ，那就有可能通过修改 $x_i$ 的值让 $y$ 增大。当所有 $c_i< 0$ ，即可以证明线性规划已经达到了最优解。。 $Pivot$ 就是修改某个值之后相应变换整个线性规划的过程。

Pivot

对于选定出的 $e$ 使得 $c_e> 0$ ，需要在满足条件的情况下。那就遍历每个式子 $x'_i=b_i-\sum a_{ij}x_j,x'_i\ge 0$ ，如果 $a_{ie}\ge 0$ ，说明这个式子对 $x_e$ 产生了约束，在这个式子中， $x_e$ 取最大值的情况就是其它变量为 $0$ ，使得 $a_{ie}x_e=b_i$ 。因此用 $\dfrac {b_i}{a_{ie}}$ 衡量限制的松紧。找出对这个变量限制最紧的式子，把所有 $b_i$ 都分给它，式子变形为，即。此时在 $x_e$ 位置上的那个变量就已经不是 $x_e$ ，而是 $x'_i$ ，所以需要将这个式子带到所有其它的式子里面，相当于把 $x_e$ 用它对应的新式子等效地替代掉。举个栗子(用 $'$ 表示变换之后的量) 带入另一个式子 $k$ 化简以下就出来了。相应地， $c[]$ 数组也要修改。因为也要把 $x_i''$ 向 $y$ 里面带，带完之后所有项的系数都变了。这样，单纯形就解完了。

对偶原理

是这样说的：线性规划 $\sum {a_{ij}}x_j\le b_i$ 的对偶问题是 $\sum {a_{ji}}x'_i\ge c_j$ 两者具有相同的最优解

比如算法导论上给出了一个栗子满足 $x_1+x_2+3x_3\le 30$ $2x_1+2x_2+5x_3\le 24$ $4x_1+x_2+2x_3\le 36$ $x_1,x_2,x_3\ge 0$ 的对偶问题是满足 $y_1+2y_2+4y_3\ge 3$ $y_1+2y_2+y_3\ge 1$ $3y_1+5y_2+2y_3\ge 2$ $y_1,y_2,y_3 \ge 0$

有了这个工具，一些情况下就可以避免乘 $-1$ 使 $b_i$ 出现负值了。

BZOJ 1812 Riv

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

Link

轻车熟路，独立A掉，Cool！

Solution

可以注意到，每个点对答案的贡献取决于它到它的祖先中离它最近的伐木场的距离。按照套路，设计状态 $f[i][j][d]$ 表示在以 $i$ 为根的子树内，建了 $j$ 个伐木场， $i$ 点到最近的伐木场距离为 $d$ ，这棵子树对答案的最小贡献。笼统地说 $d$ 是距离，但是直接表示是不好表示的。所以就做个转化，相当于离散化，用 $d$ 表示最近的伐木场的深度，这样也可以很方便地转移。于是考虑 $f[i][j][d]$ 的转移。通过观察，可以得到一个性质：一个点 $p$ ，与它的任意子节点 $u$ ，要么 $d$ 相同，要么 $d[u]==depth[u]$ ，即 $u$ 上建了伐木场。~~你说这个还叫性质？不是一眼秒的东西嘛。好吧当我没说~~ 然后就可以分情况讨论转移了。然后这里又涉及背包的合并，我想当然地写完，发现输出 $0$ 。最后发现，一开始设置的合法状态的 $0$ 和任何的值取min都是它本身。苦思冥想得不到结果，最后得出的结论是要求用最小代价把背包填满的多重背包不能用滚动数组。。（如果可以的话还请指教）

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=111,INF=0x7f7f7f7f;
using std::vector;
using std::min;
int sum(int x,int y){return x==INF||y==INF?INF:x+y;}
int dis[MAXN],fs[MAXN][MAXN],w[MAXN],fa[MAXN],n,m,f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN],dep[MAXN];
int son[MAXN][MAXN];
int cost(int id,int d){return (dis[id]-dis[fs[id][d]])*w[id];}
void DP(int pos)
{
	static int Pack[MAXN][MAXN];
	#define Reset(x) (memset(x,127,sizeof(x)),x[0][0]=0)
	int *sons=son[pos],sonc=sons[0];
	for(int i=1;i<=sonc;i++) DP(sons[i]);
	if(pos)
	{
		Reset(Pack);
		for(int i=1;i<=sonc;i++)
		{
			int u=sons[i];
			for(int j=m-1;~j;j--)
				for(int k=0;k<=j;k++)
					chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][dep[pos]],f[u][k][dep[u]])));
		}
		for(int j=m-1;~j;j--)
			f[pos][j+1][dep[pos]]=sum(Pack[sonc][j],cost(pos,dep[pos]));
		for(int d=0;d<dep[pos];++d)
		{
			Reset(Pack);
			for(int i=1;i<=sonc;i++)
			{
				int u=sons[i];
				for(int j=m;~j;j--)
					for(int k=0;k<=j;k++)
						chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][d],f[u][k][dep[u]])));
			}
			for(int j=m;~j;j--)
				f[pos][j][d]=sum(Pack[sonc][j],cost(pos,d));
		}
	}
	else
	{
		f[pos][0][0]=0;
		Reset(Pack);
		for(int i=1;i<=sonc;i++)
		{
			int u=sons[i];
			for(int j=m;~j;j--)
				for(int k=0;k<=j;k++)
					chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][0],f[u][k][1])));
		}
		for(int j=m;~j;j--) f[pos][j][0]=Pack[sonc][j];
	}
}
void DFS(int pos)
{
	for(int i=1;i<=son[pos][0];i++)
	{
		dep[son[pos][i]]=dep[pos]+1;
		dis[son[pos][i]]+=dis[pos];
		DFS(son[pos][i]);
	}
}
int main()
{
	get(n),get(m);
	for(int i=1;i<=n;i++)
	{
		get(w[i]),get(fa[i]),get(dis[i]);
		son[fa[i]][++son[fa[i]][0]]=i;
	}

	DFS(0);
	for(int i=0;i<=n;i++)
	{
		int p=i;
		while(p) 
			fs[i][dep[p]]=p,p=fa[p];
	}
	memset(f,127,sizeof(f));
	DP(0);
	printf("%d\n",f[0][m][0]);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 2037 Sue的小球

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

Link

Solution

将最大收益转化成最小损失，在转移的时候将损失提前计算，这样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=1000+11;
const LL INF=1e15;
using std::sort;
using std::min;
template <class T> inline T min(const T &a,const T &b,const T &c,const T &d){return min(min(a,b),min(c,d));}
struct poi{int x,y,v;}p[MAXN];
bool operator <(const poi &a,const poi &b){return a.x<b.x;}
int sumv[MAXN],mid,n;
LL f[MAXN][MAXN][2];
bool ud[MAXN][MAXN][2];
LL dist(int l,int r){return p[r].x-p[l].x;}
LL sigmaV(int l,int r){return sumv[r]-sumv[l-1];}
LL DP(int l,int r,int d)
{
	if(r<mid || l>mid) return INF;
	if(ud[l][r][d]) return f[l][r][d];
	LL &res=f[l][r][d];ud[l][r][d]=1;
	if(d==0)
		res=min(DP(l+1,r,0)+(sigmaV(1,l)+sigmaV(r+1,n))*dist(l,l+1),
				DP(l+1,r,1)+(sigmaV(1,l)+sigmaV(r+1,n))*dist(l,r));		
	else
		res=min(DP(l,r-1,1)+(sigmaV(1,l-1)+sigmaV(r,n))*dist(r-1,r),
				DP(l,r-1,0)+(sigmaV(1,l-1)+sigmaV(r,n))*dist(l,r));
	return res;
}
int main()
{
	int x0,sumy=0;get(n),get(x0);
	for(int i=1;i<=n;i++) get(p[i].x);
	for(int i=1;i<=n;i++) get(p[i].y);
	for(int i=1;i<=n;i++) get(p[i].v);
	p[++n].x=x0;p[n].y=0;p[n].v=0;
	sort(p+1,p+1+n);
	for(int i=1;i<=n;i++)
	{
		sumv[i]=sumv[i-1]+p[i].v;
		sumy+=p[i].y;
		if(p[i].x==x0 && p[i].y==0)
		{
			f[i][i][0]=f[i][i][1]=0;
			ud[i][i][0]=ud[i][i][1]=1;
			mid=i;
		}
	}
	printf("%.3lf\n",(sumy-min(DP(1,n,0),DP(1,n,1)))/1000.0);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 1065 奥运物流

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

Link

做了大概一年的样子

Solution

因为任何站都可以到达 $1$ ，所以这个图的形态一定是一个包含 $1$ 的环上挂着很多树。考虑环， $V_1=C_1+kV_3$ $V_2=C_2+kV_1$ $V_3=C_3+kV_2$ 带进去最后得到 $V_1-k^3V_1=C_1+kC_2+k^2C_3$ , 可以看出每个点对答案的贡献与到 $1$ 的距离成正相关，且 $V_1$ 的值是和环的大小有关的。所以通过枚举修改环上点的后继为 $1$ ，就可以得到确定环的大小，并且把这个图转化成一棵树，可以进行DP了（在建图的时候直接忽略 $1$ 的后继，因为忽略了才是树，而且从上式可以看出忽略也没影响）。然后就转化成一个树上的问题：可以修改一个点的后继为 $1$ ，使得 $\sum k^{dist(1,i)}c_i$ 最大。然后就开始高能了。设计状态 $f[i][j]$ 表示在以 $i$ 为根的子树中修改 $j$ 次，子树中的点对答案的最大贡献。假如说现在要修改一个点的后继为 $1$ ，有如下的情况：

其子孙节点都没有改过
其子孙节点有一个已经改到了1

明显对答案的影响是不一样的。这个状态没法转移。 ~~于是 $f[i][j][S]$ 表示在以 $i$ 为根的子树中修改 $j$ 次，其子孙节点的修改状态为 $S$ ，子树中的点对答案的最大贡献。~~ 发现这个问题的特点：当前状态的转移方法会对之后的状态的转移产生影响，而将当前状态的转移方法进行状压又不现实。于是观察答案的性质：每个点对答案的贡献是 $k^{dist(1,i)}c_i$ ，也就是说，只要 $dist(1,i)$ 知道了，这个点对答案的贡献就可以算了。所以就考虑把状态加上一维: $f[i][j][d]$ 表示在以 $i$ 为根的子树中修改 $j$ 次， $dist(1,i)==d$ 的情况下，子树中的点对答案的最大贡献。这样以来，每个点对答案的影响就可以独立统计了，也就解决了当前转移对后面状态转移产生影响的问题。现在考虑如何转移 $f[i][j][d]$ (我做的时候把不合法的状态都设置了 $-\infty$ ..) 首先定义 $1$ 的深度 $dep=0$ 对于 $dep>1$ 的点，有两种选择：修改自己和不修改自己如果修改自己，那子节点如果不修改，深度就是 $2$ ，子节点如果修改，深度就是 $1$ ；如果不修改自己，子节点如果不修改，深度就是 $dep+1$ ，如果修改，深度就是 $1$ 。所以

f[i][j][d]=max \left\{ \begin{aligned} max\{\sum max\{f[son_t][k_t][d+1],f[son_t][k_t][1]\}|,\sum k_t==j\},d>1\\ max\{\sum max\{f[son_t][k_t][1],f[son_t][k_t][2]\}|,\sum k_t==j-1\},d==1\\ \end{aligned}\right.

然后 $dep==1$ 和 $==0$ 也类似，就可做了。

初始的合法状态

以下纯属一个蒟蒻的自言自语 当 $dep> 1$ ，对于自己不修改的情况 $f[pos][0][dep]$ 肯定是合法的，置为 $0$ 。当在这棵子树中花费为 $0$ 的时候，任意的 $f[pos][0][d],d\le dep$ 都是合法的（祖先可能被修改）。而对于自己有修改的情况，只需要把 $f[pos][1][1]$ 置为 $0$ 即可。如果正向推不出来，可以反过来思考：对于可能出现的每种合法转移，都必须能够沿着它的转移路线走到一个 $0$ 。对于自己不修改的情况，对于不同的 $d$ ， $f[pos][][d]$ 的转移是互相独立的，所以在每种 $d$ 上都需要有一个 $0$ 。对于自己有修改的情况，最终追溯到最优的一定是先用1次修改来把自己接到 $1$ 上。 ~~$\uparrow$ 其实这么做完全是作茧自缚，网上遍地是全都置 $0$ ，在转移的时候走合法路径的代码。。~~

多重背包的滚动数组

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品最多有 $M_i$ 件可用，每件耗费的空间是 $C_i$ ，价值是 $W_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

for(int i=1;i<=n;i++)
	for(int v=0;v<=V;v++)
    	for(int k=0;k*c[i]<=v && k<=cnt[i];k++)
        	chkmx(f[i][v],f[i-1][v-k*c[i]]+k*w[i]);

对于 $01$ 背包和完全背包，可以使用滚动数组优化空间复杂度。

for(int i=1;i<=n;i++)
	for(int v=V;v>=c[i];v--)
    //for(int v=c[i];v<=V;v++)
    	chkmx(f[v],f[v-c[i]]+w[i]);

而对于多重背包，使用滚动数组必须要保证：对于同一个体积 $v$ ，不会同时被 $k_1$ 和 $k_2$ 个相同的物品同时优化。即，不能在一个体积的背包里先装上 $k_1$ 个 $A$ ，然后又装上 $k_2$ 个 $A$ 。实现的方法是

for(int i=1;i<=n;i++)
	for(int v=V;~v;v--)
    	for(int k=0;k*c[i]<=v && k<=cnt[i];k++)
        	chkmx(f[v],f[v-k*c[i]]+k*w[i]);

对于一般的多重背包，第三层循环的枚举顺序应该可以倒过来~~(我没想出反例的样子？)~~ 但是对于这道题目就不行了。因为这个题目在 $k==0$ 的时候也可能会对答案产生贡献，如果从大到小枚举，就会让答案多加了 $f[u][0][d+1/1]$ ~~(不要问我怎么知道的)~~ 所以不管怎样写成从小到大的还是保险一些。(也许这样写也有坑点？)

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define getf(x) scanf("%lf",&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=100;
const double INF=1e10;
using std::vector;
using std::max;

vector<int> son[MAXN];
double c[MAXN],f[MAXN][MAXN][MAXN],pw[MAXN];int m;

void DP(int pos,int dep)
{
	#define foreach(it,x) for(vector<int>::iterator it=x.begin();it!=x.end();++it)
	for(int j=0;j<=m;j++)
		for(int d=0;d<=dep;d++)
			f[pos][j][d]=-INF;//*(j!=0);//-INF;
	f[pos][0][dep]=0;
	foreach(it,son[pos]) DP(*it,dep+1);
	if(dep>1)
	{
		//每个d是一个独立的背包
		f[pos][1][1]=0;
		for(int d=2;d<dep;d++) f[pos][0][d]=0;
		//改自己
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m-1;~v;v--)
				for(int i=v;~i;i--)
					chkmx(f[pos][v+1][1],f[pos][i+1][1]+max(f[u][v-i][1],f[u][v-i][2]));
		}
		//不改自己
		for(int d=2;d<=dep;++d)
			foreach(it,son[pos])
			{
				int u=*it;
				for(int v=m;~v;v--)
					for(int i=v;~i;i--)
						chkmx(f[pos][v][d],f[pos][i][d]+max(f[u][v-i][1],f[u][v-i][d+1]));
			}
		for(int d=1;d<=dep;d++)
			for(int v=m;~v;v--)
				f[pos][v][d]+=c[pos]*pw[d];
	}
	else if(dep==1)
	{
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m;~v;v--)
				for(int i=v;~i;i--)
					chkmx(f[pos][v][1],f[pos][i][1]+max(f[u][v-i][1],f[u][v-i][2]));
		}
		for(int v=m;~v;v--)
			f[pos][v][1]+=c[pos]*pw[1];
	}
	else
	{
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m;~v;v--)
				for(int i=v;~i;i--)	
					chkmx(f[pos][v][0],f[pos][i][0]+f[u][v-i][1]);
		}
		for(int v=m;~v;v--)
			f[pos][v][0]+=c[pos]*pw[0];
	}
}
int main()
{
	static int succ[MAXN];
	int n;double K;
	get(n),get(m),getf(K);
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*K;
	for(int i=1;i<=n;i++) get(succ[i]);
	for(int i=1;i<=n;i++) getf(c[i]);
	double Ans=-INF;
	for(int brp=succ[1],cl=2;brp!=1;brp=succ[brp],cl++)
	{
		for(int i=1;i<=n;i++) son[i].clear();
		for(int i=2;i<=n;i++) 
			son[i==brp?1:succ[i]].push_back(i);
		DP(1,0);
		double res=-INF;
		for(int i=m-(succ[brp]!=1);~i;i--) chkmx(res,f[1][i][0]);
		chkmx(Ans,res/(1-pw[cl]));
	}
	printf("%.2lf\n",Ans);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 1495 网络收费

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

Link

没有表示出状态，因为叶节点的不会记录，而叶节点的状态对后来的转移也是产生影响的。之前也做过涉及到未来费用的题目，但是远远没有这个毒瘤。

Solution

可以看出两种情况是对称的。找一下它们的共同点：同0/2 不同 1 进而可以发现一个点对对答案产生的贡献是可以分开统计的：当 $nA < nB$ 时，每个 $A$ 都会对答案产生一倍的贡献；当 $nB \ge nB$ 时，每个 $B$ 都会对答案产生一倍贡献。这个转换是明显等价的，这样就把计算过程大大简化了，由计算点对变成了计算点。那么，对于一个点 $u$ ，如果它任意一个祖先点 $p$ 的 $nA$ 和 $nB$ 的大小关系确定了，那么 $u$ 对 $p$ 的贡献也就确定了。而祖先的这种大小关系可以用一个二进制串 $S$ 表示。由此，设计状态如下 $f[i][nA][S]$ 表示在以 $i$ 为根的子树中有 $nA$ 个 $A$ 节点， $i$ 的所有祖先状态为 $S$ 的时候，子树子树中的点对答案产生的最小贡献。转移基本就和普通的树形DP相同了。但是这样会MLE： $nA$ 的上界是 $2^n$ ， $S$ 的上界是 $111...111,n-1$ 个 $1$ ，所以也是 $O(2^n)$ 级别。然而，可以发现 $nA$ 和 $S$ 是互相制约的，深度越浅的点，子树中的节点越多，但是到祖先的路径越短、状态总数越少。于是，可以把 $nA$ 和 $S$ 这两维压到一起存储。所以这个题就呵呵了

Code

如果有谁A掉了这个题，万望解答我在注释中的疑问

//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 INF=0x7f7f7f7f,MAXN=11,A=0,B=1;
int lca(int x,int y)
{
	while(x!=y) (x>y?x:y)>>=1;
	return x;
}
int sum(int x,int y){return x==INF||y==INF?INF:x+y;}
int dep[1<<MAXN],init[1<<MAXN],pay[1<<MAXN],flow[1<<MAXN][1<<MAXN],n,sumc[1<<MAXN][MAXN],f[1<<MAXN][1<<MAXN<<1];
void DP(int pos)//定义路由器的颜色为数量少的颜色
{
	int id=pos-(1<<n)+1,divider=n-dep[pos]+1,covers=(1<<divider>>1);
	if(dep[pos]==n)
	{
		for(int S=0;S<=(1<<dep[pos])-1;++S)//总量为1是A 0是B
		{
			f[pos][(init[id]^1)+(S<<divider)]=pay[id];
			f[pos][init[id]+(S<<divider)]=0;
			for(int i=dep[pos]-1;~i;i--)
				if(((S>>i)&1)==A) f[pos][1+(S<<divider)]+=sumc[id][i];
				else f[pos][0+(S<<divider)]+=sumc[id][i];
		}
	}
	else
	{
		int ls,rs,sonD=divider-1;DP(ls=pos<<1),DP(rs=pos<<1|1);
		for(int fl=0;fl<=(covers>>1);fl++)
			for(int fr=0;fr<=(covers>>1);fr++)
			{
				for(int S=0;S<=(1<<dep[pos])-1;++S)
				{
					int kind;
					//f[i][j][k]表示在以i节点为根的子树，有j个A，祖先状态为K的最小代价
					//把第二第三维压成(j+(k<<UPLIM)
					if((fl+fr)<=(covers-fl-fr)) kind=A; 						
					else kind=B;
					//这里判断当前节点的类型
					//如果改成<会WA
					
					int sonS=S|(kind<<dep[pos]);
					//int sonS=S|(((fl+fr)>(covers-fl-fr))<<dep[pos]);
					chkmn(f[pos][fl+fr+(S<<divider)],sum(f[ls][fl+(sonS<<sonD)],f[rs][fr+(sonS<<sonD)]));
				}
			}
	}
}
int main()
{
	get(n);
	
	dep[0]=-1;
	for(int i=1;i<=(1<<n<<1)-1;i++) dep[i]=dep[i>>1]+1;

	for(int i=1;i<=(1<<n);i++) get(init[i]);
	for(int i=1;i<=(1<<n);i++) get(pay[i]);
	for(int i=1;i<=(1<<n)-1;i++)
		for(int j=i+1;j<=(1<<n);j++)
			get(flow[i][j]);
	for(int i=1;i<=(1<<n)-1;i++)
		for(int j=i+1;j<=(1<<n);j++)
		{
			int d=dep[lca(i+(1<<n)-1,j+(1<<n)-1)];
			sumc[i][d]+=flow[i][j],sumc[j][d]+=flow[i][j];
		}
	memset(f,0x7f,sizeof(f));//sizeof(127) heheda
	DP(1);
	int Ans=INF;
	for(int i=0;i<=(1<<n);i++)
		chkmn(Ans,f[1][i]);
	printf("%d\n",Ans);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

BZOJ 3261 最大异或和

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

Link

模板题了

Code

各种卡终于卡到了RANK1。。感觉自己好闲好zz。。

//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;}
namespace IO
{
	#ifndef get
	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;static char ch;
		f=1;while(!isdigit(ch=getc())) if(ch=='-') f=-1;
		x=ch-'0';while(isdigit(ch=getc())) (x*=10)+=ch-'0';
		x*=f;
	}
	#endif
	const int OUT=1e7;
	char outbuf[OUT],*optr=outbuf,*oend=outbuf+OUT-1;
	#define flush() (fwrite(outbuf,1,optr-outbuf,stdout))
	#define putc(x) ((optr==oend)?flush(),optr=outbuf,*optr++=x:*optr++=x)
	inline void put(int x)
	{
		if(x<0) putc('-');
		if(!x) putc('0');
		if(x)
		{
			static char stack[100];int top;
			for(top=0;x;x/=10)
				stack[++top]=(x%10)+'0';
			while(top) putc(stack[top--]);
		}
		putc('\n');
	}
}using namespace IO;
const int MAXN=400000+10;
namespace iTrie
{
	const int LEN=24,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<<1]={null};
	int sum[MAXN<<1],rc;
	Node *newNode()
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;cur->cnt=0;
		return cur;
	}
	Node *newNode(Node *old)
	{
		static Node *cur;cur=new(ME++) Node;*cur=*old;
		return cur;
	}
	void Insert(Node *&pos,int x)
	{
		pos=newNode(pos);Node *cur=pos;
		for(int c,i=LEN-1;~i;i--)
		{
			c=(x>>i)&1;cur->cnt++;
			cur->son[c]=newNode(cur->son[c]);
			cur=cur->son[c];
		}
		cur->cnt++;
	}
	void Add(int x)
	{
		++rc;sum[rc]=sum[rc-1]^x;
		Insert(root[rc]=root[rc-1],sum[rc]);
	}
	int cnxt(Node *pl,Node *pr,int c){return pr->son[c]-pl->son[c];}
	int Query(int x,int l,int r)
	{
		int res=x;Node *pl=root[l],*pr=root[r+1];
		for(int c,i=LEN-1;~i;i--)
		{
			c=(x>>i)&1;
			if(cnxt(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;
	}
}using namespace iTrie;
int main()
{
	null->son[0]=null->son[1]=null;
	Add(0);
	int n,m;get(n),get(m);
	for(int i=1;i<=n;i++)
	{
		int x;get(x);
		Add(x);
	}

	for(int i=1;i<=m;i++)
	{
		char opt;int l,r,x;
		while(!isalpha(opt=getc()));
		if(opt=='A')
		{
			get(x);
			Add(x);
		}
		else
		{
			get(l),get(r),get(x);
			//printf("%d\n",Query(x^sum[rc],l-1,r-1));
			put(Query(x^sum[rc],l-1,r-1));
		}
	}
	flush();
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */

Lucida

It's been a while.

222 日志

127 标签

Solution

Code

Solution

Tips

关于 的用法

Code

p1

Solution

Code

p1

Code

p2

Code

p3

Solution

Code

Problem

Solution

标准型与松弛型

Simplex

Pivot

对偶原理

Solution

Code

Solution

Code

Solution

初始的合法状态

多重背包的滚动数组

Code

Solution

Code

Code

关于的用法