首页 > 其他分享 >Codeforces Round 963 (Div. 2)

Codeforces Round 963 (Div. 2)

时间:2024-08-06 10:55:08浏览次数:18  
标签:奇数 963 Codeforces 偶数 cdots Div 2k

Codeforces Round 963 (Div. 2)

A

A, B, C, D 的数量和 \(n\) 取个 \(\min\) 相加

B

只有奇数或只有偶数答案为 \(0\),否则,只能把所有的偶数改为奇数,因为不可能把所有奇数改为偶数。

然后就是改的大小问题了。考虑找到最大的奇数,然后把偶数从小到大依次修改。

C

显然对 \(2k\) 考虑同余就好了,因为循环节长度是 \(2k\) 的。

然后变成一个长度为 \(2k\) 的数轴,求若干个区间的交集。

分成两种区间,一种是包左右两头的,一种是包中间的。

由于这两种区间的交集最多只会有两个区间,直接维护这两个区间就好了。

D

直接 dp,设 f[i][j] 表示考虑前 \(i\) 个数,保留 \(\le j\) 的数,最少保留几个,显然 f[n][j] = (n + 1) / 2 的最大 \(j\) 就是答案了。不难注意到这个东西第二维是单调的,考虑二分这个 \(j\),然后去 dp。

E

假设只考虑对一列 \(j\) 进行修改的操作,可以发现相当于把 \(f(1), f(2), \cdots, f(n)\) 覆盖掉第 \(j\) 列。覆盖之后,新的 \(f'(1), f'(2), \cdots, f'(n)\) 居然就是原来的第 \(j\) 列。

这不是相当于,把 \(f(1), f(2), \cdots, f(n)\) 看作第 \(0\) 列,然后交换第 \(0\) 和第 \(j\) 列么。

不过 \(g(j)\) 被改变了,这个操作不能这么单纯地被描述。但是一看就会发现 \(g(j)\) 变成了所有数的异或和,于是不难想到,定义第 \(0\) 行和第 \(0\) 列,\(a_{0, 0}\) 就是所有数的异或和,\(a_{i, 0} = f(i), a_{0, j} = g(j)\),于是操作变成交换第 \(0\) 行和第 \(i\) 行或交换第 \(0\) 列和第 \(j\) 列。

推广一下,其实就是交换任意两行和任意两列,然后让差值和最小。

那就是给行决定一个排列,列决定一个排列,然后让差值和最小。这时候行、列是独立的。

当题意能简化成简单的一句话时,说明我们建立的模型很对啊!

显然可以求出第 \(i\) 行和第 \(j\) 行的差值,把这个看作边权,变成找到一个最短哈密顿路径。

这个问题我没那么熟悉,思考一下直接状压就能 \(O(n^2 2^n)\) 做完?

F

还不会

标签:奇数,963,Codeforces,偶数,cdots,Div,2k
From: https://www.cnblogs.com/lingfunny/p/18344717

相关文章

  • Educational Codeforces Round 168 (Rated for Div. 2)
    没有时间参赛直接补几道简单题吧~B.MakeThreeRegions题意:给一个2行的字符串,有block和其他东西,问把一个位置变成block让联通的部分变成3个部分,有多少种方法思路:找规律,找所哟符合条件的块即可voidsolve(){ intn; cin>>n; array<string,2>s; cin>>s[0]>>s[1];......
  • CodeForces-765F
    首先,如果你写过P9058的话,应该会想到支配点对这个trick,我们不妨将此题的套路搬到这套题上.定义点对\((i,j),a_i\lea_j\),当\((i,j)\)被支配当且仅当存在\(i<k<j\)满足\(a_i\lea_k\lea_j\)。相应的,一个有效的点对\((i,j)\),其中\(i\)满足\(i\)最大且\(a_i<a_j\)。......
  • Codeforces Round 963 (Div. 2) A - C 详细题解(思路加代码,C++,Python) -- 来自灰名
    比赛链接:Dashboard-CodeforcesRound963(Div.2)-Codeforces之后有实力了再试试后面的题目,现在要做那些题,起码要理解一个多小时题目A:链接:Problem-A-Codeforces题目大意理解:        极少数不考翻译能读懂的cf题目(bushi)每个测试用例第一行一个n,......
  • Codeforces Round 963 (Div. 2) D题解
    CodeforcesRound963D题目描述给定两个正整数n和k以及另一个由n个整数组成的数组a。在一次操作中,可以选择a中大小为k的任意一个子数组,然后将其从数组中删除,而不改变其他元素的顺序。更正式地说,假设(l,r)是对子数组a[l],a[l+1],...,a[r]的操作,使得r-l+1......
  • div中添加el-loading(局部loading的使用)
    div中添加el-loading(局部loading的使用)效果:在div中实现el-loadinghttps://img-blog.csdnimg.cn/c2870e74bd344b06ad1ccb0844b8e8ce.png<divclass="content-main">{{hotList}}</div>getHotList(columnType){this.$nextTic......
  • Codeforces Round 963 (Div. 2) 补题记录(A~D,F1)
    不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.不会做F1.A直接计算每一个选项最多对多少个题加起......
  • Codeforces Round 891 (div.3) D题解析
    CodeForcesRound898(div4)D题.StrongVertices大致思路对于题目的给的式子,au-av>=bu-bv,我们可以通过移项得到au-bu>=av-bv,这样就能够构造出来一个ai-bi的项出来对于构造出来的项,我们可以遍历一遍用数组把每一个项存起来,找到值最大的项,值最大的项所对应的下标就是强顶......
  • ARC 180 D - Division into 3
    ARC180D-Divisioninto3首先考虑分成两段,首先两端中必定有一个是最大值,问题就是让另一段的最大值最小化。并且这两段一定一个是前缀\(\max\),一个是后缀\(\max\),那么显然就是只留第一个值或者只留最后一个值。所以就是\(mx+\min(a_l,a_r)\),然后考虑分成三段。对于一组询......
  • Educational Codeforces Round 168 (Rated for Div. 2)-7.30复盘
    A.StrongPassword简单题,找到相同的两个相邻字母之间插一个跟他们不同的大写字母即可inlinevoidsolve(){ cin>>s; intid=0; charhh=''; for(inti=1;i<s.size();i++){ if(s[i-1]==s[i]){ id=i;break; } } for(inti=0;i<26;i++){ if(s[id]!='a'+i&a......
  • Educational Codeforces Round 168 (Rated for Div. 2)
    题目链接:EducationalCodeforcesRound168(RatedforDiv.2)总结:题目较简单,但是发挥很一般。A,B题一直读假题,卡了半个小时;C题用char存int,难绷了。A.StrongPasswordtag:模拟voidsolve(){strings;cin>>s;for(inti=1;i<s.size();i++){......