KEYENCE Programming Contest 2019 自闭记

时间：2021-11-07 10:41:20

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int a[];

int main()

{

    //freopen("a.in","r",stdin);

    //freopen("a.out","w",stdout);

    for (int i=;i<;i++) a[i]=read();

    sort(a,a+);

    if (a[]==&&a[]==&&a[]==&&a[]==) cout<<"YES";

    else cout<<"NO";

}

　　B：签到*2。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

char s[];

int n;

int main()

{

    //freopen("a.in","r",stdin);

    //freopen("a.out","w",stdout);

    scanf("%s",s);n=strlen(s);

    char a[]="keyence";

    if (n<) cout<<"NO";

    else

    {

        int x=,y=;

        for (int i=;i<;i++) if (s[i]==a[i]) x++;else break;

        for (int i=n-;i>n-;i--) if (s[i]==a[-(n-i)]) y++;else break;

        if (x+y>=) cout<<"YES";

        else cout<<"NO";

    }

}

　　C：按ai-bi从小到大排序，依次将剩余最多的分配给需求最大的即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,c[N];

ll ans;

struct data

{

    int x,y;

    bool operator <(const data&a) const

    {

        return x-y<a.x-a.y;

    }

}a[N];

int main()

{

    //freopen("a.in","r",stdin);

    //freopen("a.out","w",stdout);

    n=read();

    for (int i=;i<=n;i++) a[i].x=read();

    for (int i=;i<=n;i++) a[i].y=read();

    sort(a+,a+n+);

    for (int i=;i<=n;i++) c[i]=a[i].x;

    for (int i=;i<=n;i++) ans+=a[i].x-a[i].y;

    if (ans<) {cout<<-;return ;}

    int x=n,ans=;

    for (int i=;i<=n;i++)

    {

        if (a[i].x>=a[i].y) break;

        while (a[i].y-a[i].x>a[x].x-a[x].y)

        {

            a[i].x+=a[x].x-a[x].y;

            a[x].x=a[x].y;

            x--;

        }

        a[x].x-=a[i].y-a[i].x,a[i].x=a[i].y;

    }

    for (int i=;i<=n;i++) if (c[i]!=a[i].x) ans++;

    cout<<ans;

}

　　D：按数从大到小考虑，如果其作为某行最大值出现就会多一行被占领，列同理。记录当前被占领的行和列的数量，每次考虑填当前数的方案数，根据其是否在行列最大值中出现，分类讨论一下，给答案乘上这个方案数即可。这个弱智的不行的讨论写了我一年。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1010

#define P 1000000007

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],b[N],posa[N*N],posb[N*N],ans;

int row,line;

int main()

{

    //freopen("a.in","r",stdin);

    //freopen("a.out","w",stdout);

    n=read(),m=read();

    for (int i=;i<=n;i++)

    {

        a[i]=read();

        if (posa[a[i]]) {cout<<;return ;}

        posa[a[i]]=i;

    }

    for (int i=;i<=m;i++)

    {

        b[i]=read();

        if (posb[b[i]]) {cout<<;return ;}

        posb[b[i]]=i;

    }

    row=,line=;ans=;

    for (int i=n*m;i>=;i--)

    {

        if (posa[i]&&posb[i]) {row++,line++;continue;}

        if (!posa[i]&&!posb[i])

        {

            if (row*line-(n*m-i)<=) {cout<<;return ;}

            ans=1ll*ans*(row*line-(n*m-i))%P;

        }

        if (posa[i]) ans=1ll*ans*line%P,row++;

        if (posb[i]) ans=1ll*ans*row%P,line++;

    }

    cout<<ans;

}

　　result：rank 241 rating +19

　　E：分治，每次考虑跨越中点的边，此时可以将边权中的绝对值分配到点权上。找到两边各自点权最小的点i0,、j0，将所有包含这两点之一且跨越中点的边加进图中，最后跑kruskal即可。因为考虑边(i,j)，其边权一定大于(i0,j)和(i,j0)，众所周知环上的最大边不可能出现在MST中。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,d,a[N],fa[N],t;

ll ans;

struct data

{

	int x,y;ll z;

	bool operator <(const data&a) const

	{

		return z<a.z;

	}

}e[N<<5];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

ll calcl(int i)

{

	return a[i]-1ll*i*d;

}

ll calcr(int i)

{

	return a[i]+1ll*i*d;

}

void solve(int l,int r)

{

	if (l==r) return;

	int mid=l+r>>1;

	solve(l,mid);

	solve(mid+1,r);

	int L=l;

	for (int i=l;i<=mid;i++) if (calcl(i)<calcl(L)) L=i;

	int R=r;

	for (int i=mid+1;i<=r;i++) if (calcr(i)<calcr(R)) R=i;

	for (int i=l;i<=mid;i++) e[++t]=(data){i,R,calcl(i)+calcr(R)};

	for (int i=mid+1;i<=r;i++) e[++t]=(data){L,i,calcl(L)+calcr(i)};

}

signed main()

{

	freopen("e.in","r",stdin);

	freopen("e.out","w",stdout);

	n=read(),d=read();

	for (int i=1;i<=n;i++) a[i]=read();

	solve(1,n);

	for (int i=1;i<=n;i++) fa[i]=i;

	sort(e+1,e+t+1);

	for (int i=1;i<=t;i++)

	if (find(e[i].x)!=find(e[i].y))

	{

		fa[find(e[i].x)]=find(e[i].y);

		ans+=e[i].z;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　另一种做法是直接用线段树维护prim的过程。发现早就忘了prim是啥了。

　　F：正常的想法是计算第i次切割的贡献，但似乎很难低于n2。

　　换一种思路，考虑计算以点(i,j)为左下角的矩形的贡献。这个矩形在选择第i行和第j列切割后出现，出现时贡献为1，出现后每切一刀贡献+1。不妨先考虑i,j>0的情况。

　　为了便于考虑，改为计算该矩形贡献的期望。

　　矩形首次出现产生的贡献显然就是i行j列都在前k次切割中出现的概率，这个概率显然为C(k,2)/C(n+m,2)，即一共有C(n+m,2)对，该对在其中等概率出现。

　　对于出现后的贡献，考虑是切x时产生的贡献，这相当于是i,j,x都在前k次中出现，且x在i和j之后出现，那么概率是1/3*C(k,3)/C(n+m,3)。x有n+m-2种取值，所以再乘上n+m-2。

　　i=0或j=0的情况类似。当然求的是期望最后别忘了换成总贡献。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 20000010

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,k,fac[N],inv[N],ans;

int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}

int invC(int n,int m){if (m>n) return 0;return 1ll*inv[n]*fac[m]%P*fac[n-m]%P;}

signed main()

{

	n=read(),m=read(),k=read();

	fac[0]=1;for (int i=1;i<=n+m;i++) fac[i]=1ll*fac[i-1]*i%P;

	inv[0]=inv[1]=1;for (int i=2;i<=n+m;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

	for (int i=2;i<=n+m;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;

	ans=1ll*C(k,2)*invC(n+m,2)%P;

	ans=(ans+1ll*invC(3,1)*C(k,3)%P*invC(n+m,3)%P*(n+m-2))%P;

	ans=1ll*ans*n%P*m%P;

	int ans1=0;

	ans1=1ll*C(k,1)*invC(n+m,1)%P;

	ans1=(ans1+1ll*invC(2,1)*C(k,2)%P*invC(n+m,2)%P*(n+m-1))%P;

	ans1=1ll*ans1*(n+m)%P;

	ans=(ans+ans1+k)%P;

	cout<<1ll*ans*C(n+m,k)%P*fac[k]%P;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

相关文章