NOIP模拟 6.28
NOIP模拟赛6.28
Problem 1 高级打字机(type.cpp/c/pas)
【题目描述】
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。
请为这种高级打字机设计一个程序,支持如下3种操作:
1.T x:在文章末尾打下一个小写字母x。(type操作)
2.U x:撤销最后的x次修改操作。(Undo操作)
(注意Query操作并不算修改操作)
3.Q x:询问当前文章中第x个字母并输出。(Query操作)
文章一开始可以视为空串。
【输入格式】
第1行:一个整数n,表示操作数量。
以下n行,每行一个命令。保证输入的命令合法。
【输出格式】
每行输出一个字母,表示Query操作的答案。
【样例输入】
7
T a
T b
T c
Q 2
U 2
T c
Q 2
【样例输出】
b
c
【数据范围】
对于40%的数据 n<=200;
对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。
<高级挑战>
对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。
<IOI挑战>
必须使用在线算法完成该题。
简单:栈模拟即可
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
inline void read(int &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();if(c == '-')x = -x;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a > b ? b : a;} const int INF = 0x3f3f3f3f;
const int MAXN = + ; char stack[MAXN]; int main()
{
register char c;
register int top = ,n,tmp;
read(n);
for(register int i = ;i <= n;++ i)
{
c = getchar();while(c != 'T' && c != 'U' && c != 'Q')c = getchar();
if(c == 'T')
{
c = getchar();
while(c > 'z' || c < 'a')c = getchar();
stack[++top] = c;
}
else if(c == 'U')
{
read(tmp);
top -= tmp;
if(top < )top = ;
}
else
{
read(tmp);
printf("%c\n", stack[tmp]);
}
}
return ;
}
高级:
我们把每一个操作后得到的序列称作一个版本,第i个操作后得到的序列称作版本i。我们需要把这些版本维护成一个树。
如果第i + 1个操作是插入操作,那么我们把版本i指向i + 1;
如果第i + 1个操作是撤销k次操作,那么我们把版本(i - k )指向i + 1.
这其实是一颗字典树。我们记num[i]为版本i所代表字符,从根节点走到i,就能得到版本i的序列,从而进行查询。
为了保持优秀的复杂度,我们不能每一次询问都去从根节点向上找这棵树,因为这颗树的高度并不是logn级别的。因此我们需要预先读入询问,在dfs的过程中处理询问,保证了线性复杂度。
代码待补充
Problem 2 不等数列(num.cpp/c/pas)
【题目描述】
将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2012取模。
【输入格式】
第一行2个整数n,k。
【输出格式】
一个整数表示答案。
【样例输入】
5 2
【样例输出】
66
【数据范围】
对于30%的数据:n <= 10
对于100%的数据:k < n <= 1000
水水的小DP
记f[i][j]为1..i中有j个<的方案数
对于第i个数,有四种方法:放在最左边,放在最右边,放在中间‘>’的位置,放在中间'<'的位置
由于第i个数是当前最大,易得:
放在最左边 方案数:f[i - 1][j]
放在最右边 方案数:f[i - 1][j - 1]
放在中间‘>’的位置 方案数:f[i - 1][j - 1] * ((i - 2) - (j - 1)) = f[i - 1][j - 1] * (i - j - 1)
放在中间'<'的位置 方案数:f[i - 1][j] * j
综上,总转移方程:
f[i][j] = f[i - 1][j] * (j + 1) + f[i - 1][j - 1] * (i - j)
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
inline void read(int &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();if(c == '-')x = -x;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a > b ? b : a;} const int MOD = ;
const int INF = 0x3f3f3f3f;
const int MAXN = + ;
const int MAXK = + ; int n,k; //f[i][j]表示前i个数插入j个<的方案数
//f[i][j] = f[i-1][j] + f[i-1][j-1] * (i - 2) int f[MAXN][MAXK]; //'<' int main()
{
read(n);read(k);
for(register int i = ;i <= n;++ i)f[i][] = ;
f[][] = ;
for(register int i = ;i <= n;++ i)
{
for(register int j = ;j < i;++ j)
{
f[i][j] = (f[i - ][j - ] * (i - j)) % MOD + (f[i - ][j] * (j + )) % MOD;
}
}
printf("%d", f[n][k] % MOD);
return ;
}
Problem 3 经营与开发(exploit.cpp/c/pas)
【题目描述】
4X概念体系,是指在PC战略游戏中一种相当普及和成熟的系统概念,得名自4个同样以“EX”为开头的英语单词。
eXplore(探索)
eXpand(拓张与发展)
eXploit(经营与开发)
eXterminate(征服)
——维基百科
今次我们着重考虑exploit部分,并将其模型简化:
你驾驶着一台带有钻头(初始能力值w)的飞船,按既定路线依次飞过n个星球。
星球笼统的分为2类:资源型和维修型。(p为钻头当前能力值)
1.资源型:含矿物质量a[i],若选择开采,则得到a[i]*p的金钱,之后钻头损耗k%,即p=p*(1-0.01k)
2.维修型:维护费用b[i],若选择维修,则支付b[i]*p的金钱,之后钻头修复c%,即p=p*(1+0.01c)
注:维修后钻头的能力值可以超过初始值(你可以认为是翻修+升级)且金钱可以透支
请作为舰长的你仔细抉择以最大化收入。
【输入格式】
第一行4个整数n,k,c,w。
以下n行,每行2个整数type,x。
type为1则代表其为资源型星球,x为其矿物质含量a[i];
type为2则代表其为维修型星球,x为其维护费用b[i];
【输出格式】
一个实数(保留2位小数),表示最大的收入。
【样例输入】
5 50 50 10
1 10
1 20
2 10
2 20
1 30
【样例输出】
375.00
【数据范围】
对于30%的数据 n<=100
另有20%的数据 n<=1000;k=100
对于100%的数据 n<=100000; 0<=k,c,w,a[i],b[i]<=100;保证答案不超过10^9
非常神奇的做法
我们不难发现一个结论:如果我们把初始能量看做1,那么把算出来的结果乘上w即可
如果我们从第二个星球开始,把在那个星球的初始能量看做1,那么把算出来的答案乘上第二个星球时的能量即可
(w或w + (1 + 0.01 *c) 或 w - (1 - 0.01 * k))
第三....n - 1个星球同理
但是这样没法做。无论贪心还是dp,都会枚举所有选与不选的情况。
考虑倒推。我们记f[i]为把即将离开(即采集或修理或什么都不做之后)第i个星球的能量看做1,第i...n星球所能获得的最大收益。
在第i个星球有两种决策:收集/修理 或 不收集/不修理
不难得到:f[i] = max(f[i + 1], f[i + 1] * (1 - 0.01 * k) + a[i] * 1) 或 f[i] = max(f[i + 1], f[i + 1] * (1 + 0.01 * c) - b[i] * 1)
初始状态:如果第n颗星球为资源型,则收集,否则不维修
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
inline void read(int &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();if(c == '-')x = -x;}
inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline double max(double a, double b){return a > b ? a : b;}
inline int min(int a, int b){return a > b ? b : a;} const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + ; double c,k;
int tmp1,tmp2;
int n,w,type[MAXN],num[MAXN]; double ans; int main()
{
read(n);read(tmp2);read(tmp1);read(w);
c = + 0.01 * tmp1;
k = - 0.01 * tmp2;
for(register int i = ;i <= n;++ i)
read(type[i]), read(num[i]);
if(type[n] - )ans = ;
else ans = num[n];
for(register int i = n - ;i;-- i)
if(type[i] - )
ans = max(ans, ans * c - num[i]);
else
ans = max(ans, ans * k + num[i]);
printf("%.2lf", ans * (double)w);
return ;
}
最新文章
- Wordpress基础:安装主题和插件
- C/C++面试题总结
- 简易版CMS后台管理系统开发流程
- 滚动光效shader
- LightOJ::1077 -----奇妙的最大公约数
- Codeforces 452D [模拟][贪心]
- ScrollBox 响应鼠标滚轮和ComboBox禁止滚动
- Unreal Engine4 蓝图入门
- 基于jq图片居中插件 [center]
- Android之Notification的多种用法
- js——DOM操作(一)
- loadrunner监控度量项及中文解释
- Python数据类型和变量
- 第 15 章 可扩展性设计之 Cache 与 Search 的利用
- 八.nginx网站服务实践应用
- MogoDB(6)--mongoDB高可用和4.0特性
- 微信原始坐标转换成百度坐标 lat lng
- [leetcode]96. Unique Binary Search Trees给定节点形成不同BST的个数
- 洗礼灵魂,修炼python(12)--python关键词,包
- 使用AWR报告诊断Oracle性能问题
热门文章
- mysql order by排序查询速度问题
- Office宏的基本利用
- Error-Idea:Process finished with exit code 1
- Python学习day41-数据库(1)
- ubuntu与xshell连接不起来:
- 732F Tourist Reform
- [转]WPF的Presenter(ContentPresenter)
- 深入浅出 Java Concurrency (11): 锁机制 part 6 CyclicBarrier[转]
- 组件:组合slot
- Spring Boot入门样例-001-Java和Maven安装配置