codeforces 1330 C.D.题解
Dreamoon Likes Coloring
**题意:**给
n
<
=
100000
n<=100000
n<=100000个待染色的格子,
m
m
m个
l
i
l_i
li对应
m
m
m次染色过程(
m
m
m种颜色),第
i
i
i次染色的区间范围为
[
p
i
,
p
i
+
l
i
−
1
]
[p_i, p_i+l_i-1]
[pi,pi+li−1] , 其中,
p
i
p_i
pi的值可从区间
[
1
,
n
−
l
i
+
1
]
[1,n-l_i+1]
[1,n−li+1]中任选。每一个格子最终的颜色为最后一次对其染色的值,要求构造使得每一个格子都被染色且
m
m
m种颜色均出现的染色方案,如果不存在则输出一1。
**题解:**不存在的情况:
- 所有染色区间的长度之和小于
n
n
n的话是不存在有效方案的(即
∑
i
=
1
m
l
i
<
n
\sum_{i=1}^{m}l_i<n
∑i=1mli<n , 此时
n
n
n个格子无法被全部染色,直接输出一1。
- 第
i
i
i次染色的时候,
p
i
p_i
pi能够取到的最大值比i小,即
n
−
l
i
+
1
<
i
n-l_i+1<i
n−li+1<i, 输出-1。
考虑完不存在的情况后,我们从后往前染色,用
s
u
f
f
i
suff_i
suffi代表
l
i
l_i
li的后缀,则当剩余染色格子的数目大于染色的次数
i
i
i时,
p
i
=
s
u
f
f
i
p_i = suff_i
pi=suffi; 当等于
i
i
i时, 此时可以刚好将剩余的格子全部染色。
综上:
p
i
=
m
a
x
(
i
,
n
−
s
u
f
f
i
+
1
)
p_i = max(i, n-suff_i+1)
pi=max(i,n−suffi+1)。
AC:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 1e5 + 10;
int l[maxn], p[maxn];
void solve(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> l[i];
if(l[i] > n-i+1){
cout << -1 << endl;
return;
}
}
l[n + 1] = 0;
for (int i = m; i >= 1; i--) l[i] += l[i+1];
if(l[1] < n){
cout << -1 << endl;
return;
}
for (int i = m; i >= 1; i--) p[i] = max(i, n-l[i]+1);
for (int i = 1; i <= m; i++) cout << p[i] << " ";
cout << endl;
}
int main(){
IOS;
int t; t = 1;
while(t--){
solve();
}
return 0;
}
Dreamoon Likes Sequences
**题意:**给出两个数
d
,
m
d, m
d,m, 构造一个升序序列
a
i
a_i
ai, 使得按照构造方式构造的
b
i
b_i
bi也是升序,问构造方案数。
构造方式:
b
1
=
a
1
,
b
i
=
b
i
−
1
x
o
r
a
i
b_1 = a_1, b_i = b_{i-1}\ xor\ a_i
b1=a1,bi=bi−1 xor ai 。
**题解:**规律:每个划分
i
i
i,对应的
b
i
b_i
bi的最高位的
1
1
1比
b
i
−
1
b_{i-1}
bi−1的最高位的
1
1
1要高一位。如:
$ {1}{2,3}{4,5,6,7}{8,9,10,11,12,13,14,15}$ ,
注意边界
i
i
i的取值:
m
i
n
(
d
,
2
i
−
2
i
−
1
)
min(d, 2^i - 2^{i-1})
min(d,2i−2i−1)
AC:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 2e5 + 10;
void solve(){
ll n, m;
cin >> n >> m;
ll ans = 1, i = 1;
while((1 << (i-1))-1 <= n){
ll t = min(n, (ll)((1 << i) - 1)) - ((1 << (i - 1)) - 1);
ans = (ans * (t + 1)) % m;
i++;
}
cout << (ans - 1 + m) % m << endl;
}
int main(){
IOS;
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)