P5955 Pionek
抽搐小几何
P5955
假设已知答案向量的方向，想要答案向量长度最大，就要把再答案向量方向投影为正的向量相加。
在选中的向量中不存在两个向量投影为负（极角的差超过\(\pi\)），否则可以删去一个使总体更优。
如果把所有向量按照极角（向量平移到原点后与\(x\)轴正半轴的夹角）排序，所选择相加的向量就是一段连续的区间，所有向量呈环形存在，所以需要复制数组开环，双指针枚举左右端点求解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int maxn=2e5+10;
const double pi=acos(-1);
struct vec1
{
int x,y;//向量坐标
double theta;//极角（向量与x轴正方向夹角）
vec1 operator + (vec1 a)
{
return {x+a.x,y+a.y};
}
vec1 operator - (vec1 a)
{
return {x-a.x,y-a.y};
}
bool operator < (const vec1 &a)const //按极角从小到大排序，保证所选的向量是连续的
{
return theta<a.theta;
}
};
vec1 vec[2*maxn];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&vec[i].x,&vec[i].y);
vec[i].theta=atan2(vec[i].y,vec[i].x);
vec[n+i].x=vec[i].x; vec[n+i].y=vec[i].y; vec[i+n].theta=vec[i].theta+2*pi;
}
sort(vec+1,vec+2*n+1);
int l=1,r=1;
vec1 ans={0,0,0.0},res={0,0,0.0};
//双指针
for(l=1;l<=n;l++)//移动l
{
while(r-l+1<=n&&vec[r].theta-vec[l].theta<pi)//移动r到最接近vec[l]的相反向量最接近的向量
{
res=res+vec[r];
if(ans.x*ans.x+ans.y*ans.y<res.x*res.x+res.y*res.y) ans=res; r++;
}
res=res-vec[l]; if(ans.x*ans.x+ans.y*ans.y<res.x*res.x+res.y*res.y) ans=res;
}
printf("%lld",ans.x*ans.x+ans.y*ans.y);
}
P5953 水箱
抽象图论建模
P5952
对于相邻的两个格子，在水高度超过中间的墙后两个格子水位共同涨落，可以把两个格子合并在一起。
把格子看成点，墙看成边，边权为墙的高度，只有最小生成数上的边对答案有影响，因为格子是否连通由水是否经过最矮的墙决定。
把边按从小到大（墙按从低到高）排序，让水逐步上涨，达到一面墙的高度如果不能连通两个区域就不管它，连通两个区域后两个区域即将合并，先分别计算上涨过程新增贡献（设\(f_{uu},f_{vv}\)是两个连通块的答案，\(h_{uu},h_{vv}\)是两个连通块历史最高水位，\(h\)是当前水位（正好漫过分隔\(uu,vv\)两个连通块的最矮的墙），新连通块的答案为\((f_{uu}+h-h_{uu})\times (f_{vv}+h-h_{vv})\)），再依次漫过所有的墙。最后整个水箱被连接为一个整体，整个水箱水位共同增长至最高水位\(H\)处。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,H;
const int maxn=5e5+10;
const int mod=1e9+7;
struct node
{
int x,y,h;
bool operator < (const node &a)const
{
return h<a.h;
}
};
node e[2*maxn];
int e1;
int h[maxn],f[maxn],fa[maxn];
int getx(int i,int j)
{
return (i-1)*m+j;
}
int getfa(int x)
{
return fa[x]==x?fa[x]:fa[x]=getfa(fa[x]);
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&H);
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
e[++e1].x=getx(i,j); e[e1].y=getx(i,j+1); scanf("%lld",&e[e1].h);
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
e[++e1].x=getx(i,j); e[e1].y=getx(i+1,j); scanf("%lld",&e[e1].h);
}
}
sort(e+1,e+e1+1);
for(int i=1;i<=m*n;i++)
{
fa[i]=i; f[i]=1;
}
for(int i=1;i<=e1;i++)
{
int x=e[i].x,y=e[i].y;
int xx=getfa(x),yy=getfa(y);
if(xx!=yy)
{
fa[yy]=xx;
f[xx]=(f[xx]+e[i].h-h[xx])*(f[yy]+e[i].h-h[yy])%mod;
h[xx]=e[i].h;
}
}
int xx=getfa(1);
int ans=(f[xx]+H-h[xx])%mod;
printf("%lld",ans);
}
P5953 Różnorodność
诡异的差分and扫描线
P5953
对每一种数值做一次不重复的贡献，由于矩形之间没有包含关系使用扫描线一行一行扫描来维护当前位置为左上角的答案，加入或删除一个矩形只会影响一段连续的区间，所以要进行差分，用\(set\)维护矩形左右端点的位置，每一条边插入时插入\(multiset\)删除时确定影响范围，在差分数组上修改，最后做前缀和把差分数组还原。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
const int maxn=3010;
int a[maxn][maxn],sz[100010],sum[maxn][maxn];
struct node
{
int c/*数值*/,x,y/*出现的位置*/;
};
node b[maxn*maxn];
struct node1
{
int l,r;
bool operator < (const node1 &x)const
{
return l<x.l;
}
};
multiset<node1> c;
multiset<node1>::iterator it,i;
void add(int x,int l,int r,int t)//第x行 l到r范围内 t=0为插入 t=1为撤销 一个数值的贡献
{
if(x>n) return;
if(!t) c.insert({l,r});//新人来力
it=c.lower_bound({l,r});//锁定目标
int lx,rx;
if(it==c.begin()) lx=0;
else i=it,i--,lx=(*i).r;
i=it;
i++;
if(i==c.end()) rx=m+1;
else rx=(*i).l;
lx++; rx--;
lx=max(lx,l); rx=min(rx,r);
if(lx<=rx)//差分
{
int k=t?-1:1;
sum[x][lx]+=k;
sum[x][rx+1]-=k;
}
if(t) c.erase(it);//再见了旧矩形，送走它去远航
}
void solve(int l,int r)//扫描线添加一个数字的贡献
{
int h1=l-1,h2=l-1;
while(h1<r&&h2<r)
{
int t0=b[h1+1].x,t1=b[h2+1].x+k;//矩形b[h1+1]的上下边界
if(t0<=t1) ++h1,add(t0,b[h1].y,b[h1].y+k-1,0);
if(t1<=t0) ++h2,add(t1,b[h2].y,b[h2].y+k-1,1);
}
for(int i1=h2+1;i1<=r;i1++)
{
add(b[i1].x+k,b[i1].y,b[i1].y+k-1,1);
}
c.clear();
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
++sz[a[i][j]];
}
}
for(int i=1;i<=100000;i++) sz[i]+=sz[i-1];
for(int i1=n;i1>=1;i1--)
{
for(int j=m;j>=1;j--)
{
b[sz[a[i1][j]]--]={a[i1][j],i1,j};//把数值相等的放在一起
}
}
int l=1,r;
while (l<=n*m) //提取数值相等的部分，分别计算贡献
{
r=l;
while(b[r+1].c==b[l].c) r++;
solve(l,r);
l=r+1;
}
for(int i=1;i<=n;i++) //前缀和把所有区域的贡献加回来
{
for(int j=1;j<=m;j++) sum[i][j]+=sum[i][j-1];
for(int j=1;j<=m;j++) sum[i][j]+=sum[i-1][j];
}
int sum1=0,ans=0;
for(int i=k;i<=n;i++)
{
for(int j=k;j<=m;j++) sum1+=sum[i][j],ans=max(ans,sum[i][j]);
}
printf("%lld %lld",ans,sum1);
}
P5959 Plan metra
可怕小构造
P5959
把\(1\)到\(n\)的路径单独拿出来，剩下的点只有两种情况：
- 在从\(1\)到\(n\)的链上\(dis(1,u)+dis(u,n)=dis(1,n)\)
- 直接与这条链上的点相连\(dis(1,u)+dis(u,n)-dis(1,n)=2\times dis(u,s)\)（\(u\)为当前点，\(s\)为路径上应该与\(u\)直接相连的点）
（如果不在链上的点可与其他一个也不在链上的点连边，它一定可以通过改变边权的方式连到链上，不会影响它与\(1\)或\(n\)的距离）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=5e5+10;
const int maxd=1e6+10;
int d1[maxn]/*点i与1的距离*/,dn[maxn]/*点i与n的距离*/,k=maxd/*1到n连接的链的长度*/,id[maxd]/*链中与1距离为i的点*/,fa[maxn]/*链外点向链中哪个点连边*/;
int solve1()//1与n直接相连，其他点与1或n相连 |dis(1,i)-dis(i,n)|=dis(1,n)
{
int d=abs(d1[2]-dn[2]);
if(!d)return 0;
for(int i=3;i<n;i++)
{
if(d!=abs(d1[i]-dn[i])) return 0;//链中除1和n外还有其他点
}
cout<<"TAK"<<endl<<"1 "<<n<<' '<<d<<endl;
for(int i=2;i<n;i++)
{
if(d1[i]>dn[i]) printf("%d %d %d\n",n,i,dn[i]);
if(dn[i]>d1[i]) printf("%d %d %d\n",1,i,d1[i]);
}
return 1;
}
int solve2()
{
id[0]=1; id[k]=n;
for(int i=2;i<n;i++)//链中点插入链
{
if(d1[i]+dn[i]==k)
{
if(id[d1[i]]) {return 1;}
else id[d1[i]]=i;
}
}
for(int i=2;i<n;i++)//链外点与链中点相连
{
if(d1[i]+dn[i]==k) continue;
if((d1[i]+dn[i]-k)%2) return 1;
int d2=(d1[i]+dn[i]-k)/2;
if(!id[d1[i]-d2]) return 1;
fa[i]=id[d1[i]-d2];
}
return 0;
}
int fg,w[maxn];
int main()
{
scanf("%d",&n);
if(n==2){cout<<"TAK"<<endl<<1<<' '<<n<<' '<<1;return 0;}
for(int i=2;i<n;i++) scanf("%d",&d1[i]);
for(int i=2;i<n;i++) scanf("%d",&dn[i]);
for(int i=2;i<n;i++) dn[i]+d1[i]<k?k=dn[i]+d1[i]:1;
d1[n]=k;dn[1]=k;
if(solve1()) return 0;
if(solve2()) {cout<<"NIE";return 0;}
int u=1,v;
cout<<"TAK"<<endl;
for(int i=1;i<=k;i++)
{
if(!id[i]) continue;
v=id[i];
printf("%d %d %d\n",u,v,i-d1[u]);
u=v;
}
for(int i=2;i<n;i++)
{
if(!fa[i]) continue;
printf("%d %d %d\n",fa[i],i,abs(d1[i]-d1[fa[i]]));
}
}