标签：ch return int st while ans CSP 模拟
挺有趣的思路，每个字母相互独立， \(C\) 和 \(F\) ，我们可以把 \(C\) 分成一个两个端点和一个三个端点的路径（以同一个起点开始）,而 \(F\) 为了方便统计，我们也可以把它分成两个两个端点和一个三个端点的路径（同样是以同一个端点为起点）。那我们定义 $s_{i} = \sum_{j} [(i,j)双向联通] $ ，\(d_{i}= \sum_{j,k}[(i,j,k)双向联通]=\sum_{j}s_{j}[i,j双向联通]\)
那 \(C=\sum_{i}s_{i}*d_{i}\) , \(F=\sum_{i}s_{i}^{2}*d_{i}\) 。
正着遍历肯定会 \(T\) ，比较好知道如果不删点的话，答案为 \(n^{3}*(n-1)^{10}\) ,那我们可以试着看看删掉一个点会对答案造成什么影响，我们先把每个点 \(s_{i}\) 赋成 \((n-1)\) , \(d_{i}\) 赋成 \((n-1)^{2}\),那考虑删点就两种情况，一种是删的点的影响，一种是删掉这个点对其他点的影响，先看后一种，很明显被删的点的 \(s_{i}\) 应减去 \(1\) ,那每个点的 \(d_{i}\) 应该减去 \(2\) （删两个点）,那总共每个节点应减去 \((n*2)\) 个点，那只考虑这种肯定有所欠缺，我们既没有考虑这样对删掉点本身不再给另一个点施加影响，而且没考虑删掉点本身的 \(d_{i}\) 不应计算。
现在再考虑第一种情况，对于删掉的点的\(s_{i}\)减去 \(1\) ，\(d_{i}\) 则要减去 \((n-1)\) ，我们设被删的两个点为\(x,y\)，目前就两个问题，一个是已经被删的点再发生变化时，不会再对另一个点造成贡献（ \(x,y\) 已经被删, \(y\) 和另一个点再被删）。一个是减去点本身 \(d_{i}\) 也不应该被自身影响而减去值。知道了删点所造成的影响之后就比较好处理了，直接看代码吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+107;
const int mod=998244353;
int n,m;
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
int s[N],d[N];
int a[N],b[N];
int vis[N];
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++) s[i]=n-1,d[i]=s[i]*s[i]%mod;
for(int i=1;i<=m;i++)
{
a[i]=read(),b[i]=read();
vis[a[i]]++,vis[b[i]]++;
}
for(int i=1;i<=m;i++)
{
d[a[i]]=(d[a[i]]-(n-1)+vis[b[i]]+mod)%mod;
d[b[i]]=(d[b[i]]-(n-1)+vis[a[i]]+mod)%mod;
s[a[i]]--,s[b[i]]--;
}
for(int i=1;i<=n;i++)
{
d[i]=(d[i]-m*2+(n-1)-s[i]+mod)%mod;
}
int ans1=0,ans2=0,ans=1;
for(int i=1;i<=n;i++)
{
(ans1+=d[i]*s[i]%mod)%=mod;
(ans2+=d[i]*s[i]%mod*s[i])%=mod;
}
ans=ans1*ans1%mod*ans2%mod;
printf("%lld",ans);
}
比较明显可以用并查集来维护点的合并，一个问题就是搜一个点到新开的点时不太好处理，我们可以做一个新开点到原图的映射（好吧，其实也挺好处理的），那这题就没啥了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+107;
int n,m,ans;
int d[N<<1];
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
int h[N<<1],to[N<<1],nxt[N<<1],tot;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
int f[N][23],dep[N];
bool vis[N];
void dfs(int u,int fat)
{
dep[u]=dep[fat]+1;
f[u][0]=fat;
for(int i=h[u];i;i=nxt[i])
{
int v=to[i];
if(v==fat) continue;
if(!vis[v])
{
vis[v]=1;
dfs(v,u);
}
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
}
if(x==y) return x;
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int fa[N<<1];
int find(int x)
{
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y,int i)
{
if(x>n) x=d[x];
if(y>n) y=d[y];
int z=find(lca(x,y));
d[n+i]=z;
while(x!=z)
{
fa[x]=z;
x=find(f[x][0]);
ans--;
}
while(y!=z)
{
fa[y]=z;
y=find(f[y][0]);
ans--;
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++) fa[i]=i, d[i]=i;
for(int i=1;i<=n-1;i++)
{
int x=read(),y=read();
add(x,y); add(y,x);
}
dfs(1,1);
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
ans=n;
for(int i=1;i<=m;i++)
{
int a=read(),b=read();
merge(a,b,i);
printf("%d\n",ans);
}
}
计算几何
我们维护一个凸包，然后直接做旋转卡壳，额，剩下没啥了，都是板子。好吧，还是稍微说点，主要是了解一下向量的叉乘（向量积 \(cross\) ）和极角排序，向量积它的数值的几何意义比较重要，在二维空间里，它表示是两条边所构成平行四边形的面积，在三维空间里，它表示垂直于两条直线所在平面的法向量。而极角排序可以使用叉积来排序，也可以使用 \(C++\) 自带的 \(atan2\) 排序，它返回的是点 \((x,y)\) 与原点 \((0,0)\) 连线和 \(x\) 轴正方向的夹角弧度（ \(atan2()\) 相对于叉积排序精度低，但也够用了，而且它比较快，还方便）。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+107;
int n,m;
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
void write(__int128 x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
struct Ans
{
__int128 z,m;
double val;
bool operator >=(const Ans &a)const{return val>=a.val;}
Ans min(Ans a,Ans b){return a.val<b.val?a:b;}
}ans;
struct lmy
{
int x,y;
double k;
bool operator ==(const lmy &a)const{return (a.x==x)&&(a.y==y);}
}st[N],vec[N];
int tp;
bool comp1(lmy a,lmy b)
{
if(a.y==b.y) return a.x<b.x;
else return a.y<b.y;
}
int cross(lmy a,lmy b,lmy c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
//double dis(lmy a,lmy b)
//{
// return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
//}
Ans dis(lmy a,lmy b,lmy c)
{
__int128 yz=b.y-c.y,xz=b.x-c.x,n=a.x-b.x,m=b.y-a.y;
Ans w={yz*yz*n*n+xz*xz*m*m+2*xz*yz*n*m,xz*xz+yz*yz,1.0*(yz*yz*n*n+xz*xz*m*m+2*xz*yz*n*m)/(xz*xz+yz*yz)};
return w;
}
bool comp(lmy a,lmy b)
{
if(a.k!=b.k) return a.k<b.k;
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int xx,yy;
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n=read();
if(n<=2)
{
printf("0/1");
return 0;
}
for(int i=1;i<=n;i++) vec[i]={read(),read()};
sort(vec+1,vec+n+1,comp1);
n=unique(vec+1,vec+1+n)-(vec+1);
st[++tp]=vec[1];
xx=st[tp].x,yy=st[tp].y;
for(int i=2;i<=n;i++) vec[i].k=atan2(vec[i].y-yy,vec[i].x-xx);
sort(vec+2,vec+1+n,comp);
st[++tp]=vec[2];
for(int i=2;i<=n;i++)
{
while(tp>1&&cross(st[tp-1],st[tp],vec[i])<0) tp--;
st[++tp]=vec[i];
}
st[++tp]=st[1];
int l=1,r=1;
for(l=1;l<tp;l++)
{
int last=r;
while(dis(st[r%tp+1],st[l+1],st[l])>=dis(st[r],st[l+1],st[l]))
{
r=r%tp+1;
if(r==last) return printf("0/1"),0;
}
ans=ans.min(ans,dis(st[r],st[l],st[l+1]));
}
ans.m*=4;
__int128 gcd=__gcd(ans.m,ans.z);
write(ans.z/gcd);
printf("/");
write(ans.m/gcd);
return 0;
}
超级线段树，不会，咕咕咕……
标签：ch,
return,
int,
st,
while,
ans,
CSP,
模拟
From： https://www.cnblogs.com/zhengchenxi/p/18429075