首页 > 其他分享 >Codeforces Round 983 div2 个人题解(A~D)

Codeforces Round 983 div2 个人题解(A~D)

时间：2024-11-02 08:50:33浏览次数：1  
标签：typedef 开关 题解 Codeforces leq 测试用例 983 include 节点

Codeforces Round 983 div2 个人题解(A~D)

Dashboard - Codeforces Round 983 (Div. 2) - Codeforces

火车头

#define _CRT_SECURE_NO_WARNINGS 1

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <chrono>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

#define ft first
#define sd second

#define yes cout << "yes\n"
#define no cout << "no\n"

#define Yes cout << "Yes\n"
#define No cout << "No\n"

#define YES cout << "YES\n"
#define NO cout << "NO\n"

#define pb push_back
#define eb emplace_back

#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define unq_all1(x) x.erase(unique(all1(x)), x.end())
#define sort_all(x) sort(all(x))
#define sort1_all(x) sort(all1(x))

#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fLL

#define RED cout << "\033[91m"     // 红色
#define GREEN cout << "\033[92m"   // 绿色
#define YELLOW cout << "\033[93m"  // 蓝色
#define BLUE cout << "\033[94m"    // 品红
#define MAGENTA cout << "\033[95m" // 青色
#define CYAN cout << "\033[96m"    // 青色
#define RESET cout << "\033[0m"    // 重置

template <typename T>
void Debug(T x, int color = 1)
{
    switch (color)
    {
    case 1:
        RED;
        break;
    case 2:
        YELLOW;
        break;
    case 3:
        BLUE;
        break;
    case 4:
        MAGENTA;
        break;
    case 5:
        CYAN;
        break;
    default:
        break;
    }
    cout << x;
    RESET;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t i128;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<ll, int> pli;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef tuple<int, int, int> ti3;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ld, ld, ld> tld3;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pli> vpli;
typedef vector<pss> vpss;
typedef vector<ti3> vti3;
typedef vector<tl3> vtl3;
typedef vector<tld3> vtld3;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue<int> qi;
typedef queue<ll> ql;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef queue<psi> qpsi;
typedef queue<psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;

typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<ll, ll> mll;
typedef map<ll, bool> mlb;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<char, bool> mcb;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef map<int, bool> mib;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

template <typename T>
inline T read()
{
    T x = 0;
    int y = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * y;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

/*#####################################BEGIN#####################################*/
void solve()
{
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int _ = 1;
    std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/
// 链接：

A. Circuit

Alice 刚刚制作了一个带有 \(n\) 个灯和 \(2n\) 个开关的电路。每个组件（灯或开关）都有两种状态：开或关。灯和开关的排列方式如下：

每个灯连接到恰好两个个开关。
每个开关连接到恰好一个灯。不知道每个开关连接到哪个灯。
当所有开关都关闭时，所有灯也会关闭。
如果切换开关（从开到关，或反之亦然），则连接到它的灯的状态也会切换。

Alice 把只显示 \(2n\) 个开关状态的电路带给她的妹妹 Iris，并给了她一个谜语：可以打开的灯的最小和最大数量是多少？

Iris 非常了解她妹妹的滑稽动作，她只用了一秒钟就给了 Alice 一个正确的答案。你能做到同样的事情吗？

输入
每个测试由多个测试用例组成。第一行包含一个整数 \(t\) (\(1 \leq t \leq 500\)) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 \(n\) (\(1 \leq n \leq 50\)) — 电路中的灯的数量。

每个测试用例的第二行包含 \(2n\) 个整数 \(a_1,a_2,…,a_{2n}\) (\(0 \leq a_i \leq 1\)) — 电路中开关的状态。 \(a_i=0\) 表示第 \(i\) 个开关关闭， \(a_i=1\) 表示第 \(i\) 个开关打开。

输出
对于每个测试用例，输出两个整数——分别表示可以打开的灯的最小数量和最大数量。

示例
输入

5
1
0 0
1
0 1
1
1 1
3
0 0 1 0 1 0
3
0 1 1 1 0 0

输出

0 0
1 1
0 0
0 2
1 3

提示
在第一个测试用例中，电路中只有一个灯，且没有开关开启，因此灯肯定是关闭的。

在第二个测试用例中，电路中只有一个灯，但与之连接的一个开关是开启的，因此灯是开启的。

在第三个测试用例中，电路中只有一个灯，且两个开关都是开启的，因此灯是关闭的，因为它被切换了两次。

在第四个测试用例中，为了没有灯开启，开关可以这样排列：

开关 \(1\) 和开关 \(4\) 连接到灯 \(1\)。由于两个开关都关闭，灯 \(1\) 也关闭。
开关 \(2\) 和开关 \(6\) 连接到灯 \(2\)。由于两个开关都关闭，灯 \(2\) 也关闭。
开关 \(3\) 和开关 \(5\) 连接到灯 \(3\)。两个开关都是开启的，因此灯 \(3\) 被切换了两次，从初始关闭状态保持关闭。
而为了开启 \(2\) 个灯，开关可以这样排列：

开关 \(1\) 和开关 \(2\) 连接到灯 \(1\)。由于两个开关都关闭，灯 \(1\) 也关闭。
开关 \(3\) 和开关 \(4\) 连接到灯 \(2\)。由于开关 \(3\) 是开启的而开关 \(4\) 是关闭的，灯 \(2\) 从初始关闭状态被切换了一次，因此它是开启的。
开关 \(5\) 和开关 \(6\) 连接到灯 \(3\)。由于开关 \(5\) 是开启的而开关 \(6\) 是关闭的，灯 \(3\) 从初始关闭状态被切换了一次，因此它是开启的。

解题思路

读题可知一个01对应一个开着的灯，而00和11对应着关着的灯。

所以如果1为偶数，则最小开灯数为\(0\)，1和0内部之间互相匹配，否则为\(1\)。

最大开灯数则为\(\min(\text{cnt0},\text{cnt1})\)

代码实现

void solve()
{
    int n;
    cin >> n;
    vi a(n * 2);
    int cnt0 = 0;
    int cnt1 = 0;
    for (int i = 0; i < n * 2; i++)
    {
        cin >> a[i];
        if (a[i] == 0)
            cnt0++;
        else
            cnt1++;
    }
    cout << (cnt1 & 1) << " " << min(cnt0, cnt1) << endl;
}

B. Medians

给定一个数组 $ a = [1, 2, \ldots, n] $，其中 $ n $ 为奇数，以及一个整数 $ k $。

您的任务是选择一个奇数正整数 $ m $，并将 $ a $ 拆分为 $ m $ 个子数组 $ b_1, b_2, \ldots, b_m $，使得：

  • 数组 $ a $ 的每个元素都只属于一个子数组。
  • 对于所有 $ 1 \leq i \leq m $， $ |b_i| $ 为奇数，即每个子数组的长度为奇数。
  • $ \text{median}([\text{median}(b_1), \text{median}(b_2), \ldots, \text{median}(b_m)]) = k $，即所有子数组中位数的数组中位数必须等于 $ k \(。\) \text{median}(c) $ 表示数组 $ c $ 的中位数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $ t $ （$ 1 \leq t \leq 5000 $）——测试用例数。测试用例说明如下。

每个测试用例的第一行包含两个整数 $ n $ 和 $ k $ （$ 1 \leq k \leq n < 2 \cdot 10^5 $，且 $ n $ 为奇数）——数组 $ a $ 的长度和所有子数组中位数数组的期望中位数。

保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。

输出
对于每个测试用例：

如果没有合适的分区，则单行输出 \(-1\)。
否则，在第一行输出一个奇数整数 $ m $ （$ 1 \leq m \leq n $），在第二行输出 $ m $ 个不同的整数 $ p_1, p_2, p_3, \ldots, p_m $ （$ 1 = p_1 < p_2 < p_3 < \ldots < p_m \leq n $）——表示每个子数组的左边界。具体来说，对于有效答案 $ [p_1, p_2, \ldots, p_m] $：

  • $ b_1 = [a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1}] $
  • $ b_2 = [a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1}] $
  • \(\ldots\)
  • $ b_m = [a_{p_m}, a_{p_m + 1}, \ldots, a_n] $

如果有多个解决方案，您可以输出其中任何一个。

示例
输入

4
1 1
3 2
3 3
15 8

输出

1
1
3
1 2 3
-1
5
1 4 7 10 13

提示
在第一个测试用例中，给定的分区有 $ m = 1 $ 且 $ b_1 = [1] $。显然 $ \text{median}([\text{median}([1])]) = \text{median}([1]) = 1 $。

在第二个测试用例中，给定的分区有 $ m = 3 $ 且：

  • $ b_1 = [1] $
  • $ b_2 = [2] $
  • $ b_3 = [3] $

因此， $ \text{median}([\text{median}([1]), \text{median}([2]), \text{median}([3])]) = \text{median}([1, 2, 3]) = 2 $。

在第三个测试用例中，对于 $ k = 3 $ 并没有有效的分区。

在第四个测试用例中，给定的分区有 $ m = 5 $ 且：

  • $ b_1 = [1, 2, 3] $
  • $ b_2 = [4, 5, 6] $
  • $ b_3 = [7, 8, 9] $
  • $ b_4 = [10, 11, 12] $
  • $ b_5 = [13, 14, 15] $

因此， $ \text{median}([\text{median}([1, 2, 3]), \text{median}([4, 5, 6]), \text{median}([7, 8, 9]), \text{median}([10, 11, 12]), \text{median}([13, 14, 15])]) = \text{median}([2, 5, 8, 11, 14]) = 8 $。

解题思路

由于分区长度任意，我们考虑把\(k\)单独拎出来放在最中间的分区，然后再左右两侧划分相同数量的分区。

\(k\)为奇数，我们可以\([1,1][2,k-1][k,k][k+1,k+1][k+2,n]\)划分。

\(k\)为偶数，我们可以\([1,k-1][k][k+1,n]\)划分

还要特判一下\(k=1，k=n\)和\(k\)刚好为中位数的情况

代码实现

void solve()
{
    ll n, k;
    cin >> n >> k;
    if (k == (n + 1) / 2)
    {
        cout << "1\n1\n";
        return;
    }
    if (k == 1 || k == n)
    {
        cout << "-1\n";
        return;
    }
    if (k & 1)
    {
        cout << "5\n";
        cout << 1 << " " << 2 << " " << k << " " << k + 1 << " " << k + 2 << "\n";
    }
    else
    {
        cout << "3\n";
        cout << 1 << " " << k << " " << k + 1 << "\n";
    }
}

C. Trinity

您将获得一个包含 $ n $ 个元素 $ a_1,a_2,…,a_n $ 的数组 $ a $。

您可以执行以下操作任意次数（可能是 0）：

选择两个整数 $ i $ 和 $ j $，其中 $ 1 \leq i,j \leq n $，并分配 $ a_i := a_j $。找出使数组 $ a $ 满足条件所需的最少操作数：

对于每个成对不同的索引三元组 \((x,y,z)\) （$ 1 \leq x,y,z \leq n $， $ x \neq y $， $ y \neq z $， $ x \neq z $），存在一个非退化三角形，其边长为 $ a_x \(、\) a_y $ 和 $ a_z $，即 $ a_x + a_y > a_z \(、\) a_y + a_z > a_x $ 和 $ a_z + a_x > a_y $。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $ t $ （$ 1 \leq t \leq 10^4 $）——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $ n $ （$ 3 \leq n \leq 2 \cdot 10^5 $）——数组 $ a $ 中的元素数量。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1,a_2,…,a_n $ （$ 1 \leq a_i \leq 10^9 $）——数组 $ a $ 的元素。

保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

输出
对于每个测试用例，输出一个整数——所需的最少操作数。

示例
输入

4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7

输出

3
1
0
8

提示
在第一个测试用例中，可以进行以下操作：

  1. 赋值 $ a_1 := a_4 = 4 $，数组变为 $ [4,2,3,4,5,6,7] $。
  2. 赋值 $ a_2 := a_5 = 5 $，数组变为 $ [4,5,3,4,5,6,7] $。
  3. 赋值 $ a_7 := a_1 = 4 $，数组变为 $ [4,5,3,4,5,6,4] $。

可以证明，最终数组中任意三元组的元素都能形成一个非退化三角形，且不可能用少于 3 次操作得到答案。

在第二个测试用例中，我们可以赋值 $ a_1 := a_2 = 3 $，使数组 $ a = [3,3,2] $。

在第三个测试用例中，由于 3、4 和 5 是有效的三角形边长，因此不需要对数组进行任何操作。

解题思路

观察题目要求和三角形的性质发现，我们实际上是在求一个极差小于最小值的区间，即\(\min\times2>\max\)。

所以我们可以先给数组排个序，枚举最小值，然后二分查找最大值，我们就得到了所需的区间。

但是！！！

这种做法忽略了最小值只有一个的情况，如果最小值只有一个且次小值加最小值大于最大值，也是可行的。

所以，我们应该枚举最小值和次小值，然后二分查找小于他们之和的最大值，所找到的区间即为三角形可行区间。

区间外的元素就是我们需要操作的元素。

代码实现

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n); // 注意a的范围为1e9，最小值和次值相加时可能会溢出
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(all(a));
    int ans = inf;
    for (int i = 1; i < n; i++)
    {
        int p = lower_bound(all(a), a[i] + a[i - 1]) - a.begin();
        ans = min(ans, n - p + i - 1);
    }
    cout << ans << endl;
}

D. Genokraken

这是一个交互式问题。

清理完水边区域后，Gretel 发现了一个名为 Genokraken 的怪物，她将其控制起来用于科学研究。

怪物的神经系统可以构造为一棵由 $ n $ 个节点组成的树，编号从 $ 0 $ 到 $ n−1 $，以节点 $ 0 $ 为根。

Gretel 的目标是了解怪物神经系统的确切结构——更具体地说，她想知道树的值 $ p_1,p_2,…,p_{n−1} $，其中 $ p_i $ （$ 0 \leq p_i < i $）是节点 $ i $ （$ 1 \leq i \leq n−1 $）的直接父节点。

她不知道节点的具体放置方式，但她知道一些方便的事实：

  • 如果我们删除根节点 $ 0 $ 和所有相邻边，这棵树将变成仅由路径组成的森林。最初与节点 $ 0 $ 相邻的每个节点将成为某条路径的终点。
  • 节点的索引方式为，如果 $ 1 \leq x \leq y \leq n−1 $，则 $ p_x \leq p_y $。
  • 节点 $ 1 $ 恰好有两个相邻节点（包括节点 $ 0 $）。

Gretel 可以对包含单元进行查询：

“? a b”（$ 1 \leq a,b < n \(，\) a \neq b $）——单元将检查节点 $ a $ 和 $ b $ 之间的简单路径是否包含节点 $ 0 $。但是，为了避免过度刺激生物而导致意外后果，Gretel 最多希望查询 $ 2n−6 $ 次。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $ t $ （$ 1 \leq t \leq 500 $）——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $ n $ （$ 4 \leq n \leq 10^4 $）——Genokraken神经系统中的节点数。

保证所有测试用例的 $ n $ 之和不超过 $ 10^4 $。

交互

对于每个测试用例，交互从读取整数 $ n $ 开始。

然后您可以进行以下类型的查询：

“? a b”（不带引号）（$ 1 \leq a,b < n \(，\) a \neq b $）。查询后，读取一个整数 $ r $——查询的答案。您最多可以使用 $ 2n−6 $ 个此类查询。

  • 如果节点 $ a $ 和 $ b $ 之间的简单路径不包含节点 $ 0 $，您将得到 $ r=0 $。
  • 如果节点 $ a $ 和 $ b $ 之间的简单路径包含节点 $ 0 $，您将得到 $ r=1 $。
  • 如果您进行了超过 $ 2n−6 $ 次查询或进行了无效查询，您将得到 $ r=−1 $。您需要在此之后终止以获得“错误答案”判决。

当您找出结构时，以“! $ p_1 \ p_2 \ \ldots \ p_{n−1} $”（不带引号）格式输出一行，其中 $ p_i $ （$ 0 \leq p_i < i $）表示节点 $ i $ 的直接父节点的索引。此查询不计入 $ 2n−6 $ 查询限制。

解决一个测试用例后，程序应立即转到下一个测试用例。解决所有测试用例后，程序应立即终止。

示例

输入

3
4
1
5
1
0
9

输出

? 2 3
! 0 0 1
? 2 3
? 2 4
! 0 0 1 2
! 0 0 0 1 3 5 6 7

提示
在第一个测试用例中，Genokraken 的神经系统形成了以下树：

对“? 2 3”的答案是 $ 1 $。这意味着节点 $ 2 $ 和 $ 3 $ 之间的简单路径包含节点 $ 0 $。

在第二个测试用例中，Genokraken 的神经系统形成了以下树：

对“? 2 3”的答案是 $ 1 $。这意味着节点 $ 2 $ 和 $ 3 $ 之间的简单路径包含节点 $ 0 $。

对“? 2 4”的答案是 $ 0 $。这意味着节点 $ 2 $ 和 $ 4 $ 之间的简单路径不包含节点 $ 0 $。

解题思路

说人话的题意：

给了你一棵特殊的树，其节点编号为\(0\sim n-1\)，根节点为\(0\)。

有3个性质

  1. 除了根节点外，其它节点最多只有一个子节点。
  2. 如果节点\(u\)的编号小于\(v\)的编号，即\(u<v\)，它们的父亲\(p_u\)和\(p_v\)的关系为\(p_u\le p_v\)。
  3. \(1\)固定为根节点的一个子节点。

如果我们把根节点下的各个子树称为链，每次可以询问\(a\)和\(b\)是否不在同一条链上

花费最多\(2n-6\)次询问，找出除根以外的节点的父节点

思路

我们称根节点的所有子节点为开始节点，可以得到三个推论：

  1. 开始节点是连续的，即开始节点的编号为\([1, m]\)。

    假设其不连续，设不连续的那个点编号为\(x\)，则$p_x \in [1,x-1] \(，可知\)p_{x+1}=0\(，则\)p_{x+1}\lt p_{x}$，违反了性质2

  2. 每条链上的点随深度递增的。

  3. 综合上面两个性质，我们可以得出，同一深度的点，所在链开始节点小的点的编号小于开始节点大的点的编号

据此，我们可以很轻易的想出询问方式。

首先枚举\(2\sim n-1\)与\(1\)一起进行询问，如果得到的是\(1\)说明该点也是开始节点。如果询问\(1,m\)得到的是\(0\)，说明开始节点为\([1,m-1]\)，且由推论3可得\(p_m=1\)。

接着我们使用类似\(\text{bfs}\)的思路枚举剩下的节点\(i\in[m+1,n-1]\)，我们设\(i\)可能的父节点为\(j\)，\(j\)初始为2。如果询问\(i,j\)得到的是\(0\)，说明\(p_i=j\)，\(i\)和\(j\)都要加一，因为一个节点最多只能由一个子节点，否则\(j\)加一。

代码实现

int query(int a, int b)
{
    printf("? %d %d\n", a, b);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}

void answer(const vector<int> &v)
{
    printf("!");
    for (int i = 1; i < v.size(); i++)
    {
        printf(" %d", v[i]);
    }
    printf("\n");
    fflush(stdout);
}
void solve()
{
    int n;
    scanf("%d", &n);
    vector<int> p(n);
    int i = 1;
    int m = 2;
    while (query(1, m))
    {
        p[m] = 0;
        m++;
    }
    p[m] = 1;
    int j = 2;
    for (int i = m + 1; i < n; i++)
    {
        while (query(i, j))
        {
            j++;
        }
        p[i] = j++;
    }
    answer(p);
}

这场掉大分。

B 题卡了好久，

C 题忘记考虑最小值只有一个的情况，连wa五发，

D 一开始没看太明白题意，先去看E了

E 一开始以为是高斯消元求解线性方程组，设每个位置的操作次数都为\(x_i\)，每个位置的值则为\(T=x_{i-1} +x_i*2+ x_{i+1} +a_i\)，然后按这个思路搞了半天，突然发现时间复杂度不对。然后就一直在找快速求稀疏矩阵的方法，没找到。赛后才发现不是求解线性方程组。

今天的题图就选铃兰妈了，庆祝一下送的十连出了忍冬

标签：typedef,开关,题解,Codeforces,leq,测试用例,983,include,节点
From： https://www.cnblogs.com/extractstars/p/18521568

相关文章

  • SP30785 ADAAPPLE - Ada and Apple 题解
    洛谷题目传送门博客园可能食用更佳题目大意：给定一棵权值为\(0\)或\(1\)的树，\(n\)个点，\(q\)次操作：0i把结点\(i\)的权值取反；1ij询问点\(i\)到点\(j\)的最短路径上权值是否全为\(0\)或全为\(1\)。题目分析：树上操作，看了下操作发现是树剖板子题。开......
  • P5298 Minimax 题解
    传送门小\(C\)有一棵\(n\)个结点的有根树，根是\(1\)号结点，且每个结点最多有两个子结点。定义结点\(x\)的权值为：1.若\(x\)没有子结点，那么它的权值会在输入里给出，保证这类点中每个结点的权值互不相同。2.若\(x\)有子结点，那么它的权值有\(p_x\)的概率是它的子结点......
  • AT_utpc2012_07 k番目の文字列 题解
    模拟赛搬了这个题，来写个题解。\(n\)这么小，不是状压就是很多很多维DP（暴论）。状压我没想出来，那就正常DP。考虑依次填入字符串的每个位置，记\(f(i,j,num,op)\)表示填了前\(i\)个位置，其中比\(s_0\)小的有\(j\)个，目前字典序比\(s\)小的子串有\(num\)个的方案数，\(op\)表......
  • 天津大学2024华为杯I.个大的大个 题解
    原题链接https://acm.tju.edu.cn/problem/P2040学校oj好像挂了，题解发不出去，又没有草稿功能，所以先存在这里了。前言华为杯时候对字符串不太熟，加上看错题了导致没做出这题，很可惜，苦练几个月，现在已经成为串串大师，回过头来秒一下这题发个题解泄恨。题意给定一个长为\(n\)的字符......
  • 2024御网线上Pwn方向题解
    ASMChecksec检查保护基本上保护都关闭了64位ida逆向程序只有一段，并且返回地址就是输入的数据，看起来就是srop了，找一下可以用的gadget通过异或清空rax值，然后通过异或ecx和1，异或rax和rcx即可增加rax的值，同理左移一位同样可以增加rax的值，将rax增加到0xf然后打srop，程序还给出了......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\)，定义数组的\(range\)是最大值减最小值，即极差。给出两个值\(a\)和\(b\)，每步操作中，可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后（可以是\(0\)步），极差的最小值。思路（要直接看答案可以跳......
  • Codeforces Round 982 (Div. 2)解题报告
    CodeforcesRound982(Div.2)解题报告A显然答案不会小于\(2(\maxw+\maxh)\)。构造方案学习样例一，挺明显的。B有个小性质（好像没用）：一旦能通过操作变成non-increasing，再对整个序列操作一次必然变为同一个数字。我们把一开始remove的数字记为A类，通过操作删掉的记为B类......
  • 第八届御网杯线下赛Pwn方向题解
    由于最近比赛有点多，而且赶上招新，导致原本应该及时总结的比赛搁置了，总结来说还是得多练，因为时间很短像这种线下赛，一般只有几个小时，所以思路一定要清晰，我还是经验太少了，导致比赛力不从心，先鸽了~Skillchecksec检查保护（没有开PIE和Canary）ida逆向分析一下不同的选项对应不同的功......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\)，\(s_{i,j}\in[1,9]\cup\{+,*\}\)，从\((1,1)\)开始，仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径，求所有合法路径对应的表达式的运算结果之和，答案对\(998244353\)取模。部分分44pts爆搜，枚举路径，......
  • 2024 -- 国庆集训 -- 临沂四中 -- 10月01 日 -- S/N模拟赛#1 题解
    A.2025--[炼石计划--NOIP模拟三]--T1--矩形赛时草了个\(O(n^4\log(n))\)竟然能过70分虽然本来就是这么分配的，发现正解只需将二分改为双指针就可以了，最气的是上面计算的时候用到还是尺取下面就用的二分（唐诗）。其实这题就是暴力，然后在低级的暴力上加一些操作变得稍微高级一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99