Educational Codeforces Round 137 (Rated for Div. 2)

A. Password

void solve(){
    int n=read();
    for(int i=1;i<=n;i++)int x=read();
    cout<<combination(10-n,2)*6<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Permutation Value

void solve(){
    int n=read();deque<int>a;
    for(int i=n;i>=1;i--){
        if(i%2==0)a.push_back(i);
        else a.push_front(i);
    }
    for(auto x:a){
        cout<<x<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Save the Magazines

int f[N],a[N];
void solve(){
    int n=read();
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    memset(f,0 ,sizeof f);
    for(int i=n-1;i>=0;i--){
        if(s[i]=='0')f[i]=max(f[i],f[i+1]);
        else {
            f[i-1]=max({f[i+1]+a[i-1],f[i-1],f[i]+a[i-1]});

            f[i]=max(f[i+1]+a[i],f[i]);
        }
    }
    cout<<f[0]<<'\n';
}

D. Problem with Random Tests

题意：

选择01字符串的两个字串，让两个字符串二进制或最大，求最大值。题目说明，样例为纯随机字符串。

Tag：

暴力枚举+贪心。

解法：

对于将要选择的字串命名为a和b，那么令其中一个（不妨令a字串）为s串。因为字串的1所在位置越大，他能构成的异或值也更大。那么此时b字串要做的就是尽量将a串的0变为1。这下找到a串的第一个非前导0的位置，选择一个1填上去，之后比较后续的值是否更大，b字串的长度是 a的长度-没有0出现的最长前缀长。这时候这是一个O(n^2)的算法，但是因为纯随机字符串，假设在第30位才找到第一个0的概率是2的30次方分之一，所以b的长度会接近n。那么对b字串的枚举数就很小，会是一个带较大常数的O(n)算法。

void solve(){
    int n=read(),sb=0,z=-1;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            sb=i;
            break;
        }
    }
    string a,b;
    for(int i=sb;i<n;i++){
        a+=s[i];
        if(s[i]=='0'&&z==-1){
            z=i;
        }
    }
    int la=n-sb;
    int lb=n-z;
    for(int i=0;i<n-lb;i++){
        string tmp;
        if(s[i]==0)continue;
        for(int j=0;j<lb;j++){
            tmp+=max(s[i+j],a[j+z-sb]);
        }
        b=max(b,tmp);
    }
    string ans;
    for(int i=0;i<la-lb;i++){
        ans+=a[i];
    }
    ans+=b;
    int fl=0;
    for(int i=0;i<ans.size();i++){
        if(ans[i]=='1')fl=1;
        if(fl)cout<<ans[i];
    }
    if(fl==0)cout<<0<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

E. FTL

题意：

给定两个激光发射器，给定伤害和充电时间，以及怪物的血量，以及每次被攻击的护盾承伤，求击杀怪物的最短时间。

Tag：

动态规划

解法：

首先发现每一次同时攻击后，两艘飞船都会回到初始状态，所以可以尝试dp找什么时候同时攻击。设f(i)函数表示打出i点伤害的最短时间。

对于状态转移，先考虑最简单的由一个炮打一次就完成，转移方程为f[i]=min(f[max(0,i-p1+s)]+t1,f[max(0,i-p2+s)]+t2)

然后是两个炮互相等待一起进攻状态转移，这样的进攻造成（先假设1号炮自己发射了j次，最后一次两个炮共同发射）damage=(j-1)*(p1-s)+(t1*j-t2)/t2*(p2-s)+p1+p2-s

转移方程为f[i]=min(f[i],f[max(0,i-damage)]+t1*j)

整个算法的复杂度为O(n^2)

#define int long long
int f[N];
void solve(){
    int p1=read(),t1=read(),p2=read(),t2=read(),h=read(),s=read();
    memset(f,inf,sizeof f);
    f[0]=0;
    for(int i=1;i<=h;i++){
        f[i]=min(f[max(0ll,i-(p1-s))]+t1,f[max(0ll,i-(p2-s))]+t2);
        for(int j=1;j<=i;j++) {
            if(t1*j>=t2){ 
                int dmg=(j-1)*(p1-s)+(t1*j-t2)/t2*(p2-s)+p1+p2-s;
                f[i]=min(f[i],f[max(0ll,i-dmg)]+t1*j);
            } 
            if(t2*j>=t1){
                int dmg=(j-1)*(p2-s)+(t2*j-t1)/t1*(p1-s)+p1+p2-s;
                f[i]=min(f[i],f[max(0ll,i-dmg)]+t2*j);
            }
        }
    }
    cout<<f[h]<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}