头像

垫底抽风

yxc粉丝后援会


访客:21131

离线:15小时前



垫底抽风
15小时前

题目描述中指出 $1 \leq P \leq 10 ^ 9$,但在题目中的一组数据中(可能是第 $7$ 组数据),$P$ 给到了 $10^9+7$

虽然超的不多,但是我被卡了

建议将题目描述改为 $1 \leq P \leq 10 ^ 9 + 7$

注:下面这段代码会 $\text{WA}$ 在那组 $P = 10 ^ 9 + 7$ 的数据上

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N=100005;

int n,m,mod;
int root,idx;
struct Point
{
    int s[2],p,v,size;
    ll sum,add,mul;
}tr[N];
int w[N];

void pushup(int u)
{
    tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
    tr[u].sum=(tr[tr[u].s[0]].sum+tr[tr[u].s[1]].sum+tr[u].v)%mod;
}

void pushdown(int u)
{
    static int a,b,l,r;
    a=tr[u].mul,b=tr[u].add;
    l=tr[u].s[0],r=tr[u].s[1];
    tr[l].v=(tr[l].v*a+b)%mod;
    tr[l].mul=tr[l].mul*a%mod;
    tr[l].add=(tr[l].add*a+b)%mod;
    tr[l].sum=(tr[l].sum*a+b*1ll*tr[l].size)%mod;
    tr[r].v=(tr[r].v*a+b)%mod;
    tr[r].mul=tr[r].mul*a%mod;
    tr[r].add=(tr[r].add*a+b)%mod;
    tr[r].sum=(tr[r].sum*a+b*1ll*tr[r].size)%mod;
    tr[u].add=0,tr[u].mul=1;
}

int build(int p,int l,int r)
{
    if(l>r)return 0;
    int u=++idx,mid=l+r>>1;
    tr[u].v=w[mid],tr[u].p=p,tr[u].mul=1;
    tr[u].s[0]=build(u,l,mid-1);
    tr[u].s[1]=build(u,mid+1,r);
    pushup(u);
    return u;
}

void rotate(int u)
{
    int v=tr[u].p,x=tr[v].p;
    bool k=tr[v].s[1]!=u;
    tr[x].s[tr[x].s[1]==v]=u,tr[u].p=x;
    tr[v].s[!k]=tr[u].s[k],tr[tr[u].s[k]].p=v;
    tr[u].s[k]=v,tr[v].p=u;
    pushup(v),pushup(u);
}

void splay(int u,int k)
{
    while(tr[u].p!=k)
    {
        int v=tr[u].p,x=tr[v].p;
        if(x!=k)
            if((tr[v].s[1]==u)!=(tr[x].s[1]==v))rotate(u);
            else    rotate(v);
        rotate(u);
    }
    if(!k)root=u;
}

int kth(int k)
{
    int u=root;
    while(u)
    {
        pushdown(u);
        if(tr[tr[u].s[0]].size>=k)u=tr[u].s[0];
        else if(tr[tr[u].s[0]].size+1==k)return u;
        else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
    }
    return -1;
}

void output(int u)
{
    pushdown(u);
    if(tr[u].s[0])output(tr[u].s[0]);
    printf("%d ",tr[u].v);
    if(tr[u].s[1])output(tr[u].s[1]);
}

int main()
{
    scanf("%d%d",&n,&mod);
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    root=build(0,0,n+1);
    for(scanf("%d",&m);m--;)
    {
        int op,l,r,x;
        scanf("%d%d%d",&op,&l,&r);
        l=kth(l),r=kth(r+2);
        splay(l,0),splay(r,l);
        Point &u=tr[tr[r].s[0]];
        if(op==1)
        {
            scanf("%d",&x);
            u.add=u.add*x%mod;
            u.mul=u.mul*x%mod;
            u.sum=u.sum*x%mod;
            u.v=u.v*x%mod;
        }
        else if(op==2)
        {
            scanf("%d",&x);
            u.v=(u.v+x)%mod;
            u.add=(u.add+x)%mod;
            u.sum=(u.sum+x*1ll*u.size)%mod;
        }
        else printf("%lld\n",u.sum);
    }
    return 0;
}


新鲜事 原文

垫底抽风
19小时前
Splay好慢啊(相比线段树 最近尝试用Splay代替线段树,有的题不卡常根本过不去,TLE了调半天,自闭


新鲜事 原文

开学一个月了,QQ&AcWing里面这么多人问我东西是我没想到的。。 现在时间比较紧,毕竟明年就中考了,评论不能再及时回复了,但是看到的还是会回的,大佬们抱歉



y总先把这题时间限制改一下吧。。

话说为什么要把所有题的初试时间都设为 5min 啊。。



新鲜事 原文

勿忘国耻 铭记历史
图片 图片 图片 图片 图片 图片 图片 图片 图片


活动打卡代码 AcWing 2418. 光之大陆

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
const int N=205;

int n,mod;
int c[N][N];
int f[N][N],g[N];

int main()
{
    scanf("%d%d",&n,&mod);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    g[1]=1,g[3]=3;
    for(int i=4;i<=n;i++)g[i]=g[i-1]*i%mod;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=i-j+1;k++)
                f[i][j]=(f[i][j]+f[i-k][j-1]*1ll*c[i-1][k-1]%mod*g[k])%mod;
    ll res=g[n-1],p=1;
    for(int k=2;k<=n;k++)
    {
        res=(res+f[n][k]*p)%mod;
        p=p*n%mod;
    }
    printf("%lld\n",res);
    return 0;
}


活动打卡代码 AcWing 2419. prufer序列

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N=100005;

int n,type;
int f[N],p[N],d[N];

int main()
{
    scanf("%d%d",&n,&type);
    if(type==1)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",f+i);
            d[f[i]]++;
        }
        for(int i=0,j=1;i<n-2;j++)
        {
            while(d[j])j++;
            p[i++]=f[j];
            while(i<n-2&&!--d[p[i-1]]&&p[i-1]<j)p[i++]=f[p[i-1]];
        }
        for(int i=0;i<n-2;i++)printf("%d ",p[i]);
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",p+i);
            d[p[i]]++;
        }
        p[n-1]=n;
        for(int i=1,j=1;i<n;i++,j++)
        {
            while(d[j])j++;
            f[j]=p[i];
            while(i<n-1&&!--d[p[i]]&&p[i]<j)f[p[i]]=p[i+1],i++;
        }
        for(int i=1;i<n;i++)printf("%d ",f[i]);
    }
    return 0;
}


活动打卡代码 AcWing 2417. 指挥网络

邻接矩阵版

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N=105;
const double INF=2e9;

int n,m;
int pre[N];
int x[N],y[N];
double g[N][N],ans;
int dfn[N],low[N],ts,scc_cnt;
int id[N],stk[N],tt;
bool ins[N];
struct Edge
{
    int a,b;
    double w;
}edges[10005];
int cnt;

void tarjan(int u)
{
    dfn[u]=low[u]=++ts;
    stk[++tt]=u,ins[u]=true;
    if(!dfn[pre[u]])
    {
        tarjan(pre[u]);
        low[u]=min(low[u],low[pre[u]]);
    }
    else if(ins[pre[u]])
        low[u]=min(low[u],dfn[pre[u]]);
    if(dfn[u]==low[u])
    {
        int y;
        ++scc_cnt;
        do
        {
            y=stk[tt--];
            ins[y]=false;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

bool check_con()
{
    static int q[N],hh,tt;
    static bool st[N];
    memset(st,false,sizeof st);
    *q=1,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=1;i<=n;i++)
            if(!st[i]&&g[t][i]<INF)
                st[i]=true,q[++tt]=i;
    }
    for(int i=2;i<=n;i++)if(!st[i])return false;
    return true;
}

int main()
{
    memset(g,0x42,sizeof g);
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)scanf("%d%d",x+i,y+i);
        memset(g,0x42,sizeof g);
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(b==1)continue;
            g[a][b]=min(g[a][b],hypot(x[a]-x[b],y[a]-y[b]));
        }
        if(check_con())
        {
            ans=0;
            while(true)
            {
                for(int i=1;i<=n;i++)
                {
                    pre[i]=i;
                    for(int j=1;j<=n;j++)
                        if(g[j][i]<g[pre[i]][i])
                            pre[i]=j;
                }
                memset(dfn,0,sizeof dfn),ts=scc_cnt=0;
                for(int i=1;i<=n;i++)
                    if(!dfn[i])
                        tarjan(i);
                if(scc_cnt<n)
                {
                    cnt=0;
                    for(int i=2;i<=n;i++)
                        if(id[pre[i]]==id[i])
                            ans+=g[pre[i]][i];
                    for(int i=1;i<=n;i++)
                        for(int j=1;j<=n;j++)
                            if(g[i][j]<INF&&id[i]!=id[j])
                                if(id[j]!=id[pre[j]])edges[cnt++]={id[i],id[j],g[i][j]};
                                else    edges[cnt++]={id[i],id[j],g[i][j]-g[pre[j]][j]};
                    memset(g,0x42,sizeof g);
                    for(int i=0;i<cnt;i++)
                    {
                        int a=edges[i].a,b=edges[i].b;
                        g[a][b]=min(g[a][b],edges[i].w);
                    }
                    n=scc_cnt;
                }
                else break;
            }
            for(int i=2;i<=n;i++)ans+=g[pre[i]][i];
            printf("%.2lf\n",ans);
        }
        else puts("poor snoopy");
    }
    return 0;
}

邻接表版

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=105;
const int M=10005;

int n,m;
double ans;
int x[N],y[N];
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],ts,scc_cnt;
int id[N],pre[N],stk[N],tt;
bool ins[N];
struct Edge
{
    int a,b;
    double w;
}edges[M],t[M];
int cnt;

void add(int a,int b)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++ts;
    stk[++tt]=u,ins[u]=true;
    for(int i=h[u];i;i=ne[i])
        if(!dfn[e[i]])
        {
            tarjan(e[i]);
            low[u]=min(low[u],low[e[i]]);
        }
        else if(ins[e[i]])
            low[u]=min(low[u],dfn[e[i]]);
    if(low[u]==dfn[u])
    {
        int y;
        ++scc_cnt;
        do
        {
            y=stk[tt--];
            ins[y]=false;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

bool check_con()
{
    static int q[N],hh,tt;
    static bool st[N];
    *q=1,hh=tt=0;
    memset(st,false,sizeof st);
    memset(h,0,sizeof h),idx=0;
    for(int i=0;i<m;i++)add(edges[i].a,edges[i].b);
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!st[e[i]])
                st[e[i]]=true,q[++tt]=e[i];
    }
    for(int i=2;i<=n;i++)if(!st[i])return false;
    return true;
}

int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=n;i++)scanf("%d %d",x+i,y+i);
        cnt=0;
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            if(b!=1)edges[cnt++]={a,b,hypot(x[a]-x[b],y[a]-y[b])};
        }
        m=cnt;
        if(check_con())
        {
            ans=0;
            int last=1;
            while(true)
            {
                // for(int i=0;i<m;i++)printf("%d  %d  %.5lf\n",edges[i].a,edges[i].b,edges[i].w);
                // printf("%d %.2lf\n",last,ans);
                memset(pre,-1,sizeof pre);
                for(int i=0;i<m;i++)
                    if(pre[edges[i].b]==-1||edges[pre[edges[i].b]].w>edges[i].w)
                        pre[edges[i].b]=i;
                memset(h,0,sizeof h),idx=0;
                memset(dfn,0,sizeof dfn),ts=scc_cnt=0;
                for(int i=1;i<=n;i++)
                    if(i!=last)
                        add(edges[pre[i]].a,i);
                for(int i=1;i<=n;i++)
                    if(!dfn[i])
                        tarjan(i);
                if(scc_cnt<n)
                {
                    cnt=0;
                    for(int i=0;i<m;i++)
                        if(id[edges[i].b]==id[edges[i].a])
                        {
                            if(pre[edges[i].b]==i)ans+=edges[i].w;
                        }
                        else if(id[edges[i].b]==id[edges[pre[edges[i].b]].a])
                            t[cnt++]={id[edges[i].a],id[edges[i].b],edges[i].w-edges[pre[edges[i].b]].w};
                        else    t[cnt++]={id[edges[i].a],id[edges[i].b],edges[i].w};
                    m=cnt,n=scc_cnt,last=id[last];
                    memcpy(edges,t,sizeof t);
                }
                else break;
            }
            for(int i=1;i<=n;i++)
                if(i!=last)
                    ans+=edges[pre[i]].w;
            printf("%.2lf\n",ans);
        }
        else puts("poor snoopy");
    }
    return 0;
}



$\texttt{ABC178-F}$

题目描述

给定两个升序排序的长度为 $n$ 的序列 $A, B$,问是否可以将序列 $B$ 重新排列,使得对于每个 $i$,有$A _ i \neq B _ i$

如果可以,输出重新排序后的 $B$ 序列

输入格式

输入共三行

第一行有一个正整数 $n$

第二行有 $n$ 个整数,第 $i$ 个整数表示 $A _ i$

第三行有 $n$ 个整数,第 $i$ 个整数表示 $B _ i$

输出格式

如果没有满足条件的 $B$ 的排列,输出 No

否则在第一行输出 Yes,第二行输出序列 $B$

如果有多组解,输出其中任意一组即可

输入样例 $1$

6
1 1 1 2 2 3
1 1 1 2 2 3

输出样例 $1$

Yes
2 2 3 1 1 1

输入样例 $2$

3
1 1 2
1 1 3

输出样例 $2$

No

输入样例 $3$

4
1 1 2 3
1 2 3 3

输出样例 $3$

Yes
3 3 1 2

算法

(贪心,双指针) $O(n)$

结论:将 $B$ 按降序排序后,$B$ 中最多只会有一段 $B[l \sim r]$ 与 $A[l \sim r]$ 是相同的,且 $A[l \sim r]$ 和 $B[l \sim r]$ 中所有值都等于同一个数

证明:
我们假设将 $B$ 按倒序排序后,$B$ 中与 $A$ 相同的有两段

即存在一组 $[l _ 1, r _ 1], [l _ 2, r _ 2]$,满足 $\left\{
\begin {aligned}
& l _ 2 < r _ 1 \\
& B[l _ 1, r _ 1] = A[l _ 1, r _ 1] \\
& B[l _ 2, r _ 2] = A[l _ 2, r _ 2] \\
& B[r _ 1 + 1, l _ 2 - 1] \neq A[r _ 1 + 1, l _ 2 - 1] \\
\end {aligned}
\right.
$

因为 $A$ 是按升序排序的,所以 $A[l _ 2] \geq A[r _ 1]$

因为 $A[l _ 2] = B[l _ 2], A[r _ 1] = B[r _ 1]$,所以 $B[l _ 2] \geq B[r _ 1]$

因为 $B$ 是按降序排序的,所以 $B[l _ 2] \leq B[r _ 1]$

所以 $B[l _ 2] = B[r _ 1]$,同理 $B[l _ 2] = B[r _ 1]$

又因为 $A$ 和 $B$ 都具有单调性,所以 $A[r _ 1 \sim l _ 2], B[r _ 1 \sim l _ 2]$ 都是同一个数

所以 $A[r _ 1 \sim l _ 2] = B[r _ 1 \sim l _ 2]$

不满足假设,原命题证毕

根据这个结论,我们可以先将 $B$ 翻转,然后找到 $B$ 中和 $A$ 相同的一段 $[l, r]$,然后判断是否能用 $B$ 中其它的数替换掉 $B[l \sim r]$ 这一段

如果不能,输出 No,否则替换掉并输出

时间复杂度

根据结论,我们只需要找出 $A$ 中第一个和 $B$ 相同的数,然后试图替换即可

查找是 $O(n)$ 的,替换也可以做到 $O(n)$,所以总时间复杂度是 $O(n)$ 的

C++ 代码与注释

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200005;

int n;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 0; i < n; i ++ ) cin >> b[n - i]; // 读入并将 B 翻转

    bool success = true; // 标记是否有合法的 B 的重排

    // 找第一个 a[i] == b[i] 的 i
    // 如果找到之后 success 被更新成 false 了,直接跳出
    for (int i = 1; i <= n && success; i ++ )
        if (a[i] == b[i])
        {
            // 这里要试图将 B 和 A 中相等的一段,用 B 的其它元素替换掉
            // 如果 a[i] 和 b[i] 不相等了,说明是 B 中和 A 相等的部分替换完了,直接跳出
            for (int k = 1; k <= n && a[i] == b[i]; k ++ )
            // 如果找到了 B 中的一个元素 b[k], 满足将 b[k] 与 b[i] 交换之后, a[k] != b[k] 且 a[i] != b[i],
                if (b[k] != b[i] && a[k] != b[i])
                    swap(b[i], b[k]), i ++ ; // 那么将 b[i] 与 b[k] 交换,并让 i 走到下一个要替换的位置

            // 如果试图替换后 b[i] 仍与 a[i] 相同,说明不存在一组合法答案,让 success = false
            if (a[i] == b[i]) success = false;
        }

    puts(success ? "Yes" : "No");
    if (success) for (int i = 1; i <= n; i ++ ) cout << b[i] << ' '; 

    return 0;
}

顺便说一下做这道题的历程吧

这场 $\text{ABC}$ 打到 $\text{32min}$ 就过 $\text{E}$ 题了,感觉应该能过 $\text{F}$

结果看了题之后想了半天一点思路都没有。。我低估了 $\text{F}$ 题的难度

比赛还剩 $\text{2min}$ 的时候才猜到结论,写完代码比赛已经结束 $\text{4min}$ 了。。

差亿点点就 $\text{AK}$ 了。。我枯了。。。

我一共就打过四把 $\text{ABC}$,四把都被卡在了 $\text{F}$ 题。。

结语:wtcl



活动打卡代码 AcWing 1032. 游戏

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N=100005;
const int M=200005;

int n,m,d,cnt;
char str[N],ans[N];
int bh[N],bidx;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],ts,scc_cnt;
int id[N],stk[N],tt;
bool ins[N];
struct Edge
{
    int i,j;
    char a,b;
}edges[M];
int p[N],idxx;

void add(int a,int b)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}

void addedge(int i,char a,int j,char b)
{
    if(a>str[i])a--;a-='a';
    if(str[j]==b)add(i<<1|a,i<<1|!a);
    else
    {
        if(b>str[j])b--;b-='a';
        add(i<<1|a,j<<1|b);
        add(j<<1|!b,i<<1|!a);
    }
}

void tarjan(int u)
{
    dfn[u]=low[u]=++ts;
    stk[++tt]=u,ins[u]=true;
    for(int i=h[u];i;i=ne[i])
        if(!dfn[e[i]])
        {
            tarjan(e[i]);
            low[u]=min(low[u],low[e[i]]);
        }
        else if(ins[e[i]])
            low[u]=min(low[u],dfn[e[i]]);
    if(low[u]==dfn[u])
    {
        int y;
        ++scc_cnt;
        do
        {
            y=stk[tt--];
            ins[y]=false;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

int main()
{
    scanf("%d %d\n%s\n%d",&n,&d,str+1,&m);
    for(int i=1;i<=n;i++)if(str[i]=='x')p[idxx++]=i;
    while(m--)
    {
        int i,j;
        char a,b;
        scanf("%d %c %d %c",&i,&a,&j,&b);
        a=tolower(a),b=tolower(b);
        if(str[i]=='x'||str[j]=='x')edges[cnt++]={i,j,a,b};
        else if(str[i]!=a)addedge(i,a,j,b);
    }
    int state=1;
    for(int k=d,a=3;k;k>>=1,a*=a)
        if(k&1)state*=a;
    memcpy(bh,h,sizeof h),bidx=idx;
    while(state--)
    {
        memcpy(h,bh,sizeof h),idx=bidx;
        memset(dfn,0,sizeof dfn),ts=scc_cnt=0;
        for(int i=0,r=state;i<d;i++,r/=3)
            if(r%3==0)str[p[i]]='a';
            else if(r%3==1)str[p[i]]='b';
            else    str[p[i]]='c';
        for(int i=0;i<cnt;i++)
            if(str[edges[i].i]!=edges[i].a)
                addedge(edges[i].i,edges[i].a,edges[i].j,edges[i].b);
        for(int i=2;i<n+1<<1;i++)
            if(!dfn[i])
                tarjan(i);
        bool success=true;
        for(int i=1;i<=n&&success;i++)
            if(id[i<<1]==id[i<<1|1])
                success=false;
        if(success)
        {
            for(int i=1;i<=n;i++)
                if(id[i<<1]<id[i<<1|1])putchar(str[i]=='a'?'B':'A');
                else    putchar(str[i]=='c'?'B':'C');
            return 0;
        }
    }
    puts("-1");
    return 0;
}