首页 > 其他分享 >GJOI 2024.4.20 总结

GJOI 2024.4.20 总结

时间:2024-04-23 13:44:21浏览次数:26  
标签:le 2024.4 int ed st ++ res 20 GJOI

Morning:

T1 小鸟

Statement:

在一个 \(n\) 的二维平面里,\(X\) 轴的正方向是向右的,\(Y\) 轴的正方向是向上的。

在坐标系第一象限里,左下角的点的坐标是 \((0,0)\) ,右上角的点的坐标是 \((n-1,n-1)\)。

所以本题我们考虑的整个平面总共有 \(n \times n\)个整点,每个整点都有一只小鸟,除了\((0,0)\)。

在整点 \((0,0)\) 处有一把静音的机关枪,你可以选择任意的角度开枪,每开一枪,相当于

从 \((0,0)\) 处发射出一条射线,凡是在该射线上的小鸟都会被打死。

你最多可以开 \(k\) 枪,请问最多可以打死多少只小鸟?

但是有 \(m\) 只小鸟事先收到风,在你没开枪之前就先飞走了。

\(1\le n \le 4000000, 1\le k\le16000000000000, 1\le m\le \min(n*n-1,2500)\)


Solution:

考场被卡常力(悲

先计算 \(m=0\) 的情况。

注意到一个点至多被一条直线经过,因此分别计算每一条直线的贡献,取最大贡献的 \(k\) 条即可。而且除了 \(y = x\) 都是唯一的,斜率小于 1 的和斜率大于 1 的直线是可以一一对应的,因此接下来只考虑斜率小于 1 的直线。

考虑一条经过 \((0, 0)\) 的直线 \(y = \frac{p}{q}x (p < q, \gcd(p, q) = 1)\) 会经过多少个点。显然是 \(\lfloor \frac{n - 1}{q} \rfloor\) 个。那么分母为 \(q\) 的直线有 \(\phi(q)\) 条,每条贡献 \(\lfloor \frac{n - 1}{q} \rfloor\)。这样就好做了。

那么现在加入 \(m\) 个去除的点。对于一个点 \((x, y)\),将其约分后得到 \((x_0, y_0)\)。这个点就在 \(y = \frac{y0}{x0} x\) 上了。那么就让这条直线的贡献减一就好了。

注意 \(x = 0\) 和 \(y = 0\) 这两条直线。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long 
using namespace std;

const int N = 4e6 + 10, M = 5e3 + 10; 

int n, m, k;
int phi[N], prime[N], tot;
struct point{
	int x, y;
}p[M], s[N];
bool isprime[N];
map<int, int> mp; 

void init(){
	for(int i = 1; i < N; i++) isprime[i] = true;
	phi[1] = 1; isprime[1] = false;
	for(int i = 2; i < N; i++){
		if(isprime[i]) phi[i] = i - 1, prime[++tot] = i;
		for(int j = 1; j <= tot && i * prime[j] < N; j++){
			isprime[i * prime[j]] = false;
			if(i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]];
			else{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;	
			}  
		}
	}
}

bool cmp(struct point p1, struct point p2){
	if(p1.x != p2.x) return p1.x > p2.x;
	return p1.y < p2.y; 
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T; init();
	while(T--){
		cin >> n >> k >> m; mp.clear();
		mp[n - 1] += 2; int tmp = 0;
		for(int i = 1; i < n; i++) mp[(n - 1) / i] += phi[i] * (i == 1 ? 1 : 2);
		for(int i = 1; i <= m; i++){
			cin >> p[i].x >> p[i].y;
			int g = __gcd(p[i].x, p[i].y);
			if((!p[i].x) || (!p[i].y)) g = 0;
			if(g) p[i].x /= g, p[i].y /= g;
		}
		sort(p + 1, p + m + 1, cmp); 
		int ths = 1;
//		for(int i = 1; i <= m; i++) cout << p[i].x << " " << p[i].y << "\n";
		for(int i = 2; i <= m; i++){ 
			if((p[i].x != p[i - 1].x || p[i].y != p[i - 1].y) && (p[i].x || p[i - 1].x) && (p[i].y || p[i - 1].y)){
				int g = max(p[i - 1].x, p[i - 1].y);
//				cout << p[i - 1].x << " " << p[i - 1].y << " " << g << " " << ths << "\n";  
				if(min(p[i - 1].x, p[i - 1].y) == 0) mp[n - 1]--, mp[n - 1 - ths]++;
				else mp[(n - 1) / g]--, mp[(n - 1) / g - ths]++; 
				ths = 0;
			}
			ths++;
		}
		if(ths){
			int g = max(p[m].x, p[m].y);
			if(min(p[m].x, p[m].y) == 0) mp[n - 1]--, mp[n - 1 - ths]++;
			else mp[(n - 1) / g]--, mp[(n - 1) / g - ths]++; 
		}
		int ans = 0;
		for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
			if(k <= 0) break;
			int val = (*it).first, cnt = (*it).second;
			if(cnt) s[++tmp] ={val, cnt};
		}
		sort(s + 1, s + tmp + 1, cmp);
		for(int i = 1; i <= tmp; i++){
			if(k <= 0) break;
			//cout << s[i].x << " " << s[i].y << "\n";
			ans += s[i].x * min(k, s[i].y); k -= s[i].y;
		}
		cout << ans << "\n";
	}
	
	return 0;
}
/*
1
9 1 7
8 2 
0 1 
7 6 
6 8 
3 3 
0 5 
3 4 
*/

T2 最长连续值域

Statement:

给出一个长度为 \(n\) 的排列 \(P(P1,P2,...Pn)\),以及 \(m\) 个询问。每次询问某个区间 \([l,r]\) 中,最长的值域连续段长度。

1\(\le n,m\le50000\).

Solution:

考虑用莫队求解。

我们令 \(st[x],ed[x]\) 分别是 \(x\) 最远向后可以延申到何处和向前最远延申至何处。

那么添加一个数 \(x\) 就令 \(st[ed[x - 1]] = ed[x + 1], ed[st[x + 1]] = st[x - 1]\),并更新答案 \(res = \max(res, ed[x + 1] - st[x - 1] + 1)\) 即可。

发现不好在删除的时候更新答案,于是使用回滚莫队。

#include<bits/stdc++.h>
#define int long long 
#define bk(x) ((x + unit - 1) / unit)
using namespace std;

const int N = 5e4 + 10;

int n, m, a[N]; 
int unit, st[N], ed[N];
struct query{
	int l, r, id;
}q[N];
int res, tmp, ans[N];

void clr(int x){st[x] = x + 1; ed[x] = x - 1;}

void add(int x){
	res = max(res, ed[x + 1] - st[x - 1] + 1);
	ed[st[x - 1]] = ed[x + 1];
	st[ed[x + 1]] = st[x - 1];
}

void del(int x){
	ed[st[x - 1]] = x - 1;
	st[ed[x + 1]] = x + 1;
}

bool cmp(struct query q1, struct query q2){
	if(bk(q1.l) != bk(q2.l)) return q1.l < q2.l;
	return q1.r < q2.r;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
	cin >> n >> m; unit = sqrt(m);
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for(int i = 1; i <= m; i++){
		if(bk(q[i].l) != bk(q[i - 1].l)){
			for(int j = 0; j <= n + 1; j++) clr(j);
			r = min(n, bk(q[i].l) * unit); l = min(n, bk(q[i].l) * unit) + 1;  res = 0;
		}
		if(bk(q[i].l) == bk(q[i].r)){
			res = 0;
			for(int j = q[i].l; j <= q[i].r; j++) add(a[j]);
			ans[q[i].id] = res;
			for(int j = q[i].r; j >= q[i].l; --j) del(a[j]);
			res = 0; continue;
		}
		while(r < q[i].r) add(a[++r]);
		int tmp = res, _l = l;
		while(_l > q[i].l) add(a[--_l]);
		ans[q[i].id] = res; res = tmp;
		while(_l < l) del(a[_l++]); 
	}
	for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
	
	return 0;
}

T3 P5306 [COCI2018-2019#5] Transport

一道淀粉质板子题就不讲了。

Afternoon

T1 [ABC246G] Game on Tree 3

首先二分答案 \(x\),将权值大于等于 \(x\) 的置为 \(1\),小于的置为 \(0\)。

于是这个时候我们判断 \(B\) 是否可以让 \(A\) 拿不到任何一个权值为 \(1\) 的点。

设 \(f_u\) 为以 \(u\) 为根的子树中 \(A\) 以最优策略操作,\(B\) 至少要在游戏开始前删除多少个 \(1\) 的点。

显然 \(f_u = \max(0, (\sum_{v \in subtree(u)}f_v) - 1) + a_i\)。其中 \(a_i = [w_i >= x]\)

判断 \(f_1\) 是否等于 \(0\) 即可。

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 2e5 + 10;
struct edge{
	int v, next;
}edges[N << 1];
int head[N], idx;

void add_edge(int u, int v){
	edges[++idx] = {v, head[u]};
	head[u] = idx;
}

int n, a[N];
int f[N];

void dfs(int u, int fa){
	int s = 0;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa) continue;
		dfs(v, u); s += f[v];
	}
	f[u] += max(0ll, s - 1);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 2; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++){
		int x, y; cin >> x >> y;
		add_edge(x, y); add_edge(y, x);
	}
	int l = 1, r = 1e9, ans = 0; 
	while(l <= r){
		int mid = (l + r >> 1);
		for(int i = 1; i <= n; i++) f[i] = (a[i] >= mid);
		dfs(1, 0);
		if(f[1] == 0) r = mid - 1;
		else ans = mid, l = mid + 1;
	}
	cout << ans;

	return 0;
}

T2 无向图染色

Statement:

给出 \(n\) 个结点 \(m\) 条边的无向图。有 \(k\) 种不同的颜色,编号 \(1\) 至 \(k\)。现在你要对这 \(n\) 个结点染色,每个结点只能染一种颜色。还有一个特殊要求:凡是有边相连的两个结点,它们的颜色编号的和不能等于\(z\)。问有多少种不同的染色方案,答案模 \(1000000007\)。

\(1 \le n \le 18,0 \le m \le \min(18,n\times(n-1)/2), 1 \le k \le 10^9, 2 \le z \le 2*10^9\)

Solution:

考虑容斥。

定义不可行边为一条连接 \((u, v)\) 的边,而且 \(color_u + color_v = z\),对于一个不可行边集合 \(S\),我们建出这张图。

对于一个孤立点,它染色的可能性就有 \(k\) 种。

接下来我们考虑点数 $ > 1$ 的连通块,有两种情况:

  • 该连通块有奇环:如果 \(z\) 为偶数,就只能把所有点染成 \(\frac{z}{2}\),否则没有染色的可能。

  • 该连通块没有奇环:注意到如果我们确定了一个点的颜色,整个连通块的颜色就可以确定了。那么一个点的可能性就是:

  1. \(k \times 2 < z:0\)
  2. \(k >= z - 1: z - 1\).
  3. \(otherwise: 2 \times k - (z - 1)\)
#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 18 + 3, mod = 1e9 + 7;

int n, m, k, z;
int from[N], to[N], nodecnt;

int qpow(int x, int y){
	int ret = 1;
	while(y){
		if(y & 1) ret = (ret * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return ret;
}

struct edge{
	int v, next;
}edges[N << 1];
int head[N], idx;

void add_edge(int u, int v){
	edges[++idx] = {v, head[u]};
	head[u] = idx;
}

int col[N];

int popcnt(int x){if(!x) return 0; return popcnt(x >> 1) + (x & 1);} 
void build(int S){//建图
	idx = 0; nodecnt = 0;
	for(int i = 1; i <= n; i++) head[i] = col[i] = 0;
	for(int i = 0; i < m; i++) if((1 << i) & S) add_edge(from[i + 1], to[i + 1]), add_edge(to[i + 1], from[i + 1]);  
	for(int i = 1; i <= n; i++) if(head[i]) nodecnt++;//自由点的个数
}
bool checker(int u){//检查是否有奇环
	bool flag = true;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(!col[v]) col[v] = -col[u], flag &= checker(v); //
		else if(col[v] + col[u] != 0) flag = false; //
	}
	return flag;
}
int lsy(){ // 
	if(k >= z - 1) return z - 1;
	if(2 * k < z) return 0;
	return 2 * k - z + 1;
}
int solver(){//算这个图染色的方案数
	int ret = 1;
	for(int i = 1; i <= n; i++){
		if((!col[i]) && head[i]){
			col[i] = 1;//将第 1 个节点染成 1
			if(checker(i) && (z <= 2 * k)) ret = (ret * lsy()) % mod;
			else if((z & 1) || z > 2 * k) ret = 0;
		}
	}
	return ret;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> z;
	for(int i = 1; i <= m; i++) cin >> from[i] >> to[i];
	int ans = 0;
	for(int S = 0; S < (1 << m); S++){
		build(S);
		ans = (ans + ((qpow(k, n - nodecnt) * ((popcnt(S) & 1) ? -1 : 1) * solver()) % mod + mod) % mod) % mod;
		// cout << S << " " << nodecnt << " " << ans << "\n";
	}
	cout << ans;

	return 0;
}

标签:le,2024.4,int,ed,st,++,res,20,GJOI
From: https://www.cnblogs.com/little-corn/p/18152698

相关文章

  • FasterViT:英伟达提出分层注意力,构造高吞吐CNN-ViT混合网络 | ICLR 2024
    论文设计了新的CNN-ViT混合神经网络FasterViT,重点关注计算机视觉应用的图像吞吐能力。FasterViT结合CNN的局部特征学习的特性和ViT的全局建模特性,引入分层注意力(HAT)方法在降低计算成本的同时增加窗口间的交互。在包括分类、对象检测和分割各种CV任务上,FasterViT在精度与图像吞吐......
  • 洛谷题单指南-动态规划2-P1020 [NOIP1999 提高组] 导弹拦截
    原题链接:https://www.luogu.com.cn/problem/P1020题意解读:拦截系统发射导弹的高度依次不增,计算能拦截的最大导弹数以及需要几套拦截系统。解题思路:问题1:最多能拦截多少导弹?由于发射导弹高度不增,所以求一个最长不增子序列即可得到最大拦截数。方法一、O(n^2)做法:动态规划。采......
  • 2024天梯赛【搜索】
    吉利矩阵题目大意dfs思路搜索策略:每一行每一行的搜索,(1,1)->(1,2)->...->(1,n)->(2,1)->...(n,n)剪枝策略:记录每一行与每一列的总和,sumRow,sumCol,接下来要填的数要小于等于l-sumRow[x]与l-sumCol[y],如果当前行填完了,要判断当前行sumRow[x]是否等于l。题目代码#inc......
  • mipi dsi4线720P国产gowin lattice crosslink配套屏Fpga dsi
     1.产品概述    显示屏LCDMIPIDSI4lane,支持分辨率720*1280,60HZ彩色显示。用于对接国产GOWIN的NR-9C的开发板和LATTICE的CROSSLINK开发板,显示MIPIDSI 功能。      MIPIDSI是4-LANE,MIPI速率在480MHZ。支持LP模式初始化和HS模式显示数据发送。    ......
  • 洛谷 P8818 [CSP-S 2022] 策略游戏
    https://www.luogu.com.cn/problem/P8818什么玩意儿。。这种策略题不就是你来我往的,你如果选那个我就选这个,到了最后俩人都做不了决策,一直在博弈吗放个示例跑不过去的代码真不想调,这种题就是恶心啊,你说说怎么调呢针对一方的选择,另一方总能选出更优的策略来。然后这一方针对另......
  • Metasploit Pro 4.22.3-2024041701 (Linux, Windows) - 专业渗透测试框架
    MetasploitPro4.22.3-2024041701(Linux,Windows)-专业渗透测试框架Rapid7Penetrationtesting,ReleaseApr17,2024请访问原文链接:MetasploitPro4.22.3-2024041701(Linux,Windows)-专业渗透测试框架,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org世......
  • 【2024-04-22】深夜食堂
    20:00对于绝大多数的人,人生本就是一堆责任而已。参透此谛,爱情是缘,友情是缘,亲情尤其是缘,不论怎样,皆当润砾成珠。                                                 ——梁......
  • 2024团体程序设计天梯赛——赛后总结
    2022年135分2023年164分感觉还是挺失望的,本来很稳的国三的就这样丢了,不过也是菜是原罪。一是对于读题的反思,L1-3,L1-4读题不认真导致直接白白被卡20分钟左右,还搞心态,后面的题目基本都没有一遍仔细地看完过。以后的题目尽量先把全部看一遍,然后再仔细看一遍题目部分(不看背景了),不......
  • 【专题】2023年中国社会办口腔医疗企业报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34300原文出处:拓端数据部落公众号口腔健康是整体健康的重要基石,当前,无论是哪个年龄段的人群,或多或少都会受到口腔问题的困扰。随着国民口腔健康意识的不断提高,消费者对口腔医疗服务的需求日益多元化,口腔医疗行业也迎来了快速发展阶段。阅读原文,获......
  • 关于Windows 10 LTSC 2019无法安装Edge的解决方案
    最近新换了Windows10LTSC2019系统,使用体验干净且流畅,但是在更新Edge时遇到了问题:系统内装的是9x版本的Edge浏览器,并且提示更新错误,有systemlevel方面的问题,查询多方后,最终在MicrosoftCommunity中找到了解决方案,在任意地方创建一个名为edge.reg的注册表文件,具体名称随意,然后用......