ccpc网络邀请赛部分

A - ^&^

给出 a，b 求

最小

结果即为 a&b

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e2+50;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        ll a,b,c=0;
        scanf("%lld %lld",&a,&b);
        for(int bt=0;bt<=32;bt++){
            if(( ( (a>>bt)&1 )==1ll) && ( ( (b>>bt)&1 )==1ll))c+=(1ll<<bt);
        }
        if(c==0ll)puts("1");
        else printf("%lld
",c);

    }


    // system("pause");
    return 0;
}

View Code

D - path

HDU - 6705

一张有向图，求 m次路径第k小的路径长

解法：考虑如何得到有向图的所有路径，先把所有边放进小顶堆里，不断合并边得到新的路径，这时按优先队列出队顺序得到第k小，

但这样扩展所有边会MLE，考虑不需要扩充所有边，队列里只需要维持Max条路径即可，复杂度O（ K*mlog（k））

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+600;
typedef long long ll;
#define mp make_pair
vector<pair<int,int> >G[N];
int n,m;
int b[N];
ll book[N];
void init(){
    for(int i=1;i<=n;i++)G[i].clear();
}
struct node{
    int u,v;ll w;
    friend bool operator<(node a,node b){
        return a.w>b.w;
    }
};
int main(){ 
        int t;scanf("%d",&t);
    while(t--){
        int q;scanf("%d %d %d",&n,&m,&q);
        init();
        priority_queue<node>Q;           
        priority_queue< ll,vector<ll>,less<ll> >q1;
        
        for(int i=1;i<=m;i++){
            int u,v,w;scanf("%d %d %d",&u,&v,&w);
            G[u].push_back(mp(w,v));
            Q.push(node{u,v,w});
            q1.push(w);
        }
        for(int i=1;i<=n;i++)if(G[i].size())sort(G[i].begin(),G[i].end());
        int Max=-1;
        for(int i=1;i<=q;i++)scanf("%d",&b[i]),Max=max(Max,b[i]);
        
        int cnt=0;
        
        while(cnt<=Max&&!Q.empty()){
            int u=Q.top().u,v=Q.top().v;ll w=Q.top().w;
            book[++cnt]=w;Q.pop();
            for(int i=0;i<G[v].size();i++){
                int tv=G[v][i].second;
                ll tw=w+G[v][i].first;
                if(q1.size()==Max){
                    if(tw>q1.top())break;
                    else {q1.pop();q1.push(tw);Q.push(node{u,tv,tw});}
                }
                else q1.push(tw),Q.push(node{u,tv,tw});
// 
            }
        }

        for(int i=1;i<=q;i++)printf("%d
",book[ b[i] ]);

    }
        // system("pause");
    return 0;
}

View Code

F - Shuffle Card

HDU - 6707

模拟洗牌过程，倒序输出即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+600;
int b[N],vis[N];
int main(){
        int n,m,x;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&x);
            for(int i=1;i<=m;i++)scanf("%d",&b[i]);
            memset(vis,0,sizeof vis);
        for(int i=m;i>=1;i--){
            if(!vis[ b[i] ]){
                printf("%d ",b[i]);
            }
            vis[b[i]]=1;
        }
        for(int i=1;i<=n;i++){
            if(!vis[i])printf("%d ",i);
        }
        
        // system("pause");
    return 0;

}

View Code

G - Windows Of CCPC

HDU - 6708

置换规则为：将c变成ccpc，将p变成ppcp，

不难发现左下角与k-1阶相反，其他均为k-1阶，递归处理即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e3+50;
int A[N][N];
void copy(int s,int t,int len){
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            A[s+i][t+j]=A[i][j];
        }
    }
}
void make(int step){
    if(step==0){A[0][0]=1;return ;}
    make(step-1);
    int len=1<<(step-1);
    copy(0,len,len);
    copy(len,len,len);
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            A[len+i][j]=A[i][j]^1;
        }
    }
}
void print(int len){
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            printf("%c",A[i][j]?'C':'P');
        }
        puts("");
    }
}

int main(){
    int t;scanf("%d",&t);
        while(t--){
            int k;scanf("%d",&k);
            make(k);
            k=(1<<k);
            print(k);
        }

    // system("pause");
    return 0;
}

View Code