Codeforces Round #547 (Div. 3) 完整题解

A. Game 23
题意：陈年老题，数字a->b，可以通过乘2或者乘3的方式，可以直接计算或者BFS，我没想直接BFS的。

#include <bits/stdc++.h>
using namespace std;

map <int, int> vis;
int main(){
    int x, y;
    scanf("%d %d", &x, &y);
    pair <int, int> p1;
    p1.first = x, p1.second = 0;
    queue <pair<int, int> > q;
    q.push(p1);
    int ans = -1;
    while(!q.empty()){
        pair<int, int> now = q.front();
        q.pop();
        if(now.first == y){
            ans = now.second;
            break;
        }
        vis[now.first] = 1;
        if(!vis[now.first*2] && now.first*2 <= y){
            q.push(make_pair(now.first*2, now.second+1));
            vis[now.first*2] = 1;
        }
        if(!vis[now.first*3] && now.first*3 <= y){
            q.push(make_pair(now.first*3, now.second+1));
            vis[now.first*3] = 1;
        }
    }
    printf("%d\n", ans);
}

B. Maximal Continuous Rest
题意：求数列连续1的最长长度，其中数列是个环。
解法：扩展到2*N的长度，然后扫描一遍就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
int n, a[maxn];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        a[n+i] = a[i];
    }
    int ans = 0;
    for(int i = 1; i <= 2 * n; ){
        if(a[i] == 0){
            i++;
            continue;
        }
        int j, temp = 1;
        for(j = i+1; j <= 2*n; j++){
            if(a[j] == a[i]){
                temp++;
            }else{
                break;
            }
        }
        ans = max(ans, temp);
        i = j;
    }
    printf("%d\n", ans);
    return 0;
}

C. Polycarp Restores Permutation
题意：需要你求出一个1到n的排列，首先给出n-1个数，每个数代表的是 $q_i=p_{i+1}-p_i$qi​=pi+1​−pi​，其中 $p_i$pi​代表i位置上的数
解法：根据上面的等式， $q_1=p_2-p_1$q1​=p2​−p1​, $q_2=p_3-p_2$q2​=p3​−p2​，两个等式加起来我们发现 $p_3-p1=q_1+q_2$p3​−p1=q1​+q2​，也就是说每个数 $p_n$pn​都可以表示为p1加 ${\sum }_{i=1}^{n-1}{q}_i$∑i=1n−1​qi​，并且由于是一个排列，所以我们还有 ${\sum }_{i=1}^n{p}_i=(n+1)\ast n/2$∑i=1n​pi​=(n+1)∗n/2和每一个 $p_i$pi​都恰好出现一次，且是1-n。综合这些条件就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n, q[maxn];
long long sumq[maxn];
int main(){
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        scanf("%d", &q[i]);
        sumq[i] = sumq[i-1] + (long long)q[i];
    }
    long long sum = (long long)n * (n + 1) / 2;
    for(int i = 1; i < n; i++){
        sum -= (long long)(n - i) * q[i];
    }
    if(sum%n != 0){
        puts("-1");
        return 0;
    }
    sum /= n;
    set <long long> s;
    vector <long long> v;
    v.push_back(sum);
    s.insert(sum);
    for(int i = 1; i < n; i++){
        v.push_back(sum+sumq[i]);
        s.insert(sum+sumq[i]);
    }
    if(s.size()!=n){
        puts("-1");
        exit(0);
    }
    for(int i = 1; i < n; i++){
        if(v[i]-v[i-1]!=q[i]){
            puts("-1");
            exit(0);
        }
    }
    int cnt = 1;
    for(auto it = s.begin(); it!=s.end(); it++){
        if(*it != cnt){
            puts("-1");
            exit(0);
        }
        cnt++;
    }
    for(int i = 0; i < v.size(); i++){
        printf("%lld ", v[i]);
    }
    printf("\n");
}

D. Colored Boots
题意：两个字符串，定义两个字符匹配当且仅当字符相同，或者某一个是?，或者都是?。问最大匹配数，且输出匹配的关系，需要保证a,b中所有位置最多只能匹配一次。
解法：按照题意，对每个字符，开2个队列记录出现的位置模拟即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 150010;
queue <int> q1[28], q2[28];
vector <pair<int, int> > ans;
char s1[maxn], s2[maxn];

int main(){
    int n;
    scanf("%d", &n);
    scanf("%s", s1);
    scanf("%s", s2);
    for(int i = 0; i < n; i++){
        if(islower(s1[i])){
            q1[s1[i]-'a'+1].push(i);
        }
        else{
            q1[27].push(i);
        }
    }
    for(int i = 0; i < n; i++){
        if(islower(s2[i])){
            q2[s2[i]-'a'+1].push(i);
        }
        else{
            q2[27].push(i);
        }
    }
    for(int i = 1; i <= 26; i++){
        while(!q1[i].empty() && !q2[i].empty()){
            ans.push_back(make_pair(q1[i].front(), q2[i].front()));
            q1[i].pop();
            q2[i].pop();
        }
        while(!q1[i].empty() && !q2[27].empty()){
            ans.push_back(make_pair(q1[i].front(), q2[27].front()));
            q1[i].pop();
            q2[27].pop();
        }
        while(!q1[27].empty() && !q2[i].empty()){
            ans.push_back(make_pair(q1[27].front(), q2[i].front()));
            q1[27].pop();
            q2[i].pop();
        }
    }
    while(!q1[27].empty() && !q2[27].empty()){
        ans.push_back(make_pair(q1[27].front(), q2[27].front()));
        q1[27].pop();
        q2[27].pop();
    }
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); i++){
        printf("%d %d\n", ans[i].first+1, ans[i].second+1);
    }
    return 0;
}

E. Superhero Battle
题意：给一个H和n，然后n个数，然后一个人来不停的循环从H减去一个数d[i],如果是负数就是加上，问最少多少次可以让H变为<=0，如果永远不能输出-1。
解法：先扫描一遍就可以特判出无解的情况，剩下的可以使用二分，不过这里二分的不是具体多少次，二是多少个第n轮会将H减少为小于等于0。因为只有当数列的总和>0时，才能保证二分的单调性，具体细节看代码啦。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
long long H, n, sum;
long long a[maxn];
long long maxx = 0;
long long ans = 0;
long long l, r, minn;
bool check(long long mid){
    long long temp = H - (mid - 1) * sum;
    if(maxx >= temp){
        long long temp_ans = ans;
        long long tt = 0;
        for(int i = 0; i < n; i++){
            tt += -a[i];
            if(tt >= temp){
                temp_ans = i + 1 + (mid - 1) * n;
                break;
            }
        }
        if(mid < minn){
            minn = mid;
            ans = temp_ans;
        }
        return 1;
    }
    return 0;
}

int main(){
    scanf("%lld%lld", &H, &n);
    sum = 0;
    for(int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
        sum += a[i];
        maxx = max(maxx, -sum);
    }
    if(sum >= 0){
        long long sum2 = 0;
        bool flag = false;
        for(int i = 0; i < n; i++){
            sum2 += -a[i];
            if(sum2 >= H){
                flag = true;
                printf("%d\n", i+1);
                return 0;
            }
        }
        if(flag == false){
            puts("-1");
            return 0;
        }
    }
    sum = abs(sum);
    long long bas = H * n / sum;
    l = 1;
    r = H / sum + 2;
    minn = r;
    long long mid;
    while(l <= r){
        mid = (l + r) / 2;
        if(check(mid)){
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

F1. Same Sum Blocks (Easy)
题意：要你从长度为n(n<=50)的序列选出最多的子序列，使得这些子序列的和都相等且每个子序列都不相交。
解法：数据范围比较小，直接统计出每个sum对应的所有l,r区间，然后按照r排序，扫描一遍得到答案。需要注意的是，和可能为负数，所以我离散化了一下。

#include <bits/stdc++.h>
using namespace std;
int n, a[55], sum[55];
vector <int> v;

int getid(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

struct node{
    int l, r;
    node(){}
    node(int _l, int _r):l(_l), r(_r){}
    bool operator<(const node &rhs) const{
        return r < rhs.r;
    }
};

vector <vector<node> > v2(3000);

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            v.push_back(sum[j] - sum[i-1]);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            int id = getid(sum[j] - sum[i-1]);
            v2[id].push_back(node(i, j));
        }
    }
    int ans = 0;
    vector <node> pr;
    for(int i = 0; i < 3000; i++){
        if(v2[i].size() == 0) continue;
        sort(v2[i].begin(), v2[i].end());
        //for(int k = 0; k < v2[i].size(); k++){
        int ret = 1;
        int last = v2[i][0].r;
        for(int j = 1; j < v2[i].size(); j++){
            if(v2[i][j].l > last){
                ret++;
                last = v2[i][j].r;
            }
        }
        ans = max(ans, ret);
        if(ans == ret){
            pr.clear();
            pr.push_back(v2[i][0]);
            last = v2[i][0].r;
            for(int j = 1; j < v2[i].size(); j++){
                if(v2[i][j].l > last){
                    pr.push_back(v2[i][j]);
                    last = v2[i][j].r;
                }
            }
        }
        //}
    }
    printf("%d\n", ans);
    for(int i = 0; i < pr.size(); i++){
        printf("%d %d\n", pr[i].l, pr[i].r);
    }
    return 0;
}

F2. Same Sum Blocks (Hard)
上一题的进阶版n<=1500，考虑一下可以优化的地方，我们不能把所有和对应的区间存下来再排序，我们想是否可以通过枚举的方法避免排序并直接维护最长的序列，其实是可以的。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
int n, a[maxn];
vector <pair<int, int> > ptr;
map <int, int> mp;
unordered_map <int, vector<pair<int, int> > > mp2;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        a[i] = a[i - 1] + a[i];
    }
    int ans = 1;
    ptr.push_back(make_pair(1, 1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            int sum = a[i] - a[j-1];
            if(mp.find(sum) == mp.end() || mp[sum] < j){
                mp2[sum].push_back(make_pair(j, i));
                mp[sum] = i;
            }
        }
    }

    for(unordered_map<int, vector<pair<int, int> > >::iterator it = mp2.begin(); it != mp2.end(); it++){
        if((*it).second.size() > ans){
            ans = (*it).second.size();
            ptr = (*it).second;
        }
    }
    printf("%d\n", ans);
    for(int i = 0; i < ans; i++){
        printf("%d %d\n", ptr[i].first, ptr[i].second);
    }
    return 0;
}

题目真多。。。
G. Privatization of Roads in Treeland
题意：给定一个 N 个点的无根树，现给这个树进行染色。定义一个节点是坏点，若满足与该节点相连的至少两条边是相同的颜色，求至多有 k 个坏点的情况下最少需要几种颜色才能进行合法染色。
解法：现在比较傻，这题还真没想到。考虑一个点不是坏点的情况，必须满足与之相连的每条边颜色均不同，设最多的点的度数为 X，若一个坏点也没有，那么最少肯定需要 X 种颜色，若允许有 K 个坏点，则意味着度数第 K+1 大的节点相连的每条边必须颜色均不同，即：答案为第 K+1 大点的度数。至于染色，满足以上条件的话，随便染色即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct node{
    int v, nxt;
}E[maxn<<2];

int n, k, ans, du[maxn], color[maxn], head[maxn], edgecnt;
void add_edge(int u, int v){
    E[edgecnt].v = v;
    E[edgecnt].nxt = head[u];
    head[u] = edgecnt++;
}
bool cmp(int x, int y){
    return x > y;
}
void dfs(int u, int fa, int c){
    for(int i = head[u]; ~i; i = E[i].nxt){
        int v = E[i].v;
        if(v == fa) continue;
        ++c;
        if(c > ans){
            c -= ans;
        }
        color[i / 2] = c;
        dfs(v, u, c);
    }
}
int main(){
    edgecnt = 0;
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
        ++du[x];
        ++du[y];
    }
    sort(du+1, du+n+1, cmp);
    ans = du[k+1];
    dfs(1, 0, 0);
    printf("%d\n", ans);
    for(int i = 0; i < n-1; i++){
        printf("%d ", color[i]);
    }
    printf("\n");
}