| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 42026 人关注过本帖, 47 人收藏
标题:C论坛算法团队 首战 西安电子科技大学OJ
只看楼主 加入收藏
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
在曹哥的帮助下终于AC了,基本功不扎实啊。非常感谢~~~


Problem 1209 - 破译电话号码
Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 132  Accepted: 33  Special Judge: No
Description
在已经过去了的某一天,优酷视频上一位记者报道了360和百度的搜索战,视频中有这位记者用电话拨打360董事长周鸿祎手机的情节,一位蛋疼的大学生把其中电话拨号的录音给截取下来,通过音频分析得到了周鸿祎的电话号码。
                   下面是音频分析的原理(来自微博):
                   我们平常所用的电话,是通过DTMF信号来向交换机传递命令的,我们每按下电话键盘上的一个键,就会同时发出两个不同频率的声音,转化成电流在对面解析(可以回忆柯南剧场版中通过唱歌拨打电话)。也就是说,记者每按下的每个键的声音,实际上是由两个纯粹的音(tone)构成的,通过下面可以看到每个数字由哪两个频率的声音构成。

 
                   假设你是这位破译电话号码的大学生,你已经得出了每个按键音的两个频率,请你告诉大家这些频率代表的字符或者数字。
Input
多组数据,每组数据三行,第一行一个整数N(100000>=N>0)代表已经得到的按键音的个数,第二行N个整数,在这一行中,第i个整数代表第i个按键音的高音。第三行N个整数,在这一行中,第i个整数代表第i个按键音的低音。
输入N=0,代表输入结束。
Output
对于每组数据,输出N个字符或数字,代表破译后的字符或数字,按照输入给出的顺序输出,每行23个字符或数字。
Sample Input
3
1209 1209 1336
697 697 941
3
1336 1336 1336
770 697 941
0
Sample Output
110
520
Hint
Source
zjy

程序代码:
#include <iostream>
#define N 100000
using namespace std;

typedef struct
{
    int x,y;
}Code;

char f(int x,int y)
{
    if(x+y == 2277)         return '0';
    else if(x+y == 1906)    return '1';
    else if(x+y == 2033)    return '2';
    else if(x+y == 2174)    return '3';
    else if(x+y == 1979)    return '4';
    else if(x+y == 2106)    return '5';
    else if(x+y == 2247)    return '6';
    else if(x+y == 2061)    return '7';
    else if(x+y == 2188)    return '8';
    else if(x+y == 2329)    return '9';
    else if(x+y == 2330)    return 'A';
    else if(x+y == 2403)    return 'B';
    else if(x+y == 2485)    return 'C';
    else if(x+y == 2574)    return 'D';
    else if(x+y == 2150)    return '*';
    else    return '#';
}

int main()
{
    int n,i;
    Code code[N];
    while(cin>>n && n)
    {
        for(i=0;i<n;++i)    cin>>code[i].x;
        for(i=0;i<n;++i)    cin>>code[i].y;
        for(i=0;i<n;++i)   
        {
            if (i!=0 && i%23==0) cout<<endl;
            cout<<f(code[i].x,code[i].y);
        }
        cout<<endl;
    }
    return 0;
}



[ 本帖最后由 C_戴忠意 于 2012-12-23 18:42 编辑 ]

编程之路定要走完……
2012-12-21 16:52
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
你这程序无法处理n超过23的情况啊
2012-12-21 22:54
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
回复 119楼 czz5242199
昂,我好像明白了。Thanks!

编程之路定要走完……
2012-12-22 13:33
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
刚考完六级回来

Problem 1201 - An Unfair Game
n个人分配n个target,每个人对于每个target都有一个对应的完成时间,你要计算给第m个人分配哪些任务使得他有可能是最后一个完成的

枚举所有任务,如果让第m个人做第i个任务,那么其他人都只能做时间<map[m][i]的任务(这样他就是最后一个完成的了),建立一个二分图,计算能否匹配即可,而且这题会卡常数,一定匹配不上就要中断,否则会超时


程序代码:
#include <iostream>
#define N 100
using namespace std;

int map[N][N],new_map[N][N],v[N],l[N],n,m;

int find(int p)
{
    for (int i=0; i<n; i++)
      if (new_map[p][i] && !v[i])
      {
                        v[i]=1;
                        if (l[i]==-1 || find(l[i]))
                        {
                                     l[i]=p; 
                                     return 1;
                        }
      }
    return 0;
}

int f()
{
    int ans=0;
    for (int i=0; i<n; i++) l[i]=-1;
    for (int i=0; i<n; i++)
    if (i!=m)
    {
        for (int j=0; j<n; j++) v[j]=0;
        if (!find(i)) return 0;
    }
    return 1;
}

int main()
{
    while (cin>>n)
    {
          int flag=1;
          for (int i=0; i<n; i++)
            for (int j=0; j<n; j++) cin>>map[i][j];
          cin>>m;
          m--;
          
          for (int i=0; i<n; i++)
          {
              for (int k=0; k<n; k++)
                for (int j=0; j<n; j++)
                  if (k!=m && j!=i && map[k][j]<map[m][i]) new_map[k][j]=1; else new_map[k][j]=0;
              
              if (f()) 
              {
                            if (flag) cout<<i+1; else cout<<' '<<i+1;
                            flag=0; 
              }
          }
          if (flag) cout<<-1;
          cout<<endl;
    }
}
    
2012-12-22 18:05
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1040 - Banner
小戴的建议也不错,不过先把这题发上来。
Problem 1040 - Banner

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 4  Accepted: 4  Special Judge: No


Description


    Bessie is returning from a long trip abroad, and Farmer John wantsto erect a nice "Welcome Home" banner in her pasture for her arrival.The banner will hang between two poles on a wire whose length isin the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).

    The pasture's size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and Farmer John has installed a post at every point with integer coordinates. Of these (W + 1) * (H + 1) points, Farmer John must pick just two that will hold either end of the wire from which he will hang the banner.

    FJ wants no interference with his banner as it hangs and requires that no post be directly under the tight wire he stretches between the two chosen posts.

    Farmer John needs your help to figure out how many possible ways he can hang the banner. He knows the number is large and that a 32-bit integer might not be sufficient to compute the answer.

   Consider the example pasture below, with W = 2 and H = 1:

       * * *

       * * *

    The banner size is in the range 2..3. This pasture contains (2+1)* (1+1) = 6 points and has (6 take 2) = (6*5)/(2*1) = 15 different potential pairs of points between which the banner-holding wire might stretch:

   (0,0)-(0,1)   (0,0)-(2,1)   (0,1)-(2,1)   (1,1)-(2,0)

   (0,0)-(1,0)   (0,1)-(1,0)   (1,0)-(1,1)   (1,1)-(2,1)

   (0,0)-(1,1)   (0,1)-(1,1)   (1,0)-(2,0)   (2,0)-(2,1)

   (0,0)-(2,0)   (0,1)-(2,0)   (1,0)-(2,1)

    Of these pairs, only four have a length in the range 2..3:

                     Len                       Len

        (0,0)-(2,0) 2.00          (0,1)-(2,0) 2.24

        (0,0)-(2,1) 2.24          (0,1)-(2,1) 2.00

    Of these four, the pairs (0,0)-(2,0) and (0,1)-(2,1) both have a post directly on the line between the endpoints, and thus are unsuitable.

    So, just two pairs of points out of 15 are acceptable candidates for hanging the banner wire.

Input

Line 1: Four space-separated integers: W, H, L1, and L2


Output

Line 1: A single integer denoting the number of possible banners


Sample Input

2 1 2 3


Sample Output

2


Hint


Source

USACO NOV10 SILVER
分析
好久不见奶牛贝斯和农夫约翰了,呵呵这可是USACO里很出名的故事人物。
 
在 W x H 的农场里找两个点,使得它们的距离介于L1与L2之间,而且它们的连线上不能有其它点。问这样的点对有多少。
 
如果把这两个点当做一个矩形的对角线,那问题就转化成在农场里可以划出多少个矩形。
 
而要求这个矩形的对角线上没有其它点,既是要求矩形的两边是互质的。
程序代码:
#include<stdio.h>
long long cal(int W, int H, int L1, int L2)
{
    long long c;
    int i, j, di, d, t, t1, t2;
    c = L1 == 1 ? W * H * 2 + W + H : 0;
    L1 *= L1;
    L2 *= L2;
    for(di = i = 1; i <= W; di += (++i << 1) - 1)
    for(d = di + (j = 1); j <= H && d <= L2; d += (++j << 1) - 1)
    {
        if(d < L1) continue;
        for(t1 = i, t2 = j; t = t1 % t2; t1 = t2, t2 = t);
        if(t2 == 1) c += (W - i + 1) * (H - j + 1) << 1;
    }
    return c;
}

int main()
{
    int W, H, L1, L2;
    scanf("%d%d%d%d", &W, &H, &L1, &L2);
    printf("%lld\n", cal(W, H, L1, L2));
    return 0;
}


[ 本帖最后由 beyondyf 于 2012-12-22 20:45 编辑 ]

重剑无锋,大巧不工
2012-12-22 20:44
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
顺便总结一下到现在已经完成的题目

1001 1002 1003 1004 1005 1006 1007 1008 1009 1010

1011 1012 1013 1014 1015 1016 1017 1018 1019 1020

1021 1022 1023 1024 1025 1026 1027 1028 1029 1030

1031 1032 1033 1034 1035 1036 1037 1038 1039 1040

1043 1049

1053 1054 1055

1061 1069

1076

1103 1109

1121 1130

1178

1201 1206 1207 1209

重剑无锋,大巧不工
2012-12-22 20:48
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
Problem 1205 - Binary Numbers
顺序找第m个含有n个1的二进制数

考虑一个i位的二进制数,含有n个1就有C(i,n)中可能性,如果C(i,n)<m,那么肯定不止i位,所以我们找到第一个i使得C(i,n)>=m,那么第i位就是这个数的最高位,而且问题可以转化为寻找第m-C(i-1,n)个n-1个1的数,同样一直处理即可


程序代码:
#include <iostream>
using namespace std;

int ans[5000],c[5000][11],m,n;

int main()
{
    c[0][0]=1;
    for (int i=1; i<5000; i++)
    {
        c[i][0]=1;
        for (int j=1; j<=10; j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    
    cin>>m;
    while (cin>>m>>n)
    {
          if (n==1)
          {
                   cout<<1;
                   for (int i=0; i<m-1; i++) cout<<0;
                   cout<<endl;
                   continue;
          }
          int flag=0;
          for (int i=0; i<5000; i++) ans[i]=0;
          for (int i=n; i>0; i--)
          {
              int j=1;
              while (c[j][i]<m) j++;
              if (flag==0) flag=j;
              ans[j-1]=1;
              m-=c[j-1][i];
          }
          for (int i=flag-1; i>=0; i--) cout<<ans[i];
          cout<<endl;
    }
}


[ 本帖最后由 czz5242199 于 2012-12-23 01:42 编辑 ]
2012-12-22 21:17
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
Problem 1204 - the cover circle
一道几何体,规定w>=h

1、如果w>=2h,则直接在两边放两个最大的球,r=h/2

2、如果h<=w<2h,建立坐标系,一个圆圆心为(r,r),另一个圆心为(w-r,h-r),由于两圆相切,则两心距离为2r,解方程得,r=(h+w-sqrt(2hw))/2


程序代码:
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

double w,h;

int main()
{
    while (cin>>w>>h)
    {
          double t;
          if (w<h)
          {
                  t=w; w=h; h=t;
          }
          if (w>=h+h) t=h/2; else t=(w+h-sqrt(2*h*w))/2;
          cout<<fixed<<setprecision(3)<<t<<endl;
    }
}

2012-12-22 21:52
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
回复 119楼 czz5242199
曹哥,我在这个格式控制上脑袋老是抽筋,麻烦你给改一下吧。我看看什么样的才能过。

编程之路定要走完……
2012-12-23 09:58
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
回复 126楼 C_戴忠意
程序代码:
while(cin>>n && n)
    {
        for(i=0;i<n;++i)    cin>>code[i].x;
        for(i=0;i<n;++i)    cin>>code[i].y;
        for(i=0;i<n;++i)    
        {
            if (i!=0 && i%23==0) cout<<endl;
            cout<<f(code[i].x,code[i].y);
        }
        cout<<endl;
    }
2012-12-23 16:24
快速回复:C论坛算法团队 首战 西安电子科技大学OJ
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037097 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved