GuOJ Round #1 标程与题解

wjyyy
队爷
2019-06-15 18:00:49

题解

std:

A

#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[2100000],*p1=buf,*p2=buf;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
int a[200100],b[200100];
int main()
{
    int n=read();
    int m=read(),u,v,w,x;
    long long ans=0,sum=0;
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        sum+=a[i];
    }
    for(int i=1;i<m;++i)
    {
        for(int j=1;j<=n;++j)
            b[j]=a[j];
        u=read();
        for(int j=1;j<=u;++j)
        {
            v=read();
            w=read();
            std::sort(b+v,b+w+1);
            for(int k=v;k<=w;++k)
            {
                x=read();
                ans=(ans+(long long)b[k]*x)%998244353;
            }
        }
    }
    printf("%lld %lld\n",sum,ans);
    return 0;
}

B

#include<cstdio>
#include<cstring>
int main()
{
    int n,l,r,d;
    scanf("%d%d%d%d",&n,&l,&r,&d);
    if(d<n-r)
        printf("%.8lf\n",1.0*d/n);
    else if(d>=n-r&&d<=n-l)
        printf("%.8lf\n",((2.0*n-l-r)*(r-l)-(n-d-l)*(n-d-l))/(2.0*n*(r-l)));
    else
        printf("%.8lf\n",(2.0*n-l-r)/(2*n));
    return 0;
}

C

递归

#include<cstdio>
#include<cstring>
int x=0;
void func(int i)
{
    if(i==-1)
        return;
    func(i-1);
    x^=(1<<i);
    printf("%d ",x);
    func(i-1);
}
int main()
{
    int n;
    scanf("%d",&n);
    func(n-1);
    puts("0");
    return 0;
}

lowbit

#include<cstdio>
#define lowbit(x) (x&(-x))
int main()
{
    int n,x=0;
    scanf("%d",&n);
    for(int i=1;i<(1<<n);++i)
    {
        x^=lowbit(i);
        printf("%d ",x);
    }
    puts("0");
    return 0;
}

D

#include <cstdio>
#include <cctype>
#include <cstring>
#define ll long long
const int SIZE = 1 << 21;
char ibuf[SIZE], *iS, *iT;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
//#define gc() getchar()
template <class T>
void read(T &x) {
    x = 0;
    char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
}
const int mod = 998244353;
#define mul(a, b) (1ll * (a) * (b) % mod)
inline void add(int &a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
}
ll n, k;
int m, x, y, p;
struct Matrix {
    int dx[8][8];
    Matrix() { memset(dx, 0, sizeof dx); }
    Matrix friend operator*(Matrix a, Matrix b) {
        Matrix c;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < m; k++) add(c.dx[i][j], mul(a.dx[i][k], b.dx[k][j]));
        return c;
    }
    Matrix friend operator+(Matrix a, Matrix b) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++) add(a.dx[i][j], b.dx[i][j]);
        return a;
    }
} I, pre, toki, ans, S, T, O, Tp, tp;
Matrix qp(Matrix d, ll k) {
    Matrix f = I;
    while (k) {
        if (k & 1)
            f = f * d;
        d = d * d;
        k >>= 1;
    }
    return f;
}
Matrix sol(ll r) {
    if (r == 0)
        return O;
    if (r == 1)
        return tp;
    Matrix ret = sol(r >> 1);
    Matrix saki = qp(T, 1ll * p * (r >> 1)) * (ret + ((r & 1) ? qp(T, 1ll * p * (r + 1 >> 1)) : O));
    return ret + saki;
}
Matrix cal(ll r) {
    if (r == k)
        return toki;
    return toki + Tp;
}
void work(int t) {
    ll r = (n - t) / p;
    ans = pre * (I + cal(r));
    printf("%d\n", ans.dx[0][y - 1]);
}
int main() {
    // puts("233");
    read(n), read(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) read(T.dx[i][j]);
        I.dx[i][i] = 1;
    }
    read(p), read(x), read(y);
    S.dx[0][x - 1] = 1;
    Tp = qp(T, n / p * p), tp = qp(T, p);
    pre = S;
    if (n < p) {
        for (int t = 0; t < p; t++) {
            printf("%d\n", pre.dx[0][y - 1]);
            pre = pre * T;
        }
        return 0;
    }
    toki = sol(k = (n / p - 1));
    for (int t = 0; t < p; t++) {
        work(t);
        pre = pre * T;
    }
}

E

提交答案文件下载地址:std

F

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
#define gc() getchar()
template <class T>
void read(T &x)
{
	x=0;char c=gc();
	while(!isdigit(c)) c=gc();
	while(isdigit(c)) x=x*10+c-'0',c=gc();
}
const int N=51;
const int mod=998244353;
inline void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
#define mul(x,y) (1ll*(x)*(y)%mod)
int n,ans;
int dp[2][N][N<<1],g[2][N][N],fl[2][N][N],fr[2][N][N],toki[3][N],yuu[3][N],a[2][N];
void mov(int val,int l,int pl,int r,int pr)
{
	if(!dp[pl][l][val]) return;
	int tv,ov;
	if(pl==pr)
	{
		for(int i=l+1;i<=r;i++)
		{
			tv=val;//left
			if(g[pl][l][r]) tv=(l<<1)-tv;
			tv+=fr[pl][l+1][r];
			ov=fr[!pl][l+1][i]+fl[!pl][i][r];
			if(toki[2][i]^g[pl][i][r]) ov=r-l-ov;
			add(dp[pl][r][tv+ov],dp[pl][l][val]);
		}
	}
	else
	{
		for(int i=l+1;i<=r;i++)
		{
			tv=val;
			if(g[pl][l][i]^toki[2][i]^g[pr][i][r]) tv=(l<<1)-tv;
			tv+=fr[pr][i][r]+((toki[2][i]^g[pr][i][r])?i-l-fr[pl][l+1][i]:fr[pl][l+1][i]);
			ov=toki[2][i]?r-i-fl[pl][i][r]:fl[pl][i][r];
			ov+=fr[pr][l+1][i];
			if(g[pr][i][r]) ov=r-l-1-ov;
			add(dp[pr][r][tv+ov],dp[pl][l][val]);
		}
	}
}
int work()
{
	for(int j=0;j<2;j++)
	{
		for(int l=1;l<=n;l++)
		{
			int bit[2]={1,0};
			for(int r=l+1;r<=n;r++)
			{
				if(toki[j][r-1]) std::swap(bit[0],bit[1]);
				++bit[0];
				fr[j][l][r]=bit[1];
				g[j][l][r]=g[j][l][r-1]^toki[j][r-1];
			}
		}
		for(int r=n;r;r--)
		{
			int bit[2]={1,0};
			for(int l=r-1;l;l--)
			{
				if(toki[j][l]) std::swap(bit[0],bit[1]);
				++bit[0];
				fl[j][l][r]=bit[1];
			}
		}
	}
	memset(dp,0,sizeof dp);
	dp[0][0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<=i<<1;j++)
			for(int k=i+1;k<=n;k++)
			{
				mov(j,i,0,k,0),mov(j,i,0,k,1);
				mov(j,i,1,k,0),mov(j,i,1,k,1);
			}
	int ret=0;
	for(int j=0;j<=n<<1;j++)
		add(ret,mul(dp[0][n][j],mul(j,n*2-j)));
	return ret;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[0][i]);
	for(int i=1;i<=n;i++) read(a[1][i]);
	for(int i=1;i<n;i++)
    {
        yuu[0][i]=a[0][i]+a[0][i+1];
        yuu[1][i]=a[1][i]+a[1][i+1];
    }
    for(int i=1;i<=n;i++) yuu[2][i]=a[0][i]+a[1][i];
	for(int j=0;j<=30;j++)
	{
		for(int i=1;i<n;i++)
        {
            toki[0][i]=yuu[0][i]>>j&1;
            toki[1][i]=yuu[1][i]>>j&1;
        }
		for(int i=1;i<=n;i++) toki[2][i]=yuu[2][i]>>j&1;
		add(ans,mul(work(),1<<j));
	}
	printf("%d\n",ans);
	return 0;
}