A – 1-2-4 Test

题目描述：

三场考试，分数分别是1、2、4，现在知道A和B的三场总分数分别是多少，现在C只能通过A或B能通过的考试，而不能通过A和B都不能通过的考试，问C的分数

思路：

就是求 A｜B

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n >> m;
    cout << (n|m) << endl;
}

int main(){
    io;
    work();
    return 0;
}

B – Hammer

题目描述：

一维直线，你现在在0，目标地点为X, Y处有一个门，Z处有门的钥匙，问你到达X的最短路程是多少，如果不能到达，则输出-1

思路：

分类讨论一下就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int x, y, z;

void work(){
    cin >> x >> y >> z;
    if(x == 0){
        cout << 0 << endl;
    }
    else if(x > 0){
        if(y < 0 || y > x)cout << x << endl;
        else {
            if(z > y)cout << -1 << endl;
            else{
                if(z > 0)cout << x << endl;
                else cout << -z*2 + x << endl;
            }
        }
    }
    else{
        if(y < x || y > 0)cout << -x << endl;
        else{
            if(z < y)cout << -1 << endl;
            else {
                if(z > 0)cout << 2*z - x << endl;
                else cout << -x << endl;
            }
        }
    }
}


int main(){
    io;
    work();
    return 0;
}

C – Simple path

题目描述：

给你一棵树，给定起点和和终点，输出从起点到终点的路径

思路：

简答的dfs就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k, x, y;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int fa[MAX];
void dfs(int u, int ff){
    if(u == x){
        int p = x;
        while(p != y){
            cout << p << ' ';
            p = fa[p];
        }
        cout << y << endl;
        exit(0);
    }
    for(int i = head[u];i;i = tr[i].nex){
        int v = tr[i].to;
        if(ff == v)continue;
        fa[v] = u;
        dfs(v, u);
    }
}

void work(){
    cin >> n >> x >> y;
    for(int i = 1; i < n; ++i){
        cin >> m >> k;
        add(m, k);add(k, m);
    }
    dfs(y, -1);
    
}

int main(){
    io;
    work();
    return 0;
}

D – Stones

题目描述：

给定一个序列A,现在存在K个石头，两个人进行博弈，Alice先手，Bob后手，无论谁操作，都可以选择Ai个石头从K个中移走给自己，其中要保证ai<=k，问Alice最多能获得多少的石头

思路：

dp

dp[i]表示初始为i个石头时，先手最多能获得多少石头

枚举最后一次获得的是a[j]个石头时

状态转移方程式为：dp[i] = max(dp[i], i-dp[i-tr[j]])

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
int dp[MAX];
void work(){
    cin >> k >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= k; ++i){
        for(int j = 1; j <= n; ++j){
            if(i >= tr[j])dp[i] = max(dp[i], i - dp[i - tr[j]]);
        }
    }
    cout << dp[k] << endl;
}


int main(){
    io;
    work();
    return 0;
}

E – Apple Baskets on Circle

题目描述：

n个盘子围成一圈，每个盘子中有a[i]个苹果，你现在要吃K个苹果，从第一个盘子开始，如果当前的盘子有苹果，则拿走一个并进入下一个盘子，如果当前盘子没有苹果就跳过这个盘子，问最后每个盘子的数量是多少

思路：

先二分一下拿完K个苹果需要多少轮

假设check mid，我们遍历这n个盘子，统计拿mid轮最多能拿多少个，如果大于等于k就缩小mid，否则就加大mid

假设找出进行p轮后，我们先遍历一遍，从每个盘子中扣去p-1个苹果，然后统计出剩余的数量后，再从头开始扣苹果，知道都扣完，然后输出就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n;
ll k;
ll tr[MAX];

bool judge(ll mid){
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += min(mid, tr[i]);
    }
    return ans >= k;
}
ll ans[MAX];
void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    ll l = 0, r = 1e12;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(!judge(mid))l = mid + 1;
        else r = mid - 1;
    }
    for(int i = 1; i <= n; ++i){
        ans[i] = min(l-1, tr[i]);
        tr[i] = max(0ll, tr[i]-l+1);
        k -= ans[i];
    }
    for(int i = 1; i <= n; ++i){
        if(k && tr[i]){
            --tr[i];--k;
        }
    }
    for(int i = 1; i <= n; ++i)cout << tr[i] << ' ';
}


int main(){
    io;
    work();
    return 0;
}

F – Transportation

题目描述：

n个点，m条边，每条边都有一个边权，每个点可以建机场，花费是xi,每个点也可以建火车站，花费是yi,任意两个机场直接可以直接到达，同样的，任意两个火车站之间也可以直接到达，求一下最小生成树

思路：

对于机场，我们抽象出一个虚拟中间点n+1,将每个点建机场的花费做为一条边连到n+1去

对于火车站，我们同样的去抽象出一个虚拟中间点n+2,将每个点建火车站的花费做为一条边连到n+2去

然后枚举四种情况：不建机场不建火车站、建机场不建火车站、不建机场建火车站、建机场建火车站

分别求一下最小生成树就行，取最小值

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;
typedef pair<ll, pii> piii;
#define MAX 300000 + 50
ll n, m, k, x;
ll ar[MAX], br[MAX];
struct node{
    ll a, b, c;
}cr[MAX];

vector<piii>G;
int fa[MAX];
int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void emerge(int x, int y){
    fa[getfa(x)] = getfa(y);
}
void init(){
    for(int i = 0; i <= n+2; ++i)fa[i] = i;
    G.clear();
}

ll kruskal(int n){
    ll sum = 0;
    int num = 0;
    sort(G.begin(), G.end());
    for(auto [c, p] : G){
        auto [x, y] = p;
        if(getfa(x) != getfa(y)){
            ++num;
            sum += c;
            emerge(x, y);
        }
    }
    if(num == n - 1)return sum;
    else return 1e18;
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= n; ++i)cin >> br[i];
    for(int i = 1; i <= m; ++i){
        cin >> cr[i].a >> cr[i].b >> cr[i].c;
    }
    ll ans = 1e18;
    int num[] = {0, 1, 1, 2};
    for(int j = 0; j <= 3; ++j){
        init();
        for(int i = 1; i <= m; ++i)G.push_back(m_p(cr[i].c, m_p(cr[i].a, cr[i].b)));
        if(j&1)for(int i = 1; i <= n; ++i)G.push_back(m_p(ar[i], m_p(i, n+1)));
        if((j/2)&1)for(int i = 1; i <= n; ++i)G.push_back(m_p(br[i], m_p(i, n+2)));
        ans = min(ans, kruskal(n+num[j]));
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}