C论坛算法团队首战西安电子科技大学OJ - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → C论坛算法团队首战西安电子科技大学OJ

我的收件箱(0)

共有 42026 人关注过本帖， 47 人收藏

标题：C论坛算法团队首战西安电子科技大学OJ

只看楼主加入收藏

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 31 楼

得分:0

回复 30楼 beyondyf

纠结了很久，终于ac了，这题的描述有一句是错的

Each result could be stored as a 64bit signed integer.

=_=

2012-10-30 00:47

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 32 楼

得分:0

回复 59楼 beyondyf

程序代码：

#include <stdio.h>
#include <math.h>

#define N 1000000

int arr[N];

void init()
{
    int i,j;
    for(i=2;i<sqrt(N);i++)
        for(j=2;j<N/i;j++)
            arr[i*j]=1;
}

int main()
{
   
    long long n;
    int i,first;
    init();
    while(scanf("%lld",&n) && n)
    {
        for(i=2,first=1;i<=n;i++)
        {
            if(!arr[i])
                while(!(n%i))
                {
                    printf(first ? "%d" : "*%d",i);
                    n/=i;
                    first=0;
                }
        }
        printf("\n");
    }
    return 0;
}

杨大哥，这是我重新写的1025题代码，虽然比较前一个快了许多，但还是没有达到你说的那个速度。求代码一看。

编程之路定要走完……

2012-11-03 17:18

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 33 楼

得分:0

Problem 1042 - Qinz喝饮料

Time Limit: 1000MS Memory Limit: 65536KB Difficulty:

Total Submit: 95 Accepted: 39 Special Judge: No DescriptionQinz这就要乘飞机去参加百度总决赛了！在飞机上的饮料可是免费的，Qinz大牛可不能错过这次好机会。
飞机上共有n个座位，且排成一列，而且这一列上面都已经有乘客了（编号从1到n）,每个乘客都需要一杯茶或者一杯咖啡。漂亮的空姐正准备给每位乘客送饮料。
在座位的前方有一个供应饮料的机器，可以提供茶叶和咖啡两种饮料，空姐每次可以在供应机处使用容量为
7的托盘,也就是可以放7杯饮料,且每次只可以装茶或者咖啡一种饮料。
空姐每次可以做如下动作：
1:从供应机处移动到第一个座位或从座位移动到供应机，需要一秒钟。
2:从座位i移动到座位i+1或者从座位i+1移动到座位i,需要一秒钟。
3:给每位乘客提供饮料，需要四秒钟。
4:空姐在返回供应机处取饮料需要47秒钟。

Qinz想要知道空姐给所有乘客供应饮料最少需要多长时间
Input第一行包含一个整数T，表明有T组输入数据。
接下来的T组输入数据中，每组数据第一行包含两组整数 n(1<=n<=1000) 和 m (1<=m <=n),分别表示总的乘客人数与要喝茶的人数.
接下的一行有 m 个整数,每个整数 i 表示编号为 i的乘客需要喝茶。其余的 n-m 位乘客喝咖啡。Output对于每组输入输出一个整数，表明供应饮料所需的最少时间。

Sample Input

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

Sample Output

108
59
261

Hint在第一组数据中，第一位乘客喝茶而第二位乘客喝咖啡。空姐需要从供应处取一杯茶，送给乘客1 并返回，这需要47+1+4+1=53.然后从供应处取一杯咖啡送给乘客2并返回。这需要47+2+4+2=55秒钟。
总共需要108秒钟。

Sourcezhang long pan

谁有时间看看这道题目，我觉得写的差不多了，就是AC不了。希望能够共同探讨。

[ 本帖最后由 C_戴忠意于 2012-11-3 21:27 编辑 ]

编程之路定要走完……

2012-11-03 21:25

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 34 楼

得分:0

程序代码：

#include <stdio.h>

#define N 1005

int main()
{
    int caseNum,n,m,i,ii,jj,tea,cof,time,idex[N];
    scanf("%d",&caseNum);
    while(caseNum--)
    {
        scanf("%d %d",&n,&m);
        for(i=1,time=0;i<=n;i++)    idex[i]=0;//初始化
        time+=(m/7*47+(n-m)/7*47+n*4);//有多少个座位就得停留多少次（n*4），算出去几次供应机（m/7+(n-m)/7）
        if(m%7)    time+=47;//上边加的是正好7个人的，如果有余下的必须再加一次47
        if((n-m)%7)    time+=47;//同上
        for(i=1;i<=m;i++)
        {
            scanf("%d",&ii);
            idex[ii]=1;//喝茶的置1，喝咖啡的置0
        }
        for(i=n,ii=0,tea=0,cof=0;i>0;i--)//我觉得从大往小处理时间消耗最小
        {
            if(idex[i])    {tea++;ii=i;}
            else    {cof++;jj=i;}
            if(tea==7)    {time+=(i+6)*2;tea=0;}//每送7杯茶加一次往返时间
            if(cof==7)    {time+=(i+6)*2;cof=0;}//每送7杯咖啡加一次往返时间

        }
        if(tea%7)    time+=(ii+tea%7-1)*2;//如果余下不够7杯茶加上其往返时间
        if(cof%7)    time+=(jj+cof%7-1)*2;//如果余下不够7杯咖啡加上其往返时间
        printf("%d\n",time);
    }
    return 0;
}

附上自己的代码

编程之路定要走完……

2012-11-03 21:27

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 35 楼

得分:0

Problem 1024 - Easy Job
分析

n长的数删去k个数，使得剩下的数最大，贪心即可，每次找出最小的i使得data[i]<data[i+1]，然后把data[i]删除掉，重复k次

但是由于数据比较大，不能单纯每次删除，然后得到新的数，然后再删除，这样我一开始超时了，后来发现可以统一处理在O(n)时间内找出需要删除的数，详细见代码

程序代码：

#include <iostream>
using namespace std;
#define Max 20010

int data[Max];
int n,p;

int main()
{
    while (cin>>n>>p)
    {
          char ch;
          for (int i=1; i<=n; i++) data[i]=(cin>>ch,ch-'0');
          data[0]=10;
          
          int top=0,end=1;
          while (end<=n && p)
                if (data[top]>=data[end]) data[++top]=data[end++]; 
                else
                {
                    top--; p--;
                }
          while (end<=n) data[++top]=data[end++];
          for (int i=1; i<=top-p; i++) cout<<data[i];
          cout<<endl;
    }
}

2012-11-04 01:52

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 36 楼

得分:0

Problem 1025 - Fruit
分析

一开始n个数，取出最小的两个数，此次代价为两数和，然后一个大小为两数和的数加入，之前两个数去掉，重复n-1次，求最小代价

维护一个最小堆即可

程序代码：

#include <iostream>
using namespace std;

int num,ans;

void swap(int &a,int &b)
{
     int t=a;
     a=b;
     b=t;
}

class Node
{
      private:
              int depth;
              int data[10010];
      public:
             void insert(int temp)
             {
                  data[++depth]=temp;
                  int i=depth,j;
                  while (i>1)
                  {
                        j=i/2;
                        if (data[j]>data[i]) swap(data[i],data[j]);
                        i=j;
                  }
             }
             
             void init()
             {
                  depth=0;
                  for (int i=1; i<=num; i++) 
                  {
                      cin>>data[i];
                      insert(data[i]);
                  }
             }
             
             int getdata() { return data[1]; }
             
             void del()
             {
                  data[1]=data[depth--];
                  int i=1,j;
                  while (i*2<=depth)
                  {
                        j=i*2;
                        if (data[j]>data[j+1]&& j<depth) j++;
                        if (data[i]>data[j]) swap(data[j],data[i]);
                        i=j;
                  }
             }
             
                        
};

int main()
{
    Node p;
    while (cin>>num)
    {
          ans=0;
          
          p.init();
          while (--num)
          {
                int temp=p.getdata(); 
                p.del();
                temp+=p.getdata();
                p.del();
                ans+=temp;
                p.insert(temp);
          }
          cout<<ans<<endl;
    }
}

2012-11-04 11:44

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 37 楼

得分:0

Problem 1028 - Counting Beans

Time Limit: 1000MS Memory Limit: 65536KB

Difficulty:
Total Submit: 107 Accepted: 53 Special Judge: No DescriptionWhat a day! It's dark outside, and Tiantian has nothing to do. She's boring and starts to count beans. There're two kinds of beans, red bean and mung bean. It doesn't take long, she becomes boring again. So she finds another job to do: dividing the beans into as many piles as she can! And, of course, each pile must have the same number of red beans and mung beans. For example, if she has 6 red beans and 4 mung beans, she can divide them into 2 piles, and each pile will contain 3 red beans and 2 mung beans. It's so difficult for her to solve it, so she comes to ask you to program it.
InputThere are multiple test cases. Each case takes one line and contains two integers r and m(1≤r≤2^31-1, 1≤m≤2^31-1) separated by a single space. They describe the number of red beans and mung beans separately.
r=0,m=0 indicates the end of the input and should not be processed by your program.OutputFor each case, output one line with a single integer describes the maximum piles she can get.

Sample Input

6 4
5 3
0 0

Sample Output

2
1

HintSource7th Xidian University Collegiate Programming Contest(2009.9)

题目描述意思尽把已知的红豆和绿豆尽可能多的分为含相等的红豆和绿豆的堆，其实这个就相当于求红豆总数和绿豆总数的最大公约数

最大公约数求法（欧几里得-辗转相除法），这个我就不介绍了，想理解其如何来的在随意一本算法书上或上网都能找到最给力的推理。

附上代码：

程序代码：

#include <stdio.h>

long long gcd(long long a,long long b)
{
    if(a < b)    {a+=b; b=a-b; a-=b;}
    if(b==0)    return a;
    else    return gcd(b,a%b);
}

int main()
{
    long long r,m;
    while(scanf("%lld %lld",&r,&m) && (r+m))
        printf("%lld\n",gcd(r,m));
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-11-5 14:04 编辑 ]

编程之路定要走完……

2012-11-05 14:03

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 38 楼

得分:0

Problem 1109 - 破解密码 Time Limit: 1000MS

Memory Limit: 65536KB
Difficulty:

Total Submit: 355 Accepted: 131 Special Judge: No DescriptionSHF是一个很神奇的人，他的电脑也采用了一种奇怪的密码验证方式，即一串数字的某个排列。CX是一个密码破解爱好者，当然对于这种密码很有兴趣。现在他知道SHF的初始密码是(1,2,3,...,N)，每次用两个数字A和B来修改密码，也就是把[A,B]位置区间的数字反序，包括A、B位置的数字（A,B以1作为起始编号）。例如，现在的密码是(2,1,3,5,4)，密码修改操作的数字是2和5，则修改后的密码为(2,4,5,3,1)。CX已经知道了SHF所有的密码修改操作的序列，但由于操作次数实在太多了，他计算不出最后的密码是什么，现在他需要你帮他计算出最后的密码。

Input输入数据的第一行是一个正整数T（0<T<=10），表示有T组测试数据。
每组测试数据的第一行包含两个整数N,M（0<N<=100000, 0<=M<=2000），表示初始密码为(1,2,3,...,N)，共有M次密码修改操作。
接下来有M行，每行有两个整数A,B（0<A<=B<=N），表示进行一次密码修改操作，意义如上所述。Output对于每组测试数据，在一行上输出N个整数，表示最后的密码。整数之间以一个空格隔开。

Sample Input

2
5 2
1 3
4 5
5 2
1 4
2 5

Sample Output

3 2 1 5 4
4 5 1 2 3

HintSourceqinz

这道题目就是给定处理的范围，然后按逆序排列。这道题目我用数组的方法实现的，不过我觉得用字符串更好。有兴趣的试试。

代码：

程序代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100005

int password[MAX_SIZE];

void exchange(int a,int b)
{
    for(;a<b;a++,b--)
    {
        password[a] += password[b];
        password[b] = password[a] - password[b];
        password[a] -= password[b];
    }
}

int main()
{
    int caseNum,n,m,a,b,i;
    scanf("%d",&caseNum);
    while(caseNum--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)    password[i]=i;
        for(i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            exchange(a,b);
        }
        for(i=1;i<=n;i++)    printf(i-1 ? " %d" : "%d",password[i]);
        printf("\n");
    }
    return 0;
}

编程之路定要走完……

2012-11-05 15:50

czz5242199

等　级：小飞侠
威　望：4
帖　子：660
专家分：2400
注　册：2011-10-26

第 39 楼

得分:0

Problem 1029 - Decimal
Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 87 Accepted: 15 Special Judge: No
Description
The rational number and the irrational number makes the set of real number. As a mathematics fan, Tiantian prefer investigating the kind of rational number with the form of 1/n. That kind of rational number can be a finite decimal or a recurring decimal. For example, 1/5 = 0.2 and 1/3 = 0.33333.... To learn the rational number more clearly, Tiantian came to ask you to write a program for her. The program may be able to return any number of the rational number with the form of 1/n.

Input
There are multiple test cases. Each case takes one line and contains two integers s and n (1≤s≤5000, 1≤n≤2^31-1) separated by a single space. It describes that Tiantian would like to know the nth number after the decimal point of 1/s.
s=0,n=0 indicates the end of the input and should not be processed by your program.
Output
For each case, output one line with the nth number after the decimal point of the rational number 1/s.
Sample Input
2 2
5 1
13 6
0 0
Sample Output
0
2
3
Hint
Source
7th Xidian University Collegiate Programming Contest(2009.9)

题目就是求1/s的小数点后第n位，如果1/s是有限小数直接求，如果是无限循环小数，可以通过记录当前的被除数，当被除数重复时就是循环节出现的时候，比如1/6,被除数是1，然后除，1*10/6，得到1，余4，被除数是4，然后4*10/6=6,余4，被除数又是4，所以循环节出现

程序代码：

#include <iostream>
using namespace std;

int a[5010],flag[5010],n,s;

int cal()
{
    int len=0,p=1%s;
    for (int i=0; i<s; i++) flag[i]=0;
    do
    {
        flag[p]=++len;
        a[len]=p*10/s;
        p=p*10%s; 
    }
    while (p>0 && !flag[p]);
    if (p==0)
             if (n<=len) return a[n]; else return 0;
    if (n<=flag[p]-1) return a[n]; else 
    if ((n-flag[p]+1)%(len+1-flag[p])==0) return a[len]; else
    return a[(n-flag[p]+1)%(len+1-flag[p])+flag[p]-1];
}

int main()
{
    while (cin>>s>>n,s!=0) cout<<cal()<<endl;
}

2012-11-05 17:12

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 40 楼

得分:0

程序代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10000

int dp[MAX_SIZE][MAX_SIZE],flag[MAX_SIZE][MAX_SIZE];
int girl[MAX_SIZE],boy[MAX_SIZE];

int maxx(int a,int b)    { return a>b ? a : b;}

int LCS(int n,int m)
{
    int i,j;
    int len=maxx(n,m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            flag[i][j]=0;
    for(i=0;i<=len;i++)    {dp[i][0]=0;dp[0][i]=0;}
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
        if(boy[i-1]==girl[j-1])    {dp[i][j]=dp[i-1][j-1]+1;flag[i][j]=-1;}
        else    {dp[i][j]=maxx(dp[i-1][j],dp[i][j-1]);}
    }
    /*for(i=0;i<=n;i++)
    {
        for(j=0;j<m;j++)
        {
            printf("%d(%d) ",dp[i][j],flag[i][j]);
        }
        printf("\n");
    } */
    return dp[n][m];
}

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

int main()
{
    int n,m,i,j,count;
    while(scanf("%d %d",&n,&m),n+m)
    {
        for(i=0;i<n;i++)    scanf("%d",&boy[i]);       
        for(i=0;i<m;i++)    scanf("%d",&girl[i]);
        qsort(boy,n,sizeof(int),cmp);
        qsort(girl,m,sizeof(int),cmp);
        count=LCS(n,m);
        if(count > n/2)    printf("美丽的女孩，你不适合种田，你适合做ACM！\n");
        else if(count==0)    printf("有没有女孩子愿意跟我一起回家种田~~\n");
        else
        {
            printf("就是你了，陪我回家种田去吧！\n%d\n",count);
            for(i=1;i<n;i++)
            for(j=1;j<m;j++)
                if(flag[i][j]==-1)
                {
                    printf("%d\n",boy[i-1]);
                    break;
                }
        }

    }
    return 0;
}

1076题，怎么做都超时，曹哥给点意见吧，这两天不知道怎么了，做啥题都超时。

[ 本帖最后由 C_戴忠意于 2012-11-7 11:32 编辑 ]

编程之路定要走完……

2012-11-07 11:31

快速回复：C论坛算法团队首战西安电子科技大学OJ