Merging Two Decks

https://cn.vjudge.net/problem/CodeForces-234H

贪心+模拟，

可以把连续的1或0看场一块，这样每一个序列都分成若干块。合并的时候‘按块合并’。

如果两个序列块数不同，那么块数少的总能并入块数多的。

如果块数相同，那么只需枚举开头属于哪一块。

综上，只需要用双指针同时遍历两次即可，第一次假设合并的序列1开头，第二次假设合并的序列0开头

自己的代码太丑，还是标程比较简洁

#include 
#include 
#include 
using namespace std;
int A[200005];
int V[200005];
int N, M;
vector solve(int type)
{
    int K = 0, x = 1, y = N + 1;
    while (x <= N || y <= N + M)
    {
        while (x <= N && A[x] == type)
            V[K++] = x++;
        while (y <= N + M && A[y] == type)
            V[K++] = y++;
        type = 1 - type;///变换状态
    }
    /// 在该翻转的时候就翻转，相邻的两个不一样就翻转；在最后的后一步加一个哨兵0；防止……
    vector answer;
    for (int i = 0; i < N + M; ++i)
        if (A[V[i]] != A[V[i + 1]])  ///最后一个多一个哨兵
            answer.push_back(i + 1);
    return answer;
}
int main() {
    //ifstream cin("input.txt");
   // ofstream cout("output.txt");
    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> A[i];
    cin >> M;
    for (int i = N + 1; i <= N + M; ++i)
        cin >> A[i];
    vector answer = solve(0);
    if (solve(1).size() <= answer.size())
        answer = solve(1);
     else answer = solve(0);
    ///V是最后一次调用slove的结果
    for (int i = 0; i < N + M; ++i)
        cout << V[i] << " ";
    cout << "\n";
    cout << answer.size() << "\n";
    for (int i = 0; i < int(answer.size()); ++i)
        cout << answer[i] << " ";
    cout << "\n";
}

The Fair Nut and Strings

https://cn.vjudge.net/problem/CodeForces-1084E
思维题，通过trie树来计数。每个字符串刚好对应了一个trie树节点
字符串ab构成二叉树，每次向下走的过程，如果不加限制，那么节点数2，我们先假设没有限制的，2
如果s[i]等于a，那么这个节点可以扩展出a,b两个，
如果s[i]等于b，那么这个节点只能扩展出b，因为字典序必须>=s。
同理，t[i]=a的时候不能扩展出b,因为字典序必须<=t
代码相当简洁：https://blog.csdn.net/black_miracle/article/details/86536972

官方思路:https://codeforces.com/blog/entry/63753?locale=en

Can Bash Save the Day

https://cn.vjudge.net/problem/CodeForces-757G
动态点分治。过于复杂qwq

日后填坑

Array Splitting

https://cn.vjudge.net/problem/CodeForces-1197C

巧妙的贪心问题

设

$b[i] = a[i] - a[i-1]，i>=2, b1=0$

$a[ r ] - a[ l ]= \sum_{i=l+1}^{r}{b[i]}$

$a[ r ] - a[k+1] + a[ k ] -a[ l ] = \sum_{i=k+2}^{r}{b[i]} -\sum_{i=l+1}^{k}{b[i]} = (\sum_{i=l+1}^{r}{b[i]})-b[k+1]$

依次类推，我们粗略发现一个大区间分裂成小区间时，区间贡献之和减少一个bi

粗略证明：因为一旦某个点成为左端点，那么它不再与比它小的数产生贡献

a1必然是左端点

我们再在[2,n]找到k-1个左端点，就能得到k个区间。

按照bi的定义求出bi，然后sort，取最大的（k-1）个求和，然后减去它

#include<bits/stdc++.h>
/*--------------------------------------------------------------------*/
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
/*--------------------------------------------------------------------*/
int n,k,a[maxn],b[maxn];
int main()
{
    RD2(n,k);
    for(int i=1;i<=n;i++){RD1(a[i]);b[i]=a[i]-a[i-1];}    b[1]=0;
    sort(b+1,b+1+n);
    int sum=0;
    for(int i=n,cnt=1;cnt<k;i--,cnt++)sum+=b[i];
    printf("%d",a[n]-a[1]-sum);
    return 0;
}

Cards and Joy

https://cn.vjudge.net/problem/CodeForces-999F

中等难度dp题，和整数划分的dp有点像。。

设

$dp[num][person]=\max_{delt=1}^{min(k,num)}(dp[num-delt][person-1]+h[delt])$

num张牌分给person个人得到的最大值，可以从person-1个人的基础上加入1个人，并分配给他delt张牌转移而来

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,k;
int c[maxn],f[maxn],rec[maxn],dv[maxn],h[20];
vector<int>a;
ll dp[5050][505];
int main()
{
    RD2(n,k);
    for(int i=1;i<=n*k;i++){int t;RD1(t);rec[t]++;}
    for(int i=1;i<=n;i++)
    {
        int t;RD1(t);
        if(!dv[t])a.push_back(t);
        dv[t]++;
    }
    for(int i=1;i<=k;i++)RD1(h[i]);
    ll ans=0;
    while(a.size())
    {
        //see(a.size());
        ll tot=1LL*rec[a.back()],p=1LL*dv[a.back()];a.pop_back();
        CLR(dp);
        //see(tot),see(p);
        for(ll ps=1;ps<=p;ps++)
        for(ll i=1;i<=tot;i++)
        {//see(ps),see(i),NL;
        for(int v=1;v<=k&&v<=i;v++)
            dp[i][ps]=max(dp[i][ps],dp[i-v][ps-1]+h[v]);
        //see(i),see(ps),see(dp[i][ps]),NL;
        }    
        ans+=dp[tot][p];
    }
    printf("%lld",ans);
    return 0;
}

Flood Fill

https://cn.vjudge.net/problem/CodeForces-1114D

简单区间dp或者用巧妙的lcs

两种思路，见https://www.cnblogs.com/pkgunboat/p/10361375.html里面讲的十分详细

dp解法比较好想一点

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (5000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dp[maxn][maxn];
int a[maxn],n;
int main()
{
    RD1(n);for(int i=1;i<=n;i++)RD1(a[i]);
    int len=1;
    for(int i=2;i<=n;i++)if(a[i]!=a[len])
        a[++len]=a[i];
    n=len;
    INF(dp);
    for(int l=0;l<=n;l++)
    for(int st=1;st+l<=n;st++)
    {
        int ed=st+l;if(ed==st)dp[st][st]=0;
        if(a[st-1]!=a[ed+1])
            dp[st][ed+1]=min(dp[st][ed]+1,dp[st][ed+1]),
            dp[st-1][ed]=min(dp[st][ed]+1,dp[st-1][ed]);
        else
            dp[st][ed+1]=min(dp[st][ed]+1,dp[st][ed+1]),
            dp[st-1][ed]=min(dp[st][ed]+1,dp[st-1][ed]),
            dp[st-1][ed+1]=min(dp[st][ed]+1,dp[st-1][ed+1]);
    }
    printf("%d",dp[1][n]);
    return 0;
}

Mashmokh and ACM

https://cn.vjudge.net/problem/CodeForces-414B

简单dp

用当前状态更新未来状态，要比用过去状态更新当前状态方便一些

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (5000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll dp[2020][2020];
int n,k;
int main()
{
    RD2(n,k);
    for(int i=1;i<=n;i++)dp[1][i]=1;
    for(int pos=1;pos<k;pos++)
        for(int v=1;v<=n;v++)
            for(int nx=v;nx<=n;nx+=v)
                dp[pos+1][nx]=(dp[pos][v]+dp[pos+1][nx])%mod;
    ll sum=0;
    for(int i=1;i<=n;i++)sum=(sum+dp[k][i])%mod;
    printf("%lld",sum);
    return 0;
}

Lucky Common Subsequence

https://cn.vjudge.net/problem/CodeForces-346B

比较难搞的三维dp，思路参见https://www.cnblogs.com/justPassBy/p/3963200.html

理解之后，按自己的思路状态转移，但WA了，日后填坑

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (5000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
#define fi freopen("input.txt","r",stdin)
#define fo freopen("output.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s1[200],s2[200],v[200];
int dp[200][200][200];
int f[200];
int pre[200][200][200][3];
void getf(char *s)
{
    int l=strlen(s);
    int fail=-1,pos=0;f[0]=-1;
    while(pos<l)
    {
        while(fail!=-1&&s[pos]!=s[fail])fail=f[fail];
        f[++pos]=++fail;
    } 
}
void trans(int x,int y,int z,int xx,int yy,int zz,int val)
{
    if(dp[x][y][z]<dp[xx][yy][zz]+val)
        dp[x][y][z]=dp[xx][yy][zz]+val,
        pre[x][y][z][0]=xx,
        pre[x][y][z][1]=yy,
        pre[x][y][z][2]=zz;
}
int ans[200];
int main()
{
    scanf("%s%s%s",s1,s2,v);getf(v);
    int l1=strlen(s1),l2=strlen(s2),lv=strlen(v);
    NEG(pre);
    //for(int i=0;i<lv;i++)see(i),see(f[i]),NL;
    for(int i=0;i<l1;i++)for(int j=0;j<l2;j++)for(int k=0;k<lv;k++)
    {
        if(!i||!j||!k)if(s1[i]==s2[j]&&s1[i]==v[0])
        {
            dp[i][j][0]=1;//see(i),see(j),see(k),NL;
            //pre[i][j][0][0]=pre[i][j][0][1]=pre[i][j][0][2]=0;
        }
        
        trans(i+1,j,k,i,j,k,0),trans(i,j+1,k,i,j,k,0);
        if(s1[i+1]==s2[j+1])
        {
            //see(i),see(j),see(k),NL;
            trans(i+1,j+1,k,i,j,k,1);
            if(s1[i+1]==v[k+1])
                trans(i+1,j+1,k+1,i,j,k,1);
            else
            {
                int p=f[k+1];while(~p&&s1[i+1]==v[p])p=f[p];
                if(p==-1)p=0;
                if(v[p]==s1[i+1])trans(i+1,j+1,p,i,j,k,1);
            }
        }
    }
    int pos,val=-1;
    for(int i=0;i<lv-1;i++)
        if(val<dp[l1-1][l2-1][i])
            val=dp[l1-1][l2-1][i],
            pos=i;
    if(val<=0){printf("0");return 0;}
    int ed=val;
    int x=l1-1,y=l2-1;
    while(~pre[x][y][pos][0])
    {
        int xx=pre[x][y][pos][0],
            yy=pre[x][y][pos][1],
            zz=pre[x][y][pos][2];
        if(x-xx==1&&y-yy==1&&s1[x]==s2[y])
            ans[val--]=s1[x];
        x=xx,y=yy,pos=zz;
    }//see(val),see(x),see(y),see(pos);
    if(s1[x]==s2[y]&&s1[x]==v[0])ans[val]=s1[x];
    for(int i=1;i<=ed;i++)printf("%c",ans[i]);
    return 0;
}

2019.7.31