D
一张无限行，$N$ 列的直方图，$(i,j)$ 表示左数第 $i$ 列，下数第 $j$ 行的方格，第 $i$ 列高度 $h_i$ ，将每个的小方格染上红蓝色，使对于整个方格表的任意一个 $2\times 2$ 的子矩形，若四个小方格均存在，则颜色为 二红二蓝
这个好像有 $O(n)$ 的笛卡尔树做法，但我没看懂qwq
设 $h=\min\{h_i\}$ ，将直方图分成 $h\times N$ 的完全网格图以及若干子直方图
容易想到分治做法
先考虑完全网格图：对于最底层，有 $2^N$ 种方案，其中：
综上，对于完全网格图有 $2^N+2^h-2$ 种
在考虑存在子直方图的情况：
由上面可以得到，最底层是否有相邻同色格是一个关键信息
分治的最终要统计两个信息：$f_A$ 表示最底层任意两个格子不同色的方案数，$f_C$ 表示染色方案总数
设子直方图的结果为 $(u_A,u_C),(v_A,v_C)…$
则所有子直方图有 $u_A\times v_A\times …$ 种选择，则 $f_A=2^h\times u_A\times v_A$
再考虑 $f_C$ ：
设 $R_0$ 为完全网格图最上面一行中存在相邻两个方格同色的方案数，对于该方案，完全网格图的染色方法唯一，则 $f_C=R_0+2\times f_A$
此时只考虑这最上面一行的情况
设子直方图 $u$ 范围 $[l,r]$ ，考虑其所在的方格如何填充
对于 $u_A-u_C$ 种方案(存在相邻同色格)，只有一种填法；而对于 $u_C$ 种方案(任意相邻不同色)，下面有 $2$ 种，则，$r-l+1$ 个小方块共有 $u_A-u_C+2\times u_C=u_A+u_C$ 种填法
再考虑 $h_i=h$ 的方格，显然填法任意，方案数 $2^W$ ，其中 $W$ 是满足 $h_i=h$ 的方格数
最后再减去 $2\times u_A\times v_A…$ 种相邻方格不同色的方案
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
| const int mod=1e9+7;
inline void add(int &x,const int y){ x+=y-mod,x+=x>>31&mod;}
inline void sub(int &x,const int y){ x-=y,x+=x>>31&mod;}
inline ll qpow(ll a,int n,ll c=1){ for(;n;n>>=1,a=a*a%mod) if(n&1) c=c*a%mod;return c;}
PII solve(const vector<int> &h){
int j=-1;
rei n=h.size(),x,y=0,P1=1,P2=1,C1,C2,W=n;
vector<int> S; x=*std::min_element(h.begin(),h.end());
for(rei i=0;i<=n;++i)
if(i==n || h[i]==x){
if(j+1==i) ++j;
else if(j+2==i) ++j,P1=qpow(2,h[j]-x,P1),P2=qpow(2,h[j]-x,P2),++j;
else{
W-=i-j-1,S.clear(),S.reserve(i-j-1);
for(++y;++j<i;S.emplace_back(h[j]-x));
std::tie(C1,C2)=solve(S),P1=(ll)P1*(C1+C2)%mod,P2=(ll)P2*C2%mod;
}
}
C2=qpow(2,x,P2),C1=qpow(2,W,P1),sub(C1,P2),sub(C1,P2);
return add(C1,C2),PII(C1,C2);
}
int main(){
int n,x;vector<int> h;
scanf("%d",&n),h.reserve(n);
for(rei i=0;i<n;++i) scanf("%d",&x),h.emplace_back(x);
printf("%d\n",solve(h).first);
getchar(),getchar();
return 0;
}
|
E
长度为 $2\times n$ 的字符串 $S$ 由 $n$ 个 $a$ 和 $n$ 个 $b$ 构成，选择一个 $S$ 的子序列满足 $\forall 1\leq i\leq n$ ，$S$ 中第 $i$ 个出现的 $a$ 和 $S$ 中第 $i$ 个出现的 $b$ 要么都选，要么都不选，按照原顺序连接字符，求出字典序最大的一个
设 $a_i$ 为 $a$ 第 $i$ 次出现，$b_i$ 同理
设法将字符串分为尽可能多的部分是每一部分 $ab$ 出现次数相同
对于每一部分：
$\forall i,a_i<b_i$
考虑原串中两个相邻的 $a$ ：$a_ia_j…b_i…b_j$ ，发现去掉 $a_j,b_j$ 会更优，贪心计算能得到的 $ab$ ，即，先选择 $a_1,b_1$ ，再找第一个满足 $a_i>b_1$ 的 $i$ ，如此迭代
$\forall i,a_i>b_i$
假设选择 $a_i,b_i$ 那么总可以选择 $a_{i+1},b_{i+1}$ 使答案更优，枚举 $i$ 即可
考虑对于多个部分：
先对每一部分求出最优解，对于每一部分，要么选择最优解，要么为空串，($a_i>b_i$ 时) 所有可得到的串(baba..)都不是最优串的前缀
选择一个串的条件时其大于等于之后所有串拼起来时长度与其相同的前缀
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
| const int N=3e3+100;
int n,a[N],b[N],bel[N<<1];
char s[N<<1];
string ans;
void sol(int L,int R){
string res;
rei l=1; while(a[l]<L) ++l;
rei r=n; while(a[r]>R) --r;
if(s[L]=='a'){
rei cnt=1,k=l;
for(rei i=l;i<=r;++i) if(a[i]>b[k]) ++cnt,k=i;
while(cnt--) res.push_back('a'),res.push_back('b');
}
else{
for(rei i=l;i<=r;++i){
string now;
for(rei j=b[i];j<=R;++j) if(bel[j]>=i) now.push_back(s[j]);
res=max(res,now);
}
}
ans=max(ans,res+ans);
}
int main(){
scanf("%d",&n); scanf("%s",s+1);
for(rei i=1,x=0,y=0;i<=(n<<1);++i){
if(s[i]=='a') a[++x]=i,bel[i]=x;
else b[++y]=i,bel[i]=y;
}
for(rei i=(n<<1),cnt=0,last=(n<<1);i;--i){
s[i]=='a' ? ++cnt : --cnt;
if(!cnt) sol(i,last),last=i-1;
}
cout<<ans<<endl;
getchar(),getchar();
return 0;
}
|
F
$n$ 个物品 ，每个价值 $a_i$ ，$AB$ 轮流取，先手任意取(设 $x$)，后手可以取任意一个相邻的物品，设取 $x+1$ ，则两人将轮流往右取直到取至尽头，此时的先手重新选取一个点继续，直至所有都被取走，每取完一个物品后重新标号，两人均想让自己的物品价值最大，求最优策略下两人各获得的价值
这里有一个神奇的贪心/博弈：即，在任意时刻，先手始终会最优
从这个结论出发，考虑先手的选择：
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
| const int N=3e5+100;
int n,a[N],s[N];
inline int check(int mid){
rei MIN=0;
for(rei i=1;i<=n/2+1;++i)
if(s[i]+a[i*2]-MIN>=mid) MIN=min(MIN,s[i]);
else if(i==n/2+1) return 0;
return 1;
}
int main(){
scanf("%d",&n);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
if(n&1){
for(rei i=1;i<=n/2+1;++i) s[i]=s[i-1]+a[2*i-1]-a[2*i];
rei l=-1e9,r=1e9,ans=-1e9;
while(l<=r){
rei mid=l+r>>1;
check(mid) ? (ans=mid,l=mid+1) : r=mid-1;
}
rei sum=-s[n/2+1]+ans*2,s0=0;
for(rei i=1;i<=n;++i) s0+=a[i];
printf("%d %d\n",(sum+s0)/2,(s0-sum)/2);
}else{
rei s1=0,s2=0;
for(rei i=1;i<=n;i+=2) s1+=a[i],s2+=a[i+1];
if(s1<s2) swap(s1,s2);
printf("%d %d\n",s1,s2);
}
getchar(),getchar();
return 0;
}
|