NXY's Bolg

NXY's Bolg

——也许这就是最后的倔强了吧!

CSP-S 2020游记

posted on 2020-11-08 15:21:36 | under 游记 |

$Day\ 0$

早晨起晚了 $qwq$,不过应该没有太大关系吧毕竟没有人查。穿好衣服之后强忍想要出门的欲望站在屋子里想是否忘了什么事情,没有想起来就出门了,到了机房,高二的被教导员喊走了,就剩下我一个人。过了一会, $zzh$进门的一瞬间,我就想起来忘了给我妈说发健康码的事情了。等到 $zp$一来,我就去给我妈打电话了 $emmm$。

$9:00$准时出发,和 $zhs$坐在了一起 $qwq$,有一点晕车,所以大部分时间不是吃就是睡, $zp$说 $5h$就可以到日照了,结果到了下午 $5:00$才刚进酒店(由于疫情的原因,宿舍不让用了 $emmm$,只好集体住酒店喽 $qwq$, $zp$和 $yp$去找了大约 $15min$才回来,他们说是新开的,还没有挂牌,淦! 当时我脑海里浮现出来的画面只有那种路边开的,环境卫生很差的偏远小宾馆,结果我被狠狠的打脸了,好爽。 酒店非常棒!学 $OI$的两年以来,第一次住这么好的宾馆,让我不禁怀疑这到底是不是 $140$一晚上的两人标准间:

房间在顶楼, 刚开始觉得很安静 一进门,巨大的落地窗映入眼帘(夜景一定超级棒),落地窗旁边有一个长长的小沙发,感觉也很棒,沙发旁有一台电脑桌(不过没有电脑),还有一把看上去不怎么专业的电竞椅?桌子上有插头和花,还有一个神秘的需要扫码的盒子。里面装了什么?我不知道,隐约看到了 $DLS$,咱也不知道,咱也不敢问。 卫生间很干净。

收拾完, $zp$把我们叫过去了,他就在 $715$,我在 $727$,我们对面。说了一些注意事项。 $yp$突然说电视别看太晚,结果 $zp$直接说不准看电视, $9:30$睡觉,明天 $8:00$起床。

回到房间,发现还有抽烟机和洗衣机?! $zhs$趴在窗户旁边不知道在看些什么,只听见他说:

唔!看对面有一个小女孩在跳舞!

跳得不错!

她在对着镜子自己跳。

不对,她妈妈在教她。

此女必成大器

跳的不错qwq

过了一会, $zy$来了,臭小子竟然想霸弓硬上王? $zy$说:"插头里面可能有摄像头啊!"把正在从壁画里找摄像头的 $zhs$说了一愣(细思极恐),他是怎么知道的,咱也不知道,咱也不敢问

快睡觉的时候,和 $zhs$下了几盘五子棋,好玩

还是很紧张,复习去了。

$Day\ 1$

下午要考试了,紧张...心里一直默默回顾自己的作战计划:

2:30~2:50读题

2:50~4:00打暴力

4:00~6:20优化暴力

6:20~6:30检查

醒来去洗漱,没想到水龙头是有热水的,满足 $qwq$,昨天晚上睡得不太好,醒了好几次。 $8:10$的时候, $zp$喊我们吃饭,腿有点酸 $emmm$昨晚和 $zhs$聊了好久,没想到这个家伙睡觉打呼噜。

吃完饭, $zp$说不能睡觉现在,等吃完午饭再睡,昏昏欲睡的我只好去看书,发现了很多以前忽视但实质上是最重要的东西——思维。书里会给你提供一些做题的思路,但以前急功近利的我却忽视了这些东西,现在说什么都已经晚了。

他们几个说宾馆隔音效果不太好,可以听到奇怪的声音,具体是什么,咱也不知道,咱也不敢问

吃完饭,应该去睡一会了,还是很紧张...

呼,考完了,崩了, $T1$是一个模拟,赶紧打完暴力,好像会超时,不过没管,按照计划先把暴力打完再去优化, $T2$先写了暴力, $T3$发现是一个 $DAG$,想跑拓扑排序,但是优先级的问题貌似有些难处理,于是先打了暴力。 $T4$看着像博弈论,果断放弃,回去调 $T1$, $T2$了。当时已经 $4:30$了,发现 $T1$可以分段讨论,讨论完之后稀里糊涂的过了大样例,大样例真水啊。事后发现好多边界没有判,甚至把十月当成了三十天来算都没出错。 $T1$对拍上来就已经 $5:30$了,接着看 $T2$,发现可以按位讨论,每一位只有 $2$或者 $1$两种情况,容斥一下过了大样例。对拍时出了一点锅,发现暴力数组开小了,处理完已经 $6:20$了。事后发现数组 $a_i$忘了开ull,含泪60 $points$,不甘心啊!但转念一想,如果交暴力,也许 $20points$也没有,心里就好受了很多了。

剩下 $10min$去检查文件名了。

晚上出来之后,发现大家都崩了,心里就不是那么难受了,回酒店的路上,发现了找了好久的万达广场,原来它在东面,于是就决定去那里吃饭,在四楼吃了自助餐, $axy$说这是提前欢迎我们回归文化课,欠揍。终于吃完了之后,在下楼的路上发现了电玩城, $zy$, $sjy$等人像饿狼一般扑了上去,我本不想去,可 $zhs$说要不要...给她抓一个娃娃?于是立马就把我说服了,一共买了 $80RMB$的游戏币,结果...铩羽而归,很遗憾。从万达出来时,已经快 $10:00$了,于是八个人向疯子一样狂奔。突然 $szz$大吽了一声,所有人都笑了。 $wqy$说了一句什么,我没听清, $zzh$开始狂笑。

也许,这才是学 $OI$该有的样子叭。

$Day\ 2$

老实点,回家了。 依稀记得昨晚和 $zhs$玩了三局旗,很开心。然后看黑豹,由于我看过所以看了一半睡着了, $zhs$说他看完了,(漫威真香)

晚上快吃饭的时候,源代码下来了,从betway必威体育官方民间数据测了一下: $90+65+25+5=185$。 $T1$忘了开 $ll$了啊含泪 $90pts$, $T2$果不其然爆炸了。 $T3$按照 $20pts$打的没想到多过了一个点...挂了 $45pts$,感觉很难受。

牛客: $90+95+25+0=210$,貌似没卡我?


$For\ a\ long\ time$

官方成绩: $90+60+25+0=175$, $SD\ rk81$

屑代码:

$T1$

#include<cstdio>

using namespace std;

const int d1 = 365;//平年 
const int d2 = 366;//闰年 
const int T = 1461;

int q;
bool v[13];

bool pd(int x)
{
    if(x <= 1582)
    {
        if(x > 0 && x % 4 == 0)
            return true;
        if(x < 0 && (x + 1) % 4 == 0)
            return true;
    }
    if(x > 1582 && ((x % 400 == 0) || (x % 4 == 0 && x % 100 != 0))) return true;
    return false;
}

void cl(int ri , int &month , int &day , int &year)
{
    for(year;;)
    {
        if(year == 0) year++;
        if(pd(year))
        {
            if(ri >= d2) ri -= d2 , year++;
            else break;
        }
        else
        {
            if(year != 1582)
            {
                if(ri >= d1) ri -= d1 , year++;
                else break;
            }
            else
            {
                if(ri >= d1 - 10) ri -= d1 - 10 , year++;
                else break;
            }
        }
        if(ri == 0) break;
    }
    if(year == 0) year++;
    for(month;;)
    {
        if(month == 2)
        {
            if(pd(year))
            {
                if(ri >= 29) ri -= 29 , month++;
                else break;
            }
            else
            {
                if(ri >= 28) ri -= 28 , month++;
                else break;
            }
        }
        else
        {
        if(v[month])
        {

            if(ri >= 30) ri -= 30 , month++;
            else break;

        }
        else
        {
            if(year != 1582 || month != 10) 
            {   
                if(ri >= 31) ri -= 31 , month++;
                else break;
            }
            else
            {
                if(ri >= 21) ri -= 21 , month++;
                else break;
            }
        }
        }
        if(ri == 0) break;
    }
    if(year == 1582 && month == 10 && ri >= 4)
        day = ri + 11;
    else day = ri + 1; 
}

void work()
{
    int ri; scanf("%d",&ri);
    if(ri <= 1721424) //[-4713 , -1]
    {
        int year = -4713 , day = 1 , month = 1;
        int k = ri / T , r = ri % T;
        year += k * 4;
        cl(r , month , day , year);
        if(year == 0) year++;
        if(year < 0) printf("%d %d %d BC\n",day , month , -year);
        else printf("%d %d %d\n",day , month , year);
    }
    else
    {
        ri -= 1721424;
        if(ri < 577095)//[1 , 1580]
        {
            int year = 1 , day = 1 , month = 1;
            int k = ri / T , r = ri % T;
            year += k * 4;
            cl(r , month , day , year);
            if(year < 0) printf("%d %d %d BC\n",day , month , -year);
            else printf("%d %d %d\n",day , month , year);
        }
        else
        {
            ri -= 577095;
            if(ri <= 365 * 2 - 10)
            {
                int year = 1581 , day = 1 , month = 1;
                cl(ri , month , day , year);
                if(year < 0) printf("%d %d %d BC\n",day , month , -year);
                else printf("%d %d %d\n",day , month , year);
            }
            else
            {
                int year = 1583 , day = 1 , month = 1;
                ri -= 365 * 2 - 10;
                int k = ri / 146097 , r = ri % 146097;
                year += k * 400;
                cl(r , month , day , year);
                if(year < 0) printf("%d %d %d BC\n",day , month , -year);
                else printf("%d %d %d\n",day , month , year);
            }
        }
    }
}

int main()
{
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    v[4] = v[6] = v[9] = v[11] = 1;
    scanf("%d",&q);
    while(q--)
        work();
    return 0;
}

$T2$

#include<cstdio>
#include<iostream>

using namespace std;

const int N = 1e6 + 1;
const int M = 1e8 + 1;
const int Bit = 64;

int n,m,c,k;
unsigned long long ans = 1;
int a[N];
bool v[Bit],b[Bit];

void cl(int x)
{
    int bit = 0;
    while(x)
    {
        if((x & 1) && b[bit])
            v[bit] = 1;
        x >>= 1;bit++;
    }
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout); 
    scanf("%d %d %d %d",&n,&m,&c,&k);
    for(int i = 1; i <= n; i++) 
    scanf("%d",&a[i]);
    for(int i = 1; i <= m; i++)
    {
        int pi,qi; scanf("%d%d",&pi,&qi);
        b[pi] = 1;
    }
    for(int i = 1; i <= n; i++)
        cl(a[i]);
    for(int i = 0; i < k; i++)
    {
        if(!v[i] && b[i]) ans *= 1;
        else ans *= 2;
    }
    cout<<ans - n;return 0;
}

$T3$

#include<cstdio>

using namespace std;

typedef long long ll;

const int N = 2e4 + 10;
const int mod = 998244353;

ll cj = 1;
int n,m,q,sum;
int first[N];
ll a[N];

struct E
{
    int next;
    int to;
    void add(int x , int y)
    {
        next = first[x];
        to = y;
        first[x] = sum;
    }
}e[N];

struct NO
{
    int ti;
    int p,v;
}Node[N];

struct Sig
{
    int l;
    int r;
    int w;
    int lazy;
};

void dfs(int x)
{
    if(Node[x].ti == 1 || Node[x].ti == 2)
    {
        if(Node[x].ti == 1)
        {
            for(int i = 1; i <= n; i++)
                a[i] = (a[i] * cj) % mod;
            a[Node[x].p] += Node[x].v; a[Node[x].p] %= mod;
            cj = 1;
        }
        else cj = (cj * Node[x].v) % mod;
    }
    else
    {
        int b[N];b[0] = 0;
        for(int i = first[x]; i ; i = e[i].next)
        {
            int to = e[i].to;
            b[++b[0]] = to;
        }
        for(int i = b[0]; i >= 1; i--)
            dfs(b[i]);
    }
}

int main()
{
    freopen("call.in","r",stdin);
    freopen("call.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    scanf("%d",&m); 
    for(int i = 1; i <= m; i++)
    {
        int op,pi,vi,ci; scanf("%d",&op);
        switch(op)
        {
            case 1:
                scanf("%d%d",&pi,&vi);
                Node[i] = (NO){op,pi,vi};
                break;
            case 2:
                scanf("%d",&vi);
                Node[i] = (NO){op,0,vi};
                break;
            case 3:
                scanf("%d",&ci);
                for(int j = 1; j <= ci; j++)
                {
                    int ui; scanf("%d",&ui);
                    e[++sum].add(i , ui);
                }
                Node[i] = (NO){op,0,0};
                break;
            break;
        }
    }
    scanf("%d",&q);
    for(int i = 1; i <= q; i++)
    {
        int fi; scanf("%d",&fi);
        dfs(fi);
    }
    for(int i = 1; i <= n; i++)
        a[i] = (a[i] * cj) % mod;
    for(int i = 1; i <= n; i++)
        printf("%lld ",a[i]);
    return 0;
}   

经过小修小补,很快就把 $T1,T2$的锅修好了emmmm。 现在终于把 $T3$调过了。

修改之后的代码:

$T1$

#include<cstdio>

using namespace std;

const int d1 = 365;//平年 
const int d2 = 366;//闰年 
const int T = 1461;

int q;
bool v[13];

bool pd(int x)
{
    if(x <= 1582)
    {
        if(x > 0 && x % 4 == 0)
            return true;
        if(x < 0 && (x + 1) % 4 == 0)
            return true;
    }
    if(x > 1582 && ((x % 400 == 0) || (x % 4 == 0 && x % 100 != 0))) return true;
    return false;
}

void cl(int ri , int &month , int &day , int &year)
{
    for(year;;)
    {
        if(year == 0) year++;
        if(pd(year))
        {
            if(ri >= d2) ri -= d2 , year++;
            else break;
        }
        else
        {
            if(year != 1582)
            {
                if(ri >= d1) ri -= d1 , year++;
                else break;
            }
            else
            {
                if(ri >= d1 - 10) ri -= d1 - 10 , year++;
                else break;
            }
        }
        if(ri == 0) break;
    }
    if(year == 0) year++;
    for(month;;)
    {
        if(month == 2)
        {
            if(pd(year))
            {
                if(ri >= 29) ri -= 29 , month++;
                else break;
            }
            else
            {
                if(ri >= 28) ri -= 28 , month++;
                else break;
            }
        }
        else
        {
        if(v[month])
        {

            if(ri >= 30) ri -= 30 , month++;
            else break;

        }
        else
        {
            if(year != 1582 || month != 10) 
            {   
                if(ri >= 31) ri -= 31 , month++;
                else break;
            }
            else
            {
                if(ri >= 21) ri -= 21 , month++;
                else break;
            }
        }
        }
        if(ri == 0) break;
    }
    if(year == 1582 && month == 10 && ri >= 4)
        day = ri + 11;
    else day = ri + 1; 
}

void work()
{
    long long ri; scanf("%lld",&ri);
    if(ri <= 1721424) //[-4713 , -1]
    {
        int year = -4713 , day = 1 , month = 1;
        int k = ri / T , r = ri % T;
        year += k * 4;
        cl(r , month , day , year);
        if(year == 0) year++;
        if(year < 0) printf("%d %d %d BC\n",day , month , -year);
        else printf("%d %d %d\n",day , month , year);
    }
    else
    {
        ri -= 1721424;
        if(ri < 577095)//[1 , 1580]
        {
            int year = 1 , day = 1 , month = 1;
            int k = ri / T , r = ri % T;
            year += k * 4;
            cl(r , month , day , year);
            if(year < 0) printf("%d %d %d BC\n",day , month , -year);
            else printf("%d %d %d\n",day , month , year);
        }
        else
        {
            ri -= 577095;
            if(ri <= 365 * 2 - 10)
            {
                int year = 1581 , day = 1 , month = 1;
                cl(ri , month , day , year);
                if(year < 0) printf("%d %d %d BC\n",day , month , -year);
                else printf("%d %d %d\n",day , month , year);
            }
            else
            {
                int year = 1583 , day = 1 , month = 1;
                ri -= 365 * 2 - 10;
                int k = ri / 146097 , r = ri % 146097;
                year += k * 400;
                cl(r , month , day , year);
                if(year < 0) printf("%d %d %d BC\n",day , month , -year);
                else printf("%d %d %d\n",day , month , year);
            }
        }
    }
}

int main()
{
//  freopen("julian.in","r",stdin);
//  freopen("julian.out","w",stdout);
    v[4] = v[6] = v[9] = v[11] = 1;
    scanf("%d",&q);
    while(q--)
        work();
    return 0;
}

$T2$

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
const int Bit = 101;
const unsigned long long inf = 18446744073709551615;
int n,m,c,k;
unsigned long long a[N];
ll ans = 1;
bool v[Bit] , b[Bit] ,flag;

void cl(unsigned long long x)
{
    int bit = 0;
    while(x)
    {
        if(x & 1) v[bit] = 1;
        x >>= 1; bit++;
    }
}

int main()
{
//  freopen("aa.in","r",stdin);
    scanf("%d %d %d %d",&n,&m,&c,&k);
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= m; i++)
    {
        int pi,qi; scanf("%d %d",&pi,&qi);
        b[pi] = 1;
    }
    for(int i = 1; i <= n; i++)
        cl(a[i]);
    for(int i = 0; i < k; i++)
        if(!v[i] && b[i]) ans *= 1 ,flag = 1;
        else ans *= 2;
    if(!flag && k == 64)
    { 
        if(n == 0)
        printf("18446744073709551616");
        else cout<<inf - n + 1;
    }
    else cout<<ans - n;
    return 0;
}

$T3$

#include<cstdio>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 998244353;

typedef long long ll;

int n,m,q,sum;
int f[M],first[M],inn[M];
ll a[N],mult,_mult[N],Add[N];
bool v[N];

struct NO
{
    int ty;
    int p;
    int v;
    ll mul;
    ll w;
}Node[M];

struct E
{
    int next;
    int to;
    void add(int x , int y)
    {
        next = first[x];
        to = y;
        first[x] = sum;
    }
}e[M * 2];

struct queue
{
    int head,tail;
    int a[M];

    void clear()
    {head = tail = 0;}

    void push(int x)
    {a[tail++] = x;}

    void pop()
    {head++;}

    int front()
    {return a[head];}

    bool empty()
    {return head == tail ? true : false;}

}qu;

void in(int &x)
{
    x = 0; char ee = getchar();
    while(ee < '0' || ee > '9') ee = getchar();
    while(ee >= '0' && ee <= '9') x = (x << 1) + (x << 3) + ee - '0' , ee = getchar();
}

void dfs(int x)
{
    if(Node[x].ty == 1 || Node[x].ty == 2)
    {
        if(Node[x].ty == 2)
        _mult[x] = Node[x].v;
        return;
    }
    for(int i = first[x]; i ; i = e[i].next)
    {
        int to = e[i].to;
        if(!v[to]) dfs(to) , v[to] = 1;
        _mult[x] *= _mult[to] , _mult[x] %= mod;
    }
}

void topo_sort()
{
    for(int i = 1; i <= m; i++)
        if(!inn[i]) qu.push(i);
    while(!qu.empty())
    {
        int now = qu.front(); qu.pop();
        if(Node[now].ty == 1) Add[Node[now].p] += Node[now].v * Node[now].w , Add[Node[now].p] %= mod;
        ll k = Node[now].w;
        for(int i = first[now]; i ; i = e[i].next)
        {
            int to = e[i].to;
            inn[to]--; if(!inn[to]) qu.push(to);
            Node[to].w += k , Node[to].w %= mod;
            k *= _mult[to] , k %= mod;
        }
    }
}

int main()
{
//  freopen("aa.in","r",stdin);
//  freopen("aa.out","w",stdout);
    in(n);
    for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
    in(m);
    for(int i = 1; i <=m; i++)
    {
        int tye; in(tye); _mult[i] = 1;
        switch(tye)
        {
            int pi , vi , ci;
            pi = 0 , vi = 0 , ci = 0;
            case 1:
                in(pi);in(vi);
                Node[i] = (NO){tye,pi,vi,1,0};
                break;
            case 2:
                in(vi);
                Node[i] = (NO){tye,pi,vi,1,0};
                break;
            case 3:
                in(ci);
                for(int j = 1; j <= ci; j++)
                {
                    int gi; in(gi);
                    inn[gi]++;
                    Node[i] = (NO){tye,pi,vi,1,0};
                    e[++sum].add(i , gi);
                }
                break;
            break;
        }
    }
    in(q);mult = 1;
    for(int i = 1; i <= q; i++)
        in(f[i]);
    for(int i = 1; i <= m; i++)
        if(!inn[i]) dfs(i);
    for(int i = q; i >= 1; i--)
    {
        int id = f[i];
        if(Node[id].ty == 1) Node[id].w += mult;
        else if(Node[id].ty == 2) mult *= _mult[id] , mult %= mod;
        else  Node[id].w += mult , mult *= _mult[id] , mult %= mod;
    }
    topo_sort();
    for(int i = 1; i <= n; i++)
        printf("%lld ",((a[i] * mult) % mod + Add[i] % mod) % mod);
    return 0;
}

吐槽: $T1$卡int, $T2$卡ull,不愧是你。 $CCF$。