Codeforces Round #408 (Div. 2) 思维，模拟，DP, 多点BFS

A：水题，看懂题意然后模拟一下即可。复杂度O(n)

///CF 796A

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int a[110];
int main(){
    scanf("%d%d%d", &n,&m,&k);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    int ans = 1e9;
    for(int i=m-1; i>=1; i--){
        if(a[i]!=0&&a[i]<=k){
            ans = min(ans, (m-i)*10);
        }
    }
    for(int i=m+1; i<=n; i++){
        if(a[i]!=0&&a[i]<=k){
            ans = min(ans, (i-m)*10);
        }
    }
    cout<<ans<<endl;

}

B,同模拟水题，复杂度O(k)

///CF 796B

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n, m, k;
int vis[maxn];

int main(){
    scanf("%d%d%d", &n,&m,&k);
    for(int i=1; i<=m; i++){
        int x; scanf("%d", &x);
        vis[x]=1;
    }
    int curpos = 1;
    int ans = -1;
    int flag = 0;
    while(k--){
        int x, y;
        scanf("%d%d", &x, &y);
        if(flag) continue;
        if(x==curpos&&vis[x]){
            flag=1;
            ans=x;
        }
        else if(y==curpos&&vis[y]){
            flag=1;
            ans=y;
        }
        else if(x==curpos){
            if(vis[y]){
                ans = y;
                flag=1;
            }
            else{
                curpos=y;
            }
        }
        else if(y==curpos){
            if(vis[x]){
                ans = x;
                flag = 1;
            }
            else{
                curpos = x;
            }
        }
    }
    if(ans==-1) ans = curpos;
    cout<<ans<<endl;
    return 0;
}

C：题意就是给了一颗树，每个节点有一个能量值，现在一个人有个初始能量值，现在他选择一个点去破坏，

但是破坏之后这个点的相邻点和相邻点的相邻点的能量值会加1，破坏一个点的条件是这个人当前的能量值

不小于这个点的能量值。问破坏图中所有节点具有的初始能量的最小值。

解法：思维，思考一下发现如果我们选择最大的好像很能逼近正确答案，那么一定是最大吗？并不是我们可以

简单举出一些例子发现答案可以是最大值加1或者最大值加2，但是好像没有其他答案了？的确，我们深入思

考，这是一颗树，考虑极限情况就是1条链并且所有值都等于最大值时，我们用最大值加2就可以了。那么

什么情况是最大值，什么情况是最大值加一，什么情况是最大值加二呢？

最大值：只有一个点的值等于mx,相邻点包含了全部mx-1的点

最大值加一：存在一个点，它和它相邻的点，包含了全部的权值为最大值的点。

最大值加二：其他。

并且只有一个点为mx并且不满足条件1的时候，答案是mx+1。

///CF 469C

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
map <int, int> mp1;
int n, a[maxn];
vector<int>G[maxn];
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int mx = -2e9;
    for(int i=1; i<=n; i++) mx = max(a[i], mx);
    for(int i=1; i<=n; i++)
    {
        mp1[a[i]]++;
    }
    int ans = mx+2;
    if(mp1[mx]==1)
    {
        int pos;
        for(int i=1; i<=n; i++) if(a[i]==mx)
        {
            pos=i;
            break;
        }
        int cnt = 0;
        for(int i=0; i<G[pos].size(); i++)
        {
            int v = G[pos][i];
            if(a[v]==mx-1) cnt++;
        }
        if(cnt==mp1[mx-1]) ans = mx;
        else ans=mx+1;
        printf("%d\n", ans);
        return 0;
    }
    else for(int i=1; i<=n; i++){
        int cnt=0;
        if(a[i]==mx) cnt++;
        for(int j=0; j<G[i].size(); j++)
        {
            int v = G[i][j];
            if(a[v]==mx) cnt++;
        }
        if(cnt==mp1[mx])
        {
            ans = mx+1;
            printf("%d\n", ans);
            return 0;
        }
    }
    printf("%d\n", ans);
}

D：

题意：n个城市，某些城市有警察局，共k个。定义了一个规则，就是任意一个点离它最近的警察局的距离都要

不超过d。边权是1，现在问在满足这个规则的条件下最多删除多少条边？

解法：开始想的是，删除的边肯定和k个点能延伸d步能覆盖到的边的覆盖，然后就不知道怎么做了。然后观摩

了一发我队友的代码，偷取了一个思路。。。把k个起点放到队列里面，进行多起点BFS。维护两个标记，一

个标记边，一个标记点，如果当前边没有被标记但是当前点的下一个点被标记了，则说明了当前边是可以删除

的，理由很简单，因为BFS是按照距离从小到大跑的，如果当前边没有被标记但是当前点的下一个点被标记

了，也就说明了dis[u]<=d&&dis[v]<=d。并且我们这道题根本不需要关心d,因为题目说了初始状态是合法的

那么BFS跑最短路怎么都不会跑到大于d的距离。

///CF 796D

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
///u&&v连通 dis[u]<=d&&dis[v]<=d
///本质上变成了本题实际和d无关,因为初始就是合法状态

struct node{
    int v, id;
};
int n, m, d;
vector <node> G[maxn];
int vis1[maxn], vis2[maxn];
queue <int> que;
int bfs()
{
    int ans = 0;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=0; i<G[u].size(); i++){
            node nxt = G[u][i];
            if(vis1[nxt.id]) continue;
            if(vis2[nxt.v]){
                vis1[nxt.id]=2;
                ans++;
                continue;
            }
            vis2[nxt.v]=1;
            vis1[nxt.id]=1;
            que.push(nxt.v);
        }
    }
    printf("%d\n", ans);
}
int main()
{
    scanf("%d%d%d", &n,&m,&d);
    for(int i=0; i<m; i++){
        int x;
        scanf("%d", &x);
        vis2[x]=1;
        que.push(x);
    }
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d%d", &u,&v);
        G[u].push_back(node{v, i});
        G[v].push_back(node{u, i});
    }
    int ans = bfs();
    //cout<<ans<<endl;
    for(int i=1; i<n; i++){
        if(vis1[i]==2) printf("%d ", i);
    }
    cout<<endl;
}

题意：有一个人要考试作弊，她可以偷看左右两个人的试卷。但是她只能偷看p次，每次只能看一个人试卷上

的连续的k个题目。总共有n道题目，给你左右两个人能做对的题目，求出她最大能做对几道题。

一个样例：她共有2次偷看的机会，每次只能看3道题目，第一次偷看person1的（1，2，3），第二次偷看

person2的(4, 5, 6),可以作对的题目为(1, 3, 5, 6)共4道

解法：DP

dp[i][j][x][y]表示考虑完前i个问题，当前用掉了j次机会，第一个人还能看x道题，第二个人还能看j道题的最优值。

这里的复杂度O(p*k*k)，但是当p>(2*n)/k时可以全选，那么直接全选就行了。那么剩下的我们就跑个DP就

好了。复杂度是O(n*n*k)

那么dp的转移这里用被动转移好写一点，并且注意到数组直接是开不下的，观察转移发现可以滚动一下，这

题就完了。转移看代码，不难。

///CF 769E

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

const int maxn = 1002;
int n, p, k, a[maxn], b[maxn], ans;
int n1, n2, dp[2][maxn][52][52];
///dp[i][j][x][y]表示考虑完前i个问题，当前用掉了j次机会，第一个人还能看x道题，第二个人还能看j道题的最优值
void update(int &x, int y) {if(y>x) x=y;}
int now=0,pre=1;

int main()
{
    scanf("%d%d%d", &n,&p,&k);
    scanf("%d",&n1);
    for(int i=1; i<=n1; i++){
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    scanf("%d", &n2);
    for(int i=1; i<=n2; i++){
        int x;
        scanf("%d", &x);
        b[x]++;
    }
    int lim=n/p;
    if(n%p!=0) lim++;
    lim*=2;
    if(k>=lim){
        for(int i=1; i<=n; i++){
            ans += a[i]|b[i];
        }
        printf("%d\n", ans);
        return 0;
    }
    memset(dp, 0xef, sizeof(dp));
    dp[0][0][0][0]=0;
    for(int i=1; i<=n; i++){
        swap(now,pre);
        memset(dp[now], 0xef, sizeof(dp[now]));
        for(int j=0; j<=p; j++){
            for(int ii=0; ii<=k; ii++){
                for(int jj=0; jj<=k; jj++){
                    if(!ii&&!jj){
                        update(dp[now][j][0][0], dp[pre][j][0][0]);
                        update(dp[now][j+1][k-1][0], dp[pre][j][0][0]+a[i]);
                        update(dp[now][j+1][0][k-1], dp[pre][j][0][0]+b[i]);
                        update(dp[now][j+2][k-1][k-1], dp[pre][j][0][0]+(a[i]|b[i]));
                    }
                    else if(!ii){
                        update(dp[now][j][0][jj-1], dp[pre][j][0][jj]+b[i]);
                        update(dp[now][j+1][k-1][jj-1], dp[pre][j][0][jj]+a[i]);
                        update(dp[now][j+2][k-1][k-1], dp[pre][j][0][jj]+(a[i]|b[i]));
                    }
                    else if(!jj){
                        update(dp[now][j][ii-1][0], dp[pre][j][ii][0]+a[i]);
                        update(dp[now][j+1][ii-1][k-1], dp[pre][j][ii][0]+b[i]);
                        update(dp[now][j+2][k-1][k-1], dp[pre][j][ii][0]+(a[i]|b[i]));
                    }
                    else update(dp[now][j][ii-1][jj-1], dp[pre][j][ii][jj]+(a[i]|b[i]));
                }
            }
        }
    }
    for(int l=0; l<=p; l++){
        for(int i=0; i<=k; i++){
            for(int j=0; j<=k; j++){
                ans = max(ans, dp[now][l][i][j]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}