-1 month 初赛
S 组
前一天晚上翻下真题,感觉也不知道复习些什么了,于是扔了。
早上也是。
考场要 20 min 才能到。找到考场坐下来,怎么感觉一堆人比我小啊,是不是没救了(
开题。
选择题没啥问题。视频大小一开始以为 32 位 32bit,没救了(
CRT 的题,直接算出来 53,不知道怎么估计区间。
信息论???
草昨晚才看到这题啊,当时就扔了没翻答案,当时蒙对了,现在蒙错了,没救了(
选择 -2。
阅读 1 没错。
阅读 2 是个经典求 k 小,但是为什么都是算复杂度的???
T3 错题,一半猜的 $\log$。
T4 没啥问题第一层就是 $\mathcal O(n)$ 了。
T5 前一个显然是 $\mathcal O(n)$,后一个排除掉 $\log n$ 就行了。
T6 显然。
阅读 3,挺自闭的,不过坚持看完了,大概是个双向 BFS,搜什么过一会才看出来是 $[0,m]$ 和 $[m,len)$ 的循环置换。
T3 以为比 $n!$ 还低,就是以为是 $[0,m - 1]$ 和 $[m,len)$ 然后只有多项式种状态。
不过好歹对了(
T5 T6 当场爬了,想了一会,尝试找 T5 的最优方案。然后没找出来。
只有 30 min 了,非常自闭。
于是先去完善程序。
第一篇没问题,就是猜也能大概对了。T5 空脑残,错掉了。
-3。
第二篇前两空和 DP 没关系。但是没时间去细想转移方式了,T3 空填错,T4 空半猜对,T5 空填错。
-6。
回去看两个 4 分题。
打算猜一个 T5,然后觉得可以猜二次关系。
然后好像真有,但是想当然觉得可以 $f(0) = 0$,就算不出来,没救了(
非常自闭。
猜了个错的。
T6 没时间了,蒙对了(
-4。
预计 85。
中午
出来的时候觉得要完蛋了。
但是对了下粉兔答案,发现蒙对挺多(
下午的也就放心了(
J 组
挂得非常惨。
考场一群小学生,感觉非常不自在。
我市 380 人左右(J 组)。S 组的名单上午没看,下午就撕了,不知道。
开题,单选前面非常简单,又是 15 题,看到了恰好但没算进去,150 完美踩坑。
-2。
阅读 1 是个字符映射,没问题。
阅读 2 是对于 k 进制,问一个一个加进位多少。k = 1 特殊情况。
不记得 T2 T3 填的是什么。。。大概脑残都填的是正确。
-1.5。
T4 仍然脑残,踩坑了。
-2。
阅读 3 是喜闻乐见的合并求价值。
T1 又又又脑残了。
-1.5。
T4 T5 T6 就都是计算吗。。算出个 T4,后面暂时不会,去完善了。
完善 1 是个板子。
完善 2 贪心,也挺经典。
T1 反了,没救了。
T5 加了个 1,没救了。
-6。
回去看阅读后几题。主要是 1 序列(取绝对值的)不知怎样分析的。
草原来是 $\max$ 吗。。。这就去眼科医院。
那么 T5 就切掉了。
T6 发现仍然和前几问一样,从左往右合并就行的。。。
还以为是什么题呢,原来是单纯算就完了吗(
但是 1 序列不太好算,14 个二次式子求和,决定暴力算。
还有 15 min 吗,不过来得及。怎么做这么慢啊草
算了两三遍,然后和选项对上了,就填上去了。后面在略略检查。
查了个寂寞,一个脑残都没查出来
出来后对一下三个计算都没错,但是出正式答案才知道挂了多少分...
大概是 87,233333333要是没有 S 高(
大概就这样了。祝好。不过还是一样菜。
10.16 成绩
S 组 85。
J 组 83,果真挂成傻逼。
分数线:S 是 46.5,J 是 50.5。
复习复赛了。
复习
没什么计划,反正这么菜。
不过会把做过的题目列举出来,尽量写题解。
Day 0
下午 3:00 的高铁。只带了手机,要不是要防疫连手机也不会带。
一个晚上就翻了翻模板题。
Day 1
J 组
早上没啥压力,当作为下午做准备了。
不过还是得认真考的。
进考场,是纯 NOI Linux。写了个 a + b,然后试了试对拍,没问题。
然后下载题目。
T1 直接切了。而且 $n$ 只有 $10^7$,连 long long
都不用考虑。
T2 一眼看上去简单的。于是写了一遍,发现读题错了。
但是这东西怎么维护来着...当时差点就上线段树了,但是才发现 $w\leq 600$,于是仍然是个水题,5min 切了。
不过出来后发现即使值域非常大也可以对顶堆。这东西全忘光了。
然而因为这里拖延,已经过去 1h。
T3 首先没什么思路,花了大概 30min 写了一个建树暴力。其中 !
的处理用了一点时间。
10:00。
然后看 T4。
这东西好像似曾相识。
想到两个顺序分别 DP 一遍,于是写了,然后大样例过不去,答案算大了。
尝试改,然后小样例就过不去了...怒而重写,发现了错误,开了三个 dp
数组,然后过了。
用去 1h。11:00。
回去检查前三题。拍了一下 T2 觉得很稳。
T4 倒没有拍。不过大样例小的可以。
想了一下 T3,然后暂时想不到。出来后就有思路了,对的。
其实考场上要是认真一点,是可以做出来的。
于是还有 30min 时,加文件。
???????
我 T4 代码呢???
变成乱码了???
不用想,肯定是编译时搞错了。就是 g++ number.cpp -o number.cpp -g -Wall
了。
但是还有 30min,不慌。
于是 5min 写回去了。测了样例,对的。
在此时竟然还发现,第一遍写的以为答案最大是 $10^3\times 10^4$ 不会爆,现在才发现是 $(10^3)^2\times 10^4=10^{10}$,于是加了 long long
,inf
改成 $10^{11}$。
真 tm 得感恩戴德。
剩下的时间就在检查。草草草 T1 的 power.in
写成 T4 的 number.in
了,我是 sb。
然后出来。当场估计是 100 + 100 + 30 + 100 = 330。
如果手速快一点,多一点梦想的话,说不定就阿克了。
中午
没干什么。睡觉没有睡着,也没有什么上午 T3,T4 的消息。
上午用 vim 时发现一个 tab
是 $8$ 个格,非常不舒服,忘了要 set
什么了。
查一下发现是 ts
,于是下午记着要改。
S 组
心情还不错,上午感受过了机子,不怎么慌。
于是开题。
T1 恶心日期糊我一脸,还记得有道日期题死也调不出来。没错,就是它。
于是略看下题,没看懂。
觉得有点爆炸,想着这次做出 T1 就不错了。
看后面的题,T2 比较奇怪,不知道 q
和 c
是干什么用的。不过好像很套路。
T3 和 T4 不抱什么希望。
于是决定对 T1 写一个一天一天加的暴力。然而就是让这个暴力过去样例就花了 1h。
但是好歹有了一点信心(,主要处理了这些东西:
- $0$ 年不存在;
- BC 的 $1,5,9$ 是闰年。
然后就去写 T2。显然每位独立,果然套路。
于是答案是 $2^x - n$ 了。
随便写了一个,然后过去了。
q
和 c
果然没用吗???
诈骗???
还有,$2^{64}$ 连 ull
也存不下。
怎么办?当然是 long double
了。
测了一下发现没有误差,好事。
怎么 printf
long double
来着,不管了
std::cout << std::fixed << std::setprecision(0)
虽然不清楚,但大概是这样用吧
但是觉得很玄,因为没有怎么做过这种有条件不用的诈骗题。
大概只用去了不到 20min。回去 T1。
首先用暴力找了一下 $1582.10.4$ 发现是喜闻乐见的常数 $2299160$,分了个段。
两边分别对于 $400$ 年和 $4$ 年循环模一下,然后一年一年加,然后一天一天加。
快了很多,但是大样例过不去了。发现有很多都是差个几天。
发现直到一年一年加之前都没错。于是懂了,今年是闰年不代表今年到下一年要加 $366$ 天。
于是加上了月日是否在 $2$ 月 $29$ 日前/后的一大串判断。然后过了。
拍了几千组,没问题。
算了下时间,循环模后最多还有 $400$ 年及 $365$ 天,$10^5\times(365+400)=76500000$,应该稳了。
此时已经过去 2h。
T2 还是不放心,于是根据题意写了个 $2^n$ 的暴力,拍了一下,对的。
重新检查。发现 T1 有一个拍炸了,是关于公元 $0$ 年的。还好,小问题。
2.5h,17:00,大概有 200pts。
T3 不会。于是当机立断,打了个暴力。正在写就开始头痛,不过不是很要紧。
T4 也不会,看起来可以搜,但实际上我也不会搜...于是浪费 20min 后写了 $n = 3$ 的 20pts。
差不多 18:00。不是很清楚。
感觉 T3 和 T4 查无可查,于是差不多到这时就把写好的全丢一边了。
类似于颓废地加文件。
还有部分分?不过应该写不完了。
剩下的时间里并没有干什么,也许的确是头痛的原因,没有做其它部分分的想法了。
出来后,直接上地铁,然后高铁,回家是 23:30。
睡了。大概是 100 + 100 + 20 + 20 = 240,大众分。
现在觉得不是没可能做出 T3 的。但是太颓废了。
Day 2
只有 luogu 的民间数据。
J 组民间数据
T4 意外地挂了 30pts,因为 $1$ 个 int
开小了,$1001$ 开到 $1002$ 就过了。wdnmd
T3 也应该要挂分的,不过 luogu 的小数据里没有。这里提到。
所以是 100 + 100 + 30 + 70 = 300,感觉不是很差,但也挺丢人的。
S 组民间数据
T1 过去了。不过还有一点疑问,就在这里。
由于和大家做法都不一样,挺慌的。
100 + 100 + 25 + 20 = 245。
Day 3
感觉 T1 有问题啊...
感觉那个帖子里说的 2 月 29 日的确有问题啊...
啊日期都是 1.1 和 10.15 吗(
那没事了(
Day 10 成绩
J 组 100 + 100 + 55 + 75 = 330
S 组 60 + 100 + 25 + 30 = 215
T1 在 luogu 上交过了,成为全场唯一被卡常的选手。/kk
除此以外和预期情况没差多少。
考场代码
留作纪念。
J 组
T1 power.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
const int BIT = 25;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int main() {
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
int n = read();
if(n & 1) return std::puts("-1"), 0;
for(int i = BIT;i >= 1;i--) {
if((n >> i) & 1) {
std::printf("%d ",1 << i);
}
}
std::puts("");
return 0;
}
因为上午 $8$ 格 tab,有点奇怪。
T2 live.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
const int N = 100001;
const int V = 601;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,w,a[N],b[V];
int main() {
freopen("live.in","r",stdin);
freopen("live.out","w",stdout);
n = read(), w = read();
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= n;i++) {
b[a[i]]++;
int l = std::max(1,i * w / 100), rk = 0;
for(int i = V - 1;i >= 0;i--) {
if(rk + b[i] >= l) {
std::printf("%d ",i);
break;
} else rk += b[i];
}
}
return 0;
}
T3 expr.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
const int N = 100001;
const int L = 1000001;
// -1 & // -2 | // -3 !
// 0 \n
inline int readx() {
int x = 0; char ch = getchar();
while(ch != 'x' && ch != '&' && ch != '|' && ch != '!' && ch != '\n') ch = getchar();
if(ch == '\n') return 0;
if(ch == '&') return -1;
if(ch == '|') return -2;
if(ch == '!') return -3;
ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x;
}
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,map[N],st[N],tot;
int s[L],rev[L],lc[L],rc[L],fa[L],cnt;
int res[L];
void Dfs(int x) {
if(!lc[x] && !rc[x]) return void(res[x] = s[x] ^ rev[x]);
Dfs(lc[x]), Dfs(rc[x]);
if(s[x] == -1) res[x] = res[lc[x]] & res[rc[x]];
if(s[x] == -2) res[x] = res[lc[x]] | res[rc[x]];
if(rev[x] == 1) res[x] ^= 1;
// std::printf("%d ",res[x]);
}
void Change(int x) {
res[map[x]] ^= 1;
int p = fa[map[x]];
while(p != st[tot]) {
if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
if(rev[p] == 1) res[p] ^= 1;
p = fa[p];
}
if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
if(rev[p] == 1) res[p] ^= 1;
return;
}
int main() {
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
int x;
while(true) {
x = readx();
if(!x) break;
if(x > 0) {
st[++tot] = map[x] = ++cnt;
} else if(x == -3) {
rev[st[tot]] = true;
} else {
int b = st[tot--];
int a = st[tot--];
s[++cnt] = x;
lc[cnt] = a, rc[cnt] = b;
fa[a] = cnt, fa[b] = cnt;
st[++tot] = cnt;
}
}
n = read();
for(int i = 1;i <= n;i++) s[map[i]] = read();
Dfs(st[tot]);
int q = read();
while(q--) {
int x = read();
Change(x);
std::printf("%d\n",res[st[tot]]);
Change(x);
}
// std::puts("");
return 0;
}
T4 number.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
typedef long long ll;
const int N = 1001;
const ll inf = 100000000000ll;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,m,a[N][N];
ll dp1[N][N],dp2[N][N],dp[N][N];
int main() {
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
n = read(), m = read();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
a[i][j] = read();
for(int i = 0;i <= n + 1;i++)
for(int j = 0;j <= m + 1;j++)
dp[i][j] = dp1[i][j] = dp2[i][j] = -inf;
dp[1][0] = 0;
for(int i = 1;i <= m;i++) {
for(int j = 1;j <= n;j++) dp1[j][i] = std::max(dp[j][i - 1],dp1[j - 1][i]) + a[j][i];
for(int j = n;j >= 1;j--) dp2[j][i] = std::max(dp[j][i - 1],dp2[j + 1][i]) + a[j][i];
for(int j = 1;j <= n;j++) dp[j][i] = std::max(dp1[j][i],dp2[j][i]);
}
std::printf("%lld\n",dp[n][m]);
return 0;
}
S 组
T1 julian.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
typedef long long ll;
const int Q = 100001;
inline ll read() {
ll x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int mon[13] = {0,31,0,31,30,31,30,31,31,30,31,30,31};
struct Date {
ll y, m, d;
Date() {}
Date(ll _y, ll _m, ll _d) :
y(_y), m(_m), d(_d) {}
friend bool operator <(const Date &x,const Date &y) {
if(x.y != y.y) return x.y < y.y;
if(x.m != y.m) return x.m < y.m;
return x.d < y.d;
}
friend bool operator ==(const Date &x,const Date &y) {
return x.y == y.y && x.m == y.m && x.d == y.d;
}
friend bool operator <=(const Date &x,const Date &y) {
return x < y || x == y;
}
int Run1() {
ll Y = y; if(y < 0) Y++;
Y = (Y % 400 + 400) % 400;
return !(Y % 4);
}
int Run2() {
ll Y = y; if(y < 0) Y++;
Y = (Y % 400 + 400) % 400;
return !(Y % 400) || (!(Y % 4) && Y % 100);
}
int Month1() {
if(m != 2) return mon[m];
if(Run1()) return 29;
else return 28;
}
int Month2() {
if(m != 2) return mon[m];
if(Run2()) return 29;
else return 28;
}
void NextDay() {
if(*this < Date(1582,10,4)) {
d++;
if(d > Month1()) d = 1, m++;
if(m > 12) {
m = 1;
if(y == -1) y = 1;
else y++;
}
} else if(*this == Date(1582,10,4)) {
*this = Date(1582,10,15);
} else {
d++;
if(d > Month2()) d = 1, m++;
if(m > 12) {
m = 1;
if(y == -1) y = 1;
else y++;
}
}
}
void print() {
if(y < 0) std::printf("%lld %lld %lld BC\n",d,m,-y);
else std::printf("%lld %lld %lld\n",d,m,y);
}
};
void AddY(ll &y,ll d) {
ll p = y; y += d;
if(p < 0 && y >= 0) y++;
}
void Solve1(Date now,ll r) {
const int L = 365 * 4 + 1;
AddY(now.y,r / L * 4);
r %= L;
while(r >= 366) {
if((now.Run1() && Date(0,now.m,now.d) <= Date(0,2,29)) ||
(Date(now.y + 1,now.m,now.d).Run1() && Date(0,2,29) < Date(0,now.m,now.d))) r -= 366;
else r -= 365;
AddY(now.y,1);
}
while(r--) now.NextDay();
now.print();
}
void Solve2(Date now,ll r) {
const int L = (365 * 4 + 1) * 100 - 3;
AddY(now.y,r / L * 400);
r %= L;
while(r >= 366) {
if((now.Run2() && Date(0,now.m,now.d) <= Date(0,2,29)) ||
(Date(now.y + 1,now.m,now.d).Run2() && Date(0,2,29) < Date(0,now.m,now.d))) r -= 366;
else r -= 365;
AddY(now.y,1);
}
while(r--) now.NextDay();
now.print();
}
int main() {
freopen("julian.in","r",stdin);
freopen("julian.out","w",stdout);
int q = read();
while(q--) {
ll r = read();
if(r <= 2299160) Solve1(Date(-4713,1,1),r);
else Solve2(Date(1582,10,15),r - 2299161);
}
return 0;
}
T2 zoo.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
typedef unsigned long long ull;
const int N = 1000001;
const int BIT = 64;
inline ull read() {
ull x = 0; bool f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,m,c,k,p[N],q[N],ocp[BIT];
ull a[N];
int main() {
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
n = read(), m = read(), c = read(), k = read();
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= m;i++) p[i] = read(), q[i] = read(), ocp[p[i]] = true;
long double ans = 1.0;
for(int i = 0;i < k;i++) {
int v = 0;
for(int j = 1;j <= n;j++) v |= (a[j] >> i) & 1;
if(v || (!v && !ocp[i])) ans *= 2.0;
}
std::cout << std::fixed << std::setprecision(0) << ans - n << std::endl;
return 0;
}
T3 call.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
const int N = 100001;
const int P = 998244353;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,a[N],m,t[N],p[N],v[N];
std::vector <int> g[N];
void Call(int i) {
if(t[i] == 1) a[p[i]] = (a[p[i]] + v[i]) % P;
else if(t[i] == 2)
for(int j = 1;j <= n;j++) a[j] = 1ll * a[j] * v[i] % P;
else {
for(int j = 0;j < p[i];j++)
Call(g[i][j]);
}
}
int main() {
freopen("call.in","r",stdin);
freopen("call.out","w",stdout);
n = read();
for(int i = 1;i <= n;i++) a[i] = read();
m = read();
for(int i = 1;i <= m;i++) {
t[i] = read();
if(t[i] == 1) p[i] = read(), v[i] = read();
if(t[i] == 2) v[i] = read();
if(t[i] == 3) {
p[i] = read();
for(int j = 1;j <= p[i];j++) g[i].push_back(read());
}
}
int Q = read();
while(Q--) {
int i = read();
Call(i);
}
for(int i = 1;i <= n;i++) std::printf("%d ",a[i]);
std::puts("");
return 0;
}
T4 snakes.cpp
:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath> #include <algorithm>
#include <cstdlib>
const int N = 1000001;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,a[N];
void Solve() {
int ans = 0;
if(a[3] - a[1] >= a[2]) ans = 1;
else ans = 3;
std::printf("%d\n",ans);
return;
}
int main() {
freopen("snakes.in","r",stdin);
freopen("snakes.out","w",stdout);
int t = read();
n = read();
for(int i = 1;i <= n;i++) a[i] = read();
Solve(), t--;
while(t--) {
int k = read();
while(k--) {
int x = read(), y = read();
a[x] = y;
}
Solve();
}
return 0;
}
这里不知道为什么两个 #include
间没有空行,不过编译只有 Warning
,这是好的。
评价
-
复习的全没考。T3 可以线段树合并?
那我什么也没说 -
J 组较去年比较简单。(大概)
-
S 的 T1 恶心人。自己做题量也远远不够。
-
全省 J 组和 S 组都只坐了一个机房,200 人左右。
-
学校方面服务满分,一个一个问你有没有上传代码。
-
想找 WYX 和 LHQ,结果没找到。
应该算是符合水平的成绩吧。
-
要有梦想,去猜正解。
-
要多打比赛,练手速。CF 不能用娱乐式的打法了。
NOIP 是啥,不知道。
如果真可以参加(想桃子),会开新坑。