Codeforces Round #767 (Div. 2) ABCD题解

Codeforces Round #767 (Div. 2) ABCD题解 A. Download More RAM

思路：
签 到 题 签到题 签到题
按 照 a 从 小 到 大 排 序 按照a从小到大排序 按照a从小到大排序
只 要 k > = 对 应 的 b ， 就 + = b 只要k>=对应的b，就+=b 只要k>=对应的b，就+=b
输 出 k 即 可 输出k即可 输出k即可
时间复杂度： O n l o g n onlogn Onlogn

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define cf int _; cin>> _; while(_--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define sf(x) scanf("%lld",&x)
#define pll pair 
#define re register int
#define lb lower_bound
#define up upper_bound
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
inline void sf2(int &a , int &b) { sf(a) , sf(b) ;}
inline void sf3(int n , int a[]) {fer(i,1,n) sf(a[i]);} ;
inline void de(auto x) {cout << x << "n" ;}
inline void de2(auto a , auto b) {cout << a << " " << b << "n" ;}
inline void de3(int n , auto a[]){fer(i,1,n) cout << a[i] << " " ;puts("");}
inline void mo(int &a , int b) {a = (a % b + b) % b ;}
inline int gcd(int a,int b){return b ? gcd(b , a % b) : a ;}
inline int qpow(int a,int b,int c){int res=1%c;a%=c;while(b>0){if(b&1)res=res*a%c;a=a*a%c;b>>=1;}return res;}
inline int qadd(int a,int b,int c){int res=0;a%=c;while(b>0){if(b&1)res=(res+a)%c;a=(a+a)%c;b>>=1;}return res;} 
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ;
const double eps = 1e-7 , pi = acos(-1.0) ;
 
int n , k ;
struct ai{
    int a , b ;
}q[N] ;
bool cmp(ai x , ai y)
{
    return x.a < y.a ;
}
 
signed main()
{
    cf
    {
        cin >> n >> k ;
        fer(i,1,n) sf(q[i].a) ;
        fer(i,1,n) sf(q[i].b) ;
        
        sort(q + 1 , q + 1 + n , cmp) ;
        
        fer(i,1,n)
        {
            if(k >= q[i].a)
                k += q[i].b ;
        }
        
        de(k) ;
    }
    return 0;
}

B. GCD Arrays

思路：
读 完 题 目 第 一 个 想 到 的 就 是 g c d ( x , x + 1 ) = 1 读完题目第一个想到的就是gcd(x,x+1)=1 读完题目第一个想到的就是gcd(x,x+1)=1
显 然 这 个 性 质 不 是 特 别 关 键 显然这个性质不是特别关键 显然这个性质不是特别关键

在 仔 细 想 想 ， 只 要 可 能 的 g c d > 1 即 可 在仔细想想，只要可能的gcd>1即可 在仔细想想，只要可能的gcd>1即可
2 又 是 除 1 之 外 ， [ l , r ] 中 因 数 最 多 的 一 个 数 2又是除1之外，[l,r]中因数最多的一个数 2又是除1之外，[l,r]中因数最多的一个数
所 以 g c d > 1 ， 具 体 是 多 少 ， *** 作 数 最 小 的 一 定 是 2 所以gcd>1，具体是多少， *** 作数最小的一定是2 所以gcd>1，具体是多少， *** 作数最小的一定是2

那 么 统 计 一 下 [ l , r ] 中 有 多 少 个 奇 数 那么统计一下[l,r]中有多少个奇数 那么统计一下[l,r]中有多少个奇数
奇 数 是 一 定 要 和 另 外 一 个 偶 数 乘 起 来 奇数是一定要和另外一个偶数乘起来 奇数是一定要和另外一个偶数乘起来
所 以 如 果 奇 数 小 于 等 于 k ， 输 出 Y E S 所以如果奇数小于等于k，输出YES 所以如果奇数小于等于k，输出YES

在 特 殊 判 断 一 下 a = b ， 并 且 a ! = 1 的 情 况 在特殊判断一下a=b，并且a!=1的情况 在特殊判断一下a=b，并且a!=1的情况
因 为 g c d ( a , a ) = a [ a ! = 1 ] 因为gcd(a,a) = a [ a != 1] 因为gcd(a,a)=a[a!=1]
这 种 情 况 也 是 Y E S 这种情况也是YES 这种情况也是YES
时间复杂度： O t Ot Ot

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define cf int _; cin>> _; while(_--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define sf(x) scanf("%lld",&x)
#define pll pair 
#define re register int
#define lb lower_bound
#define up upper_bound
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
inline void sf2(int &a , int &b) { sf(a) , sf(b) ;}
inline void sf3(int n , int a[]) {fer(i,1,n) sf(a[i]);} ;
inline void de(auto x) {cout << x << "n" ;}
inline void de2(auto a , auto b) {cout << a << " " << b << "n" ;}
inline void de3(int n , auto a[]){fer(i,1,n) cout << a[i] << " " ;puts("");}
inline void mo(int &a , int b) {a = (a % b + b) % b ;}
inline int gcd(int a,int b){return b ? gcd(b , a % b) : a ;}
inline int qpow(int a,int b,int c){int res=1%c;a%=c;while(b>0){if(b&1)res=res*a%c;a=a*a%c;b>>=1;}return res;}
inline int qadd(int a,int b,int c){int res=0;a%=c;while(b>0){if(b&1)res=(res+a)%c;a=(a+a)%c;b>>=1;}return res;} 
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ;
const double eps = 1e-7 , pi = acos(-1.0) ;
 
int get(int x) // 返回1-x中有多少个奇数
{
    return (x + 1) / 2 ;
}
 
signed main()
{
    cf
    {
        int a , b , k ;
        sf2(a , b) , sf(k) ;
        
        int s = get(b) - get(a - 1) ;
        if(s <= k || (a == b && a != 1)) puts("YES") ;
        else puts("NO") ;
        
    }
    return 0;
}

C. Meximum Array

思路：
首 先 要 让 字 典 序 最 大 首先要让字典序最大 首先要让字典序最大
那 么 肯 定 优 先 选 最 大 的 那么肯定优先选最大的 那么肯定优先选最大的

我 们 可 以 发 现 答 案 的 第 一 个 数 是 整 个 序 列 里 面 的 M E X 我们可以发现答案的第一个数是整个序列里面的MEX 我们可以发现答案的第一个数是整个序列里面的MEX
那 么 我 们 首 先 消 除 的 前 k 个 数 那么我们首先消除的前k个数 那么我们首先消除的前k个数

要 保 证 这 k 个 数 的 M E X = 整 个 序 列 的 M E X 要保证这k个数的MEX=整个序列的MEX 要保证这k个数的MEX=整个序列的MEX
并 且 保 证 k 最 小 ， 这 样 你 可 以 选 更 多 的 数 并且保证k最小，这样你可以选更多的数 并且保证k最小，这样你可以选更多的数

删 掉 之 后 的 下 一 个 数 是 剩 下 一 整 个 序 列 的 M E X 删掉之后的下一个数是剩下一整个序列的MEX 删掉之后的下一个数是剩下一整个序列的MEX
模 拟 上 述 过 程 即 可 模拟上述过程即可 模拟上述过程即可

具 体 可 以 看 代 码 细 节 具体可以看代码细节 具体可以看代码细节
时间复杂度： O n On On

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define cf int _; cin>> _; while(_--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define sf(x) scanf("%lld",&x)
#define pll pair 
#define re register int
#define lb lower_bound
#define up upper_bound
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
inline void sf2(int &a , int &b) { sf(a) , sf(b) ;}
inline void sf3(int n , int a[]) {fer(i,1,n) sf(a[i]);} ;
inline void de(auto x) {cout << x << "n" ;}
inline void de2(auto a , auto b) {cout << a << " " << b << "n" ;}
inline void de3(int n , auto a[]){fer(i,1,n) cout << a[i] << " " ;puts("");}
inline void mo(int &a , int b) {a = (a % b + b) % b ;}
inline int gcd(int a,int b){return b ? gcd(b , a % b) : a ;}
inline int qpow(int a,int b,int c){int res=1%c;a%=c;while(b>0){if(b&1)res=res*a%c;a=a*a%c;b>>=1;}return res;}
inline int qadd(int a,int b,int c){int res=0;a%=c;while(b>0){if(b&1)res=(res+a)%c;a=(a+a)%c;b>>=1;}return res;} 
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ;
const double eps = 1e-7 , pi = acos(-1.0) ;
 
int n ;
int a[N] ;
int st[N] ;
int s[N] ;
 
signed main()
{
    cf
    {
        cin >> n ;
        fer(i,0,n) st[i] = 0 ;
        fer(i,1,n) sf(a[i]) , st[a[i]] ++ ;
        int k = 0 ;
        while(st[k]) k ++ ;
        // k为整个序列的MEX
        vector v ;
        // v数组记录答案
        
        int t = 0 ; 
        // t表示从0到k-1出现了多少个数
        fer(i,0,k) s[i] = 0 ;
        for(int i = 1 ; i <= n ; i ++)
        {
            if(a[i] <= k - 1)
            {
                if(!s[a[i]])
                {
                    s[a[i]] ++ ;
                    t ++ ;
                }
                else s[a[i]] ++ ;
            }
            
            if(t == k) // 如果连续出现的数的个数=k了
            {
                v.pb(k) ;
                fer(i,0,k - 1) st[i] -= s[i] ;
                // 在st数组里面减掉这些数的出现次数
                t = 0 ; 
                k = 0 ;
                while(st[k]) k ++ ;
                // 重新找到整个序列的MEX
                fer(i,0,k) s[i] = 0 ;
            }
        }
        
        // 输出答案
        de(sz(v)) ;
        for(auto i : v) cout << i << " " ;
        puts("") ;
        
    }
    return 0;
}

D. Peculiar Movie Preferences

思路：
如 果 出 现 了 同 一 个 字 母 组 成 的 字 符 串 一 定 为 Y E S 如果出现了同一个字母组成的字符串一定为YES 如果出现了同一个字母组成的字符串一定为YES

在 考 虑 长 度 为 2 的 字 符 串 在考虑长度为2的字符串 在考虑长度为2的字符串
x y 和 y x 同 时 出 现 说 明 可 以 xy和yx同时出现说明可以 xy和yx同时出现说明可以

在 考 虑 长 度 为 3 的 字 符 串 在考虑长度为3的字符串 在考虑长度为3的字符串
x y z 和 z y x 同 时 出 现 说 明 可 以 xyz和zyx同时出现说明可以 xyz和zyx同时出现说明可以

在 考 虑 长 度 为 2 和 3 的 拼 接 在考虑长度为2和3的拼接 在考虑长度为2和3的拼接
如 果 出 现 了 x y z y x [ x y z + y x ] 如果出现了xyzyx[xyz+yx] 如果出现了xyzyx[xyz+yx]
x y z 在 前 面 y x 在 后 面 xyz在前面yx在后面 xyz在前面yx在后面

或 者 是 x y z y x [ x y + z y x ] 或者是xyzyx[xy+zyx] 或者是xyzyx[xy+zyx]
x y 在 前 面 , z y x 在 后 面 xy在前面,zyx在后面 xy在前面,zyx在后面
这 2 种 情 况 都 可 以 这2种情况都可以 这2种情况都可以
其 他 情 况 均 为 不 可 能 其他情况均为不可能 其他情况均为不可能

为 什 么 不 讨 论 2 个 长 度 为 3 和 3 个 长 度 为 2 的 拼 接 为什么不讨论2个长度为3和3个长度为2的拼接 为什么不讨论2个长度为3和3个长度为2的拼接
因 为 如 果 出 现 了 这 样 的 情 况 ， 说 明 一 定 出 现 了 长 度 为 2 和 3 的 拼 接 因为如果出现了这样的情况，说明一定出现了长度为2和3的拼接 因为如果出现了这样的情况，说明一定出现了长度为2和3的拼接
时间复杂度： O n l o g n onlogn Onlogn

#include 
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define cf int _; cin>> _; while(_--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define sf(x) scanf("%lld",&x)
#define pll pair 
#define re register int
#define lb lower_bound
#define up upper_bound
#define int long long 
#define pb push_back
#define y second 
#define x first 
using namespace std;
inline void sf2(int &a , int &b) { sf(a) , sf(b) ;}
inline void sf3(int n , int a[]) {fer(i,1,n) sf(a[i]);} ;
inline void de(auto x) {cout << x << "n" ;}
inline void de2(auto a , auto b) {cout << a << " " << b << "n" ;}
inline void de3(int n , auto a[]){fer(i,1,n) cout << a[i] << " " ;puts("");}
inline void mo(int &a , int b) {a = (a % b + b) % b ;}
inline int gcd(int a,int b){return b ? gcd(b , a % b) : a ;}
inline int qpow(int a,int b,int c){int res=1%c;a%=c;while(b>0){if(b&1)res=res*a%c;a=a*a%c;b>>=1;}return res;}
inline int qadd(int a,int b,int c){int res=0;a%=c;while(b>0){if(b&1)res=(res+a)%c;a=(a+a)%c;b>>=1;}return res;} 
const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;
const int N = 1e6 + 10 , M = 3010 , mod = 1e9 + 7 ;
const double eps = 1e-7 , pi = acos(-1.0) ;
 
int n ;
string q[N] ;
 
signed main()
{
    cf
    {
        cin >> n ;
        int f1 = 0 ;
        map mp , p;
        fer(i,1,n) 
        {
            cin >> q[i] , mp[q[i]] ++ ;    
            if(sz(q[i]) == 1) f1 = 1 ;
            else if(sz(q[i]) == 2) 
            {
                if(q[i][0] == q[i][1]) 
                    f1 = 1 ;
            }
            else 
            {
                if(q[i][0] == q[i][1] && q[i][0] == q[i][2])
                    f1 = 1 ;
            }
            // 如果出现了同一个字母组成的字符串一定为YES
        }
        
        fer(i,1,n)
        {
            p[q[i]] ++ ;
            if(sz(q[i]) == 2)
            {
                string t = q[i] ;
                reverse(all(t)) ;
                if(mp[t]) f1 = 1 ;
                // xy和yx同时出现说明可以
            }
            else if(sz(q[i]) == 3)
            {
                string t1 = "" ;
                string t2 = "" ;
                
                string t = q[i] ;
                reverse(all(t)) ;
                if(mp[t]) f1 = 1 ;
                // xyz和zyx时出现说明可以
                
                fer(j,1,2) t1 = t1 + q[i][j] ;
                fer(j,0,1) t2 = t2 + q[i][j] ;
                
                reverse(all(t1)) ;
                reverse(all(t2)) ;
                if(p[t1] || mp[t2]) f1 = 1 ;
                // 如果出现了xyzyx[xyz+yx]
                // 或者是xyzyx[xy+zyx] 也说明可以
            }
            mp[q[i]] -- ;
        }
        
        if(f1) puts("YES") ;
        else puts("NO") ;
    }
    return 0;
}