本文共 4749 字，大约阅读时间需要 15 分钟。

目录：

T1：mobitelT2：airshipT3：reuntionT4：house

USACO，永远滴神！

正题

T1：mobitel

题目描述

一只名叫马可的蚱蜢在草地上高兴地蹦跶。一不小心， 他的诺基亚3310掉进了水坑里。现在，他的手机变得很滑稽。键盘湿了，而且完全按照不可预测的方式按出不符的字符。所有的数字键都崩溃了。当我们按下其中某一个按钮时，就如同我们在按另一个键一样。幸运的是，没有两个键是相同的。所以，马可仍然可以拼写所有的字母。

马可正在一个一个地尝试，看看每个按键能按出什么字符。现在他想给他的女朋友发短信，可是，他被这个错乱的按键弄糊涂了，所以请你帮忙发短信。对于手机原来的按键，这里有一个简短的描述。

这是一个诺基亚手机的按键面板。该图像显示按键上（在没有落入水坑时的手机）可以获得的字母的键。例如，如果我们要获取字母‘a’，我们将按“2键”一次，如果我们想要字母‘b’，我们将按“2键”两次。如果我们想从同一个键连续写两个不同的字母，我们必须按‘#’间隔。例如，我们要写字符串“klor”，我们将要按键的顺序如下：“55#555666777”。

输入

第 1 行输入包含9个数字。

第一个整数表示 “键1”实际按出的数字，第二个整数表示“键2”实际按出的数字，第三个整数表示“键3”实际按出的数字，以此类推(且保证数字1~9，每个数字当且仅当出现一次)。因为他是一只蚱蜢，所以马可没有使用“*”和“0”键。“#”键没有坏掉。 第 2 行输入一个字符串S，由英文小写字母组成。

输出

输出共一行一个字符串，即输出马可的信息，你需要按键的数字序列。

样例输入

【输入样例1】

2 3 4 5 6 7 8 9 1klor

【输入样例2】

7 8 9 1 2 3 6 5 4djevojka

【输入样例3】

9 8 7 6 5 4 3 2 1skakavac

样例输出

【输出样例1】

44#444555666

【输出样例2】

68662227778#885

【输出样例3】

33335585582228#888

分析：

一道 简易的 字符串模拟题

CODE：

#include
   
    #include
    
     #include
     
      #include
      
        using namespace std;int a[10];string s;int before_num;int c[27]={
   0,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9}; //键位int sum[27]={
   0,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};//需要按的次数void init_(){
     //读入	for(int i=1;i<=9;i++){
   		int x;cin>>x;		a[x]=i;	}	cin>>s;}int main(){
   	freopen("mobitel.in","r",stdin);	freopen("mobitel.out","w",stdout);	init_(); 	for(int i=0;i
      
     
    
   

T2：airship

题目描述

2008年9月25日21点10分，酒泉卫星发射中心指控大厅里，随着指挥员一声令下，长征二号F型火箭在夜空下点火起飞，神舟七号飞船载着翟志刚、刘伯明、景海鹏3位航天员，在戈壁茫茫的深邃夜空中飞向太空，开始人类漫步太空之旅。第583秒，火箭以7.5公里／秒的速度，将飞船送到近地点200公里、远地点350公里的椭圆轨道入口。

而此时，火箭的燃料也消耗殆尽，即将以悲壮的方式与飞船告别。这个过程，在短短不到10分钟时间内，翟志刚和他的两名战友体会到了从超重到失重的过程。 除了超重和失重的感觉之外，就是浩瀚的长空中璀璨的星星，和地面上看到的星星不同，在太空中看到的星星是成一条直线的，一共N(1<=N<=100,000)颗星星，编号为1到N,每个星星有自己的体积。 由于在飞船中很无聊，除了不停地玩弄手中失重的书和笔之外没有别的事可干，此时翟志刚说我们来玩游戏吧，一共玩了M轮(1<=M<=100,000)，每一轮都是给出两个整数L和R(1<=L<=R<=N)，询问第L到第R颗星星之间最大星星的体积，每次答对的人就可以多休息一段时间。由于翟志刚还要进行太空漫步，所以他现在请你帮忙，你得到的回报就是太空饼干。

输入

第一行输入N,M 接下来一行N个整数，表示星星的体积(1<=体积<=maxlongint) 接下来M行，每行两个整数L_i,R_i,表示询问区间。

输出

输出M行，每一行表示询问区间L_i到R_i之间最大星星的体积。

样例输入

6 35 7 3 9 2 101 32 43 6

样例输出

7910

分析：

存星星的位置 星星体积从小到大排序 然后判断

符合区间就输出

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
         
        
       
      
     
    
   

T3：reuntion

题目描述

毕业20年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备发出邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的总花费最小。我们的主人公既不擅长数学，也不擅长计算机。他请你这个NOIP的高手帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。

输入

输入文件的每一行描述了一个城市的信息。（不超过10000个城市），首先是城里同学的个数（保证总人数在2^32范围内），紧跟着是这个城市到Moscow（起始点）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0，三个数据之间分别用空格隔开。

输出

输出聚会地点城市名称和旅程费用（单程），两者之间用一个空格隔开。每km花费1元人民币。总距离保证在2^64范围内。

样例输入

7 9289 Vladivostok5 8523 chabarovsk3 5184 Irkutsk8 2213 Yalutorovsk10 0 Moscow

样例输出

Yalutorovsk 112125

分析：

so……

直接求出每个地点的花费 然后根据花费排序 输出第一位 （也就是最小的一位 自己想）

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;struct node{
   	int distancE;  //距离	int stu;  //人数	string name;  //名字	int pay;  //花费}a[90001];int n=0;bool cmp(node x,node y){
   	if(y.pay==x.pay)  //花费一致按距离	{
   		return x.distancE
        
         >a[n].stu>>a[n].distancE>>a[n].name; if(a[n].name=="Moscow") break; //输入 } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { a[i].pay+=abs(a[j].distancE-a[i].distancE)*a[j].stu; //算出花费 } } sort(a+1,a+n+1,cmp); //排序 cout<
         
          <<" "<
         
        
       
      
     
    
   

T4：house

题目描述

奶牛们想建立一个新的城市。它们想建立一条长度为 Len 的主线大街，然后建立 K 条小街,每条小街的尽头有一间房子(小街的其它位置没有房子)。每条小街在主线大街的P_i 处分支, 小街的长度用L_i表示。FJ想知道最远的两个房子之间的距离是多少。

输入

第 1 行: 两个整数 Len 和K，意义如题目描述。

第2…K+1行: 每行两个整数P_i和L_i，对应着一条小街的信息。

输出

输出共一行一个整数，即最远的两个房子之间的距离。

样例输入

【输入样例1】

5 45 62 20 32 7

【输入样例2】

5 42 42 22 102 7

样例输出

【输出样例1】

16

【输出样例2】

17

分析：

一句话：排序，永远滴神！

普通的思路： ans(i,j)=l[i]+l[j]+abs(p[i]-p[j]) 做一遍从小到大的排序 即可去掉绝对值 ans(i,j)=l[i]+l[j]+p[i]-p[j] 然后合并一下： ans(i,j)=l[i]+p[i]+(l[j]-p[j]) 最后的答案就等于max(ans(i,j)） 要使答案最大 那么ans(i,j)就要尽可能大 可以解决一些多余的运算 不然本来60分

CODE：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int max1,max2,len,n;struct node{
   	int Bifurcations,l;} a[500010];void input(){
   	scanf("%d%d",&len,&n);	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].Bifurcations,&a[i].l);  //分叉与距离}bool cmp(node x,node y){
   	return x.Bifurcations