A 电子带负电
题意简化
给定多组非负整数序列，对每组序列定义函数 $ f(l, r, L, R) $：
从序列的子区间 $ [l, r] $ 中，提取所有满足 $ L \leq a_i \leq R $ 的元素组成新序列 $ b $；若 $ b $ 非空，$ f $ 为 $ b $ 的最大子段和；否则 $ f = -\infty $。
需找出所有可能的 $ (l, r, L, R) $ 中 $ f $ 的最大值，以及能得到该最大值的不同 $ (l, r, L, R) $ 组合数量（结果对 $ 998244353 $ 取模）。
数据范围
- 测试用例数 $ T ： 1 \leq T \leq 10 $；
- 每组序列长度 $ n ： 1 \leq n \leq 2 \times 10^5 $；
- 序列元素 $ a_i ： 0 \leq a_i \leq n $；
- 输出：$ f $ 的最大值，以及达到最大值的参数组合数（模 $ 998244353 $）。
思路
注意到是子段和(连续)最大，且均为正数，因此找出，连续的大于0的最大子段和就行
若全部为0，那么值为0，方案数\((n+1)*(n+1)*(1+n)*n/2\)，l,r的组合有n(n+1)/2种，L,R的组合有（n+1)(n+1)种
否则全部为最大子段和即为全部和，方案数\((n-maxx+1)*(minn+n+1)*(minid*(n-maxid+1))\)，l可选minid种，r可选n-maxid+1种，L可选minn+n+1种,R可选n-maxx+1种，minn,maxx分别指序列种最小最大值，minid，maxid分别指最左或最右的非0值
点击查看代码
#include<bits/stdc++.h>using namespace std;
#define endl "\n"
const int maxn=3e5+10;
const int mod=998244353;
using ll=long long ;
ll n,k;
ll a[maxn];void solve(){cin>>n;bool book=0;ll minn=INT_MAX,minid;ll maxx=-1,maxid;for(int i=1;i<=n;++i){cin>>a[i];if(a[i]!=0) book=1;if(maxx<a[i]){maxx=a[i];}if(minn>a[i] && a[i]!=0){minn=a[i];}}for(int i=1;i<=n;++i){if(a[i]!=0){minid=i;break;}}for(int i=n;i>=1;--i){if(a[i]!=0){maxid=i;break;}}if(!book){cout<<0<<" ";cout<<((n+1)%mod*(n+1)%mod)%mod*(1+n)*n/2%mod<<endl;return ;}cout<<accumulate(a+1,a+1+n,0ll)<<" "<<(((n-maxx+1)%mod*(minn+n+1)%mod)%mod*((minid*(n-maxid+1))%mod)%mod)%mod<<endl;}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--){solve();} return 0;
} I 量子弹弓
简化题意
判断是否存在：
- 一棵连接 $ n $ 个星系的树 $ T $（用 $ n-1 $ 条虫洞通道连通）；
- 一个排列 $ a $（每个星系恰好出现一次的回路）；
使得对所有 $ i $，树 $ T $ 中 $ a_i $ 到 $ a_{(i \bmod n)+1} $ 的路径边数 $ \leq $ 星系 $ a_i $ 的量子弹弓强度 $ p_{a_i} $。
输入数据范围
- 测试用例组数 $ T ： 1 \leq T \leq 10^6 $；
- 每组的星系数量 $ n ： 2 \leq n \leq 10^5 $，且所有组的 $ n 之和 \sum n \leq 10^6 $；
- 每个星系的量子弹弓强度 $ p_i ： 0 \leq p_i < n $（非负整数）。
思路
思维题
现在考虑树中任意一条边 $ e $（连接子树 $ A $ 和子树 $ B $）：
- 若回路要“经过”这条边，必然需要从 $ A $ 进入 $ B $（或从 $ B $ 进入 $ A $）。
- 但回路需要回到初始星系：假设初始星系在子树 $ A $，当路径从 $ A $ 经 $ e $ 进入 $ B $ 后，必须再从 $ B $ 经 $ e $ 返回 $ A $，否则无法回到初始星系所在的子树 $ A $。
因此，每条边至少需要被“去”和“回”各一次，即至少被经过两次。
反证法理解：设某条边仅被经过一次，那么但凡从这条边的某一侧进入另一侧后，就没有办法再回到原侧，无法形成点之间的回路。
回路：将整个序列之间的连接看成回路，总会从\(a_1\)出发到\(a_1\)结束，但由于是一棵树，本身没有环，于是形成了一个巨大的回路，每个边至少经过两次
所以\(\sum p_i \geq 2*n-2\)时 成立
注意p=0显然不成立
点击查看代码
#include<bits/stdc++.h>using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
using ll=long long;
#define x first
#define y second
#define endl "\n"
using pii=pair<ll,ll>;
const int maxn=5e3;
const ll inf=1e18;
int dx[] = {-1, 1, 0, 0, 0};
int dy[] = {0, 0, -1, 1, 0};ll mod=0;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f;
}
void print(ll x) {if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');return;
}
ll qpow(ll a,ll b,ll p) {a%=p;ll res=1;while(b) {if(b&1) res=res*a%p;b>>=1;a=(a*a)%p;}return res%p;
}
ll inv(ll a,ll p) {return qpow(a,p-2,p)%p;
}
inline ll lowbit(ll x) {return x&(-x);
}
inline ll gcd(ll a,ll b) {while(b) {ll c=b;b=a%b;a=c;}return a;
} ll lcm(ll a ,ll b) {return a*b/gcd(a,b);
}void solve() {ll n;n=read();vector<ll>a(n+1);bool book=0;ll sum=0;for(int i=1;i<=n;++i) {a[i]=read();if(a[i]==0) book=1;sum+=a[i];}if(book || sum<2*n-2){puts("NO");return ;}puts("YES");return ;}
int main() {ll _=1;
// ios::sync_with_stdio(0);
// cin.tie(nullptr);_=read();
// init();while(_--) {solve();}return 0;
}
H 回忆与展望
简化题意
给定 $ n $ 个回忆的“美好度” $ a_1, a_2, \dots, a_n $，以及三个整数 $ x, y, z $（满足 $ x \geq y \geq z $）。需确定一个 $ [1,n] $ 的排列 $ p $（规定 $ p_0 = 0 $），按顺序 $ p_1, p_2, \dots, p_n $ 遍历回忆时，根据相邻回忆的美好度关系计算“展望程度”：
- 若 $ a_{p_i} > a_{p_{i-1}} $，展望程度加 $ x $；
- 若 $ a_{p_i} = a_{p_{i-1}} $，展望程度加 $ y $；
- 若 $ a_{p_i} < a_{p_{i-1}} $，展望程度加 $ z $；
求最大的总展望程度。
数据范围
- 测试用例组数 $ T ： 1 \leq T \leq 100 $；
- 每组回忆数量 $ n $：所有测试用例的 $ n $ 之和 $ \leq 5 \times 10^6 $；
- 参数 $ x, y, z ： 1 \leq z \leq y \leq x \leq 5 \times 10^6 $；
- 美好度 $ a_i ： 1 \leq a_i \leq n $。
思路
拿着题目下意识想到贪心，但是需要注意到一点如果直接构造下降序列，也许没有一增一减更优
所以我们尝试枚举i，表示有i个上升子序列，那么此时必然有i-1个下降不等式，至于相等的个数，因为要将美好度都分散到不同的子序列中，所以只有大于出现次数i的美好度（出现x次）能贡献(x-i）次
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;const int MAXN = 5001000;
int cnt[MAXN]; // cnt[a]：美好度a出现的次数
int pcnt[MAXN]; // pcnt[k]：出现次数≥k的不同美好度的数量
int n;
ll x, y, z;void solve() {cin >> n >> x >> y >> z;// 初始化数组for (int i = 1; i <= n + 2; i++) {cnt[i] = 0;pcnt[i] = 0;}// 统计每个美好度的出现次数for (int i = 1; i <= n; i++) {int a;cin >> a;cnt[a]++; // 记录a出现的次数}// 统计“出现次数为k”的美好度有多少种for (int i = 1; i <= n + 1; i++) {pcnt[cnt[i]]++; // cnt[i]是i的出现次数，pcnt记录该次数的美好度数量}// 后缀和处理：pcnt[k]变为“出现次数≥k的美好度种类数量”for (int i = n; i >= 1; i--) {pcnt[i] += pcnt[i + 1];}ll ans = 0;int sm = n; // 初始化为总回忆数，用于计算“相等”相关的贡献// 遍历所有可能的分割点，计算最优组合for (int i = 1; i <= n + 1; i++) {sm -= pcnt[i]; // 更新“相等”贡献的基数//出现次数大于等于i的可以用来构造第i个递增序列 // 分解为三部分：递减次数、相等次数、递增次数int dec = i - 1; // 递减次数（权重z）int inc = n - sm - dec; // 递增次数（权重x）// 计算当前组合的总展望程度，取最大值ans = max(ans, dec * z + sm * y + inc * x);}cout << ans << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}