发现有大佬的博客提供了翻译:https://www.yht7.com/news/294472
QOJ5500 Bars
$1,n$ 必选,选了 $1,n$ 一定不亏
$f[i] = f[j] + (i-j)*(p[i]+p[j])$ (f[i]为前i个bars并且选第i个,0<=j<i)
发现 $(i-j)\times (p[i]+p[j])$ 乘上 $1/2$ 就为梯形面积。
所以题目等同于选多个连续封闭图形使得总面积最优,可以维护上凸壳求凸壳面积就为ans
用一个stk维护即可,与斜率优化本质不同(别搞错了)
这题贴个维护凸壳代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int T,n,p[N];
int V(int i,int j){
return (j-i)*(p[i]+p[j]);
}
int stk[N],tt;
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
tt=1;stk[1]=1;
for(int i=2;i<=n;i++){
while(tt>1&&V(stk[tt-1],i)>=V(stk[tt-1],stk[tt])+V(stk[tt],i)) tt--;
stk[++tt]=i;
}
int ans=0;
for(int i=1;i<tt;i++) ans+=V(stk[i],stk[i+1]);
printf("%lld\n",ans);
}
return 0;
}
QOJ5511 Minor evil
思维题
可以发现evil Gebyte没有意义,可以理解为Ai杀了Bi。而我们的能力可以认为当Ai活着的时候,可以控制Bi是否死。而Ai死了的话,Bi的生死无法在本次决定。
当Ai死了的时候,我们无法控制Bi的生死。而当Ai活着的时候,我们可以让其将Bi杀掉
之后可发现我们希望一个人多活一些。因此倒序枚举,若Bi不是要杀的人,则让其活着。若Bi是要杀的人,标记Ai前面不可杀,然后将Bi杀了,但如果Ai也是要杀的,并且后面(倒序枚举是前面)没有杀掉,那么不可杀
另外这题输出不唯一
P9133 [THUPC 2023 初赛] 大富翁
非常神奇的题目,启示要考虑全局贡献,按照贡献排序。不要想太复杂。
[ARC154D] A + B > C ?
交互题不会写Code
可以想到,如果得到了数字1的位置,我们只需要让1不停的参与比较。1+Ai>Aj等价于Ai>Aj(因为没有两数相等而且最少相差1),1+Ai<Aj等价于Ai<Aj.
用归并排序来在 $O(n log n)$ 范围内排序
然后找到一可以利用打擂台的方式,O(n)
总体复杂度 O(n + n log n),在 $n=2000$ 的范围下 $25000$ 次比较可行
[ARC139B] Make N
我看的这个大佬的题解,看明白了说清楚点(虽然已经非常非常清晰了/bx ),也好之后复习
设1的性价比为 $1/x$, a的性价比为 $a/y$, b的性价比为 $b/z$。
1的性价比最高和次高的时候答案显然,一个全用 1 另一个用性价比最高的然后1补齐。
之后考虑1性价比最低也是最普遍的情况,钦定 $a/y >= b/z >= 1/x$
① 若 $a > \sqrt{n}$, 则 a 被选不超过 $\sqrt{n}$ 次,枚举a被选次数即可
② 若 $a <= \sqrt{n}$,则 b 被选不超过 a 次(若超过 a 次用 a 替换 b 操作显然更优),也即不超过 $\sqrt(n)$ 次,枚举b被选次数
使用根号分治解决此题,复杂度 $O(T\times\sqrt{n})$
这代码中枚举的公式很容易写错,而且要注意边界比如枚举b的时候 i<a&&b*i<=n
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool V(int x1,int y1,int x2,int y2){
return x1*y2>=y1*x2;
}
int T,n,a,b,x,y,z,q;
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld%lld%lld%lld",&n,&a,&b,&x,&y,&z);
if(a*z<b*y) swap(a,b),swap(z,y);
if(V(1,x,a,y)) printf("%lld\n",n*x);
else if(V(1,x,b,z)) printf("%lld\n",n/a*y+(n%a)*x);
else{
int ans=1e18;
if(a*a>n)
for(int i=0;a*i<=n;i++)
ans=min(i*y+(n-i*a)/b*z+(n-a*i)%b*x,ans);
else
for(int i=0;i<=a&&b*i<=n;i++)
ans=min(i*z+(n-i*b)/a*y+(n-b*i)%a*x,ans);
printf("%lld\n",ans);
}
}
return 0;
}
Luogu P2572 序列操作
由于代码太长所以学习了小粉兔的码风及操作写法
这题注意点:
-
既要保存1的数量也要保存0的数量,方便区间翻转操作
-
关于不同优先级懒标记的下传(如 乘>加 覆盖>翻转)
①若先覆盖后翻转
再pushdown操作中本身就是这个顺序,无所谓
②若先翻转后覆盖
等同于直接覆盖。若是此顺序,则一定是先调用了modify进行翻转,后调用了modify进行覆盖。在modify之中运行P函数的时候也一定是先翻转后覆盖。在P函数中可以发现在覆盖之时清空了翻转lazytag,所以翻转懒标记不会继续下传,故而顺序不会有影响。
总而言之,先覆盖后翻转就是代码中正常的顺序。但是不可能出现先翻转后覆盖的操作,因为如果这样的话翻转标记就被更新覆盖标记的时候reset为0了。也就是变为了直接覆盖,而这样是等价的。所以这样写不用考虑顺序的影响。
高级的操作(如乘法)在低级的操作之前进行(pushdown函数之中),同时在更新高级的操作的tag的时候清空掉低级操作的tag,就不会出现问题了!
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e5+10;
int n,m,w[N];
struct Node{
//w=1 b=0
int l,r,w,b,lw,rw,lb,rb,mb,mw;
}tr[N*4];
int tg1[4*N],tg2[4*N];
//tg1=0/1 则代表区间被填充为0/1
Node pushup(Node lc,Node rc){
Node rt;
rt.l=lc.l,rt.r=rc.r;
rt.w=lc.w+rc.w;rt.b=lc.b+rc.b;
rt.mw=max(lc.mw,max(lc.rw+rc.lw,rc.mw));rt.mb=max(max(lc.mb,lc.rb+rc.lb),rc.mb);
rt.lw=lc.b?lc.lw:lc.w+rc.lw;
rt.rw=rc.b?rc.rw:lc.rw+rc.w;
rt.lb=lc.w?lc.lb:lc.b+rc.lb;
rt.rb=rc.w?rc.rb:lc.rb+rc.b;
return rt;
}
void build(int u,int l,int r){
tg1[u]=-1;
if(l==r){
if(w[l]) tr[u]={l,r,1,0,1,1,0,0,0,1};
else tr[u]={l,r,0,1,0,0,1,1,1,0};
return;
}
tr[u]={l,r,0,0,0,0,0,0,0,0};
int mid=l+r>>1;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
tr[u]=pushup(tr[u<<1],tr[u<<1|1]);
}
void P(int u,int opt){//对区间整体修改(修改懒标记O(1) )
Node &t=tr[u];int len=t.r-t.l+1;
if(!opt) tg2[u]=0,tg1[u]=0,t={t.l,t.r,0,len,0,0,len,len,len,0};
else if(opt==1) tg2[u]=0,tg1[u]=1,t={t.l,t.r,len,0,len,len,0,0,0,len};
else tg2[u]^=1,swap(t.w,t.b),swap(t.lb,t.lw),swap(t.rb,t.rw),swap(t.mb,t.mw);
}
void pushdown(int u){
if(~tg1[u]) P(u<<1,tg1[u]),P(u<<1|1,tg1[u]);
if(tg2[u]) P(u<<1,2),P(u<<1|1,2);
tg1[u]=-1,tg2[u]=0;
}
void modify(int u,int l,int r,int k){
if(tr[u].l>r||tr[u].r<l) return;//完全超出范围
if(tr[u].l>=l&&tr[u].r<=r){P(u,k);return;}//修改懒标记,不继续向下搜索所以不需要pd
pushdown(u);
modify(u<<1,l,r,k);modify(u<<1|1,l,r,k);
tr[u]=pushup(tr[u<<1],tr[u<<1|1]);
}
Node query(int u,int l,int r){
if(tr[u].l>r||tr[u].r<l) return tr[100009];
if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
pushdown(u);
return pushup(query(u<<1,l,r),query(u<<1|1,l,r));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
build(1,1,n);int opt,l,r;
while(m--){
scanf("%d%d%d",&opt,&l,&r);l++,r++;
if(opt<=2) modify(1,l,r,opt);
else{
Node t=query(1,l,r);
printf("%d\n",opt==3?t.w:t.mw);
}
}
return 0;
}
/*
*/
P5021 [NOIP2018 提高组] 赛道修建
对于最小的最大这种问题,肯定进行二分答案。要在城内修建m个赛道也就等于有m个赛道>=mid
之后使用树形dp进行check
将 $f_i$ 设为以 $i$ 为根的子树中长度大于等于 $mid$ 的赛道个数,$g_i$ 表示从当前节点为赛道一端点且赛道向上延伸的最长长度
转移 见其他题解,懒得写了
P4281 [AHOI2008] 紧急集合 / 聚会
一道很裸的LCA。树上三个点到一个点距离最小,求这个点和最小值。边权1。
先求出三个点分别的三个LCA,之后取深度最深的lca点为集合点即可。正确性不会证,反正考场就是猜结论。
本来猜的是若a,b,c中两个点x,y和lca(x,y)的距离相对其他两个最小,则取这个为集合点,但是错了,这个(luogu样例1的第一个询问)就能卡掉
6 1
1 2
2 3
2 4
4 5
5 6
4 5 6
期望dp
绿豆蛙的归宿, acwing扑克牌,BNDSoj
P1220 关路灯
$n<=50$ 区间dp
发现只记录l,r不行,记录额外信息0/1代表关完l~r的路灯后,所处位置是l(0)还是r(1)
之后此题不需要枚举中转点k,从l+1和r-1转移即可。
但是呢中间的状态是无从得知的,无法求出关完l~r所花的时间,看似无法转移。
但是可以进行状态提前计算,每次走一步都将其他所有地方多耗费的功率加上,而非到达这个地方再加上
之后就完美解决了,别忘了初始化。
#include<bits/stdc++.h>
using namespace std;
const int N=51;
int n,m,f[N][N][2],s[N];
//区间l~r,结束后站在左侧(0)还是右侧(1)
struct Node{
int w,p;
}a[N];
int main(){
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].p,&a[i].w);
s[i]=s[i-1]+a[i].w;
}
f[m][m][0]=f[m][m][1]=0;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[i][j][0]=min(f[i+1][j][0]+(a[i+1].p-a[i].p)*(s[n]-s[j]+s[i]),f[i+1][j][1]+(a[j].p-a[i].p)*(s[n]-s[j]+s[i]));
f[i][j][1]=min(f[i][j-1][1]+(a[j].p-a[j-1].p)*(s[n]-s[j-1]+s[i-1]),f[i][j-1][0]+(a[j].p-a[i].p)*(s[n]-s[j-1]+s[i-1]));
}
printf("%d",min(f[1][n][0],f[1][n][1]));
return 0;
}
/*
区间dp不一定要枚举中转点k,可以一个一个转移
对于转移,我们使用提前计算状态的方法(自己老是想不出来!!)
(i,j)->(i+1,j),f+=(p[j]-p[i])*(s[n]-(s[j]-s[i]))
前缀和s求的是功率
*/
P4805 [CCC2016] 合并饭团
第一种操作与石子合并一样,只不过加上是否相等的判断即可。
分开进行。第二种操作,枚举两个中转点k1,k2(k1<k2-1),之后f(l,r)=f(l,k1)+f(k1+1,k2-1)+f(k2,r)(根据题意)
但是O(n^4)超时,发现枚举k1k2可用双指针,之后就简单了。注意转移的时候要判断f(k1+1,k2-1)!=0(不然的话中间隔着的可能不是一个数或者一个合并的数,而是一个区间)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
int n,a[N],f[N][N];
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i][i]=a[i];
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++)
if(f[l][k]&&f[k+1][r]&&f[l][k]==f[k+1][r])
f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
int k1=l,k2=r;
while(k1<k2-1){
if(!f[l][k1]) ++k1;
if(!f[k2][r]) --k2;
if(f[l][k1]&&f[k2][r]&&f[l][k1]==f[k2][r]){
if(f[k1+1][k2-1]) f[l][r]=f[l][k1]+f[k1+1][k2-1]+f[k2][r];
k1++,k2--;//注意这里同时加减
}
if(f[l][k1]<f[k2][r]) k1++;
if(f[l][k1]>f[k2][r]) k2--;
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) ans=max(ans,f[i][j]);
printf("%d",ans);
return 0;
}