头像

Accepting

TYUT 太原理工大学


访客:9979

在线 


活动打卡代码 AcWing 368. 银河

Accepting
2小时前

算法1 刨析不等关系 + 缩点 + 拓扑图递推最长路

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e5+10,M=6e5+10;

int h[N],hs[N],e[M],ne[M],w[M],idx;
int scc_size[N],dist[N],dfn[N],low[N],stk[N],id[N];
bool in_stk[N];
int scc_cnt,timestamp,top;
int n,m;

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

void tarjan(int u)
{
    low[u]=dfn[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            scc_size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    for(int i=1;i<=n;i++) add(h,0,i,1);
    while(m--)
    {
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t==1) add(h,a,b,0),add(h,b,a,0);
        else if(t==2) add(h,a,b,1);
        else if(t==3) add(h,b,a,0);
        else if(t==4) add(h,b,a,1);
        else add(h,a,b,0);
    }
    tarjan(0); 
    for(int i=0;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a==b)
            {
                if(w[j]>0)
                {
                    puts("-1");
                    return 0;
                }
            }
            else add(hs,a,b,w[j]);
        }
    for(int i=scc_cnt;i;i--)
    {
        for(int j=hs[i];~j;j=ne[j])
        {
            int k=e[j];
            if(dist[k]<dist[i]+w[j]) dist[k]=dist[i]+w[j];
        }
    }
    long long res=0;
    for(int i=1;i<=scc_cnt;i++) res+=dist[i]*scc_size[i];
    cout<< res <<endl;
    return 0;
}

算法2 差分约束

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e5+10,M=3e5+10;

int h[N],e[M],ne[M],w[M],idx;
int cnt[N],dist[N],q[N];
bool st[N];
int n,m;

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

bool spfa()
{
    memset(dist,0xcf,sizeof dist);
    dist[0]=0;
    int tt=0;
    q[++tt]=0,st[0]=true;
    while(tt)
    {
        int t=q[tt--];
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>n) return true;
                if(!st[j])
                {
                    q[++tt]=j;
                    //if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) add(0,i,1);
    while(m--)
    {
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t==1) add(a,b,0),add(b,a,0);
        else if(t==2) add(a,b,1);
        else if(t==3) add(b,a,0);
        else if(t==4) add(b,a,1);
        else add(a,b,0);
    }
    if(spfa()) puts("-1");
    else
    {
        long long res=0;
        for(int i=1;i<=n;i++) res+=dist[i];
        cout<< res <<endl;
    }
    return 0;
}



Accepting
22小时前

鄙人不才,此中鄙陋甚多,望海涵!!!

多注意一下关于X的处理!!!

#include<iostream>

using namespace std;

const int N=15,mod=11;

int a[15],cnt;

int main()
{
    char x;
    string s;
    while(cin>>x)
    {
        if(x>='0' && x<='9') a[cnt++]=x-'0';
        s+=x;
    }
    int res=0;
    for(int i=0;i<9;i++)  res+=a[i]*(i+1);
    res%=mod;
    if((res!=10 && res==a[cnt-1]) || (res==10 && s[12]=='X')) puts("Right");
    else
    {
        if(res!=10)  s[12]=res+'0';
        else s[12]='X';
        cout<< s <<endl;
    }
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!




Accepting
22小时前

鄙人不才,此中鄙陋甚多,望海涵!!!

简单标记一下,注意数的范围是10000,有1000个数!

#include<iostream>
#include<cmath>

using namespace std;

const int N=10010;

int a[N],maxv;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
        maxv=max(maxv,a[x]);
    }
    for(int i=1;i<=10000;i++)
        if(a[i]==maxv)
        {
            printf("%d\n",i);
            break;
        }
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!




Accepting
23小时前
#include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

typedef long long LL;

const int N=1e5+10,M=2e6+10;

int h[N],hs[N],e[M],ne[M],idx;
int scc_cnt,top,timestamp;
int scc_size[N],id[N],dfn[N],low[N],stk[N];
int f[N],g[N];
bool in_stk[N];
int n,m,mod;

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

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            scc_size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m>>mod;
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    unordered_set<LL> scc_set;
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            LL s=a*100000ll+b;
            if(a!=b && !scc_set.count(s))
            {
                add(hs,a,b);
                scc_set.insert(s);
            }
        }
    for(int i=scc_cnt;i;i--)
    {
        if(!f[i])
        {
            f[i]=scc_size[i];
            g[i]=1;
        }
        for(int j=hs[i];~j;j=ne[j])
        {
            int k=e[j];
            if(f[k]<f[i]+scc_size[k])
            {
                f[k]=f[i]+scc_size[k];
                g[k]=g[i];
            }
            else if(f[k]==f[i]+scc_size[k]) g[k]=(g[k]+g[i])%mod;
        }
    }
    int maxv=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(f[i]>maxv)
        {
            maxv=f[i];
            sum=g[i];
        }
        else if(f[i]==maxv) sum=(sum+g[i])%mod;
    }
    cout<< maxv << endl << sum <<endl;
    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

const int N=110,M=10010;

int h[N],e[M],ne[M],idx;
int timestamp,scc_cnt,top;
int stk[N],dfn[N],low[N],din[N],dout[N],id[N];
bool in_stk[N];
int n;

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

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

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int t;
        while(~scanf("%d",&t) && t) add(i,t);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b)  dout[a]++,din[b]++;
        }
    int in=0,out=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!din[i]) in++; 
        if(!dout[i]) out++;
    }
    printf("%d\n",in);
    if(scc_cnt==1) puts("0");
    else printf("%d\n",max(in,out));
    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

const int N=10010,M=50010;

int h[N],e[M],ne[M],idx;
int scc_cnt,top,timestamp;
int dfn[N],low[N],id[N],dout[N],se[N],stk[N];
bool in_stk[N];
int n,m;

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

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    in_stk[u]=true,stk[++top]=u;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            se[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;
        }
    int zer=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!dout[i])
        {
            zer++;
            sum+=se[i];
            if(zer>1)
            {
                sum=0;
                break;
            }
        }
    }
    cout<< sum <<endl;
    return 0;
}



鄙人不才,此中鄙陋甚多,望海涵!!!

这道题目还是比较贴近现实的,也比较有意思,直接用结构体存储每个窗口的信息,并从高往低遍历,每次点击之后就把当前点击到的窗口顶置,因此结构体开得大一些!

#include<iostream>
#include<cmath>

using namespace std;

const int N=30;

struct mp
{
    int x1,y1,x2,y2,id;
}mps[N];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        mps[i]={x1,y1,x2,y2,i};
    }
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        for(int i=n;i>=1;i--)
        {
            int x1=mps[i].x1,y1=mps[i].y1,x2=mps[i].x2,y2=mps[i].y2,id=mps[i].id;
            if(x>=x1 && y>=y1 && x<=x2 && y<=y2)
            {
                cout<< id <<endl;
                mps[++n]={x1,y1,x2,y2,id};
                break;
            }
            if(i==1)
            {
                puts("IGNORED");
                break;
            }
        }
    }
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!




鄙人不才,此中鄙陋甚多,望海涵!!!

简单标记一下,注意数据范围!

#include<iostream>
#include<cmath>

using namespace std;

const int N=1010;

int a[N];

int main()
{
    int n,res=0;
    cin>>n;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        a[abs(x)]++;
    }
    for(int i=1;i<=1000;i++) if(a[i]==2) res++;
    cout<< res <<endl;
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!



活动打卡代码 AcWing 352. 闇の連鎖

#include<iostream>
#include<cstring>

using namespace std;

const int N=1e5+10,M=2e5+10;

int h[N],e[M],ne[M],idx;
int d[N],depth[N],fa[N][17],q[N];
int n,m,ans;

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

void RMQ()
{
    memset(depth,0x3f,sizeof depth);
    depth[1]=1,depth[0]=0;
    int hh=0,tt=0;
    q[tt++]=1;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[tt++]=j;
                if(tt==N) tt=0;
                fa[j][0]=t;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int LCA(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return b;
    for(int k=16;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
            a=fa[a][k],b=fa[b][k];
    return fa[a][0];
}

int dfs(int u,int f)
{
    int res=d[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=f)
        {
            int s=dfs(j,u);
            if(s==0) ans+=m;
            else if(s==1) ans++;
            res+=s;
        }
    }
    return res;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    RMQ();
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int p=LCA(a,b);
        d[a]++,d[b]++,d[p]-=2;
    }
    dfs(1,-1);
    cout<< ans <<endl;
    return 0;
}



鄙人不才,此中鄙陋甚多,望海涵!!!

直接暴力显然是最简单的方法,那让我们来分析一下时间复杂度,若每次要执行的区间都是最大的,共10000个数,最多执行100万次,100万,统计的复杂度也是1万,也就是100万的复杂度,不会超时,但这显然是一个二位前缀和的题目,这里我们用二维前缀和来写一下就好,注意,既然用到了前缀和,那我们不妨将每个点往后推一个,下标从1开始!

#include<iostream>

using namespace std;

const int N=110;

int s[N][N];

void insert(int x1,int y1,int x2,int y2)
{
    s[x1][y1]++;
    s[x1][y2]--;
    s[x2][y1]--;
    s[x2][y2]++;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        insert(x1+1,y1+1,x2+1,y2+1);
    }
    int sum=0;
    for(int i=1;i<=101;i++)
        for(int j=1;j<=101;j++)
        {
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            if(s[i][j]) sum++;
        }
    cout<< sum <<endl;
    return 0;
} 

持续更新中,更新完历年1,2就会更新4,5!