csp-s模拟3
A. 奇观
观察到 \(c\) 和 \(f\) 互不影响，所以分开算就行，枚举相连的边太多了，会 \(T\),所以我们把总情况找出来，减去删去的边的
方案数即可，记 \(f_{u,x}\) 表示 \(u\) 节点往后跟 \(x\) 个长度的方案数，有 \(f_{u,x}=\sum_{x->y} \limits f_{y,x-1}\)
边界 \(f_{u,1}=\) 其度数,这是 \(c\) 的，\(f\) 就是长度为 \(3\) 的链后面随便取俩点
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int mod=998244353;
const int maxn=1e5+10;
using namespace std;
int n,m,sum,ans,temp,in[maxn];
int f[maxn][4];
vector<int>q[maxn];
unordered_map<int,int>a[maxn];
signed main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
fill(in+1,in+1+n,n-1);
for(int i=1,x,y;i<=m;i++)
{
cin>>x>>y;
in[x]--,in[y]--;
q[x].push_back(y);
q[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
f[i][1]=in[i];
temp=(temp+f[i][1])%mod;
}
for(int i=1;i<=n;i++)
{
f[i][2]=temp-f[i][1];
for(int j=0;j<q[i].size();j++)
{
f[i][2]-=f[q[i][j]][1];
}
ans=(ans+f[i][2])%mod;
}
temp=0;
for(int i=1;i<=n;i++)
{
f[i][3]=ans-f[i][2];
for(int j=0;j<q[i].size();j++)
{
f[i][3]-=f[q[i][j]][2];
}
temp=(temp+f[i][3])%mod;
}
// cout<<temp;
sum=1ll*temp*temp%mod;
ans=0;
for(int i=1;i<=n;i++)
{
ans=(ans+1ll*f[i][2]*in[i]%mod*in[i]%mod)%mod;
}
// cout<<ans;
cout<<1ll*sum*ans%mod;
return 0;
}
/*
4 1
1 2
*/
B. 铁路
新开一个数组来对应新建节点的位置，把位置指到合并的点中深度最小的点即可,这里合并时用并查集维护每个联通块
压缩路径也到深度最小的点，这样就对应起来了
点击查看代码
#include<bits/stdc++.h>
const int maxn=5e5+10;
using namespace std;
int head[maxn],nxt[maxn<<1],to[maxn<<1],tot;
int n,m,fa[maxn],last[maxn],pos[maxn<<1],size;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void addm(int x,int y)
{
add(x,y),add(y,x);
}
int pre[maxn],deep[maxn],st[20][maxn],cnt;
struct Lca
{
int get(int x,int y){return deep[x]<deep[y]?x:y;}
void lsx(int x,int fa)
{
pre[x]=++cnt,last[x]=fa,st[0][cnt]=fa;deep[x]=deep[fa]+1;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa) lsx(to[i],x);
}
void init()
{
lsx(1,0);
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n-(1<<i)+1;j++)
st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
int lca(int x,int y)
{
if(x==y) return x;
if((x=pre[x])>(y=pre[y])) swap(x,y);
int l=__lg(y-x);
return get(st[l][x+1],st[l][y-(1<<l)+1]);
}
}e;
void merge(int x,int y,int i)
{
int p=e.lca(x,y);
int a=find(x),b=find(y),c=find(p);
// cout<<a<<" "<<b<<" "<<p<<endl;
while(find(a)!=find(c))
{
a=fa[a]=find(last[a]);
size--;
}
while(find(b)!=find(c))
{
// cout<<b<<" "<<last[b]<<"!"<<endl;
b=fa[b]=find(last[b]);
size--;
}
pos[n+i]=c;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
size=n;
for(int i=1;i<=n;i++)fa[i]=i,pos[i]=i;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
addm(x,y);
}
e.init();
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
x=pos[x];
y=pos[y];
// cout<<x<<" "<<y<<"!"<<endl;
merge(x,y,i);
cout<<size<<'\n';
}
return 0;
}
/*
10 5
2 1
9 7
4 10
1 8
3 4
1 7
3 2
6 1
1 5
1 6
8 4
5 12
13 13
9 14
*/
C. 光纤
破防了，这东西谁愿意改谁改，我改不了一点。。。
找凸包的每一条边的高，找最小的那个就是答案
点击查看代码
#include<bits/stdc++.h>
#define int __int128
const int maxn=1e6+10;
using namespace std;
typedef pair<int,int>pr;
int n,top,st[maxn];
pr p[maxn];
bool used[maxn];
template<typename T> inline T read() {
T X = 0; bool flag = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
if (flag) return X;
return ~ (X - 1);
}
template<typename T> inline void write(T X) {
if (X < 0) {putchar('-'); X = ~ (X - 1);}
int s[50], top = 0;
while (X) {s[++top] = X % 10; X /= 10;}
if (!top) s[++top] = 0;
while (top) putchar(s[top--] + '0');
return;
}
pr operator - (pr a,pr b)
{
return {a.first-b.first,a.second-b.second};
}
int cross(pr a,pr b,pr c)
{
pr u,v;
u=b-a,v=c-a;
return u.first*v.second-v.first*u.second;
}
pr s1(pr a,pr b,pr c)
{
pr u,v;
u=b-a,v=c-a;
int x=(u.first*v.second-v.first*u.second);
return {x*x,u.first*u.first+u.second*u.second};
}
void pre()
{
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)
{
while(top>=2&&cross(p[st[top-1]],p[st[top]],p[i])>0)
{
used[st[top]]=0;
top--;
}
st[++top]=i;
used[i]=1;
}
used[1]=0;
for(int i=n-1;i>=1;i--)
{
if(used[i])continue;
while(top>=2&&cross(p[st[top-1]],p[st[top]],p[i])>0) top--;
st[++top]=i;
}
}
pr yue(pr x)
{
int a=x.first,b=x.second,c=__gcd(a,b);
return {a/c,b/c};
}
bool cmp(pr a,pr b)
{
pr c={a.first*b.second,a.second*b.second};
pr d={b.first*a.second,b.second*a.second};
return c.first>d.first;
}
pr min(pr a,pr b)
{
if(!b.first) return a;
return cmp(a,b)?b:a;
}
void solve()
{
pr a=p[st[1]],b=p[st[2]],c=p[st[3]];
pr ans=s1(a,b,c);
int k=3;
for(int i=4;i<top;i++)
{
pr d=s1(a,b,p[st[i]]);
if(d.first>ans.first)
{
ans=d;
k=i;
}
}
// write(ans.first);
int x=2,y=3;
pr l={0,1};
for(int i=k,cnt=1;cnt<top-1;cnt++,x=(x+1)%top,y=(y+1)%top)
{
if(!x)x++;if(!y)y++;
while(1)
{
a=p[st[x]],b=p[st[y]],c=p[st[i]];
pr d=s1(a,b,c);
d=yue(d),ans=yue(ans);
if(cmp(d,l))l=d;
else
{
i--;
if(!i)i=top-1;
break;
}
i=(i+1)%top;
if(!i)i++;
if(i+1==x||i+1==y) break;
}
// write(l.first);
ans=min(ans,l);
}
// cout<<ans.first<<" "<<ans.second<<endl;
ans={ans.first,ans.second*4};
ans=yue(ans);
write(ans.first);
cout<<"/";
write(ans.second);
}
signed main()
{
freopen("ex_A2.in","r",stdin);
// freopen("a.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
n=read<int>();
for(int i=1;i<=n;i++)
{
int x,y;
x=read<int>(),y=read<int>();
p[i]={x,y};
}
pre();
solve();
return 0;
}
/*
5
0 0
2 0
1 3
1 2
1 1
*/