小抹爱锻炼
题目大意
给定 $ N $ 天的举重训练计划，需构造每天的训练次数序列 $ a_1, a_2, \dots, a_N $，满足：
- 单调不降（$ a_1 \leq a_2 \leq \dots \leq a_N $）；
- 每天不低于基础值（$ a_i \geq b_i $）；
- 每天不超过安全上限（$ a_i \leq c_i $）；
且 $ N $ 天的总训练次数（$ a_1 + a_2 + \dots + a_N $）恰好等于 $ M $。判断是否存在这样的序列。
数据范围
多组测试用例，每组输入：
- 两个整数 $ N $（天数）和 $ M $（总训练目标次数）；
- 长度为 $ N $ 的数组 $ b $（每天训练次数的下限，即每天至少练 $ b_i $ 次）；
- 长度为 $ N $ 的数组 $ c $（每天训练次数的上限，即每天至多练 $ c_i $ 次，且保证 $ b_i \leq c_i $）。
其中，测试用例数 $ T \leq 10^4 $，每组 $ N \leq 10^6 、 M \leq 10^9 $，且所有测试用例的 $ N $ 之和不超过 $ 10^6 $。
思路
签到题，思路很简单，分别求出最大上限序列和最小下限序列，如果存在交叉则说明不存在，否则满足
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve() {ll n, m;cin >> n >> m;vector<ll> b(n), c(n), d(n), e(n);for (ll i = 0; i < n; i++) {cin >> b[i];}for (ll i = 0; i < n; i++) {cin >> c[i];}for (ll i = 0; i < n; i++) {d[i] = b[i];if (i > 0 && d[i] < d[i - 1]) {d[i] = d[i - 1];}}for (ll i = n - 1; i >= 0; i--) {e[i] = c[i];if (i < n - 1 && e[i] > e[i + 1]) {e[i] = e[i + 1];}}ll x = 0, y = 0;for (ll i = 0; i < n; i++) {if (d[i] > e[i]) {cout << "NO\n";return;}x += d[i];y += e[i];}if (x <= m && y >= m) {cout << "YES\n";} else {cout << "NO\n";}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}
性质不同的数字
题目大意
多组测试用例，每组给定 $ n $ 个区间 \([l, r]\)。若两个整数 $ x \(、\) y $ 存在至少一个区间，使得一个在区间内、另一个不在，则二者“性质不同”。需计算每组最多能选出多少个两两性质不同的整数。
数据范围
- 第一行：整数 $ t \(（测试用例组数，\) 1 \leq t \leq 10^4 $）。
- 每组测试用例：
- 第一行：整数 $ n \(（区间数量，\) 0 \leq n \leq 2 \times 10^5 $）。
- 接下来 $ n $ 行：每行两个整数 $ l, r $（区间的左右端点，满足 $ 0 \leq l \leq r \leq 10^9 $）。
- 附加约束：所有测试用例的 $ n $ 之和不超过 $ 10^6 $。
思路
读懂题意，我们可以选取一些代表性的数字，来检验他们是否是不同的性质
怎么选取？
对于区间[l,r]，只需要选择l，r+1两个点，l代表了所有属于这个区间的点，r+1代表了所有不属于这个区间的点，但属于其他区间的点
怎么检验？
给每个区间赋予一个值，通过异或生成每个代表点的哈希值，每有一个新的哈希值对答案产生贡献
注意一点，如果刚好有区间r+1和其他区间l重合，需要更新哈希值后再检验
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using ll = unsigned long long ;
#define endl "\n"
const int maxn=2e5+10;
const ll mod=1e17;
using pii=pair<int,int>;
unordered_map<ll,ll>has;
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int cnt=0;
void solve() {ll n;cin >> n;vector<pair<ll, ll>> a;has.clear();cnt=0;for (ll i = 1; i<=n; i++) {ll l, r;cin >> l >> r;ll x=rng();a.push_back({l, x}); a.push_back({r+1, x}); }if (n == 0) {cout<<1<<endl;return ;}sort(a.begin(), a.end());ll val=0;ll ans=0,lx=-1;for(auto [x,y]:a){if(has[val]==0 && lx!=x ){++ans;has[val]=1;// cout<<val<<endl; }val^=y;lx=x;}if(has[0]==0) ++ans;cout<<ans<<endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}