（无名氏）的博客

CSP2020 J/S

2020-11-17 23:21:34

欢乐CPS2020

before 10.10

混子一枚，整天无所事事

10.10

明天初赛了，赶快刷点模拟题，，，

10.11

9:30

提高初赛开考，首先，选择题，再见，后缀表达式忘了，栈忘了，dj算法复杂度忘了，，，全忘了，爬楼梯我特么忘进1了（（（智商-250，不过至少历史题猜对了，后面程序，还好，最后一题瞎蒙对了4题，，，，

14：30

该普及了，这个简单，，，不过。。。。。选择题最后一题不能同时选三个手套？？？？（语文不及格，是语文老师的锅） 后面还简单，基本没错多少

最后pj93.5，tg71，JS分数线pj63，tg58，危

10.12~11.5

丝毫没复习，准备完全裸考

11.6

为了赶路，能旷课，开森开森 晚上赶快抱佛脚，复习了一堆模板（似乎并没有什么卵用（（（

11.7

8：30

想想去年的简单（在考试之后才认为的），我飘了

T1，

简单，，，超级送分

T2，

我傻眼了（本人近视2500000000度，看不见ai≤600），当时想到了multiset，但是写炸了，，于是，，，我。。。

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x) {
    x = 0;
    register char c = getchar();
    while(c > '9' || c < '0')
        c = getchar();
    do {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    } while(c <= '9' && c >= '0');
}
int n,w,people,a[100005];
int main() {
    freopen("live.in","r",stdin);
    freopen("live.out","w",stdout);
    read(n);
    read(w);
    for(int i = 1; i <= n; ++i) {
        read(a[i]);
        people = max(1,i * w / 100);
        nth_element(a + 1,a + i + 1 - people,a + i + 1);
        cout << a[i + 1 - people] << " ";
    }
    return 0;
}

nth_element是个好东西，，，，O（n^2），呵呵，

T3

看来一眼，完全蒙了
连捞分都想不到。
不会再见。

然后T4

先写了个O（n^2m^2）的dp（从没做过，根本看不出来正解）

但是又炸了，，，没办法，记忆化搜索吧（结果，，，我特么忘加vis了，当场去世）

然后回到T3，啊啊啊看出来了，是数（哦不，树）！！！（自我膨胀）。。。。 1.5hours later T3写炸了，只好，。。。

cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x[i];
        if(x[i] == 1)
        f0 = 1;
        else f1 = 1;
    }       
    cin >> q;
    while(q--) {
        cin >> k;
        x[k] = !x[k];
        if(!f0)
        cout << "1\n";
        else if(!f1)
        cout << "0\n";
        else{
            srand(time(0));
            cout << rand() % 2 << endl;
        }
        x[k] = !x[k];
    }

（竟然有15分，不可思议）

中午

南航外点了啃得鸡，睡了个美觉，校园里转了转，顺便遇到大佬膜拜

14：30

考提高了，先赶快南无阿弥陀佛，保佑保佑

T1

又是道pig国杀

先一天一天模拟，再一年一年模拟，最后400一次跳过
从-4712开始（这样简便，相当于把公元前n年整体变成公元前（n-1）年，这样公元0年就有了意义，最后输出处理下即可）
然后算出1592年10月4日对于的儒略历为2299161，分情况讨论
儒略历2299161之前的4年1461天一个轮回，之后的400年146097天一个轮回，直接一次跳过，最后处理剩下的一点点
大样例竟然过了100妥妥的，不是100我改不了吃我（请看程序第13行（快读程序下一行），，，醉了，又是严重近视）

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x) {
    x = 0;
    register char c = getchar();
    while(c > '9' || c < '0')
        c = getchar();
    do {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    } while(c >= '0' && c <= '9');
}
int Q,r,y,m,d;//咳咳，变量类型忽略忽略~~就当没有“年份答案不超过10^9~~)
int a[] = {29,31,28,31,30,31,30,31,31,30,31,30,31};
inline void go_days() {//1592年10月4日及之前1天1天走
    --r;
    ++d;
    if(m == 2 && !(abs(y) % 4))//事实证明，不用取绝对值
        if(d > 29) {
            ++m;
            d = 1;
        } else;
    else if(d > a[m]) {
        ++m;
        d = 1;
    }
    if(m > 12) {
        ++y;
        m = d = 1;
    }
}
inline void go_days2() {1592年10月4日之后1天1天走
    --r;
    ++d;
    if(m == 2 && (!(y % 400) || !(y % 4) && y % 100))
        if(d > 29) {
            ++m;
            d = 1;
        } else;
    else if(d > a[m]) {
        ++m;
        d = 1;
    }
    if(m > 12) {
        ++y;
        m = d = 1;
    }
}
inline void go_years() {1592年10月4日及之前走1年1年走
    int t = r / 1461;
    r -= t * 1461;
    y += 4 * t;//直接跳过4年的轮回
    while(r > 366 || abs(y) % 4 && r > 365) {//处理剩下的0~3年
        r -= 365;
        if(!(abs(y) % 4))
            --r;
        ++y;
    }
}
inline void go_years2() {1592年10月4日之后走1年1年走
    int t = r / 146097;
    y += 400 * t;
    r -= t * 146097;//直接跳过400年的轮回
    while(r > 366 || (y % 4 || !(y % 4) && y % 400) && r > 365) {//处理剩下的0~399年
        r -= 365;
        if(!(y % 400) || !(y % 4) && y % 100)
            --r;
        ++y;
    }
}
int main() {
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    read(Q);
    while(Q--) {
        read(r);
        y = -4712;
        m = d = 1;
        if(r >= 2299161) {//1592年10月4日之后
            r -= 2299161;
            y = 1582;
            m = 10;
            d = 15;
        } else {1592年10月4日及之前
            go_years();
            while(r)
                go_days();
        }
        if(r) {1592年10月4日之后
            while(r && (m != 1 || d != 1))
                go_days2();
            go_years2();
            while(r)go_days2();
        }
        if(y <= 0)
            printf("%d %d %d BC\n",d,m,-y + 1);//公元前
        else printf("%d %d %d\n",d,m,y);//公元后
    }
    return 0;
}

我#@/|/*/****这特么卡int啊

下面T2

特么读了15分钟才读懂

发现c和q简直是fw，一下子想到了位运算，就是生成个购物清单，其二进制上有假设有t个0，则总情况数就是2^t，减掉重复的n,直接正解
想到k=64，m=0的情况，直接输出18446744073709551616
一道签到题（最后几分钟才发现要加ull，危）

#include<bits/stdc++.h>
using namespace std;
inline void read(unsigned long long &x) {
    x = 0;
    register char c = getchar();
    while(c > '9' || c < '0')
        c = getchar();
    do {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    } while(c >= '0' && c <= '9');
}
int m,c,k,t;
unsigned long long animal,vis,n,ans,a,p,q;
int main() {
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    cin >> n >> m >> c >> k;
    for(int i = 1; i <= n; ++i) {
        read(a);
        animal |= a;
    }
    for(int i = 1; i <= m; ++i) {
        read(p);
        read(q);
        if(!(animal & (1ull << p)))
            vis |= (1ull << p);
    }
    for(int i = 63; i >= 0; --i)
        if((1ull << i) <= vis) {
            ++t;
            vis -= (1ull << i);
        }
    if(k == 64 && !t && !n)
        cout << "18446744073709551616";
    else {
        if(k == 64 && !t)
            ans = (1ull << (k - 1)) - n + (1ull << (k - 1));//（1ull<<64)会超范围，小心了
        else ans = (1ull << (k - t)) - n;
        cout << ans;
    }
    return 0;
}

T3

看到这题，啊，区间乘法，这不就是线段树的板子吗
当然，玄学优化还是要有的（其实应该再加个快写的，不过我有点懒）
（什么拓扑排序的根本不会）
竟然过了大样例（吐槽这数据真水）

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
inline void read(int &x) {
    x = 0;
    register char c = getchar();
    while(c > '9' || c < '0')
        c = getchar();
    do {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    } while(c >= '0' && c <= '9');
}
struct node {
    int T,p,v,c;
    vector<int> g;
} f[100005];
struct tree {
    int l,r;
    long long lazy;
} a[400005];
int n,m,q,_g,_f,x,y,k,arr[100005];
void build(int p,int l,int r) {
    a[p].l = l;
    a[p].r = r;
    a[p].lazy = 1;
    if(l == r) {
        a[p].lazy = arr[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
}
inline void push_down(int p) {
    if(a[p].lazy != 1 && a[p].l != a[p].r) {
        a[p << 1].lazy = a[p << 1].lazy * a[p].lazy % mod;
        a[p << 1 | 1].lazy = a[p << 1 | 1].lazy * a[p].lazy % mod;
        a[p].lazy = 1;
    }
}
inline void update1(int p) {
    a[p].lazy = a[p].lazy * k % mod;
}
void update2(int p,int x) {
    if(x == a[p].l && x == a[p].r) {
        a[p].lazy = (a[p].lazy + k) % mod;
        return;
    }
    push_down(p);
    int mid = a[p].l + a[p].r >> 1;
    if(x <= mid)
        update2(p << 1,x);
    else
        update2(p << 1 | 1,x);
}
long long que(int p,int x) {
    if(x == a[p].l && x == a[p].r)
        return a[p].lazy;
    push_down(p);
    int mid = a[p].r + a[p].l >> 1;
    if(x <= mid)
        return que(p << 1,x);
    return que(p << 1 | 1,x);
}
void dfs(int x) {
    for(register int i = 0; i < f[x].c; ++i) {
        if(f[f[x].g[i]].T == 3)
            dfs(f[x].g[i]);
        else {
            k = f[f[x].g[i]].v;
            if(f[f[x].g[i]].T == 2)
                update1(1);
            else update2(1,f[f[x].g[i]].p);
        }
    }
}
int main() {
    freopen("call.in","r",stdin);
    freopen("call.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        read(arr[i]);
    build(1,1,n);
    cin >> m;
    for(int i = 1; i <= m; ++i) {
        read(f[i].T);
        if(f[i].T == 1) {
            read(f[i].p);
            read(f[i].v);
        } else if(f[i].T == 2) {
            read(f[i].v);
        } else {
            read(f[i].c);
            for(int j = 1; j <= f[i].c; ++j) {
                read(_g);
                f[i].g.push_back(_g);
            }
        }
    }
    cin >> q;
    for(int i = 1; i <= q; ++i) {
        read(_f);
        if(f[_f].T == 3)
            dfs(_f);
        else {
            k = f[_f].v;
            if(f[_f].T == 2)
                update1(1);
            else update2(1,f[_f].p);
        }
    }
    for(int i = 1; i <= n; ++i)
        printf("%d ",que(1,i));
    return 0;
}

betway必威体育官方民间数据30pts，就过了Σc=0和前4个小数据。。。。。

T4

写了半天歪解完全想写炸了，最后就写个n=3了

11.8

betway必威体育官方民间数据来一下： pj：100+85+5+0=185（我太阳）
tg：90+100+30+20=240
完了完了，彻底完了(心如土灰)

after 11.8

复习，准备期中考，考完了，又是完美偏科

11.16

pj出成绩了： 100+85+15+5=205
？？？T3rand给了15？？？？
tg： 90+100+70+20=280
？？？？？？？？T3betway必威体育官方给30，结果70？？？（暴力出奇迹）
这数据真够水的 。。。。

期待NOIP2020，加油！