Don't Never Around
cjh20090318
·
·
算法·理论
【博客园】。
标题来自 KALPA 里的曲子 Don't Never Around。
昨晚脑壳发热想写一个属于自己的骗分技巧，仅供后人参考。
当然如果你实力足够强大理论上是不屑于骗分的，所以比较适合我这种不喜欢动脑子的人看。
等死，死国可乎？
反正都拿不到分，还不如放手一搏，相信暴力出奇迹！
本文写的都是校内的题，校外的题没什么骗分方法。
更新随缘看心情。
暴 力 美 学
强 力 剪 枝
这里的剪枝并非只有搜索意义上的剪枝，而是减少冗余的计算次数，使其除以一个巨大的常数，就像 std::bitset 的 w 一样。
FZUOJ#7482. 模糊匹配
神说，要宽容，然后就放过了暴力。
这题本身正解是什么分块，但是显然我不会。
观察到一个性质：当 $\vert p_i \vert \le k$ 时，$s$ 的每个地方都可以被成功模糊匹配，于是这种情况下的答案即 $\vert s \vert - \vert p_i \vert + 1$，于是加上这个关键剪枝就能过了。
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#define MAXN 200005
using namespace std;
int k,n,q,m;
char s[MAXN],t[MAXN];
int main(){
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
scanf("%d %s %d",&k,s+1,&q);
n=strlen(s+1);
while(q--){
scanf(" %s",t+1);
m=strlen(t+1);
if(m<=k){printf("%d\n",n-m+1);continue;}//这一个剪枝非常关键，决定了你能不能通过。
int ans=0;
for(int i=1,mi=n-m+1,l,r;i<=mi;i++){
r=i+m-1;
for(l=i;l+k<=r&&s[l]==t[l-i+1];l++);
for(;(l<r&&r-l>=k)&&s[r]==t[r-i+1];--r);
if(r-l<k)++ans;
}
printf("%d\n",ans);
}
return 0;
}
```
时间复杂度 $O(\vert s \vert n)$，理论得分 $30$ 分，实际得分 $100$ 分。
### 部 分 重 构
在某些题目中，一次操作会影响部分，但是重新处理所有部分是不必要的，我们只需要处理被影响的那部分。
#### FZUOJ#8899. 小恐龙
坑，待填。
#### FZUOJ#9516. 流星雨
按照题意直接模拟流星和防御装置，时间复杂度 $O(m^2)$。
对于 $l=r,L=R$ 的情况，可以直接点对点处理。
对于剩下的情况，我们可以合理猜测区间有交的概率很大，因此不会有很多对流星防御无效的装置，所以对于无效的就丢到一个栈中，询问结束时丢回去即可。
理论得分 $25$ 分，实际得分 $100$ 分。
```cpp
//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const LL inf=0x3f3f3f3f3f3f3f3fll;
int n,m;
struct QUE{
int h,l,r;
LL d;
QUE(const int _h=0,const int _l=0,const int _r=0,const LL&_d=0):h(_h),l(_l),r(_r),d(_d){}
}q[MAXN];
void solve1(){
vector<QUE> v,w;v={QUE(0,1,n,inf)};
for(int i=1;i<=m;i++){
if(q[i].h==1) v.emplace_back(i,q[i].l,q[i].r,q[i].d);
else if(q[i].h==2){
w.clear();
while(!v.empty()&&q[i].d){
if(v.back().r>=q[i].l&&v.back().l<=q[i].r){
printf("%d ",v.back().h);
if(q[i].d<v.back().d) v.back().d-=q[i].d,q[i].d=0;
else q[i].d-=v.back().d,v.pop_back();
}
else w.push_back(v.back()),v.pop_back();
}
reverse(w.begin(),w.end());
v.insert(v.end(),w.begin(),w.end());
putchar('\n');
// for(const auto&[h,l,r,d]:v) fprintf(stderr,"D: %d %d %d %lld\n",h,l,r,d);
}
}
}
void solve4(){
vector<QUE> v[MAXN];
for(int i=1;i<=n;i++) v[i]={QUE(0,1,n,inf)};
for(int i=1,L;i<=m;i++){
L=q[i].l;
if(q[i].h==1) v[L].emplace_back(i,q[i].l,q[i].r,q[i].d);
else if(q[i].h==2){
while(!v[L].empty()&&q[i].d){
printf("%d ",v[L].back().h);
if(q[i].d<v[L].back().d) v[L].back().d-=q[i].d,q[i].d=0;
else q[i].d-=v[L].back().d,v[L].pop_back();
}
putchar('\n');
// for(const auto&[h,l,r,d]:v) fprintf(stderr,"D: %d %d %d %lld\n",h,l,r,d);
}
}
}
int main(){
scanf("%d%d",&n,&m);
bool sb4=1;
for(int i=1;i<=m;i++)
scanf("%d%d%d%lld",&q[i].h,&q[i].l,&q[i].r,&q[i].d),sb4&=q[i].l==q[i].r;
if(sb4) solve4();
else solve1();
return 0;
}
```
### 理 性 分 析
通常时间复杂度分为最好时间复杂度，平均时间复杂度，最坏时间复杂度，我们考虑一道题是否能够通过都是看最坏时间复杂度。让一种算法达到最坏时间复杂度的时候通常是需要特殊构造的，但是这种特殊构造的数据一定会带有某些性质，对这种性质再单独处理就好了。
#### FZUOJ#9325. 水槽(sink)
可以用单调栈求出第一个比它小的值，因为在这些点的位置上水量才会有变化，建树后在随机数据下树高是 $O(n \log n)$，。
考虑最坏的情况，当降序排序时，这种算法的时间复杂度会变为 $O(n^2)$，但是这种情况特殊处理一下即可。
理论分数 $60$ 分，实际分数 $100$ 分。
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define MAXN 1000005
using namespace std;
typedef long long LL;
int n,a[MAXN],p[MAXN],f[MAXN];
int stk[MAXN],t=0;
LL s[MAXN];
int main(){
// freopen("sink.in","r",stdin);
// freopen("sink.out","w",stdout);
scanf("%d",&n);
int x=1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]<a[x]&&(x=i);
if(n<=1000){
LL s=0;
memcpy(f+1,a+1,sizeof(int)*n);
for(int i=1;i<=n;i++){
rotate(f+1,f+n,f+n+1);
s=0;
for(int j=1;j<=n;j++) s+=(f[j]=min(f[j],a[j]));
printf("%lld ",s);
}
return 0;
}
stk[++t]=p[x]=x;
for(int i=x-1;i>0;--i){
while(t&&a[i]<a[stk[t]]) --t;
p[i]=stk[t],stk[++t]=i;
}
for(int i=n;i>x;--i){
while(t&&a[i]<a[stk[t]]) --t;
p[i]=stk[t],stk[++t]=i;
}
LL ans=0;
if(is_sorted(a+1,a+n+1,greater<int>())){
for(int i=1;i<=n;i++) s[1]+=a[i],s[i]-=a[i];
for(int i=1;i<=n;i++) printf("%lld ",(s[i]+=s[i-1])+(LL)i*a[n]);
return 0;
}
for(int i=1;i<=n;ans+=a[i++])if(i!=x)for(int u=i,e=0;u!=x;u=p[u]) s[e+=p[u]>u?p[u]-u:n-u+p[u]]+=a[p[u]]-a[u];
for(int i=1;i<=n;i++) printf("%lld ",ans+=s[i]);
return 0;
}
```
## 人 类 智 慧
### 局 部 最 优
有的时候会需要求解一些全局性的最优问题，却又不能直接全局贪心的时候，我们可以局部的贪心，去枚举部分局部最小值来取最优答案，在随机数据下有大概率是正确的。
#### FZUOJ#9495. 公交
正解是维护凸包做动态规划，我也不会。
这是一个来自 [P1452 【模板】旋转卡壳](https://www.luogu.com.cn/problem/P1452) 的技巧，这一题需要求的是凸包直径，于是随机旋转一个角度再按 $x,y$ 排序，然后再选前面的几个和后面的几个答案取 $x^2+y^2$ 最大值。
这题同样要求 $\min\limits_{i=1}^n((\sum\limits_{j=1}^i d_j) + m_iv)$，所以有一个必然比较小。
又因为 $d_i \ge 1$，所以 $i$ 越大 $\sum\limits_{j=1}^i d_j$ 越大，所以我们就取前 $B$ 个 $i$ 和前 $B$ 小的 $m_i$ 就可以了。$B$ 考场上取得 $800$，下来实测 $350$ 可过。
时间复杂度 $O(qB \log n)$，理论 $40$ 分，实际 $100$ 分。
```cpp
//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
using ci=const int;
ci blk=350;
const LL inf=0x3f3f3f3f3f3f3f3fll;
int n,q;
int d[MAXN],m[MAXN];
LL ds[MAXN];
struct QUE{
int op,p,f,v;
}e[MAXN];
void up(int x,const LL&v){for(;x<=n;x+=x&-x) ds[x]+=v;}
LL as(int x){LL ret=0;for(;x;x^=x&-x)ret+=ds[x];return ret;}
set<PII> S;
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>d[i];
for(int i=1;i<=n;i++) cin>>m[i];
if(1ll*n*q<=4000*4000){
for(int op,p,f,v;q--;){
cin>>op>>p>>f>>v;
if(op==1) d[p]=f;
else if(op==2) m[p]=f;
LL ans=inf,s=0;
for(int i=1;i<=n;i++) ans=min(ans,(s+=d[i])+(LL)m[i]*v);
cout<<ans<<'\n';
}
return 0;
}
for(int i=1;i<=q;i++) cin>>e[i].op>>e[i].p>>e[i].f>>e[i].v;
for(int i=1;i<=n;i++){
S.emplace(m[i],i),up(i,d[i]);
if(S.size()>blk) S.erase(--S.end());
}
for(int i=1,op,p,f,v;i<=q;i++){
op=e[i].op,p=e[i].p,f=e[i].f,v=e[i].v;
if(op==1) up(p,f-d[p]),d[p]=f;
else if(op==2){
auto it=S.find(PII(m[p],p));
if(it!=S.end()) S.erase(it);
S.emplace(m[p]=f,p);
if(S.size()>blk) S.erase(--S.end());
}
LL ans=inf;
for(const PII&x:S) ans=min(ans,as(x.second)+(LL)x.first*v);
for(int i=1,mi=min(n,blk);i<=mi;i++) ans=min(ans,as(i)+(LL)m[i]*v);
cout<<ans<<'\n';
}
return 0;
}
```
#### FZUOJ#9942. 计算 calc
很容易证明在 $x,y$ 确定后 $c_i$ 是可以三分或者分类讨论 $O(1)$ 计算的。
设 $m = \max\limits_{i=1}^n \max(a_i,b_i)$，我们设枚举的 $x,y$ 上限为 $k=m$。于是得到了一个 $O(k^2n \log m)$ 的算法。
然后可以通过前两个样例，同时我们发现答案最小的 $x,y$ 并不是很大，于是我们直接取 $k=700$ 即可，发现可以通过全部大样例，于是猜测数据强度和样例大致相同。
理论得分 $20$ 分，实际得分 $100$ 分。
```cpp
//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL f(const int a,const int b,const int x,const int y,const int c){return abs(a-(LL)c*x)+abs(b-(LL)c*y);}
int n,a[33],b[33];
int main(){
scanf("%d",&n);
int mr=0;
LL ans=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),mr=max(mr,a[i]),ans+=a[i];
for(int i=1;i<=n;i++) scanf("%d",&b[i]),mr=max(mr,b[i]),ans+=b[i];
for(int x=0,mx=min(mr,700);x<=mx;x++)for(int y=0;y<=mx;y++){
LL sum=0;
for(int i=1;i<=n;i++){
int l=0,r=mr;
for(int mid;l<r;) mid=(l+r)>>1,f(a[i],b[i],x,y,mid)>f(a[i],b[i],x,y,mid+1)?l=mid+1:r=mid;
sum+=f(a[i],b[i],x,y,l);
}
ans=min(ans,sum);
}
printf("%lld\n",ans);
return 0;
}
```
## 特 殊 构 造
### 必 要 答 案
当一个构造题无法下手的时候，可以考虑构造他的必要答案。
什么是必要答案呢？即限制比题目条件更加严格，通俗来说就是构造出来的答案一定满足题目条件，但是在更严格的限制条件下构造无解时题面不一定无解。
有的构造题并不是那么好造数据，所以构造出来有解多半就是有解，无解就是无解，这样可以混到一个比较好看的分数。
#### FZUOJ#9341. 简单题(normal)
对于 $m \le 2 \times 10^4$ 的情况，可以直接进行二分图染色构造方案，时间复杂度 $O(m^2)$。
对于剩下的情况，猜测有解的数据情况并不好造。
把所有线段按左端点排序，尝试贪心修建在上方，上方不行就尝试修建在下方，两边都不行就返回无解。
理论得分 $40$ 分，实际得分 $100$ 分。
```cpp
//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
//typedef pair<int,int> PII;
int n,m;
struct SEG{
int l,r,i;
bool operator < (const SEG&B)const{return l==B.l?r>B.r:l<B.l;}
}a[MAXN];
short c[MAXN];
stack<int,vector<int> > stk[2];
void dfs(const int u,const int o){
c[u]=o;
for(int v=1;v<=m;v++)
if((a[u].l<a[v].l&&a[v].l<a[u].r&&a[u].r<a[v].r)||(a[v].l<a[u].l&&a[u].l<a[v].r&&a[v].r<a[u].r)){
if(!c[v]) dfs(v,o^3);
else if(c[v]!=(o^3)) puts("IMPOSSIBLE"),exit(0);
}
}
int main(){
// freopen("normal.in","r",stdin);
// freopen("normal.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].i=i;
if(m<=20000){
for(int i=1;i<=m;i++)if(!c[i]) dfs(i,1);
for(int i=1;i<=m;i++) puts(c[i]==1?"N":"S");
return 0;
}
sort(a+1,a+m+1);
stk[0].push(n+1),stk[1].push(n+1);
for(int i=1;i<=m;i++){
// fprintf(stderr,"%d %d\n",a[i].l,a[i].r);
while(stk[0].top()<=a[i].l) stk[0].pop();
while(stk[1].top()<=a[i].l) stk[1].pop();
if(a[i].r<=stk[0].top()) stk[0].push(a[i].r),c[a[i].i]=0;
else if(a[i].r<=stk[1].top()) stk[1].push(a[i].r),c[a[i].i]=1;
else{
sort(a+1,a+m+1,[](const SEG&A,const SEG&B){return A.i<B.i;});
for(int i=1;i<=m;i++)if(!c[i]) dfs(i,1);
for(int i=1;i<=m;i++) puts(c[i]==1?"N":"S");
return 0;
}
}
for(int i=1;i<=m;i++) puts(c[i]?"N":"S");
return 0;
}
```