A
判断一下前面能否空出来就就行,也就是 $l \geq r-l+1$。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
int main(){
int T;scanf("%d",&T);
while(T--){
int l,r;scanf("%d%d",&l,&r);
puts(l >= r-l+1 ? "YES" : "NO");
}
return 0;
}
B
相当于不能有子串 11
和 00
。
那么如果有 11
肯定在后面有一个地方有 00
(反证),所以每次操作最多可以消去两个这样的连续的东西,求出有多少个相邻相同的位置 $x$,答案就是 $\lceil \frac{x}{2} \rceil$。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 + 5;
char str[MAXN];
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
scanf("%s",str+1);
int ans = 0;
FOR(i,2,n) if(str[i] == str[i-1]) ans++;
ans = (ans+1)>>1;
printf("%d\n",ans);
}
return 0;
}
C
首先可以发现一个东西:将匹配方式连边,一定存在一种分配方式使得最优解没有包含关系的线段,因为包含关系可以通过交换变成相交,并且代价不变。
排序后可以设 $f_{i,j}$ 表示考虑了前 $i$ 个数,最小的 $j$ 满足 $j$ 开始后面一段数字都没有被用过的代价,转移直接枚举下一个填啥就行了。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 600+5;
int n,a[MAXN];
bool vis[MAXN];
int f[2][MAXN],now;
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
FOR(i,1,n) scanf("%d",a+i);
std::sort(a+1,a+n+1);
CLR(f,0x3f);
f[now = 0][0] = 0;
FOR(i,1,n){
CLR(f[now^1],0x3f);
FOR(j,0,3*n){
if(f[now][j] == 0x3f3f3f3f) continue;
FOR(k,j+1,3*n){
f[now^1][k] = std::min(f[now^1][k],f[now][j]+std::abs(a[i]-k));
}
}
now ^= 1;
}
int ans = 1e9;
FOR(i,1,3*n) ans = std::min(ans,f[now][i]);
printf("%d\n",ans);
}
return 0;
}
D
感性理解一下,我们每次取出深度最小的点,接上连续的一段递增序列作为它的后继即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e5 + 5;
int n,a[MAXN];
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i);
std::priority_queue<P,std::vector<P>,std::greater<P> > q;
q.push(MP(0,1));int p = 2;
int ans = 0;
while(!q.empty()){
int dep = q.top().fi;q.pop();ans = std::max(ans,dep);
int las = -1;std::vector<int> v;
while(p <= n && las <= a[p]) las = a[p++],v.pb(las);
for(auto x:v) q.push(MP(dep+1,x));
}
printf("%d\n",ans);
}
return 0;
}
E
如果没有不能选的限制就是经典 dp:我们观察两个位置 $i<j$ 能同时不改变的条件是 $a_j-a_i-1 \geq j-i-1$,也就是 $a_i-i \leq a_j-j$,最多能不修改的数也就是设 $b_i=a_i-i$,$b_i$ 的非严格最长上升子序列长度。
这个题限定某些数不能改变,先判完无解后相当于变成了强制选取某些位置的最长上升子序列,对于每段分别做即可。
注意这里 infty
开大点。。要不然判无解会判错。。。真正考试对拍的时候还是多试试 corner case 吧。。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5e5 + 5;
int n,k;
LL a[MAXN];
std::vector<int> S;
std::vector<LL> SS;
struct BIT{
#define lowbit(x) ((x)&(-(x)))
int tree[MAXN],ts[MAXN],now;
inline void reset(){
++now;
}
inline void add(int pos,int x){
while(pos < MAXN){
if(ts[pos] != now) tree[pos] = 0,ts[pos] = now;
tree[pos] = std::max(tree[pos],x);
pos += lowbit(pos);
}
}
inline int query(int pos){
int res = 0;if(!pos) return 0;
while(pos){
if(ts[pos] != now) tree[pos] = 0,ts[pos] = now;
res = std::max(res,tree[pos]);
pos -= lowbit(pos);
}
return res;
}
}bit;
int b[MAXN];
int main(){
scanf("%d%d",&n,&k);
FOR(i,1,n) scanf("%d",a+i);
a[0] = -1e18;a[n+1] = 1e18;
FOR(i,0,n+1) SS.pb(a[i]-i);
std::sort(all(SS));SS.erase(std::unique(all(SS)),SS.end());
FOR(i,0,n+1) b[i] = std::lower_bound(all(SS),a[i]-i)-SS.begin()+1;
S.pb(0);
FOR(i,1,k){
int x;scanf("%d",&x);
S.pb(x);
}
S.pb(n+1);
FOR(i,1,(int)S.size()-1){
if(a[S[i]]-a[S[i-1]] < S[i]-S[i-1]){
puts("-1");
return 0;
}
}
int ans = 0;
FOR(i,1,(int)S.size()-1){
auto work = [&](int l,int r){
bit.reset();
int res = 0;
FOR(i,l,r){
if(b[i] < b[l]) continue;
res = bit.query(b[i])+1;
bit.add(b[i],res);
}
return r-l+1-res;
};
ans += work(S[i-1],S[i]);
}
printf("%d\n",ans);
return 0;
}
F
居然让我想了一会。。不过也是简单题
直接做我们可能需要记录哪些数选了,状态会爆炸。我们考虑不断往后面加数,如果这个序列的最大值确定了,那么这个序列不改变最大值的前提下的最大长度就确定了,如果知道了目前长度,我们就能知道不改变最大值前提下这个位置的数有多少种可能。
于是设 $f_{i,j}$ 表示放了 $i$ 个数,最大值是 $j$ 的方案数,预处理 $las_i$ 表示最大值是 $i$ 的时候序列的最长长度,$nxt_i$ 表示最大值是 $i$ 要改变最大值可以放的最小的数,$cnt_i$ 表示值为 $i$ 的数的个数,转移:
- 不改变最大值:$f_{i,j}\times (las_j-i+1) \to f_{i+1,j}$
- 改变最大值:$f_{i,j}\times cnt_k \to f_{i+1,k}(k \geq nxt_j)$
用一些前缀和技巧可以优化到 $O(n^2)$。
看了一个比较 nb 的做法,大概是我们 dp 的时候只在放满的时候转移(也就是最大值为 $j$ 的时候我们只考虑状态 $f_{las_j,j}$),这个就是设 $f_i$ 表示最大值为 $i$ 的方案数,这样长度就是 $las_i+1$,转移的时候枚举上一次的最大值,乘上一个系数选进去就行了。
$$ \begin{aligned} f_i &= \sum_j f_j\binom{n-las_j-2}{las_i-las_j-1}(las_i-las_j-1)!\\ &= \frac{1}{(n-las_i-1)}\sum_j f_j (n-las_j-2)! \end{aligned} $$
然后前缀和优化一下就 $O(n)$ 了。还是要考虑大多数 dp 状态都是无用的,只对真正有用的决策即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5000+5;
const int ha = 998244353;
int a[MAXN],n;
int f[2][MAXN],cf[MAXN];
// 选了 i 个数 最大值是 j
std::vector<int> S;
int las[MAXN];// 选了 i 之后 还有几个数可以放
int nxt[MAXN];// 选了 i 之后 下一个必须选啥
int cnt[MAXN];
inline void add(int &x,int y){
x += y-ha;x += x>>31&ha;
}
int main(){
scanf("%d",&n);
FOR(i,1,n) scanf("%d",a+i);
std::sort(a+1,a+n+1);
FOR(i,1,n) S.pb(a[i]);S.erase(std::unique(all(S)),S.end());
FOR(i,1,n) cnt[std::lower_bound(all(S),a[i])-S.begin()+1]++;
int m = S.size();
FOR(i,1,m){
las[i] = las[i-1];
while(las[i]+1 <= n && a[las[i]+1]*2 <= S[i-1]) las[i]++;
}
nxt[0] = 1;
FOR(i,1,m){
nxt[i] = -1;
FOR(j,i+1,m){
if(S[i-1]*2 <= S[j-1]) {nxt[i] = j;break;}
}
}
int now = 0;f[now][0] = 1;
FOR(i,1,n){
CLR(f[now^1],0);CLR(cf,0);
FOR(j,0,m){
if(!f[now][j]) continue;
int t = las[j]-i+1+1;
if(j == 0) t = 0;
if(t > 0) add(f[now^1][j],1ll*f[now][j]*t%ha);
if(nxt[j] != -1) add(cf[nxt[j]],f[now][j]);
}
FOR(j,1,m) add(cf[j],cf[j-1]),add(f[now^1][j],1ll*cf[j]*cnt[j]%ha);
now ^= 1;
// FOR(i,0,m) printf("%d ",f[now][i]);puts("");
}
printf("%d\n",f[now][m]);
return 0;
}
G
建 AC 自动机,我们枚举询问串的每一个后缀,走到对应的节点上,这个串的子串就是 fail 树的祖先,所以相当于要支持单点修改,查询到根的一条链上的最大值,树剖即可。$O(n \log^2 n)$。
题解做法一:我们发现对于一个点,它在 fail 树上到根的路径上终止节点最多有 $O(\sqrt n)$ 个(因为 $\sum_{i=1}^n i = O(n^2)$),所以记录一下每个点上面距离最近的终止节点,暴力跳就好了。$O(q\sqrt n)$。
一个比较 nb 的离线单 log 做法:先把询问和修改挂在树上,我们经过一个点 apply 它的所有操作,现在只有了操作时间的限制,我们用一个线段树,第 $i$ 个位置维护操作时间为 $i$ 的答案,不难发现要支持区间对一个数取 $\max$,撤销,单点求值。因为只需要单点求值,搞个标记永久化就好了,这样就只会改变 $O(\log n)$ 个节点,可以存下来了。这种线段树+撤销都可以考虑下标记永久化...
#include <bits/stdc++.h>
#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 3e5 + 5;
int ch[MAXN][26],fail[MAXN],tot = 1,rt = 1;
int ps[MAXN];
inline void insert(char str[],int id){
int len = strlen(str+1),v = rt;
FOR(i,1,len){
int o = str[i]-'a';
if(!ch[v][o]) ch[v][o] = ++tot;
v = ch[v][o];
}
ps[id] = v;
}
std::vector<int> G[MAXN];
inline void build(){
std::queue<int> q;
FOR(i,0,25){
if(ch[rt][i]) q.push(ch[rt][i]),fail[ch[rt][i]] = rt;
else ch[rt][i] = rt;
}
while(!q.empty()){
int v = q.front();q.pop();
FOR(i,0,25){
if(ch[v][i]) q.push(ch[v][i]),fail[ch[v][i]] = ch[fail[v]][i];
else ch[v][i] = ch[fail[v]][i];
}
}
FOR(i,2,tot) G[fail[i]].pb(i);
}
int mx[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)
inline void update(int x,int l,int r,int p,int d){
if(l == r){
mx[x] = d;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(lc,l,mid,p,d);
else update(rc,mid+1,r,p,d);
mx[x] = std::max(mx[lc],mx[rc]);
}
inline int query(int x,int l,int r,int L,int R){
if(l == L && r == R) return mx[x];
int mid = (l + r) >> 1;
if(R <= mid) return query(lc,l,mid,L,R);
if(L > mid) return query(rc,mid+1,r,L,R);
return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R));
}
int dfn[MAXN],sz[MAXN],tp[MAXN],fa[MAXN],son[MAXN];
inline void dfs1(int v){
sz[v] = 1;
for(auto x:G[v]){
fa[x] = v;
dfs1(x);sz[v] += sz[x];
if(sz[son[v]] < sz[x]) son[v] = x;
}
}
inline void dfs2(int v,int tp=1){
static int ts = 0;dfn[v] = ++ts;::tp[v] = tp;
if(son[v]) dfs2(son[v],tp);
for(auto x:G[v]){
if(x == son[v]) continue;
dfs2(x,x);
}
}
inline int query(int x){
int res = -1;
while(tp[x] != 1){
res = std::max(res,query(1,1,tot,dfn[tp[x]],dfn[x]));
x = fa[tp[x]];
}
res = std::max(res,query(1,1,tot,dfn[1],dfn[x]));
return res;
}
int n,m;
std::multiset<int> S[MAXN];
int val[MAXN];
char str[MAXN];
int main(){
scanf("%d%d",&n,&m);
CLR(mx,-1);
FOR(i,1,n){
scanf("%s",str+1);
insert(str,i);
S[ps[i]].insert(0);
}
build();
dfs1(1);dfs2(1);
FOR(i,1,n) update(1,1,tot,dfn[ps[i]],*S[ps[i]].rbegin());
while(m--){
int opt;scanf("%d",&opt);
if(opt == 1){
int p,x;scanf("%d%d",&p,&x);
S[ps[p]].erase(S[ps[p]].find(val[p]));
val[p] = x;
S[ps[p]].insert(val[p]);
update(1,1,tot,dfn[ps[p]],*S[ps[p]].rbegin());
}
else{
scanf("%s",str+1);int len = strlen(str+1);
int v = 1,res = -1;
FOR(i,1,len){
v = ch[v][str[i]-'a'];
res = std::max(res,query(v));
}
printf("%d\n",res);
}
}
return 0;
}