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

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; }


相关文章:
NOIP2015年初赛提高组模拟试题
NOIP2015年初赛提高组模拟试题_学科竞赛_高中教育_教育专区。信息学初赛模拟试题 一、 选择题 (共 20 题, 每题 1.5 分, 共计 30 分。 前 10 题为单选题;...
NOIP冲刺2010试题三
NOIP 冲刺 2010 试题三; 第一题:abbreviate; 【题目描述】 ;最近情报人员得到了一些经过加密的文章,每个单词都; 解释: “字符串 s1 是 s2 的前缀”是说把...
NOIP复赛模拟题
NOIP复赛模拟题_工学_高等教育_教育专区。2006年的旧东西了 Noip2006 复赛模拟题 NOIP2006 复赛模拟题(普及组水平) (时间:3 小时)注意事项: 1. 严格按照题目...
冲刺NOIP2010模拟试题与解析(一)
冲刺NOIP2010模拟试题与解析(一)_公务员考试_资格考试/认证_教育专区。冲刺NOIP2010模拟试题与解析(一)模拟试题与解析 试题与解析( 冲刺 NOIP2010 模拟试题与解析(...
冲刺模拟题13
7页 免费 冲刺NOIP2010模拟试题(十... 3页 免费喜欢此文档的还喜欢 广东省广雅...2012 年英语中考模拟试题(九)二、语言知识与运用(共两节,满分 20 分)第一节...
noip普及组初赛模拟试卷(附答案)
noip普及组初赛模拟试卷(附答案)_学科竞赛_初中教育_教育专区。选择一个正确答案...故本题答案为 D9H。 4. 下列关于数组的叙述,正确的是 (D)。 A.下标是...
冲刺NOIP2010模拟试题二
冲刺NOIP2010模拟试题与解... 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
冲刺NOIP2012模拟试题(十四)
NOIP2012模拟试题(六) 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP2012模拟试题(十四) NOI导刊上的...
冲刺NOIP2008模拟题12
冲刺NOIP2008 模拟题 12 湖北省宜昌市第一中学 陈凡 (提高组复赛三小时完成) 1、回文词(words.pas/c/cpp) 【问题描述】 CR 喜欢研究回文词,有天他发现一篇...
冲刺NOIP2010模拟试题与解析(十五)
冲刺NOIP2010模拟试题与解析(十五)_IT/计算机_专业资料。冲刺NOIP2010模拟试题与解析(十五)NOIP 提高组复赛模拟题(一) 提高组复赛模拟题 组复赛模拟题(题目 试题名...
更多相关标签:
noip模拟题 | noip初赛模拟题 | 小升初语文冲刺模拟题 | noip动态域名注册 | noip吧 | noip2015 | noip2016 | noip2015普及组复赛 |