20170613NOIP模拟赛
共3道题目,时间3小时
题目非原创,仅限校内交流使用
题目名称 |
Graph |
Incr |
Permutation |
文件名 |
graph |
incr |
permutation |
输入文件 |
graph.in |
incr.in |
permutation.in |
输出文件 |
graph.out |
incr.out |
permutation.out |
时间限制 |
1000ms |
1000ms |
1000ms |
内存限制 |
256mb |
256mb |
256mb |
测试点数目 |
10 |
10 |
10 |
测试点分值 |
10 |
10 |
10 |
是否有部分分 |
否 |
否 |
否 |
题目类型 |
传统 |
传统 |
传统 |
评测环境
操作系统:Windows XP Professional SP3
CPU: Intel(R) Pentium(R) CPU G2030 @ 3.00GHz (2CPUs)
系统内存:2GB
评测工具:Cena 0.8.
Problem 1 Graph (graph.cpp/c/pas)
【题目描述】
给出 N 个点,M 条边的有向图,对于每个点 v,求 A(v) 表示从点 v 出发,能到达的编号最大的点。
【输入格式】
第 1 行,2 个整数 N,M。 接下来 M 行,每行 2 个整数 Ui,Vi,表示边 ⟨Ui,Vi⟩。点用 1,2,...,N 编号。
【输出格式】
N 个整数 A(1),A(2),...,A(N)。
【样例输入】
4 3
1 2
2 4
4 3
【样例输出】
4 4 3 4
【数据范围】
对于 60% 的数据,1 ≤ N,K ≤ 10^3;
对于 100% 的数据,1 ≤ N,M ≤ 10^5。
思路
dfs/Tarjan/拓扑序列/bfs皆可。
Problem 2 Incr(incr.cpp/c/pas)
【题目描述】
数列 A1,A2,...,AN,修改最少的数字,使得数列严格单调递增。
【输入格式】
第 1 行,1 个整数 N
第 2 行,N 个整数 A1,A2,...,AN
【输出格式】
1 个整数,表示最少修改的数字
【样例输入】
3
1 3 2
【样例输出】
1
【数据范围】
对于 50% 的数据,N ≤ 10^3
对于 100% 的数据,1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9
思路
对于每个Ai,先减去i,然后求最长严格上升子序列a;
ans=n-a;
代码实现
#include<cstdio>
const int maxn=1e5+;
int n,a;
int s[maxn],v[maxn];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&s[i]),s[i]-=i;
v[++a]=s[];
for(int i=;i<=n;i++){
if(v[a]<s[i+]) v[++a]=s[i+];
else
for(int j=;j<=a;j++)
if(s[i+]<v[j]){v[j]=s[i+];break;}
}
printf("%d",n-a);
return ;
}
Problem 3 Permutation (permutation.cpp/c/pas)
【题目描述】
将 1 到 N 任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。
问在所有排列中,有多少个排列恰好有K个“<”。
例如排列(3, 4, 1, 5, 2)
3 < 4 > 1 < 5 > 2
共有2个“<”
【输入格式】
N,K
【输出格式】
答案
【样例输入】
5 2
【样例输出】
66
【数据范围】
20%:N <= 10
50%:答案在0..2^63-1内
100%:K < N <= 100
思路
DP方程:f[i][j]=f[i-1][j]*(j+1)+f[i-1][j-1]*(i-j);
代码实现
#include<cstdio>
const int maxn=;
inline int max_(int x,int y){return x>y?x:y;}
int n,k;
int s[][][];
void tot(int i,int j,int v1,int v2){
int b=max_(s[i^][j][],s[i^][j-][]);
for(int a=;a<=b;a++) s[i][j][a]=s[i^][j][a]*v1+s[i^][j-][a]*v2;
for(int a=;a<=b;a++)
if(s[i][j][a]>){
s[i][j][a+]+=s[i][j][a]/;
s[i][j][a]%=;
if(a==b) b++;
}
s[i][j][]=b;
}
void put(int i,int j){
printf("%d",s[i][j][s[i][j][]]);
for(int a=s[i][j][]-;a>;a--)
printf("%03d",s[i][j][a]);
}
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
scanf("%d%d",&n,&k);
s[][][]=s[][][]=s[][][]=s[][][]=;
for(int i=;i<=n;i++)
for(int j=;j<=k;j++)
tot(i&,j,j+,i-j);
put(n&,k);
return ;
}
最新文章
- jxl 2.6.12 与 jxl 2.3.0 稳定版性能比较
- 20145235 《Java程序设计》第4周学习总结
- linux搜索命令
- Cocos2d-x3.0游戏实例之《别救我》第二篇——创建物理世界
- Spring注入值得2种方式:属性注入和构造注入
- Struts2中数据封装方式
- 简述java接口和C++虚类的相同和不同之处
- Log4j配置文件详解及实例
- 【原创】Linux基础之linux服务器服务器间拷贝文件
- PHP删除数组中空值的方法介绍
- Spring Security(十二):5. Java Configuration
- Marriage Match IV HDU - 3416(最短路 + 最大流)
- ionic2+集成第三方sdk时,合并多个清单文件的方法
- day63 django-模板语言
- 高并发 Web 服务的演变:节约系统内存和 CPU
- 仿迅雷播放器教程 -- 封装VLC (5)
- centos 7 下多网卡绑定+ vlan 网卡配置
- 3.window窗口
- ajax和promise的结合使用
- CodeForces - 847B Preparing for Merge Sort 二分
热门文章
- 赋予option元素点击事件后,点击select时却触发了option事件。如何解决?
- Can&#39;t install &#39;*&#39; from pristine store, because no checksum is recorded for this file (SVN报错)
- 二分图最大匹配(匈牙利算法) POJ 3041 Asteroids
- javascript学习之Date对象
- python自动化--语言基础二运算符、格式化输出、条件语句、循环语句、列表、元组
- Shell输入/输出重定向
- js数组的处理
- PMP 学习心得
- tarjan求强连通分量模板
- Window下的———JDK环境的配置