Codeforces Global Round 17题解A-D

Codeforces Global Round 17 A. Anti Light’s Cell Guessing 分析：

考虑0的情况就行了。

代码：

#include 
using namespace std;
//#pragma GCC optimize(2)
#define close(); 	ios::sync_with_stdio(false);
#define endl 'n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;

void solve()
{
    int a, b; cin >> a >> b;
    if(a > b) swap(a, b);
    if(a == 1 && b == 1) cout << 0 << endl;
    else if(a == 1) cout << 1 << endl;
    else cout << 2 << endl;
}

int main()
{
    int T; cin >> T;
    while(T--) solve();
    // system("pause");
}

B. Kalindrome Array 分析:

不妨记字符串为s, 长度为m.

分以下情况讨论:

1. 本身是回文串, 输出yes
2. 本身不是回文串, 那么一定存在一对 s i ! = s j , i = m + 1 − j s_i!=s_j, i = m+1-j si​!=sj​,i=m+1−j.
   • 考虑把 s i s_i si​类的字符全部删掉, 再看一遍是不是回文串.
   • 考虑把 s j s_j sj​类的字符全部删掉, 再看一遍是不是回文串.

为什么是将其类字符全部删掉呢, 这好像和题干有点不太一样. 实际上, 即便不删掉其类字符也是匹配的本身, 和全删掉的情况下判是否是回文串是等价的.

代码:

#include 
using namespace std;
//#pragma GCC optimize(2)
#define close(); 	ios::sync_with_stdio(false);
#define endl 'n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;

int a[N];

bool check(int n, int x)
{
    int l = 1, r = n;
    while(l < r)
    {
        while(l < r && a[l] == a[x]) l++;
        if(l >= r) break;
        while(l < r && a[r] == a[x]) r--;
        if(l >= r) break;
        if(a[l] == a[r]) l++, r--;
        else if(a[l] != a[r]) return 0;
    }
    return 1;
}

void solve()
{
    int n; cin >> n;
    rep(i, 1, n) cin >> a[i];
    int l = 1, r = n;
    int u, v; u = v = 0;
    while(l < r) 
    {
        if(a[l] == a[r]) l++, r--;
        else 
        {
            u = l;
            v = r;
            break;
        }
    }
    bool f = 0;
    if(u == v) f = 1;
    else 
    {
        f |= check(n, u);
        f |= check(n, v);
    }
    if(f) cout << "YESn";
    else cout << "NOn";
}

int main()
{
    close();
    int T; cin >> T;
    while(T--) solve();
    // system("pause");
}

C. Keshi Is Throwing a Party 分析:

一开始我考虑了一会反悔贪心, 发现不可做.

然后发现是***useful algorithm***二分.

当我们确定我们要check的人数的时候, 直接贪心地找. 不懂的话看代码.

时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)

代码:

#include 
using namespace std;
//#pragma GCC optimize(2)
#define close(); 	ios::sync_with_stdio(false);
#define endl 'n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;

int a[N], b[N];
int n; 
bool check(int x)
{
    int cnt = 0;
    rep(i, 1, n)
    {
        if(a[i] >= x-cnt-1 && b[i] >= cnt)
        {
            cnt++;
        }
        if(cnt == x) return 1;
    }
    return 0;
}

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> a[i] >> b[i];

    int l = 1, r = n;    
    while(l < r)
    {
        if(l == r-1) 
        {
            if(check(r)) l = r;
            else r = l;
            break;
        }
        int mid = l+r>>1;
        if(check(mid)) l = mid;
        else r = mid-1;
    }
    cout << l << endl;
}

int main()
{
    close();
    int T; cin >> T;
    while(T--) solve();
    // system("pause");
}

D. Not Quite Lee 分析：

考虑一个有 k k k个元素的数组 c c c，如何去判断是否为good。

我们发现对于每个 c i ∈ c c_iin c ci​∈c, 其整数的连续序列的和为 c i ( c i − 1 ) 2 + x i c i frac{c_i(c_i-1)}{2}+x_ic_i 2ci​(ci​−1)​+xi​ci​， 其中 x i x_i xi​为任意整数。

于是我们可以将一个数组c是否good等价地转换为这个式子：
0 = ∑ i = 1 k c i ( c i − 1 ) 2 + x i c i 0 = sum_{i=1}^k frac{c_i(c_i-1)}{2}+x_ic_i 0=i=1∑k​2ci​(ci​−1)​+xi​ci​
观察这个式子, 发现这个东西我们很熟悉, 不妨定义 t t t为下式:
t = ∑ i = 1 k x i c i t = sum_{i=1}^k x_ic_i t=i=1∑k​xi​ci​
根据裴蜀定理, g c d ( c 1 , c 2 , . . . , c k ) ∣ t gcd(c_1, c_2, ... , c_k) | t gcd(c1​,c2​,...,ck​)∣t

记 s = ∑ i = 1 k c i ( c i − 1 ) 2 , g = g c d ( c 1 , c 2 , . . . , c k ) s = sum_{i=1}^k frac{c_i(c_i-1)}{2}, g = gcd(c_1, c_2, ... , c_k) s=∑i=1k​2ci​(ci​−1)​,g=gcd(c1​,c2​,...,ck​)

于是判定一个数组c是否good的问题转换成了: g是否可以整除s.

考虑对于数组c存在奇数的时候:

1. 数组c存在奇数和偶数, 那么 g = 1 g=1 g=1, 有解.
2. 数组c只存在奇数, 那么让所有连续序列的中点置于零点, s = 0, 有解.

于是接下来我们只需要考虑数组c只存在偶数的情况.

观察到这么一个事实: 如果奇数y整除偶数x, 那么 y ∣ x 2 y|frac{x}{2} y∣2x​; 如果偶数y整除偶数x, 那么 y 2 ∣ x 2 frac{y}{2}|frac{x}{2} 2y​∣2x​

考虑到枚举g是时间不可行的, 因此我们尝试建立一个1-1映射来减少我们需要枚举的约数.

对于 g ∣ s g|s g∣s, 显然s是偶数, g也是偶数(奇数已经算完了), 那么 g 2 l ∣ s 2 l frac{g}{2^l}|frac{s}{2^l} 2lg​∣2ls​. 其中$2^l | g space $ 且   2 l + 1 ∤ g space2^{l+1} not | g  2l+1​∣g, 也就是说 2 l 2^l 2l是g的最大的2的整次幂因子.

注意: 这里因为奇数都被我们提前处理了, 所以 l ≥ 1 lge 1 l≥1

于是我们不妨把g映射到 2 l 2^l 2l上, 这显然是一个1-1映射. 具体操作如下:

对于数组c中所有可以被 2 l 2^l 2l整除但不能被$ 2^{l+1} $整除的元素, 放入集合A.

对于数组c中所有可以被 2 l + 1 2^{l+1} 2l+1整除的元素, 放入集合B.

显然对于任意包含集合A中的偶数个元素的任意组合, 其g的映射都是 2 l 2^l 2l.

为什么包含集合A中的奇数个元素不是呢? 观察单个元素, 不妨记为 e = k 2 l e = k2^l e=k2l, 其中k为奇数. 那么 e ( e − 1 ) 2 = k 2 l − 1 ( k 2 l − 1 ) frac{e(e-1)}{2} = k2^{l-1}(k2^l-1) 2e(e−1)​=k2l−1(k2l−1), 这是一个最大的2的整次幂因子为 2 l − 1 2^{l-1} 2l−1的数. 那显然s 的最大的2的整次幂因子也为 2 l − 1 2^{l-1} 2l−1.

但如果是偶数个集合A元素就可以解决这个问题.

设数组c中所有可以被 2 l 2^l 2l整除但不能被$ 2^{l+1} $整除的元素的个数为 a a a; 数组c中所有可以被 2 l + 1 2^{l+1} 2l+1整除的元素的个数为 b b b.

那么 2 l 2^l 2l的答案为 2 a − 1 ⋅ 2 b 2^{a-1}cdot 2^b 2a−1⋅2b

枚举 l l l统计答案即可.

总的时间复杂度是 O ( n log ⁡ ( 1 e 9 ) ) O(nlog(1e9)) O(nlog(1e9))

代码:

#include 
using namespace std;
//#pragma GCC optimize(2)
#define close(); 	ios::sync_with_stdio(false);
#define endl 'n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
const LL p = 1e9+7;
LL qpow(LL a, LL b)
{
    LL rev = 1;
    while(b){
        if(b&1) rev = rev * a % p;
        a = a * a % p;
        b>>=1;
    }
    return rev;
}

LL a[N];

int main()
{
    // close();

    int n; cin >> n;
    rep(i, 1, n) cin >> a[i];
    LL ans = 0;
    LL even = 0;
    rep(i, 1, n) 
    {
        if(a[i] & 1) ; else even++; 
    }
    ans = (qpow(2, n) - qpow(2,even)) % p;
    rep(i, 1, 31)
    {
        LL x = 1ll< 0) (ans += ((qpow(2, o-1)-1+p)%p) * ((qpow(2, e))%p) ) %= p;
    }
    
    cout << ans << endl;

    // system("pause");
}

E. AmShZ and G.O.A.T.

赶作业, 有空再补