A - Buying A House

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

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

#include
    
     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<
     
      <
     
    

B - Find The Bone

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

题解：模拟即可。

#include
    
     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<
     
      <
     
    

C - Bank Hacking

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

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

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

#include
    
     using namespace std;const int maxn = 3e5+7;vector
     
       E[maxn];int a[maxn],n;multiset
      
       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
      
     
    

D - Police Stations

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

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

#include
    
     using namespace std;const int maxn = 5e5+8;int n,k,d;vector
     
      
        >E[maxn];int vis[maxn],D[maxn];int main(){    memset(D,-1,sizeof(D));    scanf("%d%d%d",&n,&k,&d);    queue
       
         Q;    for(int i=0;i
        
          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<
         
          <
         
        
       
      
     
    

E - Exam Cheating

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

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

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

#include
    
     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