用户工具

站点工具


2020-2021:teams:namespace:牛客多校第一场

这是本文档旧的修订版!


牛客多校第一场

因为事务繁忙、时间紧迫,这里的题解区仅暂存一下通关代码。

有趣的是,过的几个题都是C语言,暂时还没用到C++的STL。

D

高斯消元板子,含快速幂,没什么内容。

点击以显示 ⇲

点击以隐藏 ⇱

#include<stdio.h>
#include<string.h>
 
#define MOD 998244353
 
long long n,var,equ,pic[256][256],x[256];
long long ans[256];
 
long long abs(long long x)
{
	return (x>0)?x:-x;
}
 
long long QPow(long long bas,long long t)
{
    long long ret=1;
    for(;t;t>>=1,bas=(bas*bas)%MOD)
    {
        if(t&1LL)
        {
            ret=(ret*bas)%MOD;
        }
    }
    return ret;
}
 
void Gauss()
{
    long long i,j,k,col,maxr;
    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        maxr=k;
        for(i=k+1;i<equ;i++)
        {
        	if(abs(pic[i][col])>abs(pic[maxr][col]))
        	{
        		maxr=i;
			}
		}
        if(k!=maxr)
        {
            for(j=col;j<var;j++)
            {
            	long long temp=pic[k][j];
            	pic[k][j]=pic[maxr][j];
            	pic[maxr][j]=temp;
			}
			long long temp=x[k];
            x[k]=x[maxr];
            x[maxr]=temp;
        }
        x[k]*=QPow(pic[k][col],998244351);
        x[k]%=MOD;
        for(j=col+1;j<var;j++)
        {
        	pic[k][j]=(pic[k][j]%MOD*QPow(pic[k][col],998244351))%MOD;
		}
        pic[k][col]=1;
        for(i=0;i<equ;i++)
        {
            if(i!=k)
            {
                x[i]-=x[k]*pic[i][col];
                x[i]%=MOD;
                for(j=col+1;j<var;j++)
                {
                    pic[i][j]-=pic[k][j]*pic[i][col];
                    pic[i][j]%=MOD;
                }
                pic[i][col]=0;
            }
        }
    }
}
 
int main()
{
    while(~scanf("%d",&n))
    {
        var=equ=n;
        int i;
        for(i=0;i<n;i++)
        {
        	int j;
        	for(j=0;j<n;j++)
        	{
        		scanf("%lld",&pic[i][j]);
			}
		}
        for(i=0;i<n;i++)
        {
            scanf("%lld",&x[i]);
            ans[i]=x[i];
        }
        Gauss();
        long long l=0;
        for(i=0;i<n;i++)
        {
            l+=(ans[i]*x[i])%MOD;
            l%=MOD;
        }
        printf("%lld\n",(l>=0?l:l+MOD));
    }
    return 0;
}

F

本题几乎什么都没用到,却因为max的小问题,WA了非常多次。深表惭愧。

点击以显示 ⇲

点击以隐藏 ⇱

#include<stdio.h>
#include<string.h>
 
int main()
{
	int lena,lenb,flag;
	long long max;
	char a[100005],b[100005];
	while(~scanf("%s%s",a,b))
	{
		lena=strlen(a);
		lenb=strlen(b);
		max=2*(lena>lenb?lena:lenb);
		flag=0;
		long long i; 
		for(i=0;i<max;i++)
		{
			if(a[i%lena]<b[i%lenb])
			{
				printf("<\n");
				flag=1;
				break;
			}
			if(a[i%lena]>b[i%lenb])
			{
				printf(">\n");
				flag=1;
				break;
			}
		}
		if(!flag)
		{
			printf("=\n");
		}
	}
	return 0;
}
2020-2021/teams/namespace/牛客多校第一场.1594559207.txt.gz · 最后更改: 2020/07/12 21:06 由 great_designer