Educational Codeforces Round 94 (Rated for Div. 2)A~D题解

发布于 2020-08-26  0 次阅读


A. String Similarity

题目大意:

给你一个n和一个长度为2 ∗ n − 1 的01字符串,对于给定字符串,你需要构造一个长度为n的字符串,其与原字符串的s [ 1.. n ] , s [ 2.. n + 1 ] , s [ 3.. n + 2 ] , . . . , s [ n . . 2 n − 1 ] 全部相似
相似:两个二进制字符串某一位置上的字符相同

思路:

原字符串一共刚好有n个子字符串,答案字符串的长度也是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;
string s;
void solve(){
    cin>>n;
    cin>>s;
    string ans="";
    for(int i=0; i<2*n-1; i+=2) ans+=s[i];
    cout<<ans<<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;
}

B. RPG Protagonist

题目大意:

有一个人和一个随从,告诉你他们分别能带的东西的最大重量
分别有两种物品,分别告诉你两种物品的数量和大小,每个物品的权值均为1,求两人可以带走的最大权值

思路:

这个题很明显的是贪心,所以思考怎么贪心
首先处理一下数据,保证第一个物品的大小最小
枚举第一个人所选择的第一种物品的数量,剩下的空间尽可能的装2
第二个人根据第一个人的枚举,尽可能的选择多的第一种物品(它大小更小),剩下的空间尽可能的装2即可

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 p, f, cnts, cntw, s, w;
void solve(){
    cin>>p>>f;
    cin>>cnts>>cntw;
    cin>>s>>w;
    if(s>w) swap(s,w), swap(cnts, cntw);
    int cnt=0;
    for(int i=0; i<=cnts; i++){
        if(i*s>p)   break;
        int ans1, ans2, ans3, ans=0;
        ans1=min(cntw, (p-i*s)/w);
        ans2=min(cnts-i, f/s);
        ans3=min(cntw, (f-ans2*s)/w);
        ans=min(cnts,i+ans2)+min(cntw, ans1+ans3);
        cnt=max(cnt, ans);
    }
    cout<<cnt<<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. Binary String Reconstruction

题目大意:

给你一个01字符串和一个x,让你构造一个字符串
该字符串满足,当原字符串满足a [ i − x ] = = 0 & & a [ i + x ] = = 0时,该字符串的a [ i ] = 0,否则均为1

思路:

首先处理给出的字符串中的0,这说明答案的字符串中a [ i − x ] = = 0 & & a [ i + x ] = = 0,处理完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;
string s, w, ss;
int len, x;
void solve(){
    cin>>s;
    cin>>x;
    len=s.length();
    w.assign(len,'1');
    ss.assign(len,'1');
    for(int i=0; i<len; i++){
        if(s[i]=='0'){
            if(i-x>=0)  w[i-x]='0';
            if(i+x<len) w[i+x]='0';
        }
    }
    for(int i=0; i<len; i++){
        if(((i-x>=0) && w[i-x]=='0') && ((i+x)<len && w[i+x]=='0'))   ss[i]='0';
        else if((i-x<0) && (i+x)>=len)  ss[i]='0';
        else if((i-x<0) && ((i+x)<len && w[i+x]=='0')) ss[i]='0';
        else if(((i-x>=0) && w[i-x]=='0') && (i+x)>=len)    ss[i]='0';
    }
    if(s==ss)   cout<<w<<endl;
    else                cout<<"-1"<<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;
}

D. Zigzags

题目大意:

给你一个长度为n的数组,求一个四元组的数量
该四元组的定义:
1 ≤ i < j < k < l ≤ n
ai = ak && aj = al

思路:

直接dp肯定是不行的
考虑枚举其中的两个数后枚举,所以选择枚举中间两个,因为第一个和第四个分别在两边,受到的限制更小
然后提前dp求1 − i 中j的个数,最后计算即可

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=3e3 +9;
int n, a[N], dp[N][N];
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
            else        dp[i][j]=dp[i-1][j];
        }
    }
    int ans=0;
    for(int i=2; i<=n-2; i++){
        for(int j=i+1; j<=n-1; j++){
            ans+=dp[i-1][a[j]]*(dp[n][a[i]]-dp[j][a[i]]);
        }
    }
    cout<<ans<<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;
}


平平无奇的大学在读本科生