pts: 100 + 100 + 0 = 200
T1 ad
题目描述
给定 (N) 个数 (a_1, a_2 dots a_n)，现在对每个数都加 (K) 或者减 (K)，求操作操作之后的最大值减去最小值的差最小。
(1 leq N leq 10^5, 1 leq K, a_i leq 10^9)
solution
40pts:
(N leq 10)
直接 (2^N) 暴力枚举就好了。
100pts
不难发现答案一定可以为 (Max(a_i) - Min(a_i)), 也就是所有值的都加 (k) 或者都减 (k) 的情况。
然后预处理出两个数组，(a_i = num_i + k, b_i = num_i - k) 其中 (num_i) 是原数组。
然后就是用 (b) 数组中的某些数去替换 (a) 数组中的某些数。
然后你会惊奇的发现一定是从头往后依次替换掉 (a) 中的数一定是最优的，然后你只需要在替换过程中更新答案就好了。
code
/*
work by:Ariel_
Knowledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN], b[MAXN], num[MAXN], n, k, Ans;
signed main(){
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++){
scanf("%lld", &num[i]);
a[i] = num[i] - k, b[i] = num[i] + k;
}
sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
Ans = a[n] - a[1];
for (int i = 1; i < n; i++) {
Ans = min(Ans, max(b[i], a[n]) - min(b[1], a[i + 1]));
}
cout<<Ans;
system("pause");
return 0;
}
T2 cutter
题目大意
给你一个长为 (L) 的字符串，然后给你 (N) 个英文单词，现在给这个英文句子断句，要求断完句之后每一段都是一个英文单词，求断句的所有方案。
(Lleq 200, Nleq 30)
solution
设 (f_i) 表示字符串前 (i) 个字符断句的方案数。
转移就枚举最后一次断句的位置 (j)，只有 (j + 1 sim i) 这段是一个单词，并且 (f_j) 这个状态被更新过才能转移。这个 (hash) 就可以实现。
然后怎么统计方案呢？
深受昨晚牛客 A 题打击。
(dp) 时候，能转移状态的时候就从 (j) 向 (i) 连一条边，然后 (dfs) 输出所有的方案就好了。
code
/*
work by:Ariel_
Sorce:
Knowledge:
Time:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include<vector>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 210;
const int mod = 998244353;
const int seed = 30;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int f[MAXN], n, base[MAXN], _hash[MAXN];
char s[MAXN], t[MAXN];
map<int, bool>mp;
int get(char c) {return c - 'a' + 1;}
vector<int>vec[MAXN];
int tmp[MAXN], tot, L;
bool vis[MAXN], fag[MAXN][MAXN];
void dfs(int u, int tot) {
tmp[tot] = u;
if(u == L) {
for(int i = 1; i <= L; i++) {
cout<<s[i];
if(i != L) {
for (int j = 1; j <= tot; j++) {
if(tmp[j] == i) cout<<"_";
}
}
}
puts("");
return ;
}
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i];
dfs(v, tot + 1);
}
}
signed main(){
scanf("%s", s + 1);
L = strlen(s + 1);
for (int i = 1; i <= L; i++) _hash[i] = (_hash[i - 1] * seed % mod + get(s[i])) % mod;
n = read();
base[0] = 1;
for (int i = 1; i <= n; i++) base[i] = base[i - 1] * seed % mod;
for (int i = 1; i <= n; i++) {
scanf("%s", t + 1);
int Hash = 0, len = strlen(t + 1);
for (int j = 1; j <= len; j++) {
Hash = (Hash * seed % mod + get(t[j])) % mod;
}
mp[Hash] = 1;
}
f[0] = 1;
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= i; j++) {
if(f[j - 1]) {
int H = 0;
for (int k = j; k <= i; k++) H = (H * seed % mod + get(s[k])) % mod;
if(!mp[H]) continue;
f[i] = f[i] + f[j - 1];
vec[j - 1].push_back(i);
}
}
}
if(f[L] == 0) {return 0;}
dfs(0, 1);
return 0;
}
T3
题目大意
总共由 (N) 家商店排成一行，第 (i) 家商店的物价为 (v_i)。小葱购物从第 (a) 家商店走到第 (b) 家商店。在走的过程可以做下面事情的任意一件：
- 购买一件商品
- 卖出一件商品，要求这个时候小葱手上至少有一件商品才能卖出
- 路过啥也不干
(m) 次询问，每次有两种操作，修改某个商店的物价或者求出从 (a) 到 (b) 的最大收益。
假设它的本金无限，但是他只能带着一件商品，并且卖出的时候要保证手里面有商品。
(1 leq N, M leq 10^5, 1 leq a, b leq N, 1leq v_i, v leq 10^4)
solution
这题好像全网没有题解，所以还是写详细点吧。
30pts dp
对每次询问都 (dp) 一次。
设 (f_i) 表示到达第 (i) 商店的最大收益。
转移的时候就考虑当前是不动还是卖物品。不可能买物品，因为如果最后买了物品都卖不掉了。
啥也不干的话就是 (f_i = f_{i - 1})
如果要卖物品的话就要从前面找出一个能卖物品的最优状态，这个东西 (dp) 的时候顺便记录以下就好了。
(f_i = Max + val[i])
(Max = max(Max, f[i - 1] - val[i]))
从右向左走就是枚举顺序不同。
复杂度 (O(nm))
code
//if(opt == 1) work(l, r)
int work(int l, int r) {
memset(f, 0, sizeof f);
if(l <= r) {
int Max = -val[l];//找出前面可以卖东西的最优状态
for (int i = l + 1; i <= r; i++) {
f[i] = max(f[i - 1], Max + val[i]);
Max = max(Max, f[i - 1] - val[i]);
}
return f[r];
}
else {
swap(l, r);
int Max = -val[r];
for (int i = r - 1; i >= l; i--) {
f[i] = max(f[i + 1], Max + val[i]);
Max = max(Max, f[i + 1] - val[i]);
}
return f[l];
}
}
100pts
下面是 cgp 学长代码里面的注释：
价格是一个波动的序列，所以根据贪心的策略，要在最高点卖，最低点买，这样的差是最大的，所以用树状数组维护区间和，把一个区间里面那些最高点的和和最低点的相反数维护出来。
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n,m;
namespace PT1 {
const int N=100000+100;
int a[N],tree1[N],tree2[N],bz1[N],bz2[N],ma[N],nn;
int lowbit(int x) {
return x&-x;
}
void update(int *tree,int pos,int c) {
while(pos<=n) {
tree[pos]+=c;
pos+=lowbit(pos);
}
}
int query(int *tree,int pos) {
int ret=0;
while(pos) {
ret+=tree[pos];
pos-=lowbit(pos);
}
return ret;
}
void updatep_v(int i) {
if(i<=1||i>=n) return ;
int tmp=query(tree1,i)-query(tree1,i-1);
update(tree1,i,-tmp);
tmp=query(tree2,i)-query(tree2,i-1);
update(tree2,i,-tmp);
bz1[i]=0;
bz2[i]=0;
if(a[i]>a[i-1]&&a[i]>=a[i+1]) bz1[i]=1,update(tree1,i,a[i]);
if(a[i]<=a[i-1]&&a[i]<a[i+1]) bz1[i]=-1,update(tree1,i,-a[i]);
if(a[i]>=a[i-1]&&a[i]>a[i+1]) bz2[i]=1,update(tree2,i,a[i]);
if(a[i]<a[i-1]&&a[i]<=a[i+1]) bz2[i]=-1,update(tree2,i,-a[i]);
}
int main() {
for(int i=1; i<=n; ++i) a[i]=read();
for(int i=2; i<n; ++i) {
if(a[i]>a[i-1]&&a[i]>=a[i+1]) bz1[i]=1,update(tree1,i,a[i]);
if(a[i]<=a[i-1]&&a[i]<a[i+1]) bz1[i]=-1,update(tree1,i,-a[i]);
if(a[i]>=a[i-1]&&a[i]>a[i+1]) bz2[i]=1,update(tree2,i,a[i]);
if(a[i]<a[i-1]&&a[i]<=a[i+1]) bz2[i]=-1,update(tree2,i,-a[i]);
}
while(m--) {
int opt=read();
if(opt==1) {
int l=read(),r=read();
if(l==r) {
cout<<0<<'
';
continue;
}
int ans=0;
if(l<r) {
if(a[l]<a[l+1]) ans-=a[l];
if(a[r]>a[r-1]) ans+=a[r];
ans+=query(tree1,r-1)-query(tree1,l);
} else {
swap(l,r);
if(a[r]<a[r-1]) ans-=a[r];
if(a[l]>a[l+1]) ans+=a[l];
ans+=query(tree2,r-1)-query(tree2,l);
}
printf("%d
",ans);
} else {
int p=read(),w=read();
a[p]=w;
updatep_v(p-1),updatep_v(p),updatep_v(p+1);
}
}
return 0;
}
}
int main() {
n=read(),m=read();
PT1::main();//100pts
return 0;
}