昨晚第一次做cf，结果做了两题就笔记本断电滚粗了。。
A Sereja and Coat Rack 水题
B Sereja and Suffixes 预处理
C Sereja and Algorithm
题意：给出长度<=1e5的字符串s（只含有xyz），给出算法：随意选三个字母长的子串，且要求它不是xzy、yxz、zyx三个中的一个，然后可以随意重排它。直到找不出这样的三字母长的子串，算法结束。对于每个样例，给出m个询问（m<=1e5）：l r。问s[l……r]能否在有限步数内终结。
思路：可知如果会终结，则最后的字符串一定是以下情况中的一种：
(1)形如xzyxzy……或者yxzyxz……或者zyxzyx……
(2)只有一个字母或两个字母。
注意第（2）种情况，被坑了。。
所以预处理统计符合条件的长度为i的字符串中x、y、z各自的个数即可（三种情况），然后统计s[l……r]中x、y、z的个数
D：现在还不会。。。。。。。
E Sereja and the Arrangement of Numbers
题意：给出n（n<=2*1e6），m(m<=1e5),给出m个互异的整数。定义数列:a1、a2……an，如果任意两个数ai、aj(ai!=aj)存在pos(1<=pos<=n)，a[pos]=ai,a[pos+1]=aj或者a[pos]=aj,a[pos+1]=ai,则称该数列合法。给出的m个数有各自的价值，问组成长度为n的合法数列最多能得到价值。
看了题解才知道是图论，，弱爆了。。
先求出i个不同的数组成合法序列的最小长度。然后对于n只要在这个数组（已经单调）中二分出它的位置pos，pos表示组成长度为n的合法序列最多可以用多少个不同的数。然后将给出的m个数降序排列，取前面pos个。
关键在于求出i个不同的数组成合法序列的最小长度：
方法是可以把i个不同的数看成i个点，两两之间连边形成完全图。有边表示两点相邻。问题变为求最小加多少条边可以使其变成半欧拉图。（因为如果是半欧拉图的话，就可以不重复的遍历所有边，也就是找到了一个序列满足所有相邻关系）。分奇偶讨论，偶数要加n/2-1，因为i为偶数的话，每个点的度数是奇数，最后要补成只有两个奇度点。注意序列长度=边数+1；
Author Archives: shadow
polya定理&&burnside引理
专题地址：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36645#overview
这里有更完整的：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=484
看了下大白书，做下上面的习题。两个定理叙述很简单，证明暂时没看，先把题做的差不多再说。。
一些小结：
1.置换。一对一的函数
2.置换的乘法：满足结合律，但不满足交换律
3.置换分解成几个循环的乘积，因为假如将一个置换看成一条有向边那么形成的图中每个点都是入度为1，出度为1.所以一定是若干个圈。
4.独立的循环之间的乘法满足交换律
5.设A是与元素个数为n的循环，则：
(1)若n为奇数，则A*A是一个n个元素的循环
(2)若n为偶数，则A*A是两个n/2个元素且相互独立的循环的乘积
6.引出：由5的性质可知：
(1)一个长度n为奇数的循环B，一定可以找到一个长度为n的循环A,满足A^2=B;
(2)两个长度都为n的不相交循环B和C，一定可以找到长度为2*n的循环A，使得A^2=B*C;
7.继续引出：
(1)长度n为奇数的循环既可以是两个长度为n的循环乘出来的，也可以是两个长度为2n的循环乘出来的。
(2)长度n为偶数的循环只可能是两个长度为2n的循环乘出来的。
下面是一些题目
UVA 10294 Arif in Dhaka (First Love Part 2)
数学推算。。
#include<stdio.h>
#include<math.h>
typedef long long ll;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
ll fact[15][60];
int main()
{
int i,j;
int n,t;
for(i=1;i<=10;i++)
fact[i][1]=(ll)i;
for(i=1;i<=10;i++)
for(j=2;j<=50;j++)
fact[i][j]=fact[i][j-1]*(ll)i;
while(~scanf("%d%d",&n,&t))
{
ll a=0,b=0;
for(i=0;i<=n-1;i++)
a+=fact[t][gcd(n,i)];
b=n*(fact[t][(n+1)/2]+fact[t][(n+2)/2])/2;
printf("%lld ",a/n);
printf("%lld\n",(a+b)/(2*n));
}
return 0;
}
UVALive 3641 Leonardo’s Notebook
上述的几点“引出”。。
#include<stdio.h>
#include<string.h>
char s[30];
int ring[30];
bool visit[30];
int dfs(int cur)
{
int ret=1;
if(visit[cur]) return 0;
visit[cur]=1;
ret+=dfs(s[cur]-'A'+1);
return ret;
}
int main()
{
int i,j;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
memset(ring,0,sizeof(ring));
memset(visit,0,sizeof(visit));
for(i=1;i<=26;i++)
{
if(visit[i]) continue;
int ret=dfs(i);
ring[ret]++;
}
for(i=1;i<=26;i++)
if(!(i&1) && ring[i]&1) break;
if(i<=26) printf("No\n");
else printf("Yes\n");
}
return 0;
}
UVA 11077 Find the Permutations
递推，具体见lrj的训练指南。
#include<stdio.h>
#include<string.h>
typedef unsigned long long ll;
ll f[22][22];
int main()
{
int i,j;
int n,k;
memset(f[1],0,sizeof(f[1]));
f[1][0]=1;
for(i=2;i<=21;i++)
for(j=0;j<i;j++)
{
if(j==0) f[i][j]=1;
f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1);
}
while(~scanf("%d%d",&n,&k) && !(n==0 && k==0))
printf("%llu\n",f[n][k]);
return 0;
}
2013 hangzhou regional I题
感觉最近写代码总是小错误不断，没有刚学acm时认真了。。
#include<stdio.h>
#include<string.h>
int box[30][10];
int dp[1<<21];
int g,b,s,goal;
inline int max(int a,int b){return a>b?a:b;}
int DP(int st)
{
int i,j,k;
if(dp[st]!=-1) return dp[st];
int co[10];
memset(co,0,sizeof(co));
for(i=0;i<=b-1;i++)
{
if(!(st&(1<<i))) continue;
for(j=1;j<=g;j++) co[j]+=box[i][j];
}
int sr=0;
for(i=1;i<=g;i++)
{
sr+=co[i]/s;
co[i]=co[i]%s;
}
int rest=goal-sr;
for(i=0;i<=b-1;i++)
{
if(st&(1<<i)) continue;
int score=0,tmpc[10];
for(j=1;j<=g;j++) tmpc[j]=co[j];
for(j=1;j<=g;j++)
{
tmpc[j]+=box[i][j];
score+=tmpc[j]/s;
}
if(score)
{
dp[st]=max(dp[st],score+DP(st|(1<<i)));
}
else
{
dp[st]=max(dp[st],rest-DP(st|(1<<i)));
}
}
return dp[st];
}
int main()
{
int i,j;
while(~scanf("%d%d%d",&g,&b,&s) && !(g==0 && b==0 && s==0))
{
memset(dp,-1,sizeof(dp));
memset(box,0,sizeof(box));
dp[(1<<b)-1]=0;
for(i=0;i<=b-1;i++)
{
int n;
scanf("%d",&n);
for(j=1;j<=n;j++)
{
int c;
scanf("%d",&c);
box[i]1++;
}
}
goal=0;
int col[10];memset(col,0,sizeof(col));
for(i=0;i<=b-1;i++)
for(j=1;j<=g;j++)
col[j]+=box[i][j];
for(j=1;j<=g;j++)
goal+=col[j]/s;
printf("%d\n",2*DP(0)-goal);
}
return 0;
}
uva12589 Learning Vector
比赛的时候没想到是背包的dp啊。。。
思路：先按斜率排序，因为对于确定的一些向量，一定是斜率大的在前可以使总面积最大化。dp方程主体是背包，但是加了一维，表示最右侧的向量的最高点的y值。也就是dp[i][j][k]表示前i个向量中选取j个且最右侧高为k的最大面积。可以用滚动数组省掉阶段那一维，然后和一般背包不同的是，因为如果填表的话，每次对于dp[i][j][k]，都要枚举dp[i-1][j-1][0……k-1],复杂度很高，所以用刷表的方式，每次用dp[i][j][k]更新dp[i+1][j+1][k+p[i].y]。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Point{
int x,y;
}Point;
Point p[60];
bool cmp(Point a,Point b)
{
return a.y*b.x>b.y*a.x;
}
int dp[60][3000];
int main()
{
int i,j,r,cases=0;
int t,n,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
memset(dp,-inf,sizeof(dp));dp[0][0]=0;
for(i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+1+n,cmp);
for(i=1;i<=n;i++)
{
for(j=k;j>=0;j--)
{
for(r=0;r<=50*n;r++)
{
if(dp[j][r]==-inf) continue;
int tmp=dp[j][r]+(r+p[i].y+r)*p[i].x;
if(tmp>dp[j+1][r+p[i].y])
dp[j+1][r+p[i].y]=tmp;
}
}
}
int ans=-inf;
for(r=0;r<=50*n;r++) if(dp[k][r]>ans) ans=dp[k][r];
printf("Case %d: %d\n",++cases,ans);
}
return 0;
}
splay tree专题
很早以前就想学splay，但是迫于图论方面的知识还很不全面，于是放弃了计划，第一次区域赛之后打算学一下splay，所以这几天就开始看起来了，看着爽哥的ppt和模板慢慢学，到现在为止基本上理解了splay树的旋转和splay操作，然后就开始做题啦。。接下来要开始重点转入dp和数据结构的学习了~
1.关于rotate和splay操作的一个问题：为什么旋转x结点的时候只pushup()fa[x]?
答：因为rotate操作是用在splay操作里面的，由于splay的时候x结点可能被旋转多次，所以x结点为根的子树的结构在不停变化中，没必要每次旋转都pushup，但是旋转点x的父亲结点却在旋转后不会再旋转了，所以要pushupx结点的父亲。最后全部旋转完毕在pushupx结点就行了。
2.由此可能想到另一个问题：splay的时候，又是旋转x结点前要先旋转x的父节点y，这时候pushup了y的父节点z，那么y结点有没有pushup呢？
答：有的，因为每次旋转y必然伴随着旋转一次x，所以旋转x的时候，y结点pushup了。
3.要注意哪些地方要pushdown。旋转一个节点前要先pushdown父节点，再pushdownx节点，将信息下推，完成这个节点的”使命”再旋转。访问一个节点的操作之前记得pushdown，再对这个节点操作。
4.深刻理解splay树的“序”:这个序是很广义的，没有序也可以是序。加入初始插入节点完毕时其实就形成了一个“序”。这时它的中序遍历序列就是它的序，也就是说此时splay中的任意两个元素间有了一种前后关系，这就是序。splay操作会维护splay树的平衡但是不会改变这个序，也就是说splay操作之后树的中序遍历序列式不变的。
5.findpre(x)和findnext(x):这两个操作必须先把x节点splay到根。因为如果不是根，那么x的父节点有可能是所求答案，但是findpre()和findnext()并没有考虑
6.关于翻转操作
void rever(int x)
{
swap(LC,RC);
rev[x]^=1;//为什么不是rev[x]=1;因为可能原来rev[x]就是1，表示这棵子树翻转过了，所以现在再翻一次，之后rev[x]^=1,rev[x]=0了，表示这棵树不用翻转了，也就不用向下传递标记了。
return;
}
hdoj1754 I Hate It
单点更新，区间询问最值
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 200000+5
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
int top1;//曾经用过的结点
int top2;//可用结点栈的栈顶
int ss[N];//可用结点栈
int que[N];//回收节点用到的队列
int num[N];//结点的权值
int val[N];//结点的值
int maxvalue[N];//区间最大值
int nodeNum;
void pushup(int x)
{
sz[x]=1+sz[LC]+sz[RC];//如果左子树为空，则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在，则指向空结点0，空节点的sz=0，不会造成错误
maxvalue[x]=max(maxvalue[LC],maxvalue[RC]);
maxvalue[x]=max(maxvalue[x],val[x]);
}
void rotate(int x, bool f) //旋转
{
int y=fa[x];
int z=fa[y];
ch[y][!f]=ch[x][f];
fa[ch[x][f]]=y;
fa[x]=z;
if(z)
{
ch[z][ch[z][1]==y]=x;
}
ch[x][f]=y;
fa[y]=x;
pushup(y);
}
void splay(int x, int g) //把结点x转到结点g下
{
int y=fa[x];
while (y!=g)
{
int z=fa[y];
bool f=(ch[y][0]==x);
if (z!=g && f==(ch[z][0]==y))
{
rotate(y,f);
}
rotate(x,f);
y=fa[x];
}
pushup(x);
if(g==0)
{
root=x;
}
}
void rotateto(int k,int g) { //把第k个结点转到结点g下,从第0个开始，因为有附加结点
int x=root;
while (sz[LC]!=k)
{
if (k<sz[LC])
{
x=LC;
} else
{
k-=(sz[LC]+1);
x=RC;
}
}
splay(x,g);
}
void newNode(int &x,int c)
{
if (top2)
{//ss栈是存储删掉的结点，这些结点可用，如果该栈不空，直接用这里面的结点号
x=ss[--top2];
}
else
{
x=++top1;//如果没有可用结点，则增加结点数。
}
LC=RC=fa[x]=0;
sz[x]=1;
val[x]=c;
maxvalue[x]=c;
}
void makeTree(int &x,int l,int r,int f)
{
if (l>r)
{
return;
}
int m=(l+r)>>1;
newNode(x,num[m]); /*num[m]权值改成题目所需的*/
makeTree(LC,l,m-1,x);
makeTree(RC,m + 1,r,x);
fa[x]=f;
pushup(x);//建立树的时候，从下往上依次pushup
}
void init(int n)
{
nodeNum=n;
ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;//0结点是空节点，代表没有
maxvalue[0]=-inf;
root=top1=top2=0;
//为了方便处理边界,加两个边界顶点
newNode(root,-inf);
newNode(ch[root][1],-inf);//这两个边界结点的值不影响正常求解
fa[top1]=root;
sz[root]=2;
makeTree(KT,1,n,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
//返回区间[l, r]中的最大值
int query(int l,int r)
{
rotateto(l-1,0);
rotateto(r+1,root);
return maxvalue[KT];
}
void update(int id,int v)
{
rotateto(id-1,0);
rotateto(id+1,root);
int x=ch[root][1];
maxvalue[LC]=val[LC]=v;
pushup(x);
pushup(root);
return;
}
}spt;
int main()
{
int i,j;
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%d",&spt.num[i]);
spt.init(n);
char com[5];
int a,b;
while(m--)
{
scanf("%s%d%d",com,&a,&b);
if(com[0]=='U') {spt.update(a,b);continue;}
printf("%d\n",spt.query(a,b));
}
}
return 0;
}
hdoj1890 Robotic Sort
题意：一个序列，要对其排序，排序方法是:
第一轮从[1,n]中找到最小值的下标id，旋转序列[1，id],这时候第一个数已经是最小数了。
第二轮从[2,n]中找到最小值的下标id，旋转序列[2,id]，这时候第二个数已经是第二小数了。
……
(以此类推)
第n轮从[n,n]中找到最小值的下标id，旋转序列[n,id],这时候第n个数已经是最小数了。
如果两个数相等，那么在排完序之后，原来下标小的仍然在前面，即这个排序过程是稳定的
思路：因为有重复值，而相等的数按排序时要按下标排，所以可以在插入splay之前先将这n个数hash成1~n这n个数，这样就避免了重复值得问题。
涉及splay的区间最小值和区间旋转，以及找到区间最小值的下标，显然按下标建树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define N 100000+5
#define inf 0x3f3f3f3f
using namespace std;
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
int top1;//曾经用过的结点
int top2;//可用结点栈的栈顶
int ss[N];//可用结点栈
int que[N];//回收节点用到的队列
int num[N];//结点的权值
int val[N];//结点的值
int minv[N];//区间最大值
bool rev[N];
int nodeNum;
void rever(int x)
{
rev[x]^=1;
swap(LC,RC);
}
void flip(int l,int r)
{
rotateto(l-1,0);
rotateto(r+1,root);
rever(KT);
}
void pushup(int x)
{
sz[x]=1+sz[LC]+sz[RC];//如果左子树为空，则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在，则指向空结点0，空节点的sz=0，不会造成错误
minv[x]=min(minv[LC],minv[RC]);
minv[x]=min(minv[x],val[x]);
}
void pushdown(int x)
{
if(!rev[x]) return;
rever(LC);rever(RC);
rev[x]=0;
}
int getminv_id(int l,int r)
{
rotateto(l-1,0);
rotateto(r+1,root);
int tmp=minv[KT];
int id=l-1;
int x=KT;
pushdown(x);
while(val[x]!=tmp)
{
if(minv[LC]==tmp) x=LC;
else
{
id+=sz[LC]+1;
x=RC;
}
pushdown(x);
}
return id+sz[LC]+1;
}
void rotate(int x, bool f) //旋转
{
int y=fa[x];
int z=fa[y];
pushdown(y);
pushdown(x);
ch[y][!f]=ch[x][f];
fa[ch[x][f]]=y;
fa[x]=z;
if(z)
{
ch[z][ch[z][1]==y]=x;
}
ch[x][f]=y;
fa[y]=x;
pushup(y);
}
void splay(int x, int g) //把结点x转到结点g下
{
int y=fa[x];
pushdown(x);
while (y!=g)
{
int z=fa[y];
bool f=(ch[y][0]==x);
if (z!=g && f==(ch[z][0]==y))
{
rotate(y,f);
}
rotate(x,f);
y=fa[x];
}
pushup(x);
if(g==0)
{
root=x;
}
}
void rotateto(int k,int g) { //把第k个结点转到结点g下,从第0个开始，因为有附加结点
int x=root;
pushdown(x);
while (sz[LC]!=k)
{
if (k<sz[LC])
{
x=LC;
} else
{
k-=(sz[LC]+1);
x=RC;
}
pushdown(x);
}
splay(x,g);
}
void newNode(int &x,int c)
{
if (top2)
{//ss栈是存储删掉的结点，这些结点可用，如果该栈不空，直接用这里面的结点号
x=ss[--top2];
}
else
{
x=++top1;//如果没有可用结点，则增加结点数。
}
LC=RC=fa[x]=0;
sz[x]=1;
rev[x]=0;
val[x]=c;
minv[x]=c;
}
void makeTree(int &x,int l,int r,int f)
{
if (l>r)
{
return;
}
int m=(l+r)>>1;
newNode(x,num[m]); /*num[m]权值改成题目所需的*/
makeTree(LC,l,m-1,x);
makeTree(RC,m + 1,r,x);
fa[x]=f;
pushup(x);//建立树的时候，从下往上依次pushup
}
void init(int n)
{
nodeNum=n;
ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;//0结点是空节点，代表没有
minv[0]=inf;
rev[0]=0;
root=top1=top2=0;
//为了方便处理边界,加两个边界顶点
newNode(root,inf);
newNode(ch[root][1],inf);//这两个边界结点的值不影响正常求解
fa[top1]=root;
sz[root]=2;
makeTree(KT,1,n,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void dfs(int x)
{
if(x==0) return;
dfs(LC);
printf("%d ",val[x]);
dfs(RC);
}
}spt;
typedef struct Node{
int v,pos;
}Node;
Node node[N];
bool cmp(Node a,Node b)
{
if(a.v!=b.v) return a.v<b.v;
return a.pos<b.pos;
}
int main()
{
int i,j;
int n,m;
while(~scanf("%d",&n) && n)
{
for(i=1;i<=n;i++)
{
scanf("%d",&node[i].v);
node[i].pos=i;
}
sort(node+1,node+1+n,cmp);
for(i=1;i<=n;i++) spt.num[node[i].pos]=i;
spt.init(n);
bool flag=1;
for(i=1;i<=n;i++)
{
int ret=spt.getminv_id(i,n);
spt.flip(i,ret);
if(flag) flag=0;else printf(" ");
printf("%d",ret);
}
printf("\n");
}
return 0;
}
HYSBZ 1588 营业额统计
一直wa，加了句if(scanf(“%lld”,&tmp)==EOF) tmp=0;就ac了，实在不太懂，求高手不吝解惑
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 50000+5
#define inf 100000000000000000LL
typedef long long ll;
inline ll min(ll a,ll b){return a<b?a:b;}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int top1;//曾经用过的结点
int top2;//可用结点栈的栈顶
int ss[N];//可用结点栈
int que[N];//回收节点用到的队列
ll val[N];
void rotate(int x, bool f) //旋转
{
int y=fa[x];
int z=fa[y];
ch[y][!f]=ch[x][f];
fa[ch[x][f]]=y;
fa[x]=z;
if(z)
{
ch[z][ch[z][1]==y]=x;
}
ch[x][f]=y;
fa[y]=x;
}
void splay(int x, int g) //把结点x转到结点g下
{
int y=fa[x];
while (y!=g)
{
int z=fa[y];
bool f=(ch[y][0]==x);
if (z!=g && f==(ch[z][0]==y))
{
rotate(y,f);
}
rotate(x,f);
y=fa[x];
}
if(g==0)
{
root=x;
}
}
void newNode(int &x,ll c)
{
if (top2)
{//ss栈是存储删掉的结点，这些结点可用，如果该栈不空，直接用这里面的结点号
x=ss[--top2];
}
else
{
x=++top1;//如果没有可用结点，则增加结点数。
}
LC=RC=fa[x]=0;
val[x]=c;
}
void init()
{
ch[0][0]=ch[0][1]=fa[0]=0;//0结点是空节点，代表没有
root=top1=top2=0;
//为了方便处理边界,加两个边界顶点
newNode(root,-inf);
newNode(ch[root][1],inf);//这两个边界结点的值不影响正常求解
fa[top1]=root;
}
int insert(int &x,ll v,int f)
{
if(!x)
{
newNode(x,v);fa[x]=f;return x;
}
if(val[x]==v) return 0;
int ret;
if(v<val[x]) ret=insert(LC,v,x);
if(v>val[x]) ret=insert(RC,v,x);
return ret;
}
ll findpre(int x)
{
splay(x,0);
int key=x;
x=LC;
while(RC) x=RC;
return val[key]-val[x];
}
ll findnext(int x)
{
splay(x,0);
int key=x;
x=RC;
while(LC) x=LC;
return val[x]-val[key];
}
}spt;
int main()
{
int i,j;
int n;
while(~scanf("%d",&n))
{
ll sum=0,tmp;
spt.init();
for(i=1;i<=n;i++)
{
if(scanf("%lld",&tmp)==EOF) tmp=0;
int ret=spt.insert(spt.root,tmp,0);
if(i==1) {sum+=tmp;continue;}
if(ret==0) continue;
ll tmp1=spt.findpre(ret),tmp2=spt.findnext(ret);
sum+=min(tmp1,tmp2);
}
printf("%lld\n",sum);
}
return 0;
}
hdoj2475 Box
通过这道题我终于理解了splay森林的建法以及splay的“序”
思路：用一对括号表示一个盒子，开始时splay中没有点，然后按照盒子间的拓扑序插入括号。这样就保证splay中起始的序是正确的。为了splay等操作的方便，盒子的编号和节点编号保持一致。开始的时候，将盒子(x,x+n)剪下来的时候用的是findpre(),findnext()操作找到盒子x的前驱和后继，然后splay(前驱，0)，splay(后继，前驱),然后减下x盒子，但是无情的TLE了，，然后改成splay(x,0),splay(x+n,x)。然后手工改变ch[x+n][1]和ch[x][0]，将ch[x+n][1]作为根，将ch[x][0]插入ch[x+n][1]左边为空的左孩子，这样也能把x盒子裁剪下来，然后能ac了。。（ps：为毛前后两者效率相差那么大啊）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100000+10
#define inf 0x3f3f3f3f
#define LC ch[x][0]
#define RC ch[x][1]
#define maxe 60000+10
#define maxn 60000+10
typedef struct Edge{
int to,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt,n,m;
void add(int u,int v)
{
edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
return;
}
int a[maxn];
int ind[maxn];
int q[maxn+10],iq;
struct SplayTree {
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int n;
void rotate(int x, bool f) { //旋转
int y = fa[x];
int z = fa[y];
ch[y][!f] = ch[x][f];
fa[ch[x][f]] = y;
fa[x] = z;
if (z) {
ch[z][ch[z][1] == y] = x;
}
ch[x][f] = y;
fa[y] = x;
}
void splay(int x, int g) { //把结点x转到结点g下
int y = fa[x];
/*
while (y != g) {
int z = fa[y];
bool f = (ch[y][0] == x);
if (z != g && f == (ch[z][0] == y)) {
rotate(y, f);
}
rotate(x, f);
y = fa[x];
}
*/
while (y != g) {
rotate(x, ch[y][0] == x);
y = fa[x];
}
}
void init()
{
ch[0][0] = ch[0][1] = fa[0] = 0;//0结点是空节点，代表没有
}
void initnode(int x)
{
ch[x][0]=ch[x][1]=0;fa[x]=0;
}
int findpre(int x)
{
x=LC;
while(RC) x=RC;
return x;
}
int findnext(int x)
{
x=RC;
while(LC) x=LC;
return x;
}
void insert1(int x)
{
initnode(x);
ch[x][1]=x+n;
initnode(x+n);
fa[x+n]=x;
}
void insert2(int x,int f)
{
splay(f,0);
int next=findnext(f);
splay(next,f);
initnode(x);
fa[x]=next;
ch[next][0]=x;
ch[x][1]=x+n;
initnode(x+n);
fa[x+n]=x;
return;
}
bool judge(int x,int y)
{
if(x==y) return 0;
splay(x,0);splay(x+n,x);
while(y)
{
if(ch[x+n][0]==y) return 0;
y=fa[y];
}
return 1;
}
void cutto(int x,int y)
{
int tmp;
if(a[x]==0 && y==0) return;
if(a[x])
{
fa[ch[x+n][1]]=0;
int xh=ch[x+n][1];
while(ch[xh][0]) xh=ch[xh][0];
ch[xh][0]=ch[x][0];
fa[ch[x][0]]=xh;
ch[x+n][1]=0;
ch[x][0]=0;
}
if(y!=0)
{
splay(y,0);
tmp=findnext(y);
splay(tmp,y);
fa[x]=tmp;
ch[tmp][0]=x;
}
a[x]=y;
return;
}
int query_rootbox(int x)
{
splay(x,0);
while(LC) x=LC;
return x;
}
void dfs(int x)
{
if(x==0) return;
dfs(LC);
printf("%d ",x);
dfs(RC);
}
}spt;
void topsort()
{
iq=0;
int i,j;
for(i=1;i<=n;i++)
if(ind[i]==0) q[iq++]=i;
for(i=0;i<=iq-1;i++)
{
int u=q[i];
for(j=head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].to;
ind[v]--;
if(!ind[v]) q[iq++]=v;
}
}
return;
}
void scan(int &num) //对G++使用
{
char in;
bool neg=false;
while(((in=getchar()) > '9' || in<'0') && in!='-') ;
if(in=='-')
{
neg=true;
while((in=getchar()) >'9' || in<'0');
}
num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
num*=10,num+=in-'0';
if(neg)
num=0-num;
}
int main()
{
int i,j;
int x,y;
bool flag=1;
while(~scanf("%d",&n))
{
spt.n=n;
cnt=0;memset(head,-1,sizeof(int)*(n+5));
memset(ind,0,sizeof(int)*(n+5));
for(i=1;i<=n;i++)
{
scan(a[i]);
if(a[i]==0) continue;
add(a[i],i);
ind[i]++;
}
topsort();
spt.init();
for(i=0;i<=iq-1;i++)
{
if(a[q[i]]==0) spt.insert1(q[i]);
else spt.insert2(q[i],a[q[i]]);
}
/*
for(i=1;i<=n;i++)
if(a[i]==0) {spt.splay(i,0);spt.dfs(i);printf("\n");}
*/
scanf("%d",&m);
char com[10];
if(!flag) printf("\n");else flag=0;
while(m--)
{
scanf("%s",com);
if(com[0]=='M')
{
scan(x);scan(y);
if(!spt.judge(x,y)) continue;
if(a[x]==y) continue;
spt.cutto(x,y);
/*
for(i=1;i<=n;i++)
if(a[i]==0) {spt.splay(i,0);spt.dfs(i);printf("\n");}
*/
continue;
}
scan(x);
printf("%d\n",spt.query_rootbox(x));
}
}
return 0;
}
bzoj 1208 宠物收养所
简单题，但是不知道为什么long long会TLE，int就A了。。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define N 100000+10
#define inf 0x3f3f3f3f
#define mod 1000000
struct SplayTree {
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
int val[N];//结点的值
int nodenum;
int num;
void pushup(int x)
{
sz[x]=sz[LC]+sz[RC]+1;
return;
}
void rotate(int x, bool f) { //旋转
int y = fa[x];
int z = fa[y];
ch[y][!f] = ch[x][f];
fa[ch[x][f]] = y;
fa[x] = z;
if (z) {
ch[z][ch[z][1] == y] = x;
}
ch[x][f] = y;
fa[y] = x;
pushup(y);
}
void splay(int x, int g) { //把结点x转到结点g下
int y = fa[x];
while (y != g) {
int z = fa[y];
bool f = (ch[y][0] == x);
if (z != g && f == (ch[z][0] == y)) {
rotate(y, f);
}
rotate(x, f);
y = fa[x];
}
pushup(x);
if (g == 0) {
root = x;
}
}
void rotateto(int k, int g)
{ //把第k个结点转到结点g下
int x = root;
while (sz[LC]!=k) {
if (k<sz[LC]) {
x=LC;
} else {
k-=sz[LC]+1;
x=RC;
}
}
splay(x,g);
return;
}
void init() {
root=nodenum=num=0;
ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;
ch[1][0]=ch[1][1]=0;fa[1]=0;sz[1]=2;ch[1][1]=2;val[1]=-inf;
ch[2][0]=ch[2][1]=0;fa[2]=1;sz[2]=1;val[2]=inf;
root=1;
num=2;
return;
}
void insert(int &x,int v,int f)
{
if(!x)
{
x=++num;
val[x]=v;
sz[x]=1;
ch[x][0]=ch[x][1]=0;fa[x]=f;
nodenum++;
return;
}
if(v<val[x]) insert(LC,v,x);
else insert(RC,v,x);
pushup(x);
return;
}
int findpre(int x)
{
x=LC;
while(RC) x=RC;
return x;
}
int findnext(int x)
{
x=RC;
while(LC) x=LC;
return x;
}
int rank(int v)
{
int x=root,cnt=0;
while(x)
{
if(val[x]==v) {cnt+=sz[LC];break;}
else if(v<val[x])
{
x=LC;
}
else
{
cnt+=sz[LC]+1;
x=RC;
}
}
return cnt;
}
void erase(int x)
{
nodenum--;
int tmp=rank(val[x]);
rotateto(tmp-1,0);
rotateto(tmp+1,root);
KT=0;
pushup(ch[root][1]);
pushup(root);
return;
}
int query(int b)
{
int tmp=rank(b);
rotateto(tmp,0);
int pre=findpre(root);
int v1=val[pre],v2=val[root];
if(abs(v1-b)<=abs(v2-b))
{
erase(pre);
return abs(v1-b);
}
erase(root);
return abs(v2-b);
}
}spt;
void scan(int &num) //对G++使用
{
char in;
bool neg=false;
while(((in=getchar()) > '9' || in<'0') && in!='-') ;
if(in=='-')
{
neg=true;
while((in=getchar()) >'9' || in<'0');
}
num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
num*=10,num+=in-'0';
if(neg)
num=0-num;
}
int main()
{
int i,j;
int n,a,b;
while(~scanf("%d",&n))
{
int sum=0;
int type;
spt.init();
while(n--)
{
scan(a);scan(b);
if(spt.nodenum==0)
{
type=a;
spt.insert(spt.root,b,0);
continue;
}
if(a==type)
{
spt.insert(spt.root,b,0);
continue;
}
sum=(sum+spt.query(b))%mod;
}
printf("%d\n",sum);
}
return 0;
}
bzoj1507 Editor
这题实在是坑，首先样例中的第一个Delete操作是非法的（题意说不会非法），而且不是故意非法而是10写成了11.。
其次insert时的字符串长度没告诉，RE几次，当然严格来说这个是自己做题疏忽，题意说总共insert的字符数是2M。所以一次最多插入2M的字符，数组应当开到2*10^6左右。。。
#include<stdio.h>
#include<string.h>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define inf 0x3f3f3f3f
#define N 2000000+10
struct SplayTree {
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
char val[N];//结点的值
int num;
int cur;
void pushup(int x)
{
sz[x]=sz[LC]+sz[RC]+1;
return;
}
void rotate(int x, bool f) { //旋转
int y = fa[x];
int z = fa[y];
ch[y][!f] = ch[x][f];
fa[ch[x][f]] = y;
fa[x] = z;
if (z) {
ch[z][ch[z][1] == y] = x;
}
ch[x][f] = y;
fa[y] = x;
pushup(y);
}
void splay(int x, int g) { //把结点x转到结点g下
int y = fa[x];
while (y != g) {
int z = fa[y];
bool f = (ch[y][0] == x);
if (z != g && f == (ch[z][0] == y)) {
rotate(y, f);
}
rotate(x, f);
y = fa[x];
}
pushup(x);
if (g == 0) {
root = x;
}
}
void rotateto(int k, int g) { //把第k个结点转到结点g下
int x = root;
while (sz[LC]!=k) {
if (k<sz[LC]) {
x = LC;
} else {
k-=sz[LC]+1;
x=RC;
}
}
splay(x,g);
return;
}
void newnode(int &x,char c)
{
x=++num;
ch[x][0]=ch[x][1]=fa[x]=0;
sz[x]=1;
val[x]=c;
return;
}
void init() {
cur=num=0;
ch[0][0] = ch[0][1] = fa[0] = sz[0] = 0;
ch[1][0]=ch[1][1]=fa[1]=val[1]=0;
ch[2][0]=ch[2][1]=fa[2]=val[2]=0;
ch[1][1]=2;fa[2]=1;
sz[1]=2;sz[2]=1;
num=2;
root=1;
return;
}
void make(int &x,int l,int r,char s[],int f)
{
if(l>r) return;
int mid=(l+r)/2;
newnode(x,s[mid]);
make(LC,l,mid-1,s,x);
make(RC,mid+1,r,s,x);
fa[x]=f;
pushup(x);
return;
}
void insert(int n,char s[])
{
rotateto(cur,0);
rotateto(cur+1,root);
make(KT,1,n,s,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
return;
}
void del(int n)
{
rotateto(cur,0);
rotateto(cur+n+1,root);
KT=0;
pushup(ch[root][1]);
pushup(root);
return;
}
void get(int n)
{
rotateto(cur,0);
rotateto(cur+n+1,root);
mid_dfs(KT);
printf("\n");
return;
}
void mid_dfs(int x)
{
if(!x) return;
mid_dfs(LC);
printf("%c",val[x]);
mid_dfs(RC);
}
}spt;
void get_line(char *s,int n)
{
char c;
for(int i=1;i<=n;i++)
{
c=getchar();
if(c=='\n') {i--;continue;}
s[i]=c;
}
return;
}
char s[2000000];
int main()
{
//freopen("F:\\test.in","r",stdin);
int i,j,k;
int t,n;
char com[20];
scanf("%d",&t);
spt.init();
while(t--)
{
scanf("%s",com);
if(!strcmp(com,"Move"))
{
scanf("%d",&k);
spt.cur=k;
continue;
}
if(!strcmp(com,"Insert"))
{
scanf("%d",&n);
get_line(s,n);
spt.insert(n,s);
continue;
}
if(!strcmp(com,"Delete"))
{
scanf("%d",&n);
spt.del(n);
continue;
}
if(!strcmp(com,"Get"))
{
scanf("%d",&n);
spt.get(n);
continue;
}
if(!strcmp(com,"Prev")) {spt.cur--;continue;}
if(!strcmp(com,"Next")) {spt.cur++;continue;}
}
return 0;
}
bzoj1269 文本编辑器editor
上一题的加强版，加入了旋转操作，这样就需要延迟标记啦。get操作变成输出一个字符。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define inf 0x3f3f3f3f
#define N 3000000+10
using namespace std;
struct SplayTree {
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
char val[N];//结点的值
int rev[N];
int num;
int cur;
void pushup(int x)
{
sz[x]=sz[LC]+sz[RC]+1;
return;
}
void rever(int x)
{
swap(LC,RC);
rev[x]^=1;
return;
}
void flip(int l,int r)
{
rotateto(l-1,0);
rotateto(r+1,root);
rever(KT);
return;
}
void pushdown(int x)
{
if(!rev[x]) return;
rever(LC);
rever(RC);
rev[x]=0;
return;
}
void rotate(int x, bool f) { //旋转
int y = fa[x];
int z = fa[y];
pushdown(y);
pushdown(x);
ch[y][!f] = ch[x][f];
fa[ch[x][f]] = y;
fa[x] = z;
if (z) {
ch[z][ch[z][1] == y] = x;
}
ch[x][f] = y;
fa[y] = x;
pushup(y);
}
void splay(int x, int g) { //把结点x转到结点g下
int y = fa[x];
pushdown(x);
while (y != g) {
int z = fa[y];
bool f = (ch[y][0] == x);
if (z != g && f == (ch[z][0] == y)) {
rotate(y, f);
}
rotate(x, f);
y = fa[x];
}
pushup(x);
if (g == 0) {
root = x;
}
}
void rotateto(int k, int g) { //把第k个结点转到结点g下
int x = root;
pushdown(x);
while (sz[LC]!=k) {
if (k<sz[LC]) {
x = LC;
} else {
k-=sz[LC]+1;
x=RC;
}
pushdown(x);
}
splay(x,g);
return;
}
void newnode(int &x,char c)
{
x=++num;
ch[x][0]=ch[x][1]=fa[x]=0;
sz[x]=1;
val[x]=c;
rev[x]=0;
return;
}
void init() {
cur=num=0;
ch[0][0] = ch[0][1] = fa[0] = sz[0]=rev[0] = 0;
ch[1][0]=ch[1][1]=fa[1]=val[1]=rev[1]=0;
ch[2][0]=ch[2][1]=fa[2]=val[2]=rev[2]=0;
ch[1][1]=2;fa[2]=1;
sz[1]=2;sz[2]=1;
num=2;
root=1;
return;
}
void make(int &x,int l,int r,char s[],int f)
{
if(l>r) return;
int mid=(l+r)/2;
newnode(x,s[mid]);
make(LC,l,mid-1,s,x);
make(RC,mid+1,r,s,x);
fa[x]=f;
pushup(x);
return;
}
void insert(int n,char s[])
{
rotateto(cur,0);
rotateto(cur+1,root);
make(KT,1,n,s,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
return;
}
void del(int n)
{
rotateto(cur,0);
rotateto(cur+n+1,root);
KT=0;
pushup(ch[root][1]);
pushup(root);
return;
}
void get()
{
rotateto(cur+1,0);
printf("%c\n",val[root]);
return;
}
void mid_dfs(int x)
{
if(!x) return;
mid_dfs(LC);
printf("%c",val[x]);
mid_dfs(RC);
}
}spt;
void get_line(char *s,int n)
{
char c;
for(int i=1;i<=n;i++)
{
c=getchar();
if(c=='\n') {i--;continue;}
s[i]=c;
}
return;
}
char s[3000000];
int main()
{
//freopen("F:\\test.in","r",stdin);
int i,j,k;
int t,n;
char com[20];
scanf("%d",&t);
spt.init();
while(t--)
{
scanf("%s",com);
if(!strcmp(com,"Move"))
{
scanf("%d",&k);
spt.cur=k;
continue;
}
if(!strcmp(com,"Insert"))
{
scanf("%d",&n);
get_line(s,n);
spt.insert(n,s);
continue;
}
if(!strcmp(com,"Delete"))
{
scanf("%d",&n);
spt.del(n);
continue;
}
if(!strcmp(com,"Get"))
{
spt.get();
continue;
}
if(!strcmp(com,"Rotate"))
{
scanf("%d",&n);
spt.flip(spt.cur+1,spt.cur+n);
continue;
}
if(!strcmp(com,"Prev")) {spt.cur--;continue;}
if(!strcmp(com,"Next")) {spt.cur++;continue;}
}
return 0;
}
11月1号完成此题
贴个链接，然后睡觉。。
用二分和平衡树完成
http://www.cnblogs.com/Booble/archive/2010/08/23/1806054.html
线段树优化dp，待做
poj3171
lightoj 1415
bzoj1835
uestc 1501
poj2376
poj2374
zjoi2010
fafu1231 http://acm.fafu.edu.cn/problem.php?id=1231
poj2355
hdoj4719
uestc1558
接下来要深入学习不单调的斜率优化dp，线段树深入，线性规划，分数规划，还有splay和可持久化的一些数据结构
hdoj3698 Let the light guide us——线段树优化dp
终于ac了，好久不写线段树，成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新，求区间最小值（包括历史值在内的最小值）。
dp[i][j]:前i行，且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m，超时
其实对于确定的i，j可以选择哪些k呢？abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心，f[i][j]为半径的区间和以k为中心，f[i-1][k]为半径的区间的重合部分，so。。求解每个阶段的时候，可以建立线段树[1,m]，然后不断加入上个阶段的dp值，dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])]，线段树维护最小值，注意lazy字段，lazy表示要往下更新的最小值，但是子孙节点的lazy有可能是小于它的（加入先对父区间更新为10，然后左子区间更新为8，这时候子区间的lazy就要比父区间小了），所以pushdown的时候，只有儿子节点的lazy没值或者小于父节点的lazy，才能重写这个儿子节点的lazy,否则可能导致结果偏大
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 110
#define maxm 5020
#define inf (0x3f3f3f3f)*2
int cost[maxn][maxm],f[maxn][maxm],dp[maxn][maxm];
int x[4*maxm];
int lazy[4*maxm];
int n,m;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id)
{
x[id]=min(x[lson],x[rson]);
return;
}
void pushdown(int id)
{
if(lazy[id]==-1) return;
if(lazy[lson]==-1 || lazy[id]<lazy[lson])
{
lazy[lson]=lazy[id];
}
if(lazy[rson]==-1 || lazy[id]<lazy[rson])
{
lazy[rson]=lazy[id];
}
x[lson]=min(x[lson],lazy[id]);
x[rson]=min(x[rson],lazy[id]);
lazy[id]=-1;
return;
}
void update(int id,int l,int r,int L,int R,int v)
{
if(L<=l && r<=R)
{
x[id]=min(x[id],v);
if(lazy[id]==-1 || v<lazy[id]) lazy[id]=v;
return;
}
pushdown(id);
int mid=l+(r-l)/2;
if(L<=mid) update(lson,l,mid,L,R,v);
if(R>mid) update(rson,mid+1,r,L,R,v);
pushup(id);
return;
}
int query(int id,int l,int r,int L,int R)
{
if(L<=l && r<=R) return x[id];
pushdown(id);
int mid=l+(r-l)/2,ret=inf;
if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
if(R>=mid+1) ret=min(ret,query(rson,mid+1,r,L,R));
return ret;
}
int solve()
{
int i,j;
for(i=2;i<=n;i++)
{
memset(x,inf,sizeof(int)*(4*m+10));
memset(lazy,-1,sizeof(int)*(4*m+10));
for(j=1;j<=m;j++)
update(1,1,m,max(1,j-f[i-1][j]),min(m,j+f[i-1][j]),dp[i-1][j]);
for(j=1;j<=m;j++)
dp[i][j]=cost[i][j]+query(1,1,m,max(1,j-f[i][j]),min(m,j+f[i][j]));
}
int ret=inf;
for(i=1;i<=m;i++) ret=min(ret,dp[n][i]);
return ret;
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&cost[i][j]);
dp[i][j]=(i==1?cost[i][j]:inf);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&f[i][j]);
printf("%d\n",solve());
}
return 0;
}
斯坦纳树相关
1.复杂度 O(n*3^k+cE*2^k)
c为SPFA复杂度中的常数，E为边的数量，但几乎达不到全部边的数量，甚至非常小。3^k来自于子集的转移sum{C(i,n)*2^i} (1<=i<=n)，用二项式展开求一下和。
2.如果最后可以是森林，最后还要dp一次，f[state]表示状态为state时的最小花费，首先
for(j=0;j<(1<<cc+1);j++)
for(i=1;i<=n;i++)
f[j]=min(f[j],dp[i][j]);
表示最后是一棵树的情况。然后
for(j=1;j<(1<<cc+1);j++)
{
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
{
if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
f[j]=min(f[j],f[sub]+f[j-sub]);
}
}
表示有一些独立的斯坦纳树组合，这些子集枚举时往往对state有约束条件，需要check。最后的答案state往往也有约束条件。
hdoj3311 Dig The Wells
加一个点0，向各个点连边，权为各个点挖井的费用，求包含n个和尚和0点的最小斯坦纳树。这样就解决了边权的问题
#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 2010
#define K 8
#define maxe 20000+10
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Edge{
int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,p;
int dp[maxn][1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
void add(int u,int v,int w)
{
edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
head[u]=cnt++;
return;
}
void init()
{
int i,j;
memset(dp,inf,sizeof(dp));
memset(st,0,sizeof(st));
memset(in,0,sizeof(in));
for(i=0;i<=n;i++) st[i]=(1<<i);
for(i=0;i<=n+m;i++)
dp[i][st[i]]=0;
return;
}
bool update(int &a,int b)
{
if(b<a) {a=b;return 1;}
return 0;
}
void spfa(int state)
{
while(!q.empty())
{
int u=q.front();
q.pop();
in[u][state]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;
int state2=state|st[v];
if(dp[u][state]+w<dp[v][state2])
{
dp[v][state2]=dp[u][state]+w;
if(state2!=state || in[v][state]) continue;
in[v][state]=1;q.push(v);
}
}
}
return;
}
void SteinerTree()
{
int i,j,sub;
for(j=1;j<(1<<n+1);j++)
{
for(i=0;i<=n+m;i++)
{
bool flag=1;
if(st[i] && (st[i]&j)==0) continue;
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
{
int x=sub|st[i],y=(j-sub)|st[i];
if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
flag=update(dp[i][j],dp[i][x]+dp[i][y]);
}
//if(!flag) continue;
if(dp[i][j]<inf)
q.push(i),in[i][j]=1;
}
spfa(j);
}
}
int main()
{
int i,j;
while(~scanf("%d%d%d",&n,&m,&p))
{
cnt=0;memset(head,-1,sizeof(head));
for(i=1;i<=n+m;i++)
{
int tmp;
scanf("%d",&tmp);
add(0,i,tmp);add(i,0,tmp);
}
for(i=1;i<=p;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
init();
SteinerTree();
int ans=inf;
for(i=0;i<=n+m;i++)
if(dp[i][(1<<n+1)-1]<ans) ans=dp[i][(1<<n+1)-1];
printf("%d\n",ans);
}
return 0;
}
hdoj4085 Peach Blossom Spring
最后可能是森林，还要dp一次
#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 60
#define K 13
#define maxe 3000+10
#define inf 0x3f3f3f3f//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m,k;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
head[u]=cnt++;
return;
}
void init()
{
int i;
memset(dp,inf,sizeof(dp));
memset(f,inf,sizeof(f));
memset(st,0,sizeof(st));
memset(in,0,sizeof(in));
for(i=1;i<=k;i++) st[i]=(1<<i-1);
for(i=n-k+1;i<=n;i++) st[i]=(1<<i-n+k+k-1);
for(int i=1;i<=n;i++)
dp[i][st[i]]=0;
return;
}
void spfa(int state)
{
while(!q.empty())
{
int u=q.front();
q.pop();
in[u][state]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;
int state2=state|st[v];
if(dp[u][state]+w<dp[v][state2])
{
dp[v][state2]=dp[u][state]+w;
if(state2!=state || in[v][state]) continue;
in[v][state]=1;q.push(v);
}
}
}
return;
}
bool check(int state)
{
int i,j;
int cnt=0;
for(i=0;i<k;i++)
{
if(state&(1<<i)) cnt++;
if(state&(1<<i+k)) cnt--;
}
return cnt==0;
}
int SteinerTree()
{
int i,j,sub;
for(j=1;j<(1<<(2*k));j++)
{
for(i=1;i<=n;i++)
{
if(st[i] && (st[i]&j)==0) continue;
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
{
int x=sub|st[i],y=(j-sub)|st[i];
if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
}
if(dp[i][j]>=inf) continue;
q.push(i);in[i][j]=1;
}
spfa(j);
}
for(j=0;j<(1<<2*k);j++)
for(i=1;i<=n;i++)
f[j]=min(f[j],dp[i][j]);
for(j=1;j<(1<<2*k);j++)
{
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
if(check(sub) && check(j-sub))
f[j]=min(f[j],f[sub]+f[j-sub]);
}
return f[(1<<2*k)-1];
}
int main()
{
int i,j;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
cnt=0;memset(head,-1,sizeof(head));
for(i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
init();
int ans=SteinerTree();
if(ans>=inf) printf("No solution\n");
else printf("%d\n",ans);
}
return 0;
}
zoj3613 Wormhole Transport
同样最后可能是森林，要dp一次
注意check函数，合法条件是资源数>=工厂数，最后的最大工厂数取决于集合中资源数
#include<stdio.h>
#include<string.h>
#include<queue>
#define maxn 210
#define K 10
#define maxe 20000+10
#define inf (0x3f3f3f3f)*2//注意wa很可能是inf不够大。。
using namespace std;
typedef struct Edge{
int w,to,next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt,n,m;
int dp[maxn][1<<K],f[1<<K],st[maxn];//非关键点的st值为0
bool in[maxn][1<<K];
queue<int> q;
int p[maxn],s[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v,int w)
{
edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];
head[u]=cnt++;
return;
}
int bit[10],cc;
void init()
{
int i;
memset(dp,inf,sizeof(dp));
memset(f,inf,sizeof(f));
memset(st,0,sizeof(st));
memset(in,0,sizeof(in));
//记得对关键点的st[]赋权
cc=-1;
for(i=1;i<=n;i++)
{
if(p[i] || s[i]){ cc++;st[i]=(1<<cc);bit[cc]=i;}
}
for(i=1;i<=n;i++)
dp[i][st[i]]=0;
return;
}
void spfa(int state)
{
while(!q.empty())
{
int u=q.front();
q.pop();
in[u][state]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;
int state2=state|st[v];
if(dp[u][state]+w<dp[v][state2])
{
dp[v][state2]=dp[u][state]+w;
if(state2!=state || in[v][state]) continue;
in[v][state]=1;q.push(v);
}
}
}
return;
}
bool check(int state)
{
int i,tmp1=0,tmp2=0;
for(i=0;i<=cc;i++)
{
if(state&(1<<i))
tmp1+=p[bit[i]],tmp2+=s[bit[i]];
}
return tmp1>=tmp2;
}
void SteinerTree()
{
int i,j,sub;
for(j=1;j<(1<<cc+1);j++)
{
for(i=1;i<=n;i++)
{
if(st[i] && (st[i]&j)==0) continue;
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
{
int x=sub|st[i],y=(j-sub)|st[i];
if(dp[i][x]>=inf || dp[i][y]>=inf) continue;
dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][y]);
}
if(dp[i][j]>=inf) continue;
q.push(i);in[i][j]=1;
}
spfa(j);
}
for(j=0;j<(1<<cc+1);j++)
for(i=1;i<=n;i++)
f[j]=min(f[j],dp[i][j]);
for(j=1;j<(1<<cc+1);j++)
{
for(sub=(j-1)&j;sub;sub=(sub-1)&j)
{
if(!check(sub) || !check(j-sub) || f[sub]>=inf || f[j-sub]>=inf) continue;
f[j]=min(f[j],f[sub]+f[j-sub]);
}
}
}
int cal(int state)
{
int i,j,ans=0;
for(i=0;i<=cc;i++)
{
if(state&(1<<i))
ans+=s[bit[i]];
}
return ans;
}
int main()
{
int i,j;
int u,v,w;
while(~scanf("%d",&n))
{
cnt=0;memset(head,-1,sizeof(head));
memset(p,0,sizeof(p));memset(s,0,sizeof(s));
for(i=1;i<=n;i++)
{
scanf("%d%d",&p[i],&s[i]);
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
init();
SteinerTree();
int ans=0,cost=0;
for(j=0;j<(1<<cc+1);j++)
{
if(!check(j) || f[j]>=inf) continue;
int tmp=cal(j);
if(tmp>ans)
{
ans=tmp;
cost=f[j];
}
else if(tmp==ans && f[j]<cost) cost=f[j];
}
printf("%d %d\n",ans,cost);
}
return 0;
}
hdoj3401 Trade
单调队列优化dp，太菜了做不出来啊，看了题解才ok
dp[i][j]表示第i天有j张股票的最大money
dp[i][j]=max{dp[i-1][j],dp[i-w-1][k]-ap[i]*(j-k),dp[i-w-1][k]+bp[i]*(k-j)}
其中第二个决策表示买入股票，第三个决策表示卖出股票
复杂度太高需需优化
考虑第二个决策：dp[i-w-1][k]-ap[i]*(j-k)=dp[i-w-1][k]+ap[i]*k-ap[i]*j
可见对于dp[i][j]，要找的是dp[i-w-1][k]+ap[i]*k的最大值，因为ap[i]*j在当前阶段和状态确定后是常数。用单调队列将决策那一维优化到O(n)
第三个决策也可以这样考虑
#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int ap[2010],bp[2010],as[2010],bs[2010],dp[2010][2010],q[2010],num[2010],head,tail;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int main()
{
int i,j,T;
int t,maxp,w;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&t,&maxp,&w);
for(i=1;i<=t;i++) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
memset(dp,-inf,sizeof(dp));
for(i=1;i<=1+w;i++)
{
for(j=0;j<=min(maxp,as[i]);j++)
dp[i][j]=-ap[i]*j;
}
for(i=2;i<=t;i++)
{
for(j=0;j<=maxp;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
head=0;tail=-1;
for(j=0;j<=maxp;j++)
{
int bound=max(0,j-as[i]);
while(head<=tail && num[head]<bound) head++;
if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-ap[i]*j);
int tmp=i-w-1<0?0:i-w-1;
while(head<=tail && dp[tmp][j]+ap[i]*j>=q[tail]) tail--;
q[++tail]=dp[tmp][j]+ap[i]*j;num[tail]=j;
}
head=0;tail=-1;
for(j=maxp;j>=0;j--)
{
int bound=min(maxp,j+bs[i]);
while(head<=tail && num[head]>bound) head++;
if(head<=tail) dp[i][j]=max(dp[i][j],q[head]-bp[i]*j);
int tmp=i-w-1<0?0:i-w-1;
while(head<=tail && dp[tmp][j]+bp[i]*j>=q[tail]) tail--;
q[++tail]=dp[tmp][j]+bp[i]*j;num[tail]=j;
}
}
int ans=dp[t][0];
for(i=1;i<=maxp;i++)
if(dp[t][i]>ans) ans=dp[t][i];
printf("%d\n",ans);
}
return 0;
}
http://hi.baidu.com/mobius_strip/item/a0152244c47e4ec9c1a592f6
hdoj4122 Alice’s mooncake shop
哎，一道简单的单调队列比赛时候居然没做出来，很不应该。
假设第i小时定的月饼在第j小时或第k小时制作，那么j和k哪个更优呢？
(i-j)*s+cost[j]<(i-k)*s+cost[k]=====》cost[j]-j*s<cost[k]-k*s
可见，对于第i小时定的月饼用哪个决策与i无关:i choose min{cost[j]-j*s}其中i-T<=j<=i
区间最值，下界非递减，显然是单调队列。。
注意可能有两个及两个以上订单在同一小时。。
#include<stdio.h>
#include<string.h>
#include<map>
#include<string>
using namespace std;
typedef __int64 ll;
const int maxm=1e5+10;
map<string,int> mon;
ll num[maxm],cost[maxm];
ll cc[15];
bool is(ll year)
{
if((year%100 && year%4==0) || (year%400==0)) return 1;
return 0;
}
void cal(string m,ll date,ll year,ll h,ll r)
{
int i,j;
ll tmp=0;
for(i=2000;i<=year-1;i++) tmp+=(is(i)?366:365);
for(i=1;i<=mon[m]-1;i++) tmp+=((is(year)&&(i==2))?29:cc[i]);
tmp+=date-1;tmp=tmp*24+h+1;
num[tmp]+=r;
return;
}
ll q[maxm],flag[maxm];
int head,tail;
int main()
{
int i,j;
ll n,m;
mon["Jan"]=1;mon["Feb"]=2;mon["Mar"]=3;mon["Apr"]=4;mon["May"]=5;mon["Jun"]=6;mon["Jul"]=7;mon["Aug"]=8;mon["Sep"]=9;mon["Oct"]=10;mon["Nov"]=11;mon["Dec"]=12;
cc[1]=31;cc[2]=28;cc[3]=31;cc[4]=30;cc[5]=31;cc[6]=30;cc[7]=31;cc[8]=31;cc[9]=30;cc[10]=31;cc[11]=30;cc[12]=31;
while(~scanf("%I64d%I64d",&n,&m) && !(n==0 && m==0))
{
char month[5];ll date,year,h,r;
memset(num,0,sizeof(ll)*(m+3));
for(i=1;i<=n;i++)
{
scanf("%s%I64d%I64d%I64d%I64d",month,&date,&year,&h,&r);
cal((string)month,date,year,h,r);
}
ll T,S;
scanf("%I64d%I64d",&T,&S);
for(i=1;i<=m;i++) scanf("%I64d",&cost[i]);
ll ans=0;head=0;tail=-1;
for(i=1;i<=m;i++)
{
while(head<=tail && q[tail]>=cost[i]-i*S) tail--;
q[++tail]=cost[i]-i*S;flag[tail]=(ll)i;
while(head<=tail && flag[head]<(ll)(i-T)) head++;
if(num[i]==0) continue;
ans+=(q[head]+i*S)*num[i];
}
printf("%I64d\n",ans);
}
return 0;
}
hdoj3507 Print Article
比较水的斜率优化dp
dp[i]：前i个词的最小cost
s[i]：前i个词的cost之和
w[j,i]:把第j到i个词分在一行的cost
dp[i]=min{dp[j]+w[j+1,i]}(0<=j<=i-1)
其中w[j,i]=(s[i]-s[j])^2+m
dp[i]的是式子展开：dp[i]=min{dp[j]+s[j]^2-2s[i]*s[j]}+s[i]^2+m
k=2s[i]
x=s[j]
y=dp[j]+s[j]^2
点的横坐标非递减，所以可以用单调队列维护凸壳，因为斜率非递减(即决策单调)，所以可以均摊O(1)的求出最优决策是哪个，总复杂度O(n)
//////////////////
关于决策单调的另一种严格证明：
即证明w[i,j]满足四边形不等式：对于i<i’<j’<j,w[i,j']+w[i',j]<=w[i,j]+w[i',j']
(s[j']-s[i])^2+(s[j]-s[i'])^2<=(s[j]-s[i])^2+(s[j']-s[i'])^2
继续化简:-2s[i]s[j']-2s[i']s[j]<=-2s[i]s[j]-2s[i']s[j']
s[i]s[j']+s[i']s[j]>=s[i]s[j]+s[i']s[j']
(s[i']-s[i])(s[j]-s[j'])>=0
因为i<i’<j’<j,(s[i']-s[i])(s[j]-s[j'])>=0显然成立，所以w[i,j]满足四边形不等式，决策单调
#include<stdio.h>
#include<string.h>
int const maxn=5e5+10;
double const eps=1e-8;
typedef struct Point{
int x,y;
Point(){}
Point(int _x,int _y):x(_x),y(_y){}
}Point;
Point operator -(const Point &a,const Point &b)
{
return Point(a.x-b.x,a.y-b.y);
}
int s[maxn],dp[maxn];
int n,m;
int head,tail;
Point q[maxn];
int cal(Point a,int k)
{
return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
Point p1=b-a,p2=c-b;
return (double)(p1.y/(p1.x+eps))<(double)(p2.y/(p2.x+eps));
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
s[0]=0;dp[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&j);
s[i]=s[i-1]+j;
}
head=tail=0;
q[0]=Point(0,0);
for(i=1;i<=n;i++)
{
int k=-2*s[i];
while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
dp[i]=cal(q[head],k)+s[i]*s[i]+m;
Point p(s[i],dp[i]+s[i]*s[i]);
while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
q[++tail]=p;
}
printf("%d\n",dp[n]);
}
return 0;
}
hdoj2829 Lawrence
我擦。。去掉一个语句居然就ac了，纠结n久。这题貌似不用斜率有优化，用四边形不等式优化也行。具体明天再说。。
第一道状态是二维，决策一维的斜率优化dp，其实和状态一维的差不多，无非多了层外层循环。每个阶段都用一下单调队列。。
#include<stdio.h>
#include<string.h>
const int maxn=1010;
const int inf=0x3f3f3f3f;
typedef struct Point{
int x,y;
Point(){}
Point(int _x,int _y)
{
x=_x;y=_y;
}
}Point;
Point operator -(const Point &a,const Point &b)
{
return Point(a.x-b.x,a.y-b.y);
}
int cal(Point a,int k)
{
return a.y+k*a.x;
}
bool cmp(Point a,Point b,Point c)
{
Point p1=b-a,p2=c-b;
return (p1.y*1.0/p1.x)<(p2.y*1.0/p2.x);
}
Point q[maxn];
int s[maxn],c[maxn],dp[maxn][maxn];
int head,tail,n,m;
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
{
c[0]=s[0]=0;
for(i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
s[i]=s[i-1]+tmp;
c[i]=c[i-1]+tmp*s[i];
}
memset(dp,0,sizeof(dp));
for(j=1;j<=n;j++) dp[1][j]=0;
for(i=1;i<=n;i++)
dp[i][1]=s[i]*s[i]-c[i];
for(j=2;j<=m+1;j++)
{
head=tail=0;
q[0]=Point(s[1],dp[1][j-1]+c[1]);
for(i=2;i<=n;i++)
{
//if(i<j+1) continue;
int k=-s[i];
while(head<tail && cal(q[head],k)>=cal(q[head+1],k)) head++;
dp[i][j]=cal(q[head],k)+s[i]*s[i-1]-c[i-1];
Point p(s[i],dp[i][j-1]+c[i]);
while(head<tail && !cmp(q[tail-1],q[tail],p)) tail--;
q[++tail]=p;
}
}
printf("%d\n",dp[n][m+1]);
}
return 0;
}
bzoj1010 玩具装箱toy
斜率优化dp第一题，纠结了n久。。最后输出改成%I64d就PE，要%lld才能ac，而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp，记下几点：
(1)求最大值，维护上凸壳；求最小值，维护下凸壳；
(2)当点的横坐标单调，且斜率单调时，此时决策是单调的（即满足四边形不等式），可以用单调队列从前往后找最优决策(怎么找？只有最优决策点的值比两侧都要优，注意只有二字)，找到之后前面的都是无用决策了，插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的，而斜率不单调，这时候决策是不单调的，但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1
正确做法是用平衡树维护动态凸壳。（我擦，说着简单，写着蛋疼无比）(这种情况细节还不太会，有待学习)
#include<stdio.h>
typedef long long ll;
const int maxn=5e4+10;
typedef struct Node{
ll x,y;
}Node;
Node q[maxn];
int n;
ll s[maxn],L,dp[maxn];
int head,tail;
ll cal(ll x,ll y,ll k)
{
return y-2*k*x;
}
bool xielv(Node a,Node b,Node c)
{
ll x1=a.x,y1=a.y,x2=b.x,y2=b.y,x3=c.x,y3=c.y;
return (y2-y1)*(x3-x2)<(y3-y2)*(x2-x1);
}
int main()
{
int i,j;
while(~scanf("%d%lld",&n,&L))
{
s[0]=0;dp[0]=0;
ll tmp;
for(i=1;i<=n;i++)
{
scanf("%lld",&tmp);s[i]=s[i-1]+tmp;
}
head=tail=0;q[0].x=0;q[0].y=0;
for(i=1;i<=n;i++)
{
ll k=s[i]+i-1-L,x,y;
while(head<tail && cal(q[head].x,q[head].y,k)>=cal(q[head+1].x,q[head+1].y,k))
head++;
dp[i]=cal(q[head].x,q[head].y,k)+k*k;
x=s[i]+i;y=dp[i]+x*x;
Node tt;tt.x=x;tt.y=y;
while(head<tail && !xielv(q[tail-1],q[tail],tt))
tail--;
q[++tail]=tt;
}
printf("%lld\n",dp[n]);
}
return 0;
}