我错惹，现在是总结了QWQ
与 T4 数据搏斗了一晚上终于找到时间写了。
T1 math
我炸了……
我连小学水平都没有。
代码已经钉上耻辱柱了所以没有。
T2 tree
很水，然后我的代码被反复吊起来锤，然后我就只能告诉他们这个东西能跑前提是输入数据必须满足题意。
#include<cstdio>
using namespace std;
int t,n,d[100010][3];
char BuF[1<<26],*InF=BuF;
template<typename T>void read(T &x){
for(;*InF<33;++InF);
for(x=0;47<*InF&&*InF<58;x=(x<<3)+(x<<1)+(*InF++^48));
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
fread(BuF,1,1<<26,stdin);
for(read(t);t;--t){
bool ans=1,tmp=1;
read(n);
for(int i=0;i<n;++i){
read(d[i][0]);
}
d[0][1]=0;d[0][2]=n+1;
for(int l=0,r=0;l<=r;++l){
if(d[l][1]<d[r+1][0]&&d[r+1][0]<d[l][0]){
++r;
d[r][1]=d[l][1];
d[r][2]=d[l][0];
tmp^=1;
}
if(d[l][2]>d[r+1][0]&&d[r+1][0]>d[l][0]){
++r;
d[r][1]=d[l][0];
d[r][2]=d[l][2];
tmp^=1;
}
ans&=tmp;
}
printf(ans?"YES
":"NO
");
}
fclose(stdin);
fclose(stdout);
return 0;
}
T3 minecraft
题目有意思，但是很离谱。
是个人都知道地狱的距离在奇怪的地形下并没有屁用，只有长期档才会有地狱交通这种东西。
这就跟100的数据没人写倍增一个道理
然后就是倍增，然后炸了。
然后把转移删去两个就过了。
以下代码正解。
#include<cstdio>
#include<iostream>
#define N 600010
#define ll long long
using namespace std;
int n,q,a[N],b[N<<1][3],dp[N],last,st[N],size,i[N],mx[N];
ll pt[N];
bool vis[N];
struct patop{
ll d[4];
int p;
patop(){
d[0]=d[1]=d[2]=d[3]=p=0;
}
patop operator+(patop b){
patop re;
re.p=b.p;
re.d[0]=min(d[0]+b.d[0],d[1]+b.d[2]);
re.d[1]=min(d[1]+b.d[3],d[0]+b.d[1]);
re.d[2]=min(d[2]+b.d[0],d[3]+b.d[2]);
re.d[3]=min(d[3]+b.d[3],d[2]+b.d[1]);
return(p?re:b);
}
}s[N][21];
char BuF[1<<26],*InF=BuF;
template<typename T>void read(T &x){
for(;*InF<33;++InF);
for(x=0;47<*InF&&*InF<58;x=(x<<3)+(x<<1)+(*InF++^48));
}
void add(int x,int y,int z){
b[++last][0]=a[x];
b[a[x]=last][1]=y;
b[last][2]=z;
}
void dfs(){
for(st[size=1]=1;size;){
register int m=st[size],&im=i[st[size]];
vis[m]=1;
if(!im){
dp[m]=dp[s[m][0].p]+1;
for(mx[x]=1;s[m][mx[x]-1].p;++i){
s[m][mx[x]]=s[m][mx[x]-1]+s[s[m][mx[x]-1].p][mx[x]-1];
}
im=a[m];
}else{
im=b[im][0];
}
for(;im&&b[im][1]==s[m][0].p;im=b[im][0]);
if(im){
s[b[im][1]][0].p=m;
s[b[im][1]][0].d[0]=b[im][2]<<3;
s[b[im][1]][0].d[1]=min(pt[b[im][1]]+b[im][2],(b[im][2]<<3)+pt[m]);
s[b[im][1]][0].d[2]=min(pt[b[im][1]]+(b[im][2]<<3),b[im][2]+pt[m]);
s[b[im][1]][0].d[3]=b[im][2];
st[++size]=b[im][1];
}else{
size--;
}
}
}
ll lca(int x,int y){
patop a,b;
if(dp[x]<dp[y]){
swap(x,y);
}
for(register int i=mx[x];dp[x]>dp[y];--i){
if(dp[s[x][i].p]>=dp[y]){
a=a+s[x][i];
x=s[x][i].p;
}
}
for(register int i=mx[x];i>=0;--i){
if(s[x][i].p!=s[y][i].p){
a=a+s[x][i];
x=s[x][i].p;
b=b+s[y][i];
y=s[y][i].p;
}
}
if(x!=y){
a=a+s[x][0];
b=b+s[y][0];
}
return(min(a.d[0]+b.d[0],min(a.d[1]+(b.d[1]?b.d[1]:pt[a.p]),min(a.d[0]+b.d[1],a.d[1]+b.d[0])+pt[a.p])));
}
int main(){
freopen("minecraft5.in","r",stdin);
freopen("minecraft.out","w",stdout);
fread(BuF,1,1<<26,stdin);
read(n);
for(register int i=1;i<=n;++i){
read(pt[i]);
}
for(register int i=1,x,y,z;i<n;++i){
read(x);read(y);read(z);
add(x,y,z);
add(y,x,z);
}
dfs();
for(register int i=1;i<=n;i++){
if(!vis[i]){
printf("%d
",i);
}
}
read(q);
for(register int i=1,x,y;i<=q;++i){
read(x);read(y);
printf("%lld
",lca(x,y));
}
fclose(stdin);
fclose(stdout);
return 0;
}
T4 matrix
讲题时点名的那个该不会是我……
反正我是写的网络流。
然后被拉去造民间（？）数据，然后锅了，然后又锅了……
然后一晚上就过了。
这辈子再不想造数据
#include<cstring>
#include<iostream>
#define N 1010
#define TT 2020
#define INF 0x7f7f7f7f
using namespace std;
int n,a[N][N],b[N][N],r[TT+1],cur[TT+1],w[TT+1],d[TT+1];
struct CFS{
int h[TT+1],b[N*N<<3][3],last;
CFS(){
last=-1;
}
void add(int x,int y,int z){
b[++last][0]=h[x];
b[h[x]=last][1]=y;
b[last][2]=z;
}
}h;
bool p[N][N];
char BuF[1<<26],*InF=BuF;
template<typename T>void read(T &x){
for(;*InF<33;++InF);
for(x=0;47<*InF&&*InF<58;x=(x<<3)+(x<<1)+(*InF++^48));
}
bool bfs(){
memset(w,127,sizeof(w));
w[0]=0;
for(int l=1,r=1;l<=r;++l){
cur[d[l]]=h.h[d[l]];
for(int j=h.h[d[l]];j>=0;j=h.b[j][0]){
if(h.b[j][2]&&w[h.b[j][1]]==INF){
w[h.b[j][1]]=w[d[l]]+1;
d[++r]=h.b[j][1];
}
}
}
return(w[TT]<INF);
}
int dfs(int x,int flow){
if(x==TT){
return(flow);
}
int used=0,aflow;
for(;cur[x]>=0;cur[x]=h.b[cur[x]][0]){
if(h.b[cur[x]][2]&&w[h.b[cur[x]][1]]==w[x]+1){
if((aflow=dfs(h.b[cur[x]][1],min(flow-used,h.b[cur[x]][2])))){
h.b[cur[x]][2]-=aflow;
h.b[cur[x]^1][2]+=aflow;
if((used+=aflow)==flow){
return(used);
}
}else{
w[h.b[cur[x]][1]]=INF;
}
}
}
return(used);
}
void dinic(){
while(bfs()){
dfs(0,INF);
}
}
int main(){
fread(BuF,1,1<<26,stdin);
memset(h.h,-1,sizeof(h.h));
read(n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
read(a[i][j]);
b[i][j]=a[i][j]>>1;
if(a[i][j]&1){
h.add(i,j+N,1);
h.add(j+N,i,0);
++r[i];
++r[j+N];
}
}
}
for(int i=1;i<=n;++i){
h.add(0,i,r[i]>>1);
h.add(i,0,0);
h.add(i+N,TT,r[i+N]>>1);
h.add(TT,i+N,0);
}
dinic();
for(int i=1;i<=n;++i){
for(int j=h.h[i];j>=0;j=h.b[j][0]){
if(h.b[j][1]>N&&h.b[j][1]!=TT){
b[i][h.b[j][1]-N]+=h.b[j^1][2];
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
printf("%d ",b[i][j]);
}
putchar('
');
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
printf("%d ",a[i][j]-b[i][j]);
}
putchar('
');
}
fclose(stdin);
fclose(stdout);
return 0;
}