A

https://www.luogu.com.cn/problem/P16232

思路:找规律

(n+1)/2

B

思路:打表,找规律,bfs,阶乘逆元

来自B站up yeVegetable https://www.bilibili.com/video/BV1PzDkBsEzU/?spm_id_from=333.1391.0.0

打表找规律,很神奇,最后是个杨辉三角(遇到跟2有关的选项杨辉三角)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

void bfs(int n) {
    vector<int>s(n);
    queue <vector<int>>q;
    map<vector<int>,int>dis;
    q.push(s);
    dis[s] = 0;
	while (q.size()) {
		auto u = q.front();
		q.pop();
		for (int i = 0; i < n; i++) {
            auto v = u;
            if (dis[u] % 2 == 0) {
				for (int j = i; j < n; j++) v[j]^=1;
            }
			else for (int j = 0; j <= i; j++) v[j] ^= 1;
			if (!dis.count(v)) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	int ans = 0;
	for (auto& [v, d] : dis) {
		for (auto x : v)cout<<x<<" ";
		cout << endl;
		cout << "步数： " << d << endl;
		ans += d;
	}
	cout << "总步数" << ans << endl;
}

void solve()
{
	for (int i = 1; i <= 5; i++) {
		cout << "n = " << i << endl;
		bfs(i);
	}
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;//cin>>t;
    while (t--)solve();

    return 0;
}

n	操作数	(0- ∞ )操作数的个数
1	0 1	1 1
2	0 1 2 1	1 2 1
3	0 1 3 1 2 2 2 1	1 3 3 1
4	0 1 3 1 3 4 3 1 2 2 3 2 2 2 2 1	1 4 6 4 1
...	...	...

得出公式

$sum=\sum_{i=1}^n C^i_n*i$

然后n=2026求解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

ll fact[3000],inv[3000];
const int mod = 998244353;
ll fastpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

ll calc(int n, int m) {
	if (m > n)return 0;
	return fact[n] * inv[n - m] % mod * inv[m] % mod;
}

void solve()
{
	fact[0] = 1;
	for (int i = 1; i <= 2026; i++)fact[i] = fact[i - 1] * i % mod;
	inv[2026] = fastpow(fact[2026], mod - 2);
	for (int i = 2025; i >= 0; i--)inv[i] = inv[i + 1] * (i + 1) % mod;
	ll sum = 0;
	for (int i = 0; i <= 2026; i++) {
		sum = (sum + calc(2026, i)*i%mod) % mod;
	}
	cout << sum << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;//cin>>t;
    while (t--)solve();

    return 0;
}

C

https://www.luogu.com.cn/problem/P16234

思路:无

即序列元素都相同

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

void solve()
{
    ll n, x, y; cin >> n >> x >> y;
    if (x > y)cout << 0 << endl;
    else cout << y - x + 1 << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;cin>>t;
    while (t--)solve();

    return 0;
}

D

https://www.luogu.com.cn/problem/P16235

思路:数论

总和sum%5==0,队员的最大数量mx<=sum/5 证:if mx>sum/5,需要总人数mx*5>sum,不成立,所以mx<=sum/5

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl '\n'

void solve()
{
    ll n; cin >> n;
    ll maxx = -1, sum = 0;
    for (int i = 0; i < n; i++) {
        ll num; cin >> num;
        maxx = max(maxx, num);
        sum += num;
    }
    if (sum % 5 != 0 || maxx > sum / 5) {
        cout << "F" << endl;
    }
    else {
        cout << "T" << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1; cin >> t;
    while (t--)solve();

    return 0;
}

E

https://www.luogu.com.cn/problem/P16236

思路:枚举,前缀和

注意到在m个'?'里左边为'L'右边为'Q'永远是最优的,在m里枚举分界线的位置

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl '\n'

int l[100010], r[100010];
void solve()
{
	int n; cin >> n;
	string s; cin >> s;
	vector<int>pos;
	if (s[0] == '?')s[0] = 'L';
	if (s[0] == 'L')l[0] = 1;
	if (s[n - 1] == '?')s[n - 1] = 'Q';
	if (s[n - 1] == 'Q')r[n - 1] = 1;


	for (int i = 1; i < n; i++) {
		l[i] = l[i - 1];
		if (s[i] == 'L')l[i] += 1;
		else if (s[i] == '?') {
			pos.push_back(i);
			s[i] = 'Q';
		}
	}
	for (int i = n - 2; i >= 0; i--) {
		r[i] = r[i + 1];
		if (s[i] == 'Q')r[i] += 1;
	}
	ll res = 0, cntl = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'L')cntl++;
		else res += cntl;
	}
	ll ans = res;

	for (int i = 0; i < pos.size(); i++) {
		ans = max(ans, res += -l[pos[i]] + r[pos[i] + 1] - i);
	}//当前贡献res -(i左边原始'L'的个数)+(i右边'Q'的个数)-(修改增加的'L'的个数
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;//cin>>t;
	while (t--)solve();

	return 0;
}

F

https://www.luogu.com.cn/problem/P16237

思路:并查集

!!!!考虑有环,要用并查集求块的数量,未联通的联通块也要联通,所以是cnt+1个连通块需要cnt个跳线,计算cnt个跳线的度,用n个电脑去平摊,f=(2*cnt)/n,f>1,需要某块额外连一个块,0<f<1,保证一个块最多连一个块,f=0,只有一个块。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

int fa[100010];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }

void solve()
{
    int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)fa[i] = i;
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		int fa = find(a), fb = find(b);
		if (fa != fb) {
			merge(a, b);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)if (fa[i] == i)cnt++;
	cout << --cnt << " " << (2 * cnt + n - 1) / n << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;//cin>>t;
    while (t--)solve();

    return 0;
}

G

https://www.luogu.com.cn/problem/P16238

思路:最大字段和,前缀和

先求出差值c[i]数组,计算从1到该位置0个数的前缀和s[i],把差值相同的下标用 unordered_map<ll,vector<int>>存起来,遍历差值,求最大字段和ans,最后答案为=ans+总0的个数。复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

void solve()
{
	int n; cin >> n;
	vector<ll>a(n+1), b(n+1), c(n+1), s(n+1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++)c[i] = a[i] - b[i];
	int c0 = 0;
	unordered_map<ll, vector<int>>mp;
	for (int i = 1; i <= n; i++) {
		s[i] = s[i - 1] + (c[i] == 0);
		if (c[i] == 0)c0++;
		else mp[c[i]].push_back(i);
	}
	int ans = 0;
	for (auto& [k, v] : mp) {
		int dp = 1,mx = 1;//初始 就可以选择这一个端点变为合法
		for (int i = 1; i < v.size(); i++) {
			int l = v[i - 1], r = v[i];
			int cnt0 = s[r - 1] - s[l];
			dp = max(1, dp + 1 - cnt0);//字段和：加上当前端点，减去中间的0
			mx = max(mx, dp);
		}
		ans = max(ans, mx);
	}
	cout << ans + c0 << endl;//加上所有的0
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;//cin>>t;
    while (t--)solve();

    return 0;
}

H

https://www.luogu.com.cn/problem/P16239

思路:二分,优先队列

核心数学原理：边际收益我们要最大化乘积 $\prod (a_i + k_i b_i)$ 。假设我们当前已经分配了一些天数，现在多出 1 天，该给谁？给队员 $i$ ，乘积会变为原来的： $\frac{a_i + (k_i+1)b_i}{a_i + k_i b_i} = 1 + \frac{b_i}{a_i + k_i b_i}$ 为了让乘积增幅最大，我们要选择 $\frac{b_i}{a_i + k_i b_i}$ 最大的人。这等价于选择 $\frac{a_i + k_i b_i}{b_i}$ 最小的人。我们将这个值拆解： $\frac{a_i}{b_i} + k_i$ 。这就变成了一个“补短板”的问题：谁的“实力/天赋”比值（加上已训练天数）最小，我们就训练谁。
二分搜索：寻找“水位线”因为 $m$ 太大，不能一个个加。代码想象了一个“水位线” $p$ ：代码中 c[i] = a[i] / b[i] 是每个队员初始的“基础水位”。如果我们想让所有队员的“水位”至少达到 $p$ ，那么第 $i$ 名队员需要的训练天数 $k_i = p - c[i]$ （如果 $p > c[i]$ ）。chk(p) 函数：计算如果要达到水位 $p$ ，总共需要多少天。如果总天数 $\le m$ ，说明水位 $p$ 还可以更高。通过二分查找，代码找到了在 $m$ 天内能让所有人达到的最高整数水位 $l$ 。
处理余数：精细排序二分只能处理整数部分 c[i]，但实际的“水位”是 $\frac{a_i}{b_i} + k_i = \frac{\lfloor a_i/b_i \rfloor \cdot b_i + r_i}{b_i} + k_i$ 。即使整数部分相同，余数 $r_i$ 越小的人，其实际数值越小，也就越优先需要训练。排序逻辑（代码第 52-53 行）：比较两个人的“分数”： $\frac{r_x}{b_x}$ 和 $\frac{r_y}{b_y}$ 。代码通过 r[x] * b[y] < r[y] * b[x]（交叉相乘）来避免浮点误差。余数比例越小的人，在分配完基础天数后，优先获得额外的 1 天训练机会。
计算结果最后，根据二分出的水位 $p$ 和排序补齐的额外天数，算出每个队员最终的实力值 $v = a_i + k \cdot b_i$ ，累乘并取模得到答案。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull  unsigned long long
#define endl '\n'

const ll mod = 998244353;

void solve()
{
	int n; cin >> n;
    ll m; cin >> m;
    vector<ll> a(n), b(n), c(n), r(n);
	ll mx = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		if (b[i] > 0) {
			c[i] = a[i] / b[i]; // 实力比值
			r[i] = a[i] % b[i]; // 余数
			mx = max(mx, c[i]); // 记录最大实力比值，二分上界
		}
		else {// b[i]为0时，c[i]设为一个极大值，使其不参与二分补齐
			c[i] = 9e18;
		}
	}

    // 二分检测函数：达到比值 p 需要多少天
    auto check = [&](ll p) {
        ll s = 0;
        for (int i = 0; i < n; i++) {
            if (p > c[i]) {
                s += p - c[i];
                if (s > m) return s; // 防止累加溢出，提前退出
            }
        }
        return s;
    };

    // 1. 二分查找最大可以达到的整数比值 p
	ll l = 0, h = mx + m + 1;//上界为最大比值加上所有天数，保证足够大
    while (l < h) {
        ll mid = (l + h + 1) >> 1;
        if (check(mid) <= m) l = mid;
        else h = mid - 1;
    }

	ll p = l; // 最终比值
    ll used = check(p);
    ll rem = m - used; // 剩下的天数，每人最多再分1天

    // 2. 按余数比例 r/b 从小到大排序
    // 比例越小，说明在当前比值下其实际实力越弱，优先补齐
    vector<int> id;
    for (int i = 0; i < n; i++) {
        if (b[i] > 0 && c[i] <= p) {
            id.push_back(i);
        }
    }

    sort(id.begin(), id.end(), [&](int x, int y) {
        // 比较 r[x]/b[x] < r[y]/b[y] -> r[x]*b[y] < r[y]*b[x]
        return (ll)r[x] * b[y] < (ll)r[y] * b[x];
        });

    // 3. 分配额外的训练天数
    vector<int> ad(n, 0);
    for (int i = 0; i < id.size() && i < rem; i++) {
        ad[id[i]] = 1;
    }

    // 4. 计算最终结果
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        ll k = 0;//天数
        if (b[i] > 0 && p > c[i]) { // 跳过不增长的和已达标的
			k = p - c[i];//补齐到比值 p 需要的天数
        }
		if (ad[i]) k++; // 如果分配了额外天数，再加1
        // 最终实力 v = a + k*b
        ll v = (a[i] + k * b[i]%mod)%mod;
        ans = ans * v % mod;
    }

    cout << ans << endl;

}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;//cin>>t;
    while (t--)solve();

    return 0;
}

总结: 做题时想法很多,接近30%~80%,但是不能实际解决问题,在代码细节上还不熟练,代码从想法到实现不成熟; 目标评估:思维67% 实现50%,目前刷题200个,目标400个。

蓝桥杯17届B组c++

A