SDOI2016 Round1

  1. 1 储能表
  2. 2 数字配对
  3. 3 游戏
  4. 4 生成魔咒
  5. 5 排列计数
  6. 6 征途

Menci的省选,2333

1 储能表

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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 n 种数字,第 i i 种数字是 ai a_i 、有 bi b_i 个,权值是 ci c_i
若两个数字 ai a_i aj a_j 满足,ai a_i aj a_j 的倍数,且 ai÷aj a_i \div a_j 是一个质数,那么这两个数字可以配对,并获得 ci×cj c_i \times c_j 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于 0 0 的前提下,求最多进行多少次配对。
n<=200n <= 200 , ai<=109a_i <= 10^9 , bi,ci<=105b_i , \mid c_i \mid <= 10^5 .

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#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 n 个点的树上进行。最初,每个点上都只有一个数字,那个数字是 123456789123456789 123456789123456789
有时,Alice 会选择一条从 s s t t 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r r ,若 r r s s 的距离是 dis dis ,那么 Alice 在点 r r 上添加的数字是 a×dis+b a \times dis + b
有时,Bob 会选择一条从 s s t t 的路径。他需要先从这条路径上选择一个点,再从那个点上选择一个数字。
Bob 选择的数字越小越好,但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。
n,m100000 n,m \leq 100000 , a10000 \mid a \mid \leq 10000 , b109 \mid b \mid \leq 10^9 , 1w109 1 \leq w \leq 10^9

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#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 1 2 2 拼凑起来形成一个魔咒串 [1,2] [1, 2]
一个魔咒串 S S 的非空字串被称为魔咒串 S S 的生成魔咒。
例如 S=[1,2,1] S = [1, 2, 1] 时,它的生成魔咒有 [1] [1] [2] [2] [1,2] [1, 2] [2,1] [2, 1] [1,2,1] [1, 2, 1] 五种。S=[1,1,1] S = [1, 1, 1] 时,它的生成魔咒有 [1] [1] [1,1] [1, 1] [1,1,1] [1, 1, 1] 三种。
最初 S S 为空串。共进行 n n 次操作,每次操作是在 S S 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 S S 共有多少种生成魔咒。
1n100000 1 \leq n \leq 100000 ;用来表示魔咒字符的数字 x x 满足 1x109 1 \leq x \leq 10 ^ 9

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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 n 的序列 A A ,满足以下条件:
1 . 1 1 ~ n n n n 个数在序列中各出现了一次
2 . 若第 i i 个数 A[i] A[i] 的值为 i i ,则称 i i 是稳定的。序列恰好有 m m 个数是稳定的。
满足条件的序列可能很多,序列数对 109+7 10 ^ 9 + 7 取模。
T=500000 T = 500000 n,m1000000 n,m \leq 1000000

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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 S 地到 T T 地的征途。
S S 地到 T T 地的路可以划分成 n n 段,相邻两段路的分界点设有休息站。
Pine 计划用 m m 天到达 T T 地。除第 m m 天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助 Pine 求出最小方差是多少。
设方差是 v v ,可以证明,v×m2 v \times m ^ 2 是一个整数。为了避免精度误差,输出结果时输出 v×m2 v \times m ^ 2
1n3000 1 \leq n \leq 3000 。保证从 S S T T 的总路程不超过 30000 30000

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

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

a>ba>baabb 优,则有 f[i1][a]+(s[j]s[a])2<f[i1][b]+(s[j]s[b])2 f[i - 1][a] + (s[j] - s[a]) ^ 2 < f[i - 1][b] + (s[j] - s[b]) ^ 2
化简得 (f[i1][a]+s[a]2)(f[i1][b]+s[b]2)s[a]s[b]<2×s[j] \frac{(f[i-1][a] + s[a] ^ 2) - (f[i-1][b] + s[b] ^ 2)}{s[a] - s[b]} < 2\times s[j]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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]);
}