【博客】WHU校赛2019(网络赛) 解题报告

WHU校赛2019(网络赛) 解题报告

CCNU_你们好强啊我们都是面包手(xzc zx lj)

战况： 比赛时3题，排名57，现在5题了

题目链接: WHU校赛2019 <-戳这里

以下题目按难度顺序递增叙述

B.DrunkHamster
求两点之间距离的平方，签到题

/*
Apr/07/2019 13:49UTC+8    
CCNU_你们好强啊我们都是面包手    
B - DrunkHamster    
GNU C++17    Accepted    30 ms    0 KB
*/
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
void solve(int x,int y)
{
    LL ans = (1ll*x*x+1ll*y*y);
    cout<<ans<<endl;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    LL x,y,z;
    int T,n;
    cin>>T;
    int ca = 0;
    while(T--)
    {
        x = y = 0;
        scanf("%d",&n);
        For(i,0,n-1)
        {
            scanf("%I64d",&z);    
            if(i%4==0) y += z;
            else if(i%4==1) x+=z;
            else if(i%4==2) y-=z;
            else x-=z;
        }    
        printf("Case #%d:",++ca);
        solve(x,y);
    } 
    return 0;
}

E.Egnima
简单模拟，搞个map或者数组对应，比较字符串即可

/*
Apr/07/2019 14:03UTC+8    
CCNU_你们好强啊我们都是面包手    
E - Egnima    
GNU C++17    Accepted    31 ms    2100 KB
*/
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e6+100;
char a[] = "abcdefghijklmnopqrstuvwxyz";
char b[] = "22233344455566677778889999"; 
map<char,char> mp;
char num[maxn],str[maxn]; 
int LenNum;
bool ok()
{
    int len = strlen(str)-1;
    if(len!=LenNum) return false;
    For(i,0,len)
    {
        if(mp[str[i]]!=num[i]) return false;
    }
    return true;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int len = strlen(a)-1;
    For(i,0,len)
    {
        mp[a[i]] = b[i];
    }
    int T,n;
    cin>>T;
    int ca = 0;
    while(T--)
    {
        printf("Case #%d:\n",++ca);
        scanf("%s",num);
        LenNum = strlen(num)-1;
        scanf("%d",&n);
        For(ca,1,n)
        {
            scanf("%s",str);
            if(ok())
            {
                printf("Maybe..\n");
            }
            else
            {
                printf("How could that be possible?\n");
            }
        }
    } 
    return 0;
}

D.Dandelion

卡特兰数 C(m+n-1,n-1)-C(m+n-1,m-1))
预处理阶乘以及阶乘的逆元即可
打比赛的前一天我在牛客上写了道类似的题
感谢lj正确的公式，是我写呲了，忘记%mod+mod%mod，wa了一发，我的锅

/*
Apr/07/2019 14:44 UTC+8    
CCNU_你们好强啊我们都是面包手    
D - Dandelion    
GNU C++17  Accepted 62ms 31300 KB
*/
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 2e6+100;
const int mod = 1e9+7;
LL r[maxn];
LL fac[maxn];
LL fast_pow(LL a,LL b);
void init();
LL C(int n,int m); 
int main()
{
   // freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T,m,n;
    init();
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&m,&n);
        LL ans = ((C(m+n-1,max(m,n)-1)-C(m+n-1,min(m,n)-1))%mod+mod)%mod;
        printf("%I64d\n",abs(ans));
    }

    return 0;
}


LL fast_pow(LL a,LL b)
{
    LL ans = 1;
    while(b)
    {
        if(b&1) ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;    
    }
    return ans; 
} 
void init()
{
    fac[0] = 1;
    r[0] = 1;
    For(i,1,2000000) fac[i] = fac[i-1]*i%mod;
    r[2000000] = fast_pow(fac[2000000],mod-2);
    Rep(i,1999999,1)
        r[i] = r[i+1]*(i+1)%mod;

}
LL C(int n,int m)
{
    if(n<m||m<0) return 0;
    return fac[n]*r[m]%mod*r[n-m]%mod;
}

C.Store

题意：
n种货物
M x y：在第x天买了第y种货物
D x y: 查询在之前比x小的天数中卖过的货物>=y的最小值
1<=y<=n<=1e5 x<=1e9

【博客】WHU校赛2019(网络赛) 解题报告

<font color="purple">WHU校赛2019(网络赛) 解题报告</font>

CCNU_你们好强啊我们都是面包手(xzc zx lj)

以下题目按难度顺序递增叙述

全站热榜