Codeforces Round #436 (Div. 2) 题解

题目链接：http://codeforces.com/contest/864

A. Fair Game

题意：水题，不说了，就是把所有数丢到set判断set的size是不是等于2，并且这两个元素出现的次数是否相等。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, x, a[110];

int main()
{
    scanf("%d", &n);
    set <int> s;
    map <int,int> mp;
    while(n--){
        scanf("%d", &x);
        s.insert(x);
        mp[x]++;
    }
    if(s.size()==2 && mp[*s.begin()] == mp[*s.rbegin()]){
        puts("YES");
        printf("%d %d\n", *s.begin(), *s.rbegin());
    }
    else{
        puts("NO");
    }
}

B. Polycarp and Letters

题意：选择一个可以不连续的子串，问这个字串是否都是小写字母，并且每个小写字母只能出现一次，还有两个小写字母之间不能有大写字母，问这个字串的最大字符数是多少？

解法：枚举起点，终点，用set来判。中间碰到大写字母continue掉。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[200];

int main(){
    int n;
    int ans = 0;
    scanf("%d", &n);
    scanf("%s", s+1);
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            bool flag = 1;
            set <char> ss;
            for(int k=i; k<=j; k++){
                if(isupper(s[k])){
                    flag = 0;
                    break;
                }
                ss.insert(s[k]);
            }
            if(flag&&ss.size()<=j-i+1){
                ans = max(ans, (int)ss.size());
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

C. Bus

题意：一辆车在水平路线上行驶，行驶到a又转向到0行驶，汽车有一个油箱最多***的油，路上有个加油站在f位置，问汽车走k趟最少需要加多少次油？一趟就是0->a或者a->0

解法：模拟题，注意最后一趟的情况即可。

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

int main()
{
    LL a,b,f,k;
    scanf("%lld%lld%lld%lld", &a,&b,&f,&k);
    int cap = b;
    int offset = 0;
    int ans = 0;
    bool can=1;
    while(k--){
        if(offset==0){
            b-=f;
            if(b < 0){
                can = 0;
                break;
            }
            if(k==0){
                if(b<a-f){
                    ans++;
                    b=cap;
                }
            }
            else{
                if(b<(a-f)*2){
                    ans++;
                    b=cap;
                }
            }
            b -= a-f;
            if(b<0){
                can = 0;
                break;
            }
        }
        else{
            b-=a-f;
            if(b < 0){
                can = 0;
                break;
            }
            if(k==0){
                if(b<f){
                    ans++;
                    b=cap;
                }
            }
            else{
                if(b<2*f){
                    ans++;
                    b=cap;
                }
            }
            b-=f;
            if(b<0){
                can=0;
                break;
            }
        }
        offset^=1;
    }
    if(can==0) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

D. Make a Permutation!

题意：给了一个n个数的序列，现在要把这n个数变成一个排列，问最少的改变数的次数，在次数最少的情况下保证字典序最小。

解法：用一个set把没有访问的数丢进去，扫到序列出现多次的数的第一次，用set里面最小的数去尝试替换在序列里出现多次的数，第二次及以后扫描到的话就直接替换，这样就可以保证字典序最小了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n, a[maxn];
set <int> s1;
map <int, int> mp;
bool vis[maxn];
int main()
{
    scanf("%d", &n);
    mp.clear();
    for(int i=1; i<=n; i++) s1.insert(i);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        if(s1.find(a[i]) != s1.end()){
            s1.erase(a[i]);
        }
        mp[a[i]]++;
    }
    int ans = 0;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++){
        if(mp[a[i]]==1&&!vis[a[i]]){
            a[i] = a[i];
            mp[a[i]]--;
        }
        else if(mp[a[i]]>1&&!vis[a[i]]){
            mp[a[i]]--;
            if(*s1.begin()<a[i]){
                a[i] = *s1.begin();
                s1.erase(a[i]);
                ans++;
            }
            else{
                a[i] = a[i];
            }
            vis[a[i]] = 1;
        }
        else{
            a[i] = *s1.begin();
            s1.erase(a[i]);
            ans++;
        }
    }
    printf("%d\n", ans);
    for(int i=1; i<=n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

E. Fire

题意：需要去拯救n个物品，对于每个物品有拯救这个物品的时间，这个物品完全被能被拯救的截止时间和这个物品的价值，问能拯救的物品的最大价值，并输出拯救了哪些物品。

解法：首先按照d的大小对物品排序，然后这就转化成了一个01背包问题，我们在背包转移的时候记录下路径就可以了，dp[i][j]代表第i个个物品在j时间拯救的最大价值。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int n, dp[105][maxn], pre[105][maxn];
struct node{
    int t, d, p, id;
    node(){}
    node(int t, int d, int p, int id):t(t),d(d),p(p),id(id){}
    bool operator<(const node &rhs) const{
        return d < rhs.d;
    }
}p[maxn];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d", &p[i].t,&p[i].d,&p[i].p);
        p[i].id = i;
    }
    memset(dp, 0x80, sizeof(dp));
    dp[0][0] = 0;
    sort(p+1, p+n+1);
    for(int i=1; i<=n; i++){
        int t = p[i].t;
        int d = p[i].d;
        int pp = p[i].p;
        for(int j=0; j<maxn; j++){
            if(dp[i-1][j]>=0){
                if(dp[i-1][j]>dp[i][j]){
                    dp[i][j]=dp[i-1][j];
                    pre[i][j]=j;
                }
                if(j+t<d){
                    if(dp[i-1][j]+pp>dp[i][j+t]){
                        dp[i][j+t] = dp[i-1][j]+pp;
                        pre[i][j+t] = j;
                    }
                }
            }
        }
    }
    int v = max_element(dp[n], dp[n]+maxn)-dp[n];
    int ans = dp[n][v];
    printf("%d\n", ans);
    stack <int> s;
    for(int i=n; i>=1; i--){
        if(v != pre[i][v]){
            s.push(p[i].id);
        }
        v = pre[i][v];
    }
    printf("%d\n", (int)s.size());
    while(!s.empty()){
        printf("%d ", s.top());
        s.pop();
    }
    printf("\n");
    return 0;
}

F：

题意：给你一个有向图，问任意两点间的字典序最小路径（如果存在）上的第k个节点是啥

解法：膜了一发题解。http://blog.csdn.net/weixin_37517391/article/details/78105828?locationNum=2&fps=1 如果不考虑环的情况，那么我们可以把从起点相同的询问放在一起来操作，然后从s点开始按照字典序选边，跑一边dfs，用栈来存储当前的路径。每到一个t点的时候。回答一下<s,t>的询问，即拿出栈中第k个位置的点，这样的话，我们跑n次dfs就可以回答所有的询问了（offline操作）。

现在问题变难了，如果有环的话，字典序最小的路径有可能不存在。这就需要我们在dfs的过程中进行判环，想到使用tarjan算法。

我们每次dfs一个点u的时候，令low[u] = inf;这样的话，如果判断有dfn[u]>=low[u]（含义就是出现了一个字典序小的环）那么从经由u到达的其他点的答案均为-1了。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3010;
const int maxq = 4e5+10;
struct node{
    int id,x,y,k;
    node(){}
    node(int id, int x, int y, int k):id(id),x(x),y(y),k(k){}
    bool operator<(const node &rhs) const{
        return x < rhs.x;
    }
}qs[maxq];
vector <node> Q[maxn];
int n, m, q, ans[maxq];
int dfsclk, top;
int dfn[maxn], low[maxn], instk[maxn], stk[maxn];
vector <int> G[maxn];
void dfs(int u, int ok){
    dfn[u] = ++dfsclk;
    low[u] = inf;
    stk[top++] = u;
    instk[u] = 1;
    if(ok){
        for(int i=0; i<Q[u].size(); i++){
            if(Q[u][i].k <= top) ans[Q[u][i].id] = stk[Q[u][i].k-1];
        }
    }
    for (int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if (!dfn[v]){
            dfs(v, ok && dfn[u] < low[u]);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    instk[u] = 0;
    --top;
}
int main(){
    scanf("%d %d %d", &n,&m,&q);
    for(int i=1; i<=m; i++){
        int u, v;
        scanf("%d %d", &u,&v);
        G[u].push_back(v);
    }
    for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());
    for(int i=0; i<q; i++){
        int x,y,k;
        scanf("%d %d %d", &x,&y,&k);
        qs[i] = node(i,x,y,k);
    }
    sort(qs, qs+q);
    memset(ans, -1, sizeof(ans));
    for(int i=0; i<q; i++){
        Q[qs[i].y].push_back(qs[i]);
        if(qs[i].x != qs[i+1].x){
            memset(dfn, 0, sizeof(dfn));
            memset(instk, 0, sizeof(stk));
            memset(low, 0, sizeof(low));
            top = dfsclk = 0;
            dfs(qs[i].x, 1);
            for(int j=1; j<=n; j++) Q[j].clear();
        }
    }
    for(int i=0; i<q; i++) printf("%d\n", ans[i]);
    return 0;
}