12.24

DP

1.洛谷P1880：环形石子合并

思路：对于直线形，就是枚举所有区间，dp[i][j]表示i-j石子合并后的最小或最大代价，之后枚举分点来转移，因此时间复杂度\(O(n^3)\)。遍历时按照长度来从小到大求解。

环形的话，延长两倍，但枚举len时上限仍然为n-1。最后遍历所有长度为n-1的区间，取最大或最小即可。

题解：

#include<bits/stdc++.h>
using namespace std;
const int M=4e2+20;
struct Stone{
    int n,a[M],dp[M][M],sum[M],dp2[M][M];
    void init(){
        scanf("%d",&n);
        for(int i=1;i<=2*n;++i)
            for(int j=i;j<=2*n;++j)
                dp2[i][j]=1e9+7;
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]),a[i+n]=a[i];
        for(int i=1;i<=2*n;++i)
            dp[i][i]=dp2[i][i]=0,sum[i]=sum[i-1]+a[i];
    }
    inline int query(int l,int r){
        return sum[r]-sum[l-1];
    }
    void run(){
        for(int len=2;len<=n;++len)
            for(int i=1,j=len;j<=2*n;++i,++j)
                for(int k=i;k<=j-1;++k)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+query(i,j)),
                    dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+query(i,j));
        int mn=1e9+7,mx=0;
        for(int i=1;i<=n;++i)
            mn=min(mn,dp2[i][i+n-1]),mx=max(mx,dp[i][i+n-1]);
        printf("%d\n%d\n",mn,mx);
    }
}s;
int main(){
    s.init(),s.run();
    return 0;
}

CF #610(div. 2)

A.Temporarily unavailable

题意：一维数轴，一个人要从a走到b，速度1/s，有一个基站在c，信号范围为r，问路程中有多少时间是没有信号的。

思路：实际上就是求线段[a,b]和[c-r,c+r]的交集。除了完全不相交的情况需要特判为0之外，其余情况可以

lf=max(lf,a),rt=min(rt,b),
printf("%d\n",b-a-(rt-lf));

来实现。

#include<bits/stdc++.h>
using namespace std;
struct Task{
    int a,b,c,r;
    int lf,rt;
    void init(){
        scanf("%d%d%d%d",&a,&b,&c,&r);
        if (a>b)
            swap(a,b);
        lf=c-r,rt=c+r;
    }
    void run(){
        init();
        if (rt<a||lf>b)
            printf("%d\n",b-a);
        else
            lf=max(lf,a),rt=min(rt,b),
            printf("%d\n",b-a-(rt-lf));
    }
}t;
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
        t.run();
    return 0;
}

B.K for the Price of One (Hard Version)

题意：有n个物品，给定k。要么只买一个，花a[i]元，要么买恰好k个，只付最大的钱，一共有p块钱，问最多能买多少个物品。（简单版本为k=2）

思路：首先按价格从小到大排序，确定恰好买k个的情况，总共有k种，即购买1-k,k+1-2k,2k+1-3k……；2-k+1,k+2-2k+1,2k+2-3k+1……；每种情况都从小到大遍历，直到买不了为止。之后，每种情况如果还有剩余，还可以单独购买前面没买的剩下的东西，记录前缀和，每次二分找<=剩余钱的最大数的位置，相加即可。

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r+1)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=4e5+20;
struct Task{
    int n,p,k,a[M];
    void init(){
        scanf("%d%d%d",&n,&p,&k);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
    }
    bool check(int x){
        int ans=0;
        while(x-k>=0)
            ans+=a[x],x-=k;
        for(int i=x;i>=1;--i)
            ans+=a[i];
        if (ans<=p)
            return true;
        return false;
    }
    void run(){
        init();
        sort(a+1,a+n+1);
        int l=k,r=n;
        while(l!=r){
            if (check(mid))
                l=mid;
            else
                r=mid-1;
            db(l);
            db(r);
        }
        if (l==k&&!check(l)){
            int ans=0,pt=0;
            while(ans+a[pt+1]<=p)
                ++pt,ans+=a[pt];
            printf("%d\n",pt);
        }
        else
            printf("%d\n",l);
    }
}t;
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
        t.run();
    return 0;
}

C.Petya and Exam

题意：考试有T分钟，n道题目，简单题目amin切，困难题目bmin切，可以随时离场。每道题目还有一个截止时间\(t_i\)，若在s分钟离场，但存在题目\(t_i<=s\)，那么就0分，否则就是做出来题目的个数为得分。问最大得分是多少。

思路：一开始思考，最优策略肯定是按照截止时间从小到大开始做（不论难易），所以先排序，从小到大开始做，如果做完一道题之后发现可以离场，那就记录一下题目个数，否则就必须继续做（这个可以用v[p+1].mant和t的比较来判断）。但这样过不了样例。问题在于，如果b>>a，那么做完一道难题之后，最优策略有可能是在下一个b的mant到来之前，先疯狂切简单题，这样反而答案更优，那就每次做完题之后再看看全切水题能多少分即可，更新最大值。

#include<bits/stdc++.h>
using namespace std;
const int M=4e5+20;
struct Prob{
    int diff,mant;
    bool operator<(const Prob &x)const{
        return mant<x.mant||(mant==x.mant&&diff<x.diff);
    }
};
struct Task{
    int n,T,a,b,numa;
    Prob v[M];
    void init(){
        numa=0;
        scanf("%d%d%d%d",&n,&T,&a,&b);
        for(int i=1;i<=n;++i)
            scanf("%d",&v[i].diff),numa+=(v[i].diff?0:1);
        for(int i=1;i<=n;++i)
            scanf("%d",&v[i].mant);
        sort(v+1,v+n+1);
        v[n+1].mant=T+1;
    }
    void run(){
        init();
        int mx=max(0,min(numa,(v[1].mant-1)/a)),now=0,t=0;
        for(int i=1;i<=n;++i){
            ++now;
            if (v[i].diff)
                t+=b;
            else
                t+=a,--numa;
            if (t>T)
                break;
            if (t<v[i+1].mant)
                mx=max(mx,now+min(numa,(v[i+1].mant-t-1)/a));
        }
        printf("%d\n",mx);
    }
}t;
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
        t.run();
    return 0;
}

D.Enchanted Artifact

题意：一个密码锁，密码为长度<=300的，由a和b组成的字符串。每次你输入密码会返回一个耐久，耐久为最小删除/插入/修改的次数使得你输入的密码和答案相同的次数。给你n+2次机会尝试。n不知道。

题意：首先求出a和b的个数，方法是用300的a和300的b去试，那么a的个数就是300-c1，b的个数就是300-c2。那么len=c1+c2。之后c2表示还缺的b的个数。以len个a的字符串为基准开始试，每次修改一位为b。如果答案比c2小，说明改对了，这位就是b，--c2。如果答案比c2大，说明改错了，这位是a，就改回去，c2不变。最后一共用了n+2次。

#include<bits/stdc++.h>
using namespace std;
const int M=300;
int main(){
    string s=string(M,'a');
    int c1,c2;
    cout<<s<<endl;cout.flush();
    scanf("%d",&c1);
    c1=300-c1;
    s=string(M,'b');
    cout<<s<<endl;cout.flush();
    scanf("%d",&c2);
    c2=300-c2;
    if (c1==0){
        s=string(c2,'b');
        cout<<s<<endl;cout.flush();
        scanf("%d",&c2);
        return 0;
    }
    else if (c2==0){
        s=string(c1,'a');
        cout<<s<<endl;cout.flush();
        scanf("%d",&c1);
        return 0;
    }
    int len=c1+c2;
    s=string(len,'a');
    int c=0;
    for(int i=0;i<len-1;++i){
        s[i]='b';
        cout<<s<<endl;cout.flush();
        scanf("%d",&c);
        if (c==0)
            return 0;
        if (c>c2)
            s[i]='a';
        else
            --c2;
    }
    if(c2)
        s[len-1]='b';
    cout<<s<<endl;cout.flush();
    scanf("%d",&c);
    return 0;
}