恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右
手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排
成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每
位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右
手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，
使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入输出格式
输入格式：&
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手
和右手上的整数。
输出格式：
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的
输入输出样例
输入样例#1：
输出样例#1：
【输入输出样例说明】
按 1、2、3 号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、3、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；
按 3、1、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。
【数据范围】
对于 20%的数据，有 1& n& 10，0 & a、b & 8；
对于 40%的数据，有 1& n&20，0 & a、b & 8；
对于 60%的数据，有 1& n&100；
对于 60%的数据，保证答案不超过 109；
对于 100%的数据，有 1 & n &1,000，0 & a、b & 10000。
NOIP 2012 提高组 第一天 第二题
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
二分不行，那就贪心了。
从头开始不方便，我就先从队伍最后的人开始。W=S/(A*B)
(A*B)最大的人排在最后好，所以按(A*B)小到大排序，扫描即可
[这样好像不太严谨，最大的不一定在最后]
还有一种贪心思路：
考虑相邻的两个人，交换位置只会影响到他们两个人，(A*B)小的人在前好
-------------------------------------------------------------------------
因为规模太大，所以要用高精度！！！
高精乘和高精除。
然后就开始&证明&我的基础有多弱，先用一种&把不存在的项置为-1&的方式写，调了4个小时还不好，就开始封装结构体
除法，我只会累减，貌似tle了
----------
我的代码，洛谷re，vijos50分，哎哎哎哎哎哎
----------------------------------------------update-23:28:48----------------------------------------
补了一下高精度除单精度，直接模拟行了，高精度除高精度才要减，我太弱智了
//关于高精
都是高精和低精 B取的低精最大值所以简化了一点
//小新chuInt--&B大g可能溢出
#include &iostream&
#include &cstdio&
#include &cstring&
#include &cmath&
#include &algorithm&
using namespace
const int N=1005,B=1e4,W=4,L=1005;
struct people{
int a,b,t;
bool cmp(people x,people y){
return x.t&y.t;
struct big{
int size,d[L];
big(int a=1):size(a){memset(d,0,sizeof(int)*L);}
bool bigger(big &a,big &b){
if(a.size&b.size) return true;
if(a.size&b.size) return false;
for(int i=a.size-1;i&=0;i++){
if(a.d[i]&b.d[i]) return true;
return false;
void copy(big &t,big &s){
memcpy(t.d,s.d,sizeof(int)*L);
void chengInt(big &a,int k){
int g=0,i;
for(i=0;i&a.i++){
int tmp=a.d[i]*k;
a.d[i]=(tmp+g)%B;
g=(tmp+g)/B;
a.d[i++]=g%B; a.size++;
void chuInt(big &a,int k){
for(int i=a.size-1;i&=0;i--){
g=g*B+a.d[i];
a.d[i]=g/k;
while(a.d[a.size-1]==0) a.size--;
//原来的弱智方法
//void chuInt(big &a,int k,big &ans){
while(noSmallInt(a,k))
{jianInt(a,k);addInt(ans,1);}
//void chuInt(big &a,int k,int &ans){
while(noSmallInt(a,k))
{jianInt(a,k);ans++;}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=0;i&=n;i++){scanf("%d%d",&p[i].a,&p[i].b); p[i].t=p[i].a*p[i].b;}
sort(p+1,p+n+1,cmp);
s.d[0]=p[0].a;
for(int i=1;i&=n;i++){for(int i=s.size-1;i&=0;i--)
copy(t,s);
chuInt(t,p[i].b);
if(bigger(t,mx)) copy(mx,t);
chengInt(s,p[i].a);
for(int i=mx.size-1;i&=0;i--){
if(i!=mx.size-1){
if(mx.d[i]&10) cout&&"000";
else if(mx.d[i]&100) cout&&"00";
else if(mx.d[i]&1000) cout&&"0";
cout&&mx.d[i];
阅读(...) 评论()NOIP2012&提高组&国王游戏
考虑交换相邻两个二元组的影响，交换i和i+1，实际上只影响到Fi和Fi+1。
设T&=&A1&*&A2&*&...&*&Ai-2&*&Ai-1
方案A：Fi&=&T&/&Bi，Fi+1&=T&*&Ai&/&Bi+1
方案B：Fi&=&T&/&Bi+1，Fi+1&=T&*&Ai+1&/&Bi
①假设1&/&Bi&＜&Ai&/&Bi+1，1&/&Bi+1&＜&Ai+1&/&Bi
那么方案A优于方案B&&&=&&&Ai&/&Bi+1&＜&Ai+1&/&Bi&&&=&&&Ai&*&Bi&＜&Ai+1&*&B&i+1
②假设1&/&Bi&≥&Ai&/&Bi+1&&=&&&Ai&*&Bi&≤&Bi+1
那么1&/&Bi&≤&Ai+1&/&Bi，方案A更优
③假设1&/&Bi+1&≥&Ai+1&/&Bi&&=&&&Ai+1&*&Bi+1&≤&Bi
那么1&/&Bi+1&≤&Ai&/&Bi+1，方案B更优
也就是说，对于相邻两个二元组，将A&*&B的较小的放在前面总能使答案更优。
已经按A&*&B排好序的方案为{1,2,3,4,...n}，发现可以通过一种构造，生成所有其他排列且保证结果更差。
设任意一种排列是{P1,P2,P3,P4....Pn}，称为目标序列。{1,2,3,4,...n}，称为原始序列。我们观察目标序列，从后往前，每
次将Pi从原始序列中往后交换直到它位于目标序列的位置。不难发现，序列在任意时刻都是由单调增的一段和排列好的一段组成，且每次交换都能保证结果更差。
综上，最优方案就是按A&*&B递增排序的方案，具体实现的时候需要加高精度处理。
这个做法的复杂度是O(NlogN+NL)。
& i,j,k,m,n,x,y,len:
& s,sa,sb:
& a,ans,c:array[1..10000]
& b:array[1..]
procedure qs(head,tail:longint);
var t,mid,i,j:
i:=j:=mid:=b[(head+tail)&&1,3];
while b[i,3]
&while b[j,3]&mid do dec(j);
&if i&=j then
&& t:=b[i,3];
&& b[i,3]:=b[j,3];
&& b[j,3]:=t;
&&&&&&&&&&
t:=b[i,1];
&& b[i,1]:=b[j,1];
&& b[j,1]:=t;
&&&&&&&&&&
t:=b[i,2];
&& b[i,2]:=b[j,2];
&& b[j,2]:=t;
&& inc(i);dec(j);
&& if head
procedure cheng(x:longint);
var i,j,k:
& for i:=1 to 10000 do
a[i]:=a[i]*x;
& for i:=1 to 9999 do
a[i+1]:=a[i+1]+a[i] div 10;
&a[i]:=a[i] mod 10;
function bijiao:
& for i:=10000 downto 1 do
&& if ans[i]&c[i] then
exit(false);
&& if c[i]&ans[i] then
exit(true);
& exit(false);
procedure dv(x:longint);
&& for i:=10000 downto 1 do
&& d:=d*10+a[i];
&& readln(n);
&& readln(x,y);a[1]:=x;
&& for i:=1 to n do
readln(b[i,1],b[i,2]);
b[i,3]:=b[i,1]*b[i,2];
&& qs(1,n);
&& len:=10000;
&& for i:=1 to n do
dv(b[i,2]);
if bijiao then
for j:=len downto 1 do ans[j]:=c[j];
&&&&&&&&&&&&
cheng(b[i,1]);
&& len:=10000;
(ans[len]=0)and(len&&1) do dec(len);
&& for i:=len downto 1 do
write(ans[i]);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。当前位置： >>
NOIP2012提高组day1
全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1CCF 全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1（请选手务必仔细阅读本页内容）一．题目概况中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 Vigenère 密码 vigenere vigenere vigenere.in vigenere.out 1秒 10 10 有 传统 国王游戏 game game game.in game.out 1秒 10 10 有 全文比较（过滤行末空格及文末回车） 传统 传统 开车旅行 drive drive drive.in drive.out 1秒 20 5 有二．提交源程序文件名对于 C++语言 对于 C 语言 对于 pascal 语言 vigenere.cpp vigenere.c vigenere.pas game.cpp game.c game.pas drive.cpp drive.c drive.pas三．编译命令（不包含任何优化开关）对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o vigenere vigenere.cpp -lm gcc-o vigenere vigenere.c -lm fpc vigenere.pas g++ -o game game.cpp -lm gcc-o game game.c -lm fpc game.pas g++ -o drive drive.cpp -lm gcc-o drive drive.c -lm fpc drive.pas四．运行内存限制内存上限 128M 128M 128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为：CPU Intel Core2 Quad QGHz, 内存 2G，上 述时限以此配置为准。 4、特别提醒：评测在 NOI Linux 下进行。第1页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day11．Vigenère 密码(vigenere.cpp/c/pas) 【问题描述】 16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法――Vigenère 密 码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为 南军所广泛使用。 在密码学中，我们称需要加密的信息为明文，用 M 表示；称加密后的信息为密文，用 C 表示； 而密钥是一种参数， 是将明文转换为密文或将密文转换为明文的算法中输入的数据， 记为 k。 在 Vigenère 密码中， 密钥 k 是一个字母串， 1k2…kn。 k=k 当明文 M=m1m2…mn 时， 得到的密文 C=c1c2…cn，其中 ci=mi?ki，运算?的规则如下表所示： ?Vigenère 加密在操作时需要注意： 1. ?运算忽略参与运算的字母的大小写，并保持字母在明文 M 中的大小写形式； 2. 当明文 M 的长度大于密钥 k 的长度时，将密钥 k 重复使用。 例如，明文 M=Helloworld，密钥 k=abc 时，密文 C=Hfnlpyosnd。 明文 密钥 密文 H a H e b f l c n l a l o b p w c y o a o r b s l c n d a d【输入】 输入文件名为 vigenere.in。 输入共 2 行。 第一行为一个字符串，表示密钥 k，长度不超过 100，其中仅包含大小写字母。第二行 为一个字符串，表示经加密后的密文，长度不超过 1000，其中仅包含大小写字母。第2页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1【输出】 输出文件名为 vigenere.out。 输出共 1 行，一个字符串，表示输入密钥和密文所对应的明文。 【输入输出样例】 vigenere.in CompleteVictory Yvqgpxaimmklongnzfwpvxmniytmvigenere.out Wherethereisawillthereisaway【数据说明】 对于 100%的数据，输入的密钥的长度不超过 100，输入的密文的长度不超过 1000，且 都仅包含英文字母。2．国王游戏(game.cpp/c/pas) 【问题描述】 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右 手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排 成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每 位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数，然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏， 所以他想请你帮他重新安排一下队伍的顺序， 使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。 【输入】 输入文件为 game.in。 第一行包含一个整数 n，表示大臣的人数。 第二行包含两个整数 a 和 b， 之间用一个空格隔开， 分别表示国王左手和右手上的整数。 接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手 和右手上的整数。 【输出】 输出文件名为 game.out。 输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的 金币数。第3页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1【输入输出样例】 game.in 3 1 2 7 4 1 3 4 6game.out 2【输入输出样例说明】 按 1、2、3 号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 2、3、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9； 按 3、1、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。 因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。 【数据范围】 对于 20%的数据，有 1≤ n≤ 10，0 & a、b & 8； 对于 40%的数据，有 1≤ n≤20，0 & a、b & 8； 对于 60%的数据，有 1≤ n≤100； 对于 60%的数据，保证答案不超过 109； 对于 100%的数据，有 1 ≤ n ≤1,000，0 & a、b & 10000。3．开车旅行(drive.cpp/c/pas) 【问题描述】 小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1 到 N 编号，且编号较小的 城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为 Hi ，城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即 d[i, j] = | ?
|。 旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划 选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 A 和小 B 的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿 着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离 相同，则认为离海拔低的那个城市更近） 。如果其中任何一人无法按照自己的原则选择目的 城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。 在启程之前，小 A 想知道两个问题： 1．对于一个给定的 X=X0，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶 的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷第4页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1大视为相等） 。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比 值都最小，则输出海拔最高的那个城市。 2. 对任意给定的 X=Xi 和出发城市 Si，小 A 开车行驶的路程总数以及小 B 行驶的路程 总数。 【输入】 输入文件为 drive.in。 第一行包含一个整数 N，表示城市的数目。 第二行有 N 个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N 的海 拔高度，即 H1，H2，……，Hn，且每个 Hi 都是不同的。 第三行包含一个整数 X0。 第四行为一个整数 M，表示给定 M 组 Si 和 Xi。 接下来的 M 行，每行包含 2 个整数 Si 和 Xi，表示从城市 Si 出发，最多行驶 Xi 公里。 【输出】 输出文件为 drive.out。 输出共 M+1 行。 第一行包含一个整数 S0，表示对于给定的 X0，从编号为 S0 的城市出发，小 A 开车行驶 的路程总数与小 B 行驶的路程总数的比值最小。 接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si 和 Xi 下小 A 行驶的里程总数和小 B 行驶的里程总数。 【输入输出样例 1】 drive.in 4 2 3 4 1 2 3 4 3 1 4drive.out 1 1 2 0 0 1 0 0 03 3 3 3【输入输出样例 1 说明】第5页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1各个城市的海拔高度以及两个城市间的距离如上图所示。 如果从城市 1 出发， 可以到达的城市为 2,3,4， 这几个城市与城市 1 的距离分别为 1,1,2， 但是由于城市 3 的海拔高度低于城市 2，所以我们认为城市 3 离城市 1 最近，城市 2 离城市 1 第二近，所以小 A 会走到城市 2。到达城市 2 后，前面可以到达的城市为 3,4，这两个城 市与城市 2 的距离分别为 2,1，所以城市 4 离城市 2 最近，因此小 B 会走到城市 4。到达城 市 4 后，前面已没有可到达的城市，所以旅行结束。 如果从城市 2 出发，可以到达的城市为 3,4，这两个城市与城市 2 的距离分别为 2,1，由 于城市 3 离城市 2 第二近，所以小 A 会走到城市 3。到达城市 3 后，前面尚未旅行的城市为 4，所以城市 4 离城市 3 最近，但是如果要到达城市 4，则总路程为 2+3=5&3，所以小 B 会 直接在城市 3 结束旅行。 如果从城市 3 出发，可以到达的城市为 4，由于没有离城市 3 第二近的城市，因此旅行 还未开始就结束了。 如果从城市 4 出发，没有可以到达的城市，因此旅行还未开始就结束了。 【输入输出样例 2】 drive.in 10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7drive.out 2 3 2 2 2 5 5 2 2 0 0 2 4 1 4 1 1 1 0 0 0【输入输出样例 2 说明】 当 X=7 时， 如果从城市 1 出发，则路线为 1 -& 2 -& 3 -& 8 -& 9，小 A 走的距离为 1+2=3，小 B 走的 距离为 1+1=2。 （在城市 1 时，距离小 A 最近的城市是 2 和 6，但是城市 2 的海拔更高，视 为与城市 1 第二近的城市， 所以小 A 最终选择城市 2； 走到 9 后， A 只有城市 10 可以走， 小 没有第 2 选择可以选，所以没法做出选择，结束旅行） 如果从城市 2 出发，则路线为 2 -& 6 -& 7 ，小 A 和小 B 走的距离分别为 2，4。 如果从城市 3 出发，则路线为 3 -& 8 -& 9，小 A 和小 B 走的距离分别为 2，1。 如果从城市 4 出发，则路线为 4 -& 6 -& 7，小 A 和小 B 走的距离分别为 2，4。 如果从城市 5 出发，则路线为 5 -& 7 -& 8 ，小 A 和小 B 走的距离分别为 5，1。 如果从城市 6 出发，则路线为 6 -& 8 -& 9，小 A 和小 B 走的距离分别为 5，1。 如果从城市 7 出发，则路线为 7 -& 9 -& 10，小 A 和小 B 走的距离分别为 2，1。 如果从城市 8 出发，则路线为 8 -& 10，小 A 和小 B 走的距离分别为 2，0。第6页 共7页全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1如果从城市 9 出发，则路线为 9，小 A 和小 B 走的距离分别为 0，0（旅行一开始就结 束了） 。 如果从城市 10 出发，则路线为 10，小 A 和小 B 走的距离分别为 0，0。 从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小， 但是城市 2 的海拔更高，所以输出第一行为 2。【数据范围】 对于 30%的数据，有 1≤N≤20，1≤M≤20； 对于 40%的数据，有 1≤N≤100，1≤M≤100； 对于 50%的数据，有 1≤N≤100，1≤M≤1,000； 对于 70%的数据，有 1≤N≤1,000，1≤M≤10,000； 对于 100%的数据， 1≤N≤100,000， 有 1≤M≤10,000， -1,000,000,000≤Hi≤1,000,000,000， 0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证 Hi 互不相同。第7页 共7页
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}