T1
题意简述
给定一串长度为 \(n\) 的 01 串，且第 \(1\) 位保证为 \(1\)。给定下界和上界的二进制形式，分别为 \(L\) 数组和 \(R\) 数组（长度均为 \(n\)），问：在正好反转 \(k\) 次不同的后缀的后，形成的二进制所对应的数在上下界之内的，的和为多少。（对 \(1e9+7\) 取模）（可以将原串整体反转一次，不计入反转次数）。
\(2 \le n \le 1000\)
\(0 \le k < n\)
思路
数位 DP。
设 \(dp_{i,j,l,r}\) 表示，当前处理到第 \(i\) 位，现在要反转第 \(j\) 次。当前是否贴着下界或者上界。
转移的时候，枚举这四维，设枚举状态为 \(dp_{i,j,p,q}\)，然后大部分就是正常 DP 过程了，转移的时候，先确定当前这个位置是 \(0\) 还是 \(1\)，设为 \(now\)。再看这个位置是否不在上下界的范围内，即：如果 \((now < L[i] \cap p) \cup (now > R[i] \cap q)\) ，那么就是非法的。
转移的时候，转移到的状态的下界和上界情况就应该分别是 \(p \cap (now=L[i])\) 和 \(q \cap (now=R[i])\)，设为 \(P\) 和 \(Q\)，转移的时候，因为是要求满足范围的和，因此我们还需要定义一个 \(cnt\) 辅助数组。他的状态和 \(dp\) 数组是一样的，不过记录的是，满足范围的数的个数。在我们转移到下一位的时候，需要乘上 \(2\)，若这一位是 \(1\) 的时候，我们就需要加上 \(cnt\) 了，因为可能有多个数都是满足范围的。
这一位是可以选择反转一次也是可以不反转的。因此我们的总的 dp 转移就应该是：
\[ dp_{i,j,P,Q} = dp_{i,j,P,Q} + dp_{i-1,j,p,q} \times 2 + now \times cnt_{i-1,j,p,q} \]
当 \(j \ge 1\) 的时候，还有：
\[ dp_{i,j,P,Q} = dp_{i,j,P,Q} + dp_{i-1,j-1,p,q} \times 2 + now \times cnt_{i-1,j-1,p,q} \]
注意初始值：\(cnt_{0,0,1,1}=1\)
统计答案则是 \(dp_{n,k,0,0} + dp_{n,k,0,1} + dp_{n,k,1,0} + dp_{n,k,1,1}\)
因为整个串还可以反转一次，所以我们将原串除了第一位反转一次后，再跑一次，最终就是答案啦！
时间复杂度 \(O(nk)\)
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e3+10;
const int mod=1e9+7;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
x=0;
bool f=false;
char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
read(x),read(y...);
}
int n,k,ans,dp[MAXN][MAXN][2][2],cnt[MAXN][MAXN][2][2];
string s,l,r;
bool S[MAXN],L[MAXN],R[MAXN];
void solve(){
memset(dp,0,sizeof(dp));
memset(cnt,0,sizeof(cnt));
cnt[0][0][1][1]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
int now=S[i]^(j&1);
for(int p=0;p<2;p++){
for(int q=0;q<2;q++){
if((p&now<L[i])||(q&now>R[i])) continue;
bool awa=p&now==L[i];
bool qwq=q&now==R[i];
dp[i][j][awa][qwq]=(dp[i][j][awa][qwq]+dp[i-1][j][p][q]*2+now*cnt[i-1][j][p][q])%mod;
cnt[i][j][awa][qwq]=(cnt[i][j][awa][qwq]+cnt[i-1][j][p][q])%mod;
if(j>0){
dp[i][j][awa][qwq]=(dp[i][j][awa][qwq]+dp[i-1][j-1][p][q]*2+now*cnt[i-1][j-1][p][q])%mod;
cnt[i][j][awa][qwq]=(cnt[i][j][awa][qwq]+cnt[i-1][j-1][p][q])%mod;
}
}
}
}
}
for(int i=0;i<2;i++) for(int j=0;j<2;j++) ans=(ans+dp[n][k][i][j])%mod;
}
signed main(){
cin>>n>>k>>s>>l>>r;S[1]=1;
for(int i=2;i<=n;i++) S[i]=s[i-2]=='R';
for(int i=1;i<=n;i++) L[i]=l[i-1]=='1';
for(int i=1;i<=n;i++) R[i]=r[i-1]=='1';
solve();
for(int i=2;i<=n;i++) S[i]^=1;
solve();
cout<<ans;
return 0;
}T2
题意简述
给定一个 \(n\) 个数的序列 \(a\)，要求从中选出任意多个数，并且相邻的两个数的距离不得超过 \(k\)，有一些数必须选，现有 \(q\) 操作，每次将序列中的某个数改变（询问独立），问每次操作完后，所有合法的选择中的数之和最小为多少。
\(1 \le n \le 2 \times
10^{6}\)
\(1 \le k \le \min{(n+1,3000)}\)
\(1 \le q \le 3000\)
值域 \(10^{9}\)
思路
容易想到 \(O(qnk)\) 的做法
设计 DP 为 \(dp_{i}\)
表示当前考虑到了第 \(i\) 个数。
转移很显然为
\[ dp_{i} = (\textstyle \min^{i-1}_{j=\max(1,i-k)} dp_{j})+a_{i} \]
若在枚举范围内有必须选的，那就直接从必须选的位置转移即可。注意倒序枚举。
考虑怎么优化这个式子，取 \(\min\) 可以用单调队列来实现。这样的话，时间复杂度就变为了 \(O(nq)\)。
但现在依然无法通过，注意到 \(k\) 的范围比较小，我们可以考虑和 \(k\) 有关的时间复杂度。
考虑修改了一个数后，对答案的变化有什么影响。设更改后的值为 \(v\)，原本的值为 \(w\)
分两种情况：
- 发生了影响，那此时答案应变为原来答案加上 \(v-w\)。
- 没发生影响，那么答案应变为从 \(\max(i-k,1)\) 到 \(i-1\) 中的 DP 值，加上从 \(i+1\) 到 \(\min(i+k,n)\) 的DP 值的最小值，注意需要满足两者的差小于等于 \(k\) 的条件。
若当前修改的位置是必须选的，那么就没有第二种情况了。
第一个是简单的，第二个可以通过单调队列来实现。
先将所有的 \(dp_{\max(i-k,1)}\) 到
\(dp_{i-1}\)
加入一个单调队列，然后依次枚举右边的点，若距离大于了 \(k\)，那么就出队，对于每一个右端点对应的左端点中最小的和取
\(min\) 就是答案了。
时间复杂度 \(O(n+qk)\)。
代码
没有代码 awa
T3
目前依然只会 \(75pts\) 的场上做法，不过场上写错了点，挂成了 \(5pts\) xwx。似乎再小小优化一下就成了 \(100pts\) 了？
题意简述
给你一堆有向简单环（可能有自环），点的数量为 \(n\)，保证每个点都在任意一个环中。再给定一个权值数组 \(a\)，现在你需要给环上的每个点赋值，使得所有点指向的点的权值之差的绝对值的最大值尽可能小，输出这个最小值以及赋值方案，若方案不唯一，输出任意一种即可。
\(1 \le n \le 150\)
\(0 \le a_{i} \le 10^{9}\)
思路
考虑怎么求得答案先。
更优的策略一定是，先对 \(a\)
数组排序，然后每个环绝对选的是一段连续的区间。（我也不知道怎么证明xwx）
选了一段区间后，怎么安排使得得出答案呢？肯定不会按从前往后的顺序来安排，这样的话，就会出现最大值减去最小值的情况，这是不优的。我们应该这样：（设区间左端点为
\(l\)，右端点为 \(r\)）
- 区间长度为奇数：\(l,l+2,l+4,\dotsb,r-2,r,r-1,r-3,\dotsb,l+1\)
- 区间长度为偶数：\(l,l+2,l+4,\dotsb,r-1,r,r-2,r-4,\dotsb,l+1\)
注意到环的个数大概率不会很大。
因此考虑状压 DP。
设 \(dp_{s}\) 表示当前选择了 \(s\)
这个集合的环。转移时，枚举没有选择过的环，转移即可，注意新的 \(dp_{s}\)
应该在所有可以转移到它的状态中与这段区间的差的绝对值的最大值取 \(\max\)，再整体取 \(\min\)。
思路还是很简单的。
虽然只需要全部为自环之类的就可以卡掉，但考虑到数据不可能全是自环，所以预估分数会更高一些。理论上只能有 \(35pts\)，但实际上有 \(75pts\)。
代码
#include<bits/stdc++.h>
using namespace std;
int read(){
int res=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
res=res*10+ch-'0';
ch=getchar();
}
return res*f;
}
const int MAXN=150+10;
const int mod=998244353;
int n,cnt,a[MAXN],b[MAXN],ans[MAXN],val[MAXN][MAXN],dp[1<<25],pre[1<<25];
vector<int> cycle[MAXN];
bool vis[MAXN];
int k,head[MAXN];
struct node{
int to,next;
}edge[MAXN<<1];
void build(int u,int v){
edge[++k].to=v;
edge[k].next=head[u];
head[u]=k;
}
void dfs(int u){
vis[u]=true;
cycle[cnt].push_back(u);
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]) continue;
dfs(v);
}
}
signed main(){
// freopen("apples.in","r",stdin);
// freopen("apples.out","w",stdout);
// freopen("3.in","r",stdin);
n=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) build(i,b[i]);
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
cnt++;
}
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if((j-i+1)&1){
for(int q=i+2;q<=j;q+=2) val[i][j]=max(val[i][j],abs(a[q]-a[q-2]));
for(int q=j-3;q>=i+1;q-=2) val[i][j]=max(val[i][j],abs(a[q]-a[q+2]));
}
else{
for(int q=i+2;q<=j-1;q+=2) val[i][j]=max(val[i][j],abs(a[q]-a[q-2]));
for(int q=j-2;q>=i+1;q-=2) val[i][j]=max(val[i][j],abs(a[q]-a[q+2]));
}
if(j-1>=i) val[i][j]=max(val[i][j],abs(a[j]-a[j-1]));
if(i+1<=j) val[i][j]=max(val[i][j],abs(a[i]-a[i+1]));
}
}
for(int i=0;i<(1<<cnt);i++) dp[i]=2e9;
dp[0]=0;
for(int i=1;i<(1<<cnt);i++){
int pos=0;
for(int j=0;j<cnt;j++) if(i&(1<<j)) pos+=cycle[j].size();
for(int j=0;j<cnt;j++){
if(i&(1<<j)){
int cache=max(dp[i-(1<<j)],val[pos-cycle[j].size()+1][pos]);
if(dp[i]>cache){
dp[i]=cache;
pre[i]=i-(1<<j);
}
}
}
}
cout<<dp[(1<<cnt)-1]<<endl;
int z=(1<<cnt)-1,pos=n;
while(z){
for(int j=0;j<cnt;j++){
if((z&(1<<j))!=(pre[z]&(1<<j))){
int l=pos-cycle[j].size()+1,r=pos,tot=0;
if(cycle[j].size()&1){
for(int q=l;q<=r-2;q+=2,tot++) ans[cycle[j][tot]]=a[q];
ans[cycle[j][tot++]]=a[r];
for(int q=r-1;q>=l+1;q-=2,tot++) ans[cycle[j][tot]]=a[q];
}
else{
for(int q=l;q<=r-1;q+=2,tot++) ans[cycle[j][tot]]=a[q];
ans[cycle[j][tot++]]=a[r];
for(int q=r-2;q>=l+1;q-=2,tot++) ans[cycle[j][tot]]=a[q];
}
pos-=cycle[j].size();
}
}
z=pre[z];
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}T4
依然只会 \(O(n^{2})\) 的暴力做法，\(28pts\)
正解为 点分治+BIT维护二维数点+容斥。
我还是简述一下题意吧 xwx
题意简述
给定一颗 \(n\) 个点的无根树，每个点有三个权值 \(a_{i},d_{i},c_{i}\)，每次的时候，选择一个点 \(s\) 开始，设初始值为 \(D=d_{s}\)，你每次只能去当前你所在的点中的相邻的点中 \(D \le d_{j}\) 的点，到达 \(j\) 这个点后，\(D\) 会增加 \(d_{j}\)。若你当前所在的点的 \(a_{j} \ge a_{i}\)，你可以选择停下。问所有能停下的点的 \(a_{i}\) 之和。需要对 \(s \in [1,n]\) 求出答案。
思路
暴力很简单吧，\(n\) 次 DFS 即可，\(28pts\)。
然后就不会了……
好了，那就到这里了，拜拜awa