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)\ast 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)\ast O(logn)$，二分+查询区间和即可确认当前数的下标。每次确定完一个数之后在树状数组或线段树中删除该数，不影响后面操作的区间和获得。总复杂度$O(n\ast logn\ast logn)$。每次扫描只需要存二分出来的答案坐标$+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$比赛时候可能时间不够，算是一个小进步。