NOIP2018模拟9.15總結

就是這樣

分數100+80+60=240

RANK1

暴力真是爽

T1題意

有N個點，M條邊，K個特殊點，邊權為1

求每個點到離他最遠的特殊點的最短距離

NK<=10000000

顯然暴力

T1代碼

#include<bits/stdc++.h>
#define N 300001
using namespace std;
int i,j,k,l,n,m,tot,tov[N],b[N],a[N],x,y,next[N],last[N],dis[N],dl[N],head,tail;
void lian(int x,int y){tot++,tov[tot]=y,next[tot]=last[x],last[x]=tot;}
void spfa(int x)
{
    memset(dis,,sizeof dis);
    dis[x]=,dl[]=x,head=,tail=;
    while(head<tail)
    {
        head++;
        int i=dl[head];
        for(j=last[i];j;j=next[j])
        {
            int y=tov[j];
            if(dis[y]<=m)continue;
            dis[y]=dis[i]+;
            tail++;
            dl[tail]=y;
        }
    }
    for(int i=;i<=n;i++)b[i]=max(b[i],dis[i]);
}
int main()
{
    freopen("oasis.in","r",stdin);
    freopen("oasis.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(i=;i<=k;i++)scanf("%d",&a[i]);
    for(i=;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        lian(x,y),lian(y,x);
    }
    for(i=;i<=k;i++)
    {
        spfa(a[i]);
    }
    for(i=;i<=n;i++)printf("%d ",b[i]);
}
           

T2題意

有N個點，點的度數為1或2，無重邊自環，不要求聯通， 求方案數，對998244353取膜

有大樣例

練習xjb猜公式的能力

T2代碼

#include<bits/stdc++.h>
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define mo 998244353
int n,x,y,z;
long long c[][],f[][],jc[],sum,a[];
using namespace std;
int main()
{
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    scanf("%d",&n);
    fo(i,,n){scanf("%d",&z);if(z==)x++;else y++;}
    if(x%2==)
    {
        printf("0");
        return ;
    }
    x/=;
    fo(i,,n)c[][i]=;
    fo(i,,n)fo(j,,n)c[i][j]=(c[i][j-]+c[i-][j-])%mo;
    jc[]=;
    fo(i,,n)jc[i]=(jc[i-]*i)%mo;  
    if(x==)
    {
        a[]=;
        fo(i,,y)
        {
            fo(j,,i)a[i]=(a[i]+a[i-j]*c[j-][i-]%mo*c[][j-]%mo*jc[j-]%mo)%mo;
        }
        printf("%lld",a[y]);
        return ;
    }   
    f[][]=;
    fo(i,,y)
    {
        fo(j,,i)f[][i]=(f[][i]+f[][i-j]*c[j-][i-]%mo*c[][j-]%mo*jc[j-]%mo)%mo;
    }
    fo(i,,x)
    {
        f[i][]=f[i-][]*(i*2-)%mo;
        fo(j,,y)
        {
            f[i][j]=;
            fo(k,,j)f[i][j]=(f[i][j]+f[i-][j-k]*(*i-)%mo*c[k][j]%mo*jc[k]%mo)%mo;
        }
    }
    printf("%lld ",f[x][y]);
}
           

T3題意

有一個長度為N的序列，權值在0~ 109 10 9 以内

每次修改一個值，然後求編号最小的權值恰好等于它前面所有點的權值之和的點（好像有點亂）

每次修改一個值，如果一個點的權值等于他前面所有點的權值之和，那它就是“史上最大毒瘤”，找出編号最小的史上最大毒瘤

開O2

練習xjb n2過50000 n 2 過 50000 的能力

#include<bits/stdc++.h>
using namespace std;
int i,n,m,x,y,j,k,sum,ans,a[];
int main()
{
    freopen("challenge.in","r",stdin);
    freopen("challenge.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=;i<=n;i++)scanf("%d",&a[i]);
    ans=;
    for(i=;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x]=y;
        if(ans<x)
        {
            printf("%d\n",ans);
            continue;
        }
        sum=k=;
        for(j=;j<=n;j++)
        {
            if(a[j]==sum)
            {
                ans=j;
                printf("%d\n",ans);
                k=;
                break;
            }
            sum+=a[j];
        }
        if(k==)
        {
            printf("-1\n");
            ans=;
        }
    }
}