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;
}

洛谷民间数据30pts,就过了Σc=0和前4个小数据。。。。。

T4

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

11.8

洛谷民间数据来一下: 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
????????T3洛谷给30,结果70???(暴力出奇迹
这数据真够水的 。。。。

期待NOIP2020,加油!