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

Codeforces Round 899 (Div. 2)

时间：2023-10-11 17:12:19浏览次数：41  
标签：ch int 899 Codeforces long kN isdigit Div getchar

目录

写在前面

比赛地址：https://codeforces.com/contest/1882。

你知道我要在这里放一首由日本女歌手演唱的歌曲：

<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1969684774&auto=0&height=66" width="330"></iframe>

一个队友去医院一个队友军训，堂堂单刷！

感觉开场 5h 太浪费了于是找了场 div2，然后 C 不会做卡了 1h，妈的。

看完题解立马会了，我果然是没脑子选手。

A

显然直接从从 1 开始构造即可，记 \(b_0 = 0\)，则：

\[b_i = \begin{cases} b_{i - 1} + 1 & (a_{i} \not= b_{i - 1} + 1)\\ b_{i - 1} + 2 & \text{otherwise} \end{cases}\]

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    int n = read(), a, b = 1;
    for (int i = 1; i <= n; ++ i, ++ b) {
      a = read();
      if (a == b) ++ b;
    }
    printf("%d\n", b - 1);
  }
  return 0;
}

B

\(S\not= \cup_{i} S_i\) 这个限制挺有趣的，又发现数据范围挺小，于是考虑枚举不在 \(S\) 中的数，将不含有该数的所有 \(S_i\) 并起来求的势的最大值即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 60;
//=============================================================
int n, sz[kN], s[kN][kN];
std::vector <int> val;
bool have[kN], vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  n = read();
  for (int i = 1; i < kN; ++ i) have[i] = 0;
  val.clear();
  
  for (int i = 1; i <= n; ++ i) {
    sz[i] = read();
    for (int j = 1; j <= sz[i]; ++ j) {
      int v = s[i][j] = read();
      if (!have[v]) val.push_back(v);
      have[v] = true;
    }
  }
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();

    int ans = 0;
    for (auto v: val) {
      int sum = 0;
      for (int i = 1; i < kN; ++ i) vis[i] = 0;
      for (int i = 1; i <= n; ++ i) {
        int flag = 1;
        for (int j = 1; j <= sz[i]; ++ j) {
          if (s[i][j] == v) {
            flag = 0;
            break;
          }
        }
        if (!flag) continue;
        for (int j = 1; j <= sz[i]; ++ j) vis[s[i][j]] = 1;
      }
      for (int i = 1; i < kN; ++ i) sum += vis[i];
      ans = std::max(ans, sum);
    }
    printf("%d\n", ans);
  }
  return 0;
}

C

呃呃呃，我是傻逼。

显然最理想的情况是数列中所有正数位于奇数位置，直接倒着取数即可；再考虑一个没那么理想但是也挺理想的情况，数列中所有正数均位于偶数位置，这样只需要拿掉他们之前的某个数，就转化成了最理想情况。

然后经过大力手玩加猜想发现固定了取的数中最靠前的位置后，总存在一种取数方案使得可以把它之后的所有正数全部取走。正确性可以感性理解，可以先对后面进行一顿操作，再把这个最靠前的位置取走，相当于改变了后面的奇偶性，再进行一顿操作，使得所有正数均可以位于奇位置上。

于是维护后缀正数和，再枚举取的数中最靠前的位置即可。对后面的位置进行操作不会影响最靠前的位置的奇偶性，该位置对答案的贡献是固定的。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN];
LL suf[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    suf[n + 1] = 0;
    for (int i = n; i; -- i) suf[i] = suf[i + 1] + std::max(a[i], 0);
    
    LL ans = 0;
    for (int i = 1; i <= n; ++ i) {
      ans = std::max(ans, suf[i + 1] + ((i & 1) ? a[i] : 0));
    }
    printf("%lld\n", ans);
  }
  return 0;
}

D

典中典之拆位，再加典中典之换根 DP。

发现进行操作的贡献是 \(\operatorname{size}\times c\)，影响是子树中所有点 \(\oplus c\)，于是考虑拆位，考虑 \(c = 2^k\) 的互不影响的若干次操作，再将所有位的答案累计即可。

拆位后每个结点的权值 \(b_i\) 只有 0/1 两种情况这太典中典之树形 DP 了。先考虑以 1 为根的情况，于是设 \(f_{i, 0/1}\) 表示将以 \(u\) 为根的子树全部置为 0/1 的最小代价，若当前拆出的是第 \(k\) 位则有：

\[\begin{aligned} f_{u, b_u} &= \sum_{v \in \operatorname{son}(u)} f_{v, b_u}\\ f_{u, \overline{b_u}} &= f_{u, b_u} + \operatorname{size}_u\times 2^k \end{aligned}\]

发现恒有 \(f_{u, b_u} < f_{u, \overline{b_u}}\)，则对于第 \(k\) 位以 1 为根的答案即 \(f_{1, b_u}\)。

再考虑换根，考虑从父亲 \(u\) 移向儿子 \(v\) 对所有节点的 \(f\) 影响，发现对于此题仅会影响 \(u, v\) 的 \(f\)。记 \(g_{u, 0/1}\) 表示以 \(u\) 为根时，将整棵树全部置为 0/1 的最小代价，则有：

\[\begin{aligned} f'_{u, b_{u}} &= g_{u, b_u} - f_{v, b_u}\\ f'_{u, \overline{b_u}} &= f'_{u, b_{u}} + (n - \operatorname{size}_v)\times 2^k\\ g_{v, b_v} &= f'_{u, b_v} + f_{v, b_v}\\ g_{v, \overline{b_v}} &= g_{v, b_v} + n\times 2^k \end{aligned}\]

注意换根的写法，\(f'_u\) 仅在计算 \(g_v\) 时有效，并不会真正修改 \(f\) 数组的值。则对于第 \(k\) 位，对答案 \(m_u\) 的贡献即为 \(g_{u, b_u}\)，求和即可。

总时间复杂度 \(O(n\log w)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, edgenum, head[kN], v[kM], ne[kM];
int sz[kN];
LL a[kN], b[kN], f[kN][2], g[kN][2], ans[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Init() {
  n = read();
  
  edgenum = 0;
  for (int i = 1; i <= n; ++ i) {
    head[i] = sz[i] = 0;
    ans[i] = 0;
  }

  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
}
void Dfs1(int u_, int fa_, LL val_) {
  sz[u_] = 1;
  f[u_][0] = f[u_][1] = g[u_][0] = g[u_][1] = 0;

  int type = (b[u_] > 0);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs1(v_, u_, val_);
    
    f[u_][type] += f[v_][type]; 
    f[u_][!type] += f[v_][type];
    sz[u_] += sz[v_];
  }
  f[u_][!type] += 1ll * sz[u_] * val_;
}
void Dfs2(int u_, int fa_, LL val_) {
  ans[u_] += g[u_][b[u_] > 0];
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;

    int tu = (b[u_] > 0), tv = (b[v_] > 0);
    LL fu[2] = {};
    fu[tu] = g[u_][tu] - f[v_][tu]; 
    fu[!tu] = fu[tu] + 1ll * (n - sz[v_]) * val_;
    
    g[v_][tv] = f[v_][tv] + fu[tv];
    g[v_][!tv] = g[v_][tv] + 1ll * n * val_;
    Dfs2(v_, u_, val_);
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    for (int i = 0; i < 20; ++ i) {
      for (int j = 1; j <= n; ++ j) b[j] = a[j] & (1 << i);
      Dfs1(1, 0, (1ll << i)); 
      g[1][0] = f[1][0], g[1][1] = f[1][1];
      Dfs2(1, 0, (1ll << i));
    }
    for (int i = 1; i <= n; ++ i) printf("%lld ", ans[i]);
    printf("\n");
  }
  return 0;
}

E1

暴力的构造。

发现先对 1 再对 \(n\) 操作可以维持形态。于是显然的想法是先分别求出复原 \(p, q\) 的方案，猜测方案步数奇偶性相同则有解，用上述操作补全步数之差即可。

又发现对于已复原的且 \(n\) 为奇数的排列，进行 \(n\) 次位置 1 的操作后可以维持形态并改变复原方案的奇偶性，于是修正上面的判无解条件，大胆猜测当且仅当 \(n,m\) 均为偶数且步数奇偶性不同时无解。

然后考虑如何复原 \(p\)，一个想法是考虑每次将 \(i+1\) 接到 \(i\) 后面，并使 \(1\sim i\) 为一个连续的子序列。手玩一下发现可以先对 \(\operatorname{pos}_{i}+1\) 操作使得保持 \(1\sim i\) 为连续子序列下将 \(i\) 移动到末尾，再对 \(\operatorname{pos}_{i+1}\) 操作即可将 \(i+1\) 接到 \(i\) 后面。

按照上述方案进行操作至多进行 \(O(2\times n)\) 步，数据范围不大可以直接暴力进行。再加上改变奇偶性的 \(n\) 步，则至多进行 \(O(3\times n)=7500\le 10000\) 步。

总复杂度 \(O(n^2 + m^2)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2510;
//=============================================================
int n, m, a[kN], b[kN], temp[kN];
std::vector <int> ans1, ans2;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Modifya(int pos_) {
  int len = 0;
  for (int i = pos_ + 1; i <= n; ++ i) temp[++ len] = a[i];
  temp[++ len] = a[pos_];
  for (int i = 1; i < pos_; ++ i) temp[++ len] = a[i];
  for (int i = 1; i <= n; ++ i) a[i] = temp[i];
}
void Modifyb(int pos_) {
  int len = 0;
  for (int i = pos_ + 1; i <= m; ++ i) temp[++ len] = b[i];
  temp[++ len] = b[pos_];
  for (int i = 1; i < pos_; ++ i) temp[++ len] = b[i];
  for (int i = 1; i <= m; ++ i) b[i] = temp[i];
}
void Calc() {
  int p;
  for (int i = 1; i < n; ++ i) {
    for (p = 1; a[p] != i; ++ p);
    if (p != n) ans1.push_back(p + 1), Modifya(p + 1);
    for (p = 1; a[p] != i + 1; ++ p);
    ans1.push_back(p), Modifya(p);
  }

  for (int i = 1; i < m; ++ i) {
    for (p = 1; b[p] != i; ++ p);
    if (p != m) ans2.push_back(p + 1), Modifyb(p + 1);
    for (p = 1; b[p] != i + 1; ++ p);
    ans2.push_back(p), Modifyb(p);
  }
}
void Print() {
  printf("%d\n", std::max(ans1.size(), ans2.size()));
  if (ans1.size() <= ans2.size()) {
    int i = 0;
    for (int sz = ans1.size(); i < sz; ++ i) {
      printf("%d %d\n", ans1[i], ans2[i]);
    }
    for (int j = 0, sz = ans2.size(); i < sz; ++ i, ++ j) {
      printf("%d %d\n", (j & 1) ? n : 1, ans2[i]);
    }
  } else {
    int i = 0;
    for (int sz = ans2.size(); i < sz; ++ i) {
      printf("%d %d\n", ans1[i], ans2[i]);
    }
    for (int j = 0, sz = ans1.size(); i < sz; ++ i, ++ j) {
      printf("%d %d\n", ans1[i], (j & 1) ? m : 1);
    }
  }
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  n = read(), m = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i <= m; ++ i) b[i] = read();
  Calc();
  
  // printf("--%d %d\n", ans1.size(), ans2.size());
  
  if (ans1.size() % 2 == ans2.size() % 2) {
    Print();
    return 0;
  }
  if (n % 2 == 1) {
    for (int i = 1; i <= n; ++ i) ans1.push_back(1);
    Print();
    return 0;
  }
  if (m % 2 == 1) {
    for (int i = 1; i <= m; ++ i) ans2.push_back(1);
    Print();
    return 0;
  }
  printf("-1\n");
  return 0;
}

E2

牛逼构造，懒了，跑路！

写在最后

学到了什么：

  • B：考虑什么不在集合中。
  • C：尝试通过理想情况进行拓展（？
  • D：复习了换根 DP。

标签：ch,int,899,Codeforces,long,kN,isdigit,Div,getchar
From： https://www.cnblogs.com/luckyblock/p/17757669.html

相关文章

  • CodeForces 1882E2 Two Permutations (Hard Version)
    洛谷传送门CF传送门如何评价，模拟赛搬了一道，前一天晚上代码写了一半的题。考虑如何让操作次数最小。发现直接做太困难了。根本原因是，一次操作对序列的影响太大了。考虑做一些转化，减少一次操作对序列的影响。仍然先考虑一个排列怎么做。不知道为什么可以想到在排列前面添加特......
  • Codeforces Round 834 (Div. 3)
    CodeforcesRound834(Div.3) A-Yes-Yes?思路：判断每种情况即可#include<bits/stdc++.h>usingnamespacestd;//#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair<string,int>PSI;typed......
  • pytorch nn.KLDivLoss()损失计算
    参考：https://blog.csdn.net/L888666Q/article/details/126346022?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-1-126346022-blog-128974654.235^v38^pc_relevant_default_base&spm=1001.2101.3001.4242.2&utm_relev......
  • Educational Codeforces Round 156 A-D
    A.SumofThree思路1：1.把数拆成1，2，n-32.如果（n-3）%3==0,那么拆成1,4,n-5，可证明n-3如果可被3整除，那么再左移两位一定除不尽思路2：1.如果n是奇数，那么可取一个数为2，其他两数为相邻数，如果两数其中一位被整除，那么两者往外走2.如果n为偶，那么可取一个数为1，同理上点击查看代码#inclu......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    Preface沉迷Galgame不打CF懒狗闪总出列！这场在大物课上口胡了前四个题，回去写了也都很顺，然后E题本来做不来的，看了眼昨天校队群里的消息就会做了F题什么东西直接弃A.SumofThree当\(n\bmod3\ne0\)时，用\((1,2,z)\)来凑；否则当\(n\bmod3=0\)时，用\((1,4,z)\)来凑#include<cst......
  • Codeforces Round 706 (Div. 2) A. Split it!
    给一个长度为\(n\)的字符串\(s\)。给定一个正整数\(k\)。询问\(s\)能否等于\(a_1+a_2+\cdots+a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\cdots+R(a_{1})\)。其中\(a_i\)代表一个非空字符串，\(R(a_i)\)代表\(a_i\)的\(reverse\)。由于\(a_{k+1}\)......
  • Codeforces Round 707 (Div. 2, based on Moscow Open Olympiad in Informatics) B. N
    按以下\(n\)次操作制作蛋糕。叠上第\(i\)块面包，然后浇上\(a_i\)单位的奶油。可以使当前往下\(a_i\)块面包沾上奶油。输出空格隔开的\(n\)个数，第\(i\)个的\(0/1\)代表第\(i\)块面包是否沾有奶油。比较显然的思路可以进行差分修改。view1#include<bits/std......
  • Codeforces Round 834 (Div. 3)
    A.Yes-Yes?#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<int,int>;usingvi=vector<int>;conststringT="Yes";voidsolve(){strings;cin>>s;inti=-1;......
  • Codeforces Round 902 Div 1 (CF 1876)
    A.HelmetsinNightLight按花费sort一下，\(b<p\)就让他用\(b\)的花费告诉别人，剩下的人一开始用\(p\)的花费告诉即可。B.EffectsofAntiPimples发现一个数会被所有它的因数贡献，\(O(n\sqrt{n})\)随便算一算，式子略。C.AutosynthesisSolution1想到了建图但没有完......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    EducationalCodeforcesRound156(RatedforDiv.2)A.SumofThree解题思路:如果\(n\leq6或n=9\),无解。若\(n\%3==0，t=\lfloor\frac{3}{n}\rfloor\):若\(t=0\)构造\(1,4,n-5\)否则，构造\(t-3,t,t+3\)若\(n\%3==1:构造1,2，n-3\)若\(n......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99