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

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

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

我的收件箱(0)

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

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

只看楼主加入收藏

czz5242199

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

第 41 楼

得分:0

1076题分析

此题无关动态规划= =
实际上核心在于求两个数组的交集，如果直接比较也能做到O(n^2)算法，和你上面的动态规划时间复杂度一样，所以是无用的

首先将两个数组排序，然后吻别设置两个变量i=0,j=0，然后比较a[i],b[j]，如果相等，则得到一个交集，同时i，j各加一，否则小的那一方加1，因为数组是有序的，所以这样一定可以得到所有的交集，时间复杂度是O(nlogn+mlogm)即排序所用的时间

注意n，m范围都是10w而不是1w

程序代码：

#include <iostream>
#include <cstdlib>
#define Max 100000
using namespace std;

int n,m,a[Max],b[Max];

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

int main()
{
    while (cin>>n>>m,n>0 && m>0)
    {
          for (int i=0; i<n; i++) cin>>a[i];
          for (int i=0; i<m; i++) cin>>b[i];
          qsort(a,n,4,cmp);
          qsort(b,m,4,cmp);
          int i=0,j=0,ans=0;
          while (i<n && j<m)
          {
                if (a[i]==b[j]) 
                {
                                a[ans++]=a[i]; i++; j++;
                }
                else if (a[i]>b[j]) j++; else i++;
          }
          if (ans>n/2) cout<<"美丽的女孩，你不适合种田，你适合做ACM！\n";
          else if (ans==0) cout<<"有没有女孩子愿意跟我一起回家种田~~\n"; 
          else 
          {
               cout<<"就是你了，陪我回家种田去吧！\n"<<ans<<endl;
               for (int i=0; i<ans; i++) cout<<a[i]<<endl;
          }
    }
}

[ 本帖最后由 czz5242199 于 2012-11-7 13:40 编辑 ]

2012-11-07 13:38

C_戴忠意

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

第 42 楼

得分:0

Problem 1121 - 排序 Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 279  Accepted: 109  Special Judge: No DescriptionMSTC里有好多有特长的人，有些是力量型人才，有些是智力型人才，有些是敏捷型的。

现在告诉你 N 个人，每个人的力量，智力，敏捷的值，和每个人的编号。

题目要求你将 N 个部员按照力量从大到小排序，如果两个部员的力量相同，则按照智力值从大到小排序，如果

两个部员力量，智力都一样，则按照敏捷从小到大排序。测试数据保证没有两个部员的力量，智力，敏捷全部相同。

Input第一行 N ：表示有 N 个同学。（  1 <= N <= 500 )
接下来 N 行，
第 i 行有 3 个值， ai, bi, ci   a 代表力量， b 代表智力， c 代表敏捷。编号为 i
（ i 是部员的编号， 1 <= i <= N )

Output输出 N 行：

将排序后的部员编号输出。
每行一个编号
Sample Input

4
2 2 3
2 3 4
4 8 9
2 2 2

Sample Output
3
2
4

1HintSourcewyz

这题只需要建立一个结构体，然后结构体排序就行了。我用的qsort函数。

程序代码：

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

#define N 505

typedef struct
{
    int no;
    int strength;
    int agile;
    int brains;
}Student ;

int cmp(const void *a,const void *b)
{
    Student *p=(Student *)a;
    Student *q=(Student *)b;
    if(p->strength != q->strength)    return q->strength - p->strength;
    else if(p->agile != q->agile)    return q->agile - p->agile;
    else    return q->brains - p->brains;
}

int main()
{
    int n,i;
    Student student[N];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d %d %d",&student[i].strength,&student[i].agile,&student[i].brains);
            student[i].no=i+1;
        }
        qsort(student,n,sizeof(Student),cmp);
        for(i=0;i<n;i++)    printf("%d\n",student[i].no);
    }
    return 0;
}

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

编程之路定要走完……

2012-11-07 20:32

C_戴忠意

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

第 43 楼

得分:0

Problem 1130 - 比较大小 Time Limit: 1000MS Memory Limit: 65536KB

Difficulty:
Total Submit: 591 Accepted: 206 Special Judge: No Description
输入两个十进制整数A，B，请判断它们的大小关系。

我们重新定义两个数的大小比较规则为：谁的二进制表示中含1的个数多谁大，若含1的个数相等，则按普通的大小关系进行比较。

Input第一行：一个整数T，表示测试数据组数。
接下来共T行，每行两个整数A，B。(A,B在int范围内)Output每组测试数据输出一行，即A，B的大小关系。
Sample Input

3
3 4
10 10
5 9

Sample Output

>
=
<

这个题目关键得到一个数二进制数中1的个数，我这个方法不是很好，见代码。

程序代码：

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

int getOne(int num)
{
    int i,temp,count=0;
    for(i=60;i>=0;i--)
    {
        temp=pow(2,i);
        if(num >= temp)    {num-=temp;count++;}
    }
    return count;
}

int main()
{
    int caseNum,a,b;
    scanf("%d",&caseNum);
    while(caseNum--)
    {
        scanf("%d %d",&a,&b);
        if(getOne(a) < getOne(b))    printf("<\n");
        else if(getOne(a) > getOne(b))    printf(">\n");
        else if(a > b)    printf(">\n");
        else if(a < b)    printf("<\n");
        else    printf("=\n");
    }
    return 0;
}

编程之路定要走完……

2012-11-07 20:38

czz5242199

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

第 44 楼

得分:0

Problem 1030 - Exact E

用公式求e的前5000位，设立一个最终答案的数组，一个存当前1/n!的数组，每次除以n+1得到1/(n+1)!的数组，然后加到最终答案里去，知道求到1/(n+1)!大概前5500位都是0停止，这时候答案应该就是e了

程序代码：

#include <iostream>
#define l 5500
using namespace std;

int a[6000],b[6000],la,lb,n,flag;

void divide(int p)
{
    int i=0,temp=0;
    while (i<l)
    {
        while (temp<p && i<l)
        {
              temp=temp*10+a[++i];
              a[i]=0;
        }
        if (temp!=0) flag=1;
        a[i]=temp/p;
        temp%=p;
    }
}

void plus_()
{
    for (int i=l-1; i>=1; i--)
    {
        b[i]+=a[i];
        b[i-1]+=b[i]/10;
        b[i]%=10;
    }
}

void prepare()
{
    int p=2;
    a[1]=5; b[1]=5; flag=1;
    while (flag)
    {
              flag=0;  
              divide(++p);
              plus_();
    }
}

int main()
{
    prepare();
    while (cin>>n,n>0) cout<<b[n]<<endl;
}

2012-11-10 15:20

C_戴忠意

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

第 45 楼

得分:0

Problem 1043 - Qinz大牛的烦恼

典型0-1背包，这里还得感谢曹哥在学习上对我的帮助，我把背包九讲打印出来了，准备好好看看。

程序代码：

#include <stdio.h>
#include <string.h>

#define N 500

int max(int a,int b)    {return a > b ? a : b;}
int main()
{
    int t,n,m,c[N],v[N],f[N];
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)    scanf("%d %d",&v[i],&c[i]);
        for(i=0;i<N;i++)    f[i]=0;
        for(i=1;i<=n;i++)
            for(j=m;j>=c[i];j--)
                f[j]=max(f[j],f[j-c[i]]+v[i]);
        printf("%d\n",f[m]);
    }
    return 0;
}

编程之路定要走完……

2012-11-10 22:45

czz5242199

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

第 46 楼

得分:0

Problem 1034 - 再战新机

从能量的角度考虑，只需要使得初始速度能上到最高点即可，找出最高点ymax，1/2*m*v^2=m*g*ymax求出v

程序代码：

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

int y,ymax,t,n;

int main()
{
    scanf("%d",&t);
    while (t--)
    {
          scanf("%d",&n);
          ymax=0;
          while (n--)
          {
                scanf("%d%d",&y,&y);
                if (ymax<y) ymax=y;
          }
          printf("%.2lf\n",sqrt((double)2*9.8*ymax));
    }
}

2012-11-11 01:53

C_戴忠意

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

第 47 楼

得分:0

http://sxu.

曹哥，杨大哥，我请教一道题目，进制转换，我测试没问题了，不知道为什么过不了。

账号：916717312@密码：000199119000

程序代码：

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

int Base_Ten(char *num,int base)
{
    int i,rows=0,num_[256],NUM=0,len=strlen(num);
    for(i=len-1;i>=0;i--)
        if(num[i]>='0' && num[i]<='9')    num_[rows++]=num[i]-'0';
        else if(num[i]>='A' && num[i]<='Z')    num_[rows++]=num[i]-'A'+10;
        else    num_[rows++]=num[i]-'a'+10;
    for(i=len-1;i>=0;i--)    NUM+=num_[i]*pow(base,i);
    return NUM;
}

void Base_N(int num,int base)
{
    char digit[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G'};
    int n[256],i,rows=0;
    while(num)
    {
        n[rows++]=num%base;
        num/=base;
    }
    for(i=rows-1;i>=0;i--)    printf("%c",digit[n[i]]);
    printf("\n");
}

int main()
{
    char n[256];
    int a,b;
    while(scanf("%d %s %d",&a,n,&b)!=EOF)
        Base_N(Base_Ten(n,a),b);
    return 0;
}

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

编程之路定要走完……

2012-11-14 15:16

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 48 楼

得分:0

回复 95楼 C_戴忠意

呵呵，拿你的帐号测试了你的代码，搞定了。

开始我怀疑是pow函数的截断误差造成的，修改后还是不对。突然想到了我的代码RT的原因，发现你没有处理0的输出。

附上我的AC代码给你对比参考。

程序代码：

#include<stdio.h>
#include<ctype.h>
#include<math.h>
char * trans(int a, char * n, int b)
{
    int d, i, t;
    for(d = i = 0; t = toupper(n[i++]); d = d * a + (t <= '9' ? t - '0' : t - 'A' + 10));
    for(n[i = (d ? log(d) : 0) / log(b) + 1] = 0; i--; d /= b) n[i] = (t = d % b) <= 9 ? t + '0' : t - 10 + 'A';
    return n;
}
int main()
{
    int a, b;
    char n[128];
    scanf("%d%s%d", &a, n, &b);
    printf("%s\n", trans(a, n, b));
    return 0;
}

重剑无锋，大巧不工

2012-11-14 17:45

czz5242199

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

第 49 楼

得分:0

杨大哥，关于23题我之前代码确实有个bug，因为我这个算法是先将所有数补齐0到最高位然后求，所以如果k=0最后答案还要减去补齐的数，减得时候我一个long long定义成了int，下面这个代码是正确的

程序代码：

#include <iostream>
#include <memory.h>
using namespace std;

int a[70],radix,p,len,final_len;
long long n,power[70],final[100];
char ch;

long long numof(int dep)
{
    long long j=0;
    for (int i=dep; i>=0; i--) j=j*radix+a[i];
    return j;
}

void pluss(long long p)
{
     final[0]=final[0]+p;
     for (int i=0; i<final_len; i++)
     {
         final[i+1]=final[i+1]+final[i]/10;
         final[i]=final[i]%10;
     }
     while (final[final_len]!=0)
     {
           final[final_len+1]=final[final_len]/10;
           final[final_len]=final[final_len]%10;
           final_len++;
     }
}

void Getans(int dep)
{
    if (dep==0)
    {
               if (a[dep]>=p) pluss(1); return;
    }
    if (radix>p) 
      for (int i=0; i<dep; i++)  pluss(a[dep]*power[dep-1]);
    if (a[dep]>p) pluss(power[dep]);
    if (a[dep]==p) pluss(numof(dep-1)+1);
    Getans(dep-1);
}

void minuss(long long p)
{
     final[0]-=p;
     int i=0;
     long long j;
     while (final[i]<0)
     {
           j=-final[i]/10;
           if (j*10<-final[i]) j++;
           final[i]+=j*10;
           final[i+1]-=j;
           i++;
     }
     while (final[final_len-1]==0) final_len--;
}
int main()
{
    while (cin>>n>>radix>>ch)
    {
          if (ch>='0' && ch<='9') p=ch-'0'; else
          if (ch>='A' && ch<='Z') p=ch-'A'+10; else p=ch-'a'+36;
          
          len=0;
          do
          {
                a[len]=n%radix; n/=radix; len++;
          }
          while (n>0);
          
          power[0]=1;
          for (int i=1; i<len; i++) power[i]=power[i-1]*radix;
          
          final_len=1; 
          memset(final,0,sizeof(final));
          
          Getans(len-1);
          if (p==0)
          {
                   if (len!=1) minuss((len-1)*radix);
                   long long j=radix-1;   //改动
                   for (int i=2; i<len; i++) 
                       minuss((len-i)*(j=j*radix));
          }
          
          for (int i=final_len-1; i>=0; i--) cout<<final[i];
          cout<<endl;
    }
}

2012-11-15 22:07

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 50 楼

得分:0

抽测了一些数据，还是没找到有什么不同。看来还是得好好分析一下你的程序才行，这两天总说要看，但总是没看，不能辜负你赠代码的情意，明天忙完工作上的事一定好好分析分析。

你要有兴趣也可以看看我的代码问题出在哪儿。下面是扩展倍数后的测试用代码。

程序代码：

#include<stdio.h>
#define FB    100000000000000000LL
int output(long long n, int p, int k)
{
    long long a, c0, c1, t;
    for(c1 = c0 = 0, a = 1; t = n / a / p; a *= p)
    {
        c0 += (t - !k) * a;
        c1 += c0 / FB;
        c0 %= FB;
        t = n % (a * p) - a * k + 1;
        c0 += t <= 0 ? 0 : t < a ? t : a;
        c1 += c0 / FB;
        c0 %= FB;
    }
    t = (k ? n - a * k : 0) + 1;
    c0 += t <= 0 ? 0 : t < a ? t : a;
    c1 += c0 / FB;
    c0 %= FB;
    return c1 ? printf("%lld%017lld\n", c1, c0) : printf("%lld\n", c0);
}
int main()
{
    long long n;
    int p, k;
    char s[4];
    for(; scanf("%lld%d%s", &n, &p, s) != EOF; output(n, p, k))
        k = s[0] >= 'a' ? s[0] - 'a' + 36 : s[0] >= 'A' ? s[0] - 'A' + 10 : s[0] - '0';
    return 0;
}

重剑无锋，大巧不工

2012-11-15 22:27

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