Tokio Marine & Nichido Fire Insurance Programming Contest 2020 参赛日志&题解
ezoixx130
2020-06-14 09:03:08
## Final Result
打进前 $100$ 是不可能的。。。。
## 参赛日志
别问我为什么 $8$ 个月没打 Atcoder ，突然回来打了，问就是被人叫去打的。
开场 $5$ 分钟都没有加载好题面，凉凉。
A 送分。
B 也是显然的。
C 想了 $15$ 分钟没有发现这个序列操作的实际意义，但是在纸上手玩了一下突然发现这个序列增长的很快，然后就证出来一定在 $log_2n$ 次以内变成不变的状态，最后推一推怎么在 $O(n)$ 时间复杂度内做一次操作，然后写个暴力模拟就好了。
D 很久没有思路。。。。后来发现折半一下，复杂度 $O(10^5\times 2^9\times 9)$ 好像有点玄？看到时限 $3\text{s}$ 就硬着写了一发，然后 $2572 \text{ms}$ 过了。。。。
（后来发现复杂度里面这个 $9$ 是很好去掉的。。。不过过了就没管）
## 题解
### A
要在这个字符串里选长度为 $3$ 的字串，就直接选前 $3$ 个字符就好了。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
cout << s[0] << s[1] << s[2];
}
```
### B
两个人都做最优决策，那就一定是同向跑，变成一个追及问题，判断速度差乘时间有没有超过位置差就好了。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long a,v,b,w,t;
cin >> a >> v >> b >> w >> t;
if(a==b || (v-w)*t>=abs(a-b))puts("YES");
else puts("NO");
}
```
### C
首先第一次操作后所有位置一定非零，考虑后面每次操作之后第一个数一定至少翻倍，中间的数增长一定比第一个数快，所以在 $log_2n$ 次操作内就一定会变成全是 $n$ 的情况，模拟这 $log_2n$ 次操作即可。
用差分然后前缀和的思想可以在 $O(n)$ 的时间复杂度内模拟一次操作，所以最后的时间复杂度为 $O(n\times log_2n)$ 。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200010
int n,k,a[MAXN],b[MAXN];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int cnt=1;cnt<=k;++cnt)
{
for(int i=1;i<=n;++i)b[i]=0;
for(int i=1;i<=n;++i)
{
int l=max(i-a[i],1),r=min(i+a[i],n);
++b[l];
--b[r+1];
}
long long sum=0;
for(int i=1;i<=n;++i)sum+=(a[i]=a[i-1]+b[i]);
if(sum==(long long)n*n)break;
}
for(int i=1;i<=n;++i)printf("%d ",a[i]);
}
```
### D
直接的想法是每个点预处理好每个 $f_{i,j}$ 值代表 $i$ 号点容量为 $j$ 时的最大价值，但是这样做空间复杂度是 $O(n\times max\{w_i\})$ 的，显然无法承受。
考虑折半，预处理好这棵树前 $9$ 层的 $f$ 的值，每次询问时先找到这个预处理好的 $f$ ，剩下的物品暴力枚举是否加入背包即可。
时间复杂度：$O(2^9\times 10^5+10^5\times 2^9\times 9)$，空间复杂度：$O(2^9\times 10^5)$。
略加优化易将时间复杂度优化为 $O(2^9\times 10^5+10^5\times 2^9)$，鉴于我过了就没写……
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 300000
int n,v[MAXN],w[MAXN],fa[MAXN],f[513][100010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",v+i,w+i);
fa[i]=i/2;
}
for(int i=1;i<512;++i)
{
for(int j=1;j<w[i];++j)f[i][j]=f[fa[i]][j];
for(int j=w[i];j<=100000;++j)f[i][j]=max(f[fa[i]][j],f[fa[i]][j-w[i]]+v[i]);
}
int q;
scanf("%d",&q);
while(q--)
{
int x,l;
scanf("%d%d",&x,&l);
if(x<512)
{
printf("%d\n",f[x][l]);
continue;
}
vector<pair<int,int> > bps;
while(x>=512)
{
bps.push_back(make_pair(v[x],w[x]));
x=fa[x];
}
int cnt=bps.size(),ans=0;
for(int i=0;i<(1<<cnt);++i)
{
int totw=0,totv=0;
for(int j=0;j<cnt;++j)
{
if(!((i>>j)&1))continue;
totv+=bps[j].first;
totw+=bps[j].second;
}
if(totw<=l)ans=max(ans,f[x][l-totw]+totv);
}
printf("%d\n",ans);
}
}
```
### E
会了就来写。
### F
会了就来写。