A.最小生成树

思路：贪心。

显然对于一个个结点的无向完全图，要想使其成为一棵树，我们只需选取条边，总贡献是

我们所有结点至少被加一次，所以剩下个结点是要重复加的，显然用点权最小的结点重复即可。所以排个序就解决了。

时间复杂度：

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int a[N];
int main(){
    int n;
    scanf("%d",&n);
    ll ans=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++)
        ans+=a[1]+a[i];
    printf("%lld\n",ans);
    return 0;
}

B.病毒感染

思路：树的重心。

显然根据树的重心性质可知，到所有结点距离和最小的结点是树的重心。

接下用求出无根树的树的重心即可， 需要注意的是树的重心可能不止一个。

时间复杂度：
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int sz[N],mn=inf,n,m;
vector<int>ans,e[N];
void dfs(int u,int fa){
    sz[u]=1;
    int mx=0;
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,n-sz[u]);
    if(mx<mn){
        ans.clear();
        mn=mx;
        ans.push_back(u);
    }
    else if(mx==mn) ans.push_back(u);
} 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        e[u].push_back(v),e[v].push_back(u);
    }
    dfs(1,0);
    for(auto i:ans) printf("%d ",i);
    puts("");
    return 0;
}

C.Shopping

思路：贪心。

显然我们可以知道，如果我们当前有个凳子，说明我们可以使个物品变成半价，所以根据贪心，我们可以取最大的个半价算，然后其他按原价算即可。

时间复杂度：
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
vector<int>e[N],b;
int c[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        b.clear();
        for(int i=1,y;i<=n;i++){
            scanf("%d%d",&c[i],&y);
            if(y==1) b.push_back(c[i]);
        }
        sort(c+1,c+n+1,greater<int>());
        int cnt=min((int)b.size(),m);
        double ans=0;
        for(int i=1;i<=cnt;i++) ans+=(double)c[i]/2.0;
        for(int i=cnt+1;i<=n;i++) ans+=c[i];
        printf("%.1lf\n",ans);
    }
    return 0;
}

D.铺地毯

思路：暴力。

因为题目有后来的地毯覆盖先前的地毯的性质，所以我们可以顺序遍历即可。

时间复杂度：
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
struct node{
    int a,b,g,k;
}A[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&A[i].a,&A[i].b,&A[i].g,&A[i].k);
    }
    int x,y;
    int ans=-1;
    scanf("%d%d",&x,&y);
    for(int i=1;i<=n;i++){
        if(x>=A[i].a&&x<=A[i].a+A[i].g&&y>=A[i].b&&y<=A[i].b+A[i].k)
            ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

E.金币馅饼

思路：。

显然根据题目我们可以知道对于当前状态可以由递推过来。

所以状态转移方程是：

注意初始化，将不能走到的点保持为。

时间复杂度：
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=305+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int dp[N][N];
int a[N][N];
int main(){
    int r,c;
    scanf("%d%d",&r,&c);
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=r;i++)
         for(int j=1;j<=c;j++)
                scanf("%d",&a[i][j]);
    dp[1][1]=a[1][1];
    for(int j=1;j<=c;j++)
       for(int i=1;i<=r;i++){
           for(int k=max(1,i-1);k<=min(r,i+1);k++){
                if(dp[k][j-1]!=-1)
                dp[i][j]=max(dp[i][j],a[i][j]+dp[k][j-1]); 
            //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
        }
       }
    printf("%d\n",dp[r][c]);
    return 0;
}