2019中国大学生プログラム設計コンテスト(CCPC)-ネット選抜試合(一部題解)

1001:^ & ^
i位に対して、AとBのi位がいずれも1である場合、Cの1位は1である必要があり、そうでない場合は0をとる.Cは正数でなければならないので、Cが0を取ることができるときは、AとBの最小の1つが1つが0のビットで現れる位置lastを見て、Cを1<

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int main()
{
     
    int T;cin>>T;
    ll a,b,c;
    while(T--){
     
        scanf("%lld%lld", &a, &b);
        c = 0;
        ll k = 1;
        int last = 0;
        for(int i = 32; i >= 0; --i){
     
            ll ba = (a&(k<<i)), bb = (b&(k<<i));
            if(ba && bb){
     
                c |= (k<<i);
            }
            else if(ba^bb) last = i;
        }
        if(c == 0) c = 1<<last;
        cout<<c<<endl;
    }
}

1002: array
作り方1:[1,r]で現れなかったものを探すのは,[r+1,end]で現れたものを探して,最後の位置にn+1を加えることに相当する.議長ツリーで[r+1,end]が現れる最小のk以上の数字を探す.各操作はend位置にa[pos]を追加するものと見なすことができる.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
using namespace std;
const int maxn = 2e5 + 50;
int sz[maxn*20], lc[maxn*20], rc[maxn*20];
int T[maxn];
int a[maxn];
int n, m;
int tot;
void build(int pre, int &cur, int l, int r, int pos){
     
    cur = ++tot;
    sz[cur] = sz[pre]+1;
    lc[cur] = lc[pre]; rc[cur] = rc[pre];
    if(l == r) return;
    if(pos <= mid)
        build(lc[pre], lc[cur], l, mid, pos);
    else
        build(rc[pre], rc[cur], mid+1, r, pos);
}
int qry(int pre, int cur, int l, int r, int k)
{
     
    if(sz[cur] - sz[pre] == 0) return -1;
    if(l == r){
     
        return l;
    }
    int res = -1;
    if(k <= mid)
        res = qry(lc[pre], lc[cur], l, mid, k);
    if(res == -1)
        res = qry(rc[pre], rc[cur], mid+1, r, k);
    return res;
}
int main()
{
     
	int ca;scanf("%d", &ca);
	while(ca--){
     
        tot = 0;
        scanf("%d%d", &n, &m);
        int ans = 0;
        for(int i = 1; i <= n; ++i){
     
            scanf("%d", &a[i]);
            build(T[i-1], T[i], 1, n+1, a[i]);
        }
        int p = n+1;
        build(T[n], T[p], 1, n+1, n+1);
        while(m--){
     
            int op; scanf("%d", &op);
            if(op == 1){
     
                int pos; scanf("%d", &pos);
                pos = pos^ans;
                if(a[pos] == -1) continue;
                build(T[p], T[p+1], 1, n+1, a[pos]);
                p++;
                a[pos] = -1;
            }
            else{
     
                int r, k;
                scanf("%d%d", &r, &k);
                r ^= ans; k ^= ans;
                ans = qry(T[r], T[p], 1, n+1, k);
                printf("%d
", ans);
            }
        }
	}
}

方法2:セグメントツリーは各値に現れる下付きスケールを維持し、クエリー時に[k,n]の最初に現れる下付きスケール値がr以上の値を探すことに相当する.操作1は、対応する値の下のスケール値をinfにすることに相当する.作り方3:操作1を行っていない答えを先に処理し、操作1ごとに削除された数字をsetで維持し、クエリー時にmin(ans[r],*lower_bound(k))
1003:array
接尾辞オートマチックfailツリーにdfsシーケンスで持続可能なセグメントツリー(誰もがバカな問題を知っているそうで、書けない私は震えています
1004: path
最短の考え方のように、最初はすべてのエッジをsetに入れて、それから毎回最短のパスを弾いて更新して、もし現在のsetのsizeがmax(k)よりも大きいならば、更新のパスがsetの中で最も長いよりも長いかどうかを見て、もしそうならば、もっと新しいことを停止して、さもなくばその最も長いパスを削除して、現在の更新のパスを加えます.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define P pair
using namespace std;
const int maxn = 5e4 + 50;
vector<P> g[maxn];
vector<int> Q;
vector<ll> ans;
int n, m, t;
int mx;
struct node{
     
    ll dis;
    int v, id;
    node(ll _dis = 0, int _v = 0, int _id = 0) : dis(_dis), v(_v), id(_id){
     }
    bool operator < (const node& a)const{
     
        if(dis != a.dis) return dis < a.dis;
        else return id < a.id;
    }
};
int tot = 0;
set<node> s;
void init(){
     
    scanf("%d%d%d", &n, &m, &t);
    s.clear();
    ans.clear();
    Q.clear();
    for(int i = 1; i <= n; ++i) g[i].clear();
    mx = 0; tot = 0;

    while(m--){
     
        int u, v; ll w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u].push_back(P(w, v));
        s.insert(node(w, v, ++tot));
    }
    for(int i = 1; i <= n; ++i) sort(g[i].begin(), g[i].end());
    for(int i = 0; i < t; ++i){
     
        int k; scanf("%d", &k);
        Q.push_back(k);
        mx = max(mx, k);
    }
}
void sol()
{
     
    for(int i = 0; i < mx; ++i){
     
        node temp = *s.begin();
        s.erase(*s.begin());
        ans.push_back(temp.dis);
        if(i == mx-1) break;

        int u = temp.v;
        ll dis = temp.dis;
        for(int j = 0; j < g[u].size(); ++j){
     
            ll w = g[u][j].first;
            int v = g[u][j].second;
            if(i + s.size() > mx){
     
                set<node>::iterator it = --s.end();
                if(dis + w >= (*it).dis) break;
                s.erase(it);
                s.insert(node(dis+w, v, ++tot));
            }
            else{
     
                s.insert(node(dis+w, v, ++tot));
            }
        }
    }
    for(int i = 0; i < Q.size(); ++i){
     
        int k = Q[i];
        printf("%lld
", ans[k-1]);
    }
}
int main()
{
     
	int T;cin>>T;
	while(T--){
     
        init();sol();
	}
}

1006:Shuffle Card
逆さまに書いて、最後に現れた数字は必ず1つ目で、それから順番に置いて、もし現れたら彼を放っておきます.処理が終わったら、残りの数字の元の順番で置きます.
1007:Windows Of CCPC
題意どおりにシミュレーションする.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int a[1<<11][1<<11];
void sol(int k)
{
     
    int len = 1<<k;
    for(int i = 0; i < len; ++i){
     
        for(int j = 0; j < len; ++j){
     
            if(a[i][j] == 0) printf("C");
            else printf("P");
        }printf("
");
    }
}
int main()
{
     
    a[0][0] = a[0][1] = 0;
    a[1][0] = 1; a[1][1] = 0;
    for(int i = 2; i <= 10; ++i){
     
        int len = (1<<(i-1));
        for(int x = 0; x < len; ++x){
     
            for(int y = 0; y < len; ++y){
     
                a[x][y+len] = a[x+len][y+len] = a[x][y];
                a[x+len][y] = a[x][y]^1;
            }
        }
    }
	int T;cin>>T;
	while(T--){
     
        int k;
        cin>>k;
        sol(k);
	}
}

1008:Fishing Master
最初の魚を捕まえるのにkと煮魚の総時間は必ずかかります.それから魚を煮るときに釣りに行くことができます.それでは、釣りに行く途中で魚が煮えましたが、魚を釣ってから煮続けなければなりません.だから、魚を煮る時間内にn-1匹の魚を釣ることができれば、余分な費用がなくてもいいです.そうしないと、魚を煮る時間のkに対するモジュール数に応じて、大きいから小さいまで余分な間隔時間を選んで、余分な時間は(k-mod)、modはt対kのモジュール数です.

#include
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn = 1e5 + 50;
ll t[maxn];
ll m[maxn];
ll k;
int n;
int main()
{
     
	int T;cin>>T;
	while(T--){
     
        scanf("%d%lld", &n, &k);
        ll num = 0, ans = k;
        for(int i = 0; i < n; ++i) {
     
            scanf("%d", &t[i]);
            m[i] = t[i]%k;
            num += t[i]/k;
            ans += t[i];
        }
        if(num >= n-1){
     
            cout<<ans<<endl;
        }
        else{
     
            sort(m, m+n);
            for(int i = 0; i < n-1-num; ++i){
     
                ans += (k-m[n-1-i]);
            }
            cout<<ans<<endl;
        }
	}
}