A.蚂蚁上树
思维，树的遍历，排序
首先发现根节点的各个子树独立。那么我们就可以对于每一个子树单独计算，最后取最大值。
对于一棵子树，设表示第
个节点的深度，如果没有“不允许两只蚂蚁站在同一个非根结点上”的限制，
也表示到达根所需要的步数。
将一个子树里的全部存入
数组并排序。从
最小的节点开始往上走。对于某一个节点
（数组
中的第
个节点），若
，那么当
到达
这一子树的根时，节点
已经到达根；否则这一子树的根有蚂蚁正在经过，需要等节点
上的蚂蚁先走过去，
。
最后一只蚂蚁过去的时间就是整棵子树的答案，时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,ans = 0,cnt = 0;
cin >> n;
vector<ll> dep(n + 1),a;
vector<vector<ll>> edge(n + 1);
for(int i = 1;i < n;i++){
ll u,v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
auto dfs = [&](auto& self,ll p,ll f) -> void{
dep[p] = dep[f] + 1;
if(edge[p].size() == 1 && p != 1) a.push_back(dep[p]);
for(auto v : edge[p]){
if(v == f) continue;
self(self,v,p);
}
};
dep[1] = 0;
for(auto i : edge[1]){
a.clear();
dfs(dfs,i,1);
sort(a.begin(),a.end());
cnt = 0;
for(int i = 1;i < a.size();i++){
a[i] = max(a[i],a[i - 1] + 1);
}
ans = max(ans,a.back());
}
cout << ans << "\n";
return 0;
}
B.奶龙大战贝利亚
博弈论，nim博弈
将每行 当作
，
当作
，然后把这个
串当作一个
位的二进制数，则该问题转换为一个nim博弈问题。则将每行异或起来，如果为0则后手必胜，否则先手必胜。
证明： 记该行二进制串所表示的数为，
表示该二进制串第
位。
记所有操作的集合为，根据每个选择最高位把
可分为
个子集
，由于
，则有
。
，设
表示最高位为
的子集。若
，则有
；
若
，对于
的所有可能操作数为
， 由于所给操作是一个异或的操作，所以这
个操作的结果两两不同，此时
。
综上，
，即
，并且由于操作结果最小为
,最大为
，所以该操作
可以取遍
。所以所给操作就等价于任选
，然后将
。如此该问题题与nim博弈等价。
时间复杂度.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin >> n >> m;
string chess;
vector<int> col(m + 1);
for(int i = 0;i < n;i++){
cin >> chess;
for(int j = 0;j < m;j++){
col[j] ^= (chess[j] == 'B');
}
}
for(int i = 0;i < m;i++){
if(col[i] == 1){
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
C.我是奶龙
数学，思维
假设黄色奶龙有只，蓝色奶龙有
只，红色奶龙有
只。
若要最终转换成一种颜色，那么最后一步一定是相同数量的两种颜色相遇转换成第三种颜色。
那么这里我们要让黄色与蓝色的数量尽可能的相等;
首先，我们让黄色与红色相碰只，然后蓝色就有
只了，黄色
;
然后我们蓝色与红色相碰只，那么
,
;
;
因为要使黄色与蓝色的只数相等，那么最后得到 ；
所以，即只要初始有两个数量差值为
的倍数即有解。
单组数据时间复杂度,总时间复杂度
。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--){
ll a,b,c;
cin >> a >> b >> c;
a %= 3,b %= 3,c %= 3;
if(a == b || a == c || b == c) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
D.多米诺骨牌
前缀和，差分
显然，如果想让所有多米诺骨牌都倒下，那么坐标轴上上每个点都被一个多米诺骨牌覆盖，所以如果不能让所有骨牌倒下，那么要修改的数量就是
中未被覆盖的数量。
我们可以先开桶或者统计坐标为
位置垒了高
的多米诺骨牌，那么该位置的多米诺就可以覆盖
，就将该区间每个位置上的计数
，区间加可以用差分数组实现。
对于查询，每次将位置的骨牌放到
，可以先将
位置上的计数
，
位置上的计数
，通过
来维护有多少位置计数为
，便可以
的处理每次查询。
时间复杂度.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,q,ans = 0;
cin >> n >> q;
vector<ll> a(n + 1),high(n + 1),cnt(n + 2);
for(int i = 1;i <= n;i++){
cin >> a[i];
high[a[i]]++;
}
for(int i = 1;i <= n;i++){
cnt[max(i - high[i] + 1,0LL)]++;
cnt[i + 1]--;
}
for(int i = 1;i <= n;i++){
cnt[i] += cnt[i - 1];
if(cnt[i] == 0) ans++;
}
while(q--){
ll x,y;
cin >> x >> y;
if(a[x] - high[a[x]] + 1 > 0 && cnt[a[x] - high[a[x]] + 1]-- == 1) ans++;
high[a[x]]--;
if(y - high[y] > 0 && cnt[y - high[y]]++ == 0) ans--;
high[y]++;
a[x] = y;
cout << ans << "\n";
}
return 0;
}
E.找出猫猫虫
思维
对于第一问，根据题目条件，可以得到如下不等式：
直接计算，即可判断
是否可能等于 0。
对于第二问，考虑先假设 ，此时
。然后，考虑贪心，给每个数依次减去其减去后使得
的能减去的最大值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n;
cin >> n;
vector<ll> l(n + 1),r(n + 1);
ll mi = 0,ma = 0;
for(int i = 1;i <= n;i++){
cin >> l[i] >> r[i];
mi += l[i],ma += r[i];
}
if(mi <= 0 && ma >= 0){
cout << "Yes\n";
ll s = 0,cnt = -mi,temp;
for(int i = 1;i <= n;i++){
temp = 0;
if(cnt > 0){
temp = min(cnt,r[i] - l[i]);
cnt -= temp;
}
cout << l[i] + temp << " ";
}
cout << "\n";
}
else cout << "No\n";
return 0;
}
F.点灯
二分图最大匹配，匈牙利算法，网络流
称横向每一段黑色格子的右边线为横墙，竖向每一段黑色格子左边线为竖墙。每一个灯泡都对应唯一一段横墙和竖墙。为了使得两个灯泡不互相照亮，每一个横墙或竖墙都得唯一对应一个灯泡。将每一段白色格子所对应横墙和竖墙连一条边，问题就转化成了二分图最大匹配问题。
时间复杂度，其中
代表图中节点的数量，
代表边的数量。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,m;
cin >> n >> m;
vector<vector<ll>> edge(n * m * 2 + 1),board(n + 1,vector<ll>(m + 1));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> board[i][j];
}
}
vector<ll> up(m + 1),fri(n * m * 2 + 1,-1),vis(n * m * 2 + 1,-1);
for(int i = 1;i <= m;i++) up[i] = n * m + i - 1;
for(int i = 1;i <= n;i++){
ll left = m * (i - 1);
for(int j = 1;j <= m;j++){
if(board[i][j]){
left = (i - 1) * m + j;
up[j] = n * m + i * m + j - 1;
}
else edge[left].push_back(up[j]);
}
}
auto match = [&](auto& self,ll x,ll t)->bool{
if(vis[x] == t) return false;
vis[x] = t;
for(auto v : edge[x]){
if(fri[v] == -1 || self(self,fri[v],t)){
fri[v] = x;
return true;
}
}
return false;
};
ll ans = 0;
for(int i = 0;i <= n * m;i++){
if(match(match,i,i)) ans++;
}
cout << ans << '\n';
return 0;
}
G.俄罗斯方块
思维，分类讨论
显然拼成高的矩形有五种基本图形。第一种是单独一个
型组成一个
的矩形；第二种是两个
型的组成一个
的矩形；第三种是两个
型的组成一个
的矩形；第四种是两个
型的组成一个
的矩形；第五种是
型、
型和
型各一个组成
的矩形，并且该图形最多只出现一次。
所以只会有两种情况。第一种情况是有第五种图形答案，
；
第二种情况是没有第五种图案，
.
答案为，时间复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a[7],ans1 = 0,ans2 = 0;
for(int i = 0;i < 7;i++) cin >> a[i];
if(a[0] && a[3] && a[4])
ans1 = (a[0] - 1) / 2 * 2 + (a[3] - 1) / 2 * 2 + (a[4] - 1) / 2 * 2 + a[1] + 3;
else
ans1 = a[1];
ans2 = a[0] / 2 * 2 + a[3] / 2 * 2 + a[4] / 2 * 2 + a[1];
cout << max(ans1,ans2) << "\n";
return 0;
}
H.super big cup
线段树，概率论
对于单独一个元素，考虑一次操作的影响是什么：显然它有的概率被修改为
，
的概率不变。
所以其期望值的变化为。
由于操作的是一个区间，可以用线段树来维护区间加区间乘。时间复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll qpow(ll a,ll b){
if(b == 0) return 1;
ll temp = qpow(a,b / 2);
temp = (temp * temp) % mod;
if(b & 1LL) temp = (temp * a) % mod;
return temp;
}
ll inv(ll a){
return qpow(a,mod - 2);
}
struct SegmentTree{
ll n;
struct node{
ll date = 0;
ll add = 0;
ll mu = 1;
};
vector<node> tr;
SegmentTree(vector<ll>& nums){
n = nums.size() - 1;
tr.resize(n * 4 + 10);
build(1,n,1,nums);
}
void push_up(ll p){
tr[p].date = (tr[p << 1].date + tr[(p << 1) | 1].date) % mod;
}
void f(ll p,ll l,ll r,ll x,ll k){
tr[p].date = (tr[p].date * k % mod + x * (r - l + 1)) % mod;
tr[p].mu = (tr[p].mu * k) % mod;
tr[p].add = (tr[p].add * k % mod + x) % mod;
}
void push_down(ll p,ll l,ll r){
ll mid = (l + r) >> 1LL;
f(p << 1,l,mid,tr[p].add,tr[p].mu);
f(p << 1 | 1,mid + 1,r,tr[p].add,tr[p].mu);
tr[p].add = 0,tr[p].mu = 1;
}
void build(ll l,ll r,ll p,vector<ll>& nums){
if(l == r){
tr[p].date = nums[l];
return;
}
ll m = l + ((r - l) >> 1);
build(l,m,p << 1,nums),build(m + 1,r,(p << 1) | 1,nums);
push_up(p);
}
//x is add,k is mul
void update(ll l,ll r,ll s,ll t,ll p,ll x,ll k){
if(l <= s && t <= r){
f(p,s,t,x,k);
return;
}
push_down(p,s,t);
ll m = s + ((t - s) >> 1);
if(l <= m) update(l,r,s,m,p << 1,x,k);
if(r > m) update(l,r,m + 1,t,(p << 1) | 1,x,k);
push_up(p);
}
ll query(ll l,ll r,ll s,ll t,ll p){
if(l <= s && t <= r) return tr[p].date;
push_down(p,s,t);
ll m = s + ((t - s) >> 1);
ll sum = 0;
if(l <= m) sum = query(l,r,s,m,p << 1);
if(r > m) sum = (sum + query(l,r,m + 1,t,(p << 1) | 1)) % mod;
return sum;
}
void RangeMul(ll l,ll r,ll x){
update(l,r,1,n,1,0,x);
}
void RangeAdd(ll l,ll r,ll x){
update(l,r,1,n,1,x,1);
}
ll query(ll l,ll r){
return query(l,r,1,n,1);
}
};
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,m;
cin >> n >> m;
vector<ll> a(n + 1);
for(int i = 1;i <= n;i++){
cin >> a[i];
}
SegmentTree tr(a);
while(m--){
ll l,r,x;
cin >> l >> r >> x;
tr.RangeMul(l,r,((r - l) * inv(r - l + 1)) % mod);
tr.RangeAdd(l,r,(x * inv(r - l + 1)) % mod);
}
for(int i = 1;i <= n;i++){
cout << tr.query(i,i) << " ";
}
return 0;
}
I.DeepSeek
二分，前缀和
题目是deepseek出的，题解也得是DeepSeek来写：
要解决这个问题，我们需要确定在给定数量的队员情况下，最多能完成多少个题目。每个题目需要一定数量的队员协作完成，且同一时间每个队员只能参与一个题目。通过排序和前缀和预处理，我们可以高效地回答每个查询。
方法思路
-
排序题目需求：将每个题目所需的队员数量按从小到大排序。这样可以优先处理需要较少队员的题目。
-
前缀和预处理：计算排序后的题目需求的前缀和数组。前缀和数组的第
个元素表示前
-
二分查找：对于每个查询，使用二分查找在前缀和数组中找到最大可完成的题目数，使得总队员数不超过给定值。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> R(n);
for (int i = 0; i < n; ++i) {
cin >> R[i];
}
sort(R.begin(), R.end());
vector<long long> sum(n + 1, 0);
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + R[i - 1];
}
while (q--) {
long long x;
cin >> x;
auto it = upper_bound(sum.begin(), sum.end(), x);
cout << (it - sum.begin() - 1) << '\n';
}
return 0;
}
J.湖工三宝
01背包，反悔贪心
显然，如果某写了一门课程的其中一项，那么其他两项一定也是要写的，所以三宝是一个整体，要么全都写，要么全不写。对于写哪些三宝最优有两种解法：
解法一 01背包
每个三宝可写可不写，这显然可以看作一个个物品，第
个物品价值为
，重量为
，容量为
。记
为前
项三宝，时间为
能达到的最优解，转移方程为:
，滚动数组优化：
，时间复杂度
。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,ans = 0,m = 0;
cin >> n;
vector<array<ll,2>> s(n + 1);
for(int i = 1;i <= n;i++){
ll a,b,c,t;
cin >> a >> b >> c >> t;
m = max(m,t);
s[i] = {t,a + b + c};
}
sort(s.begin() + 1,s.end());
vector<ll> dp(m + 1);
for(int i = 1;i <= n;i++){
ll t = s[i][0],w = s[i][1];
for(int j = t;j >= w;j--){
dp[j] = max(dp[j],dp[j - w] + 1);
ans = max(ans,dp[j]);
}
}
cout << ans << "\n";
return 0;
}
解法二 反悔贪心
按时间递增排序，遍历数组，尝试完成第门课的三宝。假如即没有超出截止时间，就记录答案，并将完成当前三宝所需时间放入大根堆中；假如超出截止时间并且堆顶的值比当前完成当前三宝所需时间更长，则反悔的将堆顶弹出，并将当前所需时间加入堆中。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,ans = 0,sum = 0;
cin >> n;
vector<array<ll,2>> s(n + 1);
for(int i = 1;i <= n;i++){
ll a,b,c,t;
cin >> a >> b >> c >> t;
s[i] = {t,a + b + c};
}
sort(s.begin() + 1,s.end());
priority_queue<ll> pq;
for(int i = 1;i <= n;i++){
if(sum + s[i][1] <= s[i][0]){
sum += s[i][1];
ans++;
pq.push(s[i][1]);
}
else{
if(!pq.empty() && pq.top() > s[i][1]){
sum += s[i][1] - pq.top();
pq.pop();
pq.push(s[i][1]);
}
}
}
cout << ans << '\n';
return 0;
}
K.在哪签到？
签到
解法一：
注意到要求输出一个高校的简称，显然直接输出HBUT即可；
解法二：
注意到该线路是：武昌火车站->华中科技大学站->街道口->省农科院->马房山->广埠屯->黄家湖->中医药大学站->沌阳大道->光谷广场->金融港北->黄龙山路->螃蟹岬->湖北大学站->北华街->江夏客厅->大花岭->湖工大。
则目的地所在高校是湖北工业大学，输出其简称HBUT。
L.帮帮Carson
模拟，枚举
直接枚举所有长为的子串表示数字
，然后计算|X - 754|取最小即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string str;
cin >> str;
ll ans = 1e5;
for(int i = 0;i + 2 < str.size();i++){
ll x = 0;
for(int j = 0;j < 3;j++){
x = x * 10 + str[j + i] - '0';
}
ans = min(ans,abs(x - 753));
}
cout << ans << '\n';
return 0;
}
M.奶龙农场的宝藏计算
思维
显然，我们就可以得到一个 的解法，如下：
由于 中会出现负数，我们稍微变一下式子可以得到：
但是这样显然还不够，于是我们可以 对 的枚举进行优化。容易想到预处理。
我们用一个中间变量 表示第二个括号里面的值。每次计算过答案以后，我们让
即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,ans = 0,las = 0;
cin >> n;
vector<ll> a(n + 1);
for(int i = 1;i <= n;i++){
cin >> a[i];
}
sort(a.begin() + 1,a.end());
for(int i = 1;i <= n;i++){
ans = (ans + (a[i] * (las + a[i])) % mod) % mod;
las = ((las * 2) % mod + a[i]) % mod;
}
cout << ans << "\n";
return 0;
}
京公网安备 11010502036488号