Preface$
\(Rank36/43\)
\(20pts + 0pts + 50pts + 0pts = 70pts\)
\(\mathfrak{T1}\ 序列问题\)
一个\(cdq\)，我没学\(cdq\)，而且我连暴力\(dp\)都没打，因为我连暴力\(dp\)都不会
赛时想了两个小时，最后打了个爆搜。。太亏了。。。
赛后写了个暴力\(dp\)莫名有\(70pts\)，别人只有\(50pts\)，不清楚为什么
这个题最后我是暴力\(dp\)+骗分过的，因为数据过水，后面两个\(subtask\)只要统计\([i==a_i]\)的数目即可(这不是正解！！)
T1
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 500005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
int n, final_ans;
int a[N], w[N], f[N];
void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
{cin >> a[i]; w[i] = i - a[i];}
if (n >= 100000)
goto pianfen;
for (re i = 1 ; i <= n ; ++ i){
if (w[i] < 0)
continue;
f[i] = 1;
for (re j = 1 ; j <= i-1 ; ++ j){
if (w[j] < 0)
continue;
if (a[j] < a[i] and w[j] <= w[i])
f[i] = MAX(f[i], f[j] + 1);
}
}
for (re i = 1 ; i <= n ; ++ i)
if (w[i] >= 0)
final_ans = MAX(final_ans, f[i]);
cout << final_ans << '\n';
return ;
pianfen:{
for (re i = 1 ; i <= n ; ++ i)
if (w[i] == 0)
final_ans ++;
cout << final_ans << '\n';
}
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(sequence);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T2}\ 钱仓\)
比较智慧的贪心。
大胆猜想有一个点是一个分割点，分割点就是他之前的钱不会经过他顺时针运到他的后边。
暴力\(O(n)\)枚举这个点，再\(O(n)\)判断，可以获得\(64pts\)的好成绩。
考虑如何优化取点过程:分割点一定存在并且为最大子段和的起点。
这个嘛我不会证\(、、、\)
最大子段和我还是会求的，这玩意记忆尤深(我谢谢\(eafoo\))
T2
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define int long long
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
“比较智慧的贪心。”
*/
int n, st, ed, final_ans, L, R;
long long sum;
int a[N<<1], b[N<<1], q[N<<1];
void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
{cin >> a[i]; a[i+n] = a[i];}
for (re i = 1 ; i <= n ; ++ i){
sum += a[i]-1;
if (sum < 0)
st = i+1, sum = 0;
}
ed = st + n - 1, L = 0, R = -1;
for (re i = st ; i <= ed ; ++ i)
b[i] = a[i];
for (re i = ed ; i >= st ; -- i){
if (b[i] == 0)
{q[++ R] = i; continue;}
while (b[i] != 0 and L <= R)
final_ans += (i-q[L])*(i-q[L]), b[i] --, b[q[L]] ++, L ++;
if (b[i] == 0)
q[++ R] = i;
}
cout << final_ans << '\n';
}
#define IXINGMY
char_phi main(){
// srand(time(0));
#ifdef IXINGMY
FBI_OPENTHEDOOR(barn);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T3}\ 自然数\)
下载下发文件的时候我看到里面有一个sample_mex1.in我就觉得事情不简单
吓死我了我以为要考博弈论\(SG\)函数
结果就是一个求\(mex\)
说正解
首先预处理出\(1 \sim n\) 的\(mex\)值，然后一个\(l\)指针指向\(1\)，考虑移动\(l\)指针对答案所造成的影响。
l++后，无非是将\(a_{l-1}\)从当前自然数集合中删去，发现从\(l-1\)到下一次\(a_{l-1}\)出现这个区间内的\(mex\)值大于\(a_{l-1}\)的都变成了\(a_{l-1}\)。原因很简单，因为出现了\(a_{l-1}\)这个数的空缺。
更新之后执行区间查询即可。
然后找点的话直接二分位置然后在线段树上查询即可。
T3
#include <iostream>
#include <map>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ " "
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 200005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}
/*
十分美丽的思路
首先预处理1~n的mex
然后移动左端点
a[l] ~ 下一个a[l]之间的mex > a[l]的直接给换成a[l]，因为出现了a[l]空缺
这思路太美丽了
然后直接二分mex，在线段树上找点
*/
int n;
long long final_ans;
int a[N], cnt[N], f[N], nxt[N];
map<int, int> mp;
struct Seg_tree{long long mn, sum, lz;} t[N<<2];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)
inline void Pushup(int rt){
t[rt].mn = MIN(t[lson].mn, t[rson].mn);
t[rt].sum = t[lson].sum + t[rson].sum;
}
inline void Pushdown(int rt, int l, int r){
t[lson].sum = (mid - l + 1) * t[rt].lz, t[rson].sum = (r - mid) * t[rt].lz;
t[lson].mn = t[rson].mn = t[rt].lz;
t[lson].lz = t[rson].lz = t[rt].lz;
t[rt].lz = -1;
}
void Build(int rt, int l, int r){
t[rt].lz = -1;
if (l == r)
{t[rt].mn = t[rt].sum = f[l]; return ;}
Build(lson, l, mid);
Build(rson, mid+1, r);
Pushup(rt);
}
long long Range_Query(int rt, int l, int r, int L, int R){// 查区间和
if (L <= l and r <= R)
return t[rt].sum;
long long rtn(0);
if (t[rt].lz != -1)
Pushdown(rt, l, r);
if (L <= mid)
rtn += Range_Query(lson, l, mid, L, R);
if (R > mid)
rtn += Range_Query(rson, mid+1, r, L, R);
return rtn;
}
long long Pos_Query(int rt, int l, int r, int pos){// 查区间最小
if (l == r)
return t[rt].mn;
if (t[rt].lz != -1)
Pushdown(rt, l, r);
if (pos <= mid)
return Pos_Query(lson, l, mid, pos);
else
return Pos_Query(rson, mid+1, r, pos);
}
void Update(int rt, int l, int r, int L, int R, long long w){
if (L <= l and r <= R){
/*if (t[rt].mn <= w)
cerr << rt << _ << l << _ << r << _ << t[rt].mn << _ << w << '\n';*/
t[rt].sum = w * (r-l+1), t[rt].lz = w, t[rt].mn = w;// 因为加进来一定比原来小(
return ;
}
if (t[rt].lz != -1)
Pushdown(rt, l, r);
if (L <= mid)
Update(lson, l, mid, L, R, w);
if (R > mid)
Update(rson, mid+1, r, L, R, w);
Pushup(rt);
}
void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
for (re i = 1, ans(0) ; i <= n ; ++ i){
if (a[i] <= n)// 大于n的【】用没有(
cnt[a[i]] ++;
while (cnt[ans] != 0)
ans ++;
f[i] = ans;
}
Build(1, 1, n);
for (re i = n ; i >= 1 ; -- i){
nxt[i] = n+1;
if (mp.find(a[i]) == mp.end())
{mp[a[i]] = i; continue;}
nxt[i] = mp[a[i]], mp[a[i]] = i;
}
int L, R, MID, plc;
for (re i = 1 ; i <= n ; ++ i){
final_ans += Range_Query(1, 1, n, i, n);
// 删掉a[i]
L = i, R = nxt[i]-1, plc = -1;
while (L <= R){// 因为mex是单调不降的
MID = (L + R) >> 1;
if (Pos_Query(1, 1, n, MID) > a[i])
plc = MID, R = MID - 1;
else
L = MID + 1;
}
if (plc != -1)
Update(1, 1, n, plc, nxt[i]-1, a[i]);
}
cout << final_ans << '\n';
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(mex);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T4}\ 环路\)
咕
标签：rt,20,int,long,re,HZOI,lz,CSP,define From： https://www.cnblogs.com/charphi/p/16721705.html