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;
}