2025暑期第一场
G
模拟 数学
给两个01串，问分别从两个位置开始的子串，有多少个子区间完全相同？
注意到这是01串/手玩，可以推出，对于每段相等的最长子区间，长度的话，对答案贡献是
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, b, a) for(int i = b; i >= a; i--)
#define endl "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int MAXN = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr ll INF = 1E18;
void solve() {
int n,q;
cin>>n>>q;
string s;
cin>>s;
rep(i,1,q){
string t;
cin>>t;
int a;
cin>>a;
ll ans=0;
int m=t.size();
int len=0;
for(int j=0;j<m&&j+a-1<n;j++){
if(t[j]==s[j+a-1]){
len++;
}
else{
ans+=1ll*len*(len+1)/2;
len=0;
}
}
ans+=1ll*len*(len+1)/2;
cout<<ans<<'\n';
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
//cin >> T;
T=1;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
H
分块 差分 状压
G的加强版，给一个01串，有区间反转操作，然后选两个子串做G中的询问。
注意到询问次数只有2500，询问的处理可以用暴力一点的方式，关键是优化占比更大的修改操作，这是01串，实际上反转就意味着，并且异或信息是可以差分，然后前缀和还原的，所以每次修改我们只要在修改端点，差分记录反转次数即可，然后询问时做一遍前缀和来还原
这样修改，查询
，总复杂度
，
为查询次数
还是有点慢，考虑上数据结构，这里我们每次查询必须累加一遍前缀和，然后再扫一遍算答案，所以得选一个能支持扫一遍的线性结构，那线段树就遗憾离场了，只能分块。
分块想要加速，就需要在前缀和累加异或，和扫描一遍计算答案这两个部分都加速。
这是个01串，分块后每一块都是个01串，考虑压成一个64位整型，那么每一块的前缀和，就可以通过位运算，在时间内实现。
然后计算答案的部分，每个块除了内部的连续1串有贡献，两个块拼起来，左侧后缀1和右侧前缀1拼起来会形成新串，有新的贡献，想要正确计算，需要对每个块维护前缀最长1，后缀最长1，内部所有极长连续1的贡献，这类似于线段树维护最长连续全1子串的的信息。这些信息会随着修改而改变，现场计算一定是的，总复杂度又会回到每次查询
，那么我们可以预处理每个二进制数对应的块的信息，这只需要
，然后计算答案时，我们只需要知道每个块的二进制数是多少，然后直接去查询预处理的信息，按顺序拼起来就能得到答案了。这样查询操作可以优化到
总复杂度，为了尽可能加速，块长可以选要尽量大，
来表示一个块，允许的最大块长是64，但是我们的预处理不可能是
，所以可以只预处理到
左右，然后一个块查询多次预处理信息，拼起来得到一个块的完整信息，为了方便，我们预处理的长度取64的因子16，这样四个恰好拼成一个大块
最终复杂度是
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define LL ll
#define int ll
#define i64 ll
#define i128 __int128
#define u64 ull
#define u128 unsigned __int128
#define db double
#define ld long double
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define fi first
#define se second
const int N=3e5+10,M=1e7+10;
const int M1=1e9+7,M2=998244353,P=100000000000031,base1=77;
struct info{
int head,tail;
bool full;
int sum;
};
u64 get(vector<u64>&a,int i){
int sz=a.size();
if(!(i&63)){
return a[i>>6];
}
else{
u64 low=a[i>>6]>>(i&63);
u64 high=(((i>>6)+1<sz)?a[(i>>6)+1]<<(64-(i&63)):0);
return low|high;
}
}
info merge(const info& l,const info& r){
info res;
res.head=l.full?l.head+r.head:l.head;
res.tail=r.full?l.tail+r.tail:r.tail;
res.full=l.full&&r.full;
res.sum=l.sum+r.sum;
res.sum-=(l.tail)*(l.tail+1)/2+(r.head)*(r.head+1)/2;
res.sum+=(l.tail+r.head)*(l.tail+r.head+1)/2;
return res;
}
array<info,1<<16>pre;
void init(){
for(int x=0;x<(1<<16);x++){
info d;
d.head=0;
for(int i=0;i<16;i++){
if(x>>i&1){
++d.head;
}
else{
break;
}
}
d.tail=0;
for(int i=15;i>=0;i--){
if(x>>i&1){
++d.tail;
}
else{
break;
}
}
d.full=(d.head==16);
int s=0;
int cur=0;
rep(i,0,15){
if(x>>i&1){
cur++;
}
else{
s+=cur*(cur+1)/2;
cur=0;
}
}
s+=cur*(cur+1)/2;
d.sum=s;
pre[x]=d;
}
}
void solve(void){
int n,q;
cin>>n>>q;
init();
vi s(n);
for(int i=0;i<n;i++){
char c;
cin>>c;
s[i]=c-'0';
}
vi dif(n);
for(int i=1;i<n;i++){
dif[i]=s[i]^s[i-1];
}
int m=(n+63)/64;
vector<u64>d(m);
for(int i=0;i<n;i++){
if(dif[i]==1){
d[i>>6]|=(1ull<<(i&63));
}
}
while(q--){
int op;
cin>>op;
if(op==1){
int l,r;
cin>>l>>r;
--l,--r;
d[l>>6]^=(1ull<<(l&63));
if(r+1<n){
d[(r+1)>>6]^=(1ull<<((r+1)&63));
}
}
else{
int l,a,b;
cin>>l>>a>>b;
--a,--b;
vector<u64>p(m);
u64 g=0;
for(int i=0;i<m;i++){
u64 y=d[i];
y^=y<<1;
y^=y<<2;
y^=y<<4;
y^=y<<8;
y^=y<<16;
y^=y<<32;
if(g){
y=~y;
}
p[i]=y;
g^=__builtin_popcountll(d[i])&1;
}
info res{0,0,1,0};
for(int i=0;i<l/64;i++){
u64 aa=get(p,a+i*64);
u64 bb=get(p,b+i*64);
u64 v=~(aa^bb);
info d0=pre[v& 0xffff];
info d1=pre[(v>>16)& 0xffff];
info d2=pre[(v>>32)& 0xffff];
info d3=pre[(v>>48)& 0xffff];
info d=merge(merge(d0,d1),merge(d2,d3));
res=merge(res,d);
}
if(l%64 != 0){
u64 aa=get(p,a+l/64*64);
u64 bb=get(p,b+l/64*64);
u64 v=~(aa^bb)&((1ull<<(l%64))-1);
info d;
d.head=0;
rep(i,0,l%64-1){
if(v>>i&1){
++d.head;
}
else{
break;
}
}
d.tail=0;
rep1(i,l%64-1,0){
if(v>>i&1){
++d.tail;
}
else{
break;
}
}
d.full=(l%64==d.head);
i64 s=0;
int cur=0;
rep(i,0,l%64-1){
if(v>>i&1){
cur++;
}
else{
s+=(cur)*(cur+1)/2;
cur=0;
}
}
s+=(cur)*(cur+1)/2;
d.sum=s;
res=merge(res,d);
}
cout<<res.sum<<'\n';
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
// cin>>test;
while(test--){
solve();
}
}
I
区间DP 贪心 二分优化
区间dp，合并的两个区间有个不平衡度，要求合并区间的不平衡度序列，是单调的，也就是大区间的不平衡度，要小于子区间合并的不平衡度，在此基础上要求合并代价最小。
也就是带约束的区间dp，只有满足不平衡度约束才能转移，那么美誉一个区间，以及一个断点
，转移
这个转移成立，需要
这两个区间的不平衡度小于
的不平衡度。
那么可以对每个区间的所有断点的转移答案，根据不平衡度升序排序，然后我们想转移时，去
的排序好的答案数组，对不平衡度二分，找到所有满足不平衡度小于
的不平衡度的转移，然后取其中最小代价。这个最小代价我们可以排序后对代价取前缀min，即可二分后直接查询。
最后一层dp时输出每个断点的答案即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define LL ll
#define int ll
#define i64 ll
#define i128 __int128
#define db double
#define ld long double
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define fi first
#define se second
const int N=3e5+10,M=1e7+10;
const int M1=1e9+7,M2=998244353,P=100000000000031,base1=77;
vector<pii>all[430][430];
void solve(void){
int n;
cin>>n;
vi a(n+1);
rep(i,1,n){
cin>>a[i];
a[i]+=a[i-1];
}
rep(i,1,n){
rep(j,1,n){
all[i][j].clear();
}
}
vvi f(n+1,vi(n+1,2e18));
rep(i,1,n){
f[i][i]=0;
all[i][i].push_back({0,0});
}
rep(len,2,n){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
rep(k,l,r-1){
int sl=a[k]-a[l-1];
int sr=a[r]-a[k];
int imbalance=abs(sl-sr),cost=ceil(log2(sl+sr));
cost*=min(sl,sr);
int sz=all[l][k].size();
int lo=1,hi=sz;
while(lo<=hi){
int m=lo+hi>>1;
if(all[l][k][m-1].fi<=imbalance){
lo=m+1;
}
else{
hi=m-1;
}
}
if(hi>=1)cost+=all[l][k][hi-1].second;
else cost=2e18;
sz=all[k+1][r].size();
lo=1,hi=sz;
while(lo<=hi){
int m=lo+hi>>1;
if(all[k+1][r][m-1].fi<=imbalance){
lo=m+1;
}
else{
hi=m-1;
}
}
if(hi>=1)cost+=all[k+1][r][hi-1].second;
else cost=2e18;
if(cost>2e18)cost=2e18;
f[l][r]=min(f[l][r],cost);
all[l][r].push_back({imbalance,cost});
if(len==n){
if(cost<1e18){
cout<<cost<<' ';
}
else{
cout<<-1<<' ';
}
}
}
sort(all[l][r].begin(),all[l][r].end());
int sz=all[l][r].size();
rep(k,1,sz-1){
all[l][r][k].second=min(all[l][r][k].second,all[l][r][k-1].second);
}
}
}
cout<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int test=1;
cin>>test;
while(test--){
solve();
}
}
L
对顶堆 思维
一个元素在一个集合中，只有至少有一半（向下取整）的元素比他严格更大时，才会麻木，每次修改一个元素，问修改后麻木的总人数
手玩发现如果元素都不相同，答案永远是向上取整
比如
[1,2,3,4,5]
里1，2，3，都有一半人比他们更大，即使修改了，如果没有产生相同元素，答案然是不变
比如
[1,3,4,5,9]
还是前一半的人都麻木
如果有元素相同，但不是中位数，也不影响
比如
[1,2,2,2,3,4,4,4,5]
1,2,2,2,3还是都麻木，因为仍然至少有一半的人4,4,4,5比他们更大
只有中位数出现多次，且在较大一半出现时，答案才会变少，且只会减去较小一半的中位数出现次数
比如
[1,2,3,3,3,4,5]
较大一半里有个中位数3，那么答案在向上取整的基础上减掉较小一半（包含中位数）里，中位数出现次数，最后只有1,2是麻木的。因为所有中位数原本都只有较大一半比他们大，才能凑齐
向下取整这么多人比他们大，现在较大一半里出现中位数了，比他们大的元素就变少了，所有中位数都不会再麻木了。所以要把原本答案中的中位数都去掉，而原本对答案有贡献的中位数一定在较小一半（原本较大一半没有中位数），所以减去较小一半中位数出现次数即可
实现时对顶堆维护俩集合，一个存较小一半和中位数，另一个存较大一半，计算答案时，先检查较大一半里有没有中位数，如果有，就去计算较小一半里的中位数个数，从答案减掉。
实现时注意这虽然是多重集合，但是不能用multiset，因为我们要用到.count()方法，而multiset.count()不是严格的，会被卡常
建议在需要对元素计数的多重集合场景，使用桶或者map
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, b, a) for(int i = b; i >= a; i--)
#define endl "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int MAXN = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr ll INF = 1E18;
#define int ll
struct Set{
const int inf=1e18+2000;
map<int,int>less,greater;
int sz1,sz2;
void init(){
less.clear();
greater.clear();
less[-inf]++;
greater[inf]++;
sz1=sz2=0;
}
void adjust(){
while(sz1>sz2+1){
auto it=less.rbegin();
greater[it->first]++;
less[it->first]--;
if(less[it->first]==0){
less.erase(it->first);
}
sz1--;
sz2++;
}
while(sz2>sz1){
auto it=greater.begin();
less[it->first]++;
greater[it->first]--;
if(greater[it->first]==0){
greater.erase(it->first);
}
sz2--;
sz1++;
}
}
void add(int val){
if(val<=greater.begin()->first){
less[val]++;
sz1++;
}
else{
greater[val]++;
sz2++;
}
adjust();
}
void del(int val){
auto it=less.lower_bound(val);
if(it!=less.end()){
less[val]--;
if(less[val]==0){
less.erase(val);
}
sz1--;
}
else{
greater[val]--;
if(greater[val]==0){
greater.erase(val);
}
sz2--;
}
adjust();
}
int get_mid(){
return less.rbegin()->first;
}
}s;
void solve() {
int n,q;
cin>>n>>q;
vector<int>a(n+1);
int ans=n/2+1;
s.init();
// for(auto &[k,v]:s.less){
// cout<<k<<' '<<v<<'\n';
// }
rep(i,1,n){
cin>>a[i];
s.add(a[i]);
}
int mid=s.get_mid();
if(s.greater.count(mid)){
ans-=s.less.count(mid);
}
rep(i,1,q){
int p,v;
cin>>p>>v;
s.del(a[p]);
a[p]+=v;
s.add(a[p]);
int ans=(n+1)/2;
mid=s.get_mid();
if(s.greater.count(mid)&&s.less.count(mid)){
ans-=s.less[mid];
}
cout<<ans<<'\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T; cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
京公网安备 11010502036488号