ccpc 2018 final

2020-09-15

字数统计: 1.9k字 | 阅读时长≈ 9分

记一次训练被爆锤

G - Pastoral Life in Stardew Valley

题意：

给你一个$N*M$的矩阵，要你从中选取子矩阵种菜和放置稻草人，且至少要放一个稻草人，稻草人必须被菜包围，

即稻草人不能放置在边缘，问一共有多少种放置的方式（每个子矩阵的放置方式相加的总和），答案对1e9+7取模。

题解：

我们可以从行列下手，我们先看行，题目的意思就相当于要找两个矩形，且大的必须包围小的，如图，

其中$A,B$表示大的边界，$C,D$表示小的边界，那么总共有$C_{n}^{4} $种选法，而有特殊的选法，就是小的只占一格，如图，

那么共有$C_{n}^{3}$种选法，总共有$C_{n}^{4}+C_{n}^{3} $种选法，则列有$C_{m}^{4}+C_{m}^{3} $种，且行列互相约束，满足分步乘法则总共有$(C_{n}^{4}+C_{n}^{3} )*(C_{m}^{4}+C_{m}^{3} )$种。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;
typedef long long ll;
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2,mod); }

ll C(int n,int m){
  if(n==m)return 1;
  if(n<m)return 0;
  ll ans = 1;
  _for(i,n-m+1,n+1)ans*=i,ans%=MOD;
  ll x=1;
  _for(i,1,m+1)x*=i;
  return ans*inv(x)%MOD;
}
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    int n,m;cin>>n>>m;
    cout<<"Case "<<_<<": ";
    if(n<3||m<3)cout<<0;
    else cout<<(C(n,3)+C(n,4))*(C(m,3)+C(m,4))%MOD;
    cout<<endl;
  }
  return 0;
}

I. Cockroaches

题意：

现在田野里有$n$条虫，给出他们的坐标，并且一个格子内不会出现多条虫，现有一种杀虫剂，能把投放的$(x,y)$的同一行列全部杀完，问最多能杀多少的虫，且有多少种投放方式。

题解：

这里可以统计每一行每一列的虫的个数，然后看行最多和列最多有多少，因为$x,y$的范围是$1e9$则我们可以用$map$或者离散化储存一下个数，然后遍历统计一下即可，细节如下。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SE second
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'
using namespace std;
typedef long long ll;

struct xy{
  int x,y;
}a[100005];
map<int,int>mpx,mpy;
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    ll n;cin>>n;
    mpx.clear(),mpy.clear();
    int mx=0,my=0;
    _for(i,0,n){
      cin>>a[i].x>>a[i].y;
      ++mpx[a[i].x],++mpy[a[i].y];
      mx=max(mx,mpx[a[i].x]);
      my=max(my,mpy[a[i].y]);
    }
    cout<<"Case "<<_<<": ";
    //特判一下在全部在同一行同一列和对角线分布的
    if(mpx.size()==1||mpy.size()==1){
      cout<<n<<" 1\n";
      continue;
    }
    if(mx==1&&my==1){
      cout<<"2 "<<n*(n-1)/2<<endl;
      continue;
    }
    int cx1=0,cx2=0;
    _sfor(it,mpx){
      if(it.SE==mx)cx1++;
      else if(it.SE==mx-1)cx2++;
    }
    int cy1=0,cy2=0;
    _sfor(it,mpy){
      if(it.SE==my)cy1++;
      else if(it.SE==my-1)cy2++;
    }
    ll a1=1ll*cx1*cy1;
    ll a2=1ll*cx1*cy2+1ll*cx2*cy1;
    int ma1=mx+my,ma2=mx+my-1;
    //这里是因为，有虫的地方，会多统计一个，要减去
    _for(i,0,n){
      if(mpx[a[i].x]+mpy[a[i].y]==ma1)--a1,++a2;
      else if(mpx[a[i].x]+mpy[a[i].y]==ma2)--a2;
    }
    if(a1)cout<<ma1<<' '<<a1<<endl;
    else cout<<ma2<<' '<<a2<<endl;
  }
  return 0;
}

K - Mr. Panda and Kakin

题意：

给出一个范围在$[1e5,1e9]$的整数$x$，令小于$x$的最大的素数为$p$，次大的为$q$，令$n=p*q$，设$c=flag^{2^{30}+3}\mod n$，求$flag$。

题解：

令$t=2^{30}+3$，易知$t$是素数，由拓展欧拉定理我们可以得出$flag^t\equiv flag^{t\mod \phi(n)}(\mod n)$，而欧拉定理又可得$\phi(n)=(p-1)*(q-1)$，而$t$关于$\phi(n)$的逆元是$t^{-1}$可用$exgcd$求出，则有$flag\equiv flag^{tt^{-1}}\equiv c^{t^{-1}}(\mod n)$。

ps:

由于我们在进行快速幂乘法的时候，可能会出现两个数都超出逼近$ll$的最大范围，会溢出，则我们由以下式子，则不会溢出。

$a*b\%p=a*b-\lfloor \frac{ab}p\rfloor\%p$

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _rfor(i,a,b) for(ll i = (a);i>(b);--i)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
ll mul(ll a,ll b,ll mod){return ((a*b-ll((ld)a/mod*b)*mod)%mod+mod)%mod;}  
ll qpow(ll x, ll y, ll MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = mul(ans,x,MOD); x = mul(x,x,MOD); }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}


signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    ll n,c;cin>>n>>c;
    ll p,q;
    _rfor(i,sqrt(n),0){
      if(n%i==0){
        p=i,q=n/i;
        break;
      }
    }
    ll t=(p-1)*(q-1),x,y,a=(1ll<<30)+3;
    exgcd(a,t,x,y);
    x=(x+t)%t;
    cout<<"Case "<<_<<": "<<qpow(c,x,n)<<endl;
  }
  return 0;
}

L - Ultra Weak Goldbach’s Conjecture

题意：

给出一个特别弱化版的哥德巴赫猜想，即任一一个大于$11$的数都可以拆成$6$个质数相加，先给出询问数字$x$，是否可以把$x$拆成$6$个质数，若可以则输出，否则输出IMPOSSIBLE。

题解：

已知歌德巴赫猜想为任一一个大于$2$的偶数都可以拆成2个质数相加，则我们可以想到，如果$x$是奇数的话，就先输出$2\ 2\ 2 \ 3$，然后数就变成了$x-9$为偶数，而我们又知道在$long\ long$的范围内，相邻的质数之间不超过300个数，那直接暴力枚举即可；如果$x$是偶数的话，先输出$2\ 2\ 2\ 2$然后枚举即可。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;
typedef long long ll;

int check(ll x){
  for(ll i=2;i*i<=x;++i){
    if(x%i==0)return 0;
  }
  return 1;
}
signed main() {
  FIO;
  int T;cin>>T;
  _for(_,1,T+1){
    ll n;cin>>n;
    cout<<"Case "<<_<<": ";
    if(n<=11)cout<<"IMPOSSIBLE";
    else if(n&1){
      n-=9;
      cout<<"2 2 2 3 ";
      for(ll i=2;;++i){
        if(check(i)&&check(n-i)){
          cout<<i<<' '<<n-i;
          break;
        }
      }
    }else{
      n-=8;
      cout<<"2 2 2 2 ";
      for(ll i=2;;++i){
        if(check(i)&&check(n-i)){
          cout<<i<<' '<<n-i;
          break;
        }
      }
    }
    cout<<endl;
  }
  return 0;
}

本文作者： baddog
本文链接： https://katoli.github.io/2020/09/15/ccpc-2018-final/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！