[C++知识库]Codeforces Round #788 (Div. 2) A B C D E

Codeforces Round #788 (Div. 2) A B C D E

打的好 ** 烂总结一下把。

A.Prof. Slim

解法： 贪心，统计正负符号，因为每个位上的数只能是其绝对值的正负形式，所以让所有负号出现在左边，正号出现在右边。 此时已经是最优形式，如果还是出现后一项小于前一项那么答案是NO。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N];
void cf(){
    int n;
    cin>>n;
    int res1,res2;
    res1=res2=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<0)res1++;
        else res2++;
    }
    for(int i=1;i<=n;i++){
        if(i<=res1)a[i]=abs(a[i])*-1;
        else a[i]=abs(a[i]);
    }
    for(int i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            cout<<"NO"<<endl;
            return ;
        }
    }
    cout<<"YES"<<endl;
    return ;
} 
signed main(){
    // freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

B.Dorms War

解法： 给B薄纱了，赛后发现其实真的很简单。正解是统计最长的两个特殊字符之间的距离。 原因：如果产生最长的距离的两个字符$a$和$b$出现在中间，那么后一个字符会被后面距离较短字符$a1$和$b1$中的$b1$所吸收，使得$b1$取代$b$的地位，但本质实则是不变的，也就是$b1$到$a$的次数和$b$到$a$的次数是一样的。其前面的距离较短字符$a2$和$b2$也一定会在$b$到$a$的过程中完全消失。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
set<char>ss;
const int N = 2e5+10;
int sum[N];
void cf(){
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)sum[i]=0;
    string s;
    cin>>s;
    string end;
    ss.clear();
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        char sss;
        cin>>sss;
        ss.insert(sss);
    }
    int last=0;
    int ma=0;
    for(int i=0;i<s.size();i++){
        if(ss.count(s[i])){
            ma=max(ma,i-last);
            last=i;
        }
    }
    cout<<ma<<endl;
} 
signed main(){
    // freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

C.Where is the Pizza?

思路： 首先考虑该题如果没有$d$数组限制会如何，那么我们需要考虑的就是$a$和$b$数组构造排列的方案数。仔细观察容易发现数组$a$和数组$b$中的数是可以构成环的，在这个环中出现的数必定出现$2$次，例如数据：
1 5 2 4 6 3
6 5 3 1 4 2

1 6 4 1 便是一个环，在没有d数组约数情况下，显然该处可产生两组数据，1 4 6 和 6 1 4 那么对于总方案数的贡献就是 $?$ $2$，但是如果d数组有约束，即$a[i]=b[i]$，那么$d[i]$必然是固定的，或者输入就已给出的情况，那么整个环的方案即唯一，那么对总方案数的贡献就是$?$ $1$，那么我们要做的就是暴力判环，以及判段时候$d$数组存在约束，最终快速幂或者累乘都可。此处的暴力判环我实现的方法是数组映射。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N],b[N],c[N];
int ba[N];
bool ok[N];
bool st;
int sta;
const int mod=1e9+7;
void cf(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],ok[i]=false;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    int ti=0;
    for(int i=1;i<=n;i++){
        ba[a[i]]=i;
    }
    int ans=1;
    for(int i=1;i<=n;i++){
        if(!ok[i]){
            st=true;
            if(a[i]==b[i]||c[i])st=false;
            ok[i]=true;
            int j;
            j=ba[b[i]];
            while(1){
                if(j==i)break;
                if(a[j]==b[j]||c[j])st=false;
                ok[j]=true;
                j=ba[b[j]];
            }
            if(st)ans=ans*2%mod;
        }
    }
    cout<<ans<<endl;
} 
signed main(){
    // freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

D.Very Suspicious

思路： 找规律+递归+二分。先偷个图会更容易理解。

在草稿纸上画图，枚举前几条线最多能带来多少个等边三角形。发现规律，每画一条固定斜率的一条线，会产生$2?(和其斜率不相同直线个数)$个等边三角形。又因为一共只有$3$条不同斜率的线可画，那么最贪心方法就是
0 0 0 = 0，1 0 0 = 0，1 1 0 = 2，1 1 1 = 4 ，2 1 1 = 4， 2 2 1 = 6 ，2 2 2 =8… 然后我是暴力map存下能实现不超过$1e9$个等边三角形的直线个数，然后二分查找。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int>mp;
int ed;
void init(){
    int all=1e9;
    int st=1;
    int number=0;
    int sum=0;
    for(int i=1;;i++){
        if(sum>=all)break;
        if(st%3!=1){
            number+=2;
        }
        sum+=number;
        mp[i]=sum;
        st++;
        ed=i;
    }
}
void cf(){
    int l=1,r=ed;
    int n;
    cin>>n;
    while(l<r){
        int mid=l+r>>1;
        if(mp[mid]>=n)r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return ;
} 
signed main(){
    // freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	init();
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

E.Hemose on the Tree

思路： 最小的最大路径异或答案必然大于等于$2^p$，因为假设我们根结点的赋值为小于等于$2^p$的值，因为存在$2^p+1$ ~ $2^p+2^p?1$之间的数，我们必然会产生高位。所以路径异或答案必然大于等于$2^p$。接下去进行构造，因为结点个数比边数多$1$，所以我们只要让结点$1$赋值为$2^p$，剩下的每一条边及链接的结点只需按照如下形式构造即可。如果前面路径异或答案为$x(x<2^p)$，那么我当前值构造为$x+2^p$，如果前面路径异或答案为$x(x>=2^p)$，我们将当前值构造为$x+1$即可目的为了消去高位。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
const int N = 3e5+10;
vector<PII>v[N];
int dp1[N],dp2[N];
int st;
int n;
void dfs(int u,int fa,int g){
    for(auto x:v[u]){
        if(x.first==fa)continue;
        st++;
        dp1[x.first]=st^g;
        dp2[x.second]=st^g^n;
        dfs(x.first,u,g^n);
    }
}
void cf(){
    cin>>n;
    n=1<<n;
    st=0;
    for(int i=1;i<=n;i++){
        v[i].clear();
        dp1[i]=dp2[i]=0;
    }
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    dp1[1]=n;
    cout<<1<<endl;
    dfs(1,-1,0);
    for(int i=1;i<=n;i++)cout<<dp1[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n-1;i++)cout<<dp2[i]<<' ';
    cout<<endl;
    return ;
} 
signed main(){
    // freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        cf();
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖