zafu个人赛 2022.2.16 A B C D E F G总结

A - Three DiceAtCoder - abc202_a

思路： 签到

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    int a,b,c;
    cin>>a>>b>>c;
    int res=21;
    cout<<res-a-b-c<<endl;

    return 0;
}

B. Lineland Mail(900分)CodeForces - 567A

Tip : greedy、implementation

思路： 显然最近的就是其相邻两数，最远的就是首和尾取一个$max$。稍微判断一下边界，模拟。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e5+10;
int a[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=a[1];
    int r=a[n];
    for(int i=1;i<=n;i++){
        if(i==1)cout<<a[2]-a[1]<<' ';
        else if(i==n)cout<<abs(a[i-1]-a[i])<<' ';
        else{
            cout<<(min(a[i]-a[i-1],a[i+1]-a[i]))<<' ';
        }
        cout<<max(abs(l-a[i]),r-a[i])<<endl;
    }
    return 0;
}

B. Code obfuscation(1100分)CodeForces - 765B

Tip : implementation 、string

思路： 一开始没看懂它在说什么，后来发现扫一遍就好了，初始从$a$开始，如果有了$a$，上限就提高到$b$，如果字符比上限高就说明不规范。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    bool ok=true;
    char st='a';
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]==st){
            st++;
        }
        else if(s[i]<st){
            continue;
        }
        else if(s[i]>st){
            ok=false;
            break;
        }   
    }
    if(ok)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

D. Restoring Painting(1400分)CodeForces - 675B

Tip : constructive algorithms、math

思路： 这题开始有了一点点难度，一开始想偏了，以为分类讨论。因为中间的数对$4$个角都有贡献所以一定提供$n$种方案，那么剩余的只需统计剩下$4$个角的组合方案。由于我们选择的数一定要在$1$ ~ $n$的区间内，所以我们只需在每个角的两边和中分别取一个$max$和$min$。那么方案数的大小即是将$min$减到$1$，$max$随着$min$的减同时跟着减。那么最终可选择方案的区间就是$max$ ~ $n$，最终的方案数就是$(n-max)*n。$考虑$max>n$的情况方案数为$0$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    int res[5];//统计四个角两边和
    res[0]=a+b;
    res[1]=b+d;
    res[2]=c+d;
    res[3]=c+a;
    sort(res,res+4);
    int x=res[3]-res[0];//最小的减到0时，max跟着减最终的值。
    x++;
    if(x>n){
        cout<<0<<endl;
    }
    else{
        int sum=n-x+1;//四个角约束条件下带来的方案数。
        cout<<sum*n<<endl;
    }
    return 0;
}

E. Hard Process(1600分)CodeForces - 660C

Tip：two pointers

思路： 一开始没看出来是双指针，往$dfs$和$dp$方向想了，似乎也可以$dp?$但是双指针还是蛮好想到和写的，练太少，调了好久。 用一个$l$和一个$r$维护区间，如果魔法次数$k$不够用了，就不断将左边界右移，缩小区间直至$k$不为$0$，并且需要记录连续$1$的数量最大时的区间左边界和右边界，最后需要将这个区间内所有数变$1$输出。如果$k$为$0$我们直接输出返回即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=3e5+10;
int a[N];
signed main(){
    int n,k;
    cin>>n>>k;
    int ma=0;//统计最大1的数量
    int ll,rr;//用来记最大连续的左右边界
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(k==0){
        int res=0;
        for(int i=1;i<=n;i++){
            if(a[i]==1){res++;}
            else if(a[i]==0){
                res=0;
            }
            ma=max(ma,res);
        }
        cout<<ma<<endl;
        for(int i=1;i<=n;i++)cout<<a[i]<<' ';
        cout<<endl;
        return 0;
    }
    int l,r;
    l=r=0;
    int res=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1){//如果是1直接右移即可，不需要消耗魔法次数
            r++;
        }
        else if(a[i]==0){
            if(res<k){//如果魔法次数还有右移，消耗1个魔法次数
                res++;
                r++;
            }
            else if(res>=k){//如果魔法次数不够用了，左边界右移。
                while(l<r){
                    if(a[l+1]==0){
                        res--;
                        l++;
                    }
                    else if(a[l+1]==1){
                        l++;
                    }
                    if(res<k)break;
                }
                if(res<k){//如果通过左移左边界得到魔法次数那么可以消耗1魔法次数将当前的0变成1
                    res++;
                    r++;
                }
            }
        }
        if(r-l>ma){//比较更新
            ma=r-l;
            ll=l,rr=r;
        }
    }
    cout<<ma<<endl;
    for(int i=1;i<=ll;i++)cout<<a[i]<<' ';
    for(int i=ll+1;i<=rr;i++)cout<<1<<' ';//区间内都是1，其他老样子输出。
    for(int i=rr+1;i<=n;i++)cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}

F. Restore Permutation(1900分)CodeForces - 1208D

Tip：Binary Indexed Tree、segment tree

思路： 感觉就是一个树状数组和线段树的板题，$O(logn)$求区间和运用。首先最后一个数一定是唯一且确定的。我们只需要$O(n)倒推$，每次$O(logn)$$O(logn)$，二分+查询区间和即可确认当前数的下标。每次确定完一个数之后在树状数组或线段树中删除该数，不影响后面操作的区间和获得。总复杂度$O(nlognlogn)$。每次扫描只需要存二分出来的答案坐标$+1$即可，存到容器里面，因为题目要求的是前面比其小的数的和，所以其数是答案坐标$+1$。往上的思路还是很简单的，我很快推出来了，结果$debug$一个多小时，有个很坑的点需要注意。如果$a[i]==0且l==1$时，如果只按照上面的方法无法确定当前的下标要不要$+1$，因为我们无法确定最终的坐标是$1$还是$2$，因为$1$这个坐标很特殊他是$2$的前面数的和同时也是$1$它本身。所以我们判断一下如果$1$还没选择，那么选择$1$，否则如果$1$选择了，最终的下标必定是$2$，用一个$bool$判断即可。现在发现这个点也并不是很难想，但是debug了好久…

• 参考代码(树状数组版本)：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int tr[N];
int a[N];
int n;
void add(int a,int x){
    for(int i=a;i<=n;i+=lowbit(i)){
        tr[i]+=x;
    }
}
int ask(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
signed main(){
    cin>>n;
    vector<int>S;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,i);//所有数全部存到树中
    }
    bool ok1=true;//判断1有没有选过
    for(int i=n;i>=1;i--){
        int l=1;int r=n;
        while(l<r){
            int mid=l+r+1>>1;
            int x=ask(mid);
            if(x>a[i])r=mid-1;
            else l=mid;
        }
        if(a[i]==0&&l==1){
            if(ok1){
                ok1=false;
                add(1,-1);
                S.push_back(1);
            }
            else{
                add(2,-2);
                S.push_back(2);
            }
        }
        else{
            l=l+1;
            add(l,-l);
            S.push_back(l);
        }
    }
    reverse(S.begin(),S.end());//S[0]是尾巴的数，所以得翻一下。
    for(auto x:S)cout<<x<<' ';
    cout<<endl;
    return 0;
}

G. Ryouko’s Memory Note(1800)CodeForces - 433C

Tip：math 、sorting

思路： 每个数从$x$变成$y$只有与其相邻数的减的绝对值发生了变化，且对答案的产生了贡献。所以我们需要$O(n)$扫描，存一下每个数相邻的数，接下去如果这个数$x$发生了变化，那么存的这些数会对$y$的选择产生至关重要的作用。最后$O(n)$扫描，从$1$到$n$进行替换选择。如果当前数没有相邻的数，那么我们直接跳过，因为他的改变不会影响答案的决策。否则的话我们需要从所有与其相邻的数中(可以重复)，选出一个中位数，当作$y$。贪心：具体参照仓货选址。 所以需要在存的数组中进行一个$sort$，所以最终的复杂度是$O(nlogn)$，然后比较改变前和改变后对答案的贡献，记录最大的改变前$-$改变后的值，那么最后的最大值就是我们可以节约的最大值。最终的答案就是原能量花费减去最大能量节约之后的能量花费。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e5+10;
int a[N];
vector<int>b[N];//用来存数
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        if(i!=m){
            if(a[i]!=a[i+1])
            b[a[i]].push_back(a[i+1]);
        }
        if(i!=1){
            if(a[i]!=a[i-1])
            b[a[i]].push_back(a[i-1]);
        }
    }
    int sum=0;
    for(int i=2;i<=m;i++){
        sum+=abs(a[i]-a[i-1]);
    }
    int ma=0;//存最大节约
    for(int i=1;i<=n;i++){
        if(b[i].size()==0)continue;//如果没有存的数跳过，不会对答案有贡献。
        sort(b[i].begin(),b[i].end());
        int y=b[i][(b[i].size()-1)>>1];//中位数
        int before,after;
        before=after=0;
        for(auto x:b[i]){
            before+=abs(i-x);
            after+=abs(y-x);
        }
        ma=max(ma,before-after);//更新最大节约
    }
    cout<<sum-ma<<endl;//最终的最小能量花费
    return 0;
}

切了$1900$的题还是蛮开心的，虽然$cf$比赛时候可能时间不够，算是一个小进步。