牛客IOI周赛17-提高组题解

可怜的比赛又被神仙xgc秒飞了……

T1

考虑枚举断掉哪一条白线，断掉这条白线之后，要使树不联通，就要把子树里延伸出子树外的黑线都删掉，显然有两条及以上时不可能做到，一条时就把这条删掉，没有时就可以随便删一条黑线，用树上差分维护一下即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 600010

int n,m;
struct edge{int y,next;}e[maxn<<1];
int first[maxn],len=0;
void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;}
int f[maxn][20],g[maxn],deep[maxn];
void dfs(int x,int fa,int dep)
{
    f[x][0]=fa;deep[x]=dep;
    for(int i=first[x];i;i=e[i].next)
    if(e[i].y!=fa)dfs(e[i].y,x,dep+1);
}
int get_lca(int x,int y)
{
    if(deep[x]>deep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(deep[f[y][i]]>=deep[x])y=f[y][i];
    if(x!=y){for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];x=f[x][0];}
    return x;
}
long long ans=0;
void get_ans(int x,int fa)
{
    for(int i=first[x];i;i=e[i].next)
    if(e[i].y!=fa)get_ans(e[i].y,x),g[x]+=g[e[i].y];
    if(g[x]==1&&x!=1)ans++;//只能删子树里延伸出去的那条
    if(g[x]==0&&x!=1)ans+=m;//随便删一条黑线
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1,x,y;i<n;i++)scanf("%d %d",&x,&y),
    buildroad(x,y),buildroad(y,x);dfs(1,0,1);
    for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        int lca=get_lca(x,y);
        g[x]++,g[y]++;g[lca]-=2;
    }
    get_ans(1,0);printf("%lld",ans);
}

T2

这个打个暴力然后去OEIS上找找规律就可以发现 $[x^n]F^i=(a+1)[x^{n-1}]F^i+b[x^{n-2}]F^i$ 这样的规律了。

证明也不难，可以发现 $F=axF+bx^2F+x$ ，即 $F=\dfrac x {1-ax-bx^2}$ 。

设 $G(x)=\sum_{i=1}F^i(x)$ ，发现这是个等比数列的形式，所以有 $G=\dfrac F {1-F}$ 。

代入一下得到：
$ $\begin{aligned} G&=\frac x {1-ax-bx^2}/\left( 1-\frac x {1-ax-bx^2}\right)\\ &=\frac x {1-ax-bx^2}\times \frac {1-ax-bx^2} {1-(a+1)x-bx^2}\\ &=\frac x {1-(a+1)x-bx^2} \end{aligned}$ $

转化回去就得到 $G$ 的递推式了，就是上面那个。

如果用一下矩阵快速幂还能做到 $O(\log n)$ 。

代码如下：

#include <cstdio>
#define maxn 2000010
#define mod 998244353

int n,a,b,f[maxn];

int main()
{
    scanf("%d %d %d",&n,&a,&b);
    f[1]=1,f[2]=a+1;for(int i=3;i<=n;i++)f[i]=(1ll*(a+1)*f[i-1]%mod+1ll*b*f[i-2]%mod)%mod;
    printf("%d",f[n]);
}

T3

不会做……题解也看不懂……只能拿头膜神仙的代码……

考虑枚举每一条线段 $st$ ，假设站在 $s$ 往 $t$ 看，然后分别统计线段前后左右四个方向的三角形数。

先考虑左右的，这个很简单，将其他点按照位置分成左右两堆，记在 $c,d$ 两个数组内，然后从一堆里面随便选 $3$ 个点构成三角形都可以，方案数就是 $C_{t1}^3+C_{t2}^3$ 。

然后再考虑前后的，前后的三角形肯定满足：两个点在 $c$ 内，一个点在 $d$ 内，或者反过来。这部分结合代码比较容易理解。

最后再加上这条线段被多少个三角形包含。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 310
#define MS(f) memset(f,0,sizeof(f))
#define ll long long

int n;
struct point{
    ll x,y;int id;point(ll xx=0,ll yy=0,int Id=0):x(xx),y(yy),id(Id){};
    point operator +(const point &B)const{return point(x+B.x,y+B.y);}
    point operator -(const point &B)const{return point(x-B.x,y-B.y);}
    ll operator ^(const point &B)const{return x*B.y-y*B.x;}
    bool operator ==(const point &B)const{return x==B.x&&y==B.y;}
}a[maxn],s,t;vector<point> b[maxn];
ll ans=0,S1[maxn],S2[maxn],T1[maxn],T2[maxn];
point c[maxn],d[maxn];int t1,t2;
void solve(int x,int y)
{
    MS(S1);MS(S2);MS(T1);MS(T2);t1=t2=0;
    for(int i=0;i<n-1;i++)if(b[x][i]==t)
    for(int j=(i+1)%(n-1);j!=i;j=(j+1)%(n-1))
    if(((b[x][j]-s)^(t-s))>0)c[++t1]=b[x][j];else d[++t2]=b[x][j];
    //右边的点放在c里，左边的放在d里
    ans+=t1*(t1-1)*(t1-2)/6+t2*(t2-1)*(t2-2)/6;//左右的方案数
    int j=t2;for(int i=t1;i>=1;i--)//st下面的方案数
    {
        while(j>=1&&((s-c[i])^(d[j]-c[i]))<0)S2[d[j].id]=t1-i,j--;
        S1[c[i].id]=j; ans+=(t1-i)*j+j*(j-1)/2;
        //S1记录c[i]能够和多少个d[j]构成一条在s下方的线段，S2记录d[j]
        //ans得到的贡献是选c[i]，再选两个点的方案数
    }
    while(j>=1)S2[d[j].id]=t1,j--; t1=t2=0;

    for(int i=0;i<n-1;i++)if(b[y][i]==s)
    for(int j=(i+1)%(n-1);j!=i;j=(j+1)%(n-1))
    if(((b[y][j]-s)^(t-s))>0)c[++t1]=b[y][j];else d[++t2]=b[y][j];
    j=1;for(int i=1;i<=t1;i++)
    {
        while(j<=t2&&((t-c[i])^(d[j]-c[i]))>0)T2[d[j].id]=i-1,j++;
        T1[c[i].id]=t2-j+1; ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
    }
    while(j<=t2)T2[d[j].id]=t1,j++;
    for(int i=1;i<=n;i++)ans+=S1[i]*T1[i]+S2[i]*T2[i];//包含该线段的三角形数
}
bool cmp(point x,point y){
    ll xx=(x-s)^(t-s),yy=(y-s)^(t-s);
    if(xx*yy>0)return ((x-s)^(y-s))<0;return xx>0;
}

int main()
{
    scanf("%d",&n);if(n<5)return printf("0"),0;
    for(int i=1;i<=n;i++)scanf("%lld %lld",&a[i].x,&a[i].y),a[i].id=i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)if(i!=j)b[i].push_back(a[j]);
        s=a[i];t=b[i][0];sort(b[i].begin()+1,b[i].end(),cmp);//顺时针排序
    }
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)s=a[i],t=a[j],solve(i,j);
    printf("%lld\n",ans);
}