Codeforces Round #498 (Div. 3)

题目链接

A  00:02
B  00:19
C  00:27
D  01:08
E  01:25
F  --:--

A. Adjacent Replacements

因为操作是由顺序的
奇数加一永远时在偶数减一之前
依次对于每个数如果是奇数就不需要改变
如果是偶数则减一

    int n = read();
    for(int i = 1 ; i <= n ; i ++){
        int x = read();
        if(x & 1) cout << x << " " ;
        else cout << x - 1 << " ";
    }

B. Polycarp's Practice

将一个序列分成k段序列使得每段序列的最大值之和最大
将序列排序找到最大的k个数,并记录一下着k个数的位置
然后对着k个位置重现排列,这个序列一定不会出现重复的数
然后对这个序列分割每遇到一个在这个序列的数就分割
一开始虽说单独处理了最后一段,但是不知道怎么回事就只是单独拉出来,应该改一下从上一个数之间到n
不是从上一个数到下一个数
----------------大脑持续空白中----------------

    int n = read(), k = read();
    for(int i = 1 ; i <= n ; i ++){
        int x = read();
        a.push_back(x);
        b.push_back(make_pair(x, i));
    }
    sort(b.rbegin(), b.rend());
    int ans = 0;
    for(int i = 0 ; i < k ; i ++)c.push_back(b[i].second), ans += b[i].first;
    cout << ans << endl;
    sort(all(c));
    int l = 1;
    for(int i = 0 ; i < Len(c) - 1 ; i ++){
        cout << c[i] - l + 1 << " " ;
        l = c[i] + 1;
    }
    cout << n - l + 1 << endl;

C. Three Parts of the Array

将一个序列分成三段使第一段的和等于第三段,并且最大话这个操作的和
枚举第一段序列二分第三段序列维护的倒叙前缀和即可
注意题目会爆int,wa10了身败名裂.jpg

    int n = read();
    for(int i = 1 ; i <= n ; i ++) a[i] = read();
    for(int i = n ; i >= 1 ; i --) b[i] = b[i + 1] + a[i];
    int s1 = 0, ans = 0;;
    for(int i = 1 ; i < n ; i ++){
        s1 += a[i];
        int l = i + 1 , r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(b[mid] <= s1) r = mid ;
            else l = mid + 1;
        }
        if(s1 == b[r]) ans = s1;
    }
    cout << ans << endl;

D. Two Strings Swaps

你可以任意交换a_i, a_{n-i+1},b_i,b_{n-i+1}这四个值
也可以去修改字符串a的单个字符,
你需要最小化第二个操作使其用这些操作让字符串a等于字符串b
仔细分析就知道每次修改的四个字符都是互不重复的,因此直接分类讨论
详情看代码

    int n; cin >> n;
    cin >> a >> b;
    int ans = 0 ;
    if(n & 1){
        if(a[n / 2] != b[n / 2]) a[n / 2] = b[n / 2],ans ++;
    }
    for(int i = 0 ; i < n / 2 ; i ++){
        map<char, int> m;
        m[a[i]] ++;m[a[n - i - 1]] ++;
        m[b[i]] ++;m[b[n - i - 1]] ++;
        if(m.size() == 1) continue;
        if(m.size() == 2){
            if(m[a[i]] == 2) continue;
            ans ++;
        }
        if(m.size() == 3){
            if(a[i] == a[n - i - 1]) ans += 2;
            else ans ++;
        }
        if(m.size() == 4) ans += 2;
        m.clear();
    }
    cout << ans << endl;

E. Military Problem

给你一颗树,有q次询问,每次询问需要给出一颗子树dfs序排名第k的序号
跑一边dfs维护序列和子树大小即可

void dfs(int u){
    a[++ tot] = u;
    d[u] = tot;
    sie[u] = 1;
    for(auto v : g[u]){
        dfs(v);
        sie[u] += sie[v];
    }
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    // ..........................................................
    int n = read(), q = read();
    a[1] = 1;
    for(int i = 2 ; i <= n ; i ++) g[read()].push_back(i);
    dfs(1);
    for(int i = 1 ; i <= q ; i ++){
        int u = read(),  k = read();
        if(sie[u] < k) cout << -1 << endl;
        else cout << a[d[u] + k - 1] << endl;
    }
    //...........................................................
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    return ~~(0^_^0);
}

F. Xor-Paths

你有一个20*20的单元格
你需要从(1,1)->(20,20),问中间路径异或和为k的情况有多少种
当时在比赛过程中没有任何思路,结束的时候去看题解,发现就把一次暴力跑到边界,下次暴力从另一个方向跑回去跑到中间同样的地方在维护答案(双向搜索)

void dfs(int x, int y, int t){
    if(x > n || y > m) return ;
    if(x + y == (n + m) / 2 + 1){
        b[x][y][t] ++;
        return ;
    }
    dfs(x + 1, y, t ^ a[x + 1][y]);
    dfs(x, y + 1, t ^ a[x][y + 1]);
}
void rdfs(int x, int y, int t){
    if(x < 1 || y < 1) return ;
    if(x + y == (n + m) / 2 + 1){
        ans += b[x][y][t ^ k ^ a[x][y]];
        return ;
    }
    rdfs(x - 1, y, t ^ a[x - 1][y]);
    rdfs(x, y - 1, t ^ a[x][y - 1]);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    // ..........................................................
    n = read(), m = read(), k = read();
    for(int i = 1 ; i <= n; i++){
        for(int j = 1 ; j <= m ; j ++){
            a[i][j] = read();
        }
    }
    dfs(1, 1, a[1][1]);
    rdfs(n, m, a[n][m]);
    cout << ans << endl;
    // ..........................................................
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    return ~~(0^_^0);
}
点赞

发表评论

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