NOIP2014普及组，提高组 比例简化 飞扬的小鸟 答案

比例简化

说明

在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498 人，反对的有 902人，那么赞同与反对的比例可以简单的记为1498:902。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’ ≥ A/B且A’/B’ - A/B的值尽可能小。

输入格式

输入共一行，包含三个整数A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。

输出格式

两个整数A’，B’，中间用一个空格隔开，表示化简后的比例。

样例

输入数据 1

1498 902 10

Copy

输出数据 1

5 3

Copy

提示

【数据说明】
对于100%的数据，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100，A/B ≤ L。
【来源】

NOIP2014普及组复赛第2题。

#include<bits/stdc++.h>
using namespace std;
int A,B,L,a,b;
int isz(int x,int y) {//辗转相除，画一画就明白了if(y==0)return x;return isz(y,x%y);
}
int main() {cin>>A>>B>>L;a=L;b=1;//定为最大值for(int i=1; i<=L; i++)//L小于100穷举for(int j=1; j<=L; j++) {//求A/B<=i/j<=a/bbool bz=(isz(i,j)==1);//判断互质bool bd=((A*j)<=(B*i));//判断是否大于（解释：原来是A/b<=i/j但会有精度问题，等式性质转换上去）bool bj=((a*j)>(b*i));//是否更接近A/B本为a/b>i/j但会有精度问题，等式性质转换上去//cout<<"i= "<<i<<" j= "<< j<<" "<<bz<<" "<<bd<<" "<<bj<<endl;if(bz==1&&bd==1&&bj==1)a=i,b=j;//dev性质&&情况默认是0，大服}cout<<a<<" "<<b;return 0;
}

[NOIP2014 提高组] 飞扬的小鸟

说明

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 $n$，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 $1$，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。

小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 $1$ 行有 $3$ 个整数 $n,m,k$，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 $n$ 行，每行 $2$ 个用一个空格隔开的整数 $x$ 和 $y$，依次表示在横坐标位置 $0\sim n-1$ 上玩家点击屏幕后，小鸟在下一位置上升的高度 $x$，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 $y$。

接下来 $k$ 行，每行 $3$ 个整数 $p,l,h$，每两个整数之间用一个空格隔开。每行表示一个管道，其中 $p$ 表示管道的横坐标，$l$ 表示此管道缝隙的下边沿高度，$h$ 表示管道缝隙上边沿的高度（输入数据保证 $p$ 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 $1$，否则输出 $0$。

第二行，包含一个整数，如果第一行为 $1$，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

样例

输入数据 1

10 10 6 
3 9  
9 9  
1 2  
1 3  
1 2  
1 1  
2 1  
2 1  
1 6  
2 2  
1 2 7 
5 1 5 
6 3 5 
7 5 8 
8 7 9 
9 1 3 

Copy

输出数据 1

1
6

Copy

提示

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

【数据范围】

对于 $30\%$ 的数据：$5\le n\le 10,5\le m\le 10,k=0$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $50\%$ 的数据：$5\le n\le 20,5\le m\le 10$，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $70\%$ 的数据：$5\le n\le 1000,5\le m\le 100$；

对于 $100\%$ 的数据：$5\le n\le 10000$，$5\le m\le 1000$，$0\le k<n$，$0<x,y<m$，$0<p<n$，$0\le l<h\le m$，$l+1<h$。

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define gc(a) a=getchar()
#define pc(a) putchar(a)
ll read(){char c;ll x=0;bool flag=0;gc(c);while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);}return flag?-x:x;
}
void pr(ll x){if(x<0){x=-x;pc('-');}if(x>9) pr(x/10);pc(x%10+48);
}
//-------快读------
#define inf 0x3f3f3f3f
const ll maxn=10005;
const ll maxm=10005;
struct node
{ll id,h,l;bool operator <(const node &a) const{return id<a.id;}
}o[maxn];
ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans;
int main()
{//memset(dp,inf,sizeof(dp));//两个被遗忘的初始化之一qwqn=read(),m=read(),k=read();for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();for(int i=1;i<=k;i++)o[i].id=read(),o[i].l=read(),o[i].h=read();sort(o+1,o+k+1);//管道id排序!//for(int i=1;i<=m;i++)//dp[0][i]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)//注意要初始化！dp[i%2][j]=inf;for(int j=x[i]+1;j<=x[i]+m;j++)//p=1，完全背包dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1);for(int j=m+1;j<=x[i]+m;j++)//比m大的都是mdp[i%2][m]=min(dp[i%2][m],dp[i%2][j]);for(int j=1;j<=m-y[i];j++)//p=0，01背包dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]);if(i==o[cnt].id)//如果这个地方有管道{ans=inf;//主要每次都要初始化一次！for(int j=0;j<=o[cnt].l;j++)dp[i%2][j]=inf;for(int j=o[cnt].h;j<=m;j++)dp[i%2][j]=inf;for(int j=1;j<=m;j++)//寻找是否可以通过ans=min(dp[i%2][j],ans);if(ans==inf){pr(0);pc('\n');pr(cnt-1);return 0;}cnt++;}}ans=inf;//注意要初始化！for(int j=1;j<=m;j++)ans=min(dp[n%2][j],ans);pr(1);pc('\n');pr(ans);return 0;
}