【Codeforces】Hello 2019

作者: Caproner | 来源:发表于2019-01-06 15:41 被阅读0次

Problem A

逐个判断即可。
时间复杂度为 $O(1)$ 。

#include <bits/stdc++.h>

using namespace std;

string s[10];

int main()
{
    for(int i = 0; i < 6; I++)
        cin >> s[i];
    bool ans = false;
    for(int i = 1; i < 6; I++)
    {
        if(s[0][0] == s[i][0] || s[0][1] == s[i][1])
        {
            ans = true;
            break;
        }
    }
    if(ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Problem B

注意到 $n$ 最大只有15，故可以使用暴力来解决。
直接枚举所有可能性，逐个尝试即可。
使用位运算实现枚举可以比较便利地枚举完所有的情况。
当然，DFS也是可以的。
时间复杂度为 $O(2^n)$ 。

#include <bits/stdc++.h>

using namespace std;

bool check(int a[], int n, int bitmp)
{
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(bitmp & 1)
            ans += a[i];
        else
            ans -= a[i];
        bitmp >>= 1;
    }
    return ans % 360 == 0;
}

int main()
{
    int a[20], n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    bool ans = false;
    for(int bitmp = 0; bitmp < (1 << n); bitmp++)
    {
        ans |= check(a, n, bitmp);
        if(ans)
            break;
    }
    
    if(ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Problem C

检查括号是否匹配这个使用栈便可以解决，这里假设大家已经知道如何检查括号匹配。
大致思想是将字符串分类，然后按类进行匹配。

字符串大致可以分为四类：

自己就已经是匹配的，例如()，(())，()(())
需要在右边再添加k个右括号才能匹配的（简称mpL[k]），例如(（还差一个），(()（还差一个），()(()(（还差两个）
需要在左边再添加k个左括号才能匹配的（简称mpR[k]）
无法在只拼接一个括号字符串之后就能匹配的，例如)(
分类的话，只需要将用栈检查括号匹配的算法稍微修改一下就可以做了（具体
参照代码的Caclu函数）

分类完毕之后，匹配的方案如下：

对于每个k而言，mpL[k]和mpR[k]匹配（也就是取两者计数最小值）
对于自己就已经是匹配的而言（在代码中为mpR[0]），在这个集合内匹配就行了（也就是取计数除以2）

这里分类使用map实现，故时间复杂度为 $O(sum(len)+n{\log}n)$

//#define TEST

#include <bits/stdc++.h>

using namespace std;

map<int, int> mpL, mpR;

void Caclu(string &s)
{
    #ifdef TEST
    cout << "Begin: " << s << endl;
    #endif
    int stk = 0;
    for(int i = 0; i < s.length(); i++)
    {
        if(s[i] == '(')
            stk++;
        else
            stk--;
        if(stk < 0)
            break;
    }
    if(stk > 0)
    {
        mpL[stk]++;
        #ifdef TEST
        cout << "L: " << stk << endl;
        #endif
    }
    
    stk = 0;
    for(int i = s.length() - 1; i >= 0; i--)
    {
        if(s[i] == ')')
            stk++;
        else
            stk--;
        if(stk < 0)
            break;
    }
    if(stk >= 0)
    {
        mpR[stk]++;
        #ifdef TEST
        cout << "R: " << stk << endl;
        #endif
    }
}

int main()
{
    mpL.clear();
    mpR.clear();
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        Caclu(s);
    }
    
    int ans = 0;
    map<int, int>::iterator it;
    for(it = mpL.begin(); it != mpL.end(); it++)
    {
        ans += min(it->second, mpR[it->first]);
    }
    ans += mpR[0] / 2;
    cout << ans << endl;
    return 0;
}

Problem D

首先考虑一个简化版的问题：假设n为某个质数p的a次幂。求问题的解。
这个的话可以直接dp就行了。假设dp[a][k]为当n为p的a次幂的时候的解。
于是就有： $dp[a][k]={\frac {{\sum _{i=0} ^{a-1}}dp[i][k-1]} {a+1}}$
这个dp的时间复杂度为 $O(ak)$ ，也就是 $O(k{\log}n)$

那么对于复杂版本的，n为任意正整数的情况。
首先我们假设答案为 $ans_k(n)$ 。
由于作者能力有限，无法给出一个详细且严谨的证明。不过可以通过小范围数据打表发现，当k固定的时候， $ans_k(n)$ 为积性函数。
于是我们可以把n分解质因数，得到 $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}p_4^{a_4}...$
于是就有： $ans_k(n)=ans_k({p_1^{a_1}})*ans_k(p_2^{a_2})*ans_k(p_3^{a_3})*ans_k(p_4^{a_4})*...$
至于每一个分解出来的函数，就是上面的简化版问题了。直接按照上面的计算即可。
至于在 $1e9+7$ 下的除法的话，逆元即可。
不过由于魔导书（Code Template）不知道被我扔哪里去了，所以只能自己手敲逆元。
分解质因数需要 $O({\sqrt n})$ 的时间，故总的时间复杂度为 $O({\sqrt n}+k{\log}n)$

#include <iostream>
#include <map>
#include <vector>

using namespace std;

typedef long long LL;

const LL mod = 1e9+7;

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 1;
        return;
    }
    LL px, py;
    exgcd(b, a%b, px, py);
    x = py;
    y = px - (a / b) * py;
}

LL inv(LL a)
{
    LL x, y;
    exgcd(a, mod, x, y);
    return ((x % mod) + mod) % mod;
}

map<LL, int> cnt;

void Analysis(LL n)
{
    for(LL i = 2; i * i <= n; i++)
    {
        while(n % i == 0)
        {
            cnt[i]++;
            n /= i;
        }
    }
    if(n != 1)
    {
        cnt[n]++;
    }
}

LL Solve(LL n, LL k)
{
    LL ret = 1;

    Analysis(n);
    map<LL, int>::iterator it = cnt.begin();
    for(; it != cnt.end(); it++)
    {
        vector<LL> v;
        v.push_back(1LL);
        for(int i = 0; i < it->second; i++)
        {
            v.push_back((v[v.size()-1] * it->first) % mod);
        }

        for(int i = 0; i < k; i++)
        {
            for(int j = 1; j < v.size(); j++)
            {
                v[j] = (v[j] + v[j-1]) % mod;
            }
            for(int j = 1; j < v.size(); j++)
            {
                v[j] *= inv(j + 1);
                v[j] %= mod;
            }
        }

        ret = (ret * v[v.size()-1]) % mod;
    }

    return ret;
}

int main()
{
    LL n, k;
    cin >> n >> k;
    cout << Solve(n, k) << endl;
    return 0;
}

Problem E

首先，这题我写不出来的orz。。这题到最后迫不得已只能放弃思考，对着官方题解思考许久，才发现自己连题都读错了orz
所以下面的题解基本上等于官方题解的翻译版。如果啃过官方题解的话会发现下面这个基本等于把官方题解复读一遍orz

大致的题意是，给定一个n个数的排列，将其拆分为k个单调的子序列。
这里很多人会读错然后认为求的是令k尽可能小的结果（为了下文描述方便，这里将尽可能小的问题简称为最小拆分），然后想了贼久百思不得其解最后放弃。
但是这里的k其实并不需要尽可能小，而是只需要小于等于 $f(n)$ 即可。
其中关于 $f(n)$ 的定义如下：

n个数的所有排列中，每个排列可以拆分的最少的单调子序列数，这些数的最大值定义为 $f(n)$

这个事实上是一道结论题。它需要基于如下结论：

设正整数 $k$ 满足 ${\frac {k(k+1)} {2}}{\leq}n<{\frac {(k+1)(k+2)} {2}}$ ，则有 $f(n)=k$

显然满足条件的k是唯一的。
这个结论事实上由两部分构成：

当 $n{\geq}{\frac {k(k+1)} {2}}$ 时，总会有一个n的排列使其最小拆分必定大于等于k
当 $n<{\frac {k(k+1)} {2}}$ 时，所有的n的排列的最小拆分必定小于k（换言之，最大为k-1）

这里分别给出这两个部分的不严谨证明：

结论一证明

对于存在性结论的话，只需要给出一个构造方法即可。
这里假设n=10，k=4。那么可以给出如下序列： $\{1,3,2,6,5,4,10,9,8,7\}$
注意到这个序列是有规律的。这也是当n恰好等于 ${\frac {k(k+1)} {2}}$ 时的构造策略。此时显然的，该序列的最小拆分是4。刚好为k。
那么当出现n不恰好为 ${\frac {k(k+1)} {2}}$ 的情况的话，只需要找到最大的满足
$n{\geq}{\frac {k(k+1)} {2}}$ 的k，然后将前k个数按如上规律构造，剩下的数堆到后面即可。
具体的可以自己尝试一下。

结论二证明

首先对n的排列求LIS（最长上升子序列）。于是就会有两种情况：

LIS的长度大于等于k
LIS的长度小于k

对于第一种情况，将这个LIS中从原序列中去掉，于是原序列的数字个数变为小于 ${\frac {k(k-1)} {2}}$ 个。这个问题其实就是原问题的 $k-1$ 版本。递归求证即可。

对于第二种情况，我们可以使用求LIS的方法构造出个数等于LIS长度的递减序列。由于序列数等于LIS长度，故小于k。命题得证。

这里重点说一下如何构造吧。前提是需要懂得LIS的 $O(n{\log}n)$ 求法。
首先，类比LIS求法需要构造一个用来存中间结果的数组 $b$ 一样，这里同样需要构造一个二维数组 $b$ （事实上更像是两重vector）。
然后遍历原序列，对于每个数 $a[i]$ 而言：

如果二维vector $b$ 全空，或者对于二维vector $b$ 中的每个小vector的最后一个数都小于 $a[i]$ ，那么新建一个vector，其仅存入元素 $a[i]$ ，并将这个vector尾部插入至二维vector $b$ 中
否则，二分查找到所有尾部元素小于 $a[i]$ 的vector的最大值，在这个vector中尾部插入 $a[i]$

事实上这个过程就是保留历史数据的LIS的 $O(n{\log}n)$ 求法。到最后每个vector的尾部元素连起来就是原序列的LIS了。故通过这样分割的递减序列的个数肯定跟LIS的长度一致。

运用结论解题

事实上结论二的证明思路就是一个构造思路了。对于任意序列，按照结论二的证明思路构造即可得到答案。
总的时间复杂度为 $O(n{\sqrt n}{\log}n)$ （我甚至不知道为啥这么爆炸的复杂度都能卡过去orz）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <ctime>

using namespace std;

typedef long long LL;

// 为了之后方便复用，把求LIS的过程抽成单独的模块
struct LIS
{
    int w[100005];
    int prt[100005];
    int dp[100005];
    int dp_pos[100005];
    int n, top;
    bool isInc;

    bool check(int a, int b)
    {
        return (a > b) ^ isInc;
    }

    void Init(bool _isInc)
    {
        n = 0;
        top = 0;
        isInc = _isInc;
    }

    void Update(int a)
    {
        w[n] = a;
        int l = 0, r = top - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(check(dp[mid], a))
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }

        if((top == 0) || check(dp[l], a))
        {
            dp[top] = a;
            dp_pos[top] = n;
            if(top == 0)
            {
                prt[n] = n;
            }
            else
            {
                prt[n] = dp_pos[top - 1];
            }
            top++;
        }
        else
        {
            dp[l] = a;
            dp_pos[l] = n;
            if(l == 0)
            {
                prt[n] = n;
            }
            else
            {
                prt[n] = dp_pos[l - 1];
            }
        }
        n++;
    }

    void Generate(vector<int> &ret)
    {
        int pos = dp_pos[top - 1];
        ret.clear();
        while(true)
        {
            ret.push_back(w[pos]);
            if(prt[pos] == pos) break;
            pos = prt[pos];
        }
        reverse(ret.begin(), ret.end());
    }
}L;

bool vis[100005];
int a[100005];

vector< vector<int> > ans;

void Solve()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    memset(vis, 0, sizeof(vis));
    ans.clear();
    int cnt = 0;

    while(cnt < n)
    {
        vector<int> ret;

        L.Init(true);
        for(int i = 0; i < n; i++)
        {
            if(vis[a[i]]) continue;
            L.Update(a[i]);
        }
        L.Generate(ret);
        
        int k = sqrt((n - cnt) * 2);
        k -= 3;
        k = max(0, k);
        while((k * (k + 1)) / 2 <= (n - cnt))k++;

        if(ret.size() >= k)
        {
            for(int i = 0; i < ret.size(); i++)
            {
                vis[ret[i]] = true;
            }
            ans.push_back(ret);
            cnt += ret.size();
        }
        else
        {
            vector< vector<int> > pans;

            for(int i = 0; i < n; i++)
            {
                if(vis[a[i]]) continue;
                int l = 0, r = pans.size() - 1;
                while(l < r)
                {
                    int mid = (l + r) >> 1;
                    int pos = pans[mid].size() - 1;
                    if(pans[mid][pos] < a[i])
                    {
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid;
                    }
                }
                if((pans.size() == 0) || (pans[l][pans[l].size() - 1] < a[i]))
                {
                    vector<int> v;
                    v.push_back(a[i]);
                    pans.push_back(v);
                }
                else
                {
                    pans[l].push_back(a[i]);
                }
            }

            for(int i = 0; i < pans.size(); i++)
            {
                ans.push_back(pans[i]);
            }

            break;
        }
    }

    printf("%d\n", (int)ans.size());
    for(int i = 0; i < ans.size(); i++)
    {
        printf("%d", (int)ans[i].size());
        for(int j = 0; j < ans[i].size(); j++)
        {
            printf(" %d", ans[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    srand(time(NULL));
    int t;
    scanf("%d", &t);
    while(t--)
    {
        Solve();
    }
    return 0;
}

Problem F

由于答案只需要0和1。故对于每一个多重集合而言，我们都可以表示成一个长度为 $7000$ 的bitset。这是一个最直接的想法。
基于这个想法我们便可以直接拟出其他步骤的实现：

对于步骤4而言，我们就可以直接取第x个bitset中的第v位（这里记为 $f_x(v)$ ）。
对于步骤1而言，我们只需要赋一个只有第v位为1的bitset就行了。
对于步骤2而言，模2下的加法事实上就是异或（可以自己尝试一下）
比较棘手的事步骤3。直接模拟的话时间复杂度是 $O(v^2)$ 的级别。这显然是超时的。

对于步骤3，我们考虑能否使用更快的计算方法。
一个显然的思路就是容斥。当我们求新的集合的第v位的时候，事实上就是在求原来两个集合的元素中gcd为v的数对数。这个显然可以使用两个集合的元素中gcd为【v的倍数】的数对数来容斥。后者就很容易计算了。
设第x个bitset中值为v的倍数的数的个数为 $F_x(v)$ 。那么两个集合的元素中gcd为【v的倍数】的数对数显然就是 $F_y(v)*F_z(v)$ 。也就是说，如果要使用这个方法的话还需要再维护一系列表示 $F_x(v)$ 的bitset，而且这个容斥的计算时间复杂度其实也不低（其实还是 $O(v^2)$ ）。
但是这个方法的副产物 $F_x(v)$ 是可以使用的。首先， $F_x(v)$ 的定义总结一下就是：
$F_x(v)={\sum_{v|d}f_x(d)}$
我们可以通过简单的莫比乌斯反演来得到如下式子：
$f_x(v)={\sum_{v|d}{\mu}({\frac d v})F_x(d)}$
也就是说，如果我们只维护 $F_x(v)$ 的话，可以在需要某个 $f_x(v)$ 的时候通过莫比乌斯反演在 $O(v)$ 的时间内计算得出。
那么四个步骤的计算方法就需要做一点改变：

对于步骤1，需要使用类似根号试除法的方法来初始化集合x。时间复杂度为 $O({\sqrt v})$
对于步骤2，同样还是对应位置的元素相加即可，在模2下的计算就是异或。时间复杂度为 $O(v)$
对于步骤3，可以发现其实只需要将对应位置的元素相乘就行了，在模2下的计算就是与运算。时间复杂度为 $O(v)$
对于步骤4，可以使用莫比乌斯反演来计算。时间复杂度为 $O(v)$

总的时间复杂度为 $O(qv)$ ，似乎还不够理想。
但事实上我们按照前面的存bitset的思想的话，我们可以使用bitet的整体计算来压缩常数。例如说步骤2和步骤3其实就是两个bitset直接进行运算。时间复杂度虽然还是 $O(v)$ ，但是常数缩小到 ${\frac 1 {32}}$ 的量级下。大致估算一下可以卡过去。
对于步骤4而言。我们也需要尽可能得转换成两个bitset直接计算。由于v的取值只有最多7000种。我们可以将莫比乌斯函数进一步处理成7000个不同的bitset用于在不同的v值下使用。于是答案就可以变成两个bitset相乘（与运算），得到新的bitset，然后对新的bitset进行count计算。这样步骤4的常数也压下去了。（这一部分不懂的话可以看一下代码里的init函数和Get函数）
这么做的总空间复杂度为 $O(nv+v^2)$ 。

#include <cstdio>
#include <cstring>
#include <bitset>

using namespace std;

bitset<7005> a[100005], mu[7005];

bool check[7005];  
int prime[7005];  

void init()  
{  
    memset(check, 0, sizeof(check));  
    mu[1][1] = 1;  
    int tot = 0; 

    for(int i = 2; i <= 7000; i++)  
    {  
        if(!check[i])
        {  
            prime[tot++] = i;  
            mu[1][i] = 1;  
        }  
        for(int j = 0; j < tot; j++)  
        {  
            if(i * prime[j] > 7000)
            {
                break;
            }  
            check[i * prime[j]] = true;  
            if(i % prime[j] == 0)
            {  
                mu[1][i * prime[j]] = 0;  
                break;  
            }
            else
            {  
                mu[1][i * prime[j]] = mu[1][i];  
            }  
        }  
    } 

    for(int i = 2; i <= 7000; i++)
    {
        for(int j = 1; j * i <= 7000; j++)
        {
            mu[i][j * i] = mu[1][j];
        }
    } 
}

void Set(int x, int v)
{
    a[x].reset();
    for(int i = 1; i * i <=v; i++)
    {
        if(v % i != 0)
        {
            continue;
        }
        int j = v / i;
        a[x][i] = a[x][i] ^ 1;
        if(j != i)
        {
            a[x][j] = a[x][j] ^ 1;
        }
    }
}

int Get(int x, int v)
{
    bitset<7005> bs = mu[v] & a[x];
    int ret = bs.count();
    ret = ((ret % 2) + 2) % 2;
    return ret;
}

int main()
{
    init();
    int n, q;
    scanf("%d%d", &n, &q);
    while(q--)
    {
        int k;
        scanf("%d", &k);
        if(k == 1)
        {
            int x, v;
            scanf("%d%d", &x, &v);
            Set(x, v);
        }
        else if(k == 2)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[x] = a[y] ^ a[z];
        }
        else if(k == 3)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[x] = a[y] & a[z];
        }
        else
        {
            int x, v;
            scanf("%d%d", &x, &v);
            printf("%d", Get(x, v));
        }
    }
    printf("\n");
    return 0;
}

【Codeforces】Hello 2019

Problem A

Problem B

Problem C

Problem D

Problem E

结论一证明

结论二证明

运用结论解题

Problem F

后续待补充

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读