头像

white_bear

HUST




离线:2天前


活动打卡代码 AcWing 238. 银河英雄传说

#include<bits/stdc++.h>
using namespace std;
//统一维护当前点到根节点的距离作差就是相对距离
//d表示到根的距离
//max(0,|dx-dy|-1)//当x=y的时候就是0
//1.让排头当根节点
//2.移动的时候每个dx要加上加到的 的列的size
//d[pa]=size[pb]
//size[pb]+=size[pa]
const int N=30010;
int m;
int p[N],siz[N],d[N];
int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}
int main()
{
    cin>>m;
    for(int i=1;i<N;i++)
    {
        p[i]=i;
        siz[i]=1;
        d[i]=0;
    }
    while(m--)
    {
        char  op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')
        {
            int pa=find(a),pb=find(b);
            d[pa]+=siz[pb];
            siz[pb]+=siz[pa];
            p[pa]=pb;
        }
        else
        {
            int pa=find(a),pb=find(b);
            if(pa!=pb)puts("-1");
            else printf("%d\n",max(0,abs(d[a]-d[b])-1));
        }
    }
    return 0;
}


活动打卡代码 AcWing 239. 奇偶游戏

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

using namespace std;

const int N = 20010;

int n, m;
int p[N], d[N];
unordered_map<int, int> S;

int get(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

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

int main()
{
    cin >> n >> m;
    n = 0;

    for (int i = 0; i < N; i ++ ) p[i] = i;

    int res = m;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        string type;
        cin >> a >> b >> type;
        a = get(a - 1), b = get(b);

        int t = 0;
        if (type == "odd") t = 1;

        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            if (((d[a] + d[b]) % 2 + 2) % 2 != t)
            {
                res = i - 1;
                break;
            }
        }
        else
        {
            p[pa] = pb;
            d[pa] = (d[a] +d[b] + t)%2;
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

#include<bits/stdc++.h>
using namespace std;
//由于限制条件只有2e6,但是数据范围很大是0~1e9
//故我们把0~1e9映射到0~2e6
//先考虑相等约束,再考虑不相等约束
//xi!=xj矛盾说明xi与xj在同一个集合中
const int N=2e6+10;
int n,m;
int p[N];
unordered_map<int,int> S;
struct query{
    int x,y,e;
}query[N];
int get(int x)
{
    if(S.count(x)==0)S[x]=++n;
    return S[x];
}
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        n=0;
        S.clear();
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            int x,y,e;
            scanf("%d%d%d",&x,&y,&e);
            query[i]={get(x),get(y),e};
        }
        for(int i=1;i<=n;i++)
        p[i]=i;
        //合并相等约束条件
        for(int i=0;i<m;i++)
            if(query[i].e==1)
            {
                int pa=find(query[i].x),pb=find(query[i].y);
                p[pa]=pb;
            }
            //检查所有不等条件
        bool has_conflict=false;
        for(int i=0;i<m;i++)
            if(query[i].e==0)
            {
                int pa=find(query[i].x),pb=find(query[i].y);
                if(pa==pb){
                    has_conflict=true;
                    break;
                }
            }
            if(has_conflict)puts("NO");
            else puts("YES");
    }

    return 0;
}


活动打卡代码 AcWing 1252. 搭配购买

#include<bits/stdc++.h>
using namespace std;
//把一个连通块看成一个物品
//连通块的价值就是这里面合起来买的价值
//把钱看成容量,价值看成最大价值
int n,m,vol;
const int N=10010;
int v[N],w[N];
int p[N];
int f[N];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>m>>vol;
    for(int i=1;i<=n;i++)
    p[i]=i;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);
        if(pa!=pb)
        {   v[pb]+=v[pa];
            w[pb]+=w[pa];
            p[pa]=pb;
        }
    }
    //0-1背包问题
    for(int i=1;i<=n;i++)
        if(p[i]==i)
        {
            for(int j=vol;j>=v[i];j--)
            {
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
    cout<<f[vol]<<endl;
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

#include<bits/stdc++.h>
using namespace std;
//处理环
//当两个点属于同一个集合里,连边后就成环
//把二维坐标变成一维坐标
//(x,y)->x*n+y,前提是x,y都是从0开始的
const int N=40010;
int n,m;
int p[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int get(int x,int y)
{
    return x*n+y;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n*n;i++)//变成一维后要从0开始
    p[i]=i;
    int res=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        char d;
        cin>>x>>y>>d;
        x--,y--;
        int a=get(x,y);
        int b;
        if(d=='D')b=get(x+1,y);
        else b=get(x,y+1);
        int pa=find(a),pb=find(b);
        if(pa==pb)
        {
            res=i;
            break;
        }
        else p[pa]=p[pb];
    }
    if(!res)puts("draw");
    else cout<<res<<endl;

    return 0;
}


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

#include<bits/stdc++.h>
using namespace std;
//从剩余的数中找出第k小的数->sum(x)=k
//删除某一个数
const int N=100010;
int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))
    tr[i]+=c;
}
int sum(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))
    res+=tr[i];
    return res;
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++)
    cin>>h[i];
    for(int i=1;i<=n;i++)tr[i]=lowbit(i);
    for(int i=n;i>=1;i--)
    {
        int k=h[i]+1;//第k小
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            //找第一个=k的
            if(sum(mid)>=k)r=mid;//会把后面>=k的都剪掉,后面的=k的就用不到了
            else l=mid+1;
        }
        ans[i]=r;
        add(r,-1);
    }
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<endl;

    return 0;
}



#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int a[N];
ll tr1[N];//表示bi的前缀和,b是个差分数组
ll tr2[N];//表示bi*i的前缀和
int lowbit(int x)
{
    return x&-x;
}
void add(ll tr[],int x,ll c)
{
    for(int i=x;i<=n;i+=lowbit(i))
    tr[i]+=c;
}
ll sum(ll tr[],int x)
{
    ll res=0;
    for(int i=x;i>=1;i-=lowbit(i))
    res+=tr[i];
    return res;
}
ll prefix_sum(int x)
{
    return sum(tr1,x)*(x+1)-sum(tr2,x);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int b=a[i]-a[i-1];
        add(tr1,i,b);
        add(tr2,i,(ll)b*i);
    }
    while(m--)
    {
        char op[2];
        int l,r ,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='Q')
        {
            printf("%lld\n",prefix_sum(r)-prefix_sum(l-1));
        }
        else
        {
            scanf("%d",&d);
            add(tr1,l,d),add(tr2,l,(ll)l*d);
            add(tr1,r+1,-d),add(tr2,r+1,-(ll)(r+1)*d);
        }
    }
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

#include<bits/stdc++.h>
using namespace std;
//f(i,j)从(i,j)开始滑动的路径
//属性:Max
//一定是没有环的,因为每一次都在递减
const int N=310;
int n,m;
int h[N][N];
int f[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dp(int x,int y){
    int &v=f[x][y];
    if(v!=-1)return v;
    v=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
            v=max(v,dp(a,b)+1);
    }
    return v;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>h[i][j];

        memset(f,-1,sizeof f);
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp(i,j));
            cout<<res<<endl;

    return 0;
}



#include<bits/stdc++.h>
using namespace std;
//f(u,0)->表示的是以u为根的所有个子树中选择,并且不选u的方案
//f(u,1)->表示的是以u为根的所有子树中选,并且选择u这个点的方案
//f(u,0)=Σmax(f(s,0),f(s,1))
//f(u,1)+Σf(si,0)
//总儿子的个数等于边的个数 O(n)
const int N=6010;
int n;
int happy[N];
int h[N],ne[N],e[N],idx;
int f[N][2];
bool has_father[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
    f[u][1]=happy[u];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        has_father[a]=true;
        add(b,a);
    }
    int root=1;
    while(has_father[root])root++;
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

#include<bits/stdc++.h>
using namespace std;
//0~n-1每个都走一次
//f(i,j)表示的是从0到j,走过的所有点是i的所有路径
//i=(1110011)从右开始表示第0 1 4 5 6都走过了
//属性->数量
//状态计算:
//0->k->j
//f(i,j)=f(i-{j},k)+a(k,j)
const int N=20,M=1<<N;
int n;
int w[N][N];
int f[M][N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>w[i][j];
    //在零号点,所以第0位上是1
    memset(f,0x3f,sizeof f);
    f[1][0]=0;
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<n;j++)
            if(i>>j&1)//
                for(int k=0;k<n;k++)
                    if((i-(1<<j))>>k&1)
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}