-
vp 情况：过了 A 到 E，F 没时间也不会。
-
vp 总结：
ABC 表现可以。
D 慢了一点，写之前大概考虑清楚每个变量或函数的意义，结构明晰才能更快的写出代码。
E 花的时间太长，原因是想偏了以及没有着重考虑异或的解法，以后见到有关位运算的题。想：按位讨论、dp、字典树、线性基等。
还有一个重点就是开
long long的情况下一定要注意1ll的使用。
ABC 太简单了就不写题解了。
ABC201D Game in Momotetsu World
一看到这题就想到了记忆化搜索，是一道练习该算法不错的题。
int dfs(int x,int y,bool z) 表示当前在 \((x,y)\)，该先手 \(0\) 还是后手 \(1\) 走，到 \((n,m)\) 的结果。
在先手走时，我们的答案加上该点贡献并且取 \(\max\)；在后手走时，我们的答案减去该店贡献并且取 \(\min\)。最后只需要判断 \(f[1][1][0]\) 与 \(0\) 的关系即可。
代码（保证简洁性去掉了快读）：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+5;
int n,m,f[N][N][2];
char a[N][N];
int dfs(int x,int y,bool z){
if(f[x][y][z]!=1e9)return f[x][y][z];
if(x==n&&y==m)return 0;
int tmp,tmpp;
if(x==n){
if(a[x][y+1]=='-')tmp=-1;
else tmp=1;
if(!z)return f[x][y][z]=dfs(x,y+1,z^1)+tmp;
else return f[x][y][z]=dfs(x,y+1,z^1)-tmp;
}else if(y==m){
if(a[x+1][y]=='-')tmp=-1;
else tmp=1;
if(!z)return f[x][y][z]=dfs(x+1,y,z^1)+tmp;
else return f[x][y][z]=dfs(x+1,y,z^1)-tmp;
}
if(a[x+1][y]=='-')tmp=-1;
else tmp=1;
if(a[x][y+1]=='-')tmpp=-1;
else tmpp=1;
if(!z)return f[x][y][z]=max(dfs(x+1,y,z^1)+tmp,dfs(x,y+1,z^1)+tmpp);
else return f[x][y][z]=min(dfs(x+1,y,z^1)-tmp,dfs(x,y+1,z^1)-tmpp);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>a[i][j];
f[i][j][0]=f[i][j][1]=1e9;
}
}
int ans=dfs(1,1,0);
if(ans>0)puts("Takahashi");
else if(ans<0)puts("Aoki");
else puts("Draw");
return 0;
}
ABC201E Xor Distances
考虑以 \(1\) 为根，记 \(f[i]\) 为 \(1\sim i\) 的路径上边的异或和。
所以 \(\mathrm{dist}(i,j)=f[i]\ \mathrm{xor}\ f[j]\)，答案即为：
\[\sum_{i=1}^n\sum_{j=i+1}^n f[i]\ \mathrm{xor}\ f[j] \]考虑异或的常见解决方式，按位拆开讨论贡献。
记 \(num0[j],num1[j]\) 分别为 \(f[i]\) 二进制下的 \(0/1\) 个数，则第 \(j\) 位对答案的贡献是 \(2^j\times num0[j]\times num1[j]\)，求和即可。
- 开
long long的时候写 \(1\) 一定要写成1ll！！！
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=1e9+7;
int n,head[N],cnt;
struct node{
int next,to,w;
}e[N<<1];
void add(int from,int to,int w){
e[++cnt]=(node){head[from],to,w};
head[from]=cnt;
}
int f[N],num0[70],num1[70];
void dfs(int x,int fa){
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(y==fa)continue;
f[y]=f[x]^e[i].w;
dfs(y,x);
}
}
signed main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
dfs(1,0);
for(int i=1;i<=n;++i){
for(int j=0;j<60;++j){
if(f[i]&(1ll<<j))num1[j]++;
else num0[j]++;
}
}
int ans=0;
for(int i=0;i<60;++i){
int tmp=num0[i]*num1[i]%mod;
ans=(ans+(1ll<<i)%mod*tmp%mod)%mod;
}
print(ans);
return 0;
}
ABC201F Insertion Sort
一眼 dp，那么怎么写呢？
显然，一个位置最多操作一次，并且不可能每个位置都操作一次。
首先我们考虑最暴力的方法，将其转化为判定性问题，每个数字显然有 \(4\) 种情况可选：去任意一个位置，去最左边，去最右边，或者不动。这是 \(O(4^nn)\) 级别的巨无霸算法。
动，或不动。
我们不考虑在排列上搞，这样很乱并且没有什么特殊性质，我们在考虑每个数的值，因为排序在意的是值的递增，这样在某种意义上消除了后效性。
记最终答案的每个数状态 \(S=\{s_1,s_2,\cdots,s_n\}\)，显然这个不动很特殊，我们考虑如果一些点不使用操作会怎样。记 \(T=\{t_1,t_2,\cdots,t_k\}\) 表示值 \(t_i\) 不进行操作，则有以下结论：
- \(1\leq j<t_1\)，代价为 \(\min(a_j,b_j)\)；
- \(t_i<j<t_{i+1}\)，代价为 \(a_j\)（使用其他操作会越过不动的位置）；
- \(t_k<j\leq n\)，代价为 \(\min(a_j,c_j)\)。
。以它为状态：记 \(f[i]\) 为将值 \(1\sim i\) 的位置排好并且 \(i\) 不使用操作所需要的最小代价，\(pos[i]\) 表示值为 \(i\) 的数的位置。
如何转移，很显然抓住定义的特点，我们只需要枚举上一个不使用操作的点 \(j\) 即可。那么 \(j\) 需要满足什么，显然需要比 \(i\) 小，并且位置在 \(i\) 的左侧，否则 \(i,j\) 都不动就不符合题意。
然后考虑从 \(f[j]\) 转移到 \(f[i]\)，或是直接将 \(i\) 作为第一个不使用操作的人：
\[f[i]=\min_{1\leq j<i,pos[j]<pos[i]}\Big(\sum_{k=1}^{i-1}\min(a_k,b_k),f[j]+\sum_{k=j+1}^{i-1}a_k \Big) \]答案即为：
\[\min_{i=1}^n\Big(f[i]+\sum_{k=i+1}^n\min(a_k,c_k) \Big) \]转移方面可以用树状数组或线段树维护前缀最小值，关于 \(\sum_{k=j+1}^{i-1}a_k\) 可以在后面补上一段变成 \(f[j]+\sum_{k=j+1}^{n}a_k\) 即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,pos[N],a[N],b[N],c[N];
int suma[N],pre[N],suf[N],f[N],bit[N];
void add(int x,int y){
for(int i=x;i<=n;i+=(i&-i)){
bit[i]=min(bit[i],y);
}
}
int query(int x){
int ans=1e18;
for(int i=x;i>=1;i-=(i&-i)){
ans=min(ans,bit[i]);
}
return ans;
}
signed main(){
n=read();
for(int i=1;i<=n;++i)pos[read()]=i,bit[i]=1e18;
for(int i=1;i<=n;++i){
a[i]=read(),b[i]=read(),c[i]=read();
suma[i]=suma[i-1]+a[i];
pre[i]=pre[i-1]+min(a[i],b[i]);
}
for(int i=n;i>=1;--i)suf[i]=suf[i+1]+min(a[i],c[i]);
int ans=1e18;
for(int i=1;i<=n;++i){
f[i]=min(pre[i-1],query(pos[i])-(suma[n]-suma[i-1]));
ans=min(ans,f[i]+suf[i+1]);
add(pos[i],f[i]+suma[n]-suma[i]);
}
print(ans);
return 0;
}