头像

送分鱼酱


访客:399

离线:6小时前


活动打卡代码 AcWing 367. 学校网络

送分鱼酱
1个月前
#include<bits/stdc++.h>
using namespace std;
int head[20010],to[20010],nxt[20010],cnt;
void add(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
int dfn[110],low[110],idx;
bool in[110];
int stk[110],top;
int scc_cnt,sz[110],id[110];
void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    in[u]=1;
    stk[++top]=u;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])low[u]=min(low[u],dfn[v]);
    }

    if(dfn[u]==low[u])
    {
        int k;
        scc_cnt++;
        do
        {
            k=stk[top--];
            in[k]=0;
            id[k]=scc_cnt;
            sz[scc_cnt]++;
        }
        while(u!=k);
    }
}
bool s[110],e[110];
int main()
{
    int n;
    int v;
    scanf("%d",&n);
    for(int u=1;u<=n;u++)
        while(scanf("%d",&v)&&v) add(u,v);
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=nxt[j])
        {
            int a=id[i],b=id[to[j]];
            if(a!=b)s[a]=1,e[b]=1;
        }
    int scnt=0,ecnt=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!e[i])scnt++;
        if(!s[i])ecnt++;
    }
    printf("%d\n%d\n",scnt,scc_cnt==1?0:max(scnt,ecnt));
    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛

送分鱼酱
1个月前
#include<bits/stdc++.h>
using namespace std;
int head[200010],to[200010],nxt[100010],cnt;
void add(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
int dfn[10010],low[10010],idx;
int stk[10010],top;
bool in[10010];
int id[10010],sz[10010],scc;
void tarjan(int u)
{
    dfn[u]=low[u]=++idx;//打上时间戳
    stk[++top]=u;//进栈
    in[u]=1;//标记,同时存在标记的点在同一scc中
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])//如果还没被经过
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);//计算能达到的最小时间戳
        }
        else if(in[v])low[u]=min(low[u],dfn[v]);
        //如果在同一scc中,可以取min
    }


    if(dfn[u]==low[u])//u是这个scc的最高点,把这个scc缩点
    {
        scc++;
        int k;
        do
        {
            k=stk[top--];//弹出栈顶

            in[k]=0;//取消标记
            id[k]=scc;//记录这个点对应的scc编号
            sz[scc]++;//当前scc元素个数+1
        }
        while(u!=k);//直到把所有都弹出
    }


    return;
}
bool out[10010];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=nxt[j])
        {
            int u=id[i],v=id[to[j]];
            if(u!=v)out[u]=1;
        }
    int sum=0,ct=0;
    for(int i=1;i<=scc;i++)
        if(!out[i])
        {
            ct++;
            sum+=sz[i];
            if(ct>1)
            {
                sum=0;
                break;
            }
        }
    printf("%d\n",sum);
    return 0;
}


活动打卡代码 AcWing 1285. 单词

送分鱼酱
1个月前
#include<bits/stdc++.h>
using namespace std;
const int mx=1000010;
int n,c[mx][26],v[mx],idx,cnt;
int nxt[mx],vis[mx];
int head[mx],nxt2[mx],to[mx];
char tmp[mx];
void add(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt2[cnt]=head[u];
    head[u]=cnt;
}
void isrt(char str[],int id)
{
    int r=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!c[r][u])c[r][u]=++idx;
        r=c[r][u];
        vis[r]++;
    }
    v[id]=r;
}
void getnext()
{
    queue<int> q;
    for(int i=0;i<26;i++)
        if(c[0][i])q.push(c[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(c[u][i])
            {
                nxt[c[u][i]]=c[nxt[u]][i];
                q.push(c[u][i]);
            }
            else c[u][i]=c[nxt[u]][i];
    }
}
void dfs(int u)
{
    for(int i=head[u];i;i=nxt2[i])
    {
        dfs(to[i]);
        vis[u]+=vis[to[i]];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",tmp);
        isrt(tmp,i);
    }
    getnext();
    for(int i=1;i<=idx;i++)
        add(nxt[i],i);
    dfs(0);
    for(int i=1;i<=n;i++)
        printf("%d\n",vis[v[i]]);
    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

送分鱼酱
1个月前
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int c[550010][26],v[550010],idx,n;
char tmp[60],l[1000010];
void isrt(char str[])
{
    int r=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!c[r][u])c[r][u]=++idx;
        r=c[r][u];
    }
    v[r]++;
}
int nxt[550010],g[550010];
void getnext()
{
    queue<int> q;
    for(int i=0;i<26;i++)
        if(c[0][i])q.push(c[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(c[u][i])
            {
                nxt[c[u][i]]=c[nxt[u]][i];
                g[c[u][i]]=v[nxt[c[u][i]]]?nxt[c[u][i]]:g[nxt[c[u][i]]];
                q.push(c[u][i]);
            }
            else c[u][i]=c[nxt[u]][i];
    }
}
int query(char str[])
{
    int r=0,tot=0;
    for(int i=0;str[i];i++)
    {
        r=c[r][str[i]-'a'];
        for(int j=r;j;j=g[j])
            tot+=v[j],v[j]=0;
    }
    return tot;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof c);
        memset(g,0,sizeof g);
        memset(v,0,sizeof v);
        memset(nxt,0,sizeof nxt);
        idx=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",tmp);
            isrt(tmp);
        }
        getnext();
        scanf("%s",l);
        printf("%d\n",query(l));
    }
    return 0;
}


活动打卡代码 AcWing 1275. 最大数

送分鱼酱
2个月前
#include<bits/stdc++.h>
using namespace std;
const int mx=200010;
int m,p;
struct node
{
    int l,r,v;
}tr[mx*4];
void pushup(int u)
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
    tr[u]=(node){l,r,0};
    if(l==r)return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].v;
    int mid=(tr[u].l+tr[u].r)>>1;
    int tmp=0;
    if(l<=mid)tmp=query(u<<1,l,r);
    if(r>mid)tmp=max(tmp,query(u<<1|1,l,r));
    return tmp;
}
void mdi(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x)tr[u].v=v;
    else
    {
        int mid=(tr[u].l+tr[u].r)>>1;
        if(x<=mid)mdi(u<<1,x,v);
        else mdi(u<<1|1,x,v);
        pushup(u);
    }
}
int main()
{
    scanf("%d%d",&m,&p);
    int a=0,n=0;
    build(1,1,m);
    for(int i=1;i<=m;i++)
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(*op=='Q')
        {
            a=query(1,n-x+1,n);
            printf("%d\n",a);
        }
        else
        {
            mdi(1,n+1,(a+x)%p);
            n++;
        }
    }
    return 0;
}


活动打卡代码 AcWing 244. 谜一样的牛

送分鱼酱
2个月前
#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
int c[100010],a[100010];
int n;
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}
int ask(int x)
{
    int tmp=0;
    for(int i=x;i;i-=lowbit(i))
        tmp+=c[i];
    return tmp;
}
int ans[100010];
int main()
{
    cin>>n;
    c[1]=1;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a[i]);
        c[i]=lowbit(i);
    }
    for(int i=n;i>=1;i--)
    {
        int k=a[i]+1;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(ask(mid)>=k)r=mid;
            else l=mid+1;
        }
        add(r,-1);
        ans[i]=r;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}



送分鱼酱
2个月前
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
int a[100010];
ll c1[100010],c2[1000010];
int n,m;
void add(ll c[],int x,ll y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}
ll ask(ll c[],int x)
{
    ll tmp=0;
    for(int i=x;i;i-=lowbit(i))
        tmp+=c[i];
    return tmp;
}
ll sum(int x)
{
    return ask(c1,x)*(x+1)-ask(c2,x);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        int b=a[i]-a[i-1];
        add(c1,i,b);
        add(c2,i,(ll)b*i);
    }
    for(int i=1;i<=m;i++)
    {
        char op;
        cin>>op;
        if(op=='C')
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            add(c1,l,d);
            add(c2,l,d*l);
            add(c1,r+1,-d);
            add(c2,r+1,-d*(r+1));
        }
        else
        {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",sum(r)-sum(l-1));
        }
    }
    return 0;
}



送分鱼酱
2个月前
#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
int n,m;
int a[100010];
int c[100010];
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}
int ask(int x)
{
    int tmp=0;
    for(int i=x;i;i-=lowbit(i))
        tmp+=c[i];
    return tmp;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    while(m--)
    {
        char op;
        cin>>op;
        if(op=='C')
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            add(l,d);
            add(r+1,-d);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",ask(x));
        }
    }
    return 0;
}


活动打卡代码 AcWing 241. 楼兰图腾

送分鱼酱
2个月前
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
int a[200010];
int sum[2000010];
int n;
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
        sum[i]+=c;
}
ll ask(int x)
{
    ll tmp=0;
    for(int i=x;i;i-=lowbit(i))
        tmp+=sum[i];
    return tmp;
}
int main()
{
    scanf("%d",&n);
    ll a1=0,a2=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(a[i],1);
        a1+=(ask(n)-ask(a[i]))*(n-a[i]-ask(n)+ask(a[i]));
        a2+=(ask(a[i]-1)*(a[i]-1-ask(a[i]-1)));
    }
    printf("%lld %lld\n",a1,a2);
    return 0;
}


活动打卡代码 AcWing 1323. 出现

送分鱼酱
2个月前
#include<bits/stdc++.h>
using namespace std;
bool s[1010];
int n;
int main()
{
    int a;
    cin>>n;
    while(n--)
    {
        cin>>a;
        s[a]=1;
        //if(a==0)puts("jp");
    }
    for(int i=0;i<=1000;i++)
    {
        if(s[i]==0)
        {
            cout<<i;
            break;

        }
    }
}