Codeforces Round #723 (Div. 2)

A. Mean Inequality

题意:
给定 2n (n为偶数) 个互不相同的元素,求一个排列使得,对于所有 i 满足 a_i \ne \frac{a_{i-1}a_{i+1}}{2}

Solution:
从小到大排序,分 2 组,{a_1,a2,\cdot \cdot \cdot, a_n}{a_{n+1},a_{n+2},\cdot \cdot \cdot, a_{2n}}, 交替组成序列即是答案。

Code:

int t, n;
int a[105];

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i = 1; i <= 2 * n; i ++){
            cin >> a[i];
        }
        sort(a + 1, a + 2 * n + 1);
        for(int i = 1; i <= n; i ++){
            cout << a[i] << " " << a[i + n] << " ";
        }
        cout << endl;
    }

    return 0;
}

B. I Hate 1111

题意:
给定 x, 判断 x 是否能由 11, 111, 1111, \cdot \cdot \cdot 组成。

Solution1:
由定理 nm 最小不能组成的数字是 nm - (n + m) 可知
本题 x > 1099 都是可以组成的。
所以我们只要跑一遍完全背包即可。

Code:

int t, n;
int x;
int f[10000];
int v[11] = {0, 11, 111, 1111, 11111, 111111, 1111111, 11111111,  111111111};

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        memset(f, 0, sizeof(f));
        if(n > 1099)   puts("YES");
        else{
            for(int i = 1; i <= 8; i ++){
                for(int j = v[i]; j <= n; j ++){
                    f[j] = max(f[j - v[i]] + v[i], f[j]);
                }
            }
            puts(f[n] == n ? "YES" : "NO");
        }
    }

    return 0;
}

Solution2:

设:11A+111B=Z
令:B=11C+D
则原式:
11A+111\left( 11*C+D \right) =Z

=11\left( A+111C \right) +111D=Z

所以可以直接暴力的判断。

Code:

int t, n;

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i = 1; i <= 20; i ++){
            if(n % 11 == 0) {
                puts("YES");
                break;
            }
            n -= 111;
            if(n < 0){
                puts("NO");
                break;
            }
        }
    }
    return 0;
}

C2. Potions (Hard Version)

题意:
给定一个正负序列,初始值为 0 , 求一个最大长度,使得求和的过程中不出现负数。

Solution:
贪心, 维护一个最小值的优先队列即可。

Code:

int n;
ll a[200005];

priority_queue<ll, vector<ll>, greater<ll> > q;

int main(){
    __;
    cin >> n;
    ll sum = 0, res = 0, ans = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        q.push(a[i]);
        sum += a[i];
        res ++;
        while(sum < 0){
            ll t = q.top();
            q.pop();
            sum -= t;
            res --;
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
    return 0;
}

D. Kill Anton

题意:
给定一个只包含 ANOT 的字符串,求一个字符串使得,交换相邻两个字符串,变成原字符串最多。

Solution:
相同字符连续的话,一定是最多的。
所以暴力的枚举即可。

Code:

int t;
int p[5] = {0, 1, 2, 3, 4};
int a[N], sum[N][4], cnt[N], rk[N];
string s, c = "ANOT";

void solve(){
    string ans = "";
    int n = s.size();
    ll cur = 0;
    for(int i = 1; i <= 4; i ++){
        sum[0][i] = 0;
        cnt[i] = 0;
    }
    for(int i = 1; i <= n; i ++){
        a[i] = c.find(s[i - 1]) + 1;
    }

    for(int i = 1; i <= 4; i ++){
        for(int j = 1; j <= n; j ++){
            sum[j][i] = sum[j - 1][i] + (i == a[j]);
            cnt[i] = sum[j][i];
        }
    }

    do{
        for(int i = 1; i <= 4; i ++)    rk[p[i]] = i;
        ll res = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= 4;j ++){
                if(rk[j] > rk[a[i]])    res += sum[i][j];
            }
        }

        if(res >= cur){
            cur = res;
            ans.clear();
            for(int i = 1; i <= 4; i ++){
                ans += string(cnt[p[i]], c[p[i] - 1]);
            }
        }

    }while(next_permutation(p + 1, p + 5));

    cout << ans << endl;
}

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> s;
        solve();
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注