ABC265F
题意：
给定两个\(n\)维空间上的点，问有多少个点距离这两个点的曼哈顿距离不超过\(m\)？
\(n\leq 100\)，其他数字小于等于\(1000\)
题解：
感谢\(SSRS\)大神
考虑一个二维的动态规划问题，暴力\(dp\)的话这个问题其实类似一个分组背包，按维度分组，每一维可选的点是\(O(m)\)级别的，加一个二维的背包容量复杂度是\(O(nm^3)\)
考虑物品的贡献形式，不妨假设在第\(i\)维上\(a[i]\geq b[i]\)，设\(s[i]=a[i]-b[i]\)那么
对于大于\(a[i]\)的点，贡献形式是\((k,k+s[i])\)
对于大于等于\(b[i]\)，小于等于\(a[i]\)的点，贡献形式是\((k,s[i]-k)\)
对于小于\(b[i]\)的点，贡献形式是\((k+s[i],k)\)
其中第一种和第三种二者的差是一定的，等价于一条主对角线上的点，第二种二者和是一定的，等价于一条副对角线。
其实\(a[i]\)和\(b[i]\)哪个更大并不影响贡献的形式。
转移的时候考虑开两个数组，\(dp2\)维护副对角线，\(dp3\)维护主对角线。
先考虑中间部分
\(x_1=j,y_1=k+s[i]\)
\(dp[j][k]->dp2[x_1][y_1]\)（这里要注意，如果\((x_1,y_1)\)超出了矩阵范围，要找到它这条副对角线上在矩阵范围内的位置，即\(x_1+=y_1-m,y_1=m\)）
\(x_2=j+s[i]+1,y_2=k-1\)
\(mod-dp[j][k]->dp2[x_2][y_2]\)
因为中间一段只有长度为\(s[i]\)的能转移，所以把超出的部分删去，如果这里超出矩阵范围就不用转移了，因为这里超出范围说明在矩阵下方。
然后是主对角线上的两段
\(x_3=j+s[i]+1,y_3=k+1\)
\(dp[j][k]->dp3[x_3][y_3]\)
以这个举例子，其实能转移过来到\(x_3,y_3\)的范围是\((j,k),(j-1,k-1),(j-2,k-2)……\)一会再做对角线求和就行了。
\(x_4=j+1,y_4=k+s[i]+1\)
\(dp[j][k]->dp3[x_4][y_4]\)
转移完了之后对角线求和
\(dp2[j][k]+=dp2[j-1][k+1]\)
\(dp3[j][k]+=dp3[j-1][k-1]\)
然后\(dp[j][k]=dp2[j][k]+dp3[j][k]\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<int> a(n),b(n),s(n);
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<n;++i) cin>>b[i];
for(int i=0;i<n;++i) s[i]=abs(a[i]-b[i]);
//vector dp(2,vector(m+1,vector<int>(m+1)));
vector dp(m+1,vector<int>(m+1,0));
dp[0][0]=1;
for(int i=0;i<n;++i)
{
vector dp2(m+1,vector<int>(m+1,0));
vector dp3(m+1,vector<int>(m+1,0));
for(int j=0;j<=m;++j)
{
for(int k=0;k<=m;++k)
{
if(j+k+s[i]<=2*m&&dp[j][k]>0)
{
int x1=j,y1=k+s[i];
if(y1>=m)
{
x1+=y1-m;
y1=m;
}
dp2[x1][y1]+=dp[j][k];
int x2=j+s[i]+1,y2=k-1;
if(x2<=m&&y2>=0)
{
dp2[x2][y2]+=mod-dp[j][k];
}
int x3=j+s[i]+1,y3=k+1;
if(x3<=m&&y3<=m)
{
dp3[x3][y3]+=dp[j][k];
}
int x4=j+1,y4=k+s[i]+1;
if(x4<=m&&y4<=m)
{
dp3[x4][y4]+=dp[j][k];
}
}
}
}
for(int j=0;j<m;++j)
{
for(int k=0;k<=m;++k)
{
if(k>0)
{
dp2[j+1][k-1]+=dp2[j][k];
dp2[j+1][k-1]%=mod;
}
if(k<m)
{
dp3[j+1][k+1]+=dp3[j][k];
dp3[j+1][k+1]%=mod;
}
}
}
for(int j=0;j<=m;++j)
{
for(int k=0;k<=m;++k)
{
dp[j][k]=(dp2[j][k]+dp3[j][k])%mod;
}
}
}
int ans=0;
for(int i=0;i<=m;++i)
for(int j=0;j<=m;++j)
{
//cout<<dp[i][j]<<" \n"[j==m];
ans+=dp[i][j];
}
cout<<ans%mod<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC265G
题意：
给定一个长度为\(n\)的序列，只包括\(0,1,2\)。
给\(m\)个操作，有两种：
\(1.l,r\)求\([l,r]\)范围内的逆序对数
\(2.l,r,x,y,z\)把\([l,r]\)范围内的\(0\)都变成\(x\)，\(1\)都变成\(y\)，\(2\)都变成\(z\)。
\(n,m\leq 10^5,0\leq x,y,z\le 2\)
题解：
分块好像还比较好想，但是线段树也能写。
具体就是需要维护一个长度为\(3\)的数组，表示\(0,1,2\)各有多少个。
然后维护一个\(3*3\)的数组，\(g[i][j]\)表示\(i\)在\(j\)前面的对数有多少对。
至于修改标记，也变成一个\(1*3\)的数组，其中\(tag[i]\)表示第\(i\)个数字要变成哪个数字，这样就可以实现信息和标记和合并了。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
struct node
{
int f[3];
int g[3][3];
void clear()
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
}
int get()
{
int sum=0;
for(int i=0;i<3;++i)
{
for(int j=0;j<i;++j)
{
sum+=g[i][j];
}
}
return sum;
}
node operator + (const node &b) const
{
node ret;
node a=*this;
for(int i=0;i<3;++i) ret.f[i]=a.f[i]+b.f[i];
for(int i=0;i<3;++i)
{
for(int j=0;j<3;++j)
{
ret.g[i][j]=a.g[i][j]+b.g[i][j]+a.f[i]*b.f[j];
}
}
return ret;
}
};
int n,m;
cin>>n>>m;
vector<int> a(n+1);
for(int i=1;i<=n;++i) cin>>a[i];
vector<node> ans(4*n+1);
typedef array<int,3> Tag;
Tag e={0,1,2};
vector<Tag> tag(4*n+1);
auto work=[&](node &tmp,Tag t) -> void
{
node ret;ret.clear();
for(int i=0;i<3;++i) ret.f[t[i]]+=tmp.f[i];
for(int i=0;i<3;++i)
{
for(int j=0;j<3;++j)
{
ret.g[t[i]][t[j]]+=tmp.g[i][j];
}
}
tmp=ret;
};
auto merge=[&](Tag &s,Tag t) -> void
{
for(int i=0;i<3;++i) s[i]=t[s[i]];
};
auto pushdown=[&](int l,int r,int p) -> void
{
work(ans[ls(p)],tag[p]);
work(ans[rs(p)],tag[p]);
merge(tag[ls(p)],tag[p]);
merge(tag[rs(p)],tag[p]);
tag[p]=e;
};
function<void(int,int,int)> build=[&](int l,int r,int p) -> void
{
tag[p]=e;
if(l==r)
{
ans[p].f[a[l]]=1;
return;
}
build(l,mid,ls(p));
build(mid+1,r,rs(p));
ans[p]=ans[ls(p)]+ans[rs(p)];
};
build(1,n,1);
function<void(int,int,int,int,int,Tag)> update=[&](int tl,int tr,int l,int r,int p,Tag k) -> void
{
if(tl<=l&&r<=tr)
{
work(ans[p],k);
merge(tag[p],k);
return;
}
if(tag[p]!=e) pushdown(l,r,p);
if(tl<=mid) update(tl,tr,l,mid,ls(p),k);
if(tr>mid) update(tl,tr,mid+1,r,rs(p),k);
ans[p]=ans[ls(p)]+ans[rs(p)];
};
function<node(int,int,int,int,int)> query=[&](int tl,int tr,int l,int r,int p) -> node
{
if(tl<=l&&r<=tr) return ans[p];
if(tag[p]!=e) pushdown(l,r,p);
if(tr<=mid) return query(tl,tr,l,mid,ls(p));
if(tl>mid) return query(tl,tr,mid+1,r,rs(p));
return query(tl,tr,l,mid,ls(p))+query(tl,tr,mid+1,r,rs(p));
};
for(int i=1;i<=m;++i)
{
int opt,l,r;
cin>>opt>>l>>r;
if(opt==1)
{
node tmp=query(l,r,1,n,1);
cout<<tmp.get()<<'\n';
}
else
{
int x,y,z;cin>>x>>y>>z;
Tag tran={x,y,z};
update(l,r,1,n,1,tran);
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC265Ex
题意：
给定一个\(n*m\)的棋盘，两个人下棋，每一行两个人各放一个棋子。
先手可以把棋子往左挪任意个，不越过其它棋子。后手可以把棋子往右挪任意个，不碰到其它棋子。挪不了的人输。
问有多少种放置方案是先手必胜的？
\(n\leq 8000,m\leq 30\)
题解：
考虑一行种两种不同的放置方法如果先手放到了第\(j\)个位置，后手放到了第\(k\)个位置。
如果\(j>k\)，那么其实是\(nim\)游戏，石子的个数就是两个人之间的格子数，挪动可以看作在取任意个石子。
如果\(j<k\)，那么两个人互相不会碰到，这种情况下可以用来逆转上述\(nim\)游戏的结果。设先手能走的格子数为\(x\)，后手能走的格子数为\(y\)
我们把\(nim\)部分和第二种情况分开来看。
设\(X\)为第二种情况先手能走的总步数，\(Y\)为第二种情况后手能走的总步数。
如果\(X\neq Y\)，那么步数多的一方一定能存在逆转战局的走法，所以谁步数多谁赢。
如果\(X=Y\)，那么游戏的胜负就取决于\(nim\)游戏了。
这样可以设计\(dp\)
\(dp[i][x][y]\)表示到第\(i\)行位置，\(nim\)游戏的异或和是\(x\)，\(X-Y\)的值是\(y\)。
转移考虑这一行的放置方案：
如果二者相背，转移即为\((0,(j-1)-(m-k))\)
\(dp[i][x][y]-> dp[i+1][x\oplus 0][y+((j-1)-(m-k))]\)
如果二者相向，转移是\((j-k,0)\)
\(dp[i][x][y]->dp[i+1][x\oplus(j-k)][y+0]\)
第三维是一个多项式卷积，而第二维又是一个异或卷积。
可以把异或卷积里面的乘法定义为多项式卷积来优化。
定义为乘法之后行数之间的转移可以用快速幂优化。
复杂度就是\(O(nm^2log(nm))\)
常数大到我自己的多项式板子跑不过，要用\(atc\)的库。
#include<bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inv2=(mod+1)/2,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector f(32,vector<int>(61,0));
for(int i=0;i<m;++i)
{
for(int j=i+1;j<m;++j)
{
int c=i-(m-1-j)+30;
++f[0][c];
}
}
for(int i=0;i<m;++i)
{
for(int j=0;j<i;++j)
{
++f[i-j-1][30];
}
}
int k=n;
auto add=[&](auto a,auto b) -> auto
{
int n=a.size();
for(int i=0;i<n;++i)
{
a[i]+=b[i];
if(a[i]>=mod) a[i]-=mod;
}
return a;
};
auto sub=[&](auto a,auto b) -> auto
{
int n=a.size();
for(int i=0;i<n;++i)
{
a[i]-=b[i];
if(a[i]<0) a[i]+=mod;
}
return a;
};
auto half=[&](auto &a) -> auto
{
int n=a.size();
for(int i=0;i<n;++i)
{
a[i]=a[i]*inv2%mod;
}
};
auto fwt=[&](auto &a,int inv) -> void
{
int m=a.size();
for(int k=1;2*k<=m;k<<=1)
{
for(int i=0;i<m;i+=2*k)
{
for(int j=0;j<k;++j)
{
auto x=a[i+j],y=a[i+j+k];
a[i+j]=add(x,y);
a[i+j+k]=sub(x,y);
if(inv) half(a[i+j]),half(a[i+j+k]);
}
}
}
};
auto mul=[&](auto a,auto b) -> auto
{
int n=a[0].size();
int m=b[0].size();
fwt(a,0);fwt(b,0);
vector c(32,vector<int>(n+m-1,0));
for(int i=0;i<32;++i)
{
c[i]=atcoder::convolution(a[i],b[i]);
}
fwt(c,1);
return c;
};
vector g(32,vector<int>(1,0));
g[0][0]=1;
while(k)
{
if(k&1) g=mul(g,f);
f=mul(f,f);
k>>=1;
}
int ans=0;
for(int i=0;i<32;++i)
{
for(int j=0;j<=60*n;++j)
{
int j2=j-30*n;
if(i==0&&j2>0||i>0&&j2>=0) ans+=g[i][j];
}
}
ans%=mod;
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC128F
题意：
给定长度\(n\)的序列\(a[0]\sim a[n-1]\)
其中\(a[0]=a[n-1]=0\)
让你选择\(A,B\)，从\(0\)开始，每次向前走\(A\)步，向后走\(B\)，每到一个位置就加上这个位置的数字作为得分。
最后在\(n-1\)结束，同一个位置不能走两次，也不能走出去。
问最大得分。
\(n\leq 10^5\)，其他数字小于等于\(10^9\)
假设选择了\(A,B\)，那么每次向后走完的位置就是\((A-B),2*(A-B),……,k*(A-B)\)
每次向前走完的位置是\((n-1)-(A-B),(n-1)-2*(A-B),……,n-1-k*(A-B)\)
所以区别只在于和\((A-B)\)，直接枚举\((A-B)\)就行了，暴力走复杂度是调和级数。
不过要判断\(k\)应该取多少，\(k\)的上届是\(\frac{n-1}{A-B}\)
如果枚举到某个\(k\)，满足\(n-1-k*(A-B)\leq A-B\)，说明这个位置在第一次落点左边，应该中断。
如果\(n-1-k*(A-B)\)是\((A-B)\)的倍数，而且\(\frac{n-1-k*(A-B)}{A-B}\leq k\) 说明这个位置已经被跳过了，也应该中断。
其他情况都可以通过构造满足要求。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;++i)
{
cin>>a[i];
}
int ans=0;
for(int d=1;d<=n-3;++d)
{
int ret=0;
for(int k=1;k<=(n-1)/d;++k)
{
int tmp=n-1-d*k;
if(tmp<=d||tmp%d==0&&tmp/d<=k) break;
ret+=a[k*d]+a[tmp];
ans=max(ans,ret);
}
}
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC251G
题意：
给一个\(n\)个点的凸包，给\(m\)个偏移量，由这个凸包加上偏移量形成\(m\)个凸包，给\(k\)个点，问这些点是不是在所有凸包内部。
\(n\leq 50,m,k\leq 2*10^5\)
题解：
半平面交裸题了。
还有一种做法，想要在凸包内部，必须在所有线段的左半侧。
假设一个线段是\((x_{i+1}-x_i,y_{i+1}-y_i)\)，点是\((a,b)\)，如果点在线段的左半侧，要满足
\[[x_{i+1}-x_i,y_{i+1}-y_i]×[a-(x_i+u_j),b-(y_i+v_j)]\geq 0 \]其中\(×\)是叉积，\(u_j,v_j\)是第\(j\)个偏移量形成的线段
设\(R_{i,j}=[x_{i+1}-x_i,y_{i+1}-y_i]×[x_i+u_j,y_i+v_j]\)，\(q_i=x_{i+1}-x_i,p_i=y_{i+1-y_i}\)
那么就变成了
\[[q_i,p_i]×[a,b]\geq R_{i,j} \]左侧的叉积只和\(i\)有关系，右侧对每个\(i\)可以预处理\(R_{i,j}\)的最大值。
复杂度就是\(O(nm+nk)\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e18;
void __init(int n=2000) {}
struct node
{
double x,y;
inline double operator ^ (const node &t) const{return x*t.y-y*t.x;}
inline node operator + (const node &t) const{return (node){x+t.x,y+t.y};}
inline node operator - (const node &t) const{return (node){x-t.x,y-t.y};}
inline node operator * (const double &t) const{return (node){x*t,y*t};}
};
struct line
{
node a,b;//a是向量起始点，b是以a为原点向量的终点
double k;
line(){}
line(const node &aa,const node &bb):a(aa),b(bb){k=atan2(b.y,b.x);}
inline bool operator < (const line &t) const{return k<t.k;}
};
inline void main()
{
int n,m,k;
cin>>n;
vector<node> a(n+2);
vector<int> q(n+2),p(n+2);
for(int i=1;i<=n;++i)
{
cin>>a[i].x>>a[i].y;
}
a[n+1]=a[1];
for(int i=1;i<=n;++i) q[i]=a[i+1].x-a[i].x,p[i]=a[i+1].y-a[i].y;
cin>>m;
vector<int> u(m+1),v(m+1);
vector<int> r(n+1,-inf);
auto cross=[&](int a,int b,int c,int d) -> int
{
return a*d-b*c;
};
for(int i=1;i<=m;++i)
{
cin>>u[i]>>v[i];
for(int j=1;j<=n;++j)
{
r[j]=max(r[j],cross(q[j],p[j],a[j].x+u[i],a[j].y+v[i]));
}
}
cin>>k;
for(int i=1;i<=k;++i)
{
int x,y;cin>>x>>y;
bool flag=1;
for(int j=1;j<=n;++j)
{
if(cross(q[j],p[j],x,y)<r[j]) flag=0;
}
if(flag) cout<<"Yes\n";
else cout<<"No\n";
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
ABC252E
题意：
给一张图，从里面构造一个生成树，使得\(1\)号点到其他所有点的距离之和最小。
\(n,m\leq 2*10^5\)
题解：
在\(dij\)的同时选中每个点最后一次松弛的边。
不能直接从最短路图上任意选边，\(hack\)如下：
绿色的边都在最短路图上，但是到\(4\)号点的路径不是最短路。
ABC252G
题意：
给定一个树的先序遍历，\(1\)号为根节点，求满足该先序遍历的树的方案数
\(n\leq 500\)
题解：
看到这个范围就想到是区间\(dp\)
设\(dp[l][r]\)是满足该要求的方案数，我们直接把\(0\)位置空出来就好，因为最后所有的节点都是要作为子节点接到\(p[0]=1\)的下面的。
这个怎么更新呢，类似括号序列那样，应该是\((A)B\)这样更新才能保证不重不漏。
也就是一个区间，枚举左边第一颗子树的长度，然后右边作为另外的区间和左边的子树做兄弟。
但是由于先序遍历的顺序，我们要保证右边区间\([l,k-1]\)和\([k,r]\)合并的时候，\(p[l]<p[k]\)，这样才会先进左边的子树。
而且要保证左边是一整颗子树，其实只要把\([l+1,k-1]\)全部接在\(p[l]\)下面就可以了。
还要算上整个区间是一颗子树的情况，即\(dp[l][r]+=dp[l+1][r]\)，把右边区间全部接在\(p[l]\)下面
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inv2=(mod+1)/2,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int n;
cin>>n;
vector<int> p(n);
vector dp(n+1,vector<int>(n+1,1));
for(int i=0;i<n;++i)
{
cin>>p[i];
dp[i][i]=1;
}
for(int len=2;len<n;++len)
{
for(int l=1,r=l+len-1;r<n;++l,++r)
{
dp[l][r]=0;
for(int k=l+1;k<=r;++k)
{
if(p[k]>p[l]) dp[l][r]=(dp[l][r]+dp[l+1][k-1]*dp[k][r])%mod;
}
dp[l][r]=(dp[l][r]+dp[l+1][r])%mod;
}
}
cout<<dp[1][n-1];
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/