NOIP模拟17.9.21
NOIP模拟17.9.21
1 任务安排
manage.in/.out/.cpp
1.1 问题描述
你有N 个工作,同一时刻只能做一个任务, 其中每个工作有其所需时
间, 及完成的Deadline(截止时间), 问要完成所有工作, 最迟要从什么时候开
始。
你最早可以从时间0 开始工作。
1.2 输入格式
第一行一个整数N,表示任务数量
接下来n 行,每行两个整数,Ti; Si,分别表示该任务的持续时间和截
止时间。
1.3 输出格式
输出一个整数,表示最晚的开始时间,如果不能完成,输出-1。
1.4 样例输入
4
3 5
8 14
5 20
1 16
1.5 样例输出
2
1.6 数据规模及约定
对于40% 的数据,N <= 20
对于60% 的数据,N <= 1000
对于100% 的数据,1<= N <= 100000
1<= Ti <= 100000
1<= Si <= 1000000
【题解】
水题贪心不解释
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} const int INF = 0x3f3f3f3f;
const int MAXN = + ; struct Node
{
int s,t;
}node[MAXN]; bool cmp(Node a, Node b)
{
return a.t < b.t;
} int n; int main()
{
read(n);
for(register int i = ;i <= n;++ i)
read(node[i].s), read(node[i].t);
std::sort(node + , node + + n, cmp);
int begin = node[].t - node[].s;
int now = node[].t;
for(register int i = ;i <= n;++ i)
{
now += node[i].s;
if(now > node[i].t)
{
begin -= now - node[i].t;
now = node[i].t;
}
}
printf("%d", max(-, begin));
return ;
}
T1
小a 的强迫症
qiang.in/.out/.cpp
2.1 问题描述
小a 是一名强迫症患者,现在他要给一群带颜色的珠子排成一列,现在
有N 种颜色,其中第i 种颜色的柱子有num(i) 个。要求排列中第i 种颜色
珠子的最后一个珠子,一定要排在第i+1 种颜色的最后一个珠子之前。问
有多少种排列珠子的方案。
2.2 输入格式
第一行一个整数N,表示珠子颜色数量
第二行N 个整数,分别表示每种珠子的颜色数量
2.3 输出格式
排列方案数,对998244353 取余
2.4 样例输入
3
2 2 1
2.5 样例输出
3
2.6 数据规模及约定
共3 种排列方案:
1 2 1 2 3
1 1 2 2 3
2 1 1 2 3
对于40% 的数据,所有珠子数量和小于15
对于80% 的数据,N <= 1000,所有珠子数量和小于5000
对于100% 的数据,N <= 100000,所有珠子数量和小于500000
【题解】
一开始想的正解然后马上否定然后推出错误的式子然后挂掉了。
本题有一个很强的限制,叫“排列中第i 种颜色珠子的最后一个
珠子,一定要排在第i+1 种颜色的最后一个珠子之前”
不难想递推
num[i]表示第i种珠子颜色
sum[i] = Σnum[1...i]
f[i]表示前i种颜色柱子的方案数
常规思路,对于每一种前i - 1种珠子的放法,考虑第i种珠子怎么放
第i种珠子一定有一颗放到最后面,剩余的num[i] - 1颗可以随便
往前面插。我们可以想成共有sum[i] - 1个空位,选num[i] - 1个空位
放第i种颜色的珠子,其余放已经确定的一种第i - 1种珠子的方法
于是f[i] = f[i - 1] * C(sum[i] - 1, num[i] - 1)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b)) inline void read(long long &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} const long long INF = 0x3f3f3f3f;
const long long MAXN = + ;
const long long MOD = ; long long n, num[MAXN], sum[MAXN], ans; long long pow(long long a, long long b)
{
long long r = , base = a % MOD;
for(;b;b >>= )
{
if(b&)r *= base, r %= MOD;
base *= base, base %= MOD;
}
return r;
} long long f[]; long long ni(long long a)
{
if(a == )return ;
return pow(a, MOD - );
} long long C(long long n, long long m)
{
if(m > n)return ;
return ((f[n]%MOD * ni(f[m]))%MOD * ni(f[n - m]))%MOD;
} int main()
{
read(n);
for(register long long i = ;i <= n;++ i)
{
read(num[i]);
num[i]%=MOD;
sum[i] = sum[i - ] + num[i];
sum[i] %= MOD;
}
f[] = ;
for(register long long i = ;i <= ;++ i) f[i] = f[i - ] * i, f[i] %= MOD;
ans = ;
for(register long long i = ;i <= n;++ i)
{
ans *= C(sum[i] - , num[i] - );
ans %= MOD;
}
printf("%lld", ans);
return ;
}
T2
3 函数求和
sum.in/.out/.cpp
3.1 问题描述
你有一个含N 个数字的数组A,元素标号1 到N,同时他也有N 个函
数,也标号1 到N。
第i 个函数会返回数组中标号Li 和Ri 之间的元素的和。
现在有以下两种询问:
1 x y 将数组的第x 个元素修改为y。
2 m n 询问标号在m 和n 之间的函数的值的和。
3.2 输入格式
输入数据第一行包含一个整数N,表示数组的长度和函数的数量。
接下来的一行包含N 个整数,表示数组中的元素Ai。
接下来的N 行,每行包含两个整数Li;Ri,表示一个函数。
接下来一行包含一个整数Q,表示询问次数。
下面Q 行,每行一个询问,格式见题目描述。
3.3 输出格式
对于每个第2 类询问,输出相应的答案。
3.4 样例输入
5
1 2 3 4 5
1 3
2 5
4 5
3 5
1 2
4
2 1 4
1 3 7
2 1 4
2 3 5
4
3.5 样例输出
41
53
28
3.6 数据规模及约定
对于前20% 的数据: N 1000;Q 1000
对于另外30% 的数据: Ri
最新文章
- Java企业实训 - 01 - Java前奏
- linux 环境下运行STS时 出现must be available in order to run STS
- Linux:Ubuntu16.04下创建Wifi热点
- ACM 笨小熊
- linux服务器调整参数支持高并发
- wcf stream 不知道长度的情况下,读取stream
- [Heroku] How to pull, push changes
- Linux shell 之 提取文件名和目录名的一些方法
- 51单片机C语言学习笔记7:关于.c文件和.h文件
- zeromq源码分析笔记之架构(1)
- php or || 和 and &;&;
- Windows 下让 Python 多个版本共存(支持 pip)
- 关于HTML5新手应该知道的几点知识
- Python基础之元组
- Jmeter 发测试报告到邮箱,expand/collapse 图片不显示
- error TS2304: Cannot find name &#39;Promise&#39; &;&; TS2307: Cannot find module &#39;**&#39;
- 【第一次玩Travis CI】终于弄好了我的马鸭
- PAT甲 1001. A+B Format (20) 2016-09-09 22:47 25人阅读 评论(0) 收藏
- Vuex 单状态库 与 多模块状态库
- Beta发布文案+美工