头像

Accepting

TYUT 太原理工大学


访客:9683

离线:1小时前



Accepting
1小时前

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

直接暴力显然是最简单的方法,那让我们来分析一下时间复杂度,若每次要执行的区间都是最大的,共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!




Accepting
2小时前

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

适当标记,记录!类似桶排序的思想。

#include<iostream>

using namespace std;

const int N=10010;

int a[N];

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

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



活动打卡代码 AcWing 356. 次小生成树

Accepting
6小时前

差点当场去世~

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10,M=3e5+10,P=2e5+10,INF=0x3f3f3f3f;

typedef long long LL; 

int h[N],w[P],ne[P],e[P],idx;
int d1[N][16],d2[N][16],depth[N],fa[N][16],q[N],p[N];
struct edg
{
    int a,b,w;
    bool is_tree;
    bool operator<(const edg &t)const
    {
        return w<t.w;
    }
}eg[M];
LL res,sum;
int n,m;

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

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void RMQ()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    int tt=0,hh=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,d1[j][0]=w[i],d2[j][0]=-INF;
                for(int k=1;k<=15;k++)
                {
                    int anc=fa[j][k-1];
                    fa[j][k]=fa[anc][k-1];
                    int d[4]={d1[j][k-1],d1[anc][k-1],d2[j][k-1],d2[anc][k-1]};
                    int df=-INF,ds=-INF;
                    for(int u=0;u<4;u++)
                    {
                        if(d[u]>df) ds=df,df=d[u];
                        else if(d[u]!=df && d[u]>ds) ds=d[u]; 
                    }
                    d1[j][k]=df,d2[j][k]=ds;
                }
            }
        }
    }
}

int LCA(int a,int b,int w)
{
    static int dis[P];
    int df=-INF,ds=-INF,cnt=0;
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
        {
            dis[cnt++]=d1[a][k];
            dis[cnt++]=d2[a][k];
            a=fa[a][k];
        }
    if(a!=b)
    {
        for(int k=15;k>=0;k--)
            if(fa[a][k]!=fa[b][k])
            {
                dis[cnt++]=d1[a][k];
                dis[cnt++]=d2[a][k];
                dis[cnt++]=d1[b][k];
                dis[cnt++]=d2[b][k];
                a=fa[a][k],b=fa[b][k];
            }
        dis[cnt++]=d1[a][0];
        dis[cnt++]=d1[b][0];
    }
    for(int i=0;i<cnt;i++)
    {
        if(dis[i]>df) ds=df,df=dis[i];
        else if(dis[i]!=df && dis[i]>ds) ds=dis[i];
    }
    if(w>df) return w-df;
    if(w>ds) return w-ds;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        eg[i]={a,b,c};
    }
    sort(eg,eg+m);
    for(int i=0;i<m;i++)
    {
        int a=find(eg[i].a),b=find(eg[i].b),w=eg[i].w;
        if(a!=b)
        {
            p[a]=b;
            eg[i].is_tree=true;
            add(eg[i].a,eg[i].b,w),add(eg[i].b,eg[i].a,w);
            sum+=w;
        }
    }
    RMQ();
    res=1e18;
    for(int i=0;i<m;i++)
        if(!eg[i].is_tree)
            res=min(res,sum+LCA(eg[i].a,eg[i].b,eg[i].w));
    cout<< res <<endl;
    return 0;
}




算法1

(倍增LCA) $O((n+m)logn)$

对于每一次询问,都再去算一遍,相当于在线做法

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=10010,M=20010;

int h[N],e[M],ne[M],w[M],idx;
int depth[N],fa[N][16],q[N];
int n,m,dist[N];

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

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;//0点作用有许多,如果某个点跳出去那他的祖宗点就是0,而且
    //跳出去以后深度为0,便不会执行跳的操作,节省了很多代码!
    int tt=0,hh=0;
    q[tt++]=root;
    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<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];//跳出去也不要紧,变成0而已!
            }
        }
    }
}

int query(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);//把2个放到同一层,只对深度高的那个进行操作
    for(int k=15;k>=0;k--)//二进制拼凑实行跳
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=15;k>=0;k--)//跳到同一层后,再同时往上跳,直到祖宗节点的下一个,便于判断!
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];//最终返回a的父节点或者b的即可
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
       int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    bfs(1);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==b) printf("0\n");
        else
        {
            int p=query(a,b);
            int res=dist[a]+dist[b]-dist[p]*2;
            printf("%d\n",res);
        }
    }
    return 0;
}

算法2

(tarjan 离线LCA) $O(n+m)$

先将所有的询问都存储下来,最终在tarjan的过程中全部计算

C++ 代码

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N=10010,M=N*2;

int h[N],e[M],ne[M],w[M],idx;
int res[M],p[N],dist[N];
vector<pair<int,int>> q[N];
int n,m,st[N];

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

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(auto x : q[u])
    {
        int y=x.first,id=x.second;
        if(st[y]==2)
        {
            int at=find(y);
            res[id]=dist[y]+dist[u]-dist[at]*2;
        }
    }
    st[u]=2;
}

int main()
{
    cin>>n>>m;
    memset(h,- 1,sizeof h);
    for(int i=1;i<n;i++)
    {
       int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b)
        {
            q[a].push_back({b,i});
            q[b].push_back({a,i});
        }
    }
    tarjan(1);
    for(int i=0;i<m;i++)  printf("%d\n",res[i]);
    return 0;
}



活动打卡代码 AcWing 1171. 距离

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int N=10010,M=N*2;

int h[N],e[M],ne[M],w[M],idx;
int res[M],p[N],dist[N];
vector<pair<int,int>> q[N];
int n,m,st[N];

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

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(auto x : q[u])
    {
        int y=x.first,id=x.second;
        if(st[y]==2)
        {
            int at=find(y);
            res[id]=dist[y]+dist[u]-dist[at]*2;
        }
    }
    st[u]=2;
}

int main()
{
    cin>>n>>m;
    memset(h,- 1,sizeof h);
    for(int i=1;i<n;i++)
    {
       int a,b,c;
       scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b)
        {
            q[a].push_back({b,i});
            q[b].push_back({a,i});
        }
    }
    tarjan(1);
    for(int i=0;i<m;i++)  printf("%d\n",res[i]);
    return 0;
}



活动打卡代码 AcWing 1172. 祖孙询问

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=40010,M=80010;

int h[N],e[M],ne[M],idx;
int depth[N],fa[N][16],q[N];
int n,m,root;

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

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    int tt=0,hh=0;
    q[tt++]=root;
    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<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

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

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b==-1) root=a;
        else add(a,b),add(b,a);
    }
    bfs(root);
    cin>>m;
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int p=query(a,b);
        if(p==a) puts("1");
        else if(p==b) puts("2");
        else puts("0");
    }
    return 0;
}



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

这道题目刨析之后就会发现它其实是按照对角线来输出的,在一个n*n的矩阵中,共有2*n+1条对角线,所以我们在读入的时候可以观察每个数的横纵坐标之和来判断它在哪条斜线上,研究后我们就会发现,当横纵坐标之和为偶数的对角线是要从下往上输出,反之是要从上往下输出,这样的话我们不难想到双端队列,可以将偶数的每次push_front(),反之push_back(),最终遍历双端队列去得到结果即可!(注意,其实双端队列的常数复杂度还是比较大的,因此这个方法在代码量上应该是最优的,但在运行时间上还是有点慢,当然也可以手动模拟双端队列,但是由于这道题目的数据少,我们直接利用STL自带双端队列即可)

#include<iostream>
#include<deque>

using namespace std;

const int N=1010;

deque<int> a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            if(!((i+j)&1)) a[i+j].push_front(x);
            else a[i+j].push_back(x);
        }
    for(int i=2;i<=2*n;i++)  for(auto x:a[i]) printf("%d ",x);
    return 0;
}

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




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

简单标记

#include<iostream>

using namespace std;

const int N=1010;

int a[N];

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
        printf("%d ",a[x]);
    }
    return 0;
}

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



活动打卡代码 AcWing 393. 雇佣收银员

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=30,M=100;

int h[N],ne[M],e[M],w[M],idx;
int dist[N],cnt[N],q[N];
int num[N],s[N],r[N];
bool st[N];

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

void build(int c)
{
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=24;i++)
    {
        add(i-1,i,0);
        add(i,i-1,-num[i]);
    }
    for(int i=8;i<=24;i++) add(i-8,i,r[i]);
    for(int i=1;i<=7;i++)  add(16+i,i,r[i]-c);
    add(0,24,c),add(24,0,-c);
}

bool spfa(int c)
{
    build(c);
    memset(dist,0xcf,sizeof dist);
    memset(cnt,0,sizeof cnt);
    memset(st,0 ,sizeof st);
    int tt=0,hh=0;
    st[0]=true;
    q[tt++]=0;
    dist[0]=0;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        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]>24) return true;
                if(!st[j])
                {
                    q[tt++]=j;
                    st[j]=true;
                    if(tt==N) tt=0;
                }
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=1;i<=24;i++) scanf("%d",&r[i]);
        memset(num,0,sizeof num);
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int t;
            scanf("%d",&t);
            num[t+1]++;
        }
        bool sus=false;
        for(int i=0;i<=n;i++)
        {
            if(!spfa(i))
            {
                sus=true;
                cout<< i <<endl;
                break;
            }
        }
        if(!sus) puts("No Solution");
    }
    return 0;
}


活动打卡代码 AcWing 1170. 排队布局

#include<iostream>
#include<cstring>

using namespace std;

const int N=1010,M=21010;

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

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,0x3f,sizeof dist);
    int tt=0,hh=0;
    for(int i=1;i<=n;i++)
    {
        q[tt++]=i;
        st[i]=true;
    }
    dist[1]=0;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        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>>k;
    memset(h,-1,sizeof h);
    for(int i=2;i<=n;i++)   add(i,i-1,0);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(b>a) add(a,b,c);
        else add(b,a,c);
    }
    while(k--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(b>a) add(b,a,-c);
        else add(a,b,-c);
    }
    if(spfa()) puts("-1");
    else
    {
        if(dist[n]==0x3f3f3f3f) puts("-2");
        else cout<< dist[n] <<endl;
    }
    return 0;
}