前言
没有前言。
Day 0
上午听完校际交流最后一节课，下午 2 点出发去 nj。
在车上和两位巨佬先讨论了一些之前的题目。
然后看到 nj 地铁，某位巨佬想要出一个图论题。
一开始是这样的：给一个无向图，一开始你有一定的体力，你可以步行走过一些边，会消耗体力，也可以坐地铁，不消耗体力，但是会花钱。如果你体力不足，可以花钱补充体力，问从一个点到另一个点最少花多少钱。
后来变成了这样：给一个无向图，一开始你有一定的体力，你可以步行走过一些边，会消耗体力，也可以坐地铁，不消耗体力，但是会花钱。有一些关键点，如果你经过关键点，可以花钱补充体力。你有一次“锁血”的机会，可以保证你的体力在某段路径上在某个值不变。问从一个点到另一个点最少花多少钱。
什么拼接题（）
然后南外给的胸牌就是一个纸片，上面写了“2023暑期信息竞赛集训”，我甚至不知道该写什么，逆天。
后来看同学的博客，听说是 IOI 赛制，好耶！
虽然还是可能爆 0，但至少不会莫名挂分了。
Day 1
总体情况
1000+1200+1400+1600+1800+1575=8575，rk65
总体来说感觉虽然开题晚一点点但是前面做起来非常顺利，后面可能有一些懈怠了，不想思考导致排名掉了很多。主要是 T6 ，再多想想就可以多拿不少分。
T1
发现可以使用U盘，于是找到了快读板子放到缺省源里面，因此比别人晚开题大概 2min。
开 T1，第一遍没过样例，被吓到了。后来发现排序反了，改了一下，过了。
就是先排序，然后看有多少人可以替换第四名。
然而到最后都没有发现题目已经帮我们排好序了
反正 6 人中仅有 lx 在赛后发现
T2
开 T2，发现比 T1 简单。一个伞直接看为一个 \(2\cdot d+1\) 的区间，用 \(n\) 除以它上取整。写了 2min。一遍过。
T3
开 T3，发现显然 \(d\) 的值为所有要走的距离的最大公约数。写了 3-4min，一遍过。
T4
开 T4，一开始没看数据范围，感觉很难……后来发现 \(n\leq 8\)，如果搜索操作 3，最多 5 层，不会超时。但是搜操作 1，2 就可能不行。
然后发现也许操作一二不需要搜索，在合并前加和合并后加等价，所以就把所有操作一二放在三后面。然后打了一个很暴力的 \(O(n!\cdot n^3)\) （大概是这个复杂度,那个 \(O(n^3)\) 是暴力计算操作一二的。
写了 15min，一遍过。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x==0){
putchar('0'); return ;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
template<typename T> inline void read(T &x){
x=0; int w=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1; ch=getchar();
}
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=w; return ;
}
}
using namespace IO;
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),putchar('\n')
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 100010
#define int long long
int n,l[maxn],a,b,c,ans;
bool cmp(int x,int y){return x>y;}
void dfs(int m){
if(m>=3){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k){
if(i==j||j==k||i==k) continue;
if(!l[i]||!l[j]||!l[k]) continue;
ans=min(ans,abs(l[i]-a)+abs(l[j]-b)+abs(l[k]-c)+10*(n-m));
}
if(m==3) return ;
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
if(!l[i]||!l[j]) continue;
int t1=l[i],t2=l[j];
l[i]=t1+t2; l[j]=0;
dfs(m-1); l[i]=t1,l[j]=t2;
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
read(n); read(a); read(b); read(c);
for(int i=1;i<=n;++i) read(l[i]);
sort(l+1,l+n+1,cmp);
ans=inf; dfs(n); writeln(ans);
return 0;
}
T5
开 T5，有一个显然的 \(O(n^6)\) 做法，先写了，+1440。
然后算了一下值域。由于本人算无能，算成了 \(100\times 100 \times 1000=10^8\) ,认为直接开会 MLE。在这里耗时约 30min。
看榜，发现好多人切了 T5，T6还写了很多部分分。
他们怎么都这么强啊.jpg
然后去想 T6 了。
后来想到 map 这种神奇的东西，用了，但是 \(O(n^4\cdot \log n)\) 超时了。
重新计算一遍，发现是 \(10^7\) ，于是果断开数组存可能的值。
然而忘了处理负数，又 WA 了一发，然后使用数组的时候每个数加上一个 \(10^7\) ,过了。（还好是 IOI 赛制
就是枚举两个矩形的交点，分左上右下和左下右上两种情况。
先枚举左上所有值，存到数组里，然后枚举右下所有值，如果和左上重复就加上贡献。
左下右上做法相似。
至于清空，再用加进来的方式把加上的都减掉就行了。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x==0){
putchar('0'); return ;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
template<typename T> inline void read(T &x){
x=0; int w=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1; ch=getchar();
}
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=w; return ;
}
}
using namespace IO;
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),putchar('\n')
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 110
int n,a[maxn][maxn],ans,h[20000010],t;
map<int,int> mp;
int calc(int x1,int yy1,int x2,int y2){
return a[x2][y2]-a[x1-1][y2]-a[x2][yy1-1]+a[x1-1][yy1-1];
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
read(n); ans=0; t=10000000;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) read(a[i][j]);
for(int i=1;i<=n;++i)
for(int j=2;j<=n;++j) a[i][j]+=a[i][j-1];
for(int i=1;i<=n;++i)
for(int j=2;j<=n;++j) a[j][i]+=a[j-1][i];
for(int k=1;k<n;++k)
for(int l=1;l<n;++l){
for(int i=1;i<=k;++i)
for(int j=1;j<=l;++j) ++h[calc(i,j,k,l)+t];
for(int i=k+1;i<=n;++i)
for(int j=l+1;j<=n;++j) ans+=h[calc(k+1,l+1,i,j)+t];
for(int i=1;i<=k;++i)
for(int j=1;j<=l;++j) --h[calc(i,j,k,l)+t];
for(int i=k+1;i<=n;++i)
for(int j=1;j<=l;++j) ++h[calc(k+1,j,i,l)+t];
for(int i=1;i<=k;++i)
for(int j=l+1;j<=n;++j) ans+=h[calc(i,l+1,k,j)+t];
for(int i=k+1;i<=n;++i)
for(int j=1;j<=l;++j) --h[calc(k+1,j,i,l)+t];
}
writeln(ans);
return 0;
}
T6
先打了一个假贪心，每次选票数大于1号的票中的最小值，+1155，很满意于是回去想 T5.
过了 T5 之后回来想 T6，浪费了很多时间之后，发现每次选择并不是一定要选票数比1号多的。于是又打了一个假贪心，+1575，75/100，但是 TLE。
此时还剩不到 10min。
发现第二个假贪心的时间可以写成 \(O(n^2)\) 的，但是没时间写了。后来好像这样写能拿 85。
但是从头到尾都觉得这题正解是 dp。
事实上是贪心。
发现 1 号投谁其实都无所谓，因为首先一号完全领先至少有 2 票，所以剩余的一定至少有一个 0，只要把票投给那个 0 票的人就行了，
枚举最终状态，最终 1 号得到多少票，然后把票数大于一号得票的人，多出的票先去掉，然后再从剩下的中找最小的使1号的票到达枚举的值。
这样计算出的所有答案取 \(\min\)。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x==0){
putchar('0'); return ;
}
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
template<typename T> inline void read(T &x){
x=0; int w=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1; ch=getchar();
}
while(isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=w; return ;
}
}
using namespace IO;
#define writesp(x) write(x),putchar(' ')
#define writeln(x) write(x),putchar('\n')
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 2010
#define int long long
int n,a[maxn],s[maxn],t[maxn],flg,res,ans;
priority_queue<int,vector<int>,greater<int> > q[maxn],pq;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
read(n); ans=inf;
for(int i=2;i<=n;++i) read(a[i]);
for(int i=2;i<=n;++i) read(s[i]);
for(int i=n-1;i>=1;--i){
for(int j=1;j<=n;++j){
t[j]=0;
while(q[j].size()) q[j].pop();
}
res=0;
for(int j=2;j<=n;++j) q[a[j]].push(s[j]);
for(int j=2;j<=n;++j) ++t[a[j]];
for(int j=2;j<=n;++j){
while(t[j]>=i){
--t[j]; ++t[1]; res+=q[j].top(); q[j].pop();
}
while(t[j]){
--t[j]; pq.push(q[j].top()); q[j].pop();
}
}
while(t[1]<i){
++t[1]; res+=pq.top(); pq.pop();
}
ans=min(ans,res);
while(pq.size()) pq.pop();
}
writeln(ans);
return 0;
}
T7
当时在考场上感觉没什么人过，所以就没写。后来发现有一些部分分是比较好写的。
有没有一种可能，我对链并且只有三种颜色的有思路，但是这两个拆成两个部分分我就不会了。
我怎么这么弱啊.jpg
考虑计算每种颜色贡献，对于每种颜色计算包含它的路径数量。
但是这样还是不太好算。但是发现计算不包含某种颜色的路径数量是好算的。即某一块中不包含这种颜色，大小为 \(sz\)，路径数为 \(\frac{sz\times (sz-1)}{2}\)。
然后发现每个点会影响离它最近的祖先，所以 dfs，记录对于每种颜色记录搜到的当前点离他最近的祖先，然后从祖先里面刨去同色点的子树大小，这一团东西里面选起点终点的方案数。
代码实现细节有一点点多，\(dfs\) 稍有些复杂，还有别忘了把上面没有祖先与他同色的点贡献减掉。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 200010
#define pb emplace_back
#define int long long
using namespace std;
int T=0,n,m,x,y,c[maxn],sz[maxn],ans,lst[maxn],d[maxn],top[maxn],f[maxn];
vector<int> g[maxn];
void clear(int n){
m=ans=0;
memset(sz,0,sizeof(sz));
memset(lst,0,sizeof(lst));
memset(top,0,sizeof(top));
memset(f,0,sizeof(f));
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i) g[i].clear();
}
int calc(int x){return x*(x-1)/2;}
void dfs(int x,int fa){
int tmp=lst[c[x]]; lst[c[x]]=x;
sz[x]=1; d[x]=0;
for(int i=0;i<g[x].size();++i){
int y=g[x][i];
if(y==fa) continue;
dfs(y,x); sz[x]+=sz[y];
ans-=calc(sz[y]-d[x]); d[x]=0;
}
lst[c[x]]=tmp;
if(tmp) d[lst[c[x]]]+=sz[x];
else top[c[x]]+=sz[x];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while(cin>>n){
clear(n); ++T;
for(int i=1;i<=n;++i){
cin>>c[i];
if(!f[c[i]]) ++m,f[c[i]]=1;
}
for(int i=1;i<n;++i){
cin>>x>>y;
g[x].pb(y); g[y].pb(x);
}
ans=calc(n)*m; dfs(1,0);
for(int i=1;i<=n;++i)
if(f[c[i]])
ans-=calc(n-top[c[i]]),f[c[i]]=0;
cout<<"Case #"<<T<<": "<<ans<<endl;
}
return 0;
}
T8
其他
讲课的时候老师讲了一些比较好笑的错误。
比如：在某个循环里面使用 memset 清空一个完整的大数组，还有 #define maxn 100000+5 然后 int a[maxn*2] 这种。
虽然觉得很好笑，但感觉像是我会干出来的事。（不如我的 lca 好笑。
中午在南外转了一圈，机房楼上面有一面墙，墙上是一个树形结构列出了很多算法。有不少是学过了忘了的，还有根本没见过的。
去二楼玩了一些物理实验器材，三楼看了生物标本，回机房休息。本来想写游记，发现中午是不开网的，是能上 OJ。困，下午再订正吧。
下午开网了。订正，但看不到自己提交的代码，并且上午写的我还没保存。晚上回家就看得到了。
OJ 上放了讲评视频，然而我没有耳机，只能看看图，很抽象。
晚上五点放学，本校 7 人调 T7 代码赖到 6 点。
前三题感觉简单，没必要放代码，就没放。