A - Buying A House

题意：给你n个房间，妹子住在第m个房间，你有k块钱，你想买一个离妹子最近的房间。其中相邻的房间之间距离为10，a[i]=0表示已经被别人买了。

题解：扫一遍更新答案即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 105;

int mp[maxn];

int n,m,k;

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=n;i++){

        scanf("%d",&mp[i]);

    }

    int Ans = 1000000;

    for(int i=1;i<=n;i++){

        if(mp[i]==0)continue;

        if(mp[i]<=k){

            Ans = min(Ans,abs(m-i)*10);

        }

    }

    cout<<Ans<<endl;

}

B - Find The Bone

题意：有n个杯子，m个杯子下面是洞，然后会交换k次杯子。如果球已经在洞里面了，就不会被交换所影响。

题解：模拟即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+7;

int mp[maxn];

int now = 1;

int n,m,k;

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=m;i++){

        int x;scanf("%d",&x);

        mp[x]=1;

    }

    int flag = 0;

    for(int i=1;i<=k;i++){

        if(mp[now])flag=1;

        int x,y;

        scanf("%d%d",&x,&y);

        if(flag)continue;

        if(now==x)now=y;

        else if(now==y)now=x;

    }

    cout<<now<<endl;

}

C - Bank Hacking

题意：给你一棵树，如果砍掉一个点，会使得周围的点+1，间接相连（中间节点必须活着）的点+2。

现在给你每个点的权值，问你最少需要多少的战斗力，能够砍完这棵树。

题解：如果你砍A，那么与A相连的+1，其他的+2。所以你拿个multiset模拟一下就好了。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5+7;

vector<int> E[maxn];

int a[maxn],n;

multiset<int>S;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        S.insert(a[i]);

    }

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        E[x].push_back(y);

        E[y].push_back(x);

    }

    int Ans = 2e9;

    for(int i=1;i<=n;i++){

        int ans = a[i];

        S.erase(S.find(a[i]));

        for(int j=0;j<E[i].size();j++){

            int v = E[i][j];

            ans = max(ans,a[v]+1);

            S.erase(S.find(a[v]));

        }

        if(S.size())ans = max(ans,*S.rbegin()+2);

        Ans = min(Ans,ans);

        S.insert(a[i]);

        for(int j=0;j<E[i].size();j++){

            int v = E[i][j];

            S.insert(a[v]);

        }

    }

    cout<<Ans<<endl;

}

D - Police Stations

题意：给你一棵树，让你删除最多的边，使得任意一个点，到关键点的距离都小于等于d。

题解：暴力bfs，把关键点都压进去跑最短路，然后把最短路径上的边保留下来就好了……

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5+8;

int n,k,d;

vector<pair<int,int> >E[maxn];

int vis[maxn],D[maxn];

int main(){

    memset(D,-1,sizeof(D));

    scanf("%d%d%d",&n,&k,&d);

    queue<int> Q;

    for(int i=0;i<k;i++){

        int x;

        scanf("%d",&x);

        D[x]=0;

        Q.push(x);

    }

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        E[x].push_back(make_pair(y,i));

        E[y].push_back(make_pair(x,i));

    }

    int ans1 = n-1;

    while(!Q.empty()){

        int now = Q.front();

        Q.pop();

        if(D[now]==d)continue;

        for(int i=0;i<E[now].size();i++){

            pair<int,int> next = E[now][i];

            if(D[next.first]!=-1)continue;

            D[next.first] = D[now] + 1;

            Q.push(next.first);

            vis[next.second]=1;

            ans1--;

        }

    }

    cout<<ans1<<endl;

    for(int i=1;i<n;i++){

        if(!vis[i])cout<<i<<" ";

    }

    cout<<endl;

}

E - Exam Cheating

题意：你在考试，你可以抄左右人的答案，你只能抄p次，每次只能看连续的k道题。现在告诉你左右两个人知道哪些题，请问你最多抄对多少题。

题解：dp[x][re][len][type]表示考虑到x位置，当前剩下re次机会，匹配长度还剩下len，当前抄的人是type。然后用记忆化搜索转移即可。

你要么换个人抄，你要么就一直抄这个人。空间复杂度是1000100050*2，会稍微爆空间，所以用short就好了。

#include<bits/stdc++.h>

using namespace std;

int a[3][1001],s[3][1001];

short dp[1001][1001][51][2];

int n,p,k,r,x;

short solve(int x,int re,int len,int type){

    if(x>n)return 0;

    if(re==0){

        return s[type][x+len-1]-s[type][x-1];

    }

    if(dp[x][re][len][type]!=-1)return dp[x][re][len][type];

    short& ans = dp[x][re][len][type];

    ans = 0;

    int Len = min(k,n-x+1);

    if(len == 0){

        ans = solve(x+1,re,len,type);

        // two choices

        ans = max(ans,solve(x,re-1,Len,0));

        ans = max(ans,solve(x,re-1,Len,1));

    }else{

        // continue

        ans = max(ans,(short)(solve(x+1,re,len-1,type)+(short)a[type][x]));

        // change type

        ans = max(ans,(short)(solve(x+len,re-1,Len-len,1-type)+(short)(s[2][x+len-1]-s[2][x-1])));

    }

    return ans;

}

int main(){

    memset(dp,-1,sizeof(dp));

    scanf("%d%d%d",&n,&p,&k);

    scanf("%d",&r);

    for(int i=0;i<r;i++){

        scanf("%d",&x);

        a[0][x]=1;

    }

    scanf("%d",&r);

    for(int i=0;i<r;i++){

        scanf("%d",&x);

        a[1][x]=1;

    }

    for(int i=1;i<=n;i++){

        for(int j=0;j<2;j++)

            s[j][i]+=a[j][i]+s[j][i-1];

        s[2][i]+=s[2][i-1];

        if(a[0][i]||a[1][i])

            s[2][i]++;

    }

    cout<<solve(1,p,0,0)<<endl;

}