Educational Codeforces Round 137 (Rated for Div. 2)

A. Password

题目描述：

长度为4的数字密码，只能用0到9，你要保证四位数的密码中，只用到了两种数字，且使用的次数都是2，现在给出不能使用的数字，问存在多种符合条件的密码

思路：

组合数，假设可以使用n个数字，则答案是 $C_{n}^{2}*C_{4}^{2}$

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, x;
int tr[MAX];

ll fuck(ll a, ll b){
    ll ans = 1;
    if(a > b / 2)a = b - a;
    for(int i=0;i<a;i++)ans = ans*(b-i)/(i+1);
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n;++i)cin >> x;
    cout << fuck(2, 10 - n) * 6 << '\n';
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

B. Permutation Value

题目描述：

构造一个全排列，记子串为全排列的数量为num，要求num尽可能少，输出这个排列

思路：

只要把1和n放在一起，则num=2，最小，此时只有1和1 2 3…n这两种全排列

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    cout << 1 << ' ' << n << ' ';
    for(int i = 2; i < n; ++i){
        cout << i << ' ';
    }
    cout << endl;
}


int main(){
    io;
    int t;cin>>t;while(t--)
    work();
    return 0;
}

C. Save the Magazines

题目描述：

给出一个长度为n的01串，和一个长度为n的数组，一个01字符对应一个数字，如果是1，则对应位置的值可取，否则不可取，若s[i]='1'&&s[i-1]='0'则可以将该1移动到i-1的位置上去，此时i的位置是0，问能取的数字的最大价值是多少

思路：

简单dp

dp[i][0]表示1-i中，第i个字符是0时的最大价值

dp[i][1]表示1-i中，第i个字符时1时的最大价值

• 当ar[i]='1'时

  • dp[i][1]=max(dp[i][0],dp[i][1])+tr[i]
  • dp[i][0]=dp[i-1][0]+tr[i-1]

• 当ar[i]='0'时

  • dp[i][1] = -inf
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1])

 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
char ar[MAX];
int tr[MAX];
int dp[MAX][2];
void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= n; ++i){
        if(ar[i] == '1'){
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]) + tr[i];
            dp[i][0] = dp[i-1][0]+tr[i-1];
        }
        else{
            dp[i][1] = -inf;
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        }
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

D. Problem with Random Tests

题目描述：

给出一个01串，你需要选择任意两个子串，变成十进制后进行或运算，输出或操作后的最大值

思路：

其中的一个串一定是原串，因为显然串的有效长度越长，数字越大

排除前导0后的串就是有效的串，所以我们先扔掉前导0

首先二进制数第i位是1的值一定大于第i是0的值，无论i后面存在多少个1，这是二进制的性质

所以我们要尽可能的让第一个0的位置变成1

假设第一个0的位置是id, 因为两个二进制数进行位运算的时候是末尾对齐，所以要想把0的位置或成1，则需要一个首位是1的且长度为n-id+1的串，所以长度固定了，起始位置也固定了，即1到id-1

再加上这个题的数据完全随机，即0和1出现的概率是50%，所以出现连续的1的概率很小，小到可以忽略，所以串的数量不会很多，暴力跑出来就行，求一个最大值

记得扣掉前导0

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m, k, x;
char tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    int num = 0;
    for(int i = 1; i <= n;++i){
        if(tr[i] == '1'){
            break;
        }
        else{
            num = i;
        }
    }
    if(num == n){
        cout << 0 << endl;
        return;
    }
    int id = -1;
    int len = -1;
    for(int i = num+1; i <= n; ++i){
        if(tr[i] == '0'){
            id = i;
            len = n - i + 1;
            break;
        }
    }
    string ans = "";
    for(int i = num+1; i < id; ++i){
        string fuck = "";
        for(int j = 0; j < len; ++j){
            if(tr[i+j] == '1' || tr[id+j] == '1'){
                fuck += '1';
            }
            else fuck += '0';
        }
        ans = max(ans, fuck);
    }
    for(int i = num+1; i < id; ++i)cout << tr[i];
    cout << ans<<endl;
}


int main(){
    io;
    work();
    return 0;
}