2018 “百度之星”程序设计大赛 - 初赛（B） 水题做题记录

又是一个手速场，实力太菜，切完水题就开始挂机….

1001 degree
这个题 给了你n个点，m条边，要求可以删除k条边，可以添加无线条边，使得某个点的度数最大
那么首先我们肯定选现有的度数最大的点， 由于题目给的是一个无环的图，相当于是一个森林，所以我们肯定将这个点与其他的树相连，这样能够增加度，当所有的森林都被连成一棵树的时候，就只剩下不与该点直接相连的点了，对这种点，我们需要删除一条边，再重新连上，才能保证不成环，并且度数加一，因此我们很容易发现森林的个数 n-m,令res为原始的度数最大的点的度数
所以答案就是min(n-1, res +n-m-1+k)

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=2e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
//head
int n,m,k;
int t;
int in[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        cl(in);
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            in[a]++;
            in[b]++;
        }
        int res = 0;
        int p=0;
        for(int i=0;i<n;i++)
        {
            if(in[i]>res)
            {
                res=in[i];
                p=i;
            }
        }
        int t= n-m-1;
        int ans= res +t;
        ans = min(n-1,ans+k);
        printf("%d\n",ans);
    }
    return 0;
}

1006
水题，要求线段最短，直接判断每个点到矩形的四条边的垂线距离最短即可，因为横纵坐标都不相等，所以必定不会相交

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=2e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
//head
int n,m,k;
int t;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        int mx,my,n;
        scanf("%d%d%d",&mx,&my,&n);
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int t =min(mx-x,x);
            int q =min(my-y,y);
            ans+=min(t,q);
        }
        printf("%I64d\n",ans);

    }
    return 0;
}

1004
其实这个题过了有运气的成分在，当时没有确切的想好怎么证明上下浮动情况的处理，直接枚举了最小值，然后使得上下增减的值变化为最小值，二分答案即可。
后来看了题解，发现只需要判断加法的次数比减法的次数少或者相等就可以达成

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=3e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod)
{
    ll r = 1;
    for (; k; k >>= 1)
    {
        if (k & 1) r = r * n%p;
        n = n * n%p;
    }
    return r;
}
ll inv(ll a, ll p = mod)
{
    return fpow(a, p - 2, p);
}
//head
int a[maxn];
int n,m,k;
int t;
bool check(ll mid)
{
    ll p =0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]>mid)
        {
            p += (a[i]-mid)/2;

        }
        if(a[i]<mid)
        {
            p+=a[i]-mid;
        }
    }
    if(p<0)return false;
    else return true;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        ll l=0,r=1e9;
        while(l<=r)
        {
            ll mid= l+(r-l)/2;
            if(check(mid))
            {
                l=mid+1;
            }
            else r=mid-1;
        }

        printf("%lld\n",l-1);

    }
    return 0;
}