The Final - NOIP2020游记

总结
编辑文章

Day -1

上午在洛谷上看到了个结论题的帖子,就去做了几道,感觉还行。剩下的时间就看自己做过的题,还有打打月赛之类的比赛里面的简单题。(太菜了

上午还跟徐妈扯了5min,终于成功把明早的集合时间从6:50改到7:10(我平时都是7:05才出寝室的说

昨天还计划今天21:20就去跑,跑个8km,结果下雨了(rp++

于是在这写游记日记。

还是惯例 NOIP2020 RP++

晚上从机房走的时候,想到这真的是最后一次在机房学竞赛了,突然有点触景生情。

晚上情绪不太好,还在群里发了一些感慨的话,感觉不太好就不放了。

Day 1

上午到校门口,发现徐妈给我们买了(除了早饭)一大袋吃的,有水、牛奶还有2条巧克力一条士力架,实名表白徐妈。

7:26就到了,本来以为要7:40才能进去,结果大概7:30就可以了,不过到了楼下还是排了半天队,在那听大佬们扯。

这次考号是按学校排的,还以为可以坐一起,进去以后才发现是竖着的顺序,然后我这个SC-0012就苦逼的坐到了最后一排。然后不准动键盘鼠标,就在那发呆。看着前面的那些人,想到自己再也不会作为选手出现在这了,就感到不是滋味。

先看T1,竟然一时间没想到拓扑,不过一看边数、层数 $\le 10$ ,写个爆搜跑了。想到了int不够,但没有算极限数据,也就没有写高精。

T2先想了个 $O(n^4)$ 的做法,然后前缀和优化掉了一维,码完一测发现1000的数据都能过,遂震惊的去上了个厕所。回来才发现复杂度算错了。然后回来写了个只有一种字母的情况,56分跑了。

坐我右边那个老哥最早提出T3数据范围有问题,改了以后放在投影上,我坐在最后一排看都看球不到;后来还说要用c11编译spj,当然编译命令也看不到(当然这点命令还是会的)。不过反正都做不来,输了个0滚了。

T4考虑极限状况对每个位置的贡献,打了个30分暴力。还剩的1h本来想写正解然后发现不会,只能写链的情况,不过貌似还写炸了。

考完估计 $100+56+0+40=196$ 。

下午15:13徐妈就把程序发给我了,我:???这么快的吗

oitiku上测的是 $100+56+0+30$,洛谷是 $90+56+?+?$(T3没测,T4还没数据)。大众分吧,自己感觉还行了。

剩下的时间颓,看皇室战争职业联赛全球总决赛,两支中国队NOVA和EDG都出局了,哎。

晚上一边循环Euphoria,一边完成了这篇游记。

那么,就这样结束了吧。

后记

出分了 $80+56+0+35=171$ ,T1有个地方没先除后乘挂了10分,不过也还可以了。

某天去机房填问卷的时候徐妈在场,告诉我很遗憾,差了4分,不过也在预料之中。

总的来说还是把自己垃圾的水平考出来了,没什么遗憾。接下来就专心搞文化课啦。

附录

附一下代码吧。

water.cpp:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=1e5+5;
vector <ll> e[N];
ll n,m,a,b,c,resp[N],resq[N];

// long long

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

void dfs(ll x,ll p,ll q)
{
    if (!e[x].size())
    {
        if (!resq[x] || !resp[x])
        {
            resq[x]=q; resp[x]=p;
            return;
        }
        ll curq=resq[x]*q;
        ll curp=resp[x]*q+resq[x]*p;
        ll g=gcd(curq,curp);
        curq/=g; curp/=g;
        resq[x]=curq; resp[x]=curp;
        return;
    }
    ll sz=e[x].size();
    ll g=gcd(p,sz);
    p/=g; sz/=g;
    ll nxtq=q*sz;
    for (ll i=0;i<sz;i++)
    {
        ll y=e[x][i];
        dfs(y,p,nxtq);
    }
    return;
}

int main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    n=read(); m=read();
    for (ll i=1;i<=n;i++)
    {
        a=read();
        for (ll j=1;j<=a;j++) e[i].push_back(read());
    }
    for (ll i=1;i<=m;i++)
    {
        //init();
        dfs(i,1,1);
    }
    for (ll i=1;i<=n;i++) if (!e[i].size()) printf("%lld %lld\n",resp[i],resq[i]);
    return 0;
}

string.cpp:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=(1<<20)+5;
int t,n,cntC[26],cntA[26],canSum[1005][1005],jiA[1005];
char s[N];
//bool can[1005][1005];

//long long

inline void init()
{
    memset(cntA,0,sizeof(cntA));
    memset(jiA,0,sizeof(jiA));
    for (int i=1;i<=n;i++)
    {
        int cur=s[i]-'a';
        cntA[cur]++;
        if (cntA[cur]&1) jiA[i]=jiA[i-1]+1;
        else jiA[i]=jiA[i-1]-1;
    }
    memset(cntC,0,sizeof(cntC));
    memset(canSum,0,sizeof(canSum));
    int jiC=0;
    for (int i=n;i;i--) //Cl
    {
        int cur=s[i]-'a';
        cntC[cur]++;
        if (cntC[cur]&1) jiC++;
        else jiC--;
        for (int j=1;j<i;j++)
        {
            canSum[i][j]=canSum[i][j-1];
            if (jiA[j]<=jiC) canSum[i][j]++;
        }
    }
    //for (int i=1;i<n;i++) cout<<i<<" "<<canSum[n][i]<<endl;
}

inline bool check(int Br,int l,int r)
{
    for (int i=1,j=l;i<=Br;i++,j++) if (s[i]!=s[j]) return 0;
    return 1;
}

int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    t=read();
    while (t--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        if (n<=1000)
        {
            init();
            ll ans=0;
            for (int Br=2;Br<n;Br++)
            {
                int maxi=1;
                for (int r=(Br<<1);r<n;maxi++,r+=Br)
                {
                    if (!check(Br,r-Br+1,r)) break;
                }
                for (int i=1;i<=maxi;i++)
                {
                    int Cl=i*Br+1;
                    ans+=canSum[Cl][Br-1];
                }
            }
            printf("%lld\n",ans);
        }
        else
        {
            bool flag=1;
            for (int i=2;i<=n;i++) flag&=s[i]==s[i-1];
            if (flag) //13~14
            {
                ll ans=0;
                for (int Cl=n;Cl>2;Cl--)
                {
                    int Br=Cl-1;
                    for (int i=1;i*i<=Br;i++)
                    {
                        if (Br%i) continue;
                        int maxAr=Br/i-1;
                        if ((n-Cl+1)&1) ans+=maxAr;
                        else ans+=maxAr>>1;
                        if (i==1 || i*i==Br) continue;
                        int i2=Br/i;
                        maxAr=Br/i2-1;
                        if ((n-Cl+1)&1) ans+=maxAr;
                        else ans+=maxAr>>1;
                    }
                }
                printf("%lld\n",ans);
            }
            else
            {
                puts("19260817");
            }
        }
    }
    return 0;
}

ball.cpp:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int main()
{
    freopen("ball.in","r",stdin);
    freopen("ball.out","w",stdout);
    cout<<0<<endl;
    return 0;
}

//I love OI forever
//Llf0703  NOIP2016~NOIP2020  AFO

walk.cpp:

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=5e5+5,K=15,ha=1e9+7;
ll n,k,w[K],c[N],d[N],mx[N],mn[N],cur[N],T[K];

// long long

int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    n=read(); k=read();
    ll ans=1,maxW=0;
    for (ll i=1;i<=k;i++) w[i]=read(),ans=1ll*ans*w[i]%ha,maxW=max(maxW,w[i]);
    for (ll i=1;i<=n;i++) c[i]=read(),d[i]=read(),T[c[i]]+=d[i];
    bool flag=1;
    for (ll i=1;i<=k;i++) flag&=T[i]==0;
    if (flag) return !printf("-1");
    if (k==1 && maxW>1000)
    {
        bool flag=1; ll res_sum=0;
        for (ll i=1;i<=n;i++)
        {
            if (i==n+1) i=1;
            cur[c[i]]+=d[i];
            mx[c[i]]=max(mx[c[i]],cur[c[i]]);
            mn[c[i]]=min(mn[c[i]],cur[c[i]]);
            ll res=1;
            for (ll j=1;j<=k;j++)
            {
                flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
                res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
            }
            if (!flag) break;
            (ans+=res)%=ha;
            (res_sum+=res)%=ha;
        }
        if (!flag) return !printf("%lld",ans);
        
        ll minT=min((w[1]-mx[1])/T[1],(w[1]+mn[1])/T[1]);
        for (ll t=1;t<=minT;t++) ans+=(res_sum-(1ll*n*T[1]%ha)*t%ha+ha)%ha;
        mx[1]=max(mx[1],mx[1]+T[1]*minT);
        mn[1]=min(mn[1],mn[1]+T[1]*minT);
        cur[1]+=T[1]*minT;
        
        for (ll i=1;i<=n;i++)
        {
            cur[c[i]]+=d[i];
            mx[c[i]]=max(mx[c[i]],cur[c[i]]);
            mn[c[i]]=min(mn[c[i]],cur[c[i]]);
            ll res=1;
            for (ll j=1;j<=k;j++)
            {
                flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
                res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
            }
            if (!flag) break;
            (ans+=res)%=ha;
        }
        return !printf("%lld",ans);
    }
    for (ll i=1;;i++)
    {
        if (i==n+1) i=1;
        cur[c[i]]+=d[i];
        mx[c[i]]=max(mx[c[i]],cur[c[i]]);
        mn[c[i]]=min(mn[c[i]],cur[c[i]]);
        ll res=1; bool flag=1;
        for (ll j=1;j<=k;j++)
        {
            flag&=((w[j]-mx[j])-(1-mn[j])+1)>0;
            res=1ll*res*((w[j]-mx[j])-(1-mn[j])+1)%ha;
        }
        if (!flag) break;
        (ans+=res)%=ha;
    }
    return !printf("%lld",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空
    llf 的小粉丝
    2020-12-04 21:56

    llf 加油!