LOJ - 6515 「雅礼集训 2018 Day10」贪玩蓝月
\(\text{Description}\)
传送门
\(\text{Solution}\)
你会发现题目就是让你维护一个 "可撤销" 的 \(01\) 背包。不过背包应该是不能撤销的。也有可能是我太鶸了。
我们可以根本不撤销 —— 线段树分治。只需要算出每件装备的存在区间，插入线段树上即可。每件装备只用插入 \(\mathcal O(\log m)\) 次，单次查询是 \(\mathcal O(p)\) 的。总共是 \(\mathcal O(pm\log m)\) 的。听上去好像挺卡的。
或者，选用一个撤销代价不那么大的做法。
考虑用两个栈维护两端的插入。
插入时将新装备加入对应栈的背包。删除就直接删。如果一个栈删完了就需要将另一个栈内元素分成两半，再重新插入和计算背包。
单次查询可以用 \(\rm st\) 表将两个栈拼起来，是 \(\mathcal O(p\log p)\) 的。重要的是分析删除的复杂度：如果用 \(\mathcal O(xp)\) 的时间复杂度将 \(x\) 个元素重新插入两个栈里，那么至少再删除 \(x/2\) 次才能够激发新的重构，我们将这两个操作捆绑在一起考虑，所以重构复杂度是 \(\mathcal O(mp)\) 级别的。
\(\text{Code}\)
#include
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define print(x,y) write(x),putchar(y)
template inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
#include
#include
using namespace std;
typedef long long ll;
const int maxm=5e4+5,maxp=505;
int m,mod,tp[2],a,b,lg[maxp];
char op[5];
ll f[2][maxm][maxp],st[maxp][11],ans;
struct node {
int w,v;
} sta[2][maxm];
ll Ask(int l,int r) {
int len=lg[r-l+1];
return max(st[l][len],st[r-(1<=0) {
l=a-i,r=b-i;
if(l<0) l+=mod;
if(r<0) r+=mod;
if(l<=r) ans=max(ans,f[0][tp[0]][i]+Ask(l,r));
else ans=max(ans,f[0][tp[0]][i]+max(Ask(l,mod-1),Ask(0,r)));
}
print(ans,'\n');
}
void Insert(bool x,int a,int b) {
sta[x][++tp[x]]=(node){a,b};
int j;
rep(i,0,mod-1) {
j=(i+a>=mod?i+a-mod:i+a);
f[x][tp[x]][j]=max(f[x][tp[x]-1][j],f[x][tp[x]-1][i]+b);
}
}
void Delete(bool x) {
if(tp[x]) return (void)(--tp[x]);
int mid=tp[x^1]+1>>1;
// 此处 mid 取大于等于 1/2，是为了保证至少拿出一件物品
fep(i,mid,2) Insert(x,sta[x^1][i].w,sta[x^1][i].v);
int tmp=tp[x^1]; tp[x^1]=0;
rep(i,mid+1,tmp) Insert(x^1,sta[x^1][i].w,sta[x^1][i].v);
}
int main() {
read(9),m=read(9),mod=read(9);
memset(f,192,sizeof f);
f[0][0][0]=f[1][0][0]=0;
rep(i,2,mod) lg[i]=lg[i>>1]+1;
while(m--) {
scanf("%s",op);
if(op[0]=='I') a=read(9)%mod,b=read(9),Insert(op[1]=='G',a,b);
else if(op[0]=='D') Delete(op[1]=='G');
else Query();
}
return 0;
}
\(\text{I love Wordle!!!}\)
见缝插针。
I guessed this 5-letter word in 3/6 tries.
???????
????????
??????????
Can you guess this word?