L1-7 拼接梯子

本来一个挺简单的题……本菜写半天发现最小是图片说明 竟然特判的是等于等于1,输出no……我也不知道当初脑子怎么瓦特这么久,好在是IOI,最后还是发现了奇数直接出no,其余我是通过位运算一个个推到第一个1。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline ll read() {
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    ll n = read(), m = read();
    if ((1ll << n + 1) - 1 < m || m &1)
        puts("No");
    else {
        puts("Yes");
        int st = -1, cnt = 0;
        while (m) {
            if (m & 1)    st = cnt;
            m >>= 1;
            ++cnt;
        }
        printf("%lld\n", 1ll << st);
    }
    return 0;
}

L1-8 幻想乡炼金学

……悔恨!没看题目的模拟题,哪怕补题也是这样,现在看一下题目不就是个模拟么,小心谨慎一点,考虑到每种情况即可。
我选择开个二维vector保存全部的原子与原子团,吧()中间看成原子团保存在一维vector中,最后遍历全部原子中的全部字母,输入时计数。
有关计数新开一个int数组即可。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 155;
vector<string> v[N];
int pos[N];

int main() {
    js; //关了同步,就不能用getchar()等全部的C  OI函数了
    int cnt = 0;
    bool ok = false;
    string s = "";
    char ch;
    while ((ch = cin.get()) && ch != EOF) {
        if (ch == ' ')    continue; //空格没有用
        if (!islower(ch) && s.size()) { //现在不是小写字母,并且s里面有东西
            v[cnt].push_back(s);
            if (!ok)    ++cnt;    //不在一个()中
            s.clear();
        }
        if (isupper(ch))    s = ch;
        else if (islower(ch))    s += ch;
        else if (ch == '(')    ok = true;
        else if (ch == ')')    ok = false, ++cnt;
        else if (ch == '{') {
            int sum = 0;
            while (ch = cin.get()) {
                if (ch == ' ')    continue;
                if (ch == '}')    break;
                sum = sum * 10 + ch - '0';
            }
            pos[cnt - 1] = sum; //先更新了cnt
        }
    }
    for (int i = 0; i < cnt; ++i)
        if (!pos[i])    pos[i] = 1; //Fe(OH){2} ->防止 OOHH 没带括号的情况
    for (int i = 0; i < cnt; ++i) //每个原子
        for (int j = 0; j < v[i].size(); ++j) //每个原子的每个字母
            for (int k = 0; k < pos[i]; ++k) //次数
                cout << v[i][j];
    cout << endl;
    return 0;
}

L2-1 特殊的沉重球

……亏了,这么简单的题目没看,这要是什么大型比赛都会气死,果然还是要先去吧全部题目看完,在思考,大部分时间花在下一题栈里面了,还是0分。
哎!好吧,回归正题,这道题就算是一个比较裸的dfs题目吧,搜索,回溯,记得按体重降序排个序,不会找的那么死,(说人话就是减枝)
代码注释的比较详细了,应该不难理解……

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 25;
int a[N], b[N]; //精灵体重,每个宝贝球已经装备的精灵重量
int ans;
int n, w;

void dfs(int x, int now) { //当前编号,当前用掉的宝贝球数目
    if (now >= ans)    return; //最优性剪枝
    if (x > n) {
        ans = min(ans, now);
        return;
    }
    for (int i = 1; i <= now; ++i) {
        if (a[x] + b[i] <= w) //如果存在一个之前的宝贝球可以放进a[x]去
            b[i] += a[x], dfs(x + 1, now), b[i] -= a[x]; //宝贝球不增加
    }
    // 为这个人单独开一个宝贝球
    b[now + 1] = a[x];
    dfs(x + 1, now + 1);
    b[now + 1] = 0;
}

int main() {
    n = read(), w = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    sort(a + 1, a + 1 + n, greater<int>());
    ans = n;
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}

L2-2 又见火车入栈

因为存在查询前y项记录用STL的stack肯定是不行的,只能手写一个栈,并且可以发现,查询和我进出栈没关系,考虑离线。
对于每个输入的查询,用一个数组a保存,在模拟进出栈的情况,模拟到第k条记录时,停止,这里要考虑输入不是递增,需要将查询数组按照记录升序先排序在查询,将答案更新为当前入栈的第y辆火车

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e6 + 7;
struct Node { //离线数组
    int l, r;
    int id;
    bool operator < (const Node& a)const {
        if (l == a.l)    return id < a.id;
        return l < a.l;
    }
}a[N];
int ans[N], vis[N];
int st[N], top; //手动模拟栈

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        char s[5];
        scanf("%s", s);
        if (s[0] == 'i')    vis[i] = 1; //1入0出
    }
    int m = read();
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        a[i] = { l,r,i }; //离线查询
    }
    sort(a + 1, a + 1 + m); //按记录排序
    int k = 0, num = 0; //k记录第几条指令,num记录当前最后一次入栈火车序号
    for (int i = 1; i <= m; ++i) {
        while (a[i].l != k) { //模拟栈
            if (vis[++k])    st[++top] = ++num;
            else    --top;
        }
        ans[a[i].id] = st[a[i].r];
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

L2-3 新旷野地带

啊啊啊!本来可以快A的,因为取模忘记了最后拿了个10分,心累……
第一步:预处理组合数的阶乘以及费马小定理处理阶乘的逆元。
第二步:对于每个给定的K,选定k行k列存在图片说明 种选择方式,填涂一行一列一个士兵很显然是k的阶乘种方案。
那么只需要枚举从1到k的全部取值组合,如果大于n或者大于m,说明有一个行或列一定存在2个士兵。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e6 + 7;
const int MOD = 1e9 + 7;
ll jc[N], inv[N];

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)  (ans *= a) %= MOD;
        b >>= 1;
        (a *= a) %= MOD;
    }
    return ans;
}

void init() {
    jc[0] = 1;
    for (int i = 1; i <= 1000000; ++i)   jc[i] = jc[i - 1] * i % MOD;
    inv[1000000] = qpow(jc[1000000], MOD - 2);
    for (int i = 999999; i >= 0; --i)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll C(int n, int m) {
    return jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}

ll A(int n, int m) {
    return jc[n] * inv[n - m] % MOD;
}

int main() {
    init();
    int n = read(), m = read(), k = read();
    ll ans = 0;
    for (int i = 1; i <= k; ++i){
        if(i>n || i>m)    break;
        (ans += C(n, i) * C(m, i) % MOD * jc[i] % MOD)%=MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

L2-4 缘之空

穹妹这么可爱,虽然她在最后一个,也必须把她给肝出来)我说的是题目,你以为是啥。
图片说明

虽然这个在最后一题,不过难度也不算很大,给我感觉就是LCA(树上最近公共祖先)的模板题……但是因为本菜的一系列魔幻操作,在WA了很多遍后才找到正确答案。
第一步:这题不是以1为根!!划重点,是需要你去找根的,我直接用1是根稳定0分……好狠,直接开个数组,统计入度,入度为0的点就是根节点。
第二步:从根节点开始dfs,预处理倍增数组,以及求解深度。具体LCA的倍增方法这里就不展开了,不懂的同学可以去网上自行百度。
第三步:对于每次查询,如果LCA找到的是自己,说明一个是一个祖先直接输出NO(这里一开始没看到也WA了几发),否则就是树上距离的公式
图片说明 再去和4比较就行了。虽然好像是祖先也要求距离!不过这个距离是一个根节点一个子节点,直接deep相减一下。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;

vector<int> e[N];
int deep[N];
int vis[N];
int fa[N][20]; //log2(100000)  = 16.

void dfs(int x, int y) { //dfs求到深度以及预处理x的倍增数组
    fa[x][0] = y;
    deep[x] = deep[y] + 1;
    for (int i = 1; i < 20; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = 0; i < e[x].size(); ++i) {
        int tmp = e[x][i];
        if (tmp != y)
            dfs(tmp, x);
    }
}

int lca(int x, int y) {
    if (deep[x] < deep[y])    swap(x, y);
    for (int i = 19; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i]; //调整到同一深度
    if (x == y)    return x;
    for (int i = 19; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int main() {
    int n = read(), m = read(), rt = 0;
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        e[u].push_back(v);
        ++vis[v];
    }
    for(int i=1;i<=n;++i)
        if(!vis[i])    {
            rt=i;
            break;
        }
    dfs(rt, 0);
    while (m--) {
        int u = read(), v = read();
        int ans;
        int tmp = lca(u, v);
        if (tmp == u || tmp == v)    ans = abs(deep[u] - deep[v]); //虽然好像有点多余……请别在意
        else
            ans = deep[u] + deep[v] - 2 * deep[tmp];
        if (ans <= 4 || tmp == u || tmp == v)    puts("NO");
        else    puts("YES");
        printf("%d\n", ans);
    }
    return 0;
}