CF 1455 题解

Author： RainAir
发布时间：December 8, 2020
1357views
2 comments
1021 words
Categories：题解

A

$g(x)$ 实际是求原数和去除后缀 $0$ 后的数的比值，发现第一个不同的值一定会在 $10^x$ 达到，所以答案就是字符串长度。

B

我们先假设走了 $m$ 步，并且都是走第一种，那么相当于就是走了 $\frac{m(m+1)}{2}$，发现将第 $i$ 个位置改成第二种操作会减少 $i+1$，我们先找到最小的 $m$ 满足 $\frac{m(m+1)}{2} \geq x$ ，设 $r=\frac{m(m+1)}{2}-x$，发现一定有 $r \leq m$，而我们发现所有位置更改后能减少的量分别是 $2,3,\ldots,m+1$，发现只有 $r=1$ 的时候不能被表示出来，所以 $r=1$ 的时候让 $m+1$ 就是答案了。

C

注意这两个人的策略都是最大化自己的胜利步数，显然后手可以一直不接球等到先手耗尽体力的时候将球打回去，剩下的球先手都接不到，所以后手最大胜利次数就是 $y$，先手由于最后一次球被接住了，胜利次数是 $x-1$。

D

贪心模拟，假设当前手里的数字是 $x$，正在考虑第 $i$ 个位置：

$a_{i-1} > a_i$：如果换不了（$a_i \leq x$）就直接输了，否则我们一定会交换，看下是否满足条件
$a_{i-1} \leq a_i$：如果 $x < a_i$，因为这个序列是不降的，就意味着以后都不能交换了，所以这时候判一下 $i+1$ 后缀是否有序，如果不有序你一定要交换；如果 $x \geq a_i$ 就可以不管。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
int n,x,a[MAXN];
bool f[MAXN];

inline void Solve(){
    scanf("%d%d",&n,&x);
    FOR(i,1,n) scanf("%d",a+i);
    int p = 1;
    ROF(i,n,2){
        if(a[i-1] > a[i]){
            p = i;break;
        }
    }
    if(p == 1){
        puts("0");
        return;
    }
    int ans = 0;
    if(x < a[1]) std::swap(x,a[1]),++ans;
    FOR(i,2,p){
        if(a[i-1] > a[i]){
            if(a[i] <= x){
                puts("-1");return;
            }
            std::swap(a[i],x);++ans;
            if(a[i-1] > a[i]){
                puts("-1");return;
            }
        }
        else if(x < a[i] && i != p){
            std::swap(a[i],x);++ans;
        }
    }
    printf("%d\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

E

我们设正方形左下角 $(x,y)$ 边长为 $d$，枚举四个点分别对应正方形的哪些点，现在有三个变量 $x,y,d$，但我们发现贡献式子最终是形如若干个 $|x-x_i|,|x+d-x_i|,|y-y_i|,|y+d-y_i|$ 的和，如果将 $d$ 看成常量，发现 $x,y$ 一定会取让某个绝对值为 $0$ 的点，枚举取什么，剩下就变成了求 $\sum_i |d+c_i|$ 的最大值，也是一定会取某个零点的位置，都算算就好了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

LL xx[5],yy[5],x[5],y[5];
int p[5];

inline LL mabs(LL x){
    return x < 0 ? -x : x;
}

std::vector<LL> S;

inline LL gao(){
    std::sort(all(S));
    int t = S.size()>>1;
    LL p = -S[t-1],res = 0;
    for(auto x:S) res += abs(x+p);
    return res;
}

inline void Solve(){
    FOR(i,1,4) scanf("%lld%lld",xx+i,yy+i),p[i] = i;
    LL ans = 1e18;
    do{
        FOR(i,1,4) x[p[i]] = xx[i],y[p[i]] = yy[i];
        for(auto i:{1,3}){
            for(auto j:{1,2}){
                S.clear();
                LL c = abs(x[1]-x[i])+abs(x[3]-x[i])+abs(y[1]-y[j])+abs(y[2]-y[j]);
                for(auto k:{2,4}) S.pb(x[i]-x[k]);
                for(auto k:{3,4}) S.pb(y[j]-y[k]);
                std::vector<LL> T = S;
                LL mn = 1e18;
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,2,3) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                c += mn;
                ans = std::min(ans,c);
            }
        }
    }while(std::next_permutation(p+1,p+4+1));
    printf("%lld\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

F

这题非常好的地方在于 dp 状态表示的不一定是个数，还可以是个字符串（

设 $f_i$ 表示操作完了 $1 \ldots i$ ，前缀的最小字典序，转移的时候分类讨论 $i+1,i+2$ 的操作：

U/D ，$f_{i} \to f_{i+1}$
L，$f_i \to f_{i+1}$
R+U/D，$f_{i} \to f_{i+2}$
RL，$f_i \to f_{i+2}$

直接转移即可，复杂度 $O(n^2)$。

可以用滚动数组+二分哈希做到 $O(n \log n)$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
int n,k;
int mn[26];
std::string f[MAXN],str;

inline std::string ctos(char x){
    return std::string(1,x);
}

inline void Solve(){
    std::cin >> n >> k >> str;str = "0"+str;
    mn[0] = 0;FOR(i,1,k-2) mn[i] = i-1;mn[k-1] = 0;
    f[0].clear();FOR(i,1,n) f[i] = "{";
    FOR(i,0,n-1){
        f[i+1] = std::min(f[i+1],f[i]+ctos('a'+mn[str[i+1]-'a']));
        if(i) f[i+1] = std::min(f[i+1],f[i].substr(0,i-1)+ctos(str[i+1])+f[i].back());
        if(i != n-1) f[i+2] = std::min(f[i+2],f[i]+ctos('a'+mn[str[i+2]-'a'])+ctos(str[i+1]));
        if(i && i != n-1) f[i+2] = std::min(f[i+2],f[i].substr(0,i-1)+ctos(str[i+2])+f[i].back()+ctos(str[i+1]));
    }
    std::cout << f[n] << std::endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    int T;std::cin >> T;
    while(T--) Solve();
    return 0;
}

G

dp 合并可以启发式合并。。这个很妙

先考虑没有 if 咋做：设 $f_{i,x}$ 表示执行了前 $i$ 条语句，当前值是 $x$ 的答案，直接做是 $O(n^2)$ 的。

观察转移相当于全局加上一个值和求一个最小值并单点赋值，用数据结构维护可以做到 $O(n \log n)$。这里可以直接用一个 set 维护最小值，map 维护每个下标对应的在 set 里的值，再维护个整体加标记即可。我们只需要维护可能的值的 dp 值就好了。

有 if 咋做呢？我们发现 if 内部是独立的，可以做一样的 dp，只是 dp 的初值需要改一下，所以我们遇到 if 就进去做 dp ，做完后考虑如何合并这两个块：我们可以用启发式合并，将大小小的每一种 dp 值都合并到大的里，注意要特判一下 if 条件给的值对应的 dp 值（这里不能单纯去 min，需要覆盖）。

启发式合并复杂度对的原因在于一次转移可以放缩看成加入一个元素，于是复杂度就是显然的 $O(n \log^2 n)$ 了。细节挺多的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int n,s;

struct Node{// 全局加 单点修改 询问最小值
    LL tag;
    std::map<int,LL> mp;// 位置 i 在 set 内的值
    std::multiset<LL> S;
    Node(LL tag=0) : tag(tag) {}
    inline void update(int p,LL d){
        if(p == s) return;
        if(mp.count(p)) S.erase(S.find(mp[p]));
        mp[p] = d-tag;
        S.insert(mp[p]);
    }

    inline LL get(int p){
        if(!mp.count(p)) return 1e18;
        return mp[p]+tag;
    }

    inline void upmin(int p,LL d){
        if(p == s) return;
        if(get(p) > d) update(p,d);
    }

    inline LL query(){
        return *S.begin() + tag;
    }
};

std::vector<Node> st;
std::vector<int> oo;

int main(){
    scanf("%d%d",&n,&s);
    Node v;v.update(0,0);
    st.pb(v);oo.pb(-114514);
    FOR(i,1,n){
        char opt[12];scanf("%s",opt);
        if(opt[0] == 's'){
            int x,y;scanf("%d%d",&x,&y);
            if(st.back().mp.empty()) continue;
            LL c = st.back().query();
            st.back().tag += y;st.back().upmin(x,c);
        }
        if(opt[0] == 'i'){
            int x;scanf("%d",&x);
            LL c = st.back().get(x);
            Node v;if(c != 1e18) v.update(x,c);
            st.pb(v);oo.pb(x);
        }
        if(opt[0] == 'e'){
            int tp = (int)st.size()-1,o = oo.back();bool flag = 1;
            if(st[tp].mp.size() > st[tp-1].mp.size()) std::swap(st[tp],st[tp-1]),flag = 0;
            for(auto x:st[tp].mp){
                if(x.fi != o) st[tp-1].upmin(x.fi,x.se+st[tp].tag);
                else{
                    if(flag) st[tp-1].update(x.fi,x.se+st[tp].tag);
                }
            }
            st.pop_back();oo.pop_back();
        }
    }
    printf("%lld\n",st[0].query());
    return 0;
}

Last modification：December 8th, 2020 at 08:53 pm

如果觉得我的文章对你有用，请随意赞赏

2 comments

Siyuan
December 18th, 2020 at 08:50 pm

道理我都懂，可为什么要关掉 pjax 呢 /kk

Reply
1. RainAir
  December 22nd, 2020 at 04:23 pm
  
  @Siyuan
  
  Siyuan！因为我的公式换了本地加载，而我不会写 js 规则所以只能每次重新加载了/kk
  
  Reply

CF 1455 题解

RainAir • 2020 年 12 月 08 日

A

$g(x)$ 实际是求原数和去除后缀 $0$ 后的数的比值，发现第一个不同的值一定会在 $10^x$ 达到，所以答案就是字符串长度。

B

C

D

贪心模拟，假设当前手里的数字是 $x$，正在考虑第 $i$ 个位置：

$a_{i-1} > a_i$：如果换不了（$a_i \leq x$）就直接输了，否则我们一定会交换，看下是否满足条件
$a_{i-1} \leq a_i$：如果 $x < a_i$，因为这个序列是不降的，就意味着以后都不能交换了，所以这时候判一下 $i+1$ 后缀是否有序，如果不有序你一定要交换；如果 $x \geq a_i$ 就可以不管。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
int n,x,a[MAXN];
bool f[MAXN];

inline void Solve(){
    scanf("%d%d",&n,&x);
    FOR(i,1,n) scanf("%d",a+i);
    int p = 1;
    ROF(i,n,2){
        if(a[i-1] > a[i]){
            p = i;break;
        }
    }
    if(p == 1){
        puts("0");
        return;
    }
    int ans = 0;
    if(x < a[1]) std::swap(x,a[1]),++ans;
    FOR(i,2,p){
        if(a[i-1] > a[i]){
            if(a[i] <= x){
                puts("-1");return;
            }
            std::swap(a[i],x);++ans;
            if(a[i-1] > a[i]){
                puts("-1");return;
            }
        }
        else if(x < a[i] && i != p){
            std::swap(a[i],x);++ans;
        }
    }
    printf("%d\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

E

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

LL xx[5],yy[5],x[5],y[5];
int p[5];

inline LL mabs(LL x){
    return x < 0 ? -x : x;
}

std::vector<LL> S;

inline LL gao(){
    std::sort(all(S));
    int t = S.size()>>1;
    LL p = -S[t-1],res = 0;
    for(auto x:S) res += abs(x+p);
    return res;
}

inline void Solve(){
    FOR(i,1,4) scanf("%lld%lld",xx+i,yy+i),p[i] = i;
    LL ans = 1e18;
    do{
        FOR(i,1,4) x[p[i]] = xx[i],y[p[i]] = yy[i];
        for(auto i:{1,3}){
            for(auto j:{1,2}){
                S.clear();
                LL c = abs(x[1]-x[i])+abs(x[3]-x[i])+abs(y[1]-y[j])+abs(y[2]-y[j]);
                for(auto k:{2,4}) S.pb(x[i]-x[k]);
                for(auto k:{3,4}) S.pb(y[j]-y[k]);
                std::vector<LL> T = S;
                LL mn = 1e18;
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,2,3) S[k] = -S[k];
                mn = std::min(mn,gao());
                S=T;FOR(k,0,1) S[k] = -S[k];
                mn = std::min(mn,gao());
                c += mn;
                ans = std::min(ans,c);
            }
        }
    }while(std::next_permutation(p+1,p+4+1));
    printf("%lld\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

F

这题非常好的地方在于 dp 状态表示的不一定是个数，还可以是个字符串（

设 $f_i$ 表示操作完了 $1 \ldots i$ ，前缀的最小字典序，转移的时候分类讨论 $i+1,i+2$ 的操作：

U/D ，$f_{i} \to f_{i+1}$
L，$f_i \to f_{i+1}$
R+U/D，$f_{i} \to f_{i+2}$
RL，$f_i \to f_{i+2}$

直接转移即可，复杂度 $O(n^2)$。

可以用滚动数组+二分哈希做到 $O(n \log n)$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
int n,k;
int mn[26];
std::string f[MAXN],str;

inline std::string ctos(char x){
    return std::string(1,x);
}

inline void Solve(){
    std::cin >> n >> k >> str;str = "0"+str;
    mn[0] = 0;FOR(i,1,k-2) mn[i] = i-1;mn[k-1] = 0;
    f[0].clear();FOR(i,1,n) f[i] = "{";
    FOR(i,0,n-1){
        f[i+1] = std::min(f[i+1],f[i]+ctos('a'+mn[str[i+1]-'a']));
        if(i) f[i+1] = std::min(f[i+1],f[i].substr(0,i-1)+ctos(str[i+1])+f[i].back());
        if(i != n-1) f[i+2] = std::min(f[i+2],f[i]+ctos('a'+mn[str[i+2]-'a'])+ctos(str[i+1]));
        if(i && i != n-1) f[i+2] = std::min(f[i+2],f[i].substr(0,i-1)+ctos(str[i+2])+f[i].back()+ctos(str[i+1]));
    }
    std::cout << f[n] << std::endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    int T;std::cin >> T;
    while(T--) Solve();
    return 0;
}

G

dp 合并可以启发式合并。。这个很妙

先考虑没有 if 咋做：设 $f_{i,x}$ 表示执行了前 $i$ 条语句，当前值是 $x$ 的答案，直接做是 $O(n^2)$ 的。

启发式合并复杂度对的原因在于一次转移可以放缩看成加入一个元素，于是复杂度就是显然的 $O(n \log^2 n)$ 了。细节挺多的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int n,s;

struct Node{// 全局加 单点修改 询问最小值
    LL tag;
    std::map<int,LL> mp;// 位置 i 在 set 内的值
    std::multiset<LL> S;
    Node(LL tag=0) : tag(tag) {}
    inline void update(int p,LL d){
        if(p == s) return;
        if(mp.count(p)) S.erase(S.find(mp[p]));
        mp[p] = d-tag;
        S.insert(mp[p]);
    }

    inline LL get(int p){
        if(!mp.count(p)) return 1e18;
        return mp[p]+tag;
    }

    inline void upmin(int p,LL d){
        if(p == s) return;
        if(get(p) > d) update(p,d);
    }

    inline LL query(){
        return *S.begin() + tag;
    }
};

std::vector<Node> st;
std::vector<int> oo;

int main(){
    scanf("%d%d",&n,&s);
    Node v;v.update(0,0);
    st.pb(v);oo.pb(-114514);
    FOR(i,1,n){
        char opt[12];scanf("%s",opt);
        if(opt[0] == 's'){
            int x,y;scanf("%d%d",&x,&y);
            if(st.back().mp.empty()) continue;
            LL c = st.back().query();
            st.back().tag += y;st.back().upmin(x,c);
        }
        if(opt[0] == 'i'){
            int x;scanf("%d",&x);
            LL c = st.back().get(x);
            Node v;if(c != 1e18) v.update(x,c);
            st.pb(v);oo.pb(x);
        }
        if(opt[0] == 'e'){
            int tp = (int)st.size()-1,o = oo.back();bool flag = 1;
            if(st[tp].mp.size() > st[tp-1].mp.size()) std::swap(st[tp],st[tp-1]),flag = 0;
            for(auto x:st[tp].mp){
                if(x.fi != o) st[tp-1].upmin(x.fi,x.se+st[tp].tag);
                else{
                    if(flag) st[tp-1].update(x.fi,x.se+st[tp].tag);
                }
            }
            st.pop_back();oo.pop_back();
        }
    }
    printf("%lld\n",st[0].query());
    return 0;
}

CF 1455 题解

A

B

C

D

E

F

G

2 comments

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

20联赛集训day12 题解

「计算几何初步」找平面凸包

简易 vim 配置

2020.09.26【NOIP提高组】模拟

ARC096E - Everything on It

CF 1455 题解

A

B

C

D

E

F

G