NOIP#17模拟赛
共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.1
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。
tarjn加dfs。
因为tarjin中的
col[stack[top]]=sumcol;写成了
col[stack[top]]=now;
挂了一半的点，要注意！！！！！！！！
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100001
using namespace std;
map<int,int>ma[MAXN];
int n,m;
int tot,tot1;
int tim,top,sumcol;
int col[MAXN],dis[MAXN];
int ans[MAXN],into[MAXN],vis[MAXN];
int to[MAXN],net[MAXN],head[MAXN];
int to1[MAXN],net1[MAXN],head1[MAXN];
int low[MAXN],dfn[MAXN],stack[MAXN],visstack[MAXN];
void add(int u,int v){
to[++tot]=v;net[tot]=head[u];head[u]=tot;
}
void add1(int u,int v){
to1[++tot1]=v;net1[tot1]=head1[u];head1[u]=tot1;
}
int tarjin(int now){
low[now]=dfn[now]=++tim;
stack[++top]=now;
vis[now]=1;
visstack[now]=1;
for(int i=head[now];i;i=net[i])
if(visstack[to[i]])
low[now]=min(low[now],dfn[to[i]]);
else if(!vis[to[i]]){
tarjin(to[i]);
low[now]=min(low[now],low[to[i]]);
}
if(dfn[now]==low[now]){
sumcol++;
col[now]=sumcol;
while(stack[top]!=now){
col[stack[top]]=sumcol;
visstack[stack[top]]=0;
top--;
}
visstack[now]=0;
top--;
}
}
void dfs(int now){
for(int i=head1[now];i;i=net1[i]){
dfs(to1[i]);
dis[now]=max(dis[now],dis[to1[i]]);
}
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
if(!vis[i])
tarjin(i);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=net[j])
if(col[i]!=col[to[j]])
if(ma[col[i]].find(col[to[j]])==ma[col[i]].end()){
ma[col[i]][col[to[j]]]=1;
add1(col[i],col[to[j]]);
into[col[to[j]]]++;
}
for(int i=1;i<=n;i++)
dis[col[i]]=max(dis[col[i]],i);
for(int i=1;i<=sumcol;i++)
if(!into[i])
dfs(i);
for(int i=1;i<=n;i++)
cout<<dis[col[i]]<<" ";
fclose(stdin);
fclose(stdout);
return 0;
}
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
数组开小了，gg，找一个最长严格上升子序列。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100005;
const int oo=0x3fffffff;//极大值
int a[maxn];
int lis[maxn], pos[maxn];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",a+i);
int top=0;
lis[0]=-oo;
for(int i=1;i<=n;i++){
if(a[i]>lis[top]&&a[i]-lis[top]-1>=i-pos[top]-1){
lis[++top]=a[i];
pos[top]=i;
}
else{
int l=0, r=top, tp=-1;
while(l<=r){
int mid=(l+r)>>1;
if(a[i]-lis[mid]-1>=i-pos[mid]-1){
tp=mid;
l=mid+1;
}
else r=mid-1;
}
if(tp!=-1) lis[tp+1]=a[i], pos[tp+1]=i;
}
}
cout<<n-top<<endl;
}
return 0;
}
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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1001
using namespace std;
int n,k;
int c1[MAXN],c2[MAXN];
struct nond{
int num[1000];
}f[101][101];
void mul1(int lena1,int q,int aa,int bb){
memset(c1,0,sizeof(c1));
for(int i=0;i<=lena1;i++)
c1[i]=f[aa-1][bb-1].num[i];
for(int i=1;i<=lena1;i++)
c1[i]*=q;
for(int i=1;i<=lena1;i++){
if(c1[i]>=10){
if(i==lena1) lena1++;
c1[i+1]+=c1[i]/10;
c1[i]%=10;
}
}
for(;lena1>=1;lena1--) if(c1[lena1]!=0) break;
c1[0]=lena1;
}
void mul2(int lena2,int q,int aa,int bb){
memset(c2,0,sizeof(c2));
for(int i=0;i<=lena2;i++)
c2[i]=f[aa-1][bb].num[i];
for(int i=1;i<=lena2;i++)
c2[i]*=q;
for(int i=1;i<=lena2;i++){
if(c2[i]>=10){
if(i==lena2) lena2++;
c2[i+1]+=c2[i]/10;
c2[i]%=10;
}
}
for(;lena2>=1;lena2--) if(c2[lena2]!=0) break;
c2[0]=lena2;
}
void jia(int aa,int bb){
c1[0]=max(c1[0],c2[0]);
for(int i=1;i<=c1[0];i++) c1[i]+=c2[i];
for(int i=1;i<=c1[0];i++)
if(c1[i]>=10){
if(i==c1[0]) c1[0]++;
c1[i+1]+=c1[i]/10;
c1[i]%=10;
}
for(;c1[0]>=1;c1[0]--) if(c1[0]!=0) break;
for(int i=0;i<=c1[0];i++) f[aa][bb].num[i]=c1[i];
}
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
scanf("%d%d",&n,&k);
f[1][0].num[1]=1;f[1][0].num[0]=1;
f[2][0].num[1]=1;f[2][0].num[0]=1;
f[2][1].num[1]=1;f[2][1].num[0]=1;
for(int i=3;i<=n;i++)
f[i][0].num[0]=1,f[i][0].num[1]=1;
for(int i=3;i<=n;i++)
for(int j=1;j<i;j++){
int k=i-j,tot1=0;
int kk=j+1,tot2=0;
mul1(f[i-1][j-1].num[0],k,i,j);
mul2(f[i-1][j].num[0],kk,i,j);
jia(i,j);
}
for(int i=f[n][k].num[0];i>=1;i--)
cout<<f[n][k].num[i];
}
/*
20 15
*/