| A |
B |
C |
D |
E |
F |
| $\color{green}{\texttt{+2}}$ |
$\color{green}{\texttt{+2}}$ |
$\color{green}{\texttt{+}}$ |
$\color{red}{\texttt{+}}$ |
$\color{green}{\texttt{+}}$ |
$\color{red}{\texttt{-}}$ |
A. Vera and Trail Building
考虑构造一条很长的链，那么每加入一个长度为 $x$ 的环，都会多出 $\binom{x}{2}$ 的贡献。
从后往前贪心取即可。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 100010
using namespace std;
vector<pair<int,int>>res;
int main()
{
int n=4700,k;scanf("%d",&k);
for(int i=1;i<n;i++) res.emplace_back(i,i+1);
int j=1;
for(int i=2;i<=n;i++)
{
if(!k) break;
if(k<1ll*(i-j+1)*(i-j)/2)
{
k-=(i-j)*(i-j-1)/2;
res.emplace_back(i-1,j);
j=i;
}
}
if(k==1ll*(n-j+1)*(n-j)/2) res.emplace_back(n,j);
printf("%d %d\n",n,(int)res.size());
for(auto w:res) printf("%d %d\n",w.first,w.second);
return 0;
}
|
B. Cartesian Conquest
直接记忆化搜索，复杂度玄学。。。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
int mn[4010][4010],mx[4010][4010];
int dfs_mn(int x,int y)
{
if(!x || !y) return 0;
if(x&1 && y&1) return 1e9;
if(x>y) swap(x,y);
if(x<=4000 && y<=4000 && mn[x][y]) return mn[x][y];
int res=1e9;
if(x*4<y) return dfs_mn(x,y%(x*2)+x*2)+y/(x*2)-1;
if(3*x<=y) return dfs_mn(x,y-2*x)+1;
if(2*x<=y) res=min(res,dfs_mn(x,y-2*x)+1);
if(x%2==0) res=min(res,dfs_mn(x,y-x/2)+1);
if(y%2==0 && x>=y/2) res=min(res,dfs_mn(x-y/2,y)+1);
if(x<=4000 && y<=4000) mn[x][y]=res;
return res;
}
int dfs_mx(int x,int y)
{
if(!x || !y) return 0;
if(x&1 && y&1) return -1e9;
if(x>y) swap(x,y);
if(x<=4000 && y<=4000 && mx[x][y]) return mx[x][y];
int res=0;
if(x*4<=y)
{
int w=x&1?x*2:x/2;
return dfs_mx(x,y%w+x*2)+(y-x*2)/w;
}
if(x%2==0) res=max(res,dfs_mx(x,y-x/2)+1);
else if(y>=2*x) res=max(res,dfs_mx(x,y-2*x)+1);
if(y%2==0 && x>=y/2) res=max(res,dfs_mx(x-y/2,y)+1);
if(x<=4000 && y<=4000) mx[x][y]=res;
return res;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
printf("%d %d\n",dfs_mn(n,m),dfs_mx(n,m));
return 0;
}
|
C. Vera and Modern Art
其实题意相当于是：有 $n$ 个字符串对 $(p_i,q_i)$，第 $i$ 个权值为 $v_i$。每次询问一个字符串对 $(x_i,y_i)$，问满足 $p_i$ 是 $x_i$ 前缀，$q_i$ 是 $y_i$ 前缀的 $v_i$ 之和。
这个可以直接建 Trie 树套 Trie 树做到 $O(n\log n+q\log^2 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
| #include<iostream>
#include<cstdio>
#include<cstring>
#define clz(x) (64-__builtin_clzll(x))
using namespace std;
typedef long long ll;
const int N=200010,M=60;
int ch[N*M*2][2],t[N*M*2],tt=1;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
ll x,y;int v;scanf("%lld%lld%d",&x,&y,&v);
int lx=clz(x),ly=clz(y),u=1;
for(int i=0;i<lx-1;u=ch[u][x>>i&1],i++) if(!ch[u][x>>i&1]) ch[u][x>>i&1]=++tt;
if(!t[u]) t[u]=++tt;u=t[u];
for(int i=0;i<ly-1;u=ch[u][y>>i&1],i++) if(!ch[u][y>>i&1]) ch[u][y>>i&1]=++tt;
t[u]+=v;
}
for(int i=1;i<=m;i++)
{
ll x,y;scanf("%lld%lld",&x,&y);
int lx=clz(x),ly=clz(y),res=0;
for(int j=0,u=1;u && j<lx;u=ch[u][x>>j&1],j++)
for(int k=0,v=t[u];v && k<ly;v=ch[v][y>>k&1],k++) res+=t[v];
printf("%d\n",res);
}
return 0;
}
|
D. Rainfall Capture
可以将积水量看做总积水高度减去柱子高度和。
容易证明，对于任意构造，都可以通过调整使得积水高度从右到左递增。这样我们从大到小枚举，每次插入一个柱子时可以使后面比它小的柱子积水量等于它。直接转移复杂度 $O(n^3h)$，考虑其实只有 $O(h)$ 个位置可能会转移，只对相同高度的柱子转移一个即可。然后用 bitset 优化，复杂度 $O(\frac{n^2h^2}{\omega})$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
#define N 510
using namespace std;
int h[N];
bitset<N*N>f[N],ans;
int main()
{
int n,s=0;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]),s+=h[i];
sort(h+1,h+n+1);
f[n][h[n]]=1;
for(int i=n-1;i>=1;i--) if(h[i]!=h[i+1] || i==n-1)
{
for(int j=i;j;j--) f[j]|=f[j+1]<<h[i];
ans|=f[1];
}
for(int i=s;i<=h[n]*n;i++) if(ans[i]) printf("%d ",i-s);
return 0;
}
|
E. Professional Network
可以转化为：将 ${a_i,b_i}$ 任意重排，如果 $a_i\geq i$，那么会造成 $b_i$ 代价，问最小代价。
显然建立二分图，将左边 $i$ 向右边 $[a_i+1,n]$ 的连 $b_i$，$[1,a_i]$ 连 $0$，总代价减去最大权匹配就是答案。考虑模拟这个过程：我们一定是将 $b_i$ 从大到小模拟这件事情，如果我们时刻取满足限制中最小的位置，那么退流过程一定会经过一条带权的反向弧，一定不优。
所以直接贪心即可。复杂度 $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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define N 200010
using namespace std;
int a[N],b[N],id[N];set<int>s;
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){return b[x]>b[y];});
for(int i=1;i<=n;i++) s.insert(i);
long long ans=0;
for(int i=1;i<=n;i++)
{
int u=id[i];auto p=s.upper_bound(a[u]);
if(p==s.end()) ans+=b[u];
else s.erase(p);
}
printf("%lld\n",ans);
return 0;
}
|