camp训练day1

https://vjudge.net/contest/312902?tdsourcetag=s_pctim_aiomsg#overview

还没补完题我好菜

A

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
const int maxm=8e5+10;
int head[maxn],ver[maxm],edge[maxm],nxt[maxm];
ll d[maxn];
int tot;
int v[maxn];
int n,m;
priority_queue<pair<ll,int> > q;
int book[maxm];
int vis[maxn];
void add(ll x,ll y,ll z)
{
    ver[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dij()
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x]; i; i=nxt[i])
        {
            int y=ver[i];
            int z=edge[i];
            if(d[y]>d[x]+z)
            {
                if(book[i])
                    vis[y]=1;
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
            if(d[y]==d[x]+z)
            {
                if(book[i]==0&&vis[y])
                    vis[y]=0;
            }
        }
    }
}

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    tot=1;
    for(int i=1; i<=m; i++)
    {
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1; i<=k; i++)
    {
        ll s,y;
        scanf("%lld%lld",&s,&y);
        add(1,s,y);
        book[tot]=1;
        add(s,1,y);
        book[tot]=1;
    }
    dij();
    int ans=0;
    for(int i=1; i<=n; i++)
        if(vis[i])
            ans++;
    printf("%d",k-ans);
}
View Code

B

#include<bits/stdc++.h>
using namespace std;
//int dir[3][2]= {-1,3,0,3,1,3};
char mp[4][110];
int dir[3][2]= {-1,0,0,0,1,0};
int vis[4][110];
struct note
{
    int x,y;
};
queue<note> q;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m,k;
        scanf("%d%d",&m,&k);
        for(int i=1; i<=3; i++)
            scanf("%s",mp[i]+1);
        memset(vis,0,sizeof(vis));
        int pos;
        for(int i=1; i<=3; i++)
            if(mp[i][1]=='s')
                pos=i;
        while(q.size())
            q.pop();
        note t;
        t.x=pos;
        t.y=1;
        q.push(t);
        int flag=0;
        while(!q.empty())
        {
            note t=q.front();
            q.pop();
            if(t.y>=m)
            {
                flag=1;
                break;
            }
            if(mp[t.x][t.y+1]=='.'||mp[t.x][t.y+1]==0)
            {
                int nx=t.x;
                int ny=t.y+1;
                for(int i=0; i<3; i++)
                {
                    int nxx=nx+dir[i][0];
                    int nyy=ny+dir[i][1];
                    if(nxx<1||nxx>3||mp[nxx][nyy]<='Z'&&mp[nxx][nyy]>='A') continue;
                    if(mp[nxx][nyy+1]<='Z'&&mp[nxx][nyy+1]>='A') continue;
                    if(mp[nxx][nyy+2]<='Z'&&mp[nxx][nyy+2]>='A') continue;
                    note tt;
                    tt.x=nxx;
                    tt.y=nyy+2;
                    if(vis[tt.x][tt.y]) continue;
                    vis[tt.x][tt.y]=1;
                    q.push(tt);
                }
            }
        }
        if(flag)
            printf("YES
");
        else
            printf("NO
");
    }
}
View Code

C 这个构造有点意思，给a,b,c,d四个数，让构造一个50*50以内由A,B,C,D四个字母构成的图，且它们四个字母的联通块个数为a,b,c,d

我的方法：emm，先造了A,B,C,D各十行50列成为四个大联通快，然后我在A,B,C,D中插D,C,B,A,往里插不同字母增加联通快，为了避免联通块断开，我在每个字母的第二行开始插，每列隔一个插，同时插完每行在隔一行，避免产生多余联通分量。叉会腰，可把我牛逼坏了。

#include<bits/stdc++.h>
using namespace std;
char mp[55][55];
int a[50];
int main()
{
    scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]);
    a[1]--;a[2]--;a[3]--;a[4]--;
    for(int i=0; i<4; i++)
    {
        int j=1+10*i;
        for(; j<=(i+1)*10; j++)
            for(int k=1; k<=50; k++)
                mp[j][k]='A'+i;
    }
    for(int i=0; i<4; i++)
    {
        int j=2+10*i;
        int flag=0;
        for(; j<=(i+1)*10; j+=2)
        {
            if(j%2)
            {
                for(int k=1; k<=50; k+=2)
                {
                    if(a[4-i])
                    {
                        a[4-i]--;
                        mp[j][k]='D'-i;
                    }
                    else
                    {
                        flag=1;
                        break;
                    }
                }
            }
            else
            {
                for(int k=2; k<=50; k+=2)
                {
                    if(a[4-i])
                    {
                        a[4-i]--;
                        mp[j][k]='D'-i;
                    }
                    else
                    {
                        flag=1;
                        break;
                    }
                }
            }
            if(flag)
                break;
        }
    }
    printf("%d %d
",40,50);
    for(int i=1; i<=40; i++)
    {
        for(int j=1; j<=50; j++)
            printf("%c",mp[i][j]);
        printf("
");
    }
}
View Code

D 优美的暴力

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=3e3+10,maxm=3e4+10;
int head[maxn],ver[maxm],nxt[maxm];
int tot=0;
int a[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x,int step,int fa)
{
    if(step==2)
    {
        a[x]++;
        return;
    }
    for(int i=head[x]; i; i=nxt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,step+1,x);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        dfs(i,0,0);
        for(int j=1; j<=n; j++)
        {
            if(a[j]>1)
                ans=ans+a[j]*(a[j]-1)/2;
            a[j]=0;
        }
    }
    printf("%lld",ans);
}
View Code

E

#include<bits/stdc++.h>
using namespace std;

char mp[1005][1005];
int mpf[1005][1005];
int dir[4][2]= {-1,0,1,0,0,-1,0,1};
int flagw[10000005];

struct note
{
    int x,y;
};
queue<note> que;
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1; i<=n; i++)
        scanf("%s",mp[i]+1);
    int flag=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j]=='.')
            {
                flag++;
                note t;
                t.x=i;
                t.y=j;
                que.push(t);
                int w=0;
                while(!que.empty())
                {

                    note t=que.front();
                    que.pop();
                    if(mp[t.x][t.y]!='.') continue;
                    mpf[t.x][t.y]=flag;
                    mp[t.x][t.y]='#';
                    for(int k=0; k<4; k++)
                    {
                        int nx,ny;
                        nx=t.x+dir[k][0];
                        ny=t.y+dir[k][1];
                        if(nx>n||nx<1||ny>m||ny<1) continue;
                        if(mp[nx][ny]=='*')
                            w++;
                        else if(mp[nx][ny]=='.')
                        {
                            note tt;
                            tt.x=nx;
                            tt.y=ny;
                            que.push(tt);
                        }
                    }
                }
                flagw[flag]=w;
            }
        }
    for(int i=1; i<=q; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d
",flagw[mpf[a][b]]);
    }
}
View Code

F

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e3+10;
int val[maxn];
int minn[2005];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        minn[i]=min(val[a],val[b]);
        ans+=minn[i];
    }
    printf("%d",ans);
}
View Code

G 给n个数字，然后给个n*n的01矩阵，为a[i][j]表示i可以和j数字交换位置，求字典序的最小顺序。

floyd传递闭包求每个数字直接或间接可以与哪些数字交换，从前往后贪心最小数字即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e2+10;
int val[maxn];
int e[maxn][maxn];
char s[maxn][maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&val[i]);
    for(int i=1; i<=n; i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(s[i][j]=='1')
                e[i][j]=1;
        }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                e[i][j]|=e[i][k]&e[k][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(val[i]>val[j]&&e[i][j])
                swap(val[i],val[j]);
        }
        printf("%d ",val[i]);
    }
}
View Code

H

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
ll sum[maxn];
ll val[maxn];
int head[2*maxn],ver[2*maxn],nxt[2*maxn];
ll edge[2*maxn];
int tot;
int ans=0;
void add(int u,int v,ll w)
{
    ver[++tot]=v;
    edge[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
void dfs(int u,int fa)
{
    if(sum[u]<=val[u])
        ans++;
    else
        return;
    for(int i=head[u]; i; i=nxt[i])
    {
        int v=ver[i];
        if(v==fa) continue;
        ll w=edge[i];
        if(sum[u]+w>0)
            sum[v]=sum[u]+w;
        else
            sum[v]=0;
        dfs(v,u);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&val[i]);
    for(int i=2; i<=n; i++)
    {
        int v;
        ll w;
        scanf("%d%lld",&v,&w);
        add(i,v,w);
        add(v,i,w);
    }
    dfs(1,0);
    printf("%d",n-ans);
}
View Code

I

这个真是一个牛逼题。

题意：给n,m,k表示有n个数字，m对边，已知任意一条边两点的值不同，现在告诉你x属于[0,2k-1],让你求满足pair<S,x>的数量%1e9+7,S为n个数字的任意集合,满足条件是S里的所有数字^X之后，

m条边还满足任意一条边两点的值都不同。

思路：首先如果没有限制条件，一共有2k*2n个方案，如果加了异或后，任意边两点都不同的条件，可以想到对于一条边上两个点a,b，如果a^b=x，那么对于这个x来说，a,b为捆绑关系，即S中要么都有a,b要么都没有a,b。把每个边的权值看为两点的异或和，然后可以想到x在[0,2k-1]中有一些点是特殊点，这些x对要求某些点为捆绑关系即必须属于一个联通块，其他的x对点没有影响。

然后答案就是将每个边按权值排序，对于每个权值来说，计算联通块的个数size，每个特殊点贡献就是2size,设边权一共有tot种，然后其余的x的贡献就是2k*2(n-tot)。

计算联通块用并查集来做，fa重置时不能全部来否则会超时，只需将上次变过的还原即可，用set记录变过的数字。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e5+10;
const ll mod=1e9+7;
set<int> s;
ll val[maxn];
int fa[maxn];
struct note
{
    ll x,y,w;
} e[maxn];
int cmp(note a,note b)
{
    return a.w<b.w;
}
int getf(int x)
{
    return fa[x]=fa[x]==x?x:getf(fa[x]);
}
ll power(ll a, ll b, ll p)
{
    ll ans=1%p;
    for(; b; b>>=1)
    {
        if(b&1) ans=(long long)ans*a%p;
        a=(long long)a*a%p;
    }
    return ans;
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=n; i++)
        scanf("%lld",&val[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld%lld",&e[i].x,&e[i].y);
        e[i].w=val[e[i].x]^val[e[i].y];
    }
    sort(e+1,e+1+m,cmp);
    ll ans=0;
    int tot=0;
    int temp=e[1].w;
    int kuai=n;
    for(int i=1; i<=n; i++)
        fa[i]=i;
    for(int i=1; i<=m;)
    {
        int j=i;
        kuai=n;
        for(auto t:s) fa[t]=t;
        s.clear();
        while(j<=m&&e[j].w==e[i].w)
        {
            int t1,t2;
            t1=getf(e[j].x);t2=getf(e[j].y);
            if(t1!=t2)
            {
                fa[t2]=t1;
                kuai--;
            }
            s.insert(t1);s.insert(t2);
            j++;
        }
        i=j;tot++;
        ans=(ans+power(2,kuai,mod))%mod;
    }
    ans=(ans+power(2,n,mod)*(power(2,k,mod)+mod-tot)%mod)%mod;
    printf("%lld",ans);
}
View Code

J 求一个bfs最长的路径可以用vector存过程路径，遇到更长的直接将vector 赋给另一个 vector ans存储答案.

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int head[maxn],ver[maxn],nxt[maxn];
int tot;

vector<int> ans;
vector<int> path;
int cdegree[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    int maxx=-999;
    for(int i=1; i<=n; i++)
    {
        int t;
        scanf("%d",&t);
        if(t)
        {
            add(i,t);
            cdegree[t]++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i])
        {
            path.clear();
            queue<int> q;
            q.push(i);
            while(q.size())
            {
                int t=q.front();
                q.pop();
                path.push_back(t);
                if(path.size()>ans.size())
                {
                    maxx=path.size();
                    ans=path;
                }
                for(int j=head[t]; j; j=nxt[j])
                {
                    int y=ver[j];
                    if(cdegree[y]==1&&a[y]==0)
                        q.push(y);
                }
            }
        }
    }
    printf("%d
",maxx);
    for(int i=ans.size()-1;i>=0;i--)
        printf("%d ",ans[i]);
}
View Code

K 是个牛逼题，题意：给n个王子，m个公主，每个公主只能和一个王子在一起，每个公主会从两个王子里选一个嫁，每个公主有一个价值，求配对的公主价值最大是多少？

思路：可以对公主所选的王子的两个点建一条边，这样的话，a指向b就表示公主选了b王子，且每个点的入度只能是1表示一个王子只能娶一个公主，这样的话就是构造基环树问题了，就是通过并查集构造树，这个并查集中每个集合最多只能有一个环，边的方向不用管，只要保证最多只有一个环，就保证了每个点只有一个入度了。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
struct note
{
    int x,y,z;
} e[2*maxn];
int fa[maxn];
int huan[maxn];
#define ll long long
int cmp(note a,note b)
{
    return a.z>b.z;
}
int getf(int x)
{
    return fa[x]=fa[x]==x?x:getf(fa[x]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i=1; i<=m; i++)
    {
        int a,b,z;
        scanf("%d%d%d",&a,&b,&z);
        note t;
        t.x=a;
        t.y=b;
        t.z=z;
        e[++cnt]=t;
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    sort(e+1,e+1+cnt,cmp);
    ll ans=0;
    for(int i=1;i<=cnt;i++)
    {
        int x,y,z;
        x=e[i].x;
        y=e[i].y;
        z=e[i].z;
        int t1,t2;
        t1=getf(x);
        t2=getf(y);
        if(t1!=t2&&(huan[t1]==0||huan[t2]==0))
        {
            fa[t2]=t1;
            huan[t1]|=huan[t2];
            ans+=z;
        }
        if(t1==t2&&huan[t1]==0)
        {
            ans+=z;            
            huan[t1]=1;
        }
    }
    printf("%lld",ans);
}
View Code

L

#include<bits/stdc++.h>
using namespace std;
//int e[5005][5005];
vector<int> e[5005];
int check(int x)
{
    int y=e[x][0];
    int z=e[y][0];
    if(e[z][0]==x)
        return 1;
    else
        return 0;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int a;
        scanf("%d",&a);
        e[i].push_back(a);
    }
    int flag=0;
    for(int i=1; i<=n; i++)
    {
        if(check(i))
        {
            flag=1;
            break;
        }
    }
    if(flag)
        printf("YES");
    else
        printf("NO");
}
View Code

M

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int f[maxn];
int head[2*maxn],ver[2*maxn],edge[2*maxn],nxt[2*maxn];
int tot;

int getf(int x)
{
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}
void add(int u,int v,int w)
{
    ver[++tot]=v;
    edge[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}

int kd[maxn];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1; i<=k; i++)
    {
        int t;
        scanf("%d",&t);
        kd[t]=1;
    }
    int minn=INF;
    for(int i=1; i<=n; i++)
    {
        if(kd[i]==1)
        {
            for(int j=head[i]; j; j=nxt[j])
            {
                int v=ver[j];
                int w=edge[j];
                if(kd[v]==0)
                    minn=min(minn,w);
            }
        }
    }
    if(minn!=INF)
        printf("%d",minn);
    else
        printf("-1"); 
}
View Code

N

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+10;
int f[maxn];
int size[maxn];

int getf(int x)
{
    if(f[x]==x)
        return x;
    else
        return f[x]=getf(f[x]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
        size[i]=1;
    }
    while(m--)
    {
        int t;
        scanf("%d",&t);
        int a,b;
        if(t>0)
        {
            scanf("%d",&a);
            t--;
        }
        else
            continue;
        int    t1=getf(a);
        for(int i=1; i<=t; i++)
        {
            scanf("%d",&b);
            int t2;
            t2=getf(b);
            if(t1==t2) continue;
            f[t2]=t1;
            size[t1]+=size[t2];
        }
    }
    for(int i=1; i<=n; i++)
    {
        int t=getf(f[i]);
        printf("%d ",size[t]);
//        printf("%d %d
",getf(f[i]),size[i]);
    }
}
View Code

O

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int> v[maxn];
int book[maxn];
vector<int> v1,v2;
int flag=1;
void dfs(int x,int fa)
{
    for(int i=0; i<v[x].size(); i++)
    {
        int y=v[x][i];
        if(y==fa) continue;
        if(book[x]==1)
        {
            if(book[y]==1)
            {
                flag=0;
                return;
            }
            if(book[y]==0)
            {
                book[y]=2;
                dfs(y,x);
            }

        }
        if(book[x]==2)
        {
            if(book[y]==2)
            {
                flag=0;
                return;
            }
            if(book[y]==0)
            {
                book[y]=1;
                dfs(y,x);
            }
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=1; i<=n; i++)
    {
        if(book[i]==0&&v[i].size())
        {
            book[i]=1;
            dfs(i,0);
        }
    }
    if(flag)
    {
        for(int i=1; i<=n; i++)
        {
            if(book[i]==1)
                v1.push_back(i);
            if(book[i]==2)
                v2.push_back(i);
        }
        printf("%d
",v1.size());
        for(auto i:v1)
            printf("%d ",i);
        printf("
");
        printf("%d
",v2.size());
        for(auto i:v2)
            printf("%d ",i);
    }
    else
        printf("-1");
}
View Code

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/dongdong25800/p/11224286.html