【Quest OJ Emulate 9 / 19】Deep ♂ Dark ♂ Fantasy / 题解

比赛地址

Deep

题目描述

失败的燃烧军团想要逃回深渊,Khadgar 想要追击它们。

然而进入深渊的传送门只有一座,燃烧军团和 Khadgar 各有一些法力水晶,由 Khadgar 先手,双方每次可以作出如下选择:

  • 使用一个法力水晶,使得传送门的法力等级增加一。

  • 不用法力水晶,让对方增加等于传送门法力等级的深度,然后将传送门的法力值清零。特别地,若法力水晶数不为零且传送门法力等级为零则不能进行这样的操作。

双方都会采取最优策略使自己的最终深度与对手深度的差最大(初始时深度均为零)。

现在多次给定双方起始的法力水晶数量 A, B,求 Khadgar 与燃烧军团的的最终深度差。

思路

结论题。对于 A, B 均为正整数的时候答案就是 A − B − 2,否则特判掉即可。

代码

为什么要写快读,这不是 $O(T)$ 做法嘛?

因为我用 cin cout 写的程序只有 40分,尽管是 $O(T)$ 但是它还是 T 了。

#include 
using namespace std;
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
int main(){
    int T,a,b;
    io>>T;
    while(T--){
        io>>a>>b;
        if ((a*b)) printf("%d\n",a-b-2);
        else if (!a) printf("%d\n",-b);
        else printf("%d\n",a);
    }
}

Dark

题目描述

给定一个长为 $n$ 的序列,每次可以选定两个相邻的正整数令它们均减1,直到不能进行更多操作。求最少的操作次数。

思路

看数据范围可以写一个 $O(\sum A_i)$的 dp。
令 $dp_{i,j,1/0}$ 为考虑到第 $i$ 个数,这个数余下的值为 $j$,前一个数是否为零。

代码

#include 
#define maxn 5000101
#define oo 0x3f3f3f3f
using namespace std;
int dp[maxn][2],tem[maxn][2],suf[maxn];
int ans=oo,a[maxn],n,top;
void work(){
    for (int i=0;i<=top;i++)
    dp[i][0]=dp[i][1]=suf[i]=oo;
    dp[0][0]=suf[0]=0;
    for (int i=1;i<=n;i++){
        for (int j=a[i-1]+1;j<=a[i];j++)
        dp[j][0]=dp[j][1]=suf[j]=oo;
        for (int j=a[i];~j;j--){
            tem[j][0]=tem[j][1]=oo;
            tem[j][0]=min(tem[j][0],a[i]-j+suf[a[i]-j]);
            tem[j][0]=min(tem[j][0],a[i]-j+dp[a[i]-j][0]);
            tem[j][1]=min(tem[j][1],a[i]-j+dp[a[i]-j][0]);
        }
        suf[a[i]+1]=oo;
        for (int j=a[i];~j;j--){
            dp[j][0]=tem[j][0];
            dp[j][1]=tem[j][1];
            suf[j]=min(suf[j+1],dp[j][1]);
        }
    }
    ans=dp[0][0];
    for (int i=0;i<=a[n];i++) ans=min(ans,dp[i][1]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],top=max(top,a[i]);
    work();
    cout<

Fantasy

题目描述

给定一个长度为 $n$ 的序列,求 $k$ 个不同的长度在 $L,R$ 之间的数字和最大的字串。

思路

Show Comments