CSP2020 J/S

# **~~欢乐~~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，但是写炸了，，于是，，，我。。。 ```cpp #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写炸了，只好，。。。 ```cpp 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行（快读程序下一行），，，醉了，~~又是严重近视~~） ```cpp #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，危） ```cpp #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 看到这题，啊，区间乘法，这不就是线段树的板子吗 当然，玄学优化还是要有的（其实应该再加个快写的，不过我有点懒） （什么拓扑排序的根本不会） 竟然过了大样例（~~吐槽这数据真水~~） ```cpp #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，加油！