UVa 11021

Type: 概率

题解

有点难以理解题解的递推式,把那句f(i-1)表示i-1天后全部死亡改成f(i-1)表示i-1天后一个不生的概率可能更好理解一点吧

不知道怎么证明这个式子,思维还是不强

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;

double f[maxn],P[maxn];;
int n,k,m,T;

int main(){
    cin>>T;
    for(int i=1;i<=T;++i){
        cin>>n>>k>>m;
        for(int j=0;j<n;++j) cin>>P[j];
        f[0]=0;f[1]=P[0];
        for(int j=2;j<=m;++j){
            f[j]=0;
            for(int t=0;t<n;++t){
                f[j]+=(P[t]*pow(f[j-1],t));
            }
        }
        printf("Case #%d: %.7lf\n",i,pow(f[m],k));
    }
    return 0;
}

UVa 11426

Link

https://vjudge.net/problem/UVA-11426

Type: 数论,欧拉函数,递推,思维

题意

输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+…+gcd(n-1,n)

保证输出不超过long long

范围: n∈[1,4000000]

题解

首先我们应该清楚

4000000的数据,用暴力 – 对每个gcd求值相加复杂度是i*j*O(gcd) 你懂就行,这么大的复杂度肯定爆炸.

所以我们第一想法肯定是预处理.

我们设 f(n) 为 (1,n)+(2,n)+(3,n)+…+(n-1,n)
则 S(n)=f(1)+f(2)+…+f(n)

通过这个公式我们就可以递推出所有的 S(n)

S(n)=S(n-1)+f(n)

然后我们的问题就转化成了求f(n)

首先我们会自然地想到,与n互素的答案是1.即(k,n)的结果都是n的约数

我们可以按照这个约数来进行分类,

用 g(n,i)表示满足gcd(x,n)=i 且 x\<n 的正整数x的个数
则: f(n)=Sum(i*g(n,i) | i是n的约数,g(n,i)是1~n中gcd(k,n)=i的k的个数)

然后我们注意到:
-gcd(x,n)=i
-则gcd(x/i,n/i)=1
-即x/i与n/i互质

然后我们就可以将 g(n,i) 看做1~n中与 n/i 互质的数的个数,即

g(n,i) = phi(n/i)

然后我们预处理phi[maxn],预处理完以后处理f(n),这里如果用二重循环依然是接受不了的

所以我们沿用筛法的思想对f[maxn]数组进行预处理,遇到i 是 k 的约数时,直接f[k]+=(i*phi[n/i])

最后预处理S[maxn]即可

Code

/*
我们要求:
G=Sigma(i=1~N) Sigma(j=i+1~N) GCD(i,j)
N<=4000000,这样的范围二次循环+GCD肯定是不行的
所以我们考虑
f(n)=Sigma(i=1~n-1) gcd(i,n)
则
G(n)=Sigma(i=1~n) f(i)
=G(n-1)+f(n)
所以我们的问题转换为如何求f(n)

即k都是n的约数
可以按照约数进行分类,用g(n,i)表示满足 (x,n)=i且x<n的正整数x的个数
则 f(n)=sum(i\*g(n,i)|i是n的约数)

再重提: g(n,i)代表满足(x,n)=i,且x<n的正整数x的个数

我们知道,如果 (a,n)=k
则 (a/k,n/k)=1

所以我们可以理解为g(n,i)代表的是x/i与n/i互质的数的个数
即满足条件的x/i 有 phi(n/i)个
g(n,i)=phi(n/i)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=4000000+10;
LL phi[maxn];

LL f[maxn];

LL g[maxn];
void phi_table(){
    for(int i=2;i<maxn;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

void init(){
    phi_table();
    memset(f,0,sizeof(f));
    for(int i=1;i<maxn;++i){
        for(int j=i*2;j<maxn;j+=i){
            f[j]+=(i*phi[j/i]);
        }
    }
    memset(g,0,sizeof(g));
    for(int i=1;i<maxn;++i) g[i]=g[i-1]+f[i];
}

int main(){
    init();
    int k;
    while(~scanf("%d",&k) && k){
        printf("%lld\n",g[k]);
    }
    return 0;
}

UVa 11806

Link

https://vjudge.net/problem/UVA-11806

Type:

组合数学,排列预处理,容斥原理,减法取模公式

题意

给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,

问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解

我们可以将问题转化为:

全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为

C((m-2)*(n-2),k).

我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,D为下边没有石子.

则(我们设~A为非A集合):

ans=|(~A)∩(~B)∩(~C)∩(~D)|

可以发现就是容斥原理
至于每个集合的计算,在图中就相当于少了一行或一列,
即:

C(row*column,k)

因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示

0000
0001
0010

我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0

答案为全部的和.

Code

/*
Link: https://vjudge.net/problem/UVA-11806
Type: 组合数学,排列预处理,容斥原理,减法取模公式
题意: 给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,
问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解:
我们可以将问题转化为:
全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为
C((m-2)*(n-2),k).
我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,
D为下边没有石子.
则(我们设~A为非A集合):
ans=|(~A)∩(~B)∩(~C)∩(~D)|
可以发现就是容斥原理
至于每个几何的计算,在图中就相当于少了一行或一列,
即:
C(row*column,k)
因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示
0000
0001
0010
我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0
答案为全部的和.
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7;
int T;

const int MAXK=500;
int C[MAXK+10][MAXK+10];
void init(){
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=0;i<=MAXK;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            //组合的一个递推公式
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}

int main(){
    init();
    cin>>T;
    for(int kase=1;kase<=T;++kase){
        int n,m,k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<16;++i){
            int nn=n,mm=m;
            int b=0;
            if(i&1){mm--;b++;}
            if(i&2){nn--;b++;}
            if(i&4){mm--;b++;}
            if(i&8){nn--;b++;}
            //奇数-偶数+
            if(b&1) sum=(sum+mod-C[nn*mm][k])%mod;
            else sum=(sum+C[nn*mm][k])%mod;
        }
        cout<<"Case "<<kase<<": "<<sum<<endl;
    }
    return 0;
}

UVa 11401

Link

https://vjudge.net/problem/UVA-11401

type

组合数学,加法原理,三角形三边定理

题意

给你N个长度为1~N的杆子,问你能用这N个杆子拼成多少个不同的三角形

题解

考虑三角形三边定理.

设c(x)为以x为最长边的可拼成三角形的数目.y,z为另外两条边.
则 z+y>x => x-y<z 即 x-y<z<x (没有等于号则代表不考虑等边)
考虑y的取值,确定z的取值.

y∈[1,x-1]
当y取1时,z无值.当y取2时,z有唯一值x-1
当y取3时,z可以取(x-1),(x-2).
故y取x-1时,z可以取的种数为x-2种.

根据等差数列求和公式:
总种类数Sn = 0+1+2+…+(x-2)

Sn = (x-2)(x-1)/2(种)

但这个值并不等于c(x)
因为:

1.对于每个三角形都计数了两遍
=> 因为y=2时 z=x-1,而最后一项为y=x-1,则z一定有一种会取到2

2.以上的计算方式存在y=z的情况
(这种情况下每个特例只会出现一次,因为只有确定y的条件下才可能出现y=z)
=> 比如x=7 y=4时,z就可以取到4

对于第二种问题的解决很简单.
对于每个x考虑y==z的情况:
设t为c(x)中y=z时的情况总数:
则因为当且仅当y∈[(x/2+1),x-1]时存在y=z的可能.

故t=(x-1)-(x/2+1)+1=x-1-(int)x/2

故c(x)=(Sn-t)/2

又因为c(x)是最长边为x时的种类数.

故设f(n)为最长边不超过n时的种类数
根据加法原理,因为互无交集
故 f(n)=c(1)+c(2)+c(3)+…+c(n)

化成递推: f(n)=f(n-1)+c(n)

Code

/*
Link: https://vjudge.net/problem/UVA-11401
type: 组合数学,加法原理,三角形三边定理
题意: 给你N个长度为1~N的杆子,问你能用这N个杆子拼成多少个不同的三角形

题解:
考虑三角形三边定理.
设c(x)为以x为最长边的可拼成三角形的数目.
设y,z为另外两条边.
则 z+y>x => x-y<z 即 x-y<z<x (没有等于号则代表不考虑等边)
考虑y的取值,确定z的取值.
y∈[1,x-1]
当y取1时,z无值.当y取2时,z有唯一值x-1
当y取3时,z可以取(x-1),(x-2).
故y取x-1时,z可以取的种数为x-2种.
根据等差数列求和公式:
总种类数Sn
= 0+1+2+...+(x-2)
= (x-2)(x-1)/2(种)
但这个值并不等于c(x)
因为:
1.对于每个三角形都计数了两遍
=> 因为y=2时 z=x-1,而最后一项为y=x-1,则z一定有一种会取到2
2.以上的计算方式存在y=z的情况
(这种情况下每个特例只会出现一次,因为只有确定y的条件下才可能出现y=z)
=> 比如x=7 y=4时,z就可以取到4
对于第二种问题的解决很简单.
对于每个x考虑y==z的情况:
设t为c(x)中y=z时的情况总数:
则因为当且仅当y∈[(x/2+1),x-1]时存在y=z的可能.
故t=(x-1)-(x/2+1)+1=x-1-(int)x/2
故c(x)=(Sn-t)/2
又因为c(x)是最长边为x时的种类数.
故设f(n)为最长边不超过n时的种类数
根据加法原理,因为互无交集
故 f(n)=c(1)+c(2)+c(3)+...+c(n)
化成递推: f(n)=f(n-1)+c(n)
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
long long sum[maxn];
int n;
inline void init(){
    long long Sn,Cn,t;
    memset(sum,0,sizeof(sum));
    for(long long i=4;i<=1000000;++i){
        Sn=(i-2)*(i-1)/2;
        t=i-1-i/2;
        Cn=(Sn-t)>>1;
        int id=(int)i;
        sum[id]=sum[id-1]+Cn;
    }
}
int main(){
    init();
    while(cin>>n){
        if(n<3)break;
        cout<<sum[n]<<endl;
    }
    return 0;
}

UVa 11538

题目连接:

https://odzkskevi.qnssl.com/865929a003dafabd8556e993f05c6637?v=1517622087

PS: 蓝书P105,书上有一个错误的地方,Sigma(1~n-1) i(i-1)那里书上得到的结果是2*Sigma(1~n-1) i(i-1)的结果.我在代码中标注了.

Link:

https://vjudge.net/problem/UVA-11538
type: 组合数学,乘法/加法原理,以及初中数学n^2和=n(n+1)(2n+1)/6

题意:

有N×M大小的棋盘,问,给你两个皇后,使他们可以互相攻击对方的可能有多少种.

题解:

分为三个方向,第一个方向为同一行,第二个方向为同一列,第三个方向为同一斜线

同一行: 对于白皇后有nm种取法,每种取法中黑皇后有(m-1)种取法,所以结果是nm(m-1)
同一列: 合同一行类似,结果是nm(n-1)
同一斜线: 画图观察,假设n<=m,(n>m可以不用看,因为等价于n<=m转置)

可以观测到所有’/’方向的斜线长度为: 1,2,3,…,n,n,n,n-1,n-2…,2,1
其中n的个数 = 总条数-2×(n-1) = m+n-1-2n+2 = m-n+1(m>n时反过来即可)
其中每条斜线上的取法种数 = i*(i-1)
diagonal=Sigma(1~n-1) i(i-1) => i==1时确实是0种可能,因为皇后是放在块内而不是点上的.
则 All_diagonal = 2(2*diagonal+(m-n+1)*n*(n-1)) => 这里的乘2是因为有两种斜线’/’和’\’的可能
其中

diagonal
=Sigma(1~n-1) i^2 – Sigma(1~n-1) i
=n(n-1)(2n-1)/6 – n(n-1)/2
=n(n-1)(2n-4)/6

All_diagonal
= 2(2*(n(n-1)(2n-4)/6)+(m-n+1)*n*(n-1))
= 2n(n-1)(3m-n-1)/3

这三种情况互不相交,最终答案就等于三者和.

Code:

/*
Link: https://vjudge.net/problem/UVA-11538
type: 组合数学,乘法/加法原理,以及初中数学n^2和=n(n+1)(2n+1)/6

题意: 有N×M大小的棋盘,问,给你两个皇后,使他们可以互相攻击对方的可能有多少种.

题解: 分为三个方向,第一个方向为同一行,第二个方向为同一列,第三个方向为同一斜线

同一行: 对于白皇后有nm种取法,每种取法中黑皇后有(m-1)种取法,所以结果是nm(m-1)
同一列: 合同一行类似,结果是nm(n-1)
同一斜线: 画图观察,假设n<=m,(n>m可以不用看,因为等价于n<=m转置)
    可以观测到所有'/'方向的斜线长度为: 1,2,3,...,n,n,n,n-1,n-2...,2,1
    其中n的个数 = 总条数-2×(n-1) = m+n-1-2n+2 = m-n+1(m>n时反过来即可)
    其中每条斜线上的取法种数 = i*(i-1)
    diagonal=Sigma(1~n-1) i(i-1)   =>   i==1时确实是0种可能,因为皇后是放在块内而不是点上的.
    则   All_diagonal = 2(2*diagonal+(m-n+1)*n*(n-1))  => 这里的乘2是因为有两种斜线'/'和'\'的可能
    其中diagonal=Sigma(1~n-1) i^2 - Sigma(1~n-1) i  =>n方和展开公式,等差数列求和
                =n(n-1)(2n-1)/6 - n(n-1)/2
                =n(n-1)(2n-4)/6

        All_diagonal = 2(2*(n(n-1)(2n-4)/6)+(m-n+1)*n*(n-1))
                     = 2n(n-1)(3m-n-1)/3

这三种情况互不相交,最终答案就等于三者和.
*/

//Code
#include<bits/stdc++.h>
using namespace std;
unsigned long long N,M;
int main(){
    while(cin>>N>>M){
        if(N==0&&M==0)break;
        unsigned long long row=N*M*(M-1);
        unsigned long long column=N*M*(N-1);

        if(N>M) swap(N,M);
        cout<<row+column+2*N*(N-1)*(3*M-N-1)/3<<endl;
    }
    return 0;
}

UVa 11235

【Topic Link】

:point_right:Frequent values

【类别】

RMQ,游程编码

【题意】

给出一个非降序的整数数组,你的任务是对于一系列询问,回答区间内出现最多的值的次数.

【题解】

题目给的数组是非降序的.所有相等的元素都会聚集到一起。这样就可以把整个数组进行游程编码(Run Length Encoding,RLE).比如 (-1,1,1,2,2,2,4)就可以编码成(-1,1),(1,2),(2,3),(4,1),其中(a,b)表示有b个连续的a。用value[i]和count[i]分别表示第i段的数值和出现次数,num[p]、left[p]、right[p]、分别表示位置p所在段的编号和左右端点的位置.每次查询(L,R)的结果为以下三个部分的最大值:

  1. 从L到L所在段的结束处的元素个数(right[L]-L+1)
  2. 从R所在段开始到R的元素个数(R-left[R]+1)
  3. 中间第num[L]+1段到第num[R]-1段的count的最大值,这一步是典型的RMQ问题,主要的时间也就花费在这里.
  4. 特殊:如果L和R在同一个段中,则答案是R-L+1

【代码】

github:

  1. :point_right:UVa 11235.cpp
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100010;
vector<int> cnt;
int num[maxn],le[maxn],ri[maxn];
int dp[maxn][20];
int N,Q;

void RMQ_init(){
    int n=cnt.size();
    for(int i=0;i<n;++i) dp[i][0]=-cnt[i];
    ///2*(2^(j-1))=2^j
    ///dp(i,j)表示从i开始,长度为2^j的一段元素中的最小值.
    for(int j=1;(1<<j)<=n;++j)
        for(int i=0;i+(1<<j)-1<n;++i)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int RMQ(int L,int R){
    if(L>R) return 0;
    int k=0;
    ///如果2^(k+1)<=R-L+1,那么k还可以加一
    while((1<<(k+1)<=R-L+1))k++;
    return min(dp[L][k],dp[R-(1<<k)+1][k]);
}

int main(){
    while(~scanf("%d",&N) && N){
        scanf("%d",&Q);
        cnt.clear();
        int pre=INF,ct=0;
        for(int i=0;i<N;++i){
            int numpy;
            scanf("%d",&numpy);
            if(numpy!=pre){
                pre=numpy;
                ct++;
                num[i]=ct-1;
                le[i]=i;
                if(i>=1)
                    for(int j=le[i-1];j<i;++j)
                        ri[j]=i-1;
                cnt.push_back(1);
            }else{
                num[i]=num[i-1];
                le[i]=le[i-1];
                cnt[ct-1]++;
            }
            if(i==N-1)
                for(int j=le[i];j<=i;++j)
                    ri[j]=i;
        }
/**
        for(int i=0;i<cnt.size();i++)
            cout<<i<<":"<<cnt[i]<<" ";
        cout<<endl;
        for(int i=0;i<N;i++)
            printf("%d(left,right,num):%d %d %d\n",i,le[i],ri[i],num[i]);
**/
        RMQ_init();
        for(int i=0;i<Q;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            if(num[--a]==num[--b])
                printf("%d\n",b-a+1);
            else
                printf("%d\n",max(max((ri[a]-a+1),-RMQ(num[a]+1,num[b]-1)),(b-le[b]+1)));
        }
    }
    return 0;
}

UVa 10859

【Topic Link】

Placing Lampposts

【题意】

给你一个n个点m条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮。每盏灯将照亮以它为一个端点的所有边。

在灯的总数最小的前提下,被两盏灯同时被照亮的边数应该尽量大。

【题解】

树形dp,Lrj P70。

这题教会了我一个很有用的技巧:有两个所求的值要优化,比如让a尽量小,b也尽量小

那么可以转化为让 M*a+b尽量小,其中M应该是一个比“a的最大值和b的最小值之差”还要大的数

最终的答案为ans/M, ans%M

回到这题,要求放的灯总数最小,被两盏灯同时照亮的边数尽量大。

因为每条边要么被一盏灯照亮,要么被两盏灯照亮,所以可以转换为:

求:放的灯总数量最少,被一盏灯照亮的边数尽量少。

就可以变成球 M*a+b 的最小值,a为放置的灯数量,b为被一盏灯照的边数

f[u][1]表示u点放灯时的整个子树最小值
f[u][0]表示u点不放灯时的整个子树最小值

如果u放,那么u个子结点可以选择放,也可以不放,选择其中较小的值。如果选的是不照,就要增加一条只有一个灯照的边

如果u不放,那么其子结点就必须选择要放,而且每条边都只有一个灯照

【Code】

github: UVa 10859.cpp

#include<bits/stdc++.h>
using namespace std;
int T,n,m,vis[2000][2],d[2000][2];
vector Graph[1010];

int dp(int i,int j,int f){
    if(vis[i][j]) return d[i][j];
    vis[i][j]=1;
    int& ans=d[i][j];

    ans=2000;
    for(int k=0;k<Graph[i].size();++k) 
        if(Graph[i][k]!=f) 
           ans+=dp(Graph[i][k],1,i); 
    if(!j && f>=0)  ans++;

    if(j || f<0){
        int sum=0;
        for(int k=0;k<Graph[i].size();++k) 
           if(Graph[i][k]!=f) 
              sum+=dp(Graph[i][k],0,i); 
        if(f>=0) sum++;
        ans=min(ans,sum);
    }
    return ans;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i) Graph[i].clear();
        for(int i=0;i<m;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            Graph[x].push_back(y);
            Graph[y].push_back(x);
        }
        memset(vis,0,sizeof(vis));
        int ans=0;
        for(int i=0;i<n;++i){
            if(!vis[i][0])///新的一棵树
                ans+=dp(i,0,-1);
        }
        printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
    }
    return 0;
}

UVa 11825

【Topic Link】

Hackers’ Crackdown

【题意】

有N台机器,每台机器上有N个服务

你可以对每台机器选择关闭他以及和他相邻的机器的一种服务

当所有机器不能运行一个服务时,就是摧毁了一种服务

问你最多能摧毁多少个服务

【题解】

就是把n台电脑看成n个集合,每个集合的成员就是这台电脑,以及和这台电脑相邻的电脑;
我们就是要求把这些集合合并成尽量多的大集合,使每个集合都等于全集;也就是因为最开始的小集合,我们可以让它里面全部电脑的某一项服务全部失误,那如果合并成一个大集合,则这个大集合的某一项服务可以全部失效;所以能合并成几个等于全集的大集合,就可以让几项服务失效;

【Tip】

状态压缩,异或操作是相同得0,不同得1.LRJ这道题的位运算用的好…

【Source Code】

github: Uva 11825.cpp


#include<bits/stdc++.h>
using namespace std;
int N,T,P[1<<17],f[1<<17],cover[1<<17],ca=1;
int main(){
    while(~scanf("%d",&N),N){
        ///初始化第i台计算机的相邻集合
        for(int i=0;i<N;++i){
            int n,m;
            scanf("%d",&n);
            P[i]=1<<i;
            for(int j=0;j<n;++j){
                scanf("%d",&m);
                P[i] |= 1<<m;
            }
        }
        ///S是N个计算机的所有组合的集合,二进制表示,cover[S]是集合的并
        for(int S=0;S<(1<<N);++S){
            cover[S]=0;
            for(int i=0;i<N;++i){
                if(S & (1<<i)) cover[S] |= P[i];///第i台机器选/不选
            }
        }
        f[0]=0;
        int ALL=(1<<N)-1;///全集二进制表示
        for(int S=1;S<(1<<N);++S){
            f[S]=0;
            ///筛出S的子集进行动态规划
            for(int S0=S;S0;S0=(S0-1)&S){
                if(cover[S0]==ALL)///如果子集S的子集的并是全集
                    f[S]=max(f[S],f[S^S0]+1);
            }
        }
        printf("Case %d: %d\n",ca++,f[ALL]);
    }
    return 0;
}

UVa 10891

【Topic Link】

Game of Sum

【题意】

给你一个序列的数,两个玩家A,B.每次A,B都需要从这个序列的两端取连续的数,保证他们每次都用最优的策略.A先手,求游戏结束后sum(A)-sum(B).

【题解】

因为任意时刻游戏的状态都是连续子序列.

用d(i,j)表示原序列的第i~j个元素组成的子序列.在双方都采取最优策略的情况下,先手得分的最大值.

状态转移时,我们考虑从左取和从右取多少个.等价于枚举给对方剩下怎样的子序列.是(k,end)(begin<k<=end),还是(begin,k)(begin<=k<end).

状态转移方程:d(begin,end)=sum(begin,end)-min{d(begin+1,end),d(begin+2,end),…,d(end,end), d(begin,end-1),d(begin,end-2),…,d(begin,begin),0}

0代表全取完,所以不需要边界处理.

【Source Code】

github: UVa 10891.cpp


#include<bits/stdc++.h>
using namespace std;
const int maxn=100+20;
int A[maxn],vis[maxn][maxn],S[maxn],d[maxn][maxn];

int dp(int b,int e){
    if(vis[b][e]) return d[b][e];///记忆化搜索
    vis[b][e]=1;
    int m=0;
    ///从b->e选最小的结果,然后d[b][e]选sum(b,e)-m
    for(int k=b+1;k<=e;++k) m=min(m,dp(k,e)); ///从e->b选最小的结果,然后d[b][e]选sum(b,e)-m
    for(int k=b;k<e;++k) m=min(m,dp(b,k));
    d[b][e]=S[e]-S[b-1]-m;
    return d[b][e];
}

int main(){
    int n;S[0]=0;
    while(~scanf("%d",&n) && n){
        for(int i=1;i<=n;++i){
            scanf("%d",&A[i]); 
            S[i]=S[i-1]+A[i]; 
        } 
        memset(vis,0,sizeof(vis)); 
        printf("%d\n",2*dp(1,n)-S[n]);///=>dp(1,n)-(S[n]-dp(1,n))
    }
    return 0;
}

 

UVa 10635 + NlogN-LIS

【Problem Link】

Prince and Princess

【题意】

有两个长度分别为p+1和q+1的序列,每个序列中的各个元素互不相同,切都是1~n²之间的整数.两个序列的第一个元素都是1,求出A和B的最长公共子序列长度.

【题解】

本体是LCS问题,但规模达到了250²=62500,O(pq)的算法显然太慢.所以考虑把A重新按照下标编号,然后输入B的时候判断B中的整数在A中的位置,不存在则为0或者不记录.然后就转换为了求B得最长单增子序列LIS问题.然后用O(nlog(n))的解法解决.

【Source Code】

github: UVa 10635.cpp


#include<bits/stdc++.h>
using namespace std;
const int maxn=250*250+10;
const int INF=0x3f3f3f3f;
int S[maxn],g[maxn],d[maxn];///LIS所需
int num[maxn]; ///num[x]为整数x的编号,num[x]=0表示在A中未出现过
int main(){
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;++kase){
        int N,p,q,x;
        scanf("%d%d%d",&N,&p,&q);
        fill(num,num+maxn,0);
        for(int i=1;i<=p+1;++i){
            scanf("%d",&x);
            num[x]=i;
        }
        int n=0;
        for(int i=0;i<q+1;++i){
            scanf("%d",&x);
            if(num[x]) S[n++]=num[x];
        }

        ///O(nlog(n))求解S[0]到S[n-1]的LIS
        for(int i=1;i<=n;++i){
            g[i]=INF;
        }
        int ans=0;
        for(int i=0;i<n;++i){
            int k=lower_bound(g+1,g+n+1,S[i])-g;///在g[1]~g[n]中查找
            d[i]=k;///k是长度
            g[k]=S[i];///g数组记录长度为k的目前最末(最大)元素大小
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",kase,ans);
    }
    return 0;
}