西安邮电第五届校赛

A.拯救咕咕咕之史莱姆
链接:https://ac.nowcoder.com/acm/contest/5678/A
可以算出来史莱姆每天减的血量
第一天：3
第二天：6
第三天：9
第四天：12
第五天：18
第六天：27
总和为:75
因此当血量<= 75 就会求饶

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

int main()
{
    ll n;
    while(cin >> n, n) {
        if(n <= 75) puts("AOLIGEI!");
        else puts("DAAAAAMN!");
    }
    return 0;
 } 

校车
链接：https://ac.nowcoder.com/acm/contest/5678/G
离散差分

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010;

vector<pii> segs;
vector<int> alls;
int a[N];

unordered_set<int> much;

int T, query;

void insert(int l, int r) {
    a[l] += 1;
    a[r] -= 1;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &query);
        while(query--) {
            int x, y;
            scanf("%d%d", &x, &y);
            segs.push_back({x, y});
            alls.push_back(x);
            alls.push_back(y);
            if(!much.count(x)) much.insert(x);
            if(!much.count(y)) much.insert(y);
        }
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        for(auto seg : segs) {
            int x = lower_bound(alls.begin(), alls.end(), seg.first) - alls.begin() + 1;
            int y = lower_bound(alls.begin(), alls.end(), seg.second) - alls.begin() + 1;
            insert(x, y);    
        }
        for(int i = 1; i <= alls.size(); i++) a[i] += a[i - 1];
        sort(a + 1, a + 1 + alls.size());
        printf("%d %d\n", much.size(), a[alls.size()]);
        much.clear();
        segs.clear();
        memset(a, 0, sizeof a);
    }
    return 0;
}

无敌阿姨
链接:https://ac.nowcoder.com/acm/contest/5678/E

#include<bits/stdc++.h>
using namespace std;
const int N = 105;

int a[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m, k;
        int sum = 0;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        int ans = 0, res;
        int now = 0;
        while(now < sum) {
            ans++;
            res = m;
            for(int i = 1; i <= n; i++) {
                if(a[i]) {
                    while(a[i] && res) {
                        a[i]--;
                        res--;
                        now++;
                    }
                    if(res <= k) 
                        break;
                    res -= k;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

烦人的依赖
链接:https://ac.nowcoder.com/acm/contest/5678/B
软件之间的依赖关系看成又向无环图，题目要按字典序排因此要用优先队列小根堆进行存储。

#include<bits/stdc++.h>
using namespace std;
const int N =  30010;

int T, n, m, cnt, an;
string s, t;
string soft[N];
int in[N];       //入度数 
vector<int> edge[N];
priority_queue<int, vector<int>, greater<int> > heap;   //由于当软件等级一样时按照字典序从小到大排， 因此用小根堆      
int ans[N];
unordered_map<string, int> mp;     //需要将软件映射成数字才能进行连边 

void init() {      //由于多组数据进行输入 要对整体进行初始化 
    memset(in, 0, sizeof in);  //度数初始化 
    while(!heap.empty()) //堆的初始化 
        heap.pop();
    for(int i = 1; i <= n; i++)  //对边的初始化 
        edge[i].clear();
    mp.clear(); //映射初始化 
    cnt = 0;  //topsort 的点数 
}

void solve() {
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; i++)
        cin >> soft[i];
    sort(soft + 1, soft + 1 + n);  //从小到大排序 
    for(int i = 1; i <= n; i++)   //进行赋值 
        mp[soft[i]] = i;
    for(int i = 1; i <= m; i++) {
        cin >> s >> t;
        ++in[mp[t]]; //入度++ 
        edge[mp[s]].push_back(mp[t]); //连边 
    }
    for(int i = 1; i <= n; i++) //将入度为0的存入堆中 
        if(!in[i]) heap.push(i);
    while(!heap.empty()) {
        int t = heap.top();
        heap.pop();
        ans[++cnt] = t; //用来存最终的答案 
        for(auto v : edge[t]) { //遍历边 
            if(!(--in[v])) heap.push(v);  //入度为0存入队列 
        }
    }
    printf("Case #%d:\n", ++an);
    if(cnt != n) {         //若点数不服则不存在 
        printf("Impossible\n");
        return ;
    }
    for(int i = 1; i <= cnt; i++)
        cout << soft[ans[i]] << endl;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

异或生成树
dp[i][j]表示以i为节点能异或出来的值， 1表示能够组成出来，0表示不能够组成出来
由于是异或因此范围是0-127
状态转移方程为dp[u][i ^ j] = dp[u][i] & dp[v][j];
代码如下

#include<bits/stdc++.h>
using namespace std;
const int N = 105, M = 1 << 7;

int n;
vector<int> G[N];
int ans = 0, a[N], dp[N][M], tmp[M];

void dfs(int u, int f) {
    dp[u][a[u]] = 1;       //由于u存在这样的点a[u] 因此赋值为1 
    for(auto v : G[u]) {
        if(v != f) {
            dfs(v, u);
            memset(tmp, 0, sizeof tmp);    //将其初始化为0，让tmp 和 dp 去或(|) 判断这样的点是否存在 
            for(int i = 0; i < 128; i++) {
                for(int j = 0; j < 128; j++)            //u 为父节点 v 为子节点 若存在 &上为1 tmp|上为1 
                    tmp[i ^ j] |= dp[u][i] & dp[v][j]; //这一步求出父节点和子节点的异或的值有哪些  
            }
            for(int i = 0; i < 128; i++) //对dp的值进行更新 
                dp[u][i] |= tmp[i];
        }
    }
    for(int i = 0; i < 128; i++) 
        if(dp[u][i])
            ans = max(ans, i);    //找到最大值 
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, -1);
    printf("%d", ans);
    return 0;
}