首页 > 其他分享 >4.17训练赛

4.17训练赛

时间：2024-04-19 22:56:11浏览次数：27  
标签：rt return 4.17 int top mid 训练赛 ti

感觉就是，题并没有多难，但考场上就是想不出来。

链接： https://vjudge.net/contest/622884#problem/

B 

天杀的B题，计算重心，真没想到

要使得重心尽可能的低，在竖立的时候是不需要考虑的，主要需要考虑水平方向上的，也就是水瓶在空中横置的时候，这时候就需要用到力矩了。

 

C

就是在一个圆里面尽可能的填正方形，其中要求圆心一定是四个相邻的正方形的公共顶点，直接二分就行了。

一开始直接思维误区，以为正方形个数是可以直接用 i^2，和 i^2 + 4i 求得的，直接看了5个小时，寄

实则计算出1/4圆能放多少个正方形就够了，时间复杂度是 nlogn的

 

D 一个最短路，比较重要的就是建图了，没啥必要，ez

 

E 

比较简单，首先可以想到，对于一个有 n 个顶点，所对应的期望范围是多少

最小：菊花图 n - 1 / n = 2(n-1) / 2n

最大： 链状图，1号顶点在最边边上 n * (n - 1) / 2n

那么对于给定的分数，先化简成最简分数的形式，然后分子分母一直乘 2， 找到一个满足条件的 a，b就好了

然后就是如何建图，一号点肯定是固定的，接下来就是考虑新的点应该接到哪里。

考虑二分，二分这个点到一号点的路径长度mid，得到mid后，考虑剩下的点所能提供的长度最小和最大分别是多少（全都接在一号点上和连成链状，接到离一号点最远的那个点之后），只要使得还需要的路径长度之和在最大值和最小值之间就好了，否则就增大mid或者减小mid，并实时更新离一号点最远的点的距离，l的话就一直是1

折叠标题 

#include<bits/stdc++.h>

const int MAXN = 1e6 + 10;
using namespace std;
typedef long long LL;

int a, b;
int cnt[MAXN];
int nee;
int n, m;
map<int, int> mp;

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd(y, x % y);
}

int check(int x, int i, int maxn){
	int havminn = x + n - i;
	int havmaxn = x + (maxn + 1 + maxn + n - i) * (n - i) / 2;
	if(havmaxn < nee) return 0;
	if(havminn <= nee && havmaxn >= nee) return 1;
	if(havminn > nee) return 2;
}
int main()
{
	string s;
	cin >> s;
	int poi = 0;
	while(s[poi] != '/') a = a * 10 + s[poi] - '0', poi++;
	poi++;
	for(int i = poi;i < s.size();i++) b = b * 10 + s[i] - '0';
//	cin >> a >> b;
	a /= gcd(a, b);
	b /= gcd(a, b);
	if(a < b - 1) {
		cout << "impossible\n";
		return 0;
	}
	// wa 的原因，a 有可能是奇数，所以也要判断
	if(b % 2 || a % 2) b *= 2, a *= 2;
	while(b / 2 <= 1e6 && a > (b / 2) * (b / 2 - 1)){
		a *= 2;
		b *= 2;
	}
	if(b / 2 > 1e6) {
		cout << "impossible\n";
		return 0;
	}
	n = b / 2, m = n - 1;
	nee = a / 2;
	int l = 1, r = 0;
//	int res = 0;
	for(int i = 2;i <= n;i++)
	{
		int L = l, R = r + 1;
		while(L < R)
		{
			int mid = L + R >> 1;
			int res = check(mid, i, r);
			if(res == 1) {
				L = R = mid;
				break;
			}
			else if(res == 0){
				L = mid + 1;
			}
			else R = mid;
		}
		if(L == r + 1) {
			r += 1;
		}
		nee -= L;
		cnt[i] = L;
	}
//	cnt[n] = nee;
	sort(cnt + 1, cnt + n + 1);
	cout << n << " " << m << '\n';
	mp[0] = 1;
	for(int i = 2;i <= n;i++)
	{
		cout << i << " " << mp[cnt[i]-1] << "\n";
		if(!mp[cnt[i]]) mp[cnt[i]] = i;
	}
	return 0;
}

 

I 不多说，签到题

 

J 排序+线段树

首先对给定的区间进行排序，开始时间最小，相同的按结束时间最晚排序（感觉这个排序方式很常见，在与区间处理，要求重叠什么的相关的问题上）

这样就可以保证在从左往右遍历的时候，当前的这个区间开始已经是晚于前面的，那么只需要考虑他们的结束时间就可以了。

两种做法：

假设所有区间中，最晚结束在时间 cnt

1. 对于当前区间 [L, R]，找到 [R, cnt]区间上的最大值，这就是答案

  然后再将 [R, cnt] 这个区间更新为最大值+1,

2. 对于当前区间 [L, R]，找到 [L, R]区间上的最小值，这就是答案

  然后再将[L, R]区间上的每一个数 与 最大值 + 1 作 max 取成最大值操作。

区间修改查询，线段树，且需要懒标记

折叠标题 
 #include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1

const int MAXN = 4e5 + 10;
using namespace std;

int n;
struct nodee
{
	int id;
	int a, b;
}k[MAXN], k2[MAXN];
int ti[MAXN], top;

struct node
{
	int l, r;
	int val;
	int flag;
}t[MAXN<<3];
int ans[MAXN];

void pushdown(int rt)
{
	if(t[rt].flag){
		t[rt].val = max(t[rt].val, t[rt].flag);
		if(t[rt].l != t[rt].r){
			// 不能和自己原本的 val 比较，因为你不确定是整个区间最大值都是 这个 val 还是
			t[ls].flag = max(t[ls].flag, t[rt].flag);
			t[rs].flag = max(t[rs].flag, t[rt].flag);
			// 不能确定这里原本的最大值和下放的flag谁大
			t[ls].val = max(t[ls].val, t[ls].flag);
			t[rs].val = max(t[rs].val, t[rs].flag);
		}
		t[rt].flag = 0;
	}
	return ;
}

void build(int rt, int l, int r)
{
	if(l == r)
	{
		t[rt].l = t[rt].r = l;
		t[rt].val = 0;
		return ;	
	}	
	int mid = l + r >> 1;
	t[rt].l = l;
	t[rt].r = r;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	return ;
}

int query(int rt, int L, int R)
{
	if(t[rt].l > R || t[rt].r < L) return 0;
	// return 前下放 必须
	pushdown(rt);
	if(t[rt].l >= L && t[rt].r <= R) return t[rt].val;
	int res = 0;
	int mid = t[rt].l + t[rt].r >> 1;
	if(L <= mid) res = max(res, query(ls, L, R));
	if(R >= mid + 1) res = max(res, query(rs, L, R));
	return res;
}

void update(int rt, int L, int R, int val)
{
	if(t[rt].l > R || t[rt].r < L) return;
	
	if(t[rt].l >= L && t[rt].r <= R){
		t[rt].flag = max(t[rt].flag, val);
		t[rt].val = max(t[rt].val, t[rt].flag);	
		return ;
	}	
	// pushdown 在这里，和上面都可
	pushdown(rt);
	update(ls, L, R, val);
	update(rs, L, R, val);
	// 很重要
	t[rt].val = max(t[ls].val, t[rs].val);
	return ;
}

void print()
{
	for(int i = 1;i <= 20;i++) 
	{
		cout << t[i].l << " " << t[i].r << " " << t[i].val << '\n';
	}
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> k[i].a >> k[i].b;
		k[i].b += k[i].a - 1;
		k[i].id = i;
		ti[++top] = k[i].a;
		ti[++top] = k[i].b;
	}
	
	sort(ti + 1, ti + 1 + top, [](const int &a, const int &b){
		return a < b;
	});
	top = unique(ti + 1, ti + top + 1) - ti - 1;
	
	sort(k + 1, k + n + 1, [](const nodee &x, const nodee &y){
		if(x.a == y.a) return x.b > y.b;
		return x.a < y.a;
	});
	
	for(int i = 1;i <= n;i++){
		k2[i].id = k[i].id;
		k2[i].a = lower_bound(ti + 1, ti + top + 1, k[i].a) - ti;
		k2[i].b = lower_bound(ti + 1, ti + top + 1, k[i].b) - ti;
	}
	build(1, 1, top+1);
	for(int i = 1;i <= n;i++)
	{
		int res = query(1, k2[i].b, top + 1);
		ans[k2[i].id] = res;
		update(1, k2[i].a, k2[i].b, res + 1);
	}
	for(int i = 1;i <= n;i++) cout << ans[i] << " \n"[i==n];
	return 0;
}
折叠标题 
 #include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1

const int MAXN = 4e5 + 10;
using namespace std;

int n;
struct nodee
{
	int id;
	int a, b;
}k[MAXN], k2[MAXN];
int ti[MAXN], top;

struct node
{
	int l, r;
	int val;
	int flag;
}t[MAXN<<3];
int ans[MAXN];

void pushdown(int rt)
{
	if(t[rt].flag){
		t[rt].val = max(t[rt].flag, t[rt].val);
		if(t[rt].l != t[rt].r){
			// 不能和自己原本的 val 比较，因为你不确定是整个区间最大值都是 这个 val 还是
			t[ls].flag = max(t[ls].flag, t[rt].flag);
			t[rs].flag = max(t[rs].flag, t[rt].flag);
			// 不能确定这里原本的最大值和下放的flag谁大
			t[ls].val = max(t[ls].val, t[ls].flag);
			t[rs].val = max(t[rs].val, t[rs].flag);
		}
		t[rt].flag = 0;
	}
	return ;
}

void build(int rt, int l, int r)
{
	if(l == r)
	{
		t[rt].l = t[rt].r = l;
		t[rt].val = 0;
		return ;	
	}	
	int mid = l + r >> 1;
	t[rt].l = l;
	t[rt].r = r;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	return ;
}

int query(int rt, int L, int R)
{
	if(t[rt].l > R || t[rt].r < L) return 0;
	// return 前下放 必须
	pushdown(rt);
	if(t[rt].l >= L && t[rt].r <= R) return t[rt].val;
	int res = MAXN;
	int mid = t[rt].l + t[rt].r >> 1;
	if(L <= mid) res = min(res, query(ls, L, R));
	if(R >= mid + 1) res = min(res, query(rs, L, R));
	return res;
}

void update(int rt, int L, int R, int val)
{
	if(t[rt].l > R || t[rt].r < L) return;
	
	if(t[rt].l >= L && t[rt].r <= R){
		t[rt].flag = max(t[rt].flag, val);
		t[rt].val = max(t[rt].val, t[rt].flag);
		return ;
	}	
	// pushdown 在这里，和上面都可
	pushdown(rt);
	update(ls, L, R, val);
	update(rs, L, R, val);
	// 很重要
	t[rt].val = min(t[ls].val, t[rs].val);
	return ;
}

void print()
{
	for(int i = 1;i <= 20;i++) 
	{
		cout << t[i].l << " " << t[i].r << " " << t[i].val << '\n';
	}
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> k[i].a >> k[i].b;
		k[i].b += k[i].a - 1;
		k[i].id = i;
		ti[++top] = k[i].a;
		ti[++top] = k[i].b;
	}
	
	sort(ti + 1, ti + 1 + top, [](const int &a, const int &b){
		return a < b;
	});
	top = unique(ti + 1, ti + top + 1) - ti - 1;
	
	sort(k + 1, k + n + 1, [](const nodee &x, const nodee &y){
		if(x.a == y.a) return x.b > y.b;
		return x.a < y.a;
	});
	
	for(int i = 1;i <= n;i++){
		k2[i].id = k[i].id;
		k2[i].a = lower_bound(ti + 1, ti + top + 1, k[i].a) - ti;
		k2[i].b = lower_bound(ti + 1, ti + top + 1, k[i].b) - ti;
	}
	build(1, 1, top+1);
	for(int i = 1;i <= n;i++)
	{
		// 最小值
		int res = query(1, k2[i].a, k2[i].b);
		ans[k2[i].id] = res;
		update(1, k2[i].a, k2[i].b, res + 1);
//		print();
	}
	for(int i = 1;i <= n;i++) cout << ans[i] << " \n"[i==n];
	return 0;
}

 

标签：rt,return,4.17,int,top,mid,训练赛,ti
From： https://www.cnblogs.com/xxx3/p/18146943

相关文章

  • 4.17毕设
    今天做了一个分页，app的分页和web端不太一样，点击下一页按钮并不会触发一个方法，而是通过内置的一个监测，确定用户是点击前一页还是后一页，以及变化之后的页码，再将全部查询到的内容按照页面要求封装。还做了一个上传图片并识别的功能，明天把之前的饮食情况查询出来，   ......
  • 4.17
    趣味典故通过不同的短篇传统典故，让儿童学习更多的常用字词及歇后语等。充分理解文字背后的故事和含义。在学习过程中塑造符合社会主流要求的观念。将不同典故设计为不同关卡，根据字数及词语的难易程度分级。在关卡中，在故事的部分句子内制作填空题，让用户根据理解选择正确的字或词......
  • 2024.4.17python复习
    非0整数（正数、负数）进行bool转换，均为true。0的强制类型转换为bool为falsebool强制类型，如果为float转bool，如果a!=0.0,则为true，否则为true;如果为str转bool，若str=''，str中为空，则bool（str）的内容为false，否则为true，空格也一样；只要列表中有数据那么强制类型转换为bool的时候就返回True；......
  • 4.17 经验帖
    1.打印输出排版问题（1）stew：用于设置输出字符宽度比如：stew（5）点击查看代码cout<<j<<'*'<<i<<stew(4)<<j*i;![](https://img2024.cnblogs.com/blog/3414398/202404/3414398-20240417081956884-1844090512.png)意思是输出的i后面的内容一共占4个字符（2）right，left函数用于在......
  • 2024.4.16 训练1（VP） CodeForces自创MashUP训练赛（rating1200-1400）
    mashup链接：https://codeforces.com/gym/518192A.FriendlyArrays经典位运算，这里有个小trick，就是涉及到逻辑运算符的都把每一位拆开来看看影响根据或运算的性质，对于a数列每个数的某一位来说，如果b数组中某个数在这一位上有1，那么在a数组的每个数的这一位都能保证变为1。而在后面......
  • TOPCODER时期训练赛小总结
    20240407模拟赛T1TurnOnLamps直接树上dp维护子树内是否有路径在根节点处停止的最小操作数\(O(n)\)维护即可，数据范围纯sbT2XorCards线性基或高斯消元板子，高斯消元比较好想。可以枚举大于等于时前若干位是相同的，然后直接搞出限制消元即可。时间复杂度合理。线性基则非常......
  • ISC2016训练赛-phrackCTF-Smali
    ISC2016训练赛-phrackCTFSmali:类型：Reverse**题目描述：都说学好Smali是学习Android逆向的基础，现在刚好有一个smali文件，大家一起分析一下吧~~**解题方法：将题目附件下载下来之后发现是一个.smali文件，将它放进jadx-gui里面进行一下反编译得到：packagenet.bluelotus.tomorrow.eas......
  • ISC2016训练赛-phrackCTF-FindKey
    ISC2016训练赛——phrackCTFReverse-FindKey:题目描述：FLAG就是你输入的key解题方法：将题目附件下载下来是一个无后缀名的文件，把他放进exeinfope.exe里查看一下它的信息这里我们看到它不是一个EXE文件，但是下面有提示说是用python，然后我们将他的后缀名改成.py文件，用python打开是......
  • SUM-ACM——VJ天梯训练赛
    这次比赛我暴露了很多问题，一些模拟还有贪心思路错误。补题如下：E-E题解：一道模拟题，我的问题在于不知道怎么替换下一个，就从0开始遍历数组然后数组的值--，如果为零就continue下一个，这个问题在于无法遍历完所有的数，会少算。其实只需要把接完水的按顺序到下一个就可以了，这样还有一个......
  • 牛客寒假训练赛第二场
    基本情况前面过的很顺，F吃满罚时，T4次WA4次最后乱搞过的，K有一点思路，但是码力跟不上，其他没做的题题目基本没思路。EFhttps://ac.nowcoder.com/acm/contest/67742/Ehttps://ac.nowcoder.com/acm/contest/67742/F两题虽然都是过了，但一个是提交前改了很久，一个是提交改了很久。E......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99