[Codeforces] Round #773 div.2

A. Hard Way

题目大意

给出三个可以组成三角形的点,每个点的横纵坐标非负。
三角形边上可以不通过内部直线连接到$x$轴上任意一点的点称为安全点。
求非安全的长度,即无法不通过内部直接连到$x$轴上的部分。

题解

易发现只有边平行于$x$轴且是最高的边才非法,判断是否存在记录此边长度即可。

Code

struct Point
{
    int x, y;
} p[5];
void solve()
{
    int ans = 0;
    for (int i = 1; i <= 3; i++)
        p[i].x = read(), p[i].y = read();
 
    if (p[1].y == p[2].y && p[1].y > p[3].y)
        ans += abs(p[1].x - p[2].x);
    if (p[1].y == p[3].y && p[1].y > p[2].y)
        ans += abs(p[1].x - p[3].x);
    if (p[2].y == p[3].y && p[2].y > p[1].y)
        ans += abs(p[2].x - p[3].x);
 
    printf("%d\n", ans);
}

B. Power Walking

题目大意

给一个长度为$n$的数组$a$,需要把$a$数组分成$k$份,每份的价值是其中不同元素的个数
求总价值最小值,从$k=1$到$k=n$输出。

  • $1 \leq k \leq n \leq 3*10^5$
  • $1 \leq a_i \leq 10^9$

题解

易知每一份的价值最小为1:只有一个元素/有多个相同元素。
贪心把$a$中相同的元素分到同一组里使代价最小,所以相同的多个元素是没有用的,用set去重看作一个。
当每组都能取到最小价值1时,总价值是$k$。
不能都取到最小价值时,$k$组要包括$a$中所有元素,总价值自然是$a$中不同元素的数目。
抽屉原理易知,当$k<s.size()$时无法每组只取一个。

Code

void solve()
{
    set<int> s;
    int n = read(),t;
    for (int i = 1; i <= n; i++)
        t = read(), s.insert(t);
    for (int k = 1; k <= n; k++)
    {
        if (k < s.size()) printf("%d ", s.size());
        else printf("%d ", k);
    }
    puts("");
}

C. Great Sequence

题目大意

给一个长度为$n$的序列$a$,一个整数$x$。当$a$中元素可以两两配对:$a_i = a_j * x$,不重不漏,称为好序列。
求至少需要补多少个元素使其称为好序列。

  • $ 1\leq n \leq 2*10^5, 2 \leq x \leq 10^6$
  • $1 \leq a_i \leq 10^9$

题解

实际上就是求能配对多少组,剩下不能配对的元素每个补一个即可。排序之后找一遍,配对了就删掉,最后看剩下多少元素就可以了。

Code

int n, x, a[200010];
map <int, int> t;
void solve()
{
    int ans = 0;
    n = read(), x = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        t[a[i]]++;
    }
    sort(a + 1, a + 1 + n);
    for (int i = n; i >= 1; i--)
    {//从大到小是为了做除法防止爆int,开longlong的话正着来也可以
        if (a[i] % x == 0&&t[a[i]])//x的倍数可能可以做pair中第二个数
        {
            if (t[a[i] / x])//pair中第一个数存在,可行
            {
                int minn = min(t[a[i]], t[a[i] / x]);
                t[a[i]] -= minn;
                t[a[i] / x] -= minn;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        ans += t[a[i]], t[a[i]] = 0;
    printf("%d\n", ans);
}

D. Repetitions Decoding

题目大意

给一个长度为$n$的序列$a$,期望把它分成一个/多个重复串。重复段的定义是:对一个长度$2*k$的段来说有$a_i=a_{i+k}$。
而这是几乎不可能的,我们可以对序列进行操作:在任意位置添加两个相同的元素。
问此序列是否可以通过操作使其变成由重复读段组成,可以的话输出操作次数,每个操作:添加元素的即时位置,添加元素的值,重复段的个数,每个重读段的长度。
无法完成的话输出$-1$。

  • $ 1\leq n \leq 500$

题解

由于每次只能添加2个相同元素,所以初始序列中如果有某个元素个数是奇数就一定不行。始终是奇数,无法分在两份里。
我们可以对一段长度为$k$的序列$s_1s_2...s_k$后依次加上$s1,s2...sk$。
$s_1s_2...s_ks_{k+1}...s_n$
$s_1s_2...s_ks_1s_1s_{k+1}...s_n$
$s_1s_2...s_ks_1s_2s_2s_1s_{k+1}...s_n$
$...$
$s_1s_2...s_ks_1s_2...s_ks_k...s_2s_1s_{k+1}...s_n$
每次插入放在在上一次插入的两个元素中间,共添加了$2*k$个元素,使$s_1s_2...s_k$完成配对,分割出配对的序列,剩下$k$个元素是初始序列的反转,发现未配对的序列长度没有减小。
易想到当$s_1=s_{k+1}$时,就可以不用加$s1$,从$s2$开始操作,这样可以配对原本的$k$个剩下得到长度为$k-1$的$s_2s_3...s_k$的倒序,这样就消去了一个元素。
依靠此想法,从一个元素开始找到下一个与它相同的元素进行此操作,可以消去这两个元素,变成它们中间元素的倒序,使其未完成配对的元素个数不断减小。$n \leq 500$,硬做就行。

Code

void solve()
{
    int n = read(), cnt = 0;
    vector <int> a(n), lens;//记录序列,重复段长度
    vector <pair<int, int>> ops;//记录操作
    
    for (int i = 0; i < n; i++)
        a[i] = read();
   
    while (!a.empty())//未配对序列不为空
    {
        int i = 0, j = i + 1;
        while (j < a.size() && a[i] != a[j])//找下一个同样的元素
            j++;
        if (j == a.size())//找不到直接寄
        {
            puts("-1");
            return;
        }
        int ptr = cnt + j + 1;、
        //ptr是用于记录操作实时的位置(未配对中的下标加上已经配对了的序列的长度)
        for (int k = i + 1; k < j; k++)
        {
            ops.emplace_back(ptr, a[k]);
            ptr++;
        }
        lens.push_back(2 * (j - i));
        cnt += 2 * (j - i);
        //vector删除元素要注意先删右边的再删左边的
        //因为删除ai后,ai之后的元素下标会左移,这里先删左边的下标就对不上了。
        a.erase(a.begin() + j);
        a.erase(a.begin() + i);
        reverse(a.begin(), a.begin() + j - 1);//反转
    }
 
    printf("%d\n", ops.size());
    for (auto& op : ops)
        printf("%d %d\n", op.first, op.second);
 
    printf("%d\n", lens.size());
    for (auto& len : lens)
        printf("%d ", len);
    puts("");
}

E. Anonymity Is Important

题目大意

有n个病人,编号从1到n。之后有q次操作,告诉我们一些信息:某段区间内无人患病/某段区间内至少有一个人患病[$0$ $l$ $r$ $0$/$0$ $l$ $r$ $1$]。或提问编号为x的人的状态。

  • $1 \leq n,q \leq 2*10^5$

题解

首先,$n$个人最初的健康情况都是未知的。
确定一个人的健康情况:一种方法是直接告知一个人没病;另一种方法$x$在至少一个人得病的区间内,并且只有$x$的情况未知,其他人都没得病。
因此我们需要维护不难确定健康状况的人以及至少一人患病的区间,并不断缩小至少一个人的病的区间,才可较优地找出谁得病了。
所以当一个大的有病区间包含小的有病区间时,大区间就无意义了,因为小区间外大区间内的人始终时不不确定的。我们要在维护时实时清理嵌套的大空间。
可以用一个set维护不确定健康状况的人,遇到没病的区间把他们删除即可。set删除是$O(nlon)$,而vector是$O(n)$。
对于至少一人患病区间,用map维护。键作为左端点,值作为右端点。map按键值排序,即按照左端点排序。我们插入一个区间后向左比较相邻区间的右端点就可以得到嵌套关系。
对于$x$不在没得病区间的询问,我们找他前一个健康状况不确定的人$l$,以及后一个$r$。
有$l<x<r$且他们的健康状况未知,$[l,r]$内其他人都没病。
我们如果可以找到一个至少一人有病的区间$[l1,r1]$,满足$l<l1<x<r1<r$,则x一定有病,找不到的话就是无法确定。
时间复杂度$O(nlogn+nlogn)$。

Code

set<int> s;
map<int, int> m;
int main()
{
    int n = read(), q = read();
    for (int i = 0; i <= n + 1; i++) s.insert(i);
    //不确定健康情况的人
    int op, l, r, x;
    while (q--)
    {
        op = read();
        if (!op)
        {
            l = read(), r = read(), x = read();
            if (!x)
            {
                while (true)
                {//告诉没病了,删除
                    auto it = s.lower_bound(l);
                    if (*it > r) break;
                    s.erase(it);
                }
            }
            else
            {//如果这是个包含别的区间的大区间,不用就行操作
                auto it = m.lower_bound(l);
                if (it != m.end() && it->second <= r)
                    continue;
                //不是的话,加入它并把包含它的删除
                m[l] = r;
                //查询左端点在它前面的,看右端点是否在它后面来判断嵌套关系
                it = m.find(l);
                while (it != m.begin() && r <= prev(it)->second)
                    m.erase(prev(it));
            }
        }
        else
        {
            x = read();
            if (s.find(x) == s.end()) puts("NO");//被删了说明没病
            else
            {
                l = *prev(s.find(x));//前一个不确定状况的人的位置
                r = *next(s.find(x));//后一个不确定状况的人的位置
                //l < x < r,都是不确定健康状况的
                //此时我们找一个至少一人有病的区间区间l1,r1
                //当存在l < l1 < x < r1 < r时,x一定有病,因为此至少一人有病区间内只有他一人健康状况不确定了。
                auto it = m.upper_bound(l);
                if (it != m.end() && it->first <= x && it->second < r)
                    puts("YES");
                else puts("N/A");
            }
        }
    }
    return 0;
}

F. Two Arrays

不会,先摆了

总结

div.2的前3题都很简单,算数/模拟,没有什么思维难度。比赛时应该快速准确的写出来,注意边界条件不要犯错。以后写题解没时间的话可能就不写A,B了
D,E有一定思维难度且可能需要一定的代码能力。
D题这类主要是找规律构造,我在写D题时因为代码能力不行出了很多奇奇怪怪的错误。。。需要多写点。
E题比较考察逻辑,这应该叫同一律还是排中律来着,emmm不重要。

最后修改:2022 年 03 月 06 日
如果觉得我的文章对你有用,请随意赞赏