| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 42026 人关注过本帖, 47 人收藏
标题:C论坛算法团队 首战 西安电子科技大学OJ
只看楼主 加入收藏
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
Problem 1015 - Requirements
分析
不知为什么前一段时间看不到这题,现在突然出现了

题目给出n个点,每个点有一个五维的坐标(x1,x2,x3,x4,x5),求任意两点间最大的“距离”,此处两点距离定义为abs(x1-y1)+....abs(x5-y5)

由于n范围会达到10w,所以列举出所有点计算是不行的,由于此处距离的定义是一个比较典型的数学表达式,可以从此处入手:

距离由5个绝对值符号加起来的,我们考虑去掉绝对值,这样就有32种可能性

第一种,原本全部是正数:(x1-y1)+...(x5-y5)=(x1+x2+..x5)-(y1+y2+..y5)
第二种,除了第二个,全部是正数:(x1-y1)+(y2-x2)+(x3-y3)+(x4-y4)+(x5-y5)=(x1-x2+x3+x4+x5)-(y1-y2+y3+y4+y5)
......
第三十二中,(y1-x1)+...(y5-x5)=(-x1-x2-x3-x4-x5)-(-y1-y2-y3-y4-y5)

同时,最终答案=以上三十二个答案中的最大值

所以,对于每一种情况,直接求出n个点的此种形式的最大值和最小值,取差,32个差中最大值即为答案

试着写的时候加上空格,看会不会好看些

程序代码:
#include <stdio.h>
#include <stdlib.h>

double a[100000][5],max,min,ans,now;
int n,i,j,k;

int main()
{
    while (scanf("%d",&n) != EOF)
    {
          for (i = 0; i < n; i++) 
            for ( j = 0; j < 5; j++) scanf("%lf",&a[ i ][ j ]);
          ans=0.0;
          for (k = 0; k < 32; k++)
          {
              max = -1e10; min = 1e10;
              for (i = 0; i < n; i++)
              {
                  now = 0;
                  for (j = 0; j < 5; j++)
                    if ((1 << j) & k) now = now + a[ i ][ j ]; else now = now - a[ i ][ j ];
                  if (max < now) max = now;
                  if (min > now) min = now;
              }
              if (ans < max - min) ans = max - min;
          }
          printf("%.2lf\n",ans);
    }
}
2012-11-17 01:00
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1027 - Black Ball
Problem 1027 - Black Ball

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


Description


Billiards is one of Tiantian's favourite sports. Now, she is playing it with one of her friends, and the game comes to the final ball---Black Eight. The one gets a pot will win the game. Fortunately, it's Tiantian's turn! She wants to win the game more wonderful, so she designs a special route. We assume that the ball will roll forever before being hit into one of the pockets. Let's neglect the middle pocket, and makes two coordinate axes along the edge as shown in the following figure. We know the length (6 shown follows) and width(4 shown follows) of the cushion, and of course the x and y coordinates of the ball. And, finally the angle between the positive direction of the X axes and the starting route is 45°. Will the ball pot?


  

Input

There are multiple test cases. Each case takes one line and contains 4 integers L, W, x and y(2≤L≤2^31-1, w≤W≤L, 0<x<L, 0<y<W). They describe the cushion and the position of the ball. The four pockets of the cushion are (0,0), (L,0), (0,W) and (L,W). The initial position of the ball is (x,y). L=0, W=0, x=0, y=0 indicates the end of the input and should not be processed by your program.

Output

For each case, output one line with one single integer. The integer -1 stands for that the ball will never be hit into any pocket. If not, output the corresponding pockets: 0 for (L,W), 1 for (0,W), 2 for (L,0) and 3 for (0,0).

Sample Input

6 4 3 3
4 4 1 3
0 0 0 0


Sample Output

1
-1

Hint


Source

7th Xidian University Collegiate Programming Contest(2009.9)
分析
在一个给定的矩形台球桌上,在给定的位置以45度角击球黑8,问球是否可以进入球桌四个角上的袋,如果可以还要给出进的是哪个袋。

这里隐含了另一个条件,即球桌的摩擦力为零,也就是说球只要不入袋就会在球桌上一直匀速地运动下去,贴库则按反射角反弹。

这样球的运动轨迹是一条折线。这不便于分析。我们将这些折线按其入射方向展开成一条直线,将会发现它们经过的路径正是球桌以各边为对称轴的镜面虚像。

这样,问题就归结到了判断

Lx + L - x0 = Wy + W - y0

这个一次不定方程有没有解,如果有解则其特征解是多少上来了。

重新整理一下,设 C = W - y0 - L + x0,则方程改写为

Lx - Wy = C

方程有解的充要条件是L和W的最大公约数能整除C。

而求取其特征解的过程可以用辗转相除法来做,具体过程不再赘述,有兴起的朋友可以参看数论的相关章节。

如果大家在纸上画一个矩形,并按题目要求标上四个角的编号,然后向四周展开这个矩形的投影以及投影后的编号,就会发现编号与上面方程的一组最小的非负整数解之间存在一种简单的很有意思的对应关系。

所以我想这四个角的编号顺序也是出题者精心设计的。当然即使随便编号也不影响这个题目的运算过程。
程序代码:
#include<stdio.h>
int gcd(int a, int b)
{
    int r;
    while(r = a % b) a = b, b = r;
    return b;
}
long long f(long long a, long long b, long long c)
{
    return (abs(b) == 1 ? c : c - a * f(b, a % b, c % b)) / b;
}
int cal(int L, int W, long long x, long long y)
{
    int c, g;
    c = W - L + x - y;
    g = gcd(L, W);
    if(c % g) return -1;
    L /= g; W /= g; c /= g;
    y = f(L, -W, c);
    x = (c + W * y) / L;
    while(x < 0 || y < 0) x += W, y += L;
    return (x & 1) + ((y & 1) << 1);
}
int main()
{
    int L, W, x, y;
    while(scanf("%d%d%d%d", &L, &W, &x, &y), (L | W | x | y))
    printf("%d\n", cal(L, W, x, y));
    return 0;
}

重剑无锋,大巧不工
2012-11-18 00:05
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
Problem 1055 - 魔兽争霸考试
Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 671  Accepted: 194  Special Judge: No
Description  
一天,热爱魔兽争霸游戏的 fz 和 wudired 发现了一份有趣的魔兽争霸考试题,内容大致如下:
1 魔兽争霸3的中国区代理是 ( )
A 暴雪 B 九城 C盛大 D奥美

2 以下物品在暗夜精灵族的商店里没有出卖的是 ( )
A.月亮宝石 B. 显形之尘 C.保存权杖 D.避难权杖

3 人族的坦克的护甲类型为 (   
A.无护甲 B.建筑物护甲 C.重型护甲 D.轻型护甲

4 不死族的侍僧生命值为多少 ( )
A.200 B.210 C.220 D.230   
……
……
……

这时候,对魔兽争霸一无所知的zzz也参与了进来。现在我们有三个长度相同的,由ABCD组成的字符串,分别表示他们三个答题的结果。现在我们知道 zzz的答题结果是完全错误的。聪明的你能知道fz 与 wudired 的可能的最大得分和吗?答对一题得一分,题目数量 n < 30.
Input输入的第一行包含一个数字n ,表明题目的数量,然后是三个长度为n的字符串,表示
Zzz, fz, wudired的选项。包含多组输入数据,以EOF结束Output每组数据输出一行,包括:
一个整数,表明他们的最大可能得分和。
Sample Input

3
AAA
ABC
BAC

2
AB
BA
AA

Sample Output

4
3
HintSourcezlp

根据题意可知,Zzz的答案是错误的,所以如果 fz和wudired也选和Zzz相同的答案不得分,如果不同,只能假设fz或wudired的答案是正确答案并得分,在判断fz与wudired或wudired与fz的答案是否相同,相同得分。详见代码:


程序代码:
#include <stdio.h>

#define N 35

int main()
{
    int n,i,score;
    char a[N],b[N],c[N];
    while(scanf("%d %s %s %s",&n,a,b,c)!=EOF)
    {
        for(i=0,score=0;i<n;i++)
        {
            if(a[i]!=b[i])   
            {
                score++;
                if(b[i]==c[i])    score++;
            }
            else if(a[i]!=c[i])    score++;
        }
        printf("%d\n",score);
    }
    return 0;
}


[ 本帖最后由 C_戴忠意 于 2012-11-19 20:08 编辑 ]

编程之路定要走完……
2012-11-19 19:58
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1033 - 实验室的新机子
呵呵,由于不要求按顺序解题,所以找出题号靠前还未被解的问题还挺不容易的。这可能也会增加以后在这里检索题目的难度。

但我又不太想要求按顺序解题。现在向各位征集解决这一矛盾的方案。

再下一城
Problem 1033 - 实验室的新机子

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


Description


  实验室到了一批新机子,这下可把WM和ZYF高兴坏了,看着配置颇高的新机子,他们决定进行一番压力测试,于是他们打开了经典的游戏——扫雷。-_-!
  扫雷的规则很简单,雷区是一个16*30的阵列,每个单元要么是一个雷,要么是一个数字,数字表示的是以这个单元为中心的9个单元中雷的个数(如果数字单元贴边则不计落在阵列外的单元)。一旦点到雷则游戏结束,否则可以继续点下去,直到将所有数字点出来。
   ZYF二话不说立马开始乱点,世界上总有某些人运气好到令人发指,ZYF连点了五下竟点出的全是数字,WM认识到这是种缺心眼的行为,并预感到下一次很可能就会点到雷,立马阻止了他。那么根据点出来的数字到底能确定多少个必定是雷的单元呢?
   此处说明一下,我们称两个有相同行坐标而坐标列只差1,或者有相同列坐标而行坐标只差1的单元为相邻的单元。相邻的单元是可达的,而拥有共同的可达单元的两个单元之间也是可达的。ZYF点开的几个单元之间就是相互可达的。

Input

输入数据的第一行是一个正整数T(1≤T≤100),表有T组待测数据,每组待测数据的第一行为一正整数N(1≤N≤5),为ZYF已点开的单元数,接下来N行, 每行三个正整数X、Y和S(1≤X≤16, 1≤Y≤30, 0≤S≤8)表示点开数字所在单元的坐标和那个数字。

Output

针对每组待测数据,输出一个正整数,表示在阵列上可以确定是雷的单元的个数。由于可能是不稳定的Windows程序错误,所以可能出现数字间矛盾的情况,此时输出0即可。

Sample Input

3
3
3 3 3
4 3 6
4 4 3
1
1 1 3
2
4 4 7
4 5 3

Sample Output

6
3
0

Hint


Source

8th Xidian University Collegiate Programming Contest(2010.6)
分析
这个问题可以通过解一个线性方程组来完成,不过由于解的值域只有0和1(某一位是雷或不是雷)且根据题意点开的位置最多只有5个,即变量的数量最多只有16个,所以所有可能的解的数量不超过2的16次方个,即65536。

这个数量对于计算机来说算是很少的,所以我决定采用穷举的方式来遍历解空间。这个效率不如解方程快,但是可以接受的,而且算法简单,可以避免解方程的过程中计算机的有限精度造成的截断误差对结果的影响。

简单说一下方程的构造方式

取所有与点开的点的位置相邻点的值为变量X(注意X是个相量),已点开的位置中标的雷数量为B,X与已点开的位置的相邻关系矩阵为A(相邻为1,不相邻为0)

这样可以得到

AX = B

解这个方程,统计在所有解相量中都为1的变量的数量既是题目要求输出的数值。

在我的代码中cal函数即完成解方程及统计变量的过程。

其中数组b中每个元素b[i]存储的即是关系矩阵的第i行,它的第j位即是第j个变量与第i个已点开位置的相邻关系。

第一组循环完成的是关系矩阵的生成过程。同时得到变量的数量t。

第二组循环是通过试值的方式求取议程的解。结果按位与至r,这样同时完成变量的统计工作。

r为32位整型,初始值为-1,即其二进制的每一位都为1。由上面的叙述知变量使用的位最多只有16位,这里利用其它位作标志位为判断方程是否有解。

如果有解,它与r作与运算后的的结果为解值,其高位多余的1将被清除。如果无解,高位的1将会保留,这时r的值为负。

最后通过r的值是否为负来判断是否有解,如果无解则按要求输出0,如果有解则输出r中1的数量。

下面算法的时间复杂度是O(2^n),虽然从评估上这不是最快的算法(解线性方程的话它的时间复杂度是O(n^2)),但它是目前西电OJ里提交时间最少的,占用内存最小的,代码量最短的。

在遍历解的过程中用了点剪枝策略看来效果还不错:-)
程序代码:
#include<stdio.h>
int cal(int n, int *x, int *y, int *c)
{
    int b[8] = {}, r, f, i, j, k, t;
   
    for(t = 0, i = 1; i <= 16; i++)
    for(j = 1; j <= 30; t += f, j++)
    {
        for(f = k = 0; k < n && (i - x[k] || j - y[k]); k++);
        if(k == n) for(k = 0; k < n; k++)
            if((i != x[k] || j != y[k]) && abs(i - x[k]) <= 1 && abs(j - y[k]) <= 1)
                b[k] |= 1 << t, f = 1;
    }

    for(r = -1, i = 0; i < 1 << t; j == n ? r &= i++ : i++)
    for(j = 0; j < n; j++)
    {
        for(f = 0, k = b[j] & i; k; f++, k &= k - 1);
        if(f != c[j]) break;
    }
   
    if(r < 0) return 0;
    for(f = 0; r; f++, r &= r - 1);
    return f;
}
int main()
{
    int t, n, x[8], y[8], c[8], i;
    for(scanf("%d", &t); t--; printf("%d\n", cal(n, x, y, c)))
    for(scanf("%d", &n), i = 0; i < n; i++)
    scanf("%d%d%d", &x[i], &y[i], &c[i]);
    return 0;
}

重剑无锋,大巧不工
2012-11-21 20:31
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
Problem 1053 - Math Practice
Time Limit: 1000MS   Memory Limit: 65536KB   
Difficulty:
Total Submit: 514  Accepted: 97  Special Judge: No
Description   
One lovely afternoon, Bessie's friend Heidi was helping Bessiereview for her upcoming math exam.

     Heidi presents two integers A (0 <= A <= 45) and B (1 <= B <= 9)to Bessie who must respond with an integer E in the range 1..62.E is the smallest integer in that range that is strictly greaterthan A and also has B as the first digit of 2 raised to the E-th power. If there is no answer, Bessie responds with 0.

    Help Bessie correctly answer all of Heidi's questions by calculatingher responses.

    By way of example, consider A=1 and B=6. Bessie might generate a table

like this:

         E         2^E    First digit of 2^E

         2          4            4

         3          8            8

         4         16            1

         5         32            3

         6         64            6      <-- matches B

Thus, E=6 is the proper answer.

NOTE: The value of 2^44 does not fit in a normal 32-bit integer.

 
InputLine 1: Two space-separated integers: A and BOutputLine 1: A single integer E calculated as aboveSample
Input
1 6
Sample Output
6
Hint
注意换行
Source

我一直以为有规律可循,没想到后面没有规律。

程序代码:
#include <stdio.h>

int main()
{
    int a,b,i,j;
    char digit[]={"124813612512481361251248136125124813612512481371251249137125124"};
    while(scanf("%d %d",&a,&b)!=EOF)
    {
        for(i=a+1,j=0;i<=62;i++)
            if(digit[i]-'0'==b)    {printf("%d\n",i);j=1;break;}
        if(j==0)    printf("0\n");
    }
    return 0;
}


[ 本帖最后由 C_戴忠意 于 2012-11-23 22:25 编辑 ]

编程之路定要走完……
2012-11-23 17:37
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
Problem 1038 - Qinz大牛猜想
Time Limit: 5000MS   Memory Limit: 65536KB   
Difficulty:
Total Submit: 220  Accepted: 104  Special Judge: No
Description
Qinz大牛很爱猜想,所以经常能在比赛中YY出一些公式,并取得出其不意的效果。Qinz大牛坐火车去深圳实习,在漫长无聊的火车上,大牛又提出了一个想,“1+1=2”,他想一个数是否都能分解为两个奇素数的和呢?如果能的话,那一共会有多少对这样的数呢?(p1+p2=n,p2+p1=n,只能算一组)并将这样的数对定义为Qinz对,Qinz大牛没有带电脑,但他又很想知道他的这个猜想是否正确。现在由你来回答这个问题。
后来Qinz大牛发现他和哥德巴赫大牛不谋而合。并为此得意很久。
Input第一行T,表示测试用例数,接下来T组测试用例
每一组测试用例有一个输入N(4<=N<=2^15),表示要分解的数。Output只有一行,输出答案
Sample Input
4
5
8
10
32768
Sample Output
0
1
2
244
Hint10=3+7,10=5+5,所以有两组这样的数
10=3+7,10=7+3算一组。
Sourcezhengzhenzhe220

这道题目我把32768以内的素数先筛选出来,把素数的和打一张表(应该是离散化得思想)。

程序代码:
#include <stdio.h>
#include <stdlib.h>

void init(int *sum)
{
    int i,j,k,x,num,n=32768,a[8192],b[32768];
    n++;n/=2;
    a[0]=2;a[1]=3;num=2;
    for(i=1;i<=2*n;i++)    b[i]=0;
    for(i=3;i<=n;i+=3)
    for(j=0;j<2;j++)
    {
        x=2*(i+j)-1;
        while(b[x]==0)
        {
            a[num++]=x;
            for(k=x;k<=2*n;k+=x)    b[k]=1;
        }
    }
    for(i=1;i<num;i++)
    for(j=i;j<num;j++)
        sum[a[i]+a[j]]++;
}

int main()
{
    int t,n,sum[65536]={0};
    init(sum);
    scanf("%d",&t);
    while(t-- && scanf("%d",&n))
        printf("%d\n",sum[n]);
    return 0;
}

编程之路定要走完……
2012-11-24 06:41
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1035 - 淼·孟德尔
Problem 1035 - 淼·孟德尔

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


Description


  作为一个实验室,仅在里面编程序显得很单调,为此WM也经常在实验室做一些物理、化学、生物等实验。一次他受到“植物大战僵尸”游戏的启发,杂交出了能生产金币的植物!这种植物刚开始每株一天能生产K个金币,这样经过D天,WM就能得到K *D个金币了。(-_-)但是WM想要得到更多的金币。每天的工作结束时,WM可以花费P * X个金币对所有植物进行杂交改良,使之一天能多生产X个金币;也可以花费P * Y个金币培育出Y株新植物(这Y株新植物的生产能力与其他植物一样)。
   一开始WM只有N株每天能生产K个金币的植物,他想通过这些植物赚到M个金币,最少需要几天呢?
 注:可以认为培育新植物或者是进行杂交能瞬间完成,即不占用轮次。

Input

输入数据第一行是一正整数T(0<T≤30),表示有T组测试数据。
每组测试数据只有一行,包括四个整数N, K, P, M(0<N, K, P≤100, 0<M≤1000000000),意义如上文描述。

Output

对于每组测试数据,输出一个整数D,表示通过这些植物赚到M个金币最少要D天。

Sample Input

4
2 1 2 10
2 1 2 9
5 4 15 100
1 1 100 1000000000

Sample Output

4
3
5
272

Hint


对于第一组数据2 1 2 10:第一天赚到2 * 1个金币,花费这2个金币去提高生产能力1,接下来3天每天都赚到2 * 2个金币,第4天结束后就有12个金币,满足要求。

Source

8th Xidian University Collegiate Programming Contest(2010.6)
分析
看似简单的一个题目,但困扰了我很久。一开始我理解错了题意,认为每次升级植物只能以一种方式进行,要么改良植物要么培育新植物。在这种理解下开始构建算法。结果在测试样例数据的第二组时出现了问题,在我的理解下无论如何不可能在3天内生产出9个钱币,除非植物的升级两种方式可以同时进行。于是在新的理解下构建算法。

目前我还没有想到更好的算法,只是穷举了所有可能的升级方式。下面分析一下我的算法。

设以当前状态不做植物升级时到之后的第t天所生产的金币数量f

当前已经拥有的金币数量为c、拥有植物数量为n、植物的生产力为k,单位升级费用为p,则

f = c + n * k * t

如果对n进行升级一次,则

f = c - p + (n + 1) * k * t
  = c - p + n * k * t + k * t

如果对k进行升级一次,则

f = c - p + n * (k + 1) * t
  = c - p + n * k * t + n * t

都是一次升级,显然升级n和k中较小的可以得到更多的金币,这是一个重要的条件。

另外,由f和t的函数关系可以看出它是一个线性函数,升级改变的是直线的斜率

那么,升级进行的越早(即t值越大)f的值越大,即越能获得更多的金币。

我们的目的是使用尽量短的时间生产出m个金币,那么由上述函数的反函数求出当f达到m时所需的时间t

这样,我们可以从第0天开始遍历升级s次之后要达到m所需要的时间,其中最小值即是题目要的结果。

每次升级的方案应用上面的结论,即升级n和k中的最小值,并尽可能的靠前升级。这算是贪心算法吧。

最后,确定升级次数s的上限。

当 n * k >= m 时,即下一天生产的金币就已经达到要求的数量时就不必再继续升级了。

而每次升级是对n或k加1,所以s的上限约为

(s/2)*(s/2) <= m

即 s <= 2 * sqrt(m)

由此知算法的时间复杂度为O(sqrt(m))

m的上限是10亿,开平方后大约是3万,这个量级是可以接受的。

代码虽短,但分析这个问题耗费了我几天的休息时间(我一直想找到一种优美的数学关系,可惜失败了)。呵呵,其实相比算法分析,写代码是件很简单的事。

希望论坛众朋友能尽快突破语言的困扰,感受算法的乐趣。
程序代码:
#include<stdio.h>
int f(int n, int k, int p, int m)
{
    int c, i, d, tn, tk, t, tm;
    for(tm = m, c = i = 0, d = n * k; d <= m; c += d, n = tn, k = tk, i++)
    for(tn = n, tk = k; c >= p && d <= m; tm = t < tm ? t : tm)
    {
        d += tn >= tk ? (tk++, tn) : (tn++, tk);
        t = i + (m - (c -= p) - 1 + d) / d;
    }
    return tm;
}
int main()
{
    int t, n, k, p, m;
    for(scanf("%d", &t); t--; printf("%d\n", f(n, k, p, m)))
        scanf("%d%d%d%d", &n, &k, &p, &m);
    return 0;
}


重剑无锋,大巧不工
2012-11-27 00:28
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1036 - 神奇的盒子
Problem 1036 - 神奇的盒子

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


Description


  WM平时喜欢在夜晚游历于花丛、土堆等新校区隐蔽的角落,因为他觉得那样可以见到某些平时见不到的东西,找到某些比较稀奇的物品。随着其长期的寻觅,他终于找到了一个外表精美但上了锁的盒子,盒子没有锁眼,只有刻在上面的3对半数字:(1,1)、(4,5)、(7,15)和那个独立的数字100。
WM将盒子带回实验室,和ZYF一起研究,经过商议与复杂的推算,他们认定这些以(x,y)形式出现的数值就是传说中的拆分数(即将x变为一系列数连加,而不同的加法式子的数目就是其拆分数y),只要得到100的拆分数就能打开这个盒子。
 例如,对于3,其不同的连加式有3个,即:3 = 1 + 1 + 1,3 = 1 + 2,3 = 3。式子1 + 2与式子2 + 1视为相同的式子。
WM和ZYF决定编写一个程序来计算给定正整数的拆分数,从而可以打开这个盒子,看看里头到底有什么秘密。

Input

输入数据的第一行是一个正整数T(1≤T≤100),表示有T组待测数据,每组待测数据占一行,是一个正整数N(1≤N≤100)。

Output

对于每组输入数据,输出一个整数表示N的拆分数,输出每个整数后换行。

Sample Input

3
1
4
7

Sample Output

1
5
15

Hint


Source

8th Xidian University Collegiate Programming Contest(2010.6)
分析
整数划分,经典的教学级算法。

设将整数n划分成不大于m的和式的数量为f(n, m)

当 m == 1时,f(n, 1) = 1                         很好理解,即n个1相加的情况。
当 m > n 时,f(n, m) = f(n, n)                   n的划分因子不可能大于n。
当 m == n时,f(n, m) = 1 + f(n, m - 1)           n可以划分成最大因子为n的情况加最大因子小于n的情况,而最大因子为n的情况只有n本身这1种。
当 m < n 时,f(n, m) = f(n - m, m) + f(n, m - 1) 同上,只是将n划分成最大因子为m的情况有f(n - m, m)种。

直接应用上面的分析递归求解也是可以的,只不过效率很差。

在m < n时有两个递归分支,这使得运算量随着n的增大呈指数级增长。

这两个递归分支中存在大量的重复运算,由此可以利用动态规划来消除重复运算提高效率。
程序代码:
#include<stdio.h>
int main()
{
    int f[101][101], i, j;
    for(i = 1; i <= 100; i++) f[i][1] = f[1][i] = 1;
    for(i = 2; i <= 100; i++)
    for(j = 2; j <= 100; j++)
        f[i][j] = j > i ? f[i][i] :
        j == i ? 1 + f[i][j - 1] :
        f[i - j][j] + f[i][j - 1];
    for(scanf("%d", &i); i--; printf("%d\n", f[j][j]))
        scanf("%d", &j);
    return 0;
}

重剑无锋,大巧不工
2012-11-27 09:19
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
Problem 1207 - love message
Time Limit: 1000MS   Memory Limit: 65536KB   
Difficulty:
Total Submit: 4  Accepted: 3  Special Judge: No
Description Jiangshan and Zhao Yiran is a sweetheart lover in different class. So, Jiangshan developed a application to send message to Zhao Yiran through wireless. However, so unfortunately, their teachers are so great that all they send will be received by their teachers too. In order to keep their message secrecy, they have to encrypt the message.

 
When a char X appear n times, Jiangshan will show it as Xn, for example bb->b2. In order to get the love message, Zhao Yiran have to deciphering the message with mind acts upon mind. Could you help they to deciphering.Input A string S, indicates the message Zhao Yiran get, all the char is lower case. There may be several test cases in the input file and end when S equal to XXX.
OutputA string T, indicates the message after deciphering.
Sample Input
a3
go12gle
XXX

Sample Output

aaa
goooooooooooogle

HintSourceSYSU


突然看见西电第三页在增加题目,就刷了一道,这道题目没什么技巧就是字符串的操作。详见代码:

程序代码:
#include <stdio.h>
#include <string.h>

int main()
{    
    char s[1024],ch;
    int i,j,len,size;
    while(scanf("%s",s) && strcmp(s,"XXX")!=0)
    {
        len=strlen(s);
        for(i=0;i<len;i++)
            if(s[i]>='0' && s[i]<='9')
            {
                size=0;
                ch=s[i-1];
                while(s[i]>='0' && s[i]<='9')
                {
                    size *= 10;
                    size += s[i]-'0';
                    i++;
                }
                i--;
                for(j=1;j<size;j++)    printf("%c",ch);
            }
            else    printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}

编程之路定要走完……
2012-11-29 20:36
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
Problem 1069 - Egypt
Time Limit: 1000MS   Memory Limit: 65536KB   
Difficulty:
Total Submit: 155  Accepted: 96  Special Judge: No DescriptionA long time ago, the Egyptians figured out that a triangle with sides of length 3, 4, and 5 had a right angle as its largest angle. You must determine if other triangles have a similar property.
InputInput represents several test cases, followed by a line containing 0 0 0. Each test case has three positive integers, less than 30,000, denoting the lengths of the sides of a triangle. OutputFor each test case, a line containing "right" if the triangle is a right triangle, and a line containing "wrong" if the triangle is not a right triangle.
Sample Input
6 8 10
25 52 60
5 12 13
0 0 0
Sample Output
right
wrong
right

HintWaterloo ACM Programming Contest October 2, 2010
SourceWaterloo ACM Programming Contest October 2, 2010

这道题目是判断直角三角形,两边的平方和等于第三边的平方即直角三角形。


程序代码:
#include <stdio.h>
#include <math.h>

int main()
{
    int a,b,c;
    while(scanf("%d %d %d",&a,&b,&c) && (a+b+c))
    {
        a=pow(a,2);
        b=pow(b,2);
        c=pow(c,2);
        if(a+b==c || a+c==b ||b+c==a)    printf("right\n");
        else    printf("wrong\n");
    }
    return 0;
}

编程之路定要走完……
2012-12-03 21:45
快速回复:C论坛算法团队 首战 西安电子科技大学OJ
数据加载中...
 
   



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

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