C

给定一个序列,每个$w_i$表示重量为$2^{w_i}$的重物
每次最多可以取走$2^k$的重物,问最少取多少次

贪心

我们可知$2*(2^k) = 2^{k+1}$,而低位向高位凑会减少操作次数
所以我们记录cnt[w[i]],然后扫一遍统计即可。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 10;
int w[maxn],cnt[maxn];

int main()
{
int n,mx = 0;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",w+i),mx = max(mx,w[i]);
memset(cnt,0,sizeof cnt);
for(int i=0;i<n;++i) ++cnt[w[i]];
for(int i=0;i<=mx;++i)
{
if(cnt[i])
{
cnt[i+1] += cnt[i]/2;
cnt[i] %= 2;
}
}
for(int i=mx+1;;++i)
{
if(cnt[i])
{
mx = i;
cnt[i+1] += cnt[i]/2;
cnt[i] %= 2;
}
else break;
}
int ans = 0;
for(int i=mx;i>=0;--i) while(cnt[i]) {cnt[i]/=2; ++ans;};
printf("%d\n",ans);
return 0;
}

D

给定一个长度为n的序列$a_0,…,a_{n-1}$,构造一个长度为l的序列$b_0,…,b_{l-1}$
其中$b_i = a_(i \, mod \, n)$
给定k,我们求对于$b_{i_1},b_{i_2},…,b_{i_x} \; (0 \leq i_1 < i_2 < … < i_x < l)$:

  • $1 \leq x \leq k$
  • $\forall 1 \leq j \leq x-1 , \lfloor \frac{i_j}{n} \rfloor + 1 = \lfloor \frac{i_{j+1}}{n} \rfloor$
  • $\forall 1 \leq j \leq x-1 , b_{i_j} \leq b_{i_{j+1}}$ (非严格递增)

满足条件的个数

DP

虽然题目很绕,但是我们可以抽象一下,即都在a中选择,为了满足非严格递增,我们将a排序
我们定义 d[i][j] 表示前i个元素以第j个元素结尾的情况
若只考虑 B段(min(k,l/n))完整的序列a 则答案为
$$\sum_{i=1}^{B} \sum_{j=0}^{n-1} d_{ij}$$
然后考虑不完整的一段a 答案为
$$\sum_{i=1}^{B} \sum_{j=0}^{rem} d_{i(lastpos_{a_j})}$$

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e6 + 10;
const LL mod = 1e9 + 7;

map<int,int> val;

int a[maxn],r[maxn];
LL dp[2][maxn];
vector<LL> d[maxn],sum[maxn];

int n,k;
LL l;

int main()
{
//freopen("test.txt","r",stdin);

scanf("%d %lld %d",&n,&l,&k);
for(int i=0;i<n;++i) scanf("%d",a+i);
if(n>=l)
{
printf("%lld\n",l);
return 0;
}
LL B = l/n,ans = l%mod;
int rem = l%n;

for(int i=0;i<rem;++i) r[i] = a[i];

sort(a,a+n);
for(int i=0;i<n;++i) val[a[i]] = i;

memset(dp,0,sizeof dp);
int cur = 0;
for(int i=0;i<n;++i) dp[1][i] = 1;

for(int i=2;i<=min(B+1,(LL)k);++i)
{
LL sum = 0;
int cnt = 0;
for(int j=0;j<n;++j)
{
while( cnt<n && a[j] >= a[cnt]) sum = (sum + dp[cur^1][cnt])%mod,++cnt;
dp[cur][j] = sum;
d[i].push_back(sum);
}
cur^=1;
}

for(int i=2;i<=min(B+1,(LL)k);++i)
{
LL s = 0;
for(int j=0;j<n;++j)
{
// printf("%d %d %lld\n",i,j,d[i][j]);
s = (s + d[i][j]) %mod;
sum[i].push_back(s);
}
}

for(int i=2;i<=min(B,(LL)k);++i) ans = (ans + (B-i+1)%mod*sum[i][n-1]%mod)%mod;
for(int i=2;i<=min(B+1,(LL)k);++i)
for(int j=0;j<rem;++j)
{
int p = val[r[j]];
ans = (ans + d[i][p])%mod;
}

printf("%lld\n",ans);
return 0;
}

E

一颗树,每个点上有一些值,对于每次询问 v,u,a
输出路径(u,v) 的所有点排序后的最多前a个

LCA

可以由LCA的倍增算法扩展一下
由于a最大只有10,我们定义一个merge函数,可以合并两段查询

记录d[u][i]表示从u的父亲到$2^i$个祖先的合并值
每次询问即一个寻找LCA的过程,并合并路径上的值,注意不要重复合并。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
const int LOG = 17;

struct Node
{
int a[11];
int sz;
Node() {sz=0;}
} d[maxn][LOG],node[maxn];

Node merge(Node a,Node b)
{
Node res;
int l1 , l2;
l1 = l2 = res.sz = 0;
while(res.sz<10 && (l1 < a.sz || l2 < b.sz))
{
while(res.sz < 10 && l1<a.sz && (l2 >= b.sz || b.a[l2] >= a.a[l1]))
{
res.a[res.sz++] = a.a[l1];
++l1;
}
while(res.sz<10 && l2<b.sz && (l1 >= a.sz || b.a[l2] <= a.a[l1]))
{
res.a[res.sz++] = b.a[l2];
++l2;
}
// printf("%d %d\n",l1,l2);
}
return res;
}

vector<int> G[maxn];
int p[maxn][LOG],deep[maxn];
int n,m,q;

void dfs(int u,int fa,int dep)
{
p[u][0] = fa;
if(fa!=-1) d[u][0] = node[fa];
deep[u] = dep;

for(int i=1;i<LOG;++i)
{
if(p[u][i-1] != -1)
{
p[u][i] = p[p[u][i-1]][i-1];
}
}

for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
dfs(v,u,dep+1);
}
}

Node query(int u,int v)
{
//printf("%d %d --> %d %d\n",u,v,deep[u],deep[v]);
if(deep[u] < deep[v]) swap(u,v);
Node resu = node[u],resv = node[v];
for(int i=LOG-1;i>=0;--i)
{
if(p[u][i]!=-1 && deep[p[u][i]] >= deep[v])
{
resu = merge(resu,d[u][i]);
u = p[u][i];
}
}
if( u == v) return resu;
for(int i=LOG-1;i>=0;--i)
{
if(p[u][i] != p[v][i])
{
resu = merge(resu,d[u][i]);
u = p[u][i];
resv = merge(resv,d[v][i]);
v = p[v][i];
}
}
return merge(d[u][0],merge(resu,resv));
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&m,&q);
for(int i=0;i<n-1;++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=m;++i)
{
int x;
scanf("%d",&x);
if(node[x].sz >= 10)
{
node[x].a[10] = i;
sort((node[x].a),(node[x].a)+10);
}
else node[x].a[node[x].sz++] = i;
}
memset(p,-1,sizeof p);
dfs(1,-1,1);
for(int i=1;i<LOG;++i)
{
for(int j=1;j<=n;++j)
{
if(p[j][i-1]!=-1)
{
d[j][i] = merge(d[j][i-1],d[p[j][i-1]][i-1]);
}
}
}
while(q--)
{
int u,v,a;
scanf("%d %d %d",&u,&v,&a);
Node now = query(u,v);
int sz = min(a,now.sz);
printf("%d",sz);
for(int i=0;i<sz;++i) printf(" %d",now.a[i]);
puts("");
}
return 0;
}