| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 42026 人关注过本帖, 47 人收藏
标题:C论坛算法团队 首战 西安电子科技大学OJ
只看楼主 加入收藏
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
  得分: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_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
  得分: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_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
  得分: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
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
  得分: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_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
  得分: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
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
  得分: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_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
  得分: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
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
  得分: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
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
  得分: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
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
  得分: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
数据加载中...
 
   



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

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