2019.7.31

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





Can Bash Save the Day

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






Array Splitting

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


巧妙的贪心问题
设

依次类推，我们粗略发现一个大区间分裂成小区间时，区间贡献之和减少一个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;
}

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

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;
} 

简单区间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;
}


简单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;
} 

比较难搞的三维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;
}

全部评论

相关推荐

昨天 20:43
已编辑
东北大学 Java
点赞 评论 收藏
分享
12-03 21:27
武汉大学 Java
点赞 评论 收藏
分享
10-10 15:50
已编辑
快手_电商_外包(实习员工)
点赞 评论 收藏
分享
12-04 10:31
远景_运维开发工程师(准入职员工)
远景能源内推， 远景能源内推码
目前被问比较多的&nbsp;1️⃣每个人只能投递一次吗？&nbsp;A：是的！所以一定要优化好简历，一面二面都挺重要的！但其实去年秋招的时候，动力来我们学校开宣讲会的过程中，hr帮很多入池子的同学转岗了～所以一定要珍惜每次宣讲会！（无论是不是我们公司的哈）&nbsp;2️⃣看BG吗？&nbsp;A：目前入职后其实感觉大家的BG都挺多样的，所以放心大胆投！海硕友好（周围很多海硕）&nbsp;3️⃣英语要求高吗？&nbsp;A：其实投递过程中可以看到远景对六级的分数划分是非常包容的，就是只有没过、过了和六百五以上三种类型，主包属于过了但还不到六百多分这样…👉👈有隐约听说/感受到，稍微卡六级吧，所以理工科类的可能要稍微注意一下，只是听说，没有明确规定必须...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了去实习，我赌上了___ #
18981次浏览 197人参与
# 摸鱼被leader发现了怎么办 #
70629次浏览 407人参与
# 百融云创求职进展汇总 #
159次浏览 0人参与
# uu们，春招你还来吗？ #
11157次浏览 79人参与
# 2025年终总结 #
11709次浏览 211人参与
# 哪一瞬间让你觉得“这班不如不上” #
10475次浏览 147人参与
# 父母对你找工作是助力还是阻力？ #
12773次浏览 192人参与
# 如果可以，你希望哪个公司来捞你 #
154717次浏览 650人参与
# 降低公积金和取消房补怎么选 #
23337次浏览 79人参与
# 工作中哪个瞬间让你想离职 #
109325次浏览 771人参与
# 十二月请对我好一点 #
23900次浏览 326人参与
# 高薪高压 vs 低薪wlb，你怎么选？ #
10151次浏览 110人参与
# 一人推荐一个值得做的项目 #
8531次浏览 115人参与
# 运营每日一题 #
112616次浏览 885人参与
# 第一份工作能做外包吗？ #
85803次浏览 574人参与
# 这些公司卡简历很严格 #
80204次浏览 367人参与
# 硬件人的简历怎么写 #
317081次浏览 3063人参与
# 工作前VS工作后，你的心态变化 #
12567次浏览 152人参与
# 学历or实习经历，哪个更重要 #
201903次浏览 1069人参与
# 秋招提前批启动你开冲了吗 #
160681次浏览 2244人参与
# 工作中出现了XX情况正常吗 #
30758次浏览 208人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务