首页 > 其他分享 >Codeforces Round 997 (Div. 2) / 2056

Codeforces Round 997 (Div. 2) / 2056

时间:2025-01-18 12:34:01浏览次数:1  
标签:pre 997 2056 int cnt back ++ ans Div

A. Shape Perimeter

难度(个人感觉)★☆☆☆☆

思考:

考虑平移

Code:

for(int i = 0; i < N; i++){
    std::cin >> dx >> dy;
    if(i){
      cnt_dx += dx; cnt_dy += dy;
    }
}
ans = (m + cnt_dx + m + cnt_dy) * 2;

B. Find the Permutation

难度(个人感觉)★☆☆☆☆

思考:

可以直接拓扑排序,但是这只是 \(b\) 题,可以用比较简单的方法

做法

任意几个点的相对关系是确定的。那么我们每次插入一个点即可。

Code:

bool ok(int x, int y){//能不能把 x 放在 y 左边 
  if(x < y){
    return a[x][y] == '1';
  } else{
    return a[x][y] == '0';
  }
}

std::vector<int> ans;
for(int x = 0; x < N; x++){
  auto p = ans.begin();
  while(p != ans.end() && !ok(x, *p)){ p++; }
  ans.insert(p, x);
}

C. Palindromic Subsequences

难度(个人感觉)★☆☆☆☆

思考:

所有数不同可以做到 \(n\)。只要再大一点就行,考虑使用乘法原理。

做法

前 \(n - 2\) 个是是 \(1\),\(2\),\(3\),... \(n - 2\)。之后是两个 \(1\)。
那么最左边的 \(1\) 必须和最右边的其中一个匹配。
枚举中间数,有 \(2(n - 3)\) 种情形。实际上 \(1\; 1\; 1\) 也是一种方案。因此是\(2(n - 3) + 1\)
当 \(n \ge 6\),$2(n - 3) + 1 = 2n - 5 > n $

Code:

std::vector<int> ans;
for(int i = 0; i < N - 2; i++){
  ans.push_back(i);
}
ans.push_back(0);
ans.push_back(0);

D. Unique Median

难度(个人感觉)★★★☆☆

思考:

考虑枚举位置或值。枚举位置不太有规律,因此通过值计数。
对于偶数,可行的情况是两个中位数相同。对一个区间,中位数可能有很多,很难找到两个特殊位置的。考虑不可行的情况。

做法:

用区间个数减去不可行的情况,不可行即长度偶数且两个中位数不同。可以枚举较大的那个,记作 \(M\)。若一个区间里有多个 \(M\),不妨枚举最后一个。
当且仅当 区间中比\(M\)小的数个数大于等于\(M\)的数个数相等时,不合法。具体实现时,前者贡献 \(-1\),后者贡献 \(+1\),那么 \(pre[l-1] = pre[r]\) 。
限制是,由于它是区间最后一个 \(M\),设它的位置 \(p\),那么 \([p + 1, r]\) 里没有 \(M\)。

Code:

i64 ans, dec;
int pre[MAXN + 1];
int cnt_l[MAXN * 2 + 1], cnt_r[MAXN * 2 + 1];
void work(int x){
  pre[0] = 0;
  std::vector<int> pos{-1};
  for(int i = 0; i < N; i++){
    pre[i + 1] = pre[i] + (a[i] < x ? -1 : 1);
    if(a[i] == x) pos.push_back(i);
  }
  pos.push_back(N);
  
  memset(cnt_l + MAXN - N, 0, sizeof(int) * (N * 2 + 1));
  memset(cnt_r + MAXN - N, 0, sizeof(int) * (N * 2 + 1));
  for(int i = 1; i < (int)pos.size() - 1; i++){
    int min = INF, max = 0;
    for(int p = pos[i - 1] + 1; p <= pos[i]; p++){ cnt_l[pre[p] + MAXN]++; }
    for(int p = pos[i] + 1; p <= pos[i + 1]; p++){ cnt_r[pre[p] + MAXN]++; chmin(min, pre[p] + MAXN); chmax(max, pre[p] + MAXN); }

    for(int k = min; k <= max; k++){      
      dec += 1ll * cnt_l[k] * cnt_r[k];
    }
    memset(cnt_r + min, 0, (max - min + 1) * sizeof(int));
  }
}
void get(){
  ans = 1ll * N * (N + 1) / 2;
  dec = 0;
  for(int x = 0; x < 10; x++) work(x);
}
void output(){
  std::cout << ans - dec << "\n";
}
未完待续

标签:pre,997,2056,int,cnt,back,++,ans,Div
From: https://www.cnblogs.com/chen-nie/p/18678152

相关文章

  • Codeforces Round 997 (Div. 2) 题解(A~D 题)
    CodeforcesRound997(Div.2)题解(A~D题)A因为\(x,y<m\),所以每次必有重叠的长方形。且重叠部分长为\(m-x\),宽为\(m-y\),用总周长减去算重了的部分就行。注意处理第一个长方形的边界条件。B.FindthePermutation按照\(g_{i,j}\)的大小关系直接写cmp然后sort就......
  • 【洛谷训练记录】【LGR-213-Div.4】洛谷入门赛 #31
    训练情况赛后反思模拟题差点红温,差一道字符串模拟题AKA题问一个数\(a\)加多少后的个位数变成\(b\),取出\(a\)的个位数,再用\(b\)去减,如果小于零答案再加十。#include<bits/stdc++.h>//#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve()......
  • 如何使用css3实现一个div设置多张背景图片?
    在CSS3中,你可以使用background-image属性为一个div设置多张背景图片。这些图片将按照它们在值列表中的顺序堆叠,第一张图片位于最前面(即最靠近用户),最后一张图片位于最后面。以下是一个示例:div{width:500px;height:500px;background-image:url(image1.jpg),url(image......
  • Educational Codeforces Round 149 (Rated for Div. 2) / 1837
    A.GrasshopperonaLine难度(个人感觉)☆☆☆☆☆Codeif(L%k==0){ans.push_back(1);ans.push_back(L-1);}else{ans.push_back(L);}B.ComparisonString难度(个人感觉)★☆☆☆☆思考:注意到最长链(指一些连续的位置,它们是单调的)是答案的下界,而实际上这是下......
  • Educational Codeforces Round 146 (Rated for Div. 2) / 1814
    A.Coins难度(个人感觉)☆☆☆☆☆思考:关键是2可以凑出任意偶数Code:if(n%2==0){ok=1;}else{if(k%2==0){ok=0;}else{ok=n>=k;}}B.LongLegs难度(个人感觉)★☆☆☆☆思考:当最终\(m=1e5\),答案不超过\(3e5\),因此最优的情况......
  • VP Codeforces Round 911 (Div. 2)
    A.CoverinWater题意:有n个格子,有些格子是好的,有些是坏的,你要给好格子都装上水,你可以花费一点价值让一个格子有水,也可以把一个格子的水移到另一个格子,没有花费。如果一个格子是好格子并且两边的格子都有水,这个格子就会自己填满水。问最少花费让所有好格子有水。容易想到,如果......
  • 如何让大小不同的图片等比缩放不变形显示在固定大小的div里?写个例子
    在前端开发中,等比缩放图片以适配固定大小的div容器是一个常见的需求。这通常可以通过CSS来实现,确保图片在缩放时不会变形。以下是一个简单的例子,说明如何使用CSS来完成这个任务:HTML结构:首先,创建一个包含图片的div容器。<divclass="image-container"><imgsrc=......
  • Codeforces Round 867 (Div. 3)-D. Super-Permutation
    Codeforces题解-[CodeforcesRound867(Div.3)-D.Super-Permutation]题目链接题目描述Apermutationisasequence\(n\)integers,whereeachintegerfrom\(1\)to\(n\)appearsexactlyonce.Forexample,\([1]\),\([3,5,2,1,4]\),\([1,3,2]\)areper......
  • VP Codeforces Round 978 (Div. 2)
    A.BustoPénjamo题意:有n个家庭,每个家庭有\(a_i\)个人,现在有r排座位,每个座位可以坐两个人。如果一个人自己一个坐一个座位或者和自己家庭的人坐一个座位,他就会开心,问所有人都入座后最多有多少人开心。我们肯定尽量让一个座位坐两个同一家庭的人,这样一个座位可以让两个人开心。......
  • CF div2 990(A~E)
    VP赛时\(4\)题,发挥得比较不错的一场,并且这场也偏简单。A数数题,找好规律直接模拟即可codeB简单排列组合题显然总方案数为:\[n!/(a_1!*a_2!*...*a_m!)\]\(a_1到a_m\)表示某种字符的数量想最小化总方案数,只能最大化上式分母的值。而题目操作等价于将某个\(a_i\)减......