ドキュメント
ylx 依舊在自言自語的講課。感覺 SDUT 裏好吃的地方都去過了。
今天是 bct NOIP Day 6，賽時 \(100+10+20+10=140\)，rk 27。
T4 不會手寫 bitset 被區分了，於是學了學。
sheep 説 T2 是典完了的連通性容斥，我咋不知道啊。
評價是 ok 場。其實 T2 原本是 T1 來着，ylx 被壓力的才加的題。
T1
把要記的都扔進狀態裏 DP 即可，轉移時還要容斥一下。
code
Show me the code
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef __int128 i128;
#define ls p*2
#define rs p*2+1
const int N=400;
const int mod=998244353;
int dp[N][N][N];
int main(){
freopen("qwq.in","r",stdin);
freopen("qwq.out","w",stdout);
string a,b,c;
cin>>a>>b>>c;
int len=c.size();
int l1=a.size();
int l2=b.size();
a=' '+a;
b=' '+b;
c=' '+c;
for(int i=0;i<=l1;i++)for(int j=0;j<=l2;j++)dp[i][j][0]=1;
for(int i=1;i<=l1;i++)for(int j=1;j<=l2;j++){
for(int p=1;p<=min(min(i,j),len);p++){
dp[i][j][p]=(0ll+dp[i-1][j][p]+dp[i][j-1][p]-dp[i-1][j-1][p]+mod)%mod;
if(c[p]=='<'&&a[i]<b[j]){
dp[i][j][p]=(0ll+dp[i][j][p]+dp[i-1][j-1][p-1])%mod;
}
if(c[p]=='>'&&a[i]>b[j]){
dp[i][j][p]=(0ll+dp[i][j][p]+dp[i-1][j-1][p-1])%mod;
}
}
}
cout<<dp[l1][l2][len];
return 0;
}T2
不想在賽前赤這種東西。放了。
T3
DP 牛牛題。
考慮為什麼花費要定義為 距離乘上價值 狀物，很重要的觀察是當重量 \(k\) 一定時，如果選的東西的距離都至少是 \(d_i\)，那麼選出來的價值和不超過 \(\left \lfloor \dfrac{k}{d_i}\right \rfloor\)
我們又知道揹包的一種常見變體就是如果物品價值很小花費很大，我們會把價值作為狀態來 DP，結果是達到這個價值用的最小代價。
於是這啓發我們分 \(d_i\)
閾值 \(B\) 表示分的大小，\(d_i\le B\) 那就暴力 \(O(k)\) 更新以代價為狀態的 DP 數組。\(d_i > B\) 那就從 \(\left \lfloor \dfrac{k}{d_i}\right \rfloor\) 到 \(v_i\)
後者有時間複雜度上界就是調和級數，\(O(k\log k)\)，前者的時間複雜度顯然是 \(O(kB)\)
對於查詢，首先顯然要時間倒流，因為揹包好加不好刪。
然後枚舉我們想在 \(d_i>B\) 這一塊拿多少價值，再看看剩餘的代價能在 \(d_i\le B\)
能取的價值的上界顯然是 \(\left \lfloor \dfrac{k}{B}\right \rfloor\)，於是查詢的時間複雜度就是 \(q\left \lfloor \dfrac{k}{B}\right \rfloor\)。
再考慮修改，\(d_i > B\) 不管反正有個上界，\(d_i\le B\) 最多就 \(B\) 個，時間複雜度是 \(O(kB)\)。
於是這東西的時間複雜度是 \(O(kB + \frac{kq}{B} + k \log k)\) 的，均值一下取 \(B=\sqrt{q}\)
感謝 sheep 一眼了我代碼的 bug。感覺比 T2 簡單。
code
Show me the code
#define rd read()
#define mkp make_pair
#define ls p<<1
#define rs p<<1|1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef __int128 i128;
i64 read(){
i64 x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
const int N=2e6+612312;
i64 d[N];i64 v[N];i64 dpw[N];i64 dpv[N];i64 ans[N];
struct que{
i64 op;i64 v;i64 qid;
}qm[N];
bitset<N> ext;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>d[i]>>v[i];
ext[i]=1;
}
int bd=sqrt(m)+1;
cerr<<bd<<'\n';
int qc=0;
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
int vk;cin>>vk;
ext[vk]=0;qm[i].op=op;qm[i].v=vk;
}
if(op==2){
int q;cin>>q;
qc++;qm[i].op=op;qm[i].qid=qc;qm[i].v=q;
}
}
memset(dpv,0x7f,sizeof dpv);
dpv[0]=dpw[0]=0;
int d1=0;
for(int i=n;i>=1;i--){
if(ext[i]==0)continue;
if(d[i]>bd){
for(int j=k/d[i];j>=v[i];j--){
dpv[j]=min(dpv[j],dpv[j-v[i]]+v[i]*d[i]);
}
d1=k/d[i];
}
else{
for(int j=k;j>=d[i]*v[i];j--){
dpw[j]=max(dpw[j],dpw[j-d[i]*v[i]]+v[i]);
}
}
}
for(int i=m;i>=1;i--){
int op=qm[i].op;
if(op==1){
int vk=qm[i].v;
i64 cst=v[vk]*d[vk];
if(d[vk]>bd){
d1=max(0ll+k/d[vk],0ll+d1);
for(int j=d1;j>=v[vk];j--){
dpv[j]=min(dpv[j],dpv[j-v[vk]]+cst);
}
}
else{
for(int j=k;j>=cst;j--){
dpw[j]=max(dpw[j],dpw[j-cst]+v[vk]);
}
}
}
if(op==2){
i64 ks=qm[i].v;
i64 anss=0;
for(int j=0;j<=k/bd;j++){
i64 req=ks-dpv[j];
if(req<0)continue;
if(req==0){
anss=max(anss,0ll+j);
}
else anss=max(anss,dpw[req]+j);
}
ans[qm[i].qid]=anss;
}
}
for(int i=1;i<=qc;i++){
cout<<ans[i]<<'\n';
}
return 0;
}T4
學了下手寫 Bitset，過了 30pts 就跑路了。
正解是大分塊，但是我們的常熟大蛇 sheep \(O(nq)\)