QOJ 8777
题目描述
你有 \(P\) 页的护照,你要进行 \(N\) 次旅游。第 \(i\) 次旅游需要在连续 \(A_i\) 页没有盖章的护照上盖章。求最坏情况下你能进行几次旅游。
思路
我们枚举那一次不成功的旅游,考虑最坏情况:每一次盖章都和上一次盖章的末尾中间有 \(A_i-1\) 个空页,这样中间的空页就全都不能用。这样总共需要 \((i-1)\cdot (A_i-1)+\sum \limits_{j=1}^i A_j\) 页,如果这个 \(>P\),则输出 \(i-1\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100005;
int n;
ll p, a[MAXN];
__int128 sum[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> p;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for(int i = 1; i <= n; ++i) {
if((__int128)(a[i] - 1) * (i - 1) + sum[i] > p) {
cout << i - 1;
return 0;
}
}
cout << n;
return 0;
}
QOJ 8780
题目描述
有 \(N\) 道题,每道题都有实现,思维难度上限和下限,只有你的实现和思维能力都在范围之内才能解决这道题。每道能做的题你都可以选择跳过。每当你解决一道题就可以选择提升思维能力或实现能力。
给定你的初始实现和思维能力 \(S,T\) ,求你最多能解决多少道题。
思路
令 \(dp_{i,j,k}\) 表示考虑前 \(i\) 道题,实现和思维能力分别为 \(S+j,S+k\) 是否可能。很容易发现其解决题目数量 \(=j+k\)。由于只用记录是否可能,所以可以使用 bitset
优化。而空间用降维优化。
空间复杂度 \(O(\frac{N^2}{w})\),时间复杂度 \(O(\frac{N^3}{w})\),其中 \(w=32\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001;
int n, s, t, ans;
bitset<MAXN> dp[2][MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> s >> t;
dp[0][0][0] = 1;
for(int i = 1, sl, sr, tl, tr; i <= n; ++i) {
cin >> sl >> sr >> tl >> tr;
sl -= s, sr -= s, tl -= t, tr -= t;
sl = max(0, sl), sr = min(n, sr), tl = max(0, tl), tr = min(n, tr);
bitset<MAXN> b;
for(int j = tl; j <= tr; ++j) {
b[j] = 1;
}
for(int j = 0; j < i; ++j) {
dp[i & 1][j] |= dp[!(i & 1)][j];
}
for(int j = sl; j <= sr; ++j) {
dp[i & 1][j + 1] |= (dp[!(i & 1)][j] & b);
dp[i & 1][j] |= ((dp[!(i & 1)][j] & b) << 1);
}
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= n; ++j) {
if(dp[n & 1][i][j]) {
ans = max(ans, i + j);
}
}
}
cout << ans;
return 0;
}
标签:NAC,int,sr,tr,tl,MAXN,sl
From: https://www.cnblogs.com/yaosicheng124/p/18437591