还未写完！！！！
还在更新ing！！！！
前言
此乃小 Oler 的一篇比赛游记，从今日后，还会进行详细的修订。
注明：由于特殊原因，不能在考完试当天写下游记，深感遗憾。
考试前夜
“最后一晚了，背背模板”
背完若干模板...（考场上一个都没用到）
“早睡养精神，不行，必须熬夜，看看 NBA 勇士的新闻日先...”
\(10:00\) 关灯睡觉了好吧。
考试当天
早上 morning
正常起床，精神不错，浅浅发个动态“++RP”。
早餐，一碗面和八个饺子，嘴里喝着瓶奶就前往 smzx 考点，感觉风挺大的。
到了考点，只见 dalao myz 早已等候多时，便谁便聊起今年题目大概难度。
接着，各路 dalao 陆续到达，such as ljs , xzk , zsw , hk , lsy , yyh ...
和dalao们互相寒暄几句就进入试室。
普及组
\(8:27\) 解压文件夹，直接看题。
\(8:30\) 考试正式开始，当时做题顺序为 \(T1-T2-T4-T3\)。
T1 apple
做题时间段：\(8:30-9:00\)
所用时：约 \(30\) \(min\)
签到题必须拿下的好吧，第一眼按照做题思路，大概规律题，\(20\) \(min\) 没找出规律，看一眼时间，想先打个暴力再看，打完后发现可以直接过，复杂度竟然为 \(O(log_3 n)\)，大样例也水过了，赶紧润。
考试期望值：\(+100pts\)
估分实际值：\(+100pts\)
T2 road
做题时间段：\(9:00-9:40\)
所用时：约 \(40\) \(min\)
看了题目像DP或贪心，再看数据范围 \(1e5\)，暂时想不到怎么定义状态，就先放下DP，去想贪心。
我的贪心很简单想，边走边取最小值，然后计算其贡献，最后相加就行了，\(10\) \(min\) 打完。
这时候有趣的事情出现了，我按照题目顺序取大数据根本没注意题目的名字，取到了 bus 的大数据，绞尽脑汁调了 \(30\) \(min\) 才发现拿错了，怪不得找不出错...拿回原来的大数据，轻松就过了，时间复杂度为 \(O(n^2)\)，为时不多了，赶紧润润润。
期望值：\(+100pts\)
估分实际值：\(+50pts/90pts\)
T3 uqe
做题时间段：\(10:30-11:57\)
所用时：约 \(90\) \(min\)
大模拟题，于是放到最后做，这时还剩 \(1h30min\)，安心做题，慢慢地按照题目打，打完还剩 \(10\) \(min\)，测试样例，结果错了几个，当我发现问题时，已经是 \(11:54\) 了，由于是 \(11:57\) 停止答题，只剩 \(3\) \(min\)，心里慌得一批，改了一半，只能把半成品交了上去。
期望值：\(+50pts\)
估分实际值：\(+10pts\)
T4 bus
做题时间段：\(9:40-10:30\)
所用时：约 \(60\) \(min\)
考前估最后一题会是DP题，结果出了道最短路，当时第一反应是找出性质，再用 dijkstra 跑个最短路，我也找出了一小点的性质，就是所走的路径长度必须为 \(k\) 的倍数，可惜当时没有想到可以用分层图，随便打了个bfs暴力就润去做 T3。
期望值：\(+10pts\)
估分实际值：\(0pts\)
出了考场，脑子一片空白，听说很多大佬都做出了 \(3\) 题，myz和xzk都做完了（意料之中）。
而我这个蒟蒻只做了两题，第 \(3\) 题生死未卜...（自卑了）
中午 noon
在 smzx 食堂随便吃了午饭，和众dalao讨论，这才发现考试时没时间忘了新建文本文档和启动 NOI Linux 了，祭！
心态崩溃，回到阶梯室休息，幸亏有以前比赛的经验，也没多想，安稳入睡。
下午 afternoon
\(1:40\) 被叫醒，一脸朦胧上楼，还不能进考场，还有些时间，醒醒神，顺便膜拜 dalao，沾沾欧气。
\(2:05\) 进考场，坐在座位上向众神祈祷，回应我的只有...
提高组
上午考砸了，这一年的努力就靠这最后一场了，背水一战...
\(2:30\) 提高考试开始。
复原当时做题顺序为 \(T1-T2-T3-T4\)，比较佛系的顺序...
T1 lock
做题时间段：\(2:30-3:00\)
所用时：约 \(30\) \(min\)
一开始认为第一题不会太过于简单，但又是第一题，也是要认真拿下的好吧，拿起草稿纸直接开始找性质，找半天发现数据范围 \(n\le 8\)，而且密码锁只有五位，可以暴搜啊，一打还真可以，过来所有的样例，心里嘀咕着，咋还比普及 T1 还简单？（虽然我都因把题目想复杂而浪费时间了）
期望值：\(+100pts\)
估分实际值：\(+100pts\)
小插曲 I
T3题目样例解释有勘误，改正...（可惜我没怎么注意）
T2 game
做题时间段：\(3:00-3:20\)
所用时：约 \(20\) \(min\)
一眼盯真，有点像zsq总喜欢出的蓝题消融——区间DP，一看数据又把我吓了一跳，\(n\le 2\times 10^5\)，这区间DP最多蹭个 \(35\) 分，看看还有没有其他方法。
突然想起考试前几天刷题时才看到大佬总结区间的题目可以先设 \(f_i\) 为开头或结尾定义状态，再浅浅结合题目，显然可以用 \(last_i\) 记录当前字符 \(i\) 其前面最后出现的位置，然后用栈维护，其实想到这时再坚持想想优化就可以对了，但当时脑子一傻，想不到怎么优化（失算了），只好打个 \(O(n^2)\)，水个 \(50\) 分算了，程序很简单，\(10\) \(min\) 解决，然后就不管这题了，润润润。
期望值：\(+50pts\)
估分实际值：\(+50pts\)
T3 struct
做题时间段：\(3:20-4:55\)
所用时：约 \(100\) \(min\)
对于我来说的毒瘤大模拟，由于时间充足，所以想尽可能拿高分，开始时是直奔正解的，结果做了 \(40\) \(min\)，我又不会了，一看特殊性质ABCD，好像把我打的程序改改后，正好都可以拿下，于是就转换方向，去考虑特殊性质，改了 大约 \(45\) \(min\)，官方没有给出特殊性质的数据，只好自己做数据，用了 \(10\) \(min\) 就都过了，信心满满...可我忽视了一个很大的问题，就是考试时的题目有误，这边考场也是在开考后便立刻更改了勘误，而那时我在啃T1，后来也没多注意，也没怎么认真审题，按照样例解释打，最后导致爆 \(0\)，哭死...
期望值：\(+80pts\)
估分实际值：\(0pts\)
自我感觉如果按照原来样例解释，这题起码都有四五十分，痛哭o(╥﹏╥)o
小插曲 II
时间段：\(4:55-5:05\)
所用时：约 \(10\) \(min\)
看着还剩一些时间到 \(5\) 点整，有了上午的经验，再加上中午请教 dalao，于是启动 NOI Linux，顺便写了个信息的文本文档，心里安稳些。
OK呀，NOI Linux上前三题程序都没有语法问题，那就赶紧去润T4。
T4 tree
做题时间段：\(5:05-6:27\)
所用时：约 \(90\) \(min\)
赛后总结
普及J
提高S
大总结
番外
还原考试程序
此部分可跳过，后面有蒟蒻写的题解。
注明：取自考试压缩包，没有删改痕迹...
普及组 160pts/200pts
提高组 150pts
T1 lock 100pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[11],ans;
int s[11][6];
void dfs(int cnt) {
if(cnt>5) {
for(int i=1;i<=n;i++) {
int p=0;
for(int j=1;j<=5;j++) {
if(s[i][j]!=a[j]) {
if(p==1) {
if(s[i][j-1]!=a[j-1]) {
if((s[i][j-1]-a[j-1]+10)%10!=(s[i][j]-a[j]+10)%10)
return ;
} else return ;
}
p++;
if(p>2) return ;
}
}
if(p==0) return ;
}
ans++;
return ;
}
for(int i=0;i<=9;i++) {
a[cnt]=i;
dfs(cnt+1);
}
}
signed main() {
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {
s[i][0]=-1;
for(int j=1;j<=5;j++)
cin>>s[i][j];
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
T2 game 50pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo=0x3f3f3f3f;
const int N=1e5+10;
int n,f[N],last[30];
int stk[N],top,ans;
string s;
signed main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
getline(cin,s);
int len=s.size();
for(int i=0;i<len;i++) {
if(s[i]>='0'&&s[i]<='9')
n=n*10+(s[i]-'0');
}
getline(cin,s);
len=s.size();
for(int i=0;i<=26;i++)
last[i]=oo;
for(int i=0;i<n;i++) {
if(last[s[i]-'a']!=oo) {
string w="";
top=0;
for(int j=last[s[i]-'a'];j<=n;j++) {
w+=s[j];
if(top&&s[j]==stk[top])
top--;
else stk[++top]=s[j];
if(top==0&&w!="")
ans++;
}
}
last[s[i]-'a']=i;
}
printf("%lld\n",ans);
return 0;
}
T3 struct 0pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1001;
int n,op,k,pos=1;
int maxv[N];
string s,t,a;
map<string,int> mp;
//map<string,int> mp3;
map<string,int> mp2;
map<int,string> mp4;
vector<string> vec[N];
int Vnum;
signed main() {
freopen("struct.in","r",stdin);
freopen("struct.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) {
cin>>op;
if(op==1) {
cin>>s>>k;
int maxx=0;
++Vnum;
vec[Vnum].push_back(s);
for(int j=1;j<=k;j++) {
cin>>t>>a;
if(t=="byte") {
maxx=max(1ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="short") {
maxx=max(2ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="int") {
maxx=max(4ll,maxx);
vec[Vnum].push_back(a);
} else {
if(t=="long") {
maxx=max(8ll,maxx);
vec[Vnum].push_back(a);
} else {
maxx=max(maxv[mp[t]],maxx);
vec[Vnum].push_back(a);
}
}
}
}
}
mp[s]=Vnum;
maxv[Vnum]=maxx;
}
if(op==2) {
cin>>t>>s;
if(t=="byte") {
mp2[s]=pos;
mp4[pos]=s;
pos++;
} else {
if(t=="short"){
mp2[s]=pos;
for(int j=pos;j<=pos+1;j++)
mp4[j]=s;
pos+=2;
} else {
if(t=="int") {
mp2[s]=pos;
for(int j=pos;j<=pos+3;j++)
mp4[j]=s;
pos+=4;
} else {
if(t=="long") {
mp2[s]=pos;
for(int j=pos;j<=pos+7;j++)
mp4[j]=s;
pos+=8;
} else {
int p=mp[t];
int len=vec[p].size();
int maxx=maxv[p];
for(int j=1;j<len;j++) {
mp2[s+'.'+vec[p][j]]=pos;
for(int ll=pos;ll<=pos+maxx-1;ll++)
mp4[ll]=s+'.'+ vec[p][j];
pos+=maxx;
}
}
}
}
}
}
if(op==3) {
cin>>s;
printf("%lld\n",mp2[s]-1);
}
if(op==4) {
cin>>k;
if(mp4[k+1]=="") printf("ERR\n");
else cout<<mp4[k+1]<<"\n";
}
}
return 0;
}
T4 tree 0pts
#include<bits/stdc++.h>
#define int long long
#define M(x,y) make_pair(x,y)
using namespace std;
typedef pair<int,int> pll;
const int N=1e5+10;
int n,x,y,a[N],b[N],c[N];
struct Node {
int to,nxt;
Node() {
to=nxt=0;
}
Node(int a,int b) {
to=a;
nxt=b;
}
} adj[N];
struct Tree {
int val,id;
} t[N];
int head[N],idx;
int dep[N],maxx[N];
int ans,w=0;
priority_queue<pll,vector<pll>,less<pll> > heap;
inline void add(int x,int y) {
adj[++idx]=Node(y,head[x]);
head[x]=idx;
}
void dfs(int u,int fa) {
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
dfs(v,u);
}
}
void dfs2(int u,int fa) {
maxx[u]=t[u].val;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
dfs2(v,u);
maxx[u]=max(maxx[u],maxx[v]);
}
}
void dfs3() {
heap.push(M(t[1].val,1));
while(!heap.empty()) {
pll k=heap.top();
heap.pop();
int u=k.second;
int distance=k.first;
for(int i=head[u];i;i=adj[i].nxt) {
int v=adj[i].to;
w++;
ans=max(ans,t[v].val-dep[u]+w-1);
// cout<<w<<" "<<v<<" "<<t[v].val-dep[u]+w-1<<"\n";
heap.push(M(t[v].val,v));
}
}
}
signed main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
int cnt=0;
bool flag=1;
for(int i=1;i<n;i++) {
scanf("%lld%lld",&x,&y);
if(y-x!=1) flag=0;
if(x==1) cnt++;
add(x,y);
}
if(flag) {
// cout<<n<<"\n";
int day=0,maxx=0;
for(int i=1;i<=n;i++) {
day++;
if(c[i]>0) {
int s=b[i]+c[i];
int m=a[i];
int g=c[i];
int ret=0;
if(g!=0) ret=(m-s-1)/g+1;
else ret=(m-s-1)+1;
if(ret*g<a[i]) ret++;
maxx=max(day+ret,maxx);
} else {
int ret=0,pp=0;
for(int j=1;;j++) {
ret+=max(1ll,b[i]+j*c[i]);
if(ret>=a[i]) {
pp=j;
break;
}
}
maxx=max(day+pp,maxx);
}
}
printf("%lld\n",maxx);
} else {
if(cnt==n-1) {
for(int i=2;i<=n;i++) {
if(c[i]>=0) {
t[i].val=111;
t[i].id=i;
} else ;
}
} else {
// cout<<111111<<"\n";
dfs(1,0);
for(int i=1;i<=n;i++) {
t[i].val=dep[i]+(a[i]-1)/b[i]+1;
t[i].id=i;
// cout<<t[i].val<<" ";
}
// cout<<"\n";
dfs2(1,0);
dfs3();
printf("%lld\n",ans);
}
}
return 0;
}
/*
4
5 1 0
8 2 0
3 1 0
11 2 0
1 2
1 3
3 4
*/