YIMING GAO

DP, 决策单调性, 斜率优化

BZOJ 3675: [Apio2014]序列分割

链接

题意

小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤:
1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。

输入

输入第一行包含两个整数n,k ($ k+1≤n $)。
第二行包含n个非负整数a1,a2,…,an($ 0≤ai≤10^4 $),表示一开始小H得到的序列。

输出

输出第一行包含一个整数,为小H可以得到的最大分数。

样例输入

7 3 
4 1 3 4 0 2 3 

样例输出

108

我们首先可以发现交换切割顺序不会影响答案
然后可以得到式子
令$f_{i,k}$表示在取到第i个数时切割k次的最大分数
则 $ f_{i,k}=max\{f_{j,k-1} + sum_{j+1,i} \times sum_{i+1,n} \} $
($sum_{i,k}$ 表示 $\sum^{k}_{j=i}a_j$ )
令$s_i= \sum^{i}_{j=1}a_j$
对于一个固定的k, 令$g_i=f_{i,k-1}$, 则$f_{i,k}=max\{g_j + (s_i – s_j) \times (s_n – s_i)\}$
化简得
$$f_{i,k}=max\{g_j – s_i^2 + s_i \times s_n – s_j \times s_n\} \\
\ \ =max\{g_j – s_j \times s_n\} – s_i^2 + s_i \times s_n $$
对于两个决策 $j,k\ (j \gt k)$
决策j比k优当且仅当 $g_j – g_k > (s_n-s_i) \times (s_j – s_k)$

$$\frac{g_j + g_k}{s_j – s_k} \gt s_n – s_i$$
故可以进行斜率优化
因为序列中的数有可能为0,所以需要注意斜率不存在的情况。
因为只有128M内存,需要滚动f数组

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
deque<int> s[210];
ll sum[N],f[2][N];
double calc(int j,int k,int p) {
	//j>k
	if(sum[j]==sum[k]) return -1e10;
	return (double)(f[p & 1][j]-f[p & 1][k])/(double)(sum[j]-sum[k]);
}
int a[N];
int main() {
	//freopen("3675.in","r",stdin);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=k;i++) {
		s[i].push_back(1);
		f[i&1][1]=sum[1]*(sum[n]-sum[1]);
	}
	s[0].push_back(0);
	for(int j=1;j<=k;j++) {
		 for(int i=2;i<=n;i++){          
			while(s[j-1].size()>1&&calc(s[j-1][s[j-1].size()-2],s[j-1].back(),j-1)>(sum[n]-sum[i]))  {
				s[j-1].pop_back();
			}
			f[j & 1][i]=f[(j-1) & 1][s[j-1].back()]+(sum[n]-sum[i])*(sum[i]-sum[s[j-1].back()]);
			while(s[j].size()>1&&calc(i,s[j].front(),j)>=calc(s[j].front(),s[j][1],j)) {
				s[j].pop_front();
			}
			s[j].push_front(i);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		ans=max(ans,f[k & 1][i]);
	}
	printf("%lld\n",ans);
}

在UOJ上也有一道一样的题,需要输出方案,但空间给的256M
可以直接开一个数组记录答案
链接
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
deque<int> s[210];
ll sum[N],f[2][N];
int pre[210][N];
double calc(int j,int k,int p) {
	//j>k
	if(sum[j]==sum[k]) return -999999;
	return (double)(f[p & 1][j]-f[p & 1][k])/(double)(sum[j]-sum[k]);
}
int a[N];
int main() {
	freopen("3675.in","r",stdin);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	/*for(int i=1;i<=k;i++) {
		s[i].push_back(1);
		f[i&1][1]=sum[1]*(sum[n]-sum[1]);
	}*/
//	s[1].push_back(1);
	f[1&1][1]=sum[1]*(sum[n]-sum[1]);
	s[0].push_back(0);
//	f[1][1]=sum[1]*(sum[n]-sum[1]);
	for(int j=1;j<=k;j++) {
		 for(int i=j;i<n;i++){          
			while(s[j-1].size()>1&&calc(s[j-1][s[j-1].size()-2],s[j-1].back(),j-1)>(sum[n]-sum[i]))  {
				s[j-1].pop_back();
			}
			f[j & 1][i]=f[(j-1) & 1][s[j-1].back()]+(sum[n]-sum[i])*(sum[i]-sum[s[j-1].back()]);
			pre[j][i]=s[j-1].back();
			while(s[j].size()>1&&calc(i,s[j].front(),j)>=calc(s[j].front(),s[j][1],j)) {
				 
				s[j].pop_front();
			}
			s[j].push_front(i);
		}
	}
	ll ans=0;
	int pos=0;
	for(int i=1;i<n;i++) {
		if(f[k&1][i]>=ans) pos=i;
		ans=max(ans,f[k & 1][i]);
	}
	printf("%lld\n",ans);
	for(int i=k;i>=1;i--) {
		printf("%d ",pos);
		if(pre[i][pos]!=0) pos=pre[i][pos];
	}
//	printf("%d",pos);
}

Be the First to comment. Read More
总结

[BZOJ 4870]: [Shoi2017]组合数问题

传送门

DP
实际上就是要从 $nk$ 件物品里面选出若干件,使得其数量模k等于r的方案数。
可以发现 $f[n∗2,i+j]+=f[n,i]∗f[n,j]$
对dp数组做快速幂即可。
$f[i][j]$表示前i个物品选模p余j个,然后矩乘即可。
复杂度 $O(k^2log^n_2)$

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn=100010;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
    return x*f;
}
int n,P,k,r;
struct num{
    int x[52];
    void init(){
        memset(x,0,sizeof x);
    }
}f;
num calc(const num &a,const num &b){
    num res;
    res.init();
    for(int i=0;i<=k;i++)
        for(int j=0;j<=k;j++)
            (res.x[(i+j)%k]+=(LL)a.x[i]*b.x[j]%P)%=P;
    return res;
}
num ksm(num a,LL t){
    num res;
    res.init();res.x[0]=1;
    while(t){
        if(t&1)res=calc(res,a);
        a=calc(a,a);
        t>>=1;
    }
    return res;
}
int main(){
    int i,j;
    n=read();P=read();k=read();r=read();
    f.x[0]=1;
    f.x[1%k]+=1;
    f=ksm(f,(LL)n*k);
//    for(i=0;i<=k;i++)printf("%d\n",f.x[i]);
    printf("%d\n",f.x[r]);
    return 0;
}

Be the First to comment. Read More
三分

[BZOJ4868]: [Shoi2017]期末考试

三分吧
很水的一道题

传送门

注意要预处理c极大的情况

#include <bits/stdc++.h>

#define N 100005

long long t[N], b[N], sum1[N], sum2[N], A, B, C;
int n, m;

long long cal(long long ddl) {
    long long res = 0, pos;
    int l = 0, r = n;
    while (r - l > 1) {
        int mid = l + r >> 1;
        (t[mid] <= ddl) ? l = mid : r = mid;
    }
    pos = t[r] <= ddl ? r : l;
    res += C * (ddl * pos - sum1[pos]);
    l = 0, r = m;
    while (r - l > 1) {
        int mid = l + r >> 1;
        b[mid] <= ddl ? l = mid : r = mid;
    }
    pos = (b[r] <= ddl) ? r : l;
    long long cnt1 = ddl * pos - sum2[pos];
    long long cnt2 = sum2[m] - sum2[pos] - ddl * (m - pos);
    long long cnt3 = cnt2 - cnt1;
    res += (cnt1 < cnt2) ? cnt1 * A + cnt3 * B : cnt2 * A;
    return res;
}

using std::cin;

int main() {
    cin >> A >> B >> C;
    if (A > B) A = B;
    scanf("%d %d", &n, &m);
    long long minn = (long long) 1e12;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        minn = std::min(minn, t[i]);
    }
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    std::sort(t + 1, t + n + 1);
    std::sort(b + 1, b + m + 1);
    for (int i = 1; i <= n; i++)
        sum1[i] = sum1[i - 1] + t[i];
    for (int i = 1; i <= m; i++)
        sum2[i] = sum2[i - 1] + b[i];
    long long ans = (long long) 1e17;
    if (C == 1e16) ans = cal(minn);
    else
        for (int i = 1; i <= 100000; i++)
            ans = std::min(ans, cal(i));
    std::cout << ans;
}

91 comments Read More
未分类

AHOI 2002 黑白瓷砖

题目

小可可在课余的时候受美术老师的委派从事一项漆绘瓷砖的任务。首先把 $frac {n×(n+1)}{2}$ 块正六边形瓷砖拼成三角形的形状。然后把每一块瓷砖漆成纯白色或者纯黑色,而且每块瓷砖的正、反两面都必须漆成同样的颜色。
有一天小可可突发奇想,觉得有必要试试看这些瓷砖究竟能够漆成多少种本质不同的图案。所谓两种图案本质不同就是其中的一种图案无论如何旋转、或者翻转、或者同时旋转和翻转都不能得到另外一种图案。

  • 旋转是将瓷砖三角形整体顺时针旋转 120 度或 240 度

  • 翻转是将瓷砖三角形整体左右翻动 180 度

一开始,小可可觉得这项实验很有意思,他知道 n=1 时有两个本质不同的漆绘方案,n=2 时也只有四个本质不同的漆绘方案。小可可还把这些漆绘方案画了出来。
但是后来小可可发现在 n 变大的过程中,漆绘方案的数目增长很快,在 n=14 的时候,居然有 6760803201217259503457555972096 种不同的漆绘方案。这果然是一项非常艰巨的实验。因此他决定请你编写程序帮他求解本质不同的漆绘方案数。

输入格式
输入一个正整数 $n(n≤20)$。

输出格式
输出一个整数,即问题的解(解的位数不超过 200 位)。

         一道Polya定理的裸题。
         首先题目中虽然只给了三种方式进行置换,但因为这三个置换并不能形成一个置换群(不满足封闭性、没有不动元素),所以需要将斜向上翻转、斜向下翻转、不置换。都添加进置换群中。(它们都可以由题目中所给的置换方式得来)
         然后就十分的愉悦了。由Polya定理可得: $ans=frac{sum^n_{i=1}(2^{c(a_i)}}{n}$。$a_i$ 代表每一个置换,$c(a_i)$ 代表在每一个$a_i$ 下所存在环的个数(下图中$c(a_i)$ 的个数为 4 {(1),(2,3),(4,6),(5)}。

         对应三种翻转的 $c(a_i)$ 为 $frac{frac{n×(n+1)}{2}+frac{n+1}{2}}{2}$
         对应两种旋转的 $c(a_i)$ 为 $2^{(frac{n×(n+1)}{2}+2)/3+1}$
         对应不动的 $c(a_i)$ 肯定为 $2^{frac{n×(n+1)}{2}}$
         将其相加再除以6即为答案。
         这道题答案很大,要使用高精。因为很懒,所以没有去写高精。用python打了打表就A掉了。好像网上的OJ上也没有这道题(我们学校的OJ上倒是有,但没有对外开放)。

         代码(没有高精)

#include<bits/stdc++.h>
#include<bits/stdc++.h>
int main() {
    int n;
    scanf("%d",&n);
    int s = n * (n + 1) / 2;
    int m = (s + (n + 1) / 2) / 2;
    printf("%dn", (2<em>(1<<((s+2)/3)) + 3</em>(1<<m) + (1<<s)) / 6);
}

Python

n=input();
s=(n<em>(n+1))/2;
m = (s + (n + 1) / 2) / 2;
ans=0;
ans=ans+2</em>((1<<(s+2)/3));
ans=ans + 3*(1<<m) + (1<<s);
ans=ans/6;
print ans;

        给一张表吧
$$
begin{array}{c|lcr}
n & text{Ans}
hline
1 & 2
2 & 4
3 & 20
4 & 208
5 & 5728
6 & 351616
7 & 44772352
8 & 11453771776
9 & 5864078802944
10 & 6004800040206336
11 & 12297829416834170880
12 & 50371909152808594571264
13 & 412646679762074900658913280
14 & 6760803201217259503457555972096
15 & 221537999297485988040673580072042496
16 & 14518714321960041110131833181979847688192
17 & 1902996923607946508078923551753025410956263424
18 & 498859225542281529413525041870510961437758449516544
19 & 261545905641111698493157893267478067457861758958922891264
20 & 274250759553534340359161530426874121271106557923036528403021824
end{array}
$$
        AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n<8) {
        int s = n * (n + 1) / 2;
        int m = (s + (n + 1) / 2) / 2;
        printf("%dn", (2(1<<((s+2)/3)) + 3(1<<m) + (1<<s)) / 6);
    }
    if(n==8) cout<<"11453771776";
    if(n==9) cout<<"5864078802944";
    if(n==10) cout<<"6004800040206336";
    if(n==11) cout<<"12297829416834170880";
    if(n==12) cout<<"50371909152808594571264";
    if(n==13) cout<<"412646679762074900658913280";
    if(n==14) cout<<"6760803201217259503457555972096";
    if(n==15) cout<<"221537999297485988040673580072042496";
    if(n==16) cout<<"14518714321960041110131833181979847688192";
    if(n==17) cout<<"1902996923607946508078923551753025410956263424";
    if(n==18) cout<<"498859225542281529413525041870510961437758449516544";
    if(n==19) cout<<"261545905641111698493157893267478067457861758958922891264";
    if(n==20) cout<<"274250759553534340359161530426874121271106557923036528403021824";
}

Be the First to comment. Read More
可并堆,

左偏树学习笔记

第一篇啊第一篇啊,那个世界你好终于可以删去了诶。
左偏树感觉写的姿势不对啊,无故WA+RE(后来发现其实是并查集的问题,滚回普及去吧)


    这里是目录

左偏树的实现

一、关于左偏树

左偏树是一颗二叉树,每个节点同样只拥有最多左右两个儿子。同时它也具有堆性质。优先队列也具有这些性质但是但将两个优先队列合并时,所需的时间复杂度却是$O(nlog_2^n)$,不能快速的进行合并。而左偏树即可以$O(log_2^n)$的时间复杂度实现。

二、左偏树的性质

1、左偏树同样具有堆的性质,所以左偏树的根节点是最小的。并且每个节点的键值小于等于其左右节点的键值。即对于任意节点 $i$  有:
i->key <= i->leftson->key && i->key <= i->rightson->key

第二个性质之前,先对左偏树引入三个概念:
1、键值:可以看作该节点的大小,比如说左偏树的根节点即为键值最大(或最小)的点。
2、外节点:只有当一个节点 $i$ 满足( i->leftson == NULL || i->rightson ==NULL)时,该节点是外节点。
3、距离:点$i$的距离 = 在以 $i$ 为根的子树中,从根出发,到离$i$最近的外节点所经过的边数。

2、任意节点 $i$ 满足 i->leftson->dis >= i->rightson->dis (dis即指节点距离)。这也就是左偏树的左偏性质。
3、对于任意节点 $i$  有 i->dis = i->rightson->dis + 1

三、左偏树的定理

1、当左偏树的根节点的距离是一定值 $k$ 时,在该树是完全二叉树时,节点数最小。
证明:因为性质3,节点的距离值 $=$ 右儿子个数+1。又因为性质2,所以当且仅当 i->leftson->dis = i->rightson->dis时,节点数最小。
2、当一颗左偏树的根的距离为 $i$ 时,可以发现它的树高也为= $i$ 。 此时根据定理一即可得到,当该树节点最少时即为一颗完全二叉树。节点数 $(n)$ $>=2^{k+1}-1$ 。

四、左偏树的代码实现

对左偏树的定义:struct Tree{Tree *son[2];int dis,key;}
1、合并操作:这是左偏树各个操作的基础,几乎每个操作都会使用。
Tree *C = Merge(Tree *x,Tree *y)$\Rightarrow$ 将树 A、B合并为C 。
假设A的根比B小(否则swap(A,B)),然后则将 A 的根作为 C 的根,则 A 的左儿子不变,然后递归Merge(A->son[1],B)。在比较A->son[1]->disA->son[0]->dis[0] 的大小,否则swap(A->son[1],A->son[0])

Tree *Merge(Tree *x,Tree *y) {
    if(x==NULL) return y;
    if(y==NULL) return x;
    if(y->key > x->key) swap(x,y);
    x->son[1]=Merge(x->son[1],y);
    if(x->son[0]->dis < x->son[1]->dis) swap(x->son[0],x->son[1]);
    x->dis=x->son[1]->dis+1;
    return x;
}

2、插入操作:
Insert(int a,Tree * A) 将a插入至A中。
即可将a看作只有一个点的左偏树,然后合并即可。
Tree *Insert(int x,Tree *A) {
    Tree *B;
    B->key=x;
    B->dis=0;
    return Merge(A,B);
}

3、删除根节点:
DeleteRoot(Tree *A) 将A的根删去。
直接将A的左右儿子合并为新树即可。
Tree *DeleteMax(Tree *A) {
    return Merge(A->son[0],A->son[1]);
}

4、建树操作:
将n个数建成一个左偏树。
将这n个树分别建成只有一个节点的左偏树,然后放进一个队列。
每次从中取出两个树,Merge 后再放回,直到队列中只剩下一个树。

4 comments Read More