首页 > 其他分享 >[赛记] 多校A层冲刺NOIP2024模拟赛19

[赛记] 多校A层冲刺NOIP2024模拟赛19

时间:2024-11-08 16:10:25浏览次数:1  
标签:赛记 19 sum 多校 long int ans now mod

图书管理 85pts

2s 1e10助我85pts

考虑正解,仍然是算贡献

这个题有一个很通用的套路:将大于某数的数看成 $ 1 $,小于这个数的数看成 $ 0 $

那么我们枚举 $ a_i $,运用上面的套路将 $ i $ 左边的前缀和算出来并开个桶记录一下端点编号之和,然后在枚举 $ i $ 右边的同时找到现在的前缀和的相反数所对应的桶中的端点编号之和,乘一下即可;

注意前缀和为 $ 0 $ 的时候需要算上 $ i $;

时间复杂度:$ \Theta(n^2) $;

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n;
long long a[500005];
long long ans;
long long t[500005];
int main() {
	freopen("book.in", "r", stdin);
	freopen("book.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ans += 1ll * i * i * a[i];
	}
	for (int i = 1; i <= n; i++) {
		int sum = 0;
		for (int j = i - 1; j >= 1; j--) {
			if (a[j] < a[i]) sum--;
			else sum++;
			t[sum + n] += j;
			if (sum == 0) ans += 1ll * i * j * a[i];
		}
		sum = 0;
		for (int j = i + 1; j <= n; j++) {
			if (a[j] < a[i]) sum--;
			else sum++;
			if (sum == 0) ans += 1ll * i * j * a[i];
			ans += 1ll * t[-sum + n] * j * a[i];
		}
		sum = 0;
		for (int j = i - 1; j >= 1; j--) {
			if (a[j] < a[i]) sum--;
			else sum++;
			t[sum + n] -= j;
		}
	}
	cout << ans;
	return 0;
}

两棵树 30pts

直接暴搜30pts;

考虑正解,有个性质,最后剩余的连通块数为(点数-边数);

所以我们的答案为点乘点-2乘点乘边+边乘边;

然后直接粘题解了

image

时间复杂度:$ \Theta(n) $;

点击查看代码
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const long long mod = 998244353;
int n;
set<int> s[500005];
struct sss{
	int t, ne;
}e[500005];
int h[500005], cnt;
void add(int u, int v) {
	e[++cnt].t = v;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
long long ksm(long long a, long long b) {
	long long ans = 1;
	while(b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
long long ans;
int d[500005];
void dfs(int x, int fa) {
	for (int i = h[x]; i; i = e[i].ne) {
		int u = e[i].t;
		if (u == fa) continue;
		long long sum = n - 1 - d[x] - d[u];
		auto it = s[x].lower_bound(u);
		if (it != s[x].end() && *it == u) sum++;
		ans = (ans + sum * ksm(16, mod - 2) % mod) % mod;
		dfs(u, x);
	}
}
int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int x, y;
	for (int i = 1; i <= n - 1; i++) {
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	for (int i = 1; i <= n - 1; i++) {
		cin >> x >> y;
		s[x].insert(y);
		s[y].insert(x);
		d[x]++;
		d[y]++;
	}
	ans = (1ll * n * (n - 1) % mod * ksm(4, mod - 2) % mod - 1ll * (n - 1) * (n - 2) % mod * ksm(4, mod - 2) % mod + mod) % mod;
	dfs(1, 0);
	cout << ans;
	return 0;
}

函数 60pts

$ \Theta(n^2) $ 居然有60pts?

一个套路:对于一个区间 $ [l, r] $,如果它们两个相反,那么它们的中点 $ mid $ 所对应的值会和 $ l, r $ 中的一个相反,所以可以依据这个来找到一对相邻的相反元素

所以对于查询操作,我们先用Trie树找到异或出来的最大值和最小值,如果它们减 $ b $ 同号就无解,否则直接用套路缩小范围即可;

注意判断两个极值和每次判断 $ mid $ 值异或完减 $ b $ 是否为 $ 0 $;

时间复杂度:$ \Theta(n (\log n + \log V)) $;

点击查看代码
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
int n, q;
long long a[1000005];
namespace Trie{
	int son[30000005][2], tot;
	int id[30000005];
	void add(long long x, int i) {
		int now = 0;
		for (int j = 30; j >= 0; j--) {
			int y = ((x >> j) & 1);
			if (!son[now][y]) son[now][y] = ++tot;
			now = son[now][y];
		}
		id[now] = i;
	}
	int ask_ma(long long x) {
		int now = 0;
		for (int j = 30; j >= 0; j--) {
			int y = ((x >> j) & 1);
			if (son[now][y ^ 1]) now = son[now][y ^ 1];
			else now = son[now][y];
		}
		return id[now];
	}
	int ask_mi(long long x) {
		int now = 0;
		for (int j = 30; j >= 0; j--) {
			int y = ((x >> j) & 1);
			if (son[now][y]) now = son[now][y];
			else now = son[now][y ^ 1];
		}
		return id[now];
	}
}
using namespace Trie;
int main() {
	freopen("fun.in", "r", stdin);
	freopen("fun.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		add(a[i], i);
	}
	long long x, y;
	for (int i = 1; i <= q; i++) {
		cin >> x >> y;
		int ma = ask_ma(x);
		int mi = ask_mi(x);
		if ((a[ma] ^ x) - y == 0) {
			if (ma == 1) cout << ma << '\n';
			else cout << ma - 1 << '\n';
			continue;
		}
		if ((a[mi] ^ x) - y == 0) {
			if (mi == 1) cout << mi << '\n';
			else cout << mi - 1 << '\n';
			continue;
		}
		if (1ll * ((a[ma] ^ x) - y) * ((a[mi] ^ x) - y) > 0) {
			cout << -1 << '\n';
			continue;
		}
		int l = min(ma, mi);
		int r = max(ma, mi);
		bool vis = false;
		while(r - l > 1) {
			int mid = (l + r) >> 1;
			if ((a[mid] ^ x) - y == 0) {
				vis = true;
				if (mid == 1) cout << mid << '\n';
				else cout << mid - 1 << '\n';
				break;
			}
			if (1ll * ((a[l] ^ x) - y) * ((a[mid] ^ x) - y) < 0) r = mid;
			else l = mid;
		}
		if (!vis) cout << l << '\n';
	}
	return 0;
}

标签:赛记,19,sum,多校,long,int,ans,now,mod
From: https://www.cnblogs.com/PeppaEvenPig/p/18535233

相关文章

  • NOIP2024 前集训:多校A层冲刺NOIP2024模拟赛19
    前言这次不是之前学长吃完吐出来的shi,这次是新拉的热乎的烫嘴的shi。T1、2、3、4大样例全部错一遍,T1题面和时限再错一遍哈哈哈。T4假做法有60哈哈哈,大样例跑出来半个对的都没有能得60哈哈哈。accodersT1前半小时没数据做得快的全部都死哈哈(还好我第一份被卡常了后......
  • 20240919 短时赛
    20240919短时训练赛AShuffle赛时一直不知道怎么不重,唐了两个小时。注意到\(n\leq5000\),那么先\(O(n^2)\)枚举发生变化的第一个数和最后一个数,这两个位置不同时方案显然不同,于是不会算重。发生变化的这两个数强制改,剩下的乱放,组合数算一下就好。BRainCXORTree注......
  • CF1995 题解
    B有n种物品,每种物品价格为$a_i$,数量为$c_i$。要求选取物品的方案,满足价格极差不超过1,价格总和不超过m。最大化价格总和。$n\le10^5,m\le10^{18},a_i,c_i\le10^9,a_i\neqa_j$显然只有\(x\)和\(x,x+1\)两种选择情况。\(x\)直接贪心选即可,考虑\(x,x+1\)。发......
  • AbMole | MRTX1133(CAS号2621928-55-8;目录号M10593)
    MRTX1133是一种首创的(first-in-class),高度选择性的突变体KRASG12D的抑制剂,可逆地结合激活和失活的KRASG12D突变体并抑制其活性。MRTX1133对KRASG12D的特异性是野生型KRAS的1000倍以上。生物活性MRTX1133是一种有效的、高选择性的KRASG12D抑制剂。MRTX1133......
  • 【ALINX 教程分享】基于 Z19-P 开发板实现 WIFI 无线通信的功能
     本教程基于ALINX开发板Z19-P,实现WIFI 无线通信的功能,WIFI模块使用 USB WIFIrtl8188cu。使用的usbwifi设备购买链接:http://e.tb.cn/h.gy25HiTTj7n5eNg?tk=zvvU3oWX4X特别提醒,本教程Z19-P所使用的 Linux环境是按照教程“Xilinx开发环境安装教程”搭建的,请......
  • [赛记] NOIP2024加赛1 && 多校A层冲刺NOIP2024模拟赛18
    暴力错解大赛玩游戏82pts乱糊的错解,正确性和时间复杂度都不对,但是拿了82pts;对于正解,考虑从$k$将原序列分成两个部分,左边和右边,然后分别求一次前缀和(注意这里,可以省去很多分讨和常数),设前一个前缀和数组为$a$,后一个为$b$,那么问题就转化成有两个指针$i,j$,可以任......
  • Microsoft Office 2019 (office全家桶)for Mac/Windows电脑安装包
    MicrosoftOffice2019forMac(Office全家桶)是一款功能全面且强大的办公软件套件,专为Mac用户设计。Mac苹果电脑下载:Office2019(含激活秘钥)Windows电脑下载:Office2019(含批量许可)    以下是其主要特点和优势:一、界面设计采用了Mac系统的设......
  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19其实不太想写博客,但还是从今天开始坚持写吧。T1图书管理对于这种一边大一边小的问题,一般套路是大的设为$1$,小的设为$-1$,这道题也是,这样之后去扫一遍,两端的前缀和值一样即可。T2两棵树新学到的一个重要$trick$是:$$连通块的个数......
  • P9192 [USACO23OPEN] Pareidolia P 题解
    P9192[USACO23OPEN]PareidoliaP题解首先自然考虑不带修的情况。考虑问题的本质就是求序列中尽量短的bessie序列个数。对于尽量短的理解是对于bessiebessie序列,不考虑其由\(1,8\sim12\)构成的序列,只考虑\(1\sim6,7\sim12\)组成的序列。于是考虑dp:设\(dp_{i......
  • [63] (多校联训) A层冲刺NOIP2024模拟赛19
    lhx对\((\lnn)^{\lnn}\)求导求出一个形如\(\frac{1}{n\lnn\ln\lnn}\)的东西A.图书管理说一种很好玩的\(n^2\logn\)做法(因为动态中位数我只会这个)对顶堆:就是你开一个大根堆和一个小根堆,然后把它们怼在一起,钦定比中位数大的放小根堆,小的放大根堆,这样中间就是中位......