首页 > 其他分享 >Codeforces 1948E Clique Partition

Codeforces 1948E Clique Partition

时间:2024-03-16 11:44:26浏览次数:24  
标签:lceil frac int Partition Codeforces 构造 1948E 考虑

考虑到有 \(|i - j|\),所以肯定是让相邻的一部分在一个团里。

考虑构造出一个最长长度的,后面类似复制几遍即可。

考虑到 \(|k - 1| = k - 1\),且因为 \(a_i\) 为一个排列,差的绝对值至少为 \(1\),所以只考虑两端最长长度也只可能为 \(k\)。

不妨先假设最长长度为 \(k\) 来构造。

那么就相当于要让 \(a_1 = x, a_k = x + 1\)。
那么对于 \(a_2\),\(|k - 1| - |k - 2| = 1\),那么如果 \(|a_k - a_2| - |a_k - a_1| = 1\),就有 \(|k - 1| - |a_k - a_1| = |k - 2| + |a_k - a_2| = k\),这是合法的。
于是便可以考虑令 \(a_2 = a_1 - 1\)。
类似的,令 \(a_{k - 1} = a_k + 1\)。
以此类推,有 \(a_i = a_{i - 1} - 1, a_i = a_{i + 1} + 1\),显然应该找到个临界点让左边的 \(a_i\) 用左边的方式,右边的 \(a_i\) 用右边的方式构造。
考虑到如果选取 \(\lfloor\frac{k}{2}\rfloor + \lceil\frac{k}{2}\rceil = k\),那么这部分最劣的距离为 \(2(\lceil\frac{k}{2}\rceil - 1) \le k + 1 - 2 = k - 1\le k\),合法。
于是按照这个方法构造即可。

时间复杂度 \(O(n)\)。

代码
#include<bits/stdc++.h>
inline void solve() {
    int n, k; scanf("%d%d", &n, &k);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = std::min(l + k - 1, n);
        int len = r - l + 1, p = len + 1 >> 1, c0 = l + p - 1, c1 = r;
        for (int i = 1; i <= p; i++) printf("%d ", c0--);
        for (int i = 1; i <= len - p; i++) printf("%d ", c1--);
    }
    puts("");
    printf("%d\n", (n + k - 1) / k);
    for (int l = 1, r, c = 0; l <= n; l = r + 1) {
        r = std::min(l + k - 1, n), c++;
        for (int i = l; i <= r; i++) printf("%d ", c);
    }
    puts("");
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

标签:lceil,frac,int,Partition,Codeforces,构造,1948E,考虑
From: https://www.cnblogs.com/rizynvu/p/18076887

相关文章

  • Codeforces-1005C
    https://codeforces.com/problemset/problem/1005/C一、代码目录#include<bits/stdc++.h>usingnamespacestd;voidsolve(){inta[122222],n,ans=0;map<int,int>m;scanf("%d",&n);for(inti=0;i<n;i++){......
  • Educational Codeforces Round 163 (Rated for Div. 2)
    EducationalCodeforcesRound163(RatedforDiv.2)A-SpecialCharacters解题思路:一个相同的连续段会贡献两个特殊字符,所以答案一定是偶数,找个不同的数分隔开即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll......
  • Codeforces Round 933 (Div. 3)赛后总结
    CodeforcesRound933(Div.3)B从边缘开始计算,因为边缘肯定只能一个一个减,就可以遍历得到答案.代码C只要对mapie特判,然后判断map和pie的个数就是答案了。D(记忆化搜索)可以通过二维数组来标记搜索状态,将已经出现过的状态直接返回,极大减少时间。#include<bits/stdc++.h>......
  • Codeforces Round 933 (Div. 3) A - G 题解
    CodeforcesRound933(Div.3)A-RudolfandtheTicketSolution因为\(n\)很小,直接枚举\(b_i+c_j\)所产生的所有数字Code#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,m,k;cin>>n>>m>>k;intans=0;......
  • CodeForces 1874E Jellyfish and Hack
    洛谷传送门CF传送门显然\(\text{fun}(P)_{\max}=\frac{|P|(|P|+1)}{2}\)。考虑大力dp,设\(f_{i,j,k}\)为\(|P|=i\),\(P_1=j\),\(\text{fun}(P)=k\)的排列\(P\)的个数。此时\(|L|=j-1,|R|=i-j\)。转移枚举\(L_1,R_1,\text{fun}(L),\text{fun}(R......
  • Codeforces Round 933 (Div. 3)
    CodeforcesRound933(Div.3)AA-RudolfandtheTicket暴力查看代码voidsolve(){intn,m,k;cin>>n>>m>>k;vector<int>b(n),c(m);for(inti=0;i<n;++i)cin>>b[i];for(inti=0;i<m;++i)cin>>c[i];......
  • Codeforces Round 933 (Div. 3)
    CodeforcesRound933(Div.3)A-RudolfandtheTicket解题思路:暴力。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingpiii=pair<ll,pair<ll,ll>&......
  • Codeforces Round 933 (Div. 3)
    A.RudolfandtheTicket#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingldb=longdouble;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;constintinf=1e9;co......
  • Codeforces Round 933 (Div. 3) A-F
    CodeforcesRound933(Div.3)A.RudolfandtheTicket题意:有两个数组\(b_n\)和\(c_m\),两个数组中分别取一个数相加是否小于k,有几种方法使\(b_f\)+\(c_s\)<=k思路:暴力枚举所有方案,时间复杂度O(nm)代码:#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e......
  • Codeforces Round 656 (Div. 3) F. Removing Leaves
    ProblemDescription给出一棵\(n\)个节点的无根树。你可以进行以下操作:选择\(k\)个共同父节点的叶子节点,将\(k\)个节点和与父节点相连的边删去。求最大操作次数。Input第一行输入一个整数\(t\)\((1\let\le2\times10^4)\),表示测试组数。接下来每组测试数据第......