https://codeforces.com/gym/101002

A

trick 题。

简单来说，去计算和全选最大的方案的差值可以换成另外一个问题。

例如：

$p<q$ ，你现在计算与选最大的方案的差值，问题变为：

$p-q,0$ 选择，不难发现，问题可以转化为所选择的商店中所有商品的权值和。

唯一还需要考虑的问题就是两个商店必须要有一个被选择，这个问题可以在 meet in middle 中强制指定对面必须选择某些商店。

然后 meet in middle + 高维前缀和一下就做完了。

时间复杂度：$O(2^{\frac{m}{2}}*(\frac{m}{2})^2)$

这题我是没有做出来的。

启示

对于一些题目，变换一下参考系有时候是可以转化问题的。

例如本题：一开始选择不同的价格本质上是将 $0$ 做参考系的，求与 $0$ 的差值。

但是如果变换参考系，变为全选最大的价格的方案代价，求与其的差值，这样就把选商品的问题变成了求被选中的商店中所有商品的权值之和，规避了一步选择。

问题就从先选商店再选商品变成选商店求和，问题大幅度简化，然后就可做了。

会发现如果不转化问题直接 meet in middle 基本没有办法解决需要进行两步选择的问题，所以这就体现了转化问题的重要性。

这不是显然吗，有些问题你不转化成其他问题不就是没法做吗？什么废话文学。

值得一提的是，由于限制非常松，我们机房分别以随机化、暴力剪枝过了，所以很多时候不会做不要紧，冲一发暴力剪枝再说。

B

做法

一个感觉非常正确的事情：这道题目应该是道模拟题，模拟出来的长度应该就是最小长度。

其次显然长度最多是 $24000$ ，所以直接暴力模拟就行了，不过模拟方式的优秀程度会决定你写代码的时间，我们这边有的队十分钟就写完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#define N 4100
#define M 31000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
int a[N],b[N],sum[N],n;
char st[N];
int sta[N],top,cnt;
void init(){fep(i,1,cnt+cnt)sum[i]=sum[i-1]+a[i];}
int getlen(int x){
    int y=0;
    while(x)x/=10,y++;
    return y;
}
char ss[M];int tot;
int main(){
    scanf("%s",st+1);n=strlen(st+1);
    fep(i,1,n){
        if(st[i]=='(')sta[++top]=++cnt,b[(cnt+cnt-1)]=cnt+cnt,a[cnt+cnt-1]=a[cnt+cnt]=2;
        else{
            int x=sta[top--];
            b[x+x]=cnt+cnt;
        }
    }
    bool bk=1;
    while(bk){
        bk=0;init();
        fep(i,1,n){
            int x=sum[b[i]];
            if(getlen(x)!=a[i]-1){
                a[i]=getlen(x)+1;bk=1;
                // break;
            }
        }
    }
    // fep(i,1,n)printf("%d %d\n",sum[i],b[i]);
    fep(i,1,n){
        int x=sum[b[i]];
        int len=getlen(x),now=1;
        fep(j,2,len)now*=10;
        fep(j,1,len)ss[++tot]=x/now+'0',x%=now,now/=10;
        if(i&1)ss[++tot]=',';
        else ss[++tot]=':';
    }
    printf("%s\n",ss+1);
    return 0;
}

C

队友写了。

D

分数规划+树上背包。

时间复杂度：$O(n^2\log V)$

E

FFT。

F

队友写了。

G

两种情况分别做一下，第一种情况处理中点，Hash一下，第二种情况类似，两点中垂线 Hash 一下，注意归一化的问题。

比较麻烦的点是有的点在对称中心（好处理）和对称轴（不好处理）。

直接 $n^3$ 可以 AC 。

但是队友有更加优秀的做法：

平面中等腰三角形个数的级别为 $O(n^{2.137})$ 。

参考[HNOI 2019] 鱼 的题解：https://www.luogu.com.cn/blog/zhoutb2333/solution-p5286

证明在这：https://link.springer.com/article/10.1007/s003730200063

然后就可以知道一个点如果在对称轴会落在哪条对称轴了。

找等腰三角形也很简单，每个点求一遍与其余点的距离，排序，显然只有有两个点到达某个点的距离相等时才可能且一定构成等腰三角形，这一部分是 $O(n^2\log{n}+n^{2.137})$ 。

总的时间复杂度也是：$O(n^2\log{n}+n^{2.137})$ 。

H

首先，一个很显然的事情，可以类似单调队列求分组背包的做法做。

唯一的问题是随着同一个 $k$ 的放置，越放价值越小，但是可以发现存在决策单调，然后就做完了。

决策单调性：

如果对于 $i$ ，从 $j$ 转移优于 $k(k<j)$ ，那么对于 $i+1$ ，从 $j$ 转移也优于从 $k$ 转移。

时间复杂度：$O(ks\log{k})$ 。

扩展

https://codeforces.com/gym/101064/problem/L

https://www.zhihu.com/question/26547156/answer/1181239468

类似的题目，只不过变成了完全背包。

做法非常的巧妙。

简单来说，你总是可以把背包拆成两个部分：$f(S)=f(X)+f(S-X)$ ，且一定可以找到一种分法使得： $||X|-|S-X||\le W$ ，所以为了得到容量 $V$ 的背包，你可以跑出 $[\frac{V-W}{2},\frac{V-W}{2}]$ 的背包，然后合并出来。

为此，你还可以不断向下分，跑出：$[\frac{\frac{V-W}{2}-W}{2},\frac{\frac{V+W}{2}+W}{2}]$ 的答案，不断往下，可以证明 $W$ 的系数一直都是 $<1$ 的，所以时间复杂度：$O(W^2\log{V})$ 。

I

SB 题，调和级数随便做。

J

我的做法

四个方向处理出每个格子的最晚到达时间，然后找一下最大最小值就做完了。

时间复杂度：$O(wh\log{n}+n)$。

也可以做到：$O(wh(\alpha(w)+\alpha(h))+n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define N 1100000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
typedef long long LL;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char st[N];
int findtype(){
    if(st[1]=='u')return 0;
    else if(st[1]=='r')return 1;
    else if(st[1]=='d')return 2;
    else return 3;
}
PII dooper(PII x,int type,int dis){return make_pair(x.first+dx[type]*dis,x.second+dy[type]*dis);}
int dis(PII x,PII y){return abs(x.first-y.first)+abs(x.second-y.second);}

int H,W,n;
vector<int> a[N];
vector<LL> fir[N],las[N];
vector<vector<PLI> > fuck[N];

bool v[N];
struct ope{
    PII st,ed;int type;
    int len;LL fir;
}op[N];
priority_queue<PLI,vector<PLI>,greater<PLI> >nt1;//small
priority_queue<PLI>nt2;//big

bool nextype(int &x,int &y,int type){
    bool bk=0;
    if(!type){x--;if(!x)x=H,y++,bk=1;}
    else if(type==1){y++;if(y==W+1)x++,y=1,bk=1;}
    else if(type==2){x++;if(x==H+1)y++,x=1,bk=1;}
    else {y--;if(!y)x++,y=W,bk=1;}
    return bk;
}
void upd(int x,int y,LL z){
    if(!fir[x][y])fir[x][y]=las[x][y]=z;
    else fir[x][y]=min(fir[x][y],z),las[x][y]=max(las[x][y],z);
}
bool check(PII x,PLI y){
    int len=dis(x,op[y.second].st);
    return len<=op[y.second].len-1;
}
void solve(int nowtype){
    fep(i,1,H){
        fep(j,1,W)fuck[i][j].clear();
    }
    fep(i,1,n){
        if(op[i].type==nowtype)fuck[op[i].st.first][op[i].st.second].push_back(make_pair(op[i].fir,i));
    }
    int nowx=1,nowy=1;
    if(!nowtype)nowx=H;
    if(nowtype==3)nowy=W;
    fep(i,1,H*W){
        for(auto x:fuck[nowx][nowy]){nt1.push(x);nt2.push(x);}
        while(!nt1.empty()){
            PLI x=nt1.top();
            if(!check(make_pair(nowx,nowy),x))nt1.pop();
            else{
                upd(nowx,nowy,x.first+dis(make_pair(nowx,nowy),op[x.second].st));
                break;
            }
        }
        while(!nt2.empty()){
            PLI x=nt2.top();
            if(!check(make_pair(nowx,nowy),x))nt2.pop();
            else{
                upd(nowx,nowy,x.first+dis(make_pair(nowx,nowy),op[x.second].st));
                break;
            }
        }
        if(nextype(nowx,nowy,nowtype)==1){
            while(!nt1.empty())nt1.pop();
            while(!nt2.empty())nt2.pop();
        }
    }
}

int main(){
    scanf("%d%d%d",&H,&W,&n);
    fep(i,0,H)a[i].resize(W+10),fir[i].resize(W+10),las[i].resize(W+10),fuck[i].resize(W+10);
    fep(i,1,H){
        scanf("%s",st+1);
        fep(j,1,W)a[i][j]=(st[j]=='#');
    }
    PII now=make_pair(H,1);LL fnow=1;
    fir[H][1]=las[H][1]=1;
    fep(i,1,n){
        scanf("%s",st+1);int len;scanf("%d",&len);
        op[i].len=len;op[i].type=findtype();op[i].fir=fnow+1;
        op[i].st=dooper(now,op[i].type,1);op[i].ed=dooper(now,op[i].type,len);
        now=op[i].ed;fnow+=len;
    }
    fep(t,0,3)solve(t);

    // fep(i,1,n){
    //     printf("%d %d:%d %d:%d %d\n",op[i].st.first,op[i].st.second,op[i].ed.first,op[i].ed.second,op[i].len,op[i].type);
    // }
    // fep(i,1,H){
    //     fep(j,1,W)printf("%lld ",fir[i][j]);
    //     printf("\n");
    // }

    LL ans1=-1,ans2=-1;
    fep(i,1,H){
        fep(j,1,W){
            if(a[i][j] && !las[i][j]){printf("-1 -1\n");return 0;}
            if(!las[i][j])continue;
            if(a[i][j]){
                if(ans1==-1 || las[i][j]+1>ans1)ans1=las[i][j]+1;
            }
            if(!a[i][j]){
                if(ans2==-1 || las[i][j]<ans2)ans2=las[i][j];
            }
        }
    }
    if(ans1==-1)ans1=1;
    if(ans2==-1)ans2=fnow+1;
    if(ans1>ans2){printf("-1 -1\n");return 0;}
    printf("%lld %lld\n",ans1-1,ans2-1);
    return 0;
}
别的队伍

先利用差分+前缀和求出跑过的路径长度。（$>0$ 表示跑过了）

二分加检验，直接倒着跑白点，类似上面的方法求出被白点覆盖且跑过的路径长度，检验一下是否相同。

时间复杂度：$O(hw(\log{n}+log{h}+\log{w}))$ 。

只考虑求最早时间的 O(n) 做法

利用二维前缀和能够求出任意区域的红点数量，然后倒着跑，直到跑到红点为止，跑到红点的时间就是墨水干的时间。

K

woc ，为什么这么 SB 的题目我想了这么久！

做法

先点分治，每个点处理到根的路径长度，这样每个点有个权值 $(A,B)$ ，然后两个点的贡献为：$A_1*A_2+B_1+B_2$ ，注意到路径有重边无所谓，权值只会增大，所以不会统计进答案里。

直接跑出整个树的凸包然后在凸包上找答案就行了，为此，我才用的是凸包+李超线段树。

时间复杂度：$O(n\log{n}\log{p})$ 。

我做的久的原因：没有注意到重边无所谓的性质，一直在想子树间相互的贡献怎么统计，一直没有想出来，直到发现重边无所谓的性质就秒了。

不过就算没有注意到这个性质也有的做：边分治，边分治可以保证把图变成大小接近的两个部分，然后就可以统计相互之间的贡献了，时间复杂度是一样的，同样也可以利用下面的优化优化到 $O(n\log{n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 210000
#define M 410000
#define NN 6100000
#define fep(i,x,y) for(int i=x;i<=y;i++)
#define feq(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
LL operator*(PLL x,PLL y){return x.first*y.first+x.second+y.second;}
LL operator*(PLL x,LL y){return x.first*y+x.second;}
int V=1000000;
struct node{
    int lc,rc;
    PLL val;int mid;
}tr[NN];int len,rot;
int newnode(int mid){int x=++len;tr[x].lc=tr[x].rc=0;tr[x].mid=mid;tr[x].val=make_pair(0,0);return len;}
void pushdown(int &x,int l,int r,PLL val){
    int mid=(l+r)>>1;
    if(!x){x=newnode(mid);tr[x].val=val;return ;}
    if(tr[x].val*mid>val*mid)swap(tr[x].val,val);
    if(l==r)return ;
    if(val.first>tr[x].val.first)pushdown(tr[x].lc,l,mid,val);
    else pushdown(tr[x].rc,mid+1,r,val);
}
LL now;
void upd(LL x,LL &y){if(!y || x<y)y=x;}
void findans(int x,int l,int r,int id){
    if(!x)return ;
    upd(tr[x].val*(LL)id,now);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(id<=mid)findans(tr[x].lc,l,mid,id);
    else findans(tr[x].rc,mid+1,r,id);
}
struct Edge{
    int y,next;LL c;
}a[M];int cnt,last[N];
void ins(int x,int y,LL c){cnt++;a[cnt].y=y;a[cnt].c=c;a[cnt].next=last[x];last[x]=cnt;}
int siz[N],msiz;bool v[N];
void dfs1(int x,int fa){
    siz[x]=1;
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;if(y==fa || v[y])continue;
        dfs1(y,x);
        siz[x]+=siz[y];
    }
}
int rt,maxsiz[N];
void dfs2(int x,int fa){
    maxsiz[x]=msiz-siz[x];
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;if(y==fa || v[y])continue;
        dfs2(y,x);
        if(siz[y]>maxsiz[x])maxsiz[x]=siz[y];
    }
    if(!rt || maxsiz[x]<maxsiz[rt])rt=x;
}
LL dep[N],zjj[N],zans[N];int sta[N],top;
void dfs3(int x,int fa){
    pushdown(rot,1,V,make_pair(zjj[x],dep[x]));sta[++top]=x;
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;if(y==fa || v[y])continue;
        dep[y]=dep[x]+a[k].c;dfs3(y,x);
    }
}
void work(int x){
    len=rot=top=0;
    dep[x]=0;dfs3(x,0);
    fep(i,1,top){
        int y=sta[i];now=0;
        findans(rot,1,V,zjj[y]);
        upd(now+dep[y],zans[y]);
    }
    v[x]=1;
}
void solve(int x){
    rt=0;dfs1(x,0);msiz=siz[x];
    dfs2(x,0);x=rt;
    work(x);
    // printf("%d\n",x);
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;if(!v[y])solve(y);
    }
}
int n;
int main(){
    scanf("%d",&n);
    fep(i,1,n)scanf("%lld",&zjj[i]);
    fep(i,2,n){
        int x,y;LL c;scanf("%d%d%lld",&x,&y,&c);
        ins(x,y,c);ins(y,x,c);
    }
    solve(1);
    LL ans=0;
    fep(i,1,n){
        // printf("%lld\n",zans[i]);
        ans+=zans[i];
    }
    printf("%lld\n",ans);
    return 0;
}

当然，注意到一个事情，每个点的斜率实际上一开始就是给定的，所以只要你愿意，在外面排好序，然后采用精妙的实现，可以做到 $O(n\log{n})$ 的时间复杂度。