2019 CCPC 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的棋盘除去中心点其余点都能相互走到，其他棋盘情况就看看从起点和终点xy的关系，如果a%2==0&&(a/2)%2==1&&b==1则可以走。

#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{
        int a=max(abs(sy-ey),abs(sx-ex)),b=min(abs(sy-ey),abs(sx-ex));
        if(a%2==0&&(a/2)%2==1&&b==1)
        printf("Yes\n");
        else printf("No\n");
    }
}

G - 置置置换

定义dp[i][j]为 i个数的排列中，最后一个数字为j

当i为偶数的时候，位于山谷，需要前面大于他
dp[i][j]+=dp[i-1][k], j<=k<=i-1
之所以可以这么写是因为，前面并没有出现i这个数字，所以也没有计算dp[i-1][i]，但是有个巧妙的做法
假设把前面所有大于等于j的数+1，就刚好解决这个问题了。

当i为奇数的时候，位于山峰，需要前面小于他
dp[i][j]+=dp[i-1][k], 1<=k<=j-1;
这个很显然直接写是n^3，可以使用前缀和优化

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int MOD=1e9+7;
typedef long long ll;
ll dp[1010][1010];
int sum[maxn];
int main(){
    int n;
    scanf("%d",&n);
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(i&1)//奇数，升序 从1->(j-1)转移
                dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]+MOD)%MOD;//前缀和优化
            else{//偶数，降序 从j -> i转移
                dp[i][j]=(dp[i][j-1]+dp[i-1][i-1]-dp[i-1][j-1]+MOD)%MOD;
            }
        }
    }
    printf("%lld\n",dp[n][n]);
    return 0;
}

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;
}