首页 > 其他分享 >2025省选模拟5

2025省选模拟5

时间：2025-01-14 12:10:57浏览次数：1  
标签：ubt return 省选 2025 int maxN using 模拟 define

2025省选模拟5

这场比较简单，T1 T2 赛后都是没调打完就过了。既然改完了，而且现在也不想写啥题那就还是补下题解吧。

T1 枇杷树

操作 \(m\le 300\)，每次操作构成一颗新树。具体：用边权为 \(w\) 的边连接编号为 \(x\) 的树中的 \(u\) 号节点，编号为 \(y\) 的树中的 \(v\) 号节点。

询问每颗树中的点两两之间距离。

考虑把两颗树连起来的影响：

\[ans=w\times siz_x \times siz_y+f_{x,u}\times siz_y + f_{y,v}\times size_x \]

\(f_{k,u}\) 表示编号为 \(k\) 的树中所有点到 \(u\) 的距离和。

维护 \(f_{k,u}\)：考虑 \(u\) 是在 \(x_k\) 中还是 \(y_k\) 中即可。具体：

\[f_{k,p}= \begin{cases} siz_{y_k}\times (w_k + dis_{x_k,u_k,p})+f_{y_k,v_k} & p\in T_{x_k} \\ siz_{x_k}\times (w_k+dis_{y_k,v_k,p})+f_{x_k,u_k} & p\in T_{x_y} \end{cases} \]

\(dis_{k,i,j}\) 表示 \(T_k\) 中 \(i,j\) 两点间的距离。

维护 \(dis\)：一样分类讨论即可。详细见代码。

点数很多记忆化就行了。

正确性：\(f,dis\) 的转移只有关键点有关，关键点数量级为 \(O(m)\)，\(f\) 状态数 \(O(m^2)\)，\(dis\) 状态数 \(O(m^3)\)。总复杂度 \(O(m^3)\)。

实现优美，是这种做法的最优解。赛后一遍过样例，没调直接交就过了。

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define IL inline
#define vec vector
#define bg begin
#define eb emplace_back
#define emp emplace
#define fi first
#define se second
#define mkp make_pair
using ubt = long long;
using uubt = unsigned long long;
using dub = double;
using puu = pair<ubt, ubt>;

template <typename T = int>
IL T _R() {
  T s = 0, w = 1;
  char c = getchar();
  while (!isdigit(c)) w = c == '-' ? -1 : 1, c = getchar();
  while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
  return s * w;
}

constexpr int mod = 1e9 + 7;
constexpr int N = 300;
constexpr int maxN = N + 3;

int m;

ubt siz[maxN];
struct FUNCTION {
  IL ubt operator [] (int i) { return siz[i] % mod; }
} sz;

int x[maxN], y[maxN];
ubt u[maxN], v[maxN];
int w[maxN];
ubt J[maxN];

ubt ans[maxN];

#define hshtb gp_hash_table
struct Has { IL uubt operator () (const puu &A) const { return A.fi * 13331ull + A.se; } };
hshtb<puu, ubt, Has> dis[maxN];
hshtb<ubt, ubt> f[maxN];

ubt D(int k, ubt i, ubt j) {
  if (i == j) return 0;
  if (i > j) swap(i, j);
  if (dis[k][mkp(i, j)]) return dis[k][mkp(i, j)];
  if (j < J[k]) return D(x[k], i, j);
  if (i >= J[k]) return D(y[k], i - J[k], j - J[k]);
  ubt res = w[k] + D(x[k], i, u[k]) + D(y[k], j - J[k], v[k] - J[k]);
  return dis[k][mkp(i, j)] = res % mod;
}
ubt F(int k, ubt p) {
  if (!k && !p) return 0;
  if (f[k][p]) return f[k][p];
  ubt res = 0;
  if (p < J[k]) {
    res = sz[y[k]] * (w[k] + D(x[k], u[k], p)) % mod + F(y[k], v[k] - J[k]);
    res += F(x[k], p);
  } else {
    res = sz[x[k]] * (w[k] + D(y[k], v[k] - J[k], p - J[k])) % mod + F(x[k], u[k]);
    res += F(y[k], p - J[k]);
  }
  return f[k][p] = res % mod;
}

int main() {
  freopen("loquat.in", "r", stdin);
  freopen("loquat.out", "w", stdout);

  m = _R();
  siz[0] = 1;
  for (int i = 1; i <= m; i++) {
    auto x = _R(), y = _R();
    auto u = _R<ubt>(), v = _R<ubt>() + siz[x];
    auto w = _R();

    siz[i] = siz[x] + siz[y];
    J[i] = siz[x];

    ans[i] = w * sz[x] % mod * sz[y] % mod;
    ans[i] += F(x, u) * sz[y] % mod + F(y, v - J[i]) * sz[x] % mod;
    ans[i] += ans[x] + ans[y];
    ans[i] %= mod;

    printf("%lld\n", ans[i]);

    ::x[i] = x, ::y[i] = y, ::u[i] = u, ::v[i] = v, ::w[i] = w;
  }
}

上古遗迹

\(n,m\le 1e5,h_i\le 1e9\)

第 \(i\) 列有 \(h_i\) 个正方形。每次询问给出 \(l,r\) 问 \([l,r]\) 中的最大矩形面积。

\(l_i\) 表示最大的 \(j\) 使得 \(j<i \land h_j<h_i\)。等不等其实不怎么关心。 \(r_i\) 定义类似。

这部分可以单调栈，或者直接 dfs 配合 RMQ（ST 表）跑类似笛卡尔树的结构。

询问区间为 \([L,R]\)。分类讨论：

\(l_i\le L \land R \le r_i\)

  • 显：\(A=\min\{h_{L\dots R}\}\times (R-L+1)\)

\(L\le l_i \land r_i \le R\)

  • \(A=(r_i-l_i+1)\times h_i\)，扫描线维护即可。

\(L\le l_i \land R < r_i\)

  • \(A = (R-l_i+1)\times h_i=h_i R+(-l_i+1)h_i\)

\(l_i<L\land r_i\le R\)

  • \(A = (r_i-L+1)\times h_i=-h_iL+(r_i+1)h_i\)

容易发现后两个是一次函数的形式，扫描线+李超线段树即可。

赛时分类讨论完了，好久没写李超线段树，没想到。还以为是单峰的，上了个线段树上三分，然后就死了。

精细实现，目前最优解。一遍码完，没调。

复杂度 \(O(n\log^2n)\)，瓶颈在于李超线段树插入线段。

#include <bits/stdc++.h>

using namespace std;

#define IL inline
#define vec vector
#define bg begin
#define eb emplace_back
#define emp emplace
#define fi first
#define se second
#define mkp make_pair
using ubt = long long;
using uubt = unsigned long long;
using dub = double;
using pdd = pair<dub, dub>;

IL int _R() {
  int x;
  scanf("%d", &x);
  return x;
}

IL void ckx(auto &x, const auto &y) { (x < y) && (x = y); }

constexpr dub inf = 1e18;

constexpr int N = 2e5;
constexpr int maxN = N + 3;

int n, h[maxN];

struct ST {
  int st[20][maxN];
  IL int get(int i, int j) { return h[i] <= h[j] ? i : j; }
  IL void init() {
    for (int i = 1; i <= n; i++) st[0][i] = i;
    for (int t = 1; t <= 18; t++)
      for (int i = 1; i + (1 << t) - 1 <= n; i++)
        st[t][i] = get(st[t - 1][i], st[t - 1][i + (1 << (t - 1))]);
  }
  IL int ask(int l, int r) {
    int t = __lg(r - l + 1);
    return get(st[t][l], st[t][r - (1 << t) + 1]);
  }
} st;

struct BIT {
  ubt t[maxN];
  IL void ins(int x, ubt v) {
    for (; x <= n; x += x & -x) ckx(t[x], v);
  }
  IL ubt ask(int x) {
    ubt res = 0;
    for (; x > 0; x -= x & -x) ckx(res, t[x]);
    return res;
  }
} bita;

struct LC_Segtree {
#define ls (p << 1)
#define rs (p << 1 | 1)
  struct dat {
    int k;
    ubt b;
    dat() : b(-inf) {}
    dat(int k, ubt b) : k(k), b(b) {}
  } t[N * 4];
  IL ubt G(int x, const dat &A) { return (ubt)A.k * x + A.b; }
  void C(int L, int R, int k, ubt b, int p, int l, int r) {
    int mid = (l + r) >> 1;
    if (L <= l && r <= R) {
      if (G(mid, t[p]) < G(mid, {k, b})) swap(k, t[p].k), swap(b, t[p].b);
      if (G(l, t[p]) >= G(l, {k, b}) && G(r, t[p]) >= G(r, {k, b})) return;
      if (G(l, t[p]) < G(l, {k, b}))
        C(L, R, k, b, ls, l, mid);
      if (G(r, t[p]) < G(r, {k, b}))
        C(L, R, k, b, rs, mid + 1, r);
      return;
    }
    if (L <= mid)
      C(L, R, k, b, ls, l, mid);
    if (R > mid)
      C(L, R, k, b, rs, mid + 1, r);
  }
  void A(int K, int p, int l, int r, ubt &ans) {
    ckx(ans, G(K, t[p]));
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (K <= mid) A(K, ls, l, mid, ans);
    else A(K, rs, mid + 1, r, ans);
  }

  IL void clear() { fill(&t[0], &t[N * 4], dat{0, (ubt)-inf}); }
#undef ls
#undef rs
} T;

int tot;
struct node {
  int l, r, h;
  ubt s;
} a[maxN];

void D(int l, int r) {
  int g = st.ask(l, r);
  a[++tot] = {l, r, h[g], (ubt)(r - l + 1) * h[g]};
  if (l < g) D(l, g - 1);
  if (g < r) D(g + 1, r);
}

int m;
struct ques {
  int l, r, id;
} q[maxN];
ubt ans[maxN];

int main() {
  freopen("relics.in", "r", stdin);
  freopen("relics.out", "w", stdout);

  n = _R(), m = _R();
  for (int i = 1; i <= n; i++) h[i] = _R();
  st.init();
  D(1, n);
  // assert(tot == n);

  for (int i = 1; i <= m; i++)
    q[i].l = _R(), q[i].r = _R(), q[i].id = i;

  for (int i = 1; i <= m; i++) {
    ubt H = h[st.ask(q[i].l, q[i].r)];
    ans[i] = H * (q[i].r - q[i].l + 1);
  }

  auto cmp1 = [&](const auto &A, const auto &B) {
    return A.l > B.l;
  };
  sort(a + 1, a + n + 1, cmp1);
  sort(q + 1, q + m + 1, cmp1);
  for (int i = 1, now = 1; i <= m; i++) {
    auto &[l, r, id] = q[i];
    while (now <= n && a[now].l >= l) {
      bita.ins(a[now].r, a[now].s);
      now++;
    }
    ckx(ans[id], bita.ask(r));
  }

  auto cmp2 = [&](const auto &A, const auto &B) {
    return A.l > B.l;
  };
  sort(a + 1, a + n + 1, cmp2);
  sort(q + 1, q + m + 1, cmp2);
  for (int i = 1, now = 1; i <= m; i++) {
    auto &[l, r, id] = q[i];
    while (now <= n && a[now].l >= l) {
      int k = a[now].h;
      ubt b = (ubt)(-a[now].l + 1) * a[now].h;
      T.C(a[now].l, a[now].r, k, b, 1, 1, n);
      now++;
    }
    T.A(r, 1, 1, n, ans[id]);
  }

  T.clear();
  auto cmp3 = [&](const auto &A, const auto &B) {
    return A.r < B.r;
  };
  sort(a + 1, a + n + 1, cmp3);
  sort(q + 1, q + m + 1, cmp3);
  for (int i = 1, now = 1; i <= m; i++) {
    auto &[l, r, id] = q[i];
    while (now <= n && a[now].r <= r) {
      int k = -a[now].h;
      ubt b = (ubt)(a[now].r + 1) * a[now].h;
      T.C(a[now].l, a[now].r, k, b, 1, 1, n);
      now++;
    }
    T.A(l, 1, 1, n, ans[id]);
  }

  for (int i = 1; i <= m; i++)
    printf("%lld\n", ans[i]);
}

T3 吞天得手

求字典序前 \(k\) 小的子序列的哈希值。

非常简单 DFS 即可，赛时想到正解，复杂度分析错了，拿了 70 分，不过是赛时最高分。

如果我们搜索了前 \(i\) 小的子序列了，那往它后面加一个数比改它之中的一个数字典序小。依次搜索它后面第 \(j\) 小的数即可。注意字典序相同的子序列应该同时搜，不然你就错了。

赛时想法是枚举后面加什么，然后用 vector + 二分找位置。“枚举后面加什么数”复杂度就是错的了。

正解是主席树找后缀第 \(k\) 小。

复杂度 \(O(k\log n)\)，因为找到一个子序列 \(k\) 就减小。

正解 
#include <bits/stdc++.h>

using namespace std;

#define IL inline
#define vec vector
#define bg begin
#define eb emplace_back
#define emp emplace
using ubt = long long;
using dub = double;

template <typename T = int>
IL T _R() {
  T s = 0, w = 1;
  char c = getchar();
  while (!isdigit(c)) w = c == '-' ? -1 : 1, c = getchar();
  while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
  return s * w;
}

constexpr int mod = 998244353;
constexpr int N = 1e5;
constexpr int maxN = N + 3;

int n, k, B;
int a[maxN];

int pos[maxN], nt[maxN];

int top[maxN], tot;
struct dat {
  int l, r, v;
} t[N * 30];
IL void upd(int p) { t[p].v = t[p].l ? t[t[p].l].v : t[t[p].r].v; }
void C(int K, int &p, int w, int l, int r) {
  p = ++tot;
  t[p] = t[w];
  if (l == r) return t[p].v = K, void();
  int mid = (l + r) >> 1;
  if (a[K] <= mid)
    C(K, t[p].l, t[w].l, l, mid);
  else
    C(K, t[p].r, t[w].r, mid + 1, r);
  upd(p);
}
int Q(int L, int R, int p, int l, int r) {
  if (!p) return -1;
  if (L <= l && r <= R) return t[p].v;
  int mid = (l + r) >> 1, res = -1;
  if (L <= mid) res = Q(L, R, t[p].l, l, mid);
  if (R > mid && res == -1)
    res = Q(L, R, t[p].r, mid + 1, r);
  return res;
}

void dfs(const multiset<int> &S, ubt H) {
  int lst = 0;
  multiset<int> T;
  while (true) {
    int tmp = Q(lst + 1, N, top[(*S.bg()) + 1], 1, N);
    if (tmp == -1) return;
    lst = a[tmp];
    ubt A = (H * B + lst) % mod;

    T.clear();
    for (auto &i : S) {
      tmp = Q(lst, lst, top[i + 1], 1, N);
      if (tmp == -1) break;
      while (tmp != -1) {
        T.emp(tmp);
        printf("%lld\n", A);
        if (!--k) exit(0);
        tmp = nt[tmp];
      }
    }
    dfs(T, A);
  }
}

int main() {
  freopen("ttds.in", "r", stdin);
  freopen("ttds.out", "w", stdout);

  n = _R(), k = _R(), B = _R();
  for (int i = 1; i <= n; i++) a[i] = _R();

  memset(pos, -1, sizeof(pos));
  for (int i = n; i >= 1; i--) {
    nt[i] = exchange(pos[a[i]], i);
    C(i, top[i], top[i + 1], 1, N);
  }

  dfs({0}, 0);
}

感觉看完暴力也就理解这题了，所以把赛时暴力也放上了。

暴力 
#include <bits/stdc++.h>

using namespace std;

#define IL inline
#define vec vector
#define eb emplace_back
#define bg begin
#define lb lower_bound
#define ub upper_bound
using ubt = long long;

template <typename T = int>
IL T _R() {
	T s = 0, w = 1;
	char c = getchar();
	while (!isdigit(c)) w = c == '-' ? -1 : 1, c = getchar();
	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
	return s * w;
}

constexpr int mod = 998244353;
constexpr int N = 1e5;
constexpr int maxN = N + 3;

int n, k;
int B;

int a[maxN];

vec<int> Hs, pos[maxN];

void dfs(const vec<int> &s, ubt H) {
	for (int &v : Hs) {
		vec<int> tmp;
		for (const int &i : s) {
			auto gps = ub(pos[v].bg(), pos[v].end(), i);
			for (auto it = gps; *it <= n; it++)
				tmp.eb(*it);
		}
		if (tmp.empty()) continue;

		ubt A = (H * B + v) % mod;
		for (int &i : tmp) {
			printf("%lld\n", A);
			if (!--k) exit(1);
		}

		dfs(tmp, A);
	}
}

int main() {
	freopen("ttds.in", "r", stdin);
	freopen("ttds.out", "w", stdout);

	n = _R(), k = _R(), B = _R();
	for (int i = 2; i <= n; i++)
		pos[a[i] = _R()].eb(i), Hs.eb(a[i]);
	sort(Hs.bg(), Hs.end());
	Hs.resize(unique(Hs.bg(), Hs.end()) - Hs.bg());
	for (int &v : Hs) pos[v].eb(n + 2);

	dfs({1}, 0);
}

这场也太阳间了。有时间写题解是因为没过营。

标签：ubt,return,省选,2025,int,maxN,using,模拟,define
From： https://www.cnblogs.com/ccxswl/p/18670522

相关文章

  • 省选构造专题
    省选构造专题Thesamepermutation首先打个表，发现在\(1\len\le5\)之内的是否有合法方案的情况为√××√√大了打不出来了。考虑一下\(4,5\)连续有解，注意到一个偶数有解，则这个偶数\(+1\)也必定有解。考虑以下构造方法即对于某一个交换，可以在它前后各添加一个右端......
  • uniapp精仿支付宝UI界面，首页/理财/消息/生活/口碑/我的，还有模拟支付宝扫码支付/收付款
    uniapp精仿支付宝UI界面，首页/理财/消息/生活/口碑/我的，还有模拟支付宝扫码支付/收付款等功能，界面漂亮颜值高，视频商城小工具等，蚂蚁森林种树养鸡农场偷菜样样齐用于视频，商城，直播，聊天等sumer-alipay介绍uniapp精仿支付宝UI界面，首页/理财/消息/生活/口碑/我的，还有模拟支付宝......
  • 2025年手机电脑多平台同步的便签app推荐
    1、Win系统便笺Windows电脑上有系统自带的便笺工具，英文名叫stickynotes，可以在开始——应用列表中找到。借助outlook账号可在手机端同步便签数据。2、敬业签这是一款比较专业的便签软件，支持在安卓、苹果手机，Windows和Mac电脑、web和iPad端使用，并且内容会自动多端同步，同时在手......
  • 日常训练2025-1-14
    日常训练2025-1-14C.MEXCyclerating：1500https://codeforces.com/contest/2049/problem/C思路注意这是一道构造题。用xy将环分成两段，为保证xy符合条件，要先给xy的权值设置成01，然后根据两段链的长度的奇偶有两种填数方案。偶数直接01填，奇数要先填一个2然后再随机填。评......
  • 2025年入职/转行网络安全，该如何规划？网络安全职业规划
     网络安全是一个日益增长的行业，对于打算进入或转行进入该领域的人来说，制定一个清晰且系统的职业规划非常重要。2025年，网络安全领域将继续发展并面临新的挑战，包括不断变化的技术、法规要求以及日益复杂的威胁环境。以下是一个关于网络安全职业规划的详细指南，涵盖了从入门到高级......
  • 2025年入职/转行网络安全，该如何规划？网络安全职业规划
     网络安全是一个日益增长的行业，对于打算进入或转行进入该领域的人来说，制定一个清晰且系统的职业规划非常重要。2025年，网络安全领域将继续发展并面临新的挑战，包括不断变化的技术、法规要求以及日益复杂的威胁环境。以下是一个关于网络安全职业规划的详细指南，涵盖了从入门到高......
  • 2025年35+程序员，是否有机会转型 AI 大模型应用开发？
    对于35岁以上的程序员来说，转型到AI大模型应用开发领域不仅是可能的，而且在很多方面还具有独特的优势。随着人工智能技术的发展，特别是大规模预训练模型（如GPT系列、LLaMA系列等）的应用日益广泛，AI行业迎来了新的发展机遇。对于希望在这个新领域寻找职业发展的成熟程序员而言，这是......
  • 2025 算法方向毕业设计选题推荐汇总 python
    目录前言毕设选题选题迷茫选题的重要性更多选题指导最后 前言  ......
  • 2025 Homebrew 配置 brew install 国内镜像源指南，快速安装加速（01月13日更新）
    2025Homebrew配置brewinstall国内镜像源指南，快速安装加速（01月13日更新）大家好！......
  • xb21cn Office 2016 绿色版 2025更新版
    软件简介office精简版xb21cn最新版是一款微软Office办公软件的免激活office绿色精简版,xb21cn精简office绿色版提供office2010精简版和Office2016精简版,功能保留三大常用组件Word,Excel,PowerPoint,适合日常使用。版本特点MicrosoftOffice2016/2013/2010/2007/2003绿色精......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99