How to AK ABC247

__vector__ · 2022-04-15 23:31:13 · 个人记录

前言：

整了一周的 whk ，总算能写写代码了。

A - Move Right

签到题

B-Unique Nicknames

这道题虽然也是一个 O(n^2) 的暴力能过的签到题，但我非要调 O(n log n) 的方法，结果吃了 19 个罚时...........（不过还好是虚拟赛）

C-1 2 1 3 1 2 1

这道题直接按照题目模拟即可，签到题 ~~（然而我犯智障吃了一个罚时）~~

D-Cylinder

这道题还是签到题。
可以定义一个结构体，用来存储连续的一段写有相同数字的球，如下：

struct Node
{
   int sum,val;
}node[maxn];

sum 代表当前段的球数，val 代表当前段的球上面的数字。
将 node 作为一个栈，加入新的球时，如果新加入的那些球与栈顶的数字相同，那么将它们合并，否则将新加入的球作为一个新的栈顶元素加入栈中。
删除球的时候也差不多，就不说了。

E-Max Min

暴力肯定都会，来说一说如何对暴力进行优化，使其复杂度降为 O(n)（就是官方题解的做法）。

数组中有一部分元素大于 x，或小于 y，这些元素的存在实际上把数组分成了几个有效的区间。因为任何区间都不可能包含这些元素，所以可以先利用这些元素把数组划分成几个独立的区间。显然，这些区间可以单独计算答案，不会互相干扰，不会互相干扰的原因是如果要干扰肯定需要经过那些 (大于 x，或小于 y) 的元素，但这是不可能的。
划分完区间之后，就可以对每个区间从左到右枚举 l，每次加上 r 的取值范围大小即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    int a[maxn];
    int sta[maxn];
    int top=0;
    int n,x,y;
    ll get_ans()
    {
        int j=1;
        int cnt_x,cnt_y;
        cnt_x=cnt_y=0;
        ll ans=0;
        for(int i=1;i<=top;i++)
        {
            for(;j<=top&&(cnt_x==0||cnt_y==0);j++)
            {
                if(sta[j]==x)cnt_x++;
                if(sta[j]==y)cnt_y++;
            }
            if(cnt_x&&cnt_y)
            {
                //此时j-1为r的最小取值
                ans+=(ll)(top-j+2);
            }
            if(sta[i]==x)cnt_x--;
            if(sta[i]==y)cnt_y--;//l向右移动，清除当前
        }
        return ans;
    }
    void main()
    {
       scanf("%d%d%d",&n,&x,&y);
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&a[i]);
       }
       ll out=0;
       int i=1;
        while(i<=n)
        {
            top=0;
            for(;i<=n&&(a[i]<=x)&&(a[i]>=y);i++)
            {
                sta[++top]=a[i];
            }
            if(top)
            {
                out+=get_ans();
            }
            else
            {i++;}
        }
        cout<<out;
    }
}
signed main()
{
    Main::main();
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

F - Cards

我是照着 \color{black}\text{c}\color{red}\text{zyjr} 大佬的代码才看懂题解的。(atcoder id=cz_yjr)

考虑把每对 (p_i,q_i) 相连，这样就形成了一些连通块，例如 (a \rightarrow b) \rightarrow (b \rightarrow c) \rightarrow (c \rightarrow d) 这样的，设第 i 个连通块大小为 size_i，那么每个连通块都要选择一些不同的数字，使得所有最后所有连通块选择的数字正好有 n 个不同的。
可以提前预处理出连通块大小为 i (i \in [1,n]) 时的方案数，记为 f_i。

f_1 = 1,f_2=3
f_i = f_{i-1}+f_{i-2} (i \ge 3)
最后答案就是所有连通块方案数相乘