Educational Codeforces Round 137 (Rated for Div. 2)

A. Password

计算出现的数，从这些数中任意选两不同的，每种组合6种方案，计算输出即可

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
        }
        n=10-n;
        cout<<n*(n-1)*3<<endl;
    }
}

B. Permutation Value 贪心+构造

排列中一定含有1，我们让1在最左边，2在最右边，价值为2，最小

#include<bits/stdc++.h>
using namespace std;
int st[100];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<1<<' ';
        for(int i=n;i>2;i--){
            cout<<i<<' ';
        }
        cout<<2<<endl;
    }
}

C. Save the Magazines 贪心/dp

贪心：我们找到每一段连续的1，计算他们和第一个1前面0对应的价值之和，同时记录最小值，让答案减去最小值，以此类推，统计每一段连续的1

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int s[N],a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string ss;
        cin>>ss;
        for(int i=1;i<=n;i++)s[i]=ss[i-1]-'0';
        for(int i=0;i<=n;i++)a[i]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        long long ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]){
                int j=i;
                int minn=a[i-1];
                ans+=a[i-1];
                for(j=i;j<=n&&s[j];j++){
                    ans+=a[j];
                    minn=min(a[j],minn);
                }
                ans-=minn;

                i=j-1;
            }
        }
        cout<<ans<<endl;
    }
}

dp:我们可以逐个考虑是否将当前盖子左移。dp[i][0]表示第 i 个物品没有盖子时，前 i 个盒子所能保留的最大价值，dp[i][1]表示第i个物品有盖子时所能保留的最大价值

当第i个物品没有盖子时，dp[i][0]=max(dp[i-1][0],dp[i-1][1]);

当第i个物品有盖子时，若左移，则dp[i][0]=dp[i-1][0]+a[i-1];若不左移，则dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[i];

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int s[N],a[N],dp[N][2];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string ss;
        cin>>ss;
        for(int i=1;i<=n;i++)s[i]=ss[i-1]-'0';
        for(int i=0;i<=n;i++)a[i]=0,dp[i][0]=0,dp[i][1]=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++){
            if(s[i]){
                dp[i][0]=dp[i-1][0]+a[i-1];
                dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[i];
            }
            else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        }
        cout<<max(dp[n][1],dp[n][0])<<endl;
    }
}

D. Problem with Random Tests 暴力

我们可以让s等于原串，t为原串右移若干位。找到原串第一个不为1的位置，然后让原串右移[1，pos]，再右移的话最高位为0不能变成1，答案不是最优。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int main() {
    int n;
    cin >> n;
    auto cmp = [&](bitset<maxn>& a, bitset<maxn>& b) {
        for (int i = 0; i < n; i++)
            if (a[i] != b[i]) return a[i] > b[i];
        return false;
    };
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    while (s.back() == '0') s.pop_back();
    if (s.empty()) {
        cout << 0 << '\n';
        return 0;
    }
    n = s.size();
    bitset<maxn> bs(s);
    bitset<maxn> ans = bs;
    int pos0 = -1;
    for (int i = 0; i < n; i++)   //bitset 遍历是从低位往高位
        if (!bs.test(i)) {
            pos0 = i;
            cout << pos0 << endl;
            break;
        }
    if (pos0 == -1) {
        cout << string(n, '1') << '\n';
        return 0;
    }
    for (int i = 1; i <= pos0; i++) {
        auto t = bs | (bs << i);
        if (cmp(t, ans)) ans = t;
    }
    for (int i = 0; i < n; i++) cout << ans[i];
    cout << '\n';
}