A最小生成树

题意：有n个点的带权无向图，给出每个结点权值 , 该图为无向完全图，边值为点权值之和，问边权和最小的生成树为多少。

解法：贪心思想，因为是一棵树所以每个点至少被一条边连，让权值最小的点与其他所有点连边所构成的树权值和最小。
注意边界条件结点数为1。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 80112002
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e7+9;
const int maxn = 1e5+9;
int a[maxn];
void solve(){
    int n , sum = 0;
    cin >> n ;
    int mi = INF ;
    rep(i , 1 , n){
        cin >> a[i];
        mi = min(mi , a[i]);
        sum += a[i];
    }
    if(n == 1){
        cout << 0 << endl;
    }else{
        cout << sum + mi * (n-2) << endl;
    }
}

signed main()
{
    //int _ ;cin>>_;while(_--)
        solve();
}

B病毒感染

题意：有给出n个点m条边的图，根据题目说明图不包含大于等于3的环，又是连通图所以可知该图去掉重边即为一棵树。找出城市，该城市到所有其他城市的距离和最短。可以知道该点就是树的重心。
重心：以该点为根的最大子树结点个数最少。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 1000000009
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 4e2+9;
const int maxn = 5e4+9;
vector<int>g[maxn];
map<int,map<int,int>>vis;
int minSize , bal;
int sz[maxn];
vector<int>v;
int n , m ;
void dfs(int u , int pre){
    sz[u] = 1 ;
    int maxSub = 0 ;
    for(int v : g[u]){
        if(v == pre) continue;
        dfs(v , u);
        sz[u] += sz[v];
        maxSub = max(maxSub , sz[v]);
    }
    maxSub = max(maxSub , n-sz[u]);
    if(minSize > maxSub){
        minSize = maxSub ;
        v.clear();
        v.pb(u);
    }else if(minSize == maxSub){
        v.pb(u);
    }
}

void solve(){
    scanf("%lld%lld" , &n , &m);
    rep(i , 1 , m){
        int u , v ;
        scanf("%lld%lld" , &u , &v);
        if(!vis[u][v]){
            g[u].pb(v);
            g[v].pb(u);
        }
        vis[u][v] = 1 ;
        vis[v][u] = 1 ;
    }
    minSize = INF;
    dfs(1 , 0);
    for(auto i : v){
        cout << i << " " ;
    }
    cout << endl;
}
signed main()
{
    solve();
}

C:Shopping

题意：n件物品，表示物品价格,表示物品是否为凳子，m个购物车，如果购物车有至少一个凳子则该购物车最贵物品半价。
解法：统计凳子数，购物车数与凳子数的最小值即为可半价商品数，让最贵商品半价。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 80112002
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e7+9;
const int maxn = 1e3+9;
int a[maxn];

bool cmp(int a , int b){
    return a > b ;
}
void solve(){
    int n , m  , ans = 0;
    cin >> n >> m ;
    rep(i , 1 , n){
        int x;
        cin >> a[i] >> x ;
        if(x)ans++;
    }
    double sum = 0;
    sort(a+1 , a+1+n , cmp);
    int k = min(ans , m);
    rep(i , 1 , k){
        sum += 1.0*a[i]/2;
    }
    rep(i , k+1 , n){
        sum += a[i];
    }
    printf("%.1lf\n" , sum);
}

signed main()
{
    int _ ;cin>>_;while(_--)
        solve();
}

D铺地毯

题意：n张地毯依次铺设在第一象限坐标轴上，给出每张地毯坐下坐标(a,b)及地毯在x轴和y轴方向的长度。问（x,y）点最上层的地毯标号，若没有地毯则输出-1.
解法：倒叙枚举判断（x,y）是否在第i块地毯区域。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define mod 80112002
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define int ll
using namespace std;
const int N = 1e7+9;
const int maxn = 1e4+9;
struct node{
    int a , b , x , y ;
}a[maxn];
void solve(){
    int n ;
    cin >> n ;
    rep(i , 1,  n){
        cin >> a[i].a >> a[i].b >> a[i].x >> a[i].y ;
    }
    int x , y ;
    cin >> x >> y ;
    red(i , n , 1){
        if(x >= a[i].a && a[i].a + a[i].x >= x && y >= a[i].b && a[i].b+a[i].y >= y){
            cout << i << endl;
            return ;
        }
    }
}

signed main()
{
    //int _ ;cin>>_;while(_--)
        solve();
}

E金币馅饼

题意：给出n*m方格，每个方格有金币Ni ， 从（1，1）走到到（n，m）所能捡到的最多金币为多少？
解法：dp[i][j]表示从（1,1）走到(i,j)所能捡到的最大金币数量。

#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef  long long ll ;
#define int ll
#define mod 80112002
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
const int N = 1e7+9;
const int maxn = 1e3+9;
int a[maxn][maxn];
int dp[maxn][maxn];
void solve(){
    int n , m ;
    cin >> n >> m ;
    rep(i , 1 , n){
        rep(j , 1 , m){
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];
    rep(j , 2 , m){
        rep(i , 1 , n){
            if(dp[i-1][j-1]){
                dp[i][j] = max(dp[i][j] , dp[i-1][j-1] + a[i][j]);
            }
            if(dp[i][j-1]){
                dp[i][j] = max(dp[i][j] , dp[i][j-1] + a[i][j]);
            }
            if(dp[i+1][j-1]){
                dp[i][j] = max(dp[i][j] , dp[i+1][j-1]+a[i][j]);
            }
        }
    }
    cout << dp[n][m] << endl;
}

signed main()
{
    //int _ ;cin>>_;while(_--)
        solve();
}