noip2013：noip2013题解

Day1：

1．转圈游戏

(circle.cpp/c/pas)

【问题描述】

n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给n 个位置编号，从 0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类 推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了 10k 轮，请问 x 号小伙伴最后走到了第几号位置。

 

【输入】

输入文件名为 circle.in。

输入共 1 行，包含 4 个整数 n、m、k、x，每两个整数之间用一个空格隔开。

 

【输出】

输出文件名为 circle.out。

输出共 1 行，包含 1 个整数，表示 10k 轮后 x 号小伙伴所在的位置编号。

 

【输入输出样例】

circle.in

10 3 4 5

circle.out

 5

【数据说明】

对于 30%的数据，0 < k < 7；

对于 80%的数据，0 < k < 10⁷；

对于 100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 10⁹。

快速幂（关于快速幂的详细解说将在即将发出的博客：数论总结。中有说明）： #include<cstdio>//快速幂 #include<algorithm>#include<cstring>using namespace std;long long n,m,k,x;int main(){freopen("circle.in","r",stdin);freopen("circle.out","w",stdout);scanf("%d %d %d %d",&n,&m,&k,&x);long long q=1,p=10;while(k>0){if(k%2!=0) q=(q*p)%n;k=k>>1;p=(p*p)%n;}x=(x+q*m)%n;printf("%d\n",x);return 0;}

2．火柴排队

(match.cpp/c/pas)

【问题描述】

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

 

【输入】

输入文件为 match.in。

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

 

【输出】

输出文件为 match.out。

输出共一行，包含一个整数，表示最少交换次数对 99,999,997取模的结果。

 

【输入输出样例 1】

match.in	match.out
4 2 3 1 4 3 2 1 4	1

【输入输出样例说明】

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

 

【输入输出样例 2】

match.in	match.out
4 1 3 4 2 1 7 2 4	2

【输入输出样例说明】

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

 

【数据范围】

对于 10%的数据， 1 ≤ n ≤ 10；

对于 30%的数据，1 ≤ n ≤ 100；

对于 60%的数据，1 ≤ n ≤ 1,000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2³¹− 1。

当了解了题目，可将问题转化为求交换相邻数字的长度。 典型的归并排序，从题目给出的公式我们可以证明到该题贪心的思路：用一个结构体记录每组的数据分别的编号和数值，分别按从小到大排序（可观察处按升序排列后对应两组数据的差值最小），排序后查找错位的点（即排序后两组对应数值编号不同的点），进行归并排序。 归并排序的大概思路：分别排序后合并排序。 #include<cstdio>//归并排序 #include<algorithm>#include<cstring>using namespace std;const int maxn=100005;const long long mod=99999997;struct node{int u,v;//记录位置和高度 }a[maxn],b[maxn],f[maxn]; //f记录第i个数移动后的位置 long long sb[maxn];long long n;long long ans=0;bool compare1(node a,node b){return a.v<=b.v;}bool compare2(node a,node b){return a.v>=b.v;}void work1(int y)//计算错位的个数 {//printf("y=%d\n",y);for(int i=y;i<=n;i+=i&-i)//如果i是奇数，变成偶数 {sb[i]++;//printf("i=%d sb=%d\n",i,sb[i]);}}int work2(int a){int ans=0;for(int i=a;i>=1;i-=i&-i){ans+=sb[i];//printf("%d\n",ans);}return ans;}int main(){freopen("match.in","r",stdin);freopen("match.out","w",stdout);scanf("%d",&n);for(long long i=1;i<=n;i++){scanf("%lld",&a[i].v);a[i].u=i;}for(long long i=1;i<=n;i++){scanf("%lld",&b[i].v);b[i].u=i;}for(int i=1;i<=n;i++){f[i].u=i;}sort(a+1,a+n+1,compare1);sort(b+1,b+n+1,compare1);for(int i=1;i<=n;i++){f[a[i].u].v=b[i].u;//printf("%d",f[a[i].u].v);//}sort(f+1,f+1+n,compare2);//不排序的话答案是错的= =woc for(int i=1;i <=n;i++){work1(f[i].u);ans+=work2(f[i].u-1);//printf("%d\n",f[i].u-1);//printf("%d\n",ans);ans=ans%mod;}printf("%d",ans);return 0;}

3．货车运输

(truck.cpp/c/pas)

【问题描述】

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

 

【输入】

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有n 座城市和 m 条道路。

接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市 运输货物到 y 城市，注意：x 不等于 y。

 

【输出】

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

 

【输入输出样例】

truck.in	truck.out
4	3		3
1	2	4	-1
2	3	3	3
3	1	1
3
1	3
1	4
1	3

 

【数据说明】

 

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

最大生成树加最近公共祖先。

#include<cstdio>#include<algorithm>using namespace std;/* 更新： 一个是f数组的更新：f[i][j]=f[f[i][j-1]][j-1]； 一个是g数组的更新：g[i][j]=min(g[i][j-1],g[f[i][j-1][j-1]) （因为i结点的2^j的祖先节点就是i的2^（j-1）的祖先节点的2^(j-1)的祖先节点） 过程： 将两个点调到同一深度（将深度大的），当x==y是就可返回值ans */int n,m,q;int deep[100001];//i节点的深度int f[100001][32];//i节点的2^j的父亲节点int g[100001][32];//i节点到2^j祖先的最短小边；struct node{int u,v,w;}e[100001];int father[100001];int s[100001];int t[100001];int ans[100001];int head[100001];int k=0;struct node1{int to,next,value;}e1[500001];bool cmp(node e1,node e2){return e1.w>e2.w;//求最大按降序排列 }int find(int x)//找祖先{if(father[x]==x)return x;else return father[x]=find(father[x]);}void add(int u,int v,int w){k++;e1[k].to=v;e1[k].value=w;e1[k].next=head[u];head[u]=k;}int dfs(int x,int sum)//最近公共祖先查找 (起点是终点的父亲){deep[x]=sum;for(int i=1;i<=14;i++)//初始 {f[x][i]=f[f[x][i-1]][i-1];g[x][i]=min(g[f[x][i-1]][i-1],g[x][i-1]);}int p1=head[x];while(p1){if(deep[e1[p1].to]==0){f[e1[p1].to][0]=x;//该节点已无儿子= =，所以x是他的祖先g[e1[p1].to][0]=e1[p1].value;dfs(e1[p1].to,sum+1);}p1=e1[p1].next;}}int work(int x,int y)//最短路 {if(deep[x]>deep[y])//默认x的深度比y小1，所以进行一个判定 {int temp=x;x=y;y=temp;}int minn=2100000000;for(int i=14;i>=0;i--)//把一个较深的点向上提，并记录他到祖先的最小距离{if(deep[x]<=deep[f[y][i]]){minn=min(g[y][i],minn);y=f[y][i];}}if(x==y)return minn;for(int i=14;i>=0;i--){if(f[x][i]!=f[y][i]){minn=min(min(g[x][i],g[y][i]),minn);//查找最短路 x=f[x][i];y=f[y][i];}}minn=min(min(g[x][0],g[y][0]),minn);return minn;}void read(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);}for(int i=1;i<=n;i++){father[i]=i;//父节点初始 }int cnt=0;sort(e+1,e+m+1,cmp);for(int i=1;i<=m;i++){int fx=find(e[i].u);int fy=find(e[i].v);if(fx!=fy){father[father[e[i].u]]=father[e[i].v];cnt++;add(e[i].u,e[i].v,e[i].w);add(e[i].v,e[i].u,e[i].w);}if(cnt==n-1)break;}for(int i=1;i<=n;i++){if(deep[i]==0)dfs(i,1);}scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%d",&s[i],&t[i]);if(find(s[i])!=find(t[i]))ans[i]=-1;elseans[i]=work(s[i],t[i]);printf("%d\n",ans[i]);}}int main(){//freopen("truck.in","r",stdin);//freopen("truck.out","w",stdout);read();return 0;}/*4 31 2 42 3 33 1 131 31 41 33-13*/

Day2：

1．积木大赛

(block.cpp/c/pas)

【题目描述】

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是ℎi。

在搭建开始之前，没有任何积木（可以看成块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块到第R块之间（含第 L 块和第 R 块）所有积木的高度分别增加1。

小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

 

【输入】

输入文件为 block.in

输入包含两行，第一行包含一个整数n，表示大厦的宽度。

第二行包含n个整数，第i个整数为ℎi。

 

【输出】

输出文件为 block.out

仅一行，即建造所需的最少操作数。

 

【输入输出样例】

block.in	block.out
5 2 3 4 1 2	5

 

 

【样例解释】

其中一种可行的最佳方案，依次选择

[1,5]   [1,3]  [2,3]   [3,3]   [5,5]

 

【数据范围】

对于 30%的数据，有1 ≤ n ≤ 10；

对于 70%的数据，有1 ≤ n ≤ 1000；

对于 100%的数据，有1 ≤ n ≤100000，0 ≤ hi ≤ 10000。
#include<cstdio>//二分思想的暴力= = #include<algorithm>#include<cstring>using namespace std;const int maxn=100005;const int inf=0x7f7f7f;int n;int h[maxn];int ans;int minn;bool visit[maxn];void work(int l,int r){if(l>r) return;minn=inf;for(int i=l;i<=r;i++){if(visit[i]==false){minn=min(minn,h[i]);}}if(minn==inf) return;//ans+=minn;for(int i=l;i<=r;i++) h[i]-=minn;//for(int i=l;i<=r;i++){if(visit[i]==false&&h[i]==0){visit[i]=true;work(l,i-1);work(i+1,r);}}return ;}int main(){freopen("block.in","r",stdin);freopen("block.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&h[i]);}memset(visit,false,sizeof(visit));work(1,n);printf("%d",ans);return 0;}

2．花匠

(flower.cpp/c/pas)

【问题描述】

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数ℎ1, ℎ2, … , ℎn。设当一部分花被移走后，剩下的花的高度依次为g₁,g₂,… , g_m，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的1≤i≤，有g_2i >g_2i-1，同时对于所有的1≤i≤，有g_2i >g_2i+1；

条件 B：对于所有的1≤i≤，有g_2i < g_2i-1，同时对于所有的1≤i≤，有g_2i <g_2i+1。

注意上面两个条件在 m = 1时同时满足，当 m> 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

 

【输入】

输入文件为 flower.in。

输入的第一行包含一个整数，表示开始时花的株数。

第二行包含个整数，依次为ℎ1, ℎ2, … , ℎn，表示每株花的高度。

 

【输出】

输出文件为 flower.out。

输出一行，包含一个整数，表示最多能留在原地的花的株数。

 

【输入输出样例】

flower.in	flower.out
5 5 3 2 1 2	3

 

【输入输出样例说明】

有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。

 

【数据范围】

对于 20%的数据，n ≤ 10；

对于 30%的数据，n ≤ 25；

对于 70%的数据，n ≤ 1000，0 ≤ ℎn≤ 1000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ ℎn≤ 1,000,000，所有的ℎn随机生成，所有随机数服从某区间内的均匀分布。

贪心加动归： 开始忘了加h[i]==h[i-1] 的情况，所以WA了2个点。 #include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn=100005;int n;int h[maxn];int dp[maxn][2];void work(){ for(int i=1;i<=n;i++) { dp[i][0]=dp[i-1][0]; if(i==1||h[i]<h[i-1]) { dp[i][0]=max(dp[i-1][0],dp[i-1][1]+1); }dp[i][1]=dp[i-1][1]; if(i==1||h[i]>h[i-1]) { dp[i][1]=max(dp[i-1][1],dp[i-1][0]+1); } }}int main(){freopen("flower.in","r",stdin);freopen("flower.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&h[i]);}work();printf("%d\n",max(dp[n][0],dp[n][1]));return 0;}