首页 > 其他分享 >2022牛客暑期多校集训解题报告 第一场

2022牛客暑期多校集训解题报告 第一场

时间：2022-08-26 21:00:50浏览次数：104  
标签：typedef int ios 多校 long 牛客 2022 include define

A. Villages: Landlines

题意 ：给定n - 1个建筑和一个发电站，分布在一个一维的数轴上，这n - 1个建筑都有各自的电力接受范围，不连通的建筑可以通过电相连，问使每个建筑都通上电所需的最小电线长度

思路 ：将每个建筑看成区间，然后问题就转化为区间贪心问题，将断开的区间补上即可

ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 300010,M = 200010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
 
int n,m,k,t;

int main()
{
	ios;
	cin >> n;
	vector<PII> a(n + 1);
	for(int i = 1;i <= n ;i ++)
	{
		int l,r;
		cin >> l >> r;
		a[i] = {l - r,l + r};
	}

	sort(all1(a));
	int r = a[1].y;
	int ans = 0;
	for(int i = 2;i <= n;i ++)
	{
		if(a[i].x > r) ans += a[i].x - r;
		r = max(r,a[i].y);
	}

	cout << ans << endl;
	return 0;
}

C. Grab the Seat!

题意 ：教室中有n * m 个座位，定义一个座位未被阻挡位为任意一个位置不会阻挡其看黑板的视线，教室中有k个人，每次改变一个人的位置，问有多少个座位为被阻挡

分析 ： 如图对于一个人所阻挡得范围为黑板两端与其连线后面的三角形区域，那么我们只需要求出每个人的范围然后取并，再求个补集即可，可以发现每一行的最靠前有人的位置会遮挡住该行其他人，所以我们按行枚举这个位置即可，注意正反两次枚举
image

ac 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
 
int n,m,k,t;
int a[N],b[N];

void solve()
{
	vector<int> p(m),ans(m + 1);
	for(int i = 0;i < m;i ++) p[i] = n + 1;
	for(int i = 1;i <= k;i ++) p[b[i] - 1] = min(p[b[i] - 1], a[i]);
	for(int i = 0;i < m;i ++) ans[i] = p[i] - 1;

	int x = n + 1,y = 0;
	for(int i = 0;i < m;i ++)
	{
		int x1 = p[i],y1 = i;
		if(1LL* y1 * x >= 1LL * y * x1) x = x1,y = y1;
		int t = n;
		if(y) t = (1LL* y1 * x - 1) / y;
		ans[i] = min(t,ans[i]);
	} 

	reverse(all(p));
	x = n + 1,y = 0;
	for(int i = 0;i < m;i ++)
	{
		int x1 = p[i],y1 = i;
		if(1LL* y1 * x >= 1LL * y * x1) x = x1,y = y1;
		int t = n;
		if(y) t = (1LL* y1 * x - 1) / y;
		ans[m - 1 - i] = min(t,ans[m - 1 - i]);
	} 

	LL res = 0;
	for(int i = 0;i < m;i ++) res += ans[i];
	cout << res << endl;
}


int main()
{
	ios;
	cin >> n >> m >> k >> t;
	for(int i = 1;i <= k;i ++) cin >> a[i] >> b[i];

	while(t --)
	{
		int x;
		cin >> x >> a[x] >> b[x];
		solve();
	}
	return 0;
}

D. Mocha and Railgun

题意 ：有一个圆 给定一个定长的线段，令这个线段绕其中点旋转，问该线段在圆周上的最长投影长度
思路：如图可以发现不管这条线段如何旋转，他都可以投影至某条直径上在进行圆周上投影，因此该问题可转化为一条定长线段在直径上平移，当线段平移至离圆心最远时投影长度最长
image
ac 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 200010,INF = 0x3f3f3f3f,mod = 998244353;
const double INFF = 0x7f7f7f7f7f7f7f7f;
 
int n,m,k,t;
LL f[20][100];
int main()
{
	ios;
	cin >> t;
	while(t --)
	{
		LL a,b,r,d;
		cin >> r >> a >> b >> d;
		double x = sqrt( a * a + b * b),y = 0;
		double x1 = x + d,x2 = x - d,dx = 2 * d;
		double y1 = sqrt(r * r - x1 * x1),y2 = sqrt(r * r - x2 * x2),dy = fabs(y2 - y1);
		double len = sqrt(dx * dx + dy * dy) / 2;
		double sina = len / r;
		double A = asin(sina) * 2;
		cout << fixed << setprecision(12) << A  * r << endl;
	}
	return 0;
}

G. Lexicographical Maximum

题意 ：给定一个数字 n 问1~n中字典序最大的数字是多少
分析：贪心
ac 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 200010,INF = 0x3f3f3f3f,mod = 998244353;
const double INFF = 0x7f7f7f7f7f7f7f7f;
 
int n,m,k,t;
LL f[20][100];
int main()
{
	ios;
	string s;
	cin >> s;
	bool success = true;
	for(int i = 0;i < s.size() - 1;i ++) if(s[i] != '9') success = false;

	if(success) cout << s <<endl;
	else 
	{
		n = s.size() - 1;
		while(n --) cout << 9;
	}
	return 0;
}

I. Chiitoitsu

题意：日本麻将，凑对子，问凑成七对对子的期望轮数
分析：定义 \(f(i,j)\) 为目前手中有i对对子，还可摸j张牌的期望轮数,最优策略为每次摸一张牌，如果能凑成一个对子就打出去一个单，不能就打回去
对于可以凑成的情况，\(f(i,j) = f(i + 1,j - 1) * has / j\)
对于不难凑成的情况，\(f(i,j) = f(i,j - 1) * hasn / j\)
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
 
int n,m,k,t;
int a[N],b[N];

int qmi(int a,int k)
{
	int res = 1;
	while(k)
	{
		if(k & 1) res = 1LL * res * a % mod;
		k >>= 1;
		a = 1LL * a * a % mod;
	}
	return res;
}
LL f[20][150];
void dp()
{
	for(int i = 6;~ i;i --)
	{
		int has = (13 - i * 2) * 3;
		for(int j = has;j <= 123;j ++)
		{
			int inv = qmi(j,mod - 2);
			int hasn = j - has;
			f[i][j] = (f[i + 1][j - 1] % mod * has % mod * inv % mod + f[i][j - 1] % mod * hasn % mod * inv % mod + 1) % mod;
		}
	}
}

int main()
{
	ios;

	dp();

	cin >> t;
	while(t --)
	{
		map<string,int> mp;
		string s;
		int Pair = 0;
		cin >> s;
		for(int i = 0;i < s.size();i += 2) 
		{
			if(mp[s.substr(i,2)]) Pair ++;
			mp[s.substr(i,2)] = 1;
		}

		cout << "Case #" << ++ k << ": " << f[Pair][123] << endl;
	}
	return 0;
}

标签：typedef,int,ios,多校,long,牛客,2022,include,define
From： https://www.cnblogs.com/notyour-young/p/16629267.html

相关文章

  • 20220823 模拟赛题解
    T1文件压缩DecriptionlinkSolution可以根据\(S'\)和\(p\)求出第一个字符，然后把\(S'\)sort一遍后得到字符串\(T\)，那么我们就可以求出每一个字符的前驱和后继，所......
  • 2022-8-26 第一组 （≥▽≤） 学习笔记
    目录1.JQuery文档就绪函数选择器基本选择器层级选择器过滤选择器内容选择器属性选择器事件函数新建删除属性遍历操作CSS动画面试题1.JQueryJS库：别人写好的js文件，我们拿来......
  • Solution - NOI 2022
    游记目前只有两个题题解（代码没有），啥时候数据出了我再来补剩下的。众数Solution有个题叫「POI2014」Couriers，这个题启示我们实际上问题等价于询问哪个数出现次数最多，最......
  • 2022-23开工之际
    不要：一直想能不能比过谁，取得什么名次不要：太满足自己的纵欲不要：把学OI的目标放成升学或是某个奖项要：找回初学OI时的乐趣，OI本身的乐趣要：多锻炼身体，不要吃得更肥要：找回两......
  • 2022百度世界大会精华总结（AI应用向）
    完整内容见微信公众号文章：https://mp.weixin.qq.com/s/0d4y9VzSVIcqemqp5O7nzA 官方主页：https://baiduworld.baidu.com/m/world/2022“感受科技，感知未来！7月21日，央视新......
  • 2022暑假每日一题笔记（六）
    T1--4519.正方形数组的数目给定一个非负整数数组A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。返回A的正方形排列的数目。两个排列A1......
  • 2022/8/26 总结
    A.括号序列一看，我趣，字符串，直接抱灵吧，让我死得体面一点……再一看数据范围，我趣，\(\mathtt{O(n)}\)，这怎么写得出来啊？Solution虽然是\(\mathtt{O(7n)}\)，但卡卡常......
  • 肖sir__jenkins搭建20220826
    Jenkins操作手册1、持续集成（CI）Continuousintegration 持续集成 团队开发成员每天都有集成他们的工作，通过每个成员每天至少集成一次，也就意味着一天有可 能多......
  • 2022 NOI 游记
    Day-2起的很早，大概是\(8:00\)左右就到了酒店前台那里，退了房然后去学校了。\(9:00\)左右就到了昆山迪邦华耀学校。（做的出租车去的，下车的时候司机锐评：\(NOI\)不如游戏......
  • 2022-08-26 第二组刘禹彤 学习笔记
    打卡41天###学习内容JS库别人写好的JS文件，我们拿来直接用--------开发中会引入很多.js文件JQery.js：濒临淘汰，经典，10%以下市场React.js：30%市场Angular.js：10%以下市......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99