最后一次模拟考试题解

这篇具有很好参考价值的文章主要介绍了最后一次模拟考试题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哦我想这不用看都知道是为了水任务

T1 黑白染色

其实这题有原
最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
什么手写体 md (指 markdown)

分析

首先这题如果你题目没看错的话 ,会发现其实他是 n × m n \times m n×m 让你求 n × n n \times n n×n 的区域内的点(不会只有我一个人题目看错了罢

然后我们会发现其实我们只关心每一列放了多少,并不关心是怎么放的(这一步可以用组合数算出来)

波利亚说过解题时可以回到定义上去 , 所以列出公式(这里 n u m [ i ] num[i] num[i] 代表每一列放置点的数量)
∑ i = 1 n n u m [ i ] = k ∑ i = 2 n + 1 n u m [ i ] = k \begin{matrix} \sum_{i=1}^n num[i] = k \\ \sum_{i=2}^{n+1} num[i] = k\end{matrix} i=1nnum[i]=ki=2n+1num[i]=k

两式相减就可以得到: n u m [ i ] = n u m [ i + n ] num[i] = num[i+n] num[i]=num[i+n]

所以我们就发现了所有模 n n n 余数相同的列的值时一样的

剩下的我就不知道了

Code

我讲不来但是我有代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;
const int mod = 1e9+7;
using namespace std;
int c[200][200];
int d[200][200];
int dp[200][10005];
int n,m,k;
int ksm(int a, int b){
	int x = a,ans = 1;
	while(b){
		if(b & 1){
			ans  = ans * x % mod;
		}
		x = x * x % mod;
		b >>= 1;
	}
	return ans;
}
signed main(){
	freopen("discolour.in","r",stdin);
	freopen("discolour.out","w",stdout);
	cin >> n >> m >> k;
	for(int i =1;i <= 100; i++){
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; j++){
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
		}
	}
	for(int i = 1;i <= n; i++){
		for(int j = 0; j <= n; j++){
			d[i][j] = ksm(c[n][j],m/n+(m/n*n+i<=m));
//			cout << d[i][j] << endl;
		}
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= min(k,n*i); j++){
			for(int kk = 0; kk <= min(j,n); kk++){
				dp[i][j] = (dp[i][j] + dp[i-1][j-kk]*d[i][kk] % mod)%mod;
//				cout << dp[i][j] << endl;
			}
		}
	}
	cout << dp[n][k];
	return 0;
}

当时还把 colour 打成了 color , 幸好最后改回来了

cspj的时候文件保存按成了撤销痛失100分我不说是谁

T2 造城墙

最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
有一说一这题数据是真的弱啊

首先,对于 40 % 40\% 40% 的数据,可以直接状压

然后对于另外 20 % 20\% 20% 的数据可以直接染色跑二分图

分析

正文开始

看到这题其实像 czy 那样的猥琐小子大佬,第一反应应该就是网络流罢,对棋盘黑白染色,这个应该不难想

没错这个跟这道题的正解没关系
但是可以帮助你理解思路

注意下面均用 0 代表偶数 1 代表奇数

首先一个很显然的贪心就是 所有横着的砖块肯定放在最顶上

如果你用脚造了几组数据玩玩的话你会发现,所有横着放的砖块会构成多个倒三角

like this
最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
如果对于这个倒三角还有点懵的可以在这里停一下搞清楚先

所以我们考虑维护当前列倒三角的高度

让我们随便造几组数据(下面的数据均是空白格的个数
一列一列枚举:1 高度为 1, 10 高度为 2 , 101 高度为 3,1011 高度为3 , 10110 高度为2

这里发现什么,当出现 00 或者 11 的时候高度不会再增加,并且下一行如果奇偶性不同高度还会减 1 (其实这个应该看图就知道了罢

如果您无法理解

可以把他看成一个黑白染色,每一列不能匹配的黑格子都会被放到最顶上,这样一列一列的黑格子剩下来就是高度了

那接下来就考虑维护高度,有了上面的规律之后,我们记 b l a c k black black 为当前的高度(黑格子数)

不难发现,如果当前的空白格数小于黑格子数,肯定就不能满足。如果空白格数减黑格子数为奇数,那黑格子数就要加一,如果为偶数,那就减一

最后别忘了在黑格子减一的时候和 0 取 m a x max max (其实不取你也能得到 80 分的好成绩)

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;

using namespace std;
int n;
priority_queue<pair<int,int>,vector<pair<int,int> > , greater<pair<int,int> > > q;
int x,y,z;

signed main(){
	freopen("chicken.in","r",stdin);
	freopen("chicken.out","w",stdout);
	cin >> n;
	cin >> x >> y >> z;
	int t,a;
	cin >> t >> a;
	q.push(make_pair(t-z+y,a));
	int sum = a;
	for(int i = 2; i <= n; i++){
		cin >> t >> a;
		while(a){
			int xx = q.top().first,num = q.top().second;
			
			if(xx + x <= t){
//				cout << xx << " " << num << endl;
				q.pop();
				if(num > a){
					num -= a;
					q.push(make_pair(xx,num));
					q.push(make_pair(max(xx+x+z,t-y+z),a));
					a = 0;
				}else{
					a -= num;
					q.push(make_pair(max(xx+x+z,t-y+z),num));
				}
//			cout << xx << " xx ";
//				cout << max(xx+x+y,t-z+y) << " xx ";
			}else{
				q.push(make_pair(t-y+z,a));
//				cout << t-y+z << " " << a << endl;
				sum += a;
				a = 0;
//				cout << t-z+y << " yy ";
			}
		}
//		cout << endl;
	}
	cout << sum;
	return 0;
}

T3 炸鸡

最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
这手写的 LaTeX \LaTeX LATEX 是真的一言难尽

分析

这题有一个很重要的性质就是 :同一份订单中,不会有任何一口锅做超过一份的鸡(因为鸡的保存时间小于制作时间)

接下来考虑贪心

虽然我们是非常单纯美好的,但是这题的做法非常的黑心,那就是 给顾客的鸡能多接近保质期就多接近保质期

然后我们就可以用优先队列维护每口锅最早开始的闲置时间,然后每次取最早的就行,如果没有锅满足要求那就新买几口锅 为了让顾客吃上临近保质期的鸡我还新买锅我真是太伟大了)

写代码的时候记得搞清楚每口锅最早开始闲置的时间是什么

好的我们写完了这个非常czy的代码,定睛一看,忽然发现,数据范围是 1 0 9 10^9 109 而不是 10

那这样我们一个一个丢肯定不对,那么怎么办呢?
如果你把每次取出的锅的时间都输出来,你会发现,有很多锅的时间其实是一样的
(别问我为什么要输出,因为当时把 y , z y,z y,z 看反了)

这样想到什么? 没错往堆里面丢 p a i r pair pair 不就好了吗

Code

这里有个小技巧就是一开始就把第一次所用的锅都扔进去,这样可以防止越界和代码打漏

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long
const int N = 1e6+10;
const int M = 1e5+10;

using namespace std;
int n;
priority_queue<pair<int,int>,vector<pair<int,int> > , greater<pair<int,int> > > q;
int x,y,z;

signed main(){
	freopen("chicken.in","r",stdin);
	freopen("chicken.out","w",stdout);
	cin >> n;
	cin >> x >> y >> z;
	int t,a;
	cin >> t >> a;
	q.push(make_pair(t-z+y,a));
	int sum = a;
	for(int i = 2; i <= n; i++){
		cin >> t >> a;
		while(a){
			int xx = q.top().first,num = q.top().second;
			
			if(xx + x <= t){
//				cout << xx << " " << num << endl;
				q.pop();
				if(num > a){
					num -= a;
					q.push(make_pair(xx,num));
					q.push(make_pair(max(xx+x+z,t-y+z),a));
					a = 0;
				}else{
					a -= num;
					q.push(make_pair(max(xx+x+z,t-y+z),num));
				}
//			cout << xx << " xx ";
//				cout << max(xx+x+y,t-z+y) << " xx ";
			}else{
				q.push(make_pair(t-y+z,a));
//				cout << t-y+z << " " << a << endl;
				sum += a;
				a = 0;
//				cout << t-z+y << " yy ";
			}
		}
//		cout << endl;
	}
	cout << sum;
	return 0;
}

T4 骑士与国王

最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
这题其实就是个容斥对吧(逃)

Code

我这题没打,那就放一下 x h g u a ⋅ h y x xhgua\cdot hyx xhguahyx 大帝的代码罢
最后一次模拟考试题解,随笔,刷题笔记,c++,笔记,学习
黄瓜好吃,拜谢黄瓜!!!

结语

谁家 noip 3道数学题起步啊

谁家 noip 3小时不到啊

谁家 noip 有人踹电源线啊

有一说一 OI这玩意真的运气成分很高

我爱优先队列 ! 优先队列好闪 拜谢优先队列!!! 以后找对象就找优先队列这样的 ! ! ! \begin{matrix}\color{white}{我爱优先队列!} \\ \color{white}{优先队列好闪\ 拜谢优先队列!!!}\\ \color{white}{以后找对象就找优先队列这样的!!!}\end{matrix} 我爱优先队列!优先队列好闪 拜谢优先队列!!!以后找对象就找优先队列这样的!!!文章来源地址https://www.toymoban.com/news/detail-633857.html

到了这里,关于最后一次模拟考试题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode题解C++】34.在排序数值中查找第一个和最后一个位置

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 思路

    2024年01月16日
    浏览(40)
  • 异步查询如何做节流(只查询时间段最后一次)

    要实现异步查询的节流,只查询时间范围内的最后一次,可以使用一个定时器来延迟执行查询操作,并在每次触发查询时取消之前的定时器。这样,只有在一定时间内没有新的查询请求时,才会执行最后一次查询。 以下是一个示例的JavaScript代码实现: 在这个示例中,thrott

    2024年02月12日
    浏览(43)
  • Unity学习笔记--File.ReadAllLines和File.ReadAllText的使用以及注意事项(一定要看到最后!!!)

    最近在做文件存储以及读取的时候,需要用到C#给我们提供的类: File 具体使用方法可以看官方文档:C# File 类 这篇文章只会说 File.ReadAllLines 和 File.ReadAllText 的使用以及注意事项 Tips:(一定要看到最后!!!) 一、File.ReadAllLines 重载 操作 ReadAllLines(String) 打开一个文本文件

    2024年02月02日
    浏览(44)
  • [C++随笔录] string模拟实现

    放在前面: 我们实现string类, 并不是 跟源码一模一样(并不是造一个新的轮子) , 只是了解 每个接口的实现过程 ⇒ 我们以后也 用的放心 (比如时间复杂度, 空间复杂度等等) 习惯把不可能为负数的值的类型 定义为 size_t 考虑到 无参调用和有参调用 只有一个参数 ⇒ 我们可以采用

    2024年02月07日
    浏览(30)
  • Hive考试练习题(参考题解)

      前置环境: 请打开【VMware Workstation Pro】中的【linux1】环境,登录账号【root】密码【root】。  一、搭建MySQL运行环境(25分,每项5分) 1、删除MySQL依赖的libs包 2、安装MySQL的服务器与安装MySQL的客户端 3、登录MySQL并修改MySQL密码 4、给与MySQL的master权限 5、刷新MySQL权限并退出

    2024年02月09日
    浏览(51)
  • 对 .NET程序2G虚拟地址紧张崩溃 的最后一次反思

    最近接连遇到了几起 2G 虚拟地址紧张 导致的程序崩溃,基本上 90% 都集中在 医疗行业 ,真的很无语,他们用的都是一些上古的 XP,Windows7 x86,我也知道技术人很难也基本无法推动硬件系统和设备的升级,这里蕴含了巨大的人情世故。 写这一篇的目的是想系统化的整理一下如

    2024年02月05日
    浏览(37)
  • 取消lodash.throttle中的默认执行完最后一次函数

    我的场景: 我有一个列表,我考虑用户连续点击删除的情况,如果用户连续点击,可能会导致数据库中的数据被删除了,但是我还需要刷新数据列表才能反应到页面上,可是这时候用户又点击了同一条数据的删除按钮多次,导致发起了多次删除一个已经不存在的数据的请求,于

    2024年01月21日
    浏览(38)
  • 「优选算法刷题」:在排序数组中查找元素的第一个和最后个位置

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 二分

    2024年01月22日
    浏览(43)
  • [C++随笔录] stack && queue模拟实现

    🗨️stack的容器适配器应该选什么比较好呢? 首先, stack的特点是 头部入, 尾部出 ⇒ 尾插 和 尾删操作比较频繁 我们前面学过的容器有 vector 和 list, vector 和 list的尾插 和 尾删的时间复杂度是 O(1) , 还是适合做容器适配器的. stack的基本结构 用这个容器对象来进行模拟实现stac

    2024年02月06日
    浏览(43)
  • 【毕业设计】考试刷题小程序 基于微信小程序的考试刷题系统小程序

    💗博主介绍:✌全网粉丝10W+,CSDN全栈领域优质创作者,博客之星、掘金/华为云/阿里云等平台优质作者。 👇🏻 精彩专栏 推荐订阅👇🏻 计算机毕业设计精品项目案例-200套 🌟 文末获取源码+数据库+文档 🌟 感兴趣的可以先收藏起来,还有大家在毕设选题,项目以及论文编

    2024年04月13日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包