首页 > 其他分享 >区域赛

区域赛

时间：2024-09-03 16:18:13浏览次数：2  
标签：return int long 区域 vec dist id

The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)

K - Rainbow Subarray

 

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

namespace Set {
  const int kInf = INT_MAX / 2;
  i64 sum1, sum2;
  int sz1, sz2;
  multiset<int> less, greater;
  void init() {
    sum1 = sum2 = sz1 = sz2 = 0;
    less.clear(), greater.clear();
    less.insert(-kInf), greater.insert(kInf);
  }
  void adjust() {
    while (less.size() > greater.size() + 1) {
      multiset<int>::iterator it = (--less.end());
      greater.insert(*it);
      less.erase(it);
      sum1 -= *it; sum2 += *it;
      sz1--; sz2++;
    }
    while (greater.size() > less.size()) {
      multiset<int>::iterator it = greater.begin();
      less.insert(*it);
      greater.erase(it);
      sum1 += *it; sum2 -= *it;
      sz1++; sz2--;
    }
  }
  void add(int val_) {
    if (val_ <= *greater.begin()) {
      sum1 += val_; sz1++;
      less.insert(val_);
    } else {
      sum2 += val_; sz2++;
      greater.insert(val_);
    }
    adjust();
  }
  void del(int val_) {
    multiset<int>::iterator it = less.lower_bound(val_);
    if (it != less.end()) {
      less.erase(it);
      sum1 -= *it;
      sz1--;
    } else {
      it = greater.lower_bound(val_);
      greater.erase(it);
      sum2 -= *it;
      sz2--;
    }
    adjust();
  }
  int get_middle() {
    return *less.rbegin();
  }
}

void solve() {
  i64 n, k; cin >> n >> k;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] -= i; 
  }
  Set::init();
  auto check = [&]() {
    i64 v = Set::get_middle();
    i64 sum = v * Set::sz1 - Set::sum1 + Set::sum2 - v * Set::sz2;
    return sum <= k;
  };
  i64 ans = 0;
  for (int i = 1, j = 1; i <= n; i++) {
    Set::add(a[i]);
    while (j < i && !check()) {
      Set::del(a[j]);
      j++;
    }
    ans = max(ans, (i64)Set::sz1 + (i64)Set::sz2);
  } cout << ans << endl;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int T; cin >> T;
  while (T--) solve();
  return 0;
}

G - Gifts from Knowledge

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long

using i64 = long long;

const int mod = 1e9 + 7;

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<char>> a(n + 1, vector<char>(m + 1));
    vector<vector<int>> vis(m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '1') vis[j].push_back(i);
        }
    }
    vector<int> fa(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++) {
        fa[i] = i;
    }
    function<int(int)> Find = [&](int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    };
    for (int i = 1; i <= m; i++) {
        int all = vis[i].size() + vis[m + 1 - i].size();
        if (all <= 1) continue;
        else if (all >= 3) {cout << 0 << endl; return;}
        if (vis[i].size() == 2) {
            int id1 = vis[i][0] + n, id2 = vis[i][1];
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;

            id1 = vis[i][0], id2 = vis[i][1] + n;
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;
        } else if (vis[m + 1 - i].size() == 2) {
            int id1 = vis[m + 1 - i][0] + n, id2 = vis[m + 1 - i][1];
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;
            
            id1 = vis[m + 1 - i][0], id2 = vis[m + 1 - i][1] + n;
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;
        } else {
            int id1 = vis[m + 1 - i][0], id2 = vis[i][0];
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;
            
            id1 = vis[m + 1 - i][0] + n, id2 = vis[i][0] + n;
            id1 = Find(id1); id2 = Find(id2);
            if (id1 != id2) fa[id2] = id1;
        }
    }
    auto ksm = [&](i64 a, i64 b) {
        i64 ans = 1 % mod;
        a %= mod;
        while (b) {
            if (b & 1) ans = (ans * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return ans;
    };

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) cnt++;
        if (Find(i) == Find(i + n)) {
            cout << 0 << endl;
            return;
        }
    }
    cout << ksm(2, cnt) << endl;
}

signed main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

 

The 2023 ICPC Asia Shenyang Regional Contest (The 2nd Universal Cup. Stage 13: Shenyang)

E - Sheep Eat Wolves

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

using i64 = long long;

const int N = 105;

int f[N][N][N][2], vis[N][N][N][2];

void solve() {
  int x, y, p, q; cin >> x >> y >> p >> q;
  queue<array<int, 4>> Q;
  memset(f, 127, sizeof f);
  Q.push({x, y, 0, 0});
  f[x][y][0][0] = 0;

  auto check = [&](int l1, int l2) {
    return !l1 || (l1 && l1 + q >= l2);
  };

  int ans = INT_MAX / 2;
  while (!Q.empty()) {
    auto [v1, v2, v3, op] = Q.front(); Q.pop();
    if (vis[v1][v2][v3][op]) continue;
    vis[v1][v2][v3][op] = 1;
    int v4 = y - v2;
    if (v3 == x) {
      ans = min(ans, f[v1][v2][v3][op]);
    }
    for (int i = 0; i <= (op ? v3 : v1); i++) {
      for (int j = 0; j <= (op ? v4 : v2); j++) {
        if (i + j > p) continue;
        if (!op) {
          int l1 = v1 - i, l2 = v2 - j;
          if (check(l1, l2) && !vis[l1][l2][v3 + i][op ^ 1]) {
            Q.push({l1, l2, v3 + i, op ^ 1});
            f[l1][l2][v3 + i][op ^ 1] = min(f[l1][l2][v3 + i][op ^ 1], f[v1][v2][v3][op] + 1);
          }
        } else {
          int l1 = v3 - i, l2 = v4 - j;
          if (check(l1, l2) && !vis[v1 + i][v2 + j][l1][op ^ 1]) {
            Q.push({v1 + i, v2 + j, l1, op ^ 1});
            f[v1 + i][v2 + j][l1][op ^ 1] = min(f[v1 + i][v2 + j][l1][op ^ 1], f[v1][v2][v3][op] + 1);
          }
        }
      }
    }
  }
  cout << (ans == INT_MAX / 2 ? -1 : ans) << endl;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  solve();
  return 0;
}

K - Maximum Rating

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define int long long

using i64 = long long;

const int N = 4e5 + 100;

int a[N];
vector<int> vec;

struct node {
  int cnt;
  i64 sum;
} Seg[N * 4];

node operator + (const node &l, const node &r) {
  node ans; ans.cnt = l.cnt + r.cnt;
  ans.sum = l.sum + r.sum;
  return ans;
}

void pushup(int id) {
  Seg[id] = Seg[id * 2] + Seg[id * 2 + 1];
}

void build(int id, int l, int r) {
  if (l == r) {
    Seg[id] = {0, 0};
    return;
  }
  int mid = l + r >> 1;
  build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r);
  pushup(id);
}

void modify(int id, int l, int r, int pos, int v) {
  if (l == r) {
    Seg[id].sum += v * vec[l - 1];
    Seg[id].cnt += v;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) modify(id * 2, l, mid, pos, v);
  else modify(id * 2 + 1, mid + 1, r, pos, v);
  pushup(id);
}

pair<int, int> query1(int id, int l, int r, int v) {
  if (l == r) return {l, Seg[id].cnt};
  int mid = l + r >> 1;
  if (Seg[id * 2].sum > v) return query1(id * 2, l, mid, v);
  else return query1(id * 2 + 1, mid + 1, r, v - Seg[id * 2].sum);
}

node query2(int id, int l, int r, int x, int y) {
  if (x <= l && y >= r) return Seg[id];
  int mid = l + r >> 1;
  node ans = {0, 0};
  if (x <= mid) ans = ans + query2(id * 2, l, mid, x, y);
  if (y > mid) ans = ans + query2(id * 2 + 1, mid + 1, r, x, y);
  return ans;
}

void solve() {
  int n, q; cin >> n >> q;
  vec.clear();
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    vec.push_back(a[i]);
  }

  vector<array<int, 2>> que(q + 1);
  for (int i = 1; i <= q; i++) {
    int x, v; cin >> x >> v;
    que[i] = {x, v};
    vec.push_back(v);
  }

  vec.push_back(-1e9 - 1); vec.push_back(1e9 + 1);
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());

  auto getid = [&](int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
  };

  int m = vec.size(), z = 0;
  i64 res = 0;
  build(1, 1, m);
  for (int i = 1; i <= n; i++) {
    int id = getid(a[i]);
    if (a[i] > 0) z++;
    modify(1, 1, m, id, 1);
    res += a[i];
  }
  for (int i = 1; i <= q; i++) {
    auto [x, v] = que[i];
    int id1 = getid(a[x]), id2 = getid(v);
    res += v - a[x];
    if (a[x] > 0) z--;
    if (v > 0) z++;
    modify(1, 1, m, id1, -1);
    a[x] = v;
    modify(1, 1, m, id2, 1);
    auto [pos, cnt] = query1(1, 1, m, 0);
    auto [num, sum] = query2(1, 1, m, 1, pos);
    // cout << "TEST" << endl;
    // for (int j = 1; j <= n; j++) {
    //  cout << a[j] << " \n"[j == n];
    // }
    // cout << vec[pos - 1] << ' ' << cnt << ' ' << num << ' ' << sum << endl;
    if (res <= 0) {
      cout << z + 1 << '\n';
      continue;
    }
    int L = 0, R = cnt;
    auto check = [&](int V) {
      return sum - V * vec[pos - 1] > 0;
    };
    while (L + 1 < R) {
      int M = L + R >> 1;
      if (check(M)) L = M;
      else R = M;
    }
    int p = check(R) ? R : L;
    p = num - p + 1;
    cout << z - (n - p + 1) << '\n';
    // cout << "TEST " << i << ' ' << z << endl;
  }
}

signed main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  solve();
  return 0;
}
The 2023 ICPC Asia Hangzhou Regional Contest (The 2nd Universal Cup. Stage 22: Hangzhou)

 

H - Sugar Sweet II

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
#define int long long

using i64 = long long;

const int N = 5e5 + 100;
const int mod = 1e9 + 7;

vector<int> g[N];
int a[N], b[N], w[N];

void solve() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  for (int i = 1; i <= n; i++) cin >> w[i];
  vector<int> tmp;
  for (int i = 1; i <= n; i++) {
    int l = a[b[i]], r = a[b[i]] + w[b[i]];
    if (a[i] >= r) {
      continue;
    } else if (a[i] < l) {
      g[b[i]].push_back(i);
      tmp.push_back(i);
    } else {
      g[b[i]].push_back(i);
    }
  }
  vector<int> dist(n + 1, 1e9), vis(n + 1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  for (auto i : tmp) {
    dist[i] = 0;
    q.push({0, i});
  }
  while (!q.empty()) {
    auto [v, x] = q.top(); q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (auto y : g[x]) {
      if (vis[y]) continue;
      if (dist[y] > dist[x] + 1) {
        dist[y] = dist[x] + 1;
        q.push({dist[y], y});
      }
    }
  }
  auto ksm = [&](i64 a, i64 b) {
    i64 ans = 1 % mod;
    a %= mod;
    while (b) {
      if (b & 1) ans = (ans * a) % mod;
      a = (a * a) % mod;
      b >>= 1;
    }
    return ans;
  };
  vector<int> p(n + 1);
  int v = 1;
  for (int i = 1; i <= n; i++) {
    v *= i; v %= mod;
    p[i] = ksm(v, mod - 2);
  }
  // cout << "TEST" << endl;
  for (int i = 1; i <= n; i++) {
    // cout << i << ' ' << dist[i] << endl;
    int ans = a[i];
    if (dist[i] < (int)1e9) {
      ans = (ans + p[dist[i] + 1] * w[i] % mod) % mod;
    }
    cout << ans << " \n"[i == n];
  }
  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }
}

signed main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int T; cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
 

G - Snake Move

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

const int N = 3005;

char a[N][N];
int X[N * 100], Y[N * 100], bel[N][N], dist[N][N], vis[N][N];
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

void solve() {
  int n, m, k; cin >> n >> m >> k;
  for (int i = 1; i <= k; i++) {
    cin >> X[i] >> Y[i];
    bel[X[i]][Y[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
    }
  }
  memset(dist, 127, sizeof dist);
  priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q;
  dist[X[1]][Y[1]] = 0;
  q.push({0, X[1], Y[1]});
  while (!q.empty()) {
    auto [v, x, y] = q.top(); q.pop();
    if (vis[x][y]) continue;
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++) {
      int nx = x + dir[i][0];
      int ny = y + dir[i][1];
      if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && !vis[nx][ny]) {
        if (bel[nx][ny]) {
          int del = k - bel[nx][ny];
          if (dist[x][y] >= del) {
            if (dist[x][y] + 1 < dist[nx][ny]) {
              dist[nx][ny] = dist[x][y] + 1;
              q.push({dist[nx][ny], nx, ny});
            }
          } else {
            if (dist[x][y] + 1 + del - dist[x][y] < dist[nx][ny]) {
              dist[nx][ny] = dist[x][y] + 1 + del - dist[x][y];
              q.push({dist[nx][ny], nx, ny});
            }
          }
        } else {
          if (dist[x][y] + 1 < dist[nx][ny]) {
            dist[nx][ny] = dist[x][y] + 1;
            q.push({dist[nx][ny], nx, ny});
          }
        }
      }
    }
  }
  u64 ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (dist[i][j] < 1 << 30) {
        ans += (u64)dist[i][j] * dist[i][j];
        // cout << dist[i][j] << " \n"[j == n];
      }
    }
  }
  cout << ans << endl;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  solve();
  return 0;
}

标签：return,int,long,区域,vec,dist,id
From： https://www.cnblogs.com/zhujio/p/18394805

相关文章

  • 中建智地1-8月房山住宅网签29.17亿！房山国贤府成交均价4.2万立区域改善标杆
    来源：中国网中建智地1-8月房山4盘住宅网签844套、成交金额29.17亿元,成为房山住宅网签金额、套数、面积三冠王。其中学府印悦以网签359套、成交金额10.95亿元,荣膺1-8月房山住宅网签金额、套数双冠王。(1-8月房山住宅网签房企排行榜,数据来源:天朗)在刚刚过去的8月,中建智地继续冠领......
  • 白骑士的CSS高级篇之CSS Grid布局进阶 4.1.2 网格模板与区域
            CSSGrid布局是CSS中强大的布局系统之一，它提供了更灵活和更高效的方式来创建复杂的网页布局。通过Grid布局，你可以将网页划分为多个网格区域，并在这些区域中放置内容，这使得布局更加直观和易于维护。本文将深入探讨Grid布局中的网格模板和区域的概念，帮助你掌握如......
  • TPAMI 2024 | 自适应区域特定损失：提高医学图像分割性能
    题目：AdaptiveRegion-SpecificLossforImprovedMedicalImageSegmentation自适应区域特定损失：提高医学图像分割性能作者：YizhengChen;LequanYu;Jen-YeuWang;NeilPanjwani;Jean-PierreObeid;WuLiu;LianliLiu;NataliyaKovalchuk摘要定义损失函数是神经......
  • ImageDraw.Draw 填充区域
    ImageDraw.Draw填充区域在Python的PIL（PythonImagingLibrary，现在通常称为Pillow）库中，ImageDraw.Draw 对象用于在图像上绘制形状。要填充一个区域，你通常会使用 rectangle、ellipse、polygon 等方法，并指定填充颜色。以下是一个使用 ImageDraw.Draw 填充矩形的例子： from......
  • 一个区域总经理的渠道实战手册：开拓、上量、精耕
    老李是某医疗协议品牌商华东区域的区总。面对华东地区庞大的医疗体系和多样化的终端需求，老李深知，在医疗器械领域，精准的渠道布局和深化合作是品牌立足市场的关键。以下是他分享的“渠道三步走”战略以及如何在不同阶段，运用专业策略实现渠道管理的精细化与高效化。 01、渠道开拓：以......
  • 数据无界：大型企业如何实现多区域文件安全传输的无缝体验？
    随着企业全球化发展，大型企业分支机构的分布越来越广泛，多区域文件传输需求也随之增加。目前大型企业多区域文件数据存储和传输交换现状如下：1.文件存储现状：集中和分散并存，局部集中，整体分散；2.文件存储管理：不同区域、分支机构、业务部门，文件存储方案差异化，各自建设，分别管理，比如：FTP服......
  • VTK随笔十：VTK图形处理（封闭性检测、联通区域分析、多分辨率处理）
    一、封闭性检测        如果一条边只被一个多边形包含，那么这条边就是边界边。是否存在边界边是检测一个网格模型是否封闭的重要特征。        vtkFeatureEdges是一个非常重要的类，该类能够提取多边形网格模型中四种类型的边。1)边界边。即只被一个多边形或......
  • Prism:区域(Region)
    Prism:区域(Region)什么是区域？区域(Region)用于实现模块化应用程序中的视图组织和管理。区域允许您在一个或多个视图容器中动态地加载和卸载视图，从而实现灵活的内容布局和管理。区域的用途动态内容加载：您可以将不同的视图加载到同一个区域中，这样可以实现在运行时动态改变应......
  • iTextSharp提取PDF指定区域或整页文字，包括文字大小、颜色、字体等
    介绍iTextSharp：是一个从JAVA项目iText衍生的.Net版本的开源项目。iText是一个PDF库，可让您创建，移植，检查和维护可移植文档格式（PDF）的文档，从而使您可以轻松地向软件项目添加PDF功能。我们甚至提供文档来帮助您进行编码。可以操作PDF的库还有PDFsharp：PDFsharp是一个开源.NET库，......
  • 软设每日一练1——（16进制快速算结果）若用256K×8bit存储器芯片，构成地址40000000H到400F
    题目：若用256K× 8bit的存储器芯片，构成地址40000000H到400FFFFFH且按字节编址的内存区域，则需（        ）片芯片A.4        B.8        C.16        D.32        答案：A解：1、首先看单位，存储器芯片单位是256K× 8bit，地址是字节......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99