2019 Wannafly Camp day4

自闭感受

Camp第五天，非常傻逼并快乐的一天????。

上午Claris给我们讲DP，而且从基础开始讲，虽然没有包DP，但是还是学到了不少，非常棒。中午所有人在科技楼下面来了一张大合影 (寒风中瑟瑟发抖) ，最最最最happy的是找各位巨巨们要到了签名，(可惜没要到唐老师的????)

下午训练是目前几场最签到的场了，但是不知为啥周围加我队3队人都傻逼了，明明非常简单片面的东西看的非常复杂，真的是…不想说了，最后吸取教训不管题目怎么样，都有保持一颗平常心态和清醒的头脑。

上题解

A - 夺宝奇兵

很简单的一道题，相邻两组宝藏走法只有两种交叉走，或者平行走（就是一号第一个宝藏走到二号第二个或者一号第一个走到二号第一个），所以for扫一遍去min就可以了

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int a[maxn],b[maxn];
ll dis(int i,int j){
    return abs(a[i]-a[j])+abs(b[i]-b[j]);
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<2*n;i++)scanf("%d%d",&a[i],&b[i]);
    ll ans=dis(2*n-1,2*n-2);
    for(int i=2;i<2*n;i+=2){
        ans+=min(dis(i,i-2)+dis(i+1,i-1),dis(i,i-1)+dis(i+1,i-2));
    }
    printf("%lld\n",ans);
}

C - 最小边覆盖

最小边覆盖，不能有多余的边重复覆盖点。所以如果发现一个点被多余的覆盖了就不是最小点覆盖

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int in[maxn],u[maxn],v[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        in[u[i]]++;
        in[v[i]]++;
    }
    for(int i=1;i<=m;i++){
        if(in[u[i]]>1 && in[v[i]]>1){
            printf("No\n");
            exit(0);
        }
    }
    printf("Yes\n");
    return 0;
}

F - 小小马

因为走法比较特殊，如果当前xy奇偶性相同，下一步则必定不同，所以黑白格子是轮流出现的，这样就可以根据起点和终点的奇偶性判断是否黑格数等于白格数了。同时可以发现只有棋盘大于3 * 4可以从一个点到达棋盘任何点， 3 * 3的棋盘除去中心点其余点都能相互走到，其他棋盘情况就看看从起点走8个方向是否可以走到终点（因为此时棋盘只能走一步）。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,sx,sy,ex,ey;
    cin>>n>>m>>sx>>sy>>ex>>ey;
    if(n>=3&&m>=3){
        if((n==3&&m==3)&&(sx==2&&sy==2)||(ex==2&&sy==2)){
            printf("No\n");
            return 0;
        }
        if((sx%2+sy%2)%2==(ex%2+ey%2)%2)printf("No\n");
        else printf("Yes\n");

    }
    else{
        if((sx+2==ex&&sy-1==ey)||(sx+2==ex&&sy+1==ey)||(sx-2==ex&&sy-1==ey)||(sx-2==ex&&sy+1==ey)||(sx+1==ex&&sy-2==ey)||(sx+1==ex&&sy+2==ey)||(sx-1==ex&&sy+2==ey)||(sx-1==ex&&sy-2==ey))
        printf("Yes\n");
        else printf("No\n");
    }
}

I - 咆咆咆哮

基本思路就是贪心枚举选a的数量num，去选择num个对ans贡献最大a，然后ans取min。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+7;
struct Node{
    int a,b;
}a[maxn];
int num;
bool cmp(Node a,Node b){
    return a.a-num*a.b>b.a-num*b.b;

}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i].a,&a[i].b);
    }
    ll ans=0,anss=0;
    for(num=1;num<=n;num++){
        sort(a,a+n,cmp);
        anss=0;
        for(int i=0;i<num;i++)anss+=a[i].a;
        for(int i=num;i<n;i++)anss+=num*a[i].b;
        ans=max(ans,anss);
    }
    printf("%lld\n",ans);
    return 0;
}