目录
Codeforces Round 980 (Div. 2)
A
思路
推方程式即可, 勉强算贪心吧.
需要使得 \({a - x}\) 最小, 那么 \(x\) 就需要最小, 而满足题目条件, 需要
- \(a - x \ge b - 2x\)
得出\(x \ge b - a\), 又因为需要\(a\)最大, 所以\(x = b - a\), $ans = b-x = 2a-b $.
但是要注意, 如果\(a\)已经大于\(b\), 或者\(a\)无法满足营利, 要输出对应结果.
## 代码
void func(void)
{
int a,b;
cin >> a >> b;
if(a >= b) cout << a << '\n';
else
{
int ans = (2*a - b);
cout << (ans >= 0 ? ans : 0) << '\n';
}
}
B
思路
因为只知道每组数目, 但不知道对应关系. 所以每次对不确定为 \(0\) 的按钮点击一次, 直到一次不出货.
那么可以用二分查找分界点, 也可以用桶模拟.
每次处理当前不确定为\(0\)的, 都减去\(min(a_i)\), 同时获得\(cnt_{(不确定为0总数)} \times (min(a_i) - 上次确定为0)\)瓶水, 次数加上获得水数\(+\)此次变为\(0\)个数, 因为确定他们变成\(0\)需要多一次操作.
wa原因
有一个式子没有删掉导致wa三发
void func(void)
{
int n,k;
cin >> n >> k;
map<int,int> cnt;
for(int i=0;i<n;++i)
{
int stp; cin >> stp;
cnt[stp] ++;
}
int stp = 0,lst = 0,times = 0;
for(auto &i : cnt)
{
if((n-stp)*(i.x - lst) >= k)
{
times += k+cnt[lst];
break;
}
else
{
k -= (n-stp)*(i.x - lst);
times += (n-stp)*(i.x - lst) + cnt[lst];
stp += i.y;
lst = i.x;
}
}
cout << times << '\n';
}
C
思路
抽象题
根据两个数中较小的排序, 然后则不受影响了.
当时赌根据两个数和排序还对了.
wa原因
赌根据第一个数排序, 实际应该根据较小数排序.
代码
void func(void)
{
int n;
cin >> n;
vector<PII> a(n);
for(auto &i : a) cin >> i.x >> i.y;
sort(a.begin(),a.end(),cmp);
for(auto &i : a) cout << i.x << ' ' << i.y << ' ';
cout << '\n';
}
D
思路
这题可以用最短路, 也可以线段树维护dp.
因为不记得最短路了, 所以用线段树维护dp.
这题纯粹模拟太难, 所以可以维护无法使用, 也就是skip的点, 使之最小. 然后用一段的前缀和减去被skip的点.
那么dp[i]就维护到dp[i]被skip的点的总值最小的路径的值.
对于每个点:
- 如果\(b_i > i\), 他可以向右移动. 获取更多的点.
- 如果\(b_i < i\), 他可以向左移动, 可以确定, 向左移动不如从这个点开始解题得分, 因为解题后只能继续解左边的点.
所以每个点只会从右边的一个点, 或者\(b_i\)的点移动而来.
又因为由右边移动而来不是被skip, 所以只需继承到此点的dp.
那么每个点\(i\)查询能到达\(i\)的点(\(j\))到\(i\)的区间内dp的最小值,
\(dp_i = dp_k + a_j(j \le k \le i-1)\).
对于区间最小值, 可以用线段树维护(st表无法修改)
只需维护单点修改和区间查询
未ac原因
思路不对, 想用朴素的递推或者dfs解答.
代码
#include<bits/stdc++.h>
#define Start cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define PII pair<int,int>
#define x first
#define y second
#define ull unsigned long long
#define int long long
using namespace std;
struct data
{
int x,y,z;
bool operator < (const data &i) const
{
return(x == i.x ? (y == i.y ? z < i.z : y < i.z) : x < i.x);
}
};
const int M = 1e18+7;
const int N = 4e5 + 10;
int n;
vector<int> t(N<<2);
void push_up(int p)
{
t[p] = min(t[p<<1],t[p<<1|1]);
}
void modity(int k,int z,int be=1,int ed=n,int p=1)
{
if(k == be && be == ed)
{
t[p] = z;
return ;
}
int mid = (be+ed) >> 1;
if(k <= mid) modity(k,z,be,mid,p<<1);
else modity(k,z,mid+1,ed,p<<1|1);
push_up(p);
}
int query(int l,int r,int be=1,int ed=n,int p=1)
{
if(l <= be && ed <= r) return t[p];
int mid = (be+ed) >> 1,res = M;
if(l <= mid) res = min(res,query(l,r,be,mid,p<<1));
if(mid+1 <= r) res = min(res,query(l,r,mid+1,ed,p<<1|1));
return res;
}
void func(void);
signed main(void)
{
Start;
int _ ; cin >> _;
while(_--) func();
return 0;
}
void func(void)
{
cin >> n;
vector<int> a(n+1),s(n+1),b(n+1);
vector<vector<int>> vis(n+1);
for(int i=1;i<=n;++i)
{
cin >> a[i];
s[i] = s[i-1] + a[i];
}
for(int i=1;i<=n;++i)
{
cin >> b[i];
if(b[i] > i) vis[b[i]].push_back(i);
}
// for(int i=0;i<=n;++i) dp[i] = M;
for(int i=0;i<=(n<<2)+10;++i) t[i] = M;
modity(1,0);
for(int i=2;i<=n;++i)
{
int dp = M;
for(auto &j : vis[i])
{
dp = min(dp,query(j,i-1)+a[j]);
}
modity(i,dp);
}
int ans = -M;
for(int i=1;i<=n;++i)
{
ans = max(ans,s[i] - query(i,i));
}
cout << ans << '\n';
}