中间咕的几次考试就先咕着吧……

A.夜莺与玫瑰

枚举斜率。只考虑斜率为正且不平行于坐标轴的直线，最后把$ans\times 2$再$+1$即可。

首先肯定需要用$gcd(i,j)==1$确保斜率的唯一性，但由于题目中Deadline的定义是直线不是线段，所以一个方向只能有一条，需要去重。那么我们计算一条直线的贡献，当且仅当它和它的前驱线段在点阵内且后继线段不在点阵内。

暴力求解：$ans=\sum \limits_{i=1}^{n-1} \sum \limits_{j=1}^{m-1} [gcd(i,j)==1] ((n-i)\times(m-j)-\max (n-2i,0) \times \max (m-2j,0))$，时间复杂度$O(n^2 T)$。

尝试通过预处理降低每次询问的复杂度：计算对于每个$i$与它互质的$j$的前缀个数与前缀和，之后把柿子拆一下复杂度就变成$O(nT)$的了。

卡内存？值域不超过4000的数组为什么不用short呢？(滑稽

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int mod=(1<<30),N=4005;

typedef long long ll;

int n,m,T;

int sum[N][N];

short gcd[N][N],copr[N][N];

void work()

{

    scanf("%d%d",&n,&m);

    ll ans=0;

    for(int i=1;i<=n-1;i++)

    {

        ll num1=1LL*(n-i)*(1LL*copr[i][m-1]*m-sum[i][m-1])%mod;

        if(n-2*i>0)num1=(num1-1LL*(n-2*i)*(1LL*m*copr[i][m/2]-2*sum[i][m/2])+mod)%mod;

        ans+=num1,ans%=mod;

    }

    /*for(int i=1;i<=n-1;i++)

        for(int j=1;j<=m-1;j++)

            if(gcd(i,j)==1)ans+=(1LL*(n-i)*(m-j)-max(n-i*2,0LL)*max(m-j*2,0LL));*/

    printf("%lld\n",(ans*2%mod+1LL*n+m)%mod);

}

int main()

{

    scanf("%d",&T);

    gcd[1][1]=gcd[1][2]=gcd[2][1]=1;

    for(int i=1;i<=4000;i++)

        gcd[i][0]=i,gcd[i][1]=gcd[1][i]=1;

    for(int i=1;i<=4000;i++)

    {

        for(int j=1;j<=4000;j++)

        {

            gcd[i][j]=gcd[min(i,j)][max(i,j)%min(i,j)];

            copr[i][j]=copr[i][j-1],sum[i][j]=sum[i][j-1];

            if(gcd[i][j]==1)copr[i][j]++,sum[i][j]+=j;

            //if(i<=50&&j<=50)cout<<i<<' '<<j<<' '<<gcd[i][j]<<' '<<copr[i][j]<<' '<<sum[i][j]<<endl;

        }

    }

    while(T--)work();

    return 0;

}

B.影子

树上的题居然还能并查集乱搞，学习了。

把所有的点按权值从大到小排序，然后扫一遍。对于每个点，尝试将它与和它相连且已经扫过的每个点合并。

并查集要维护当前集合中的最长链长度和最长链的两个端点。考虑合并时怎么处理两个集合的信息：新集合的最长链可能还是原来那两个集合中最长链的某一条，也有可能跨越了两个集合、由两个集合的最长链端点拼凑而来的。除此之外不会再有其它情况了。所以预处理一下到根的距离$dis[]$以及倍增lca，合并时枚举6种情况找到最优作为新集合的信息即可。

每个点合并完之后用当前点权$\times$当前点集最长链长度即可。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define pa pair<int,int>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

typedef long long ll;

const int N=1e5+5;

int T,n;

int tot,head[N],nxt[N<<1],to[N<<1],fa[N][25],dep[N],vis[N];

ll w[N],len[N<<1],dis[N];

pa p[N];

void add(int x,int y,ll z)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

    len[tot]=z;

}

void dfs(int x,int f)

{

    fa[x][0]=f;

    for(int i=1;i<=20;i++)

        fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        dep[y]=dep[x]+1;

        dis[y]=dis[x]+len[i];

        dfs(y,x);

    }

}

int lca(int x,int y)

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)

        if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    for(int i=20;i>=0;i--)

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    return fa[x][0];

}

namespace U

{

    int fa[N],node[N][3];

    ll d[N];

    void ini()

    {

        for(int i=1;i<=n;i++)

            fa[i]=i,node[i][0]=i,node[i][1]=i,d[i]=0;

    }

    int findf(int x)

    {

        if(x==fa[x])return x;

        return fa[x]=findf(fa[x]);

    }

    void Merge(int x,int y)

    {

        int node1=node[x][0],node2=node[x][1];

        ll maxd=d[x];

        if(maxd<d[y])maxd=d[y],node1=node[y][0],node2=node[y][1];

        for(int i=0;i<2;i++)

        {

            for(int j=0;j<2;j++)

            {

                int LCA=lca(node[x][i],node[y][j]);

                ll nowd=dis[node[x][i]]+dis[node[y][j]]-dis[LCA]*2;

                if(maxd<nowd)maxd=nowd,node1=node[x][i],node2=node[y][j];

            }

        }

        d[x]=maxd;

        node[x][0]=node1;node[x][1]=node2;

    }

    void merge(int x,int y)

    {

        int fx=findf(x),fy=findf(y);

        if(fx!=fy)Merge(fx,fy),fa[fy]=fx;

    }

}

void work()

{

    n=read();

    tot=0;

    for(int i=1;i<=n;i++)

    {

        w[i]=head[i]=dep[i]=len[i]=dis[i]=vis[i]=0;

        for(int j=0;j<=20;j++)

            fa[i][j]=0;

    }

    U::ini();

    for(int i=1;i<=n;i++)

        w[i]=read(),p[i]=make_pair(-w[i],i);

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();ll z=read();

        add(x,y,z);add(y,x,z);

    }

    dep[1]=1;

    dfs(1,0);

    sort(p+1,p+n+1);ll ans=0;

    for(int j=1;j<=n;j++)

    {

        int x=p[j].second;

        for(int i=head[x];i;i=nxt[i])

        {

            int y=to[i];

            if(vis[y])U::merge(x,y);

        }

        vis[x]=1;

        ans=max(ans,U::d[x]*w[x]);

    }

    printf("%lld\n",ans);

    return ;

}

int main()

{

    T=read();

    while(T--)work();

    return 0;

}

C.玫瑰花精

$O(nm)$暴力有60分？什么辣鸡题

线段树。每个节点维护4个值：

$lp[]:$该节点维护区间内最左的花精的位置

$rp[]:$.....................................右.......................

$mi[]:$该节点维护区间内花精之间最长距离/2

$pos[]:$该节点维护区间内的答案(离得最远的两只花精的中间位置)

然后pushup()的时候分类讨论一下就行了。思想类似于山海经那道题，不过具体实现简单很多。

注意对于每个加入操作，要特殊考虑最左和最右端点是否空着。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int N=2e5+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,m,loc[1000005];

int lp[N<<2],rp[N<<2],pos[N<<2],mi[N<<2];

#define ls(k) (k)<<1

#define rs(k) (k)<<1|1

void up(int k)

{

    lp[k]=lp[ls(k)]?lp[ls(k)]:lp[rs(k)];

    rp[k]=rp[rs(k)]?rp[rs(k)]:rp[ls(k)];

    mi[k]=mi[ls(k)];

    pos[k]=pos[ls(k)];

    if(!rp[ls(k)]||!lp[rs(k)])return ;

    int val=(lp[rs(k)]-rp[ls(k)])>>1;

    if(val>mi[k])mi[k]=val,pos[k]=(rp[ls(k)]+lp[rs(k)])>>1;

    if(mi[rs(k)]>mi[k])mi[k]=mi[rs(k)],pos[k]=pos[rs(k)];

}

void update(int k,int l,int r,int Pos,int op)

{

    if(l==r)

    {

        if(op==1)

        {

            lp[k]=l;rp[k]=r;

            pos[k]=mi[k]=0;

        }

        else lp[k]=rp[k]=pos[k]=mi[k]=0;

        return ;

    }

    int mid=l+r>>1;

    if(Pos<=mid)update(ls(k),l,mid,Pos,op);

    else update(rs(k),mid+1,r,Pos,op);

    up(k);

}

int main()

{

    n=read();m=read();

    while(m--)

    {

        int op=read(),x=read();

        if(op==1)

        {

            if(!lp[1]){loc[x]=1;puts("1");update(1,1,n,1,1);continue;}

            int maxx=-0x3f3f3f3f;

            maxx=max(lp[1]-1,max(mi[1],n-rp[1]));

            if(maxx==lp[1]-1)loc[x]=1;

            else if(maxx==mi[1])loc[x]=pos[1];

            else loc[x]=n;

            printf("%d\n",loc[x]);

            update(1,1,n,loc[x],1);

        }

        else update(1,1,n,loc[x],2);

    }

    return 0;

}

巴特西

[CSP-S模拟测试41]题解

A.夜莺与玫瑰

B.影子

C.玫瑰花精

最新文章

热门文章