Codeforces Round #591 (Div. 2)

A. CME

题目链接：https://codeforces.com/contest/1241/problem/A

题意：

你有 N 根火柴 , 多少根火柴就可以组成多大的数（如三根火柴可以表示 3）, 现在要求你用火柴组成任意三个数 A , B , C 使得 A + B = C 关系成立

如果无论怎么组都无法使等式成立 , 则你可以额外购入 X 根火柴来重新组数使得关系成立 , 求 X 的最小值

分析：

签到题。

特判 N = 2 , X = 2

当 N > 2 时不难发现当 N 为偶数时是肯定可以找到对应的 A , B , C 使得 A + B = C 的 , N 为奇数时肯定是找不到对应的 A , B , C 的 , 所以当 N 为奇数时我们只需要额外购入一根火柴使总共的火柴数为偶数即可

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 3e5 + 10;

int main()
{
    int t ;
    cin >> t;
    while(t--)
    {
        long long  n ;
        cin >> n;
        if(n == 2)
        {
            cout << 2 << endl;
         } 
         else
         {
             if(n & 1) 
             cout << 1 << endl;
             else cout << 0 << endl;
          } 
    }
    return 0;
}

View Code

B. Strings Equalization

题目链接：https://codeforces.com/contest/1241/problem/B

题意：

给定两个字符串 S 和 T , 你可以使 S 串任意相邻的两个位置的字符都变为其中的一个字符 , T 串也可以进行 S 串的操作 , 问将 S 串 T 串任意改变最后能否使得 S = T

分析：

签到题。

只要 S 和 T 串有一个相同的字符 , 那么我们就可以把 S 和 T 都变为只有这个字符的字符串 , 若一个相同字符都不存在则不可能使 S = T

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}

const int N = 3e5 + 10;

int main()
{
    ios;
    int haha;
    cin >> haha;
    string s ,t;
    while(haha--)
    {
        cin >> s >> t;
        int flag = 0;
        int len = s.size();
        for(int i = 0 ; i < len ; i++)
        {
            for(int j = 0 ; j < len ; j++)
            {
                if(s[i] == t[j])
                {
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" <<endl;
    }
    return 0;
}

View Code

C. Save the Nature

题目链接：https://codeforces.com/contest/1241/problem/C

题意：

你有 N 张票和一个预期收入 K , 每张票的价格为 Pi ,你可以从 N 张票中选出任意张票任意摆放

对于选出来的数摆放完后你的收入money = a倍数的位置的票的价格 * x + b倍数的位置的票的价格 * y + lcm(a,b)倍数的位置的票的价格 * (x + y)

// 若某个位置既是 a 或 b 的倍数又是 lcm(a,b)的倍数 , 则它只属于lcm(x,y)的倍数 ; 若某个位置不是 a 不是 b 也不是 lcm(a,b) 的倍数 , 则它能带来的收入为0

问最少可以选出几张票任意摆放后使得 money > K , 若不论怎么选都无法使得money > K , 则输出 -1

分析：

贪心 + 二分答案

从大到小排序后 , 假设挑选出 M 张票（从前往后挑选）

那么票价高的票肯定是要尽可能的放在 lcm(a,b)的位置上 , 若lcm(a,b)的位置不存在则尽可能放在 max(x,y) 对应的 a（b）位置上 , 若max(x,y)对应的a（b）位置也不存在 , 则放在min(x,y)对应的a（b）上

若这些位置都不存在或者最后得到的 money < K , 则说明挑选M 张票还不够; 若最后得到的 money >= K , 则挑选 M 张票可能过多了

所以对答案进行二分查找即可

这里用到前缀和使计算起来方便些(っ•̀ω•́)っ

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);} 
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}
 
const int N = 2e5 + 10;
ll sum[N] , aa[N];
ll n , k , x , y , a, b;
int num1 , num2 , num3;
bool check(int num)
{
    num1 = num / lcm(a,b);
    num2 = num / a - num1;
    num3 = num / b - num1;
    ll res = 0;
    res += (x + y) * sum[num1] + x * (sum[num1 + num2] - sum[num1]) + y * (sum[num1 + num2 + num3] - sum[num1 + num2]);
    return res >= k;
}
bool cmp(ll a, ll b)
{
    return a > b;
}
int main()
{
    ios;
    int t;
    cin >> t;
    while(t--)
    {
        mm(aa , 0) , mm(sum , 0);
        cin >> n;
        rep(i ,1 ,n)
        {
            cin >> aa[i];
            aa[i] /= 100;
        }
        sort(aa + 1 , aa + 1 + n , cmp);
        partial_sum(aa + 1 , aa + 1 + n , sum + 1);
        cin >> x >> a >> y >> b >> k;
        if(x < y){x^=y,y^=x,x^=y,a^=b,b^=a,a^=b;};
        int l = 1 , r = n;
        int ans = n + 1;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(check(mid))
            {
                ans = min(ans , mid);
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if(ans <= n) cout << ans << endl;
        else cout << -1 << endl; 
        
    }
    return 0;
}

View Code

D. Sequence Sorting

题目链接：https://codeforces.com/contest/1241/problem/D

题意：

给你一个长度为 N 的序列 , 你每次操作可以把序列中的相同数字移到序列的最前端或者最末端 , 问最少可以进行多少次操作使得序列为连续上升序列

分析：

求出最多的不需要移动的数字的个数, 那么答案就是总的数字个数 - 最多的不需要移动的数字的个数

对于每个数我们可以用 lef 记录它出现的最左端 , rig 记录它出现的最右端 , 然后用last记录比它小的前一个数字的最右端 , 判断 last 和 lef[ now ]的关系 , 详见代码

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define ll long long
#define numm ch - 48
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pi 3.14159265358979323
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define debug3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define debug4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
using namespace std;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;}
ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;}
 
const int N = 3e5 + 10;
int lef[N] , rig[N] , a[N];
int t , n;
int main()
{
    ios;
    cin >> t;
    while(t--)
    {
        cin >> n;
        map<int , int>haha;
        rep(i ,1 ,n)
        lef[i] = rig[i] = 0;
        rep(i ,1 ,n)
        {
            cin >> a[i];
            if(!haha[a[i]])
            {
                lef[a[i]] = i;    
            }
            rig[a[i]] = i;
            haha[a[i]] = 1;
        }
        int last = 0 , ans = 0 , cnt = 0 , tot = 0;
        rep(i ,1 ,n)
        {
            if(lef[i])
            {
                if(last < lef[i])
                cnt ++;
                else 
                cnt = 1;
                last = rig[i];
                ans = max(ans , cnt);
                tot ++;
            }
        }
        cout << tot - ans << endl;
    }
    return 0;
}