可分解的正整数

P12132 [蓝桥杯 2025 省 B] 可分解的正整数

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件：

  1. 序列长度至少为 $3$。
  2. 序列中的数字是连续递增的整数（即相邻元素之差为 $1$），可以包括正整数、负整数或 $0$。

例如，$[1, 2, 3]$、$[4, 5, 6, 7]$ 和 $[−1, 0, 1]$ 是符合条件的序列，而 $[1, 2]$（长度不足）和 $[1, 2, 4]$（不连续）不符合要求。

现给定一组包含 $N$ 个正整数的数据 $A_1, A_2, \dots , A_N$。如果某个 $A_i$ 能够表示为符合上述条件的连续整数序列中所有元素的和，则称 $A_i$ 是可分解的。

请你统计这组数据中可分解的正整数的数量。

输入格式

输入的第一行包含一个正整数 $N$，表示数据的个数。

第二行包含 $N$ 个正整数 $A_1, A_2, \dots , A_N$，表示需要判断是否可分解的正整数序列。

输出格式

输出一个整数，表示给定数据中可分解的正整数的数量。

输入输出样例 #1

输入 #1

3
3 6 15

输出 #1

3

说明/提示

样例说明

所以可分解的正整数的数量为 $3$。

评测用例规模与约定

思路:想到可以引入负数那么貌似什么正整数都可以凑除来，但是题目除了要求连续，还要至少3个以上的连续，所以1是不能凑出来的，因为0不能选两次。

代码:

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/

void solve()
{
    ll n;
    cin >> n;
    vll a(n + 1, 0);
    rep(i, 1, n) cin >> a[i];
    ll ans = 0;
    rep(i, 1, n)
    {
        if (a[i] > 1)
        {
            ans++;
        }
    }
    cout << ans << endl;
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

产值调整

P12133 [蓝桥杯 2025 省 B] 产值调整

题目描述

偏远的小镇上，三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 $A$、$B$ 和 $C$ 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。

然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，将根据当前的产值 $A$、$B$、$C$，计算新产值：

  1. 金矿新产值：$A'=\lfloor \dfrac{B+C}{2} \rfloor$；
  2. 银矿新产值：$B'=\lfloor \dfrac{A+C}{2} \rfloor$；
  3. 铜矿新产值：$C'=\lfloor \dfrac{A+B}{2} \rfloor$；

其中，$\lfloor \rfloor$ 表示向下取整。例如，$\lfloor 3.7\rfloor = 3$，$\lfloor 5.2\rfloor = 5$。

计算出 $A'$、$B'$、$C'$ 后，同时更新：$A$ 变为 $A'$，$B$ 变为 $B'$，$C$ 变为 $C'$，作为下一年调整的基础。

三兄弟认为这个方法能平衡产值波动，于是计划连续执行 $K$ 次调整。现在，请你帮他们计算，经过 $K$ 次调整后，金矿、银矿和铜矿的产值分别是多少。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行包含四个整数 $A,B,C,K$，分别表示金矿、银矿和铜矿的初始产值，以及需要执行的调整次数。

输出格式

对于每个测试用例，输出一行，包含三个整数，表示经过 $K$ 次调整后金矿、银矿和铜矿的产值，用空格分隔。

输入输出样例 #1

输入 #1

2
10 20 30 1
5 5 5 3

输出 #1

25 20 15
5 5 5

说明/提示

评测用例规模与约定

思路：k的值太大，不能最原始的暴力跑完，我们要想着跳出，我们不难想到 当a=1,b=1,c=1的情况的时，再循环跑下去的结果都是一样，直接跳出就好了，我们弄一个值不会变化的特判跳出即可。
AC代码：

#include <bits/stdc++.h>
using namespace std;
//CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p<<1
#define rc p<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x)&(-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps=1e-5;
const int N = 1e5 + 10,M=2*N,K=26;
const ll MOD = 1e9 + 7,Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template<typename T> bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template<typename T> struct BIT1 { int n; vector<T> tr; BIT1(int n) : n(n), tr(n+1) {} void add(int x, T v) { for(;x<=n;x+=x&-x) tr[x]+=v; } T sum(int x) { T r=0; for(;x;x-=x&-x) r+=tr[x]; return r; } T range(int l, int r) { return sum(r)-sum(l-1); } };
template<typename T> struct BIT2 { int n,m; vector<vector<T>> t1,t2,t3,t4; BIT2(int n_=0,int m_=0) { init(n_,m_); } void init(int n_,int m_) { n=n_; m=m_; t1.assign(n+1,vector<T>(m+1,T{})); t2.assign(n+1,vector<T>(m+1,T{})); t3.assign(n+1,vector<T>(m+1,T{})); t4.assign(n+1,vector<T>(m+1,T{})); } void _add(int x,int y,const T& v) { for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=m;j+=j&-j) { t1[i][j]+=v; t2[i][j]+=v*x; t3[i][j]+=v*y; t4[i][j]+=v*x*y; } } void rangeAdd(int x1,int y1,int x2,int y2,const T& v) { _add(x1,y1,v); _add(x1,y2+1,-v); _add(x2+1,y1,-v); _add(x2+1,y2+1,v); } T prefixSum(int x,int y) { T r{}; for(int i=x;i>0;i-=i&-i) for(int j=y;j>0;j-=j&-j) r+=t1[i][j]*(x+1)*(y+1)-t2[i][j]*(y+1)-t3[i][j]*(x+1)+t4[i][j]; return r; } T rangeSum(int x1,int y1,int x2,int y2) { if(x1>x2||y1>y2) return T{}; return prefixSum(x2,y2)-prefixSum(x1-1,y2)-prefixSum(x2,y1-1)+prefixSum(x1-1,y1-1); } };
struct Random { mt19937_64 rng; Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {} ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); } ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); } bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); } template<typename T> void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); } };
ll qmi(ll a, ll b, ll p) { ll res = 1 % p; a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }
/*
  
*/
       
       
void solve() {
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    while (k--) {
        ll x = a, y = b, z = c;
        a = (y + z) / 2;
        b = (x + z) / 2;
        c = (x + y) / 2;
        if (a == x && b == y && c == z) break; 
    }
    cout << a << " " << b << " " << c << endl;
}

int main()
{
     IOS; 
        
    int _ = 1;
    cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

画展布置

P12134 [蓝桥杯 2025 省 B] 画展布置

题目描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 $N$ 幅画作，其艺术价值分别为 $A_1, A_2, \dots , A_N$。他们需要从这 $N$ 幅画中挑选 $M$ 幅，并按照一定顺序布置在展厅的 $M$ 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。

为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 $M$ 幅画，应使艺术价值的变化程度通过一个数值 $L$ 来衡量，且该值越小越好。数值 $L$ 的定义为：

$$L=\sum_{i=1}^{M-1} |B_{i+1}^2-B_i^2|$$

其中 $B_i$ 表示展厅第 $i$ 个位置上画作的艺术价值。

现在，他们希望通过精心挑选和排列这 $M$ 幅画作，使 $L$ 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

输入格式

输入共两行。

第一行包含两个正整数 $N$ 和 $M$，分别表示画作的总数和需要挑选的画作数量。

第二行包含 $N$ 个正整数 $A_1, A_2, \dots , A_N$，表示每幅画作的艺术价值。

输出格式

输出一个整数，表示 $L$ 的最小值。

输入输出样例 #1

输入 #1

4 2
1 5 2 4

输出 #1

3

说明/提示

评测用例规模与约定

思路:我们看表达式容易想到，每一项带有绝对值，如果我们再取绝对值的时候能够把前面的项抵消，只剩下头和尾，好像是较优的，但是这要求具有连续性，我们从小到大排列，相邻的间距肯定是优于乱序的，最后我们从小到大，求尾的平方减去头的平方的最小值即可。
AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/

void solve()
{
    ll n, k;
    cin >> n >> k;
    vll a(n + 1, 0);
    rep(i, 1, n) cin >> a[i];
    sort_range(a, 1, n);
    ll ans = INF;
    rep(i, 1, n - k + 1)
    {
        ll now = a[i + k - 1] * a[i + k - 1] - a[i] * a[i];
        cmin(ans, now);
    }
    cout << ans << endl;
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

水质检测

P12135 [蓝桥杯 2025 省 B] 水质检测

题目描述

小明需要在一条 $2 \times n$ 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 $A$ 和 $B$ 连通，$B$ 和 $C$ 连通，那么 $A$ 和 $C$ 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

输入格式

输入共两行，表示一个 $2 \times n$ 的河床。

每行一个长度为 $n$ 的字符串，仅包含 # 和 .，其中 # 表示已经存在的检测器，. 表示空白。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

.##.....#
.#.#.#...

输出 #1

5

说明/提示

样例说明

其中一种方案：

.###....#
.#.######

增加了 5 个检测器。

评测用例规模与约定

对于 $100%$ 的评测用例，保证 $n \leq 1000000$。

思路:01bfs，我们找到最近的#和最远的#，从最近的到最远的，遇到#则花费为0，遇到.则花费为1，相当于填充的#的代码，我们走到目的地的时候我们就返回值即可。
AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e6 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

string g[2];
int dist[2][N];
int len, mi, ma;

int bfs(int x, int y)
{
    deque<PII> q;
    mem(dist, 0x3f);
    rep(i, 0, 1)
    {
        if (g[i][mi] == '#')
        {
            dist[i][mi] = 0;
            q.push_back({(int)i, mi});
        }
    }
    while (q.size())
    {
        auto [a, b] = q.front();
        q.pop_front();
        rep(i, 0, 3)
        {
            int nx = a + dx[i], ny = b + dy[i];
            if (nx < 0 || nx > 1 || ny < 0 || ny >= len)
                continue;
            int w = (g[nx][ny] == '.' ? 1 : 0);
            if (dist[nx][ny] > dist[a][b] + w)
            {
                dist[nx][ny] = dist[a][b] + w;
                if (w == 0)
                    q.push_front({nx, ny});
                else
                    q.push_back({nx, ny});
            }
        }
    }
    int res = inf;
    rep(i, 0, 1)
    {
        if (g[i][ma] == '#')
            cmin(res, dist[i][ma]);
    }
    return res;
}

void solve()
{
    cin >> g[0] >> g[1];
    len= g[0].size();
    mi = len, ma = -1;
    rep(i, 0, 1)
    {
        rep(j, 0, len - 1)
        {
            if (g[i][j] == '#')
            {
                cmin(mi, (int)j);
                cmax(ma, (int)j);
            }
        }
    }
    if (ma == -1 || mi == ma)
    {
        cout << 0 << endl;
        return;
    }
    cout << bfs(0, mi) << endl;
}

int main()
{
    IOS;
    int _ = 1;
    while (_--)
        solve();
    return 0;
}

生产车间

P12136 [蓝桥杯 2025 省 B] 生产车间

题目描述

小明正在改造一个生产车间的生产流水线。这个车间共有 $n$ 台设备，构成以 $1$ 为根结点的一棵树，结点 $i$ 有权值 $w_i$。其中叶节点的权值 $w_i$ 表示每单位时间将产出 $w_i$ 单位的材料并送往父结点，根结点的权值 $w_i$ 表示每单位时间内能打包多少单位成品，其他结点的权值 $w_i$ 表示每单位时间最多能加工 $w_i$ 单位的材料并送往父结点。

由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结点每单位时间内最多能打包多少单位的成品？

输入格式

输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格分开的正整数 $w_1,w_2, \dots,w_n$。

后面 $n - 1$ 行，每行两个整数表示树上的一条边连接的两个结点。

输出格式

输出共一行，一个整数代表答案。

输入输出样例 #1

输入 #1

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

输出 #1

8

说明/提示

样例说明

删掉结点 $4$、$9$ 后生产线满足条件，根结点 $1$ 每单位时间将打包出 $8$ 单位的成品。

评测用例规模与约定

思路:树形dp结合分组背包 个人感觉能在考场写出这个题目还挺难的。其实思路大多看了题目都有一些，主要是代码的实现。
AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e3 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/

int n, w[N];
int h[N], e[M], ne[M], idx;
bool can[N][N];//为 true 表示：结点 u 最终可以向父结点产出恰好 k 单位的流量

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int pa)
{
    int f[N];//当父结点的剩余容量为 j 时，能凑出的“最大流量和”是多少
    rep(i, 1, w[u])
    {
        f[i] = -1;
    }
    f[0] = 0;
    bool leaf = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == pa)
            continue;
        leaf = false;
        dfs(j, u);
        dep(k, w[u], 0)
        { // 体积
            rep(p, 0, w[u])
            { // 组内可能的值
                if (can[j][p] && k >= p && f[k - p] != -1)
                {
                    f[k] = max(f[k], f[k - p] + (int)p);
                }
            }
        }
    }
    if (leaf)
    {
        can[u][0] = true;
        can[u][w[u]] = true;
    }
    else
    {
        rep(j, 0, w[u])
        {
            if (f[j] == j)
            {
                can[u][j] = true;
            }
        }
        can[u][0] = true;
    }
}

void solve()
{
    mem(h, -1);
    mem(can, false);
    idx = 0;
    cin >> n;
    rep(i, 1, n) cin >> w[i];
    rep(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    dep(j, w[1], 0)
    {
        if (can[1][j])
        {
            cout << j << endl;
            return;
        }
    }
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

不会背包的看这个

装修报价

P12137 [蓝桥杯 2025 省 B] 装修报价

题目描述

老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 $N$ 项装修相关费用 $A_1, A_2, \dots , A_N$，系统便会根据这些费用生成最终的报价。

然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。

公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 $+$（加法）、$-$（减法）或 $\oplus$（异或）运算符，并按照特定优先级规则计算结果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。

为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。

现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你只需提供其对 $10^9+7$ 取余后的结果即可。

输入格式

第一行输入一个整数 $N$，表示装修相关费用的项数。

第二行输入 $N$ 个非负整数 $A_1, A_2, \dots , A_N$，表示各项费用。

输出格式

输出一个整数，表示所有可能的总和对 $10^9 + 7$ 取余后的结果。

输入输出样例 #1

输入 #1

3
0 2 5

输出 #1

11

说明/提示

对于输入样例中的三个数 $A = [0, 2, 5]$，所有可能的运算符组合共有 $9$ 种。计算结果如下：

$$0 \oplus 2 \oplus 5 = 7$$ $$0 \oplus 2 + 5 = 7$$ $$0 \oplus 2 - 5 = -3$$ $$0 + 2 \oplus 5 = 7$$ $$0 + 2 + 5 = 7$$ $$0 + 2 - 5 = -3$$ $$0 - 2 \oplus 5 = -7$$ $$0 - 2 + 5 = 3$$ $$0 - 2 - 5 = -7$$

所有结果的总和为：

$$7 + 7 + (-3) + 7 + 7 + (-3) + (-7) + 3 + (-7) = 11$$

$11$ 对 $10^9 + 7$ 取余后的值依然为 $11$，因此，输出结果为 $11$。

评测用例规模与约定

思路:想数学题目，我们容易想到+ - ^ 可以放在前面的n-1个空格之中，很多情况我们可以抵消+-的贡献，我们不妨算出每个符号的贡献，最后加在一起得出结论，也可以归纳法。
AC代码：

#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
    int n;
    vector<T> tr;
    BIT1(int n) : n(n), tr(n + 1) {}
    void add(int x, T v)
    {
        for (; x <= n; x += x & -x)
            tr[x] += v;
    }
    T sum(int x)
    {
        T r = 0;
        for (; x; x -= x & -x)
            r += tr[x];
        return r;
    }
    T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
    int n, m;
    vector<vector<T>> t1, t2, t3, t4;
    BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
    void init(int n_, int m_)
    {
        n = n_;
        m = m_;
        t1.assign(n + 1, vector<T>(m + 1, T{}));
        t2.assign(n + 1, vector<T>(m + 1, T{}));
        t3.assign(n + 1, vector<T>(m + 1, T{}));
        t4.assign(n + 1, vector<T>(m + 1, T{}));
    }
    void _add(int x, int y, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
            {
                t1[i][j] += v;
                t2[i][j] += v * x;
                t3[i][j] += v * y;
                t4[i][j] += v * x * y;
            }
    }
    void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
    {
        _add(x1, y1, v);
        _add(x1, y2 + 1, -v);
        _add(x2 + 1, y1, -v);
        _add(x2 + 1, y2 + 1, v);
    }
    T prefixSum(int x, int y)
    {
        T r{};
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        return r;
    }
    T rangeSum(int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2)
            return T{};
        return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
    }
};
struct Random
{
    mt19937_64 rng;
    Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
    ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
    int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
    double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
    bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
    template <typename T>
    void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
    ll res = 1 % p;
    a %= p;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
/*

*/

void solve()
{
    ll n, a;
    cin >> n;

    cin >> a;
    ll ans = a % MOD;
    ll now = a;
    ll lt = 0;
    rep(i, 2, n)
    {
        cin >> a;
        lt = now;
        now ^= a;
        ans = (ans * 3) % MOD;
        ans = (ans - (lt % MOD) + MOD) % MOD;
        ans = (ans + (now % MOD)) % MOD;
    }

    cout << ans << endl;
}

int main()
{
    IOS;

    int _ = 1;
    // cin>>_;//如果是多组数据
    while (_--)
    {
        solve();
    }
    return 0;
}

感受:整套写下来考的算法并不多，大多考的是思维，省一要多少分我也不知道，至少今年赛时的表现不尽人意，原因的话感觉其一是审题问题，其二是思维太差，其三是算法学的太少，原理不够清楚，基础不扎实，而且不会造数据，分析不到位。