CCPC-Wannafly Winter Camp Day4 Div2

夺宝奇兵

题解:
设第i宝藏对应的两个宝藏分别为$A_{i}$和$B_{i}$那么从第i种宝藏取完以后去去第i+1种宝藏的方法一种有两种

第一种:$\large A_{i}$->$\large A_{i+1}$ $ $ $\large B_{i}$->$\large B_{i+1}$

第二种:$\large A_{i}$->$\large B_{i+1}$ $ $ $\large B_{i}$->$\large A_{i+1}$

所以我们只用对所有的点计算出上面两种方案的最小值加起来就可以了

#include <bits/stdc++.h>

const int MAXN = 20000000;

using namespace std;

long long ans;

int n,m;
int x1[MAXN],Y1[MAXN],x2[MAXN],y2[MAXN];

int main()
{
    scanf("%d %d",&n,&m); 
    
    for(int i = 1;i <= n;i++){
        scanf("%d %d",&x1[i],&Y1[i]);
        scanf("%d %d",&x2[i],&y2[i]);
    }
    
    for(int i = 1;i < n;i++){
        ans += (long long)min(
        abs(x1[i]-x1[i+1])+abs(Y1[i]-Y1[i+1])+
        abs(x2[i]-x2[i+1])+abs(y2[i]-y2[i+1]),
        abs(x1[i]-x2[i+1])+abs(Y1[i]-y2[i+1])+
        abs(x2[i]-x1[i+1])+abs(y2[i]-Y1[i+1])
        );
    }
    ans += (abs(x1[n]-x2[n]) + abs(Y1[n]-y2[n]));
    printf("%lld\n",ans);
}

最小边覆盖
题解:留坑,队友写的代码

#include<bits/stdc++.h>

using namespace std;
const int N = 200005;
bool used[N];
int n,m;
bool vis[N];
int ans;
struct Edges{
    int s,t,nxt;
    Edges(){
        s = 0;
        t = 0;
        nxt = 0;
    }
    Edges(int x,int y,int nt):s(x),t(y),nxt(nt){}
}e[400010];
int head[N];
int tot = 1;
int flag[N];
int wt,bk;
int pp[N];
bool fnd(int x){
    for(int i=head[x];i;i = e[i].nxt){
        int v = e[i].t;
        if(used[v] == 0){
            used[v] = 1;
            if(pp[v]==0 || fnd(pp[v])){
                pp[v] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    if(m>=n){
        printf("No\n");
        //cout<<"fuck";
        return 0;
    }
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>n || y>n){
            printf("No\n");
            return 0;
        }
        e[++tot] = Edges(x,y,head[x]);
        head[x] = tot;
        e[++tot] = Edges(y,x,head[y]);
        head[y] = tot;
    }
    memset(flag,-1,sizeof(flag));
    for(int i=1;i<=n;++i){
        queue<int>q;
        if(vis[i])continue;
        if(head[i] == 0){
            printf("No\n");
            return  0;
        }
        q.push(i);
        flag[i] = 0;
        vis[i] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=head[u];i;i = e[i].nxt){
                int v = e[i].t;
                if(!vis[v]){
                    flag[v] = flag[u]^1;
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(flag[i]==0){
            memset(used,0,sizeof(used));
            if(fnd(i))++ans;
        }
    }
    if(ans+m!=n){
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    return 0;
}

欧拉回路

题解:留坑,队友写的代码

#include<bits/stdc++.h>

using namespace std;

int n,m;
int main(){
    scanf("%d%d",&n,&m);
    int ans = (m-1)*n+(n-1)*m;
    if(n == 2){
        ans=(m-1)*n+(n-1)*m+(m-2);
        printf("%d",ans);
        return 0;
    }
    if(m==2){
        ans=(m-1)*n+(n-1)*m+(n-2);
        printf("%d",ans);
        return 0;
    }
    if(n%2==0 && m%2!=0){
        ans+=(n-2)/2+(n-4)/2;
        ans+=(m-3)+4;
    }
    if(n%2==0 && m%2==0){
        ans+=(n-2);
        ans+=(m-2);
    }
    if(n%2!=0 && m%2==0){
        ans+=(m-2)/2+(m-4)/2;
        ans+=(n-3)+4;
    }
    if(n%2!=0 && m%2!=0){
        ans+=(n-3);
        ans+=(m-3);
        ans+=4;
    }
    printf("%d",ans);
    return 0;
}

小小马
题解:如果起点和终点的奇偶性相同显然无解,然后看看代码分类讨论一下

#include <bits/stdc++.h>

using namespace std;

int n,m;

int sx,sy,ex,ey;

int main()
{

    
    scanf("%d %d",&n,&m);
    scanf("%d %d",&sx,&sy);
    scanf("%d %d",&ex,&ey);
    
    if((ex+ey)%2 == (sx+sy)%2) {
        printf("No\n");
    }
    else {
        if(n > 2 && m > 2) {
            if( n==3 && m==3 ){
                if( ( ex==2 && ey==2 ) || ( sx==2 && ey==2 ) ) printf("No\n");
                else printf("Yes\n");
            }
            else printf("Yes\n");    
        }
        else{

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

    return 0;
}

置置置换

小声的说考试的时候我是打开OEIS,然后得知这个东西叫然后根据wiki实现了wiki中间的代码,不过在我打代码的时候队友也把那个公式推出来了

#include <bits/stdc++.h>

const long long MOD = 1e9+7,MAXN = 10000;

using namespace std;

long long ans;
long long A[2*MAXN+5],inv[2*MAXN+5],fac[2*MAXN+5],fnv[2*MAXN+5];

long long pow_mod(long long a,long long n){
    long long ans = 1;
    while (n) {
        if (n&1) ans = ans * a % MOD;
          a = a * a % MOD;
          n >>= 1;
     }
     return ans;
}

inline void pre(){
    inv[1] = 1;
    fac[0] = fnv[0] = 1;
    for(int i = 2;i <= MAXN;i++) inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i = 1;i <= MAXN;i++) {
        fac[i] = fac[i-1] * i % MOD;
        fnv[i] = fnv[i-1] * inv[i] % MOD;
    }
}

inline long long comb(long long a,long long b){
    return ((fac[a]*fnv[b])%MOD*fnv[a-b])%MOD;
}

int main()
{    
    pre();
    int n;
    
    scanf("%d",&n);
    inv[1] = fac[0] = fnv[0] = 1;

       A[0] = 1;A[1] = 1;A[2] = 1;
    
    for(int i = 3;i <= n;i++){
         for(int j = 0;j < i;j++)
        {
            A[i] += ((comb(i-1,j)*A[j])%MOD*A[i-1-j])%MOD;
            A[i] %= MOD;
        }
        A[i] *= inv[2];
        A[i] %= MOD;
        A[i] += MOD;
        A[i] %= MOD;
    }
    A[n] %= MOD;
    A[n] += MOD;
    A[n] %= MOD;
    printf("%lld\n",A[n]);
    return 0;
}
Last modification:January 29th, 2019 at 11:35 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment