首页 > 其他分享 >HDU 暑假多校 2023 第六场

HDU 暑假多校 2023 第六场

时间：2023-08-05 16:22:18浏览次数：48  
标签：第六场 ch int LL HDU up down 多校 include

目录

写在前面

补题地址：https://acm.hdu.edu.cn/listproblem.php?vol=64，题号 7336~7346。

哈哈，单刷 5 题，我是只会做套路题的飞舞。

Boc'z 那个单曲太牛逼了，最喜欢的一首，但是 live 上唱的这首是真难绷。

以下按个人向难度排序。

7336

显然若 \(n\le 2\times k\) 则前后两段任意并相同，中间一段任意，答案即 \(m^{k}\times m^{n - 2\times k} = m^{n - k}\)；若 \(n = k\) 答案即 \(m^n\)，否则序列由长度为 \(n-k\) 的循环节构成，答案仍为 \(m^{n - k}\)。

注意快速幂中要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模要对底数取模。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 998244353;
//=============================================================
//=============================================================
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;
}
LL Qpow(LL x_, LL y_) {
  LL ret = 1;
  x_ %= p;
  for (; y_; y_ >>= 1ll) {
    if (y_ & 1) ret = ret * x_ % p;
    x_ = x_ * x_ % p;
  }
  return ret % p;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    LL n, m, k;
    scanf("%lld%lld%lld", &n, &m, &k);
    LL ans = 0;
    if (n - 2 * k >= 0) ans = Qpow(m, k) * Qpow(m, n - 2 * k) % p;
    else if (k < n) ans = Qpow(m, n - k);
    else ans = Qpow(m, n);
    printf("%lld\n", ans);
  }
  return 0;
}
/*
1
5 2 4
*/

7341

暴力即可。枚举要修改的位置再枚举包含这个位置的所有区间，考虑使这些区间变为平方数时该位置要被修改为什么值，取贡献最大的目标值即可。

写的好看就 \(O(n^3)\)。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 310;
//=============================================================
bool square[kN * kN];
int n, allcnt, a[kN], sum[kN], cnt[kN];
int ans;
//=============================================================
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() {
  allcnt = 0;
}
void Solve() {
  for (int i = 1; i <= n; ++ i) {
    for (int j = i; j <= n; ++ j) {
      if (square[sum[j] - sum[i - 1]]) ++ allcnt;
    }
  }
  ans = allcnt;

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= 300; ++ j) cnt[j] = 0;

    for (int l = 1; l <= i; ++ l) {
      for (int r = i; r <= n; ++ r) {
        int s = sum[r] - sum[l - 1];
        int mins = s - a[i] + 1, maxs = s - a[i] + 300;
        for (int j = sqrt(mins - 1) + 1; j <= sqrt(maxs); ++ j) {
          cnt[j * j - (s - a[i])] ++;
        }
      }
    }

    for (int j = 1; j <= 300; ++ j) {
      ans = std::max(ans, allcnt - cnt[a[i]] + cnt[j]);
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  for (int i = 1; i <= 300; ++ i) square[i * i] = true;

  int T = read();
  while (T --) {
    Init();
    n = read();
    for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      sum[i] = sum[i - 1] + a[i];
    }
    Solve();
    printf("%d\n", ans);
  }
  return 0;
}

7345

每个节点出度均为 1，构成了一棵基环内向树，显然一段路径的贡献可以表示成 \(k\times x + b\) 的形式，两段路径也可以直接合并。直接无脑倍增预处理从某个节点走 \(2^k\) 步对答案的贡献即可。总时间复杂度 \(O((n + q)\log v)\) 级别。

注意询问中的 \(l\le 10^9\)，\(\log v\) 要取到 30 左右。

//
/*
By:Luckyblock
*/
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 1e9 + 7;
//=============================================================
int n, q, k[kN], b[kN], fa0[kN];
int fa[kN][32];
LL kk[kN][32], bb[kN][32];
//=============================================================
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(), q = read();
  for (int i = 1; i <= n; ++ i) k[i] = read();
  for (int i = 1; i <= n; ++ i) b[i] = read();
  for (int i = 1; i <= n; ++ i) fa0[i] = read();
  
  for (int i = 1; i <= n; ++ i) {
    fa[i][0] = fa0[i];
    kk[i][0] = k[fa0[i]];
    bb[i][0] = b[fa0[i]];
  }
  for (int i = 1; i <= 32; ++ i) {
    for (int u_ = 1; u_ <= n; ++ u_) {
      int fa1 = fa[u_][i - 1];
      
      fa[u_][i] = fa[fa1][i - 1];
      kk[u_][i] = kk[u_][i - 1] * kk[fa1][i - 1] % p;
      bb[u_][i] = (kk[fa1][i - 1] * bb[u_][i - 1] % p + bb[fa1][i - 1]) % p;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    while (q --) {
      int x = read(), l = read(), y = read();
      LL ans = y, nowl = l;
      for (int i = 32; i >= 0; -- i) {
        LL len = (1ll << i);
        if (len <= nowl) {
          nowl -= len;
          ans = (kk[x][i] * ans % p + bb[x][i]) % p;
          x = fa[x][i];
        }
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}

7337

扫描线套路，比较有印象的例子是 HH 的项链。

\(p\) 是 \(1\sim n\) 的排列，那么 \(p_i + p_j \le 2\times n - 1\)，可以组成的平方数的种类仅有 \(\sqrt n\) 级别；并且保证了对于每个数，当组成某种平方数时它的另一半的位置是唯一的。

一个直观的想法是对于某个询问区间 \([l, r]\) 中的元素 \(p_i\)，考虑枚举它可以组成的平方数 \(s^2\)，如果 \(s^2 - p_i\) 位于区间 \([i + 1, r]\) 中则贡献加 1。于是考虑上面的扫描线套路，考虑降序枚举询问的左端点 \(L\)，枚举元素 \(p_L\) 可以组成的平方数的另一半 \(s^2 - p_L\) 存在的位置 \(q\)，如果存在则令位置 \(q\) 的贡献加 1；在此过程中同时按照左端点降序枚举询问，枚举到对应询问的左端点时直接查询区间和即可。

上述过程需要支持单点修改，查询区间和，用树状数组简单维护即可，总复杂度 \(O(n\sqrt n\log n + q\log n)\) 级别。因为常数太小辣，跑得相当快。

给结构体起名好麻烦呃呃呃呃，现在遇到结构体就写脑子第一个想到的单词。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, q, p[kN], pos[kN];
struct AdmireVega {
  int l, r, id;
} ayabe[kN];
LL 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;
}
bool cmp(AdmireVega fir_, AdmireVega sec_) {
  return fir_.l > sec_.l;
}
namespace BIT {
  #define lowbit(x) ((x)&(-x))
  const int kL = kN;
  int lim;
  LL f[kN];
  void Init(int n_) {
    lim = n_;
    for (int i = 1; i <= lim; ++ i) f[i] = 0ll;
  }
  void Insert(int pos_, int val_) {
    for (int i = pos_; i <= lim; i += lowbit(i)) {
      f[i] += val_;
    }
  }
  LL Sum(int pos_) {
    LL ret = 0;
    for (int i = pos_; i; i -= lowbit(i)) {
      ret += f[i];
    }
    return ret;
  }
  LL Query(int l_, int r_) {
    return Sum(r_) - Sum(l_ - 1);
  }
  #undef lowbit
}
void Solve() {
  int sqrtlim = sqrt(2 * n - 1);

  for (int nowl = n, nowq = 1; nowl && nowq <= q; -- nowl) {
    int i = p[nowl];
    for (int j = sqrt(i) + 1; j <= sqrtlim; ++ j) {
      if (j * j - i < 0) continue;
      if (j * j - i > n) break;
      if (pos[j * j - i] > nowl) BIT::Insert(pos[j * j - i], 1); 
    }
    while (nowq <= q && ayabe[nowq].l == nowl) {
      ans[ayabe[nowq].id] = BIT::Query(nowl, ayabe[nowq].r);
      ++ nowq;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    BIT::Init(n);
    for (int i = 1; i <= n; ++ i) {
      p[i] = read();
      pos[p[i]] = i;
    }

    q = read();
    for (int i = 1; i <= q; ++ i) {
      int l_ = read(), r_ = read();
      ayabe[i] = (AdmireVega) {l_, r_, i};
    }
    std::sort(ayabe + 1, ayabe + q + 1, cmp);
    Solve();
    for (int i = 1; i <= q; ++ i) printf("%lld\n" ,ans[i]);
  }
  return 0;
}

7339

点分治板题，赛时去博客里贺了份板子改了改 1A 了。

在点分治统计过根节点路径时，当两条路径上的颜色数量可以互补时，可以拼接成一条有贡献的路径。设某条路径三种颜色数量分别为 \((a, b, c)\)，我们设该路径的颜色差为一个三元组 \((b - a, c - b, a - c)\)，显然颜色差与该路径完全相反的路径可以与该路径互补拼接成一条有贡献的路径。

于是开个桶记录每种颜色差的路径的数量即可，完全是板题呃呃呃呃。

算上 map 总时间复杂度为 \(O(n\log^2 n)\) 级别。

//知识点：点分治
/*
By:Luckyblock
*/
#include <map>
#include <queue>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define LL long long
#define pr std::pair
#define mp std::make_pair
#define AdmireVega pr <int, pr <int, int> >
const int kN = 1e5 + 10;
//=============================================================
int n, edgenum, head[kN], v[kN << 1], ne[kN << 1];
int root, sumsz, sz[kN], maxsz[kN];
char s[kN];
bool vis[kN];
LL ans;
AdmireVega dis[kN];
std::map <AdmireVega, int> exist;
std::vector <AdmireVega> tmp;
std::queue <AdmireVega> tag;
//=============================================================
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 Chkmax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_]; 
  head[u_] = edgenum;
}
void CalcSize(int u_, int fa_) { //求重心
  sz[u_] = 1, maxsz[u_] = 0;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    CalcSize(v_, u_);
    Chkmax(maxsz[u_], sz[v_]);
    sz[u_] += sz[v_];
  }
  Chkmax(maxsz[u_], sumsz - sz[u_]);
  if (maxsz[u_] < maxsz[root]) root = u_;
}
AdmireVega F(AdmireVega x_) {
  int a_ = x_.first, b_ = x_.second.first, c_ = x_.second.second;
  return mp(b_ - a_, mp(c_ - b_, a_ - c_));
}
void CalcDis(int u_, int fa_) { //求得各点到当前根的距离
  tmp.push_back(dis[u_]);
  int ua = dis[u_].first;
  int ub = dis[u_].second.first;
  int uc = dis[u_].second.second;
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    if (s[v_] == 'a') dis[v_] = mp(ua + 1, mp(ub, uc));
    if (s[v_] == 'b') dis[v_] = mp(ua, mp(ub + 1, uc));
    if (s[v_] == 'c') dis[v_] = mp(ua, mp(ub, uc + 1));
    CalcDis(v_, u_);
  }
}
void Dfs(int u_, int fa_) {
  int ua = (s[u_] == 'a');
  int ub = (s[u_] == 'b');
  int uc = (s[u_] == 'c');
  exist[mp(0, mp(0, 0))] = 1;
  tag.push(mp(0, mp(0, 0)));
  vis[u_] = true; //标记已处理
  
  for (int i = head[u_]; i; i = ne[i]) { //处理链信息
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    if (s[v_] == 'a') dis[v_] = mp(1, mp(0, 0));
    if (s[v_] == 'b') dis[v_] = mp(0, mp(1, 0));
    if (s[v_] == 'c') dis[v_] = mp(0, mp(0, 1));
    CalcDis(v_, u_);
    for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
      int a_ = tmp[j].first;
      int b_ = tmp[j].second.first;
      int c_ = tmp[j].second.second;

      AdmireVega ayabe = F(mp(a_ + ua, mp(b_ + ub, c_ + uc)));
      a_ = ayabe.first;
      b_ = ayabe.second.first;
      c_ = ayabe.second.second;
      ans += exist[mp(-a_, mp(-b_, -c_))];
    }
    for (int j = 0, lim = tmp.size(); j < lim; ++ j) {
      AdmireVega ayabe = F(tmp[j]);
      tag.push(ayabe);
      if (!exist.count(ayabe)) exist[ayabe] = 1;
      else exist[ayabe] ++;
    }
    tmp.clear();
  }
  while (!tag.empty()) {
    exist[tag.front()] = 0;
    tag.pop();
  }

  for (int i = head[u_]; i; i = ne[i]) { //分治求解
    int v_ = v[i];
    if (v_ == fa_ || vis[v_]) continue;
    sumsz = sz[v_];
    root = 0, maxsz[root] = kN;
    CalcSize(v_, u_), CalcSize(root, 0), Dfs(root, 0);
  }
}
//=============================================================
int main() { 
  // freopen("1.txt", "r", stdin);
  n = read();
  scanf("%s", s + 1);
  for (int i = 1; i < n; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_), Add(v_, u_);
  }
  
  sumsz = n;
  root = 0, maxsz[root] = kN;
  CalcSize(1, 0), CalcSize(root, 0), Dfs(root, 0);
  printf("%lld\n", ans);
  return 0;
}

7338

判断四个三维向量是否线性相关。

纯现代题，绷不住了我草，手写了分数运算类模拟初等行变换怎么就是过不去啊我草，我疯了，咕咕。

我先在这里放一拖四。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#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;
}
struct AdmireVega {
  LL up, down;
} a[5][5], ans[5];
LL gcd(LL x_, LL y_) {
  return y_ ? gcd(y_, x_ % y_) : x_;
}
LL lcm(LL x_, LL y_) {
  return x_ / gcd(x_, y_) * y_;
}
bool Equal1(AdmireVega fir_) {
  return fir_.up == 1 && fir_.down == 1;
}
bool Zero(AdmireVega fir_) {
  return fir_.up == 0;
}
bool Negative(AdmireVega fir_) {
  return fir_.up < 0;
}
AdmireVega Abs(AdmireVega fir_) {
  return (AdmireVega) {abs(fir_.up), fir_.down};
}
bool Cmp(AdmireVega fir_, AdmireVega sec_) {
  LL down = lcm(fir_.down, sec_.down);
  LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
  return up1 > up2;
}
AdmireVega Plus(AdmireVega fir_, AdmireVega sec_) {
  LL down = lcm(fir_.down, sec_.down);
  LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
  LL up = up1 + up2;
  if (up == 0) down = 1ll;
  LL d = gcd(abs(up), abs(down));
  if (down < 0 && up > 0) up = -up, down = -down;
  if (down < 0 && up < 0) up = -up, down = -down;
  return (AdmireVega) {up / d, down / d};
}
AdmireVega Minus(AdmireVega fir_, AdmireVega sec_) {
  LL down = lcm(fir_.down, sec_.down);
  LL up1 = down / fir_.down * fir_.up, up2 = down / sec_.down * sec_.up;
  LL up = up1 - up2;
  if (up == 0) down = 1ll;
  LL d = gcd(abs(up), abs(down));
  if (down < 0 && up > 0) up = -up, down = -down;
  if (down < 0 && up < 0) up = -up, down = -down;
  return (AdmireVega) {up / d, down / d};
}
AdmireVega Prod(AdmireVega fir_, AdmireVega sec_) {
  LL up = fir_.up * sec_.up;
  LL down = fir_.down * sec_.down;
  if (up == 0) down = 1ll;
  LL d = gcd(abs(up), abs(down));
  if (down < 0 && up > 0) up = -up, down = -down;
  if (down < 0 && up < 0) up = -up, down = -down;
  return (AdmireVega) {up / d, down / d};
}
AdmireVega Div(AdmireVega fir_, AdmireVega sec_) {
  LL up = fir_.up * sec_.down;
  LL down = fir_.down * sec_.up;
  if (up == 0) down = 1ll;
  LL d = gcd(abs(up), abs(down));
  if (down < 0 && up > 0) up = -up, down = -down;
  if (down < 0 && up < 0) up = -up, down = -down;
  return (AdmireVega) {up / d, down / d};
}
bool Solve() {
  int r1 = 0, r2 = 0;

  int pos1[5] = {0};

  for (int i = 1, k = 1; i <= 3 && k <= 3; ++ i, ++ k) { //每次将第 i 行第 k 个元素消为 1。 
    int pos = i;  //每次找到最大系数消除，减小误差 
    for (int j = i + 1; j <= 3; ++ j) {
      if (Cmp(Abs(a[j][k]), Abs(a[pos][k]))) {
        pos = j;
      }
    }
    
    if (Zero(a[pos][k])) { //系数为 0，跳
      -- i;
      continue;
    }
    pos1[++ r1] = k;
    
    for (int j = 1; j <= 4; ++ j) { //交换到第 i 行 
      std::swap(a[pos][j], a[i][j]);
    }
    
    AdmireVega tmp = a[i][k]; //将第 i 行第 k 个消成 1，同时处理该行其他系数 
    for (int j = k; j <= 4; ++ j) {
      a[i][j] = Div(a[i][j], tmp);
    }
    for (int j = i + 1; j <= 3; ++ j) { //枚举其他行 
      tmp = a[j][k]; //该行对应系数 
      for (int l = k; l <= 4; ++ l) {
        a[j][l] = Minus(a[j][l], Prod(a[i][l], tmp));
        
        // a[j][k] -= a[i][k] * tmp; //注意第 i 行的系数均已被处理过 
      }
    }
  }
  r2 = r1;
  for (int i = r1 + 1; i <= 3; ++ i) {
    if (!Zero(a[i][4])) ++ r2;
  }
  if (r2 > r1) return 0;  

  ans[r1] = a[r1][4];
  for (int i = r1 - 1; i >= 1; -- i) {
    ans[i] = a[i][4];
    for (int j = i + 1; j <= r1; ++ j) { //回带
      ans[i] = Minus(ans[i], Prod(a[i][pos1[j]], ans[j]));
      // ans[i] -= a[i][j] * ans[j];
    }
  }

  for (int i = 1; i <= r1; ++ i) {
    if (Negative(ans[i])) return 0;
  }
  return 1;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    for (int i = 1; i <= 4; ++ i) {
      for (int j = 1; j <= 3; ++ j) {
        LL x = read();
        a[j][i] = (AdmireVega) {x, 1ll};
      }
    }
    printf("%s\n", Solve() ? "YES" : "NO");
  }
  return 0;
}
/*
1
1 0 0 1 0 0 1 0 0 3 0 0

1
0 0 0 0 0 0 0 1 0 0 2 1

1
1 0 0 2 0 0 0 1 0 1 1 0

1
1 0 1 1 0 1 1 0 1 1 0 2

1
1 0 0 1 0 0 1 1 0 0 1 0

1
1 0 0 0 0 0 0 0 1 1 0 2

1
1 0 0 1 0 1 1 1 0 2 1 1
*/

写在最后

学到了什么：

  • 快速幂中要对底数取模。
  • 看数据范围确定倍增的上限。

标签：第六场,ch,int,LL,HDU,up,down,多校,include
From： https://www.cnblogs.com/luckyblock/p/17608107.html

相关文章

  • 牛客暑假多校 2023 第六场
    目录写在前面GECBA写在最后写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57360。哈基米牛魔酬宾，哈比下，哈比下，奥利安费，阿米诺斯！以下按照个人向难度排序。G\(a-b\)相当于辗转相减，\(\gcd(|a|,|b|)\)和直接\(\gcd\)没什么区别。于是当\(z=0\)时，\(x,y\)中一......
  • 2023年多校联训NOIP层测试3+「SFCOI-3」Sadness Fan Club Round 3
    2023年多校联训NOIP层测试3T1数列变换\(10pts\)考虑暴力，发现\(f\)数列进行一次变换\(A\)，再进行一次变换\(B\)后，恢复成了原数列；\(f\)数列进行一次变换\(B\)，再进行一次变换\(A\)后，也恢复成了原数列。即变换\(A\)可以和变换\(B\)相互抵消。本质是差分是前缀......
  • 【题解】[2023牛客多校] Distance
    题目传送门：[2023牛客多校]Distance题意对于任意两个元素个数相同的set：A、B，每次可以执行以下两种操作之一：将A中的任意元素加一将B中的任意元素加一\(C(A,B)\)含义为将\(A、B\)改变为完全相同的set所需要花费的最小次数；初始给你两个set：\(S、T\)，计算\(\sum_{A\subs......
  • #轮廓线dp#HDU 1400 Mondriaan's Dream
    题目传送门分析状压dp会TLE，考虑用轮廓线dp，设\(dp[i][j][S]\)表示现在处理到\((i,j)\)这个位置轮廓线上状态为\(S\)的情况二进制位为1表示左边或者上方有骨牌跨过轮廓线，然后分类讨论转移一下即可代码#include<cstdio>#include<cstring>usingnamespacestd;con......
  • 牛客多校友谊赛
    D-吹_23暑假友谊赛No.2(nowcoder.com)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;constintN=1e6+50,INF=0x3f3f3f3f;inta[N],dp[N][2];signedmain(){intn;cin>>n;for......
  • 暑假牛客多校第五场 2023-7-31（G、D、H）
    未补完G.GotoPlayMaimaiDX算法：双指针做法：从左到右用两个指针维护一段区间且右指针不断右移，当这个区间满足题目所给的性质，我们取出区间长度，然后再将左指针右移，直到右指针到边界且左指针指到不符合题目的性质的位置结束，期间不断对符合题目性质的区间长度取最小值。code......
  • 2023牛客暑期多校训练营5
    之前落下的每一场比赛都是要补回来的。。。GGotoPlayMaimaiDX题解的想法比较简单，由于找到满足1，2，3出现至少一次，4出现至少k次的最短区间，所以可以双指针，双指针用于这种长度最短，长度越长越容易满足条件的题就很恰当。我没想到双指针，就写的比较麻烦，预处理每个数后一个1，2，3的位置......
  • 2023年多校联训NOIP层测试2
    2023年多校联训NOIP层测试2爆零了T1HDU4786FibonacciTree\(0pts\)@wangyunbiao:不可以，总司令我：不，可以，总司令T2期末考试\(0pts\)T3麻烦的工作\(0pts\)@wangyunbiao:不可以，总司令我：不，可以，总司令T4小X的Galgame\(0pts\)......
  • 【题解】HDOJ 7329 [2023杭电多校] Touhou Red Red Blue
    题目传送门：HDOJ7329[2023杭电多校]TouhouRedRedBlue题意有两个口袋（口袋容量为1，初始均为空），有若干个UFO按顺序来到你的面前，每个UFO有一个颜色（GRB），你可以选择扔掉它或者把它装进口袋中，如果口袋1空着必须装进口袋1；如果口袋都满了，算上面前的UFO共有三个，有如下三种情况：如......
  • 牛客暑假多校 2023 第五场
    目录写在前面GDHCEI写在最后写在前面战犯在此。我宣布二周年这首是神。以下按个人向难度排序。G尺取法，右端点单调右移过程中右移调整左端点，使区间内每种数都至少出现1次，4出现至少\(k\)次即可。///*By:Luckyblock*/#include<cmath>#include<cstdio>#include<......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99