SDOI2016 Round1

1 储能表

有一个\(n\)行\(m\)列的表格，行从\(0\)到\(n - 1\)编号，列从\(0\)到\(m - 1\)编号。
每个格子都储存着能量。最初，第\(i\)行第\(j\)列的格子储存着\((i \ {\rm xor} \ j)\)点能量。所以，整个表格储存的总能量是，\(\sum_{i = 0} ^ {n - 1} \sum_{j = 0} ^ {m - 1} (i \ {\rm xor} \ j)\) 随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少\(1\)。显然，一个格子的能量减少到\(0\)之后就不会再减少了。
也就是说，\(k\)个时间单位后，整个表格储存的总能量是，\(\sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} \max((i \ {\rm xor} \ j) - k, 0)\) 给出一个表格，求\(k\)个时间单位后它储存的总能量。
由于总能量可能较大，输出时对\(p\)取模。
\(T <= 5000\), \(n,m,k <= 10^{18}\), \(p <= 10^9\).

数位DP
\(f[x][0/1][0/1][0/1]\)为当前状态的和，\(g[x][0/1][0/1][0/1]\)为当前状态的个数
第一维表示到二进制的第\(x\)位，第二维表示当前枚举的\(i\)与\(n\)在前\(x\)位的关系为\(<\)或\(=\)，第三维\(j\)与\(m\)，第四维表示\(i \ {\rm xor} \ j\)为\(k\)的关系为\(>\)或\(=\);
答案就是\(f[0][0][0][0]\);

然后设原串\(n,m,k\)在当前第i位的值为\(x,y,z\)，枚举这一位的数值\(xx,yy,zz\)和上一位的状态\(a,b,c\)，可以计算出这一位的状态\(aa,bb,cc\)，然后
\(g[i][aa][bb][cc]+=g[i+1][a][b][c];\)
\(f[i][aa][bb][cc]+=f[i+1][a][b][c]+(zz-z)\times (1<<i)\times g[i+1][a][b][c];\)

#include<cstring>
#include<cstdio>
using namespace std;
long long T,n,m,k,mod,f[62][2][2][2],g[62][2][2][2];
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);
		g[61][1][1][1]=1;
		for(int i=60;i>=0;i--)
		{
			int x=(n>>i)&1,y=(m>>i)&1,z=(k>>i)&1;
			for(int a=0;a<2;a++)
			 for(int b=0;b<2;b++)
			  for(int c=0;c<2;c++)
			   if(f[i+1][a][b][c]||g[i+1][a][b][c])
			   {
			  	 for(int xx=0;xx<2;xx++)
			  	  for(int yy=0;yy<2;yy++)
			  	  {
			  	  	int zz=xx^yy;
			  	   	if((a&&x<xx)||(b&&y<yy)||(c&&z>zz)) continue;
			  	   	int aa=(a&&x==xx),bb=(b&&y==yy),cc=(c&&z==zz);
			  	   	g[i][aa][bb][cc]=(g[i][aa][bb][cc]+g[i+1][a][b][c])%mod;
			  	   	f[i][aa][bb][cc]=(f[i][aa][bb][cc]+f[i+1][a][b][c]+((zz-z)+mod)%mod*((1ll<<i)%mod)%mod*g[i+1][a][b][c]%mod)%mod;
			  	  }
			   }
		}
		printf("%lld\n",f[0][0][0][0]);
	}
}

2 数字配对

有\(n\)种数字，第\(i\)种数字是\(a_i\)、有\(b_i\)个，权值是\(c_i\)。
若两个数字\(a_i\)、\(a_j\)满足，\(a_i\)是\(a_j\)的倍数，且\(a_i \div a_j\)是一个质数，那么这两个数字可以配对，并获得\(c_i \times c_j\)的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于\(0\)的前提下，求最多进行多少次配对。
\(n <= 200\), \(a_i <= 10^9\), \(b_i , \mid c_i \mid <= 10^5\).

先把能连的连起来，然后把图变成二分图
建图，费用为\(-c[i]\times c[j]\)，跑费用流（其实就是最大费用最大流）
由于SPFA法的费用流每次的单位费用一定最优，所以当最后一次\(<0\)时直接除一下就好了（当然二分答案也可以过了，2333）

#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1e5+1;
const long long inf=1e16;
int n,S,T,L,R,mid,Flow;
int totp,notp[maxn],prime[maxn];
int col[210],head1[210],next1[2000],to1[2000];
int ecnt,used[210],head[210],pre[210],to[2000],rest[2000],next[2000];
long long Cost,ds[210],cost[2000];
queue<int> Q;
struct node { int a,b,c; } a[210];
inline bool cmp(const node &x,const node &y) { return x.a<y.a; }
inline void PRE()
{
	notp[1]=1;
	for(int i=2;i<maxn;i++)
	{
		if(!notp[i]) prime[++totp]=i;
		for(int j=1,p=2;j<=totp&&p*i<maxn;p=prime[++j])
		{
			notp[p*i]=1;
			if(!(i%p)) break;
		}
	}
}
inline bool isPrime(int x)
{
	if(x<maxn) return !notp[x];
	for(int i=1,p=2;i<=totp&&p*p<=x;p=prime[++i])
	  if(!(x%p)) return 0;
	return 1;
}
inline void Dfs(int x)
{
	for(int e=head1[x],y=to1[e];e;e=next1[e],y=to1[e])
	  if(!col[y]) col[y]=col[x]^1,Dfs(y);
}
inline void Addedge(int x,int y,int r,long long c)
{
	to[++ecnt]=y;rest[ecnt]=r;cost[ecnt]=c;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;cost[ecnt]=-c;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Spfa()
{
	for(int i=0;i<=T;i++) ds[i]=inf,used[i]=0;
	Q.push(S);ds[S]=0;used[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();used[x]=0;
		for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&ds[x]+cost[e]<ds[y])
		  {
		  	ds[y]=ds[x]+cost[e];
		  	pre[y]=e;
		  	if(!used[y]) Q.push(y),used[y]=1; 
		  }
	}
	return ds[T]<inf;
}
inline pair<int,long long> Update()
{
	int flow=0x7fffffff;
	for(int e=pre[T];e;e=pre[to[e^1]])
	  if(rest[e]<flow) flow=rest[e];
	for(int e=pre[T];e;e=pre[to[e^1]])
	  rest[e]-=flow,rest[e^1]+=flow;
	return make_pair(flow,(long long)flow*ds[T]);
}
int main()
{
	scanf("%d",&n);PRE();T=n+1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].b);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].c);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<i;j++)
	    if(!(a[i].a%a[j].a)&&isPrime(a[i].a/a[j].a))
	    {
	    	to1[++ecnt]=j,next1[ecnt]=head1[i],head1[i]=ecnt;
	    	to1[++ecnt]=i,next1[ecnt]=head1[j],head1[j]=ecnt;
	    }
	for(int i=1;i<=n;i++) if(!col[i]) col[i]=2,Dfs(i);
	ecnt=1;
	for(int i=1;i<=n;i++)
	{
		if(col[i]&1)
		{
			Addedge(S,i,a[i].b,0);
			for(int e=head1[i],j=to1[e];e;e=next1[e],j=to1[e])
	  		  Addedge(i,j,0x3fffffff,-(long long)a[i].c*a[j].c);
		}
		else Addedge(i,T,a[i].b,0);
	}
	while(Spfa())
	{
		pair<int,long long> aa=Update();
		if(Cost-aa.second<0) {printf("%d\n",Flow+Cost/ds[T]);return 0;	}
		else Flow+=aa.first,Cost-=aa.second;
	} 
	printf("%d\n",Flow);
}

3 游戏

Alice 和 Bob 在玩一个游戏。
游戏在一棵有\(n\)个点的树上进行。最初，每个点上都只有一个数字，那个数字是\(123456789123456789\)。
有时，Alice 会选择一条从\(s\)到\(t\)的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点\(r\)，若\(r\)与\(s\)的距离是\(dis\)，那么 Alice 在点\(r\)上添加的数字是\(a \times dis + b\)。
有时，Bob 会选择一条从\(s\)到\(t\)的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。
\(n,m \leq 100000\), \(\mid a \mid \leq 10000\), \(\mid b \mid \leq 10^9\), \(1 \leq w \leq 10^9\)

对于一次修改，设x为S到T路径上的一点：
1 . 如果S和x在同一边，则\(dist(S,x)\times a + b = - a\times ds[x] + a\times ds[S] + b\) 2 . 如果S和x不在一边，则\(dist(S,x)\times a + b = a\times ds[x] + a\times ds[S] - 2\times a\times ds[lca] + b\) 都可以看作\(y = A \times ds[x] + B\)的形式

所以树剖一下，就变成了在区间上添加线段，求区间上的最小的y值，然后用传说中的超哥线段树解决
每个区间维护：
1 . 区间的最小值
2 . 在区间中点取到最小值的线段

更新：
1 . 如果新线段的两端都小于原线段，则完全覆盖；
2 . 如果都大于，则舍去；
3 . 否则把在中点出小的线段留下，并下传

#include <iostream>
#include <cstdio>
const int N=100005;
const long long INF=123456789123456789LL;
int n,m,tot,head[N],next[N<<1],to[N<<1],cost[N<<1];
int fa[N],dep[N],son[N],size[N],dfn[N],st[N],top[N];
long long ds[N],dis[N];
struct node { int l,r,ls,rs,a; long long b,min; } t[N<<1];
inline int DFS(int x)
{
    dep[x]=dep[fa[x]]+1;size[x]=1;
    for(int e=head[x],y=to[e];e;y=to[e=next[e]])
        if(y!=fa[x])
        {
            fa[y]=x; dis[y]=dis[x]+cost[e];
            DFS(y); size[x]+=size[y];
            if(size[y]>size[son[x]]) son[x]=y;
        }
}
inline int DFS(int x,int t)
{
    dfn[x]=++tot;st[tot]=x;
    top[x]=t;ds[tot]=dis[x];
    if(son[x]) DFS(son[x],t);
    for(int e=head[x],y=to[e];e;y=to[e=next[e]])
        if(y!=fa[x]&&y!=son[x])
            DFS(y,y);
}
inline void Build(int x,int l,int r)
{
    t[x].l=l;t[x].r=r;t[x].b=t[x].min=INF;
    if(l==r) return;
    int mid=(l+r)>>1;
    Build(t[x].ls=++tot,l,mid);
    Build(t[x].rs=++tot,mid+1,r);
}
inline void Add(int x,int l,int r,int A,long long B)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        long long prel=t[x].a*ds[t[x].l]+t[x].b,prer=t[x].a*ds[t[x].r]+t[x].b;
        long long nowl=A*ds[t[x].l]+B,nowr=A*ds[t[x].r]+B;
        t[x].min=std::min(t[x].min,std::min(nowl,nowr));
        if(nowl<prel&&nowr<prer) t[x].a=A,t[x].b=B;
        else if((prel<nowl)!=(prer<nowr))
        {
            int mid=(t[x].l+t[x].r)>>1;
            long long prem=t[x].a*ds[mid]+t[x].b,nowm=A*ds[mid]+B;
            if(nowm<prem) std::swap(A,t[x].a),std::swap(B,t[x].b);
            if((prel<nowl)!=(prem<nowm)) Add(t[x].ls,l,r,A,B);
                else Add(t[x].rs,l,r,A,B);
        }
        return;
    }
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid) Add(t[x].ls,l,r,A,B);
    if(mid<r)  Add(t[x].rs,l,r,A,B);
    t[x].min=std::min(t[x].min,std::min(t[t[x].ls].min,t[t[x].rs].min));
}
inline long long Quary(int x,int l,int r)
{
    if(l<=t[x].l&&t[x].r<=r) return t[x].min;
    int mid=(t[x].l+t[x].r)>>1;
    long long min=std::min(t[x].a*ds[std::max(l,t[x].l)]+t[x].b,t[x].a*ds[std::min(r,t[x].r)]+t[x].b);
    if(l<=mid) min=std::min(min,Quary(t[x].ls,l,r));
    if(mid<r)  min=std::min(min,Quary(t[x].rs,l,r));
    return min;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,ecnt=0,x,y,z;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        to[++ecnt]=y;next[ecnt]=head[x];cost[ecnt]=z;head[x]=ecnt;
        to[++ecnt]=x;next[ecnt]=head[y];cost[ecnt]=z;head[y]=ecnt;
    }
    DFS(1);DFS(1,1);
    Build(tot=1,1,n);
    for(int i=1,opt,S,T,x,y,A,B;i<=m;i++)
    {
        scanf("%d%d%d",&opt,&S,&T);
        if(opt==1)
        {
            scanf("%d%d",&A,&B);
            for(x=S,y=T;top[x]!=top[y];x=fa[top[x]])
                if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
            long long Bl=A*dis[S]+B,Br=A*dis[S]-2*A*dis[std::min(x,y)]+B;
            for(x=S,y=T;top[x]!=top[y];)
            {
                if(dep[top[x]]>dep[top[y]])
                    Add(1,dfn[top[x]],dfn[x],-A,Bl),x=fa[top[x]];
                else Add(1,dfn[top[y]],dfn[y],A,Br),y=fa[top[y]];
            }
            if(dep[x]<dep[y]) Add(1,dfn[x],dfn[y],A,Br);
                else Add(1,dfn[y],dfn[x],-A,Bl);
        }
        else
        {
            long long ans=INF;
            for(x=S,y=T;top[x]!=top[y];x=fa[top[x]])
            {
                if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
                ans=std::min(ans,Quary(1,dfn[top[x]],dfn[x]));
            }
            if(dep[x]>dep[y]) std::swap(x,y);
            printf("%lld\n",std::min(ans,Quary(1,dfn[x],dfn[y])));
        }
    }
}

4 生成魔咒

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符\(1\)、\(2\)拼凑起来形成一个魔咒串\([1, 2]\)。
一个魔咒串\(S\)的非空字串被称为魔咒串\(S\)的生成魔咒。
例如\(S = [1, 2, 1]\)时，它的生成魔咒有\([1]\)、\([2]\)、\([1, 2]\)、\([2, 1]\)、\([1, 2, 1]\)五种。\(S = [1, 1, 1]\)时，它的生成魔咒有\([1]\)、\([1, 1]\)、\([1, 1, 1]\)三种。
最初\(S\)为空串。共进行\(n\)次操作，每次操作是在\(S\)的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串\(S\)共有多少种生成魔咒。
\(1 \leq n \leq 100000\)；用来表示魔咒字符的数字\(x\)满足\(1 \leq x \leq 10 ^ 9\)。

这不是和hashit一样吗，来一发后缀平衡树，多一个log无所谓了。。。
正解是后缀数组+ST表

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int N=100005;
const int base=1e9+9;
unsigned long long ha[N],power[N]={1};
int n,s[N],height;
long long ans;
unsigned long long HASH(int x,int y)
{
	return ha[y]-ha[x-1]*power[y-x+1];
}
int LCP(int x,int y)
{
	int l=0,r=min(x,y),mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(HASH(x-mid+1,x)==HASH(y-mid+1,y)) l=mid; 
		else r=mid-1;
	}
	return l;
}
struct cmp
{
	bool operator() (const int &x,const int &y)
	{
		int t=LCP(x,y);return s[x-t]<s[y-t];
	}
};
set<int,cmp> S;
set<int,cmp>::iterator pre,nxt;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		ha[i]=ha[i-1]*base+s[i];
		power[i]=power[i-1]*base;
		pre=nxt=S.insert(i).first;height=0;
		if(pre!=S.begin()) height=LCP(*--pre,i);
		if(++nxt!=S.end()) height=max(height,LCP(*nxt,i));
		printf("%lld\n",ans+=i-height);
	}
}

5 排列计数

求有多少种长度为\(n\)的序列\(A\)，满足以下条件：
1 .\(1\)~\(n\)这\(n\)个数在序列中各出现了一次
2 . 若第\(i\)个数\(A[i]\)的值为\(i\)，则称\(i\)是稳定的。序列恰好有\(m\)个数是稳定的。
满足条件的序列可能很多，序列数对\(10 ^ 9 + 7\)取模。
\(T = 500000\)，\(n,m \leq 1000000\)。

就是一个错排了
把什么阶乘呀，阶乘逆元呀，错排呀都处理出来
然后\(ans = g[n-m] \times C(n,m)\)

#include<iostream>
#include<cstdio>
const int mod=1e9+7;
int T,maxn,maxm,a[500001],b[500001];
long long f[1000001]={1},g[1000001]={1},ni[1000001];
long long power(long long a,int b)
{
	long long re=1;
	for(;b;b>>=1,a=a*a%mod)
	  if(b&1) re=re*a%mod;
	return re;
}
int main()
{
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		maxn=std::max(maxn,a[i]);
		maxm=std::max(maxm,a[i]-b[i]);
	}
	for(int i=1;i<=maxn;i++) f[i]=f[i-1]*i%mod;
	ni[maxn]=power(f[maxn],mod-2);
	for(int i=maxn;i;i--) ni[i-1]=ni[i]*(i)%mod;
	for(int i=2;i<=maxm;i++) g[i]=(g[i-1]+g[i-2])%mod*(i-1)%mod;
	for(int i=1;i<=T;i++)
	{
		int n=a[i],m=b[i];
		if(n<m) printf("0\n");
		else printf("%lld\n",g[n-m]*f[n]%mod*ni[m]%mod*ni[n-m]%mod);
	} 
}

6 征途

Pine 开始了从\(S\)地到\(T\)地的征途。
从\(S\)地到\(T\)地的路可以划分成\(n\)段，相邻两段路的分界点设有休息站。
Pine 计划用\(m\)天到达\(T\)地。除第\(m\)天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。
设方差是\(v\)，可以证明，\(v \times m ^ 2\)是一个整数。为了避免精度误差，输出结果时输出\(v \times m ^ 2\)。
\(1 \leq n \leq 3000\)。保证从\(S\)到\(T\)的总路程不超过\(30000\)。

设每一天的路程为\(a_i\)，\(S=\sum\limits_{i=1}^n a_i\) \(ans = m^2 \times \sum\limits_{i=1}^m \frac{(a_i - \frac{S}{m}) ^ 2}{m}\) 化简得\(ans = m \times \sum\limits_{i=1}^m a^2 - S^2\) 只要求\(\sum\limits_{i=1}^m a^2\)就好了

设\(f[i][j]\)表示前j段路分成i天的平方和，则\(f[i][j] = \min\limits_{k = 1} ^ {i - 1}\{ f[i - 1][k] + (s[j] - s[k]) ^ 2 \}\)

设\(a>b\)且\(a\)比\(b\)优，则有\(f[i - 1][a] + (s[j] - s[a]) ^ 2 < f[i - 1][b] + (s[j] - s[b]) ^ 2\) 化简得\(\frac{(f[i-1][a] + s[a] ^ 2) - (f[i-1][b] + s[b] ^ 2)}{s[a] - s[b]} < 2\times s[j]\)

然后斜率优化
如果头上两个点的斜率小于\(2\times s[j]\)则说明后边的更优，就把head删掉，最后用head更新一定是当前最优
加上一个点的时候维护下凸包就好了

#include<iostream>
#include<cstring>
#include<cstdio>
int n,m,head,tail,sum[3001],q[3001];
long long f[3001],g[3001];
double K(int x,int y)
{
	return double(g[x]-g[y]+sum[x]*sum[x]-sum[y]*sum[y])/(double)(sum[x]-sum[y]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
	memset(f,0x7f,sizeof(g));f[0]=0;
	for(int j=1;j<=m;j++)
	{
		memcpy(g,f,sizeof(f));memset(f,0x7f,sizeof(f));
		head=tail=0;
		for(int i=1;i<=n;i++)
		{
			while(head<tail&&K(q[head],q[head+1])<2*sum[i]) head++;
			f[i]=g[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]);
			while(head<tail&&K(q[tail],q[tail-1])>K(q[tail],i)) tail--;
			q[++tail]=i;
		}
	}
	printf("%d\n",f[n]*m-sum[n]*sum[n]);
}