1922(Edu161div2)

被打爆的一场，之后更加要多打 cf 了！

A. Tricky Template

给出字符串长度 $n$，和字符串 $a,b,c(\mathrm{小}\mathrm{写})$.

假设一个模板是由 $n$ 个小写和/或大写拉丁字母组成的字符串 $t$ 。如果从 $1$ 到 $n$ 的所有 $i$ 都满足以下条件，则字符串 $s$ 与模板 $t$ 匹配：

• 如果模板中第 $i$ 个字母是小写字母，那么 $s_i$ 必须与 $t_i$ 相同；
• 如果模板中的第 $i$ 个字母是小写字母，那么 $s_i$ 必须与 $t_i$ 的小写版本不同。例如，如果模板中有字母 "A"，则不能在字符串的相应位置使用字母 "a"。

因此，如果至少有一个 $i$ 的条件不成立，字符串就与模板不匹配。

判断是否存在模板 $t$ ，使得字符串 $a$ 和 $b$ 与之匹配，而字符串 $c$ 不匹配。

Solution

根本没看懂题目意思 $\dots$

我当时的想法是只要 a,b,c不要都相同且a,b不相同的部分，不能与c相同 我觉得做法很正确，但是一直 wa，服了 $\dots$

bool ok = true;
for (int i = 0; i < n; i++)
{
	if ((a[i] == c[i] || b[i] == c[i]) && a[i] != b[i])
		ok = false;
	if (a == c || b == c)
		ok = false;
}

$\text{WOC!!!!!}$,答案那么简单，我都没过 $!!!!\dots ..$

Jiangly 的答案. 这么简单的题我做了那么久，我真是废物啊

只要 a 与 c 不同的部分，b 与 c 也不同即可。

for (int i = 0; i < n; i++) {
	if (a[i] != c[i] && b[i] != c[i]) {
		std::cout << "YES\n";
		return;
	}
}
std::cout << "NO\n";

B. Forming Triangles

你有 $n$ 根木棒，编号从 $1$ 到 $n$ 。第 $i$ 根木棒的长度是 $2^{a_i}$ 。

你想从给定的 $n$ 根小木棍中选出准确的 $3$ 根小木棍，并用这些小木棍作为三角形的边，组成一个三角形

输出选择 $3$ 根小棒组成三角形的方式的数量。不考虑顺序（即选择 $1,2,4\equiv 2,1,4\dots$）

我的答案仍然是错误的，但是至少方向找对了

void solve()
{
    memset(num, 0, sizeof num);
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++)
        cin >> a[i], num[a[i]]++;
    if (n < 3)
    {
        cout << "0\n";
        return;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] == 1)
            cnt++;
    }
    ll ans = ((n - cnt) * (n - cnt - 1) * (n - cnt - 2)) / 6 + (cnt ? (n - cnt) : 0);
    cout << ans << '\n';
}

Solution

Jiangly

• 有两个一样的，另外一个必须小于等于两个一样的数。
• 三个数字一样

所以答案等于 C(相等的个数，3)+c(相等的个数，2)*比这个数字小的个数

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        cnt[a]++;
    }
    ll ans = 0;
    int tot = 0;
    for (int i = 0; i <= n; i++) {
        ans += 1LL * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
        ans += 1LL * cnt[i] * (cnt[i] - 1) / 2 * tot;
        tot += cnt[i];
    }
    std::cout << ans << "\n";
}

C. Closest Cities

给出一个长度 $n$ 的升序数组, 从下标为 $x\to y$ 消费的金币为 $\mid a_x-a_y\mid$

For each city $i$, let's define the closest city $j$ as the city such that the distance between $i$ and $j$ is not greater than the distance between $i$ and each other city $k$.

• 前往距离为 $x$ 最近的城市，支付 $1$ 金币
• 前往其他城市，支付 $\mid a_x-a_y\mid$ 金币

输出最少的花费。

Solution

比较前后的距离，给予 1,-1,0
$f_1[i]$ 数组记录 $[1-(i+1)]$ 需要消费的金币

$f_2[i]$ 表示 $[i-1]$ 消耗的金币

$x<y:$ ans=f1[y - 1] - f1[x - 1]

$x>y:$ ans=f2[x] - f2[y]

void solve()
{
    int n, m;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i].first;
    a[1].second = 1, a[n].second = -1;
    for (int i = 2; i <= n - 1; i++)
    {
        if (a[i].first - a[i - 1].first < a[i + 1].first - a[i].first)
            a[i].second = -1;
        else if (a[i].first - a[i - 1].first > a[i + 1].first - a[i].first)
            a[i].second = 1;
        else
            a[i].second = 0;
    }
    vector<int> f1(n), f2(n + 1);
    for (int i = 1; i < n; i++)
        f1[i] = f1[i - 1] + (a[i].second >= 0 ? 1 : a[i + 1].first - a[i].first);
    // 1---n-1 f[i]表示1--i+1需要消费的金币f[1] 1--2 f[4] 1--5 f[4]-f[2]=3--5
    cout << endl;
    for (int i = n; i > 1; i--)
        f2[i] = (a[i].second <= 0 ? 1 : a[i].first - a[i - 1].first);
    for (int i = 2; i <= n; i++)
        f2[i] = f2[i - 1] + f2[i];
    // 2---n  f2[i]表示i--1消耗的金币 f[2] 2--1  f[5] 5--1   f[5]-f[2] 5--2
    cin >> m;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        if (x < y)
            cout << f1[y - 1] - f1[x - 1] << '\n';
        else
            cout << f2[x] - f2[y] << '\n';
    }
}

D. Berserk Monsters

一排有 $n$ 个怪物相互攻击，对于每个怪物：有攻击值: $a_i$,防御值：$d_i$

每个怪物都会向左右两个活着的怪物发起攻击，如果某怪物受到了超过自身防御的伤害，则死亡。

输出 $n$ 个整数，第 $i$ 个整数等于在第 $i$ 回合死亡怪物的数量。

Solution

一个大模拟题

第一轮遍历完之后，之后每一轮只需要检测上一轮死亡的怪物相邻的怪物即可。

$l,r$ 数组记录相邻的怪物的索引(不存在则为-1)。

• 若该怪物不在边界，则将 sum 加上相邻的攻击伤害。（边界则特殊考虑即可）

$vis$ 数组记录该怪物是否已经遍历过了。

对于该轮死亡的怪物

• 若 x 左边还有活着的怪物，则将 x 左边还活着的怪物 的右索引更新为 x 的右索引。(这相当于将这时 死亡的怪物的左边相邻还活着的怪物的右索引 改为了 这时已经死亡了的怪物的右索引)，如果左边还活着的怪物这轮没有死，则将左边相邻还活着的怪物加入 v 数组(下轮将继续检测该怪物会不会被新来的怪物杀死)，这时将这个怪物设置为已经遍历过。
• 若 x 左边还有活着的怪物，与上面类似。将 x 右边还活着的怪物 的右索引更新为 x 的右索引。$\dots$

Jiangly 代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), d(n), l(n), r(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> d[i];

    for (int i = 0; i < n; i++)
        l[i] = i - 1, r[i] = i + 1;
    r[n - 1] = -1;
    vector<int> v;
    for (int i = 0; i < n; i++)
        v.push_back(i);
    vector<int> vis(n, -1);

    for (int i = 0; i < n; i++)
    {
        vector<int> die;
        for (auto x : v)
        {
            int sum = 0;
            if (l[x] != -1)
                sum += a[l[x]];
            if (r[x] != -1)
                sum += a[r[x]];
            if (sum > d[x])
                die.push_back(x);
        }
        v.clear();
        cout << die.size() << " \n"[i == n - 1];
        for(auto x:die)
            vis[x] = i;
        for(auto x:die)
        {
            if(l[x]!=-1)
            {
                r[l[x]] = r[x];
                if(vis[l[x]]<i)
                    v.push_back(l[x]), vis[l[x]] = i;
            }
            if(r[x]!=-1)
            {
                l[r[x]] = l[x];
                if(vis[r[x]]<i)
                    v.push_back(r[x]), vis[r[x]] = i;
            }
        }
    }
}

E. Increasing Subsequences

让我们回顾一下，数组 $a$ 的递增子序列是指在不改变其余元素顺序的情况下，通过移除一些元素而得到的序列，并且其余元素是严格递增的（即 $a_{b_1}<a_{b_2}<\cdots <a_{b_k}$ 和 $b_1<b_2<\cdots <b_k$ ）。请注意，空子序列也是递增的。

给你一个正整数 $X$ 。你的任务是找出一个长度为最多为 $200$ 的整数数组，使得它有恰好 $X$ 个递增的子序列，或者报告说没有这样的数组。如果有多个答案，你可以打印其中任何一个。

如果两个子序列由相同的元素组成，但在数组中的位置不同，则认为它们是不同的（例如，数组 $[2,2]$ 有两个不同的子序列等于 $[2]$ ）

P8376 [APIO2022] 排列 - 洛谷 P8376 排列 - 洛谷

Percepts of AtCoder 2 - 洛谷 Percepts of AtCoder 2 - 洛谷

AGC012-C

(听说是和这个题目一样的类型，但是需要转化一下 $\dots$,(我不知道如何转化 $\dots$))(待更 $\dots$)

找到一个长度不超过 200 的数组使得恰好有 $X$ 个递增的子序列，并输出，若不存在，输出-1(空序列也是递增的)

Solution

在洛谷上的题目给出了一个比较符合我的题解：

$\mathrm{胡}\mathrm{言}\mathrm{乱}\mathrm{语}ing\dots$

我只能想到答案一定和二进制有关，一个长度为 $n$ 的递增序列，可以构成 $2^n$ 个递增的子序列，长度为 n-1 的递增序列后面加上一个递增的且完全小于前面序列的所有数字的序列就可构成 $2^{n-1}+2^{\mathrm{加}\mathrm{上}\mathrm{的}\mathrm{序}\mathrm{列}\mathrm{的}\mathrm{长}\mathrm{度}}-1$，（每次加上一个序列后，本来空序列也算是递增的，但是不能叠加，所以会少一个）这样递推下去 $\dots$

有 $2^n+2^{n-1}+\cdots +2^m-\text{Numbers - 1 }=X$

即一个 二进制串化为十进制 $-$ (该二进制串中 1 的个数-1) = $X$

将该二进制串 $\to$ 递增的子序列 $\to n$ 个最大且最长的子序列 $+\cdots +m$ 个最短且最小的子序列(啮合在一起即可)

大概我的思路就是这样，但是感觉实现就是差一点 $\dots$

按照上面洛谷的思路,我的代码(成功 AC)：

void solve()
{
    ll x;
    cin >> x;
    bitset<64> a(x);

    int idx = 63;
    for (int i = 63; i >= 0; i--)
        if (a[i]){
            idx = i;
            break;
        }
        
    vector<int> ans(__lg(x) + 1, 0);
    for (int j = 1; j <= idx; j++) ans[j] = j;
    for (int i = idx - 1; i >= 0; i--) {
        if (a[i]) {
	        ans.insert(ans.begin() + i + 1, ++idx);
        }
    }

    cout << ans.size() - 1 << '\n';
    for (int i = 1; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << "\n";
}

我还有想法：

• 法一：先按照 $1,2,3\dots$，第一轮后，在后面加 较小的数字 来满足要求 (是二进制第几位就加上几) $\dots$ (待更 $\dots$)
• 法二：从小到大加，加最前面 $+1$,加最后面 $\times 2$,即可构造。

Jiangly 代码：

int l = 0, r = 0;
vector<int> ans;
void cal(ll x)
{
    if(x==1)
        return;
    if(x%2==1)
    {
        cal(x - 1);
        ans.push_back(--l);
    }    
    else 
    {
        cal(x / 2);
        ans.push_back(++r);
    }
}
void solve()
{
    ans.clear();
    ll x;
    cin >> x;
    l = 0, r = 0;
    cal(x);
    cout << ans.size() << '\n';
    for (auto v : ans)
        cout << v << ' ';
    cout << '\n';
}

榜一的答案

(未搞懂 if ((x >> i) & 1) 如何保证的正确性 $\dots$)

void solve()
{
    ll x;
    cin >> x;
    int t = __lg(x); //如果用log2(x)会wa
    vector<int> ans;
    for (int i = 0; i < t; i++)
        ans.push_back(i);
    for (int i = t - 1; i >= 0; i--)
        if ((x >> i) & 1)
            ans.push_back(i);
    cout << ans.size() << '\n';
    for (auto x : ans)
        cout << x << " ";
    cout << '\n';
}

• __lg(x) 函数返回的是整数，为 $\lfloor {\log }_2(x)\rfloor$ 的准确值
• log2(x) 函数返回的是浮点数，因此可能会有浮点数误差的存在 $\dots$

F. Replace on Segment

(待更 $\dots$)