当前位置:首页 >> 学科竞赛 >>

NOIP冲刺模拟题


高 2016 信息学奥赛模拟考试(三十三) 题目名称 矩阵求值 中位数 过路费 程序文件名 Matrix.cpp median.cpp cost.cpp 输入文件名 Matrix.in median t.in cost.in 矩阵求值 【问题描述】 给定一个矩阵。你需要计算并输出 S=A^9*(A^1+A^2+…+A^k) 由于数字太大,你只需要输出 S 的每一项模 2012 的

值就可以了 给定一整数 k<=10^8, 矩阵规模<=30*30 Input 第一行 2 个整数 N,K 第二至第 N+1 行每行 N 个整数表示矩阵第 i-1 行的每一个元素 Output 输出如题目所示 Sample Input 11 1 Sample Output 1 Hint 【数据规模】 50% k<=100 100% k<=10^8, 矩阵规模<=30*30 [分析] 计算 S=A^1+A^2+...+A^k 令 X=A^1+A^2+...+A^(k/2) Ans=(A^(K/2)+E)*X if K is 奇数 then 快速幂 quickpow(A^K) else Ans #include <cstdio> #define MaxN 30 #define Mod 2012 struct Ac{int a[MaxN+5][MaxN+5];}; Ac src; int n, m; void Init() { scanf("%d %d", &n, &m); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { 输出文件名 Matrix.out median.out cost.out 时间、 内存 1s/256m 1s/256m 1s/256m 分值 100 100 100

scanf("%d", &src.a[i][j]); src.a[i][j] %= Mod; } return ; } inline Ac Quick_Power(Ac x, int y) { Ac ret, tmp; ret = x; y--; while (y) { if (y&1) { for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { tmp.a[i][j] = 0; for (int k=1; k<=n; k++) tmp.a[i][j] = ret.a[i][k]*x.a[k][j])%Mod; } ret = tmp; } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { tmp.a[i][j] = 0; for (int k=1; k<=n; k++) tmp.a[i][j] = x.a[i][k]*x.a[k][j])%Mod; } x = tmp; y = y>>1; } return ret; } inline Ac Dfs(int deep) { if (deep==1) return src; Ac ret, tmp; Ac tmp1 = Quick_Power(src, deep/2), tmp2 = Dfs(deep/2); for (int i=1; i<=n; i++) tmp1.a[i][i] = (tmp1.a[i][i] + 1)%Mod; for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {

(tmp.a[i][j]

+

(tmp.a[i][j]

+

tmp.a[i][j] = 0; for (int k=1; k<=n; k++) tmp.a[i][j] = (tmp.a[i][j] + tmp1.a[i][k]*tmp2.a[k][j])%Mod; } ret = tmp; if (deep&1) { tmp = Quick_Power(src, deep); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) ret.a[i][j] = (ret.a[i][j] + tmp.a[i][j])%Mod; } return ret; } Ac nine, ans; void Solve() { nine = Quick_Power(src, 9); ans = Dfs(m); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { int ret = 0; for (int t=1; t<=n; t++) ret = (ret + nine.a[i][t] * ans.a[t][j])%Mod; printf("%d ", ret); } putchar('\n'); } return ; } int main() { Init(); Solve(); getchar(); getchar(); return 0; } 中位数 【问题描述】 给出一个长度为 N 的非负整数序列 A[i],对于所有 1 ≤ k ≤ (N + 1) / 2,输出 A[1], A[2], …, A[2k - 1]的中位数。即前 1,3,5,……个数的中位数。 【输入文件】 输入文件 median.in 的第 1 行为一个正整数 N,表示了序列长度。 第 2 行包含 N 个非负整数 A[i] (A[i] ≤ 109)。

【输出文件】 输出文件 median.out 包含(N + 1) / 2 行,第 i 行为 A[1], A[2], …, A[2i – 1]的中位数。 【样例输入】 7 1 3 5 7 9 11 6 【样例输出】 1 3 5 6 【数据规模与约定】 对于 20%的数据,N ≤ 100; 对于 40%的数据,N ≤ 3000; 对于 100%的数据,N ≤ 100000。 [分析] 题目大意:对于一个序列 a[i],输出前 1 个,3 个,5 个,7 个……的中位数。维护一个最大 堆,一个最小堆。假设目前有 2*k+1 个元素,那么最大堆里装 k+1 个较小的数,最小堆中 装另外 k 个较大的数。那么最大堆中的首元素就是这 2*k+1 个元素的中位数。然后就是维 护的过程。读入一个数,如果大于等于 maxheap[1]就插入到 minheap 中,小于的话就与 maxheap[1]交换,把 maxheap[1]插入到 minheap 中,调整 maxheap;再读入一个数,这次插入 maxheap 中(如果比 minheap 大,就把 minheap[1]放到 maxheap,然后 minheap[1]变为新的 数,调整 minheap。小等于的话直接插入 maxheap) 。这样每次使得 maxheap[1]为所求。因 为维护堆的操作复杂度为 logn,所以很迅速就能出解。 #include<iostream> using namespace std; #define Maxn 100000 int Min_heap[Maxn+5], Max_heap[Maxn+5]; inline int Getint() { char c=getchar(); while(c<'0'||c>'9')c=getchar(); int ret=0; while(c>='0'&&c<='9') { ret=ret*10+(c-'0'); c=getchar(); } return ret; } void Max_heapup() { int i = Max_heap[0]; while(i>1 && Max_heap[i]>Max_heap[i/2]) swap(Max_heap[i],Max_heap[i/2]), i/=2; }

void Min_heapup() { int i = Min_heap[0]; while(i>1 && Min_heap[i]<Min_heap[i/2]) swap(Min_heap[i],Min_heap[i/2]), i/=2; } void Max_heapdown() { int i=1, j; while(i*2<=Max_heap[0]) { if(i*2==Max_heap[0] || Max_heap[i*2]>Max_heap[i*2+1]) j = 2*i; else j = i*2+1; if(Max_heap[i]<Max_heap[j]) swap(Max_heap[i],Max_heap[j]), i = j; else break; } } void Min_heapdown() { int i=1, j; while(i*2<=Min_heap[0]) { if(i*2==Min_heap[0] || Min_heap[i*2]<Min_heap[i*2+1]) j = 2*i; else j = i*2+1; if(Min_heap[i]>Min_heap[j]) swap(Min_heap[i],Min_heap[j]), i = j; else break; } } void Solve() { int N, x; scanf("%d%d", &N, &Max_heap[++Max_heap[0]]); printf("%d\n", Max_heap[1]); for (int i=2; i<=N; i++) { x = Getint(); if(x<Max_heap[1]) { Min_heap[++Min_heap[0]] = Max_heap[1]; Min_heapup(); Max_heap[1] = x; Max_heapdown(); } else Min_heap[++Min_heap[0]] = x, Min_heapup(); if(Min_heap[0]>Max_heap[0])

{ Max_heap[++Max_heap[0]] = Min_heap[1]; Max_heapup(); Min_heap[1] = Min_heap[Min_heap[0]--]; Min_heapdown(); } if(Max_heap[0]>Min_heap[0]+1) { Min_heap[++Min_heap[0]] = Max_heap[1]; Min_heapup(); Max_heap[1] = Max_heap[Max_heap[0]--]; Max_heapdown(); } if(i%2==1) printf("%d\n",Max_heap[1]); } } int main() { Solve(); getchar();getchar(); } .过路费 【问题描述】 在某个遥远的国家里,有 n 个城市。编号为 1,2,3,…,n。这个国家的政府修建了 m 条双向道 路,每条道路连接着两个城市。政府规定从城市 S 到城市 T 需要收取的过路费为所经过城 市之间道路长度的最大值。如:A 到 B 长度为 2,B 到 C 长度为 3,那么开车从 A 经过 B 到 C 需要上交的过路费为 3。 佳佳是个做生意的人, 需要经常开车从任意一个城市到另外一个城市, 因此他需要频繁地上 交过路费,由于忙于做生意,所以他无时间来寻找交过路费最低的行驶路线。然而,当他交 的过路费越多他的心情就变得越糟糕。作为秘书的你,需要每次根据老板的起止城市,提供 给他从开始城市到达目的城市,最少需要上交多少过路费。 【输入文件】 第一行是两个整数 n 和 m,分别表示城市的个数以及道路的条数。 接下来 m 行,每行包含三个整数 a,b,w(1≤a,b≤n,0≤w≤10^9) ,表示 a 与 b 之间 有一条长度为 w 的道路。 接着有一行为一个整数 q,表示佳佳发出的询问个数。 再接下来 q 行,每一行包含两个整数 S,T(1≤S,T≤n,S≠T), 表示开始城市 S 和目的 城市 T。 【输出文件】 输出文件共 q 行,每行一个整数,分别表示每个询问需要上交的最少过路费用。输入数据保 证所有的城市都是连通的。 【样例输入输出】 cost. cost.

in 45 1 2 10 1 3 20 1 4 100 2 4 30 3 4 10 2 14 41

out 20 20

【数据范围】 对于 30%的数据,满足 1≤ n≤1000,1≤m≤10000,1≤q≤100; 对于 50%的数据,满足 1≤ n≤10000,1≤m≤10000,1≤q≤10000; 对于 100%的数据,满足 1≤ n≤10000,1≤m≤100000,1≤q≤10000; 【题目大意】给定一个无向图。求任何一个点对(s,t)所有路径中最大边最小的那条路径,并 求出此时的最大边。询问非常多,要求快速计算。 【思路点拨】 一般多询问的问题要么是具有比较短的时间内可以在线获得答案, 要么是用很 多时间来处理然后用极短的时间来获得答案。 那我们先来想下在线算法。 【一般做法】求最大边最小? 二分!设最大边为 w,把<=w 的所有边重新构图,如果 s,t 连通,则 w 是一种符合的最大边。 二分这个最大边。我们可以求出该最大边的最小值。 复杂度 O(Q*(|V|+|E|)*log(|E|)) 可以过 50%的数据; 【一个定理】 定理:图 G 的(s,t)之间的最小最大边,一定是其在最小生成树中(s,t)的路径上的最大边。 证明:反证法,设(s,t)之间的最小最大边权值为 minW。 1.假设最小生成树中(s,t)的路径上的最大边 maxW<minW。 则跟 minW 是所有 s-t 路径的最小 值矛盾。 2.假设最小生成树中(s,t)的路径上的最大边 maxW>minW。则跟 maxW 是最小生成树的边矛 盾,因为在添加 maxW 之前 minW 已经添加了。 【方法 1】转成 LCA+RMQ 于是我们可以先构造出这个图的一棵最小生成树。 然后问他就转为求树上任意两点的最大边权 LCA+RMQ 【算法】求二叉树上任意两点的最短路径上的边权最大值 【问题】给出一棵树,每条边有一边权。对于任意给定的两点,求此两点的最短路径上边权 的最大值。 对于下图:

蓝圈中任意一点与红圈中任意一点的路径上的最大边必定是 8。 根据这个现象,可以把上述的树重建成如下图所示。 新图的叶子结点为原图的所有结点,内部结点为原图的边权,建边顺序为从小到大(需离散 化)。如图所示:

新图的红色编号为原图的结点编号,蓝色编号为原图的边。 这样,问题就转换为求新图中,任意两个叶子节点的最小公共祖先问题了。 【分析时间复杂度】 : 对于一棵树,n 个结点,m 条边,n=m-1。 1、对所有的边进行排序:O(mlgm); 2、建图采用并查集维护集合,并查集当前集合的根结点时间复杂度平均为 O(1),建图一共 要建立 n+m 个点,所以时间复杂度为 O(n+m); 3、查询任意两个结点的最近公共祖先,采用 RMQ 处理,预处理的时间复杂度为 O(n+m), 回答时间复杂度为 O(1); 所以,总的时间复杂度 O(nlogn)。 树上的倍增法求 LCA,掌握 #include<cstdlib> #include<cstdio> #include<cstring> const int maxn=11000,maxm=110000,logn=30; struct edge{int u,v,c;} e[maxm]; int E=1,n,q,m,i,x,y,fa[maxn],la[maxn][logn],Max[maxn][logn]; int point[maxm*2],next[maxm*2],len[maxm*2],fir[maxn],d[maxn]; bool f[maxn]; int CMP(const void *a,const void *b) {return ((edge*)a)->c-((edge*)b)->c;} int get(int x){if(fa[x]==x)return x;return fa[x]=get(fa[x]);} void add(int u,int v,int c){point[E]=v;next[E]=fir[u];len[E]=c;fir[u]=E++;} int maxi(int a,int b){return a>b?a:b;} /*la[i][j]表示从 i 点向上 1<<j 层的祖先。Max[i][j]表示从 i 点向上 1<<j 层的祖先的路径上的 最大边长,如 la[x][0]即为 x 的父亲 思想:任间一个区间都可表示成 2 的次方和的形式。同 ST 法

注意:祖先为 0 时表示该点不存在*/ void dfs(int x,int fa,int w,int deep){ d[x]=deep;f[x]=1;la[x][0]=fa;Max[x][0]=len[w]; for(int i=1;la[la[x][i-1]][i-1];i++){ /* x 向上 1<<j 层的祖先等于 x 向上 1<<(j-1)层的祖先的向上 1<<(j-1)层的祖先*/ la[x][i]=la[la[x][i-1]][i-1]; Max[x][i]=maxi(Max[x][i-1],Max[la[x][i-1]][i-1]); } for(int k=fir[x];k;k=next[k]) if(!f[point[k]])dfs(point[k],x,k,deep+1);//处理其子节点 } int ask(int x,int y){ int ans=0,i;if(d[x]>d[y]){int tmp=x;x=y;y=tmp;}//保证 y 的深度大 //y 上翻到与 y 同深度,这个深度差都可表示成 2 的次方和 for(i=logn-1;i>=0;i--)//最大为 2^(30-1) if(la[y][i]&&d[la[y][i]]>=d[x]){//y 的 i 祖先存在且深度大于 x ans=maxi(ans,Max[y][i]);y=la[y][i]; if(d[y]==d[x])break;//x,y 深度相等时终止 } if(x==y)return ans;//已找到了 lca for(i=logn-1;i>=0;i--) if(la[y][i]&&la[x][i]&&(la[y][i]!=la[x][i])){ /*x,y 的 2^i 祖先存在且不相等。 不相等的原因是防止到达其公共祖先的祖先点而返回 错误值*/ //x,y 同步向上翻,直到其 lca 的下一层 ans=maxi(ans,Max[y][i]);y=la[y][i]; ans=maxi(ans,Max[x][i]);x=la[x][i]; } //x,y 向再上一层即为 lca ans=maxi(ans,maxi(Max[y][0],Max[x][0])); return ans; } int main(){ freopen("cost.in","r",stdin); freopen("cost.out","w",stdout); scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c); for(i=1;i<=n;i++)fa[i]=i;qsort(e+1,m,sizeof(edge),CMP); for(i=1;i<=m;i++){ int p=get(e[i].u),q=get(e[i].v); if(p!=q){fa[p]=q;add(e[i].u,e[i].v,e[i].c);add(e[i].v,e[i].u,e[i].c);} } memset(f,0,sizeof(f)); dfs(1,0,0,1);scanf("%d",&q);

for(i=1;i<=q;i++){scanf("%d%d",&x,&y);printf("%d\n",ask(x,y));} return 0; } 【方法 2】 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int MaxN=20005,MaxM=100005; struct LinkType{int a,b,c;}; LinkType w[MaxM],e[MaxM],t[MaxN],q[MaxN],r[MaxN]; int he[MaxM],hq[MaxN],hr[MaxN]; int father[MaxN],mv[MaxN],mark[MaxN]; int ans[MaxN]; int N,M,Q,e0=0,q0=0,r0=0; void Addq(int x,int y,int z) { q0++; q[q0].a=y; q[q0].b=hq[x]; hq[x]=q0; q[q0].c=z;} void Adde(int x,int y,int z) { e0++; e[e0].a=y; e[e0].b=he[x]; he[x]=e0; e[e0].c=z;} void Addr(int x,int y) { r0++; r[r0].a=y; r[r0].b=hr[x]; hr[x]=r0;} void Read() { int i; scanf("%d%d",&N,&M); for(i=1;i<=M;i++) scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].c); scanf("%d",&Q); for(i=1;i<=Q;i++) { scanf("%d%d",&t[i].a,&t[i].b); Addq(t[i].a,t[i].b,i); Addq(t[i].b,t[i].a,i); } } void Qsort(int L,int R) { int i=L,j=R,Mid=w[(L+R)/2].c; while(i<=j) { while(w[i].c<Mid) i++; while(Mid<w[j].c) j--; if(i<=j) swap(w[i++],w[j--]); } if(L<j) Qsort(L,j); if(i<R) Qsort(i,R); } int Find(int x)

{ if(father[x]==x) return x; int fa=Find(father[x]); mv[x]=max(mv[x],mv[father[x]]); return father[x]=fa; } void Rebuild()//求最小生成树,并建立图 { int i,r1,r2; for(i=1;i<=N;i++)father[i]=i; Qsort(1,M); for(i=1;i<=M;i++) { r1=Find(w[i].a); r2=Find(w[i].b); if(r1!=r2) { father[r2]=r1; Adde(r1,r2,w[i].c); Adde(r2,r1,w[i].c); } } } void Tarjan(int x,int fa) { int i,y,r1,r2; father[x]=x;mv[x]=0; for(i=he[x];i;i=e[i].b) { y=e[i].a; if(y==fa)continue; Tarjan(y,x); father[y]=x;mv[y]=e[i].c; } mark[x]=1; for(i=hq[x];i;i=q[i].b) { y=q[i].a; if(mark[y])Addr(Find(y),q[i].c); } for(i=hr[x];i;i=r[i].b) { r1=t[r[i].a].a; r2=t[r[i].a].b; Find(r1); Find(r2); ans[r[i].a]=max(mv[r1],mv[r2]); } } void Solve() { Rebuild(); Tarjan(1,0);

for(int i=1;i<=Q;i++)printf("%d\n",ans[i]); } int main() { freopen("cost.in","r",stdin); freopen("cost.out","w",stdout); Read(); Solve(); return 0; } 【方法 3】 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009+10009; struct arr{int x,y,z;}e[maxn]; int dep[maxn],pre[maxn][22],fa[maxn],two[22],n,m,q,v[maxn]; struct cmp { bool operator ()(const arr p,const arr q) { return p.z < q.z; } }; void prep() { dep[n] = 1; for (int i=n-1; i>=1; i--) dep[i] = dep[pre[i][0]]+1; for (int i=0; i<20; i++) { for (int j=1; j<=n; j++) if (pre[pre[j][i]][i]) pre[j][i+1] = pre[pre[j][i]][i]; } } int iask(int x,int y) { while (x!=y) { if (dep[x] > dep[y]) { for (int i=20; i>=0; i--) if (two[i]<=dep[x]-dep[y]) { x = pre[x][i]; break; } }

else if (dep[y] > dep[x]) { for (int i=20; i>=0; i--) if (two[i]<=dep[y]-dep[x]) { y = pre[y][i]; break; } } else if (x != y) { for (int i=1; i<=20; i++) if (pre[x][i]==pre[y][i]) { x = pre[x][i-1]; y = pre[y][i-1]; break; } } } return x; } void conect(int x,int y) { pre[y][0] = x; } int find(int x) { if (fa[x]==x) return x; fa[x] = find(fa[x]); return fa[x]; } int main() { freopen("cost.in","r",stdin); freopen("cost.out","w",stdout); two[0] = 1; for (int i=1; i<=20; i++) two[i] = two[i-1]*2; scanf("%d%d\n",&n,&m); for (int i=1; i<=m; i++) scanf("%d%d%d\n",&e[i].x,&e[i].y,&e[i].z); sort(e+1,e+m+1,cmp()); for (int i=1; i<=n+m; i++) fa[i] = i; for (int i=1; i<=m; i++) { if (find(e[i].x)!=find(e[i].y)) { v[++n] = e[i].z; int x = find(e[i].x); int y = find(e[i].y);

fa[x] = n; fa[y] = n; conect(n,x); conect(n,y); } } prep(); scanf("%d\n",&q); for (int i=1; i<=q; i++) { int x,y; scanf("%d%d\n",&x,&y); int tmp = iask(x,y); printf("%d\n",v[tmp]); } return 0; }


相关文章:
NOIP冲刺模拟题
NOIP冲刺模拟题_学科竞赛_高中教育_教育专区。高 2016 信息学奥赛模拟考试(三十三) 题目名称 矩阵求值 中位数 过路费 程序文件名 Matrix.cpp median.cpp cost....
冲刺NOIP模拟试题与解析 提高组
冲刺NOIP 模拟试题与解析( 十一 ) 学校: 河南省焦作一中 出题人:刘晓刚 《NOI 导刊》 2011 年 9 月第 7 期 题目一览 题目 文件名 输入文件 输出文件 题目...
冲刺NOIP2010模拟试题15
冲刺NOIP2010模拟试题15_学科竞赛_初中教育_教育专区。冲刺 NOIP2010 模拟试题 15 题目 试题名称 程序文件名 输入文件名 输出文件名 时间限制 空间限制 中位数 med...
冲刺NOIP2010模拟试题与解析(一)
冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育_教育专区。...
冲刺noip2011模拟试题
冲刺NOIP 2011 模拟试题题目 失落的神庙 失落的猴子 被遗忘的时光 反素数 程序名 Losttemple Lostmonkey Losttime Antprime 输入文件名 Losttemple.in Lostmonkey....
冲刺模拟题10
冲刺NOIP2008模拟题十 4页 2财富值 【通用版】2012年备考冲刺... 暂无评价 7页 5财富值 初三数学中考冲刺模拟试卷... 8页 免费 高考冲刺物理模拟题10 2页 ...
冲刺NOIP2008模拟题十
冲刺NOIP2008模拟题十_IT认证_资格考试/认证_教育专区。冲刺 NOIP2008 模拟题十江苏省常州高级中学 曹文 题目 源程序名 输入文件名 输出文件名 测试点时限 字母转...
冲刺NOIP2010模拟试题
冲刺NOIP2010 模拟试题 模拟试题九 普及组) 冲刺 NOIP2010 模拟试题九(普及组)一、题目概览 中文名称 英文名称 可执行文件名 输入文件名 输出文件名 每个测试点...
冲刺模拟题13
7页 免费 冲刺NOIP2010模拟试题(十... 3页 免费喜欢此文档的还喜欢 广东省广雅...2012 年英语中考模拟试题(九)二、语言知识与运用(共两节,满分 20 分)第一节...
冲刺NOIP2008模拟题十一
冲刺NOIP2008模拟题十一_其它考试_资格考试/认证_教育专区。考试冲刺NOIP2008 模拟题十一 湖南省长沙市第一中学 曹利国 ★内存限制 64M,时限 1s 买彩票(tickt) 【...
更多相关标签:
noip模拟题 | noip初赛模拟题 | noip普及组初赛模拟题 | noip普及组复赛模拟题 | noip提高组模拟题 | noip复赛模拟题 | noip提高组复赛模拟题 | noip普及组模拟题 |