ECPC 2019 Kickoff

(Updated: )
(18 mins to read)

除了I没人过（没看），都不难特别简单的略过

B

给三根木棍长度a,b,c，再给一个k，你可以选择一根木棍让它的长度最多延长k，问你这三根木棍构成的三角形的最大面积

考虑枚举延长的边，我们可以算出这条边的范围，然后利用余弦定理求出这条边对角的范围，最大化这个角的sin值即可

K

n盆植物，第i盆初始高度为$h_i$​，生成速度为$g_i$​，问你最短第几天所有植物会形成非降序列

显然考虑相邻两盆，抽象成直线即可，要么是$[0,l]$,要么是$[r,\inf]$，维护l和r即可

J

一个序列，只有’a’,‘b’,‘c’，且’b’最多一个，现在可以交换任意两个位置，问你满足相邻两个位置的字母要么相等，要么有一个是’b’

没有b的时候，显然只有全是a或者全是c才能满足有1个b，只能是aaabcccc或者ccccbaaa的形式，取个min即可

L

给一个数n，初始有x=0，每次操作从$[0, 2^n-1]$中随机选择一个数r，让$x=x^r$，设期望p步后该数变为0，问期望步数的平方

答案就是$\sum_{i=1}^{\infty}i^2(1-\frac{1}{2^n})^{i-1}\frac{1}{2^n}$

C

给出一个序列，然后执行一次上述函数后，问你得到的序列这个函数就是每次优先找到跟你与运算不等于0的数，如果没有这样的数，再找到第一个与运算等于0的。考虑优化找这个数的过程与不等于0，那肯定有一位你是1，它也是1。用30个队列，每个队列存第i位为1的数的下标那么如果当前进行到u，枚举30位，找到队列中第一个没访问过的数，取它们的最小数就是下一个数了。显然访问过的数可以pop掉。如果没有这样的数了，剩下没访问过的显然跟你与运算都是0，用个链表维护即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N], top;
bool vis[N];
queue<int> q[32];
int to[N], from[N];
void dfs(int u)
{
  if(vis[u]) return;
  vis[u] = 1; b[++top] = a[u]; to[from[u]] = to[u]; from[to[u]] = from[u];
  while(true)
  {
    int nxt = n + 1;
    for(int i=0; i<=30; i++)
      if((a[u]>>i)&1)
      {
        while(!q[i].empty() && vis[q[i].front()]) q[i].pop();
        if(!q[i].empty()) nxt = min(nxt, q[i].front());
      }
    if(nxt==n+1) break;
    dfs(nxt);
  }
  int nxt = to[0];
  while(nxt<=n && vis[nxt]) nxt = to[nxt];
  if(nxt<=n) dfs(nxt);
}
int main()
{
  freopen("sorting.in", "r", stdin);
  scanf("%d", &n);
  for(int i=1; i<=n; i++)
  {
    scanf("%d", a+i);
    to[i] = i + 1; from[i] = i - 1;
    for(int j=0; j<=30; j++)
      if((a[i]>>j)&1) q[j].push(i);
  }
  dfs(1);
  for(int i=1; i<=n; i++) printf("%d%c", b[i], " \n"[i==n]);
  return 0;
}

D

有一个无向图，然后给你q个二元组(d,c)，表示在第d天之前访问过c，问你第0天的起点可能有几个按照d升序给出，其中第i天你可以选择不动，也可以选择移到相邻的一个节点$n \leq 2000,m\leq 10^4$

显然在每个点跑一遍bfs求出两两的最短路，相邻二元组的城市我们都走最短路，如果后面天数不够，只能往前面借，假设后面最多欠了x天，那么起点和$c_1$​的距离要满足$\leq d_1-x$。一个错误是我把bfs的距离初始化成-1，然后某些点和$c_1$​可能不连通，我也把它算作可行点了

F

还以为是道高深计算几何，然而是个数位dp有两条斜率为$s_1,s_2$​,且都是2的幂次的过原点的直线，给定$x_l,x_r$​让你求$\sum_{i=x_l}^{x_r} (s_1i) \otimes (s_2i)$首先可以转成前缀和，把下界限变成0，然后设$2^{k_1}=s_1,2^{k_2}=s_2$把式子变成$\sum_{i=0}^{n}(i<<k_1) \otimes(i<<k_2)$设$k_1<k_2$​，去掉$k_1$​，$k_2$​变成$k=k_2-k_1$​，最后答案乘上$2^{k_1}$​则$\sum_{i=0}^{n}i \otimes (i<<k)$显然按位考虑对于$[0,k-1]$位，我们只要统计$[0,n]$中那位等于1的数量对于$[41-k,40]$位，我们也只要统计$[0,n]$中那位等于1的数量对于$[k,40]$位，我们要统计$[0,n]$中x位不等于x-k位的数量写两个数位dp就行了。。写完一个，cv一下改改就行

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
ll s1, s2, xl, xr;
ll dp[45][2], dp2[45][2][2];
int a[45], top;
ll dfs(int p, int lim, int t)
{
  if(p==-1) return 1;
  ll &x = dp[p][lim];
  if(~x) return x;
  x = 0;
  int up = lim ? a[p] : 1;
  if(p==t)
  {
    if(up==1) x = dfs(p-1, lim, t);
  }
  else
  {
    for(int i=0; i<=up; i++)
      x = (x + dfs(p-1, lim&&i==up, t))%mod;
  }
  return x;
}
ll dfs2(int p, int lim, int tv, int t, int t2)
{
  if(p==-1) return 1;
  ll &x = dp2[p][lim][tv];
  if(~x) return x;
  x = 0;
  int up = lim ? a[p] : 1;
  for(int i=0; i<=up; i++)
  {
    if(p==t) x = (x + dfs2(p-1, lim&&i==up, i, t, t2))%mod;
    else if(p==t2 && tv!=i) x = (x + dfs2(p-1, lim&&i==up, tv, t, t2))%mod;
    else if(p!=t2) x = (x + dfs2(p-1, lim&&i==up, tv, t, t2))%mod;
  }
  return x;
}
ll work(int k, ll x)
{
  ll ans = 0;
  for(int i=0; i<k; i++)
  {
    memset(dp, -1, sizeof(dp));
    top = 0;
    ll n = x;
    while(n)
    {
      a[top++] = n&1;
      n >>= 1;
    }
    while(top<=40) a[top++] = 0;
    ans = (ans + (1ll<<i)%mod*dfs(top-1, 1, i))%mod;
  }
  for(int i=41-k; i<=40; i++)
  {
    memset(dp, -1, sizeof(dp));
    top = 0;
    ll n = x;
    while(n)
    {
      a[top++] = n&1;
      n >>= 1;
    }
    while(top<=40) a[top++] = 0;
    ans = (ans + (1ll<<(i+k))%mod*dfs(top-1, 1, i))%mod;
  }
  for(int i=k; i<=40; i++)
  {
    memset(dp2, -1, sizeof(dp2));
    top = 0;
    ll n = x;
    while(n)
    {
      a[top++] = n&1;
      n >>= 1;
    }
    while(top<=40) a[top++] = 0;
    ans = (ans + (1ll<<i)%mod*dfs2(top-1, 1, 0, i, i-k))%mod;
  }
  return ans;
}
void solve()
{
  int k1 = 0, k2 = 0;
  scanf("%lld%lld%lld%lld", &s1, &s2, &xl, &xr);
  while((1<<k1)<s1) ++k1;
  while((1<<k2)<s2) ++k2;
  if(k1>k2) swap(k1, k2);
  int k = k2 - k1;
  if(!k) { puts("0"); return; }
  ll ans = (work(k, xr) - work(k, xl-1) + mod)%mod;
  ans = (1ll<<k1)%mod*ans%mod;
  printf("%lld\n", ans);
}
int main()
{
  freopen("geometry.in", "r", stdin);
  int _; scanf("%d", &_);
  while(_--) solve();
  return 0;
}

H

有一个无向图，然后给你一个某个点s到其他点最短路的数组d，且要求最短路至少要经过一条边这个限制是为了防止$d_s=0$，让你找到最小的满足条件的s

没有想到很好的做法，给出一种奇怪的做法考虑以s为源点的距离数组构成的最短路图如果这个距离数组是合法的，那么这个最短路图要满足是一个连通的DAG，且只有s的入度等于0我们对每个点i，让$d_i=0$，然后建出最短路图判断一下是否满足以上条件就知道i能不能是源点了下面考虑加速以上做法我们先把原数组的最短路图建出来，对于每个i，把和它有关的边去掉，然后让$d_i=0$，再枚举和它相连的边建出新边即可。那么对于原数组建出的最短路图中的某条边$(i,j)$(i<j)来说，它存在于[1,i−1],[i+1,j−1]，[j+1,n][1,i-1],[i+1,j-1]，[j+1,n][1,i−1],[i+1,j−1]，[j+1,n]这三个区间所以线段树分治即可，在叶子的时候再建出新边。注意维护连通块数量以及入度为0的点数还需要注意要满足i的所有边的权值的最小值要是$d_i$​的一半

线段树分治在叶子不要忘记rollbackif(l==r)不要return

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
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 2e5 + 5, inf = 1e9;
int n, m;
ll s[N];
vector<pair<int, int>> G[N];
int fa[N], sz[N], undo[N*3], top, scc, ans, deg[N], zcnt;
int find(int x)
{
  while(x!=fa[x]) x = fa[x];
  return x;
}
void merge(int x, int y)
{
  x = find(x), y = find(y);
  if(x==y) return;
  if(sz[x]>sz[y]) swap(x, y);
  undo[++top] = x;
  --scc;
  fa[x] = y;
  sz[y] += sz[x];
}
void rollback(int t)
{
  while(top>t)
  {
    int x = undo[top];
    sz[fa[x]] -= sz[x];
    fa[x] = x;
    ++scc;
    --top;
  }
}
vector<pair<int, int>> op[N<<2];
void ins(int p, int l, int r, int x, int y, int px, int py)
{
  if(l>=x && r<=y)
  {
    op[p].emplace_back(px, py);
    return;
  }
  int mid = (l+r)>>1;
  if(x<=mid) ins(p<<1, l, mid, x, y, px, py);
  if(y>mid) ins(p<<1|1, mid+1, r, x, y, px, py);
}
void go(int p, int l, int r)
{
  if(~ans) return;
  int dfn = top;
  for(auto it : op[p])
  {
    merge(it.fi, it.se);
    if(!deg[it.se]) --zcnt;
    ++deg[it.se];
  }
  if(l==r)
  {
    int tmp = top, mn = inf;
    for(auto it : G[l])
    {
      mn = min(mn, it.se);
      if(it.se==s[it.fi])
      {
        merge(l, it.fi);
        if(!deg[it.fi]) --zcnt;
        ++deg[it.fi];
      }
    }
    if(scc==1 && zcnt==1 && mn*2==s[l]) ans = l;
    rollback(tmp);
    for(auto it : G[l])
      if(it.se==s[it.fi])
        if(!(--deg[it.fi])) ++zcnt;
  }
  else
  {
    int mid = (l+r)>>1;
    go(p<<1, l, mid); go(p<<1|1, mid+1, r);
  }
  rollback(dfn);
  for(auto it : op[p])
    if(!(--deg[it.se])) ++zcnt;
}
int main()
{
  freopen("hide.in", "r", stdin);
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) scanf("%lld", s+i);
  for(int i=1; i<=m; i++)
  {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    G[u].emplace_back(v, w); G[v].emplace_back(u, w);
  }
  for(int i=1; i<=n; i++) fa[i] = i, sz[i] = 1;
  scc = n, ans = -1, zcnt = n;
  for(int i=1; i<=n; i++)
    for(auto it : G[i])
      if(s[i]+it.se==s[it.fi])
      {
        int x = i, y = it.fi;
        if(x>y) swap(x, y);
        if(x>1) ins(1, 1, n, 1, x-1, i, it.fi);
        if(y<n) ins(1, 1, n, y+1, n, i, it.fi);
        if(x+1<y) ins(1, 1, n, x+1, y-1, i, it.fi);
      }
  go(1, 1, n);
  printf("%d\n", ans);
  return 0;
}