CSP-S 2020游记

· · 个人记录

Day\ 0

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

房间在顶楼， ~~刚开始觉得很安静~~ 一进门，巨大的落地窗映入眼帘(夜景一定超级棒)，落地窗旁边有一个长长的小沙发，感觉也很棒，沙发旁有一台电脑桌(不过没有电脑)，还有一把看上去不怎么专业的电竞椅?桌子上有插头和花，还有一个神秘的需要扫码的~~小~~盒子。里面装了什么？我不知道，隐约看到了$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，含泪60points，不甘心啊！但转念一想，如果交暴力，也许20points也没有，心里就好受了很多了。

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

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

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

Day\ 2

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

晚上快吃饭的时候，源代码下来了，从洛谷民间数据测了一下: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。