2019中国大学生程序设计竞赛（CCPC）

HDU 6702 ^ & ^

这题
Bit operation is a common computing method in computer science ,Now we have two positive integers A and B ,Please find a positive integer C that minimize the value of the formula (A xor C) & (B xor C) .Sometimes we can find a lot of C to do this ,So you need to find the smallest C that meets the criteria .

For example ,Let’s say A is equal to 5 and B is equal to 3 ,we can choose C=1,3… ,so the answer we’re looking for C is equal to 1.

If the value of the expression is 0 when C=0, please print 1.

让 (A xor C) & (B xor C) 最小反正 xor C 只要 C和 A&B 对齐就好 C == 0 输出 1

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
#define int long long

int a, b, c;

signed main() {
    int cas;
    cin >> cas;
    while(cas --) {
        cin >> a >> b;
        if(a & b) cout <<  (a & b) << endl;
        else cout << 1 << endl;
    }
    return 0;
}

1002 array

path

无源点无汇点找第K短路
有源点A* 没有的话

我们把当前下一次 (这里存 from 而不是 v 了)起点 + 总路程和放入队列 // 出边的这个点放入队列存储
同时考虑把(from)这边的下一个次边也放入队列进行扩展

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 100;
typedef long long ll;

int n, m, cas, q, mak, tail;
int qes[maxn];
ll ans[maxn];
struct node {
    int u, pos;
    ll w;
    bool operator < (const node& a) const {
        return w > a.w;
    }
};

bool cmp(const node &a, const node &b) {
    return a.w < b.w;
}

vector<node> G[maxn];
priority_queue<node> que;
void ade(int a, int b, int c) {
    G[a].push_back(node {b, 0, c});
}

void init() {
    for(int i = 1; i <= n; i ++) G[i].clear();
    mak = 0;
    tail = 0;
    while(!que.empty()) que.pop();
}


signed main() {
    scanf("%d", &cas);
    while(cas --) {
        scanf("%d %d %d", &n, &m, &q);
        init();
        for(int i = 1, a, b, c; i <= m; i ++)
            scanf("%d %d %d", &a, &b, &c), ade(a, b, c);

        for(int i = 1; i <= q; i ++)
            scanf("%d", &qes[i]), mak = max(mak, qes[i]);

        for(int i = 1; i <= n; i ++) sort(G[i].begin(), G[i].end(), cmp);

        for(int i = 1; i <= n; i ++)
            if(!G[i].empty()) que.push(node {i, 0, G[i][0].w});

        while(!que.empty()) {
            node p = que.top(); que.pop();
            int u = p.u;
            ll w = p.w;
            if(w == 0) {
                while(1);
            }
            ans[++ tail] = w;
            if(tail == mak + 5) break;
            if(p.pos < (int)G[u].size() - 1)
                que.push(node {u, p.pos + 1, w - G[u][p.pos].w + G[u][p.pos + 1].w});
            int v = G[u][p.pos].u;
            if(!G[v].empty())
                que.push(node {v, 0, w + G[v][0].w});
        }
        for(int i = 1; i <= q; i ++)
            printf("%lld\n", ans[qes[i]]);
    }
    return 0;
}

Shuffle Card HDU

按找之后放入顺序倒序 vis标记去重

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(false); cin.tie(0);
const int maxn = 1e5 + 5;
int n, m, k, cas, sum;

int a[maxn], b[maxn];
bool vis[maxn];

signed main() {
    fastio;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++) cin >> b[i];

    bool f = 0;
    for(int i = m; i >= 1; i--) {
        if(!vis[b[i]]) {
        
            cout << b[i];
            f = 1;
            vis[b[i]] = 1;    cout << " ";
        }
    }

    for(int i = 1; i <= n; i ++) {
        if(!vis[a[i]]) {
            
            cout << a[i];
            f = 1;
            vis[a[i]] = 1;cout << " ";
        }
    }//cout << endl;

    return 0;
}

HDU 6708 Windows Of CCPC

一般分形简单题模拟

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

char ch[1500][1500];

void init() {
    for(int i = 1; i <= 9; i ++) {
        int l1 = (1 << i) + 1;
        int r1 = (1 << i) * 2;

        for(int k = 1; k < l1; k ++) {
            for(int j = l1; j <= r1; j ++) {
                ch[k][j] = ch[k][j - l1 + 1];
            }
        }

        for(int k = l1; k <= r1; k ++) {
            for(int j = l1; j <= r1; j ++) {
                ch[k][j] = ch[k - l1 + 1][j - l1 + 1];
            }
        }

        for(int k = l1; k <= r1; k ++) {
            for(int j = 1; j < l1; j ++) {
                if(ch[k - l1 + 1][j] == 'P') ch[k][j] = 'C';
                else ch[k][j] = 'P';
// ch[k][j] = ch[k - l1 + 1][j];
            }
        }
    }
}

int main() {
    ch[1][1] = 'C';
    ch[1][2] = 'C';
    ch[2][1] = 'P';
    ch[2][2] = 'C';
    int cas;
    init();
    scanf("%d", &cas);
    while(cas --) {
        int n;
        scanf("%d", &n);

        for(int i = 1; i <= (1 << n); i ++) {
            for(int j = 1; j <= (1 << n); j ++) {
                printf("%c", ch[i][j]);
            }
            puts("");
        }

    }
    return 0;
}

HDU 6709 Fishing Master

容易wa
我们肯定先爪最长时间顿的
剩下的就是靠我们贪心往里套
最后不够抓一条鱼的顿时间存下来，后面抓鱼的时候从这些时间中选出最大的剩余时间，抓鱼的时间会和顿最大相交，这样可以使时间（k-x）最小。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(false); cin.tie(0);
const int maxn = 1e5 + 5;
int n, m, k, cas, sum;

priority_queue<int> que;
int a[maxn];
signed main() {
    fastio;
    cin >> cas;
    while(cas --) {
        while(!que.empty()) que.pop();
        cin >> n >> k;
        sum = 0;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        sort(a + 1, a + 1 + n, greater<int>{});
// cout << a[1] << endl;
        sum = k + a[1];
        int cnt = a[1]/k;
        if(a[1] % k) que.push(a[1] % k);
        int pos = 2;
        for(; pos <= n; pos ++) {
            if(cnt) {
                cnt += a[pos] / k;
                cnt --;
                sum += a[pos];
                if(a[pos] % k) que.push(a[pos] % k);
            } else break;
        }
        for(; pos <= n; pos ++) {
            int tmp = que.top();
            que.pop();
            sum += (k - tmp) + a[pos];
            que.push(a[pos]);
        }
        cout << sum << endl;
    }
    return 0;
}

K-th occurrence

以下代码学姐写的 orz 强啊
套了好多数据结构orz