Codeforces Round #669 (Div. 2)A~D题解

发布于 2020-09-10  0 次阅读


A. Ahahahahahahahaha(构造)

题目大意:

给你一个长度为n的01数组,你可以删除其中不超过n / 2位,使得数组满足a1 − a2 + a3 − a4 + … = 0

思路:

首先看到删除其中不超过n / 2 位这句话就应该想到删去其中的一半了,也就是删除01两者中最少的那个,删0留1的时候注意要保留偶数位的1

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N];
void solve(){
    cin>>n;
    int ans1=0, ans0=0;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(a[i]==1) ans1++;
        else        ans0++;
    }
    if(ans1==n){
        cout<<n<<endl;
        while(ans1--)   cout<<"1 ";
        cout<<endl;
        return ;
    }
    if(ans0==n){
        cout<<n<<endl;
        while(ans0--)   cout<<"0 ";
        cout<<endl;
        return ;
    }
    if(ans1&1)  ans1--, n--;

    if(ans1>ans0){
        cout<<n-ans0<<endl;
        while(ans1--)   cout<<"1 ";
        cout<<endl;
        return ;
    }
    if(ans1<=ans0){
        cout<<n-ans1<<endl;
        while(ans0--)   cout<<"0 ";
        cout<<endl;
        return ;
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Big Vova(暴力)

题目大意:

给你一个长度为n的数组a,求一个数组b,可以使得数组c的字典序最大
其中ci= GCD ( b1 , … , bi )

思路:

数据小,直接暴力
第一个数肯定为a中最大的数,后面依次为能使得gcd最大的数即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N], b[N], vis[N], g[N];
inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
void solve(){
    cin>>n;
    int mx=0, idx=0, len=0;
    memset(b, 0, sizeof(b));
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(a[i]>mx) mx=a[i], idx=i; 
    }
    int tmp;
    vis[idx]=1;
    b[++len]=mx;
    g[len]=mx;
    for(int j=1; j<=n; j++){
        mx=idx=0;
        for(int i=1; i<=n; i++){
            if(vis[i]==0){
                tmp=gcd(g[len],a[i]);
                if(tmp>mx) mx=tmp, idx=i;
            }
        }
        vis[idx]=1;
        b[++len]=a[idx];
        g[len]=mx;
    }
    for(int i=1; i<len; i++)   cout<<b[i]<<" ";
    cout<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Chocolate Bunny(思维)

题目大意:

求一个长度为n的数组
每次可以输入两个值i和j询问,将会得到一个为pi mod pj 返回值,最多可以进行2*n次询问

思路:

注意到询问的最高次数为2*n次,所以每位最多在两次询问中确定
再注意到pi mod pj​,联想到小的值mod大的值为本身,所以可以通过不同方法询问两个值(即询问i j和询问j i),得到较小的那个值,通过这种方法将数组走一遍,每次tmp为当前未知的大值,小值记录进数组,最后大值即为最大的n,将其放入数组即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, a[N];

void solve(){
    cin>>n;
    int tmp=1;
    for(int i=2; i<=n; i++){
        int q, p;
        cout<<"? "<<tmp<<" "<<i<<endl;
        cin>>q;
        cout<<"? "<<i<<" "<<tmp<<endl;
        cin>>p;
        if(q < p) a[i]=p;
        else      a[tmp]=q, tmp=i;
    }   
    a[tmp]=n;
    cout<<"!";
    for(int i=1; i<=n; i++) cout<<" "<<a[i];
    cout<<endl;
    return ;
}

signed main(){
    solve();
    return 0;
}

D. Discrete Centrifugal Jumps(单调栈&&dp)

题目大意:

image 22

思路:

无后效性的最优解,考虑dp,用单调栈维护转移
考虑d p [ i ] ,其中i 表示到此位置需要的最小步数
使用非严格递增的单调栈维护第三种状态
使用非严格递减的单调栈维护第三种状态
最后记得判断即将入栈的元素是否与栈顶相同,相同需要弹出栈顶元素,因为题目要求的是<而不是<=

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=5e5 +9;
int n, a[N];
int down[N], up[N], dp[N];
int totd, totu;
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    down[++totd]=1;up[++totu]=1;
    memset(dp, INF, sizeof(dp));
    dp[1]=0;
    for(int i=2; i<=n; i++){
        dp[i]=dp[i-1]+1;
        while(totd>0 && a[i]>a[down[totd]])
            dp[i]=min(dp[i], dp[down[totd--]]+1);
        while(totu>0 && a[i]<a[up[totu]])
            dp[i]=min(dp[i], dp[up[totu--]]+1);
        dp[i]=min(dp[i], min(dp[down[totd]], dp[up[totu]])+1);
        while(a[down[totd]]==a[i])    totd--;
        while(a[up[totu]]==a[i])      totu--;
        down[++totd]=i;up[++totu]=i;
    }
    cout<<dp[n]<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生