Luogu 3646 [APIO2015]巴厘岛的雕塑
标签：getch mes \n color view str temp img ||
初赛成绩出了，和预想的一样，一分都没挂，开心。
大佬的博客
subtask 1 （$n \leq 200$）
因为高位取$0$一定比高位取$1$优，我们考虑按照位从高到低进行检验，设$f_{i, j}$表示前$i$个数划分成$j$段是不是可行，在转移的时候要注意不能让之前计算过的高位从$0$变成$1$，最后只要找到一个$i$满足$A\leq i \leq B$并且$f_{n, i} == true$就可以使当前位取$0$了。
时间复杂度$O(n^3log(MaxInt))$。
subtask 2 （$n \leq 2000,\ A == 1$）
仍然从高位到低位倒叙循环考虑检验，因为这次划分的段数没有下界的限制，我们只要设$g_i$表示到$i$满足这一位取$0$所要划分的最大段数，转移的条件和$f$差不多，最后只要看一看是不是满足$g_n \leq B$就可以知道能不能取$0$了。
时间复杂度$O(n^2log(MaxInt))$。
代码里借鉴了上面大佬的一些写法。
Code：
#include
#include using namespace std;
typedef long long ll;
const int N = 205;
const int M = 2005;
const ll inf = 1 30;
int n, len = 0, st, ed, g[M];
ll ans = 0, a[M], sum[M];
bool f[N][N];
template
inline void read(T &X) {
X = 0; char ch = 0; T op = 1;
for(; ch > ‘9‘|| ch ‘0‘; ch = getchar())
if(ch == ‘-‘) op = -1;
for(; ch >= ‘0‘ && ch ‘9‘; ch = getchar())
X = (X 3) + (X 1) + ch - 48;
X *= op;
}
template
inline void chkMin(T &x, T y) {
if(y y;
}
inline void solve1() {
for(; len; --len) {
for(int i = 1; i )
for(int j = 1; j )
f[i][j] = 0;
f[0][0] = 1;
for(int i = 1; i ) {
for(int j = 1; j )
for(int k = 0; k )
if(f[k][j - 1]) {
ll now = sum[i] - sum[k];
if((now & (1LL 1))) == 0 && (ans | (now >> len)) == ans)
f[i][j] = 1;
}
}
bool flag = 0;
for(int i = st; i )
flag |= f[n][i];
ans 1;
if(!flag) ans |= 1;
}
}
inline void solve2() {
for(; len; --len) {
for(int i = 1; i inf;
g[0] = 0;
for(int i = 1; i )
for(int j = 0; j ) {
ll now = sum[i] - sum[j];
if((now & (1LL 1))) == 0 && (ans | (now >> len)) == ans)
chkMin(g[i], g[j] + 1);
}
ans 1;
if(g[n] > ed) ans |= 1;
}
}
int main() {
read(n), read(st), read(ed);
for(int i = 1; i ) {
read(a[i]);
sum[i] = sum[i - 1] + a[i];
}
len = 0;
for(ll tmp = sum[n]; tmp > 0; tmp >>= 1) ++len;
if(st != 1) solve1();
else solve2();
printf("%lld\n", ans);
return 0;
}
View Code
Luogu 3646 [APIO2015]巴厘岛的雕塑
标签：getch mes \n color view str temp img ||
原文地址：https://www.cnblogs.com/CzxingcHen/p/9831699.html
评论