C语言 « 坏男孩的博客

日志分类：C语言

一个让我蛋分的NOIP复赛模拟题

时间：2010年10月20日作者：坏男孩查看次数:1,794 views评论次数：10

其实，题目真的很水很水。基本全部模拟+穷举。然而我……竟然0分。。。

题目和测试数据我已经放在了网盘上：点击下载题目+测试数据+标程。文件名：“NOIP模拟1.rar”

接下来我把我的蛋分程序贴出来：

#include <iostream>
using namespace std;
int r;
int suma,sumb,sa,sb,a[9],b[9];
int ooxx;
int mina,minb;
bool t=true;
bool cinn (){
     for (int i=1;i<=8;i++){          cin>>a[i];
         if (a[i]==-1)return false;
     }
}
bool cinm (){
     for (int i=1;i<=8;i++){          cin>>b[i];
         //if (b[i]==-1)return false;
     }
}
void couta () {
     for (int i=1;i<=8;i++){
         if (a[i]<=r&&a[i]<minb)suma++;
     }
}
void coutb () {
     for (int i=1;i<=8;i++){
         if (b[i]<=r&&b[i]<mina)sumb++;
     }
}
 
void work (){
     //for (int i=1;i<=ooxx;i++){
         mina=9999;
         minb=9999;
         suma=0;
         sumb=0;
         for (int j=1;j<=8;j++){
             if (a[j]<mina)mina=a[j];
         }
         for (int j=1;j<=8;j++){
             if (b[j]<minb)minb=b[j];
         }
         if (mina<minb)couta();          else if (mina>minb)coutb();
         else if (mina==minb){suma=0;sumb=0;}
         cout<<suma<<':'<<sumb<<endl;          sa+=suma;          sb+=sumb;      //} } int main () {     freopen ("curling.in","r",stdin);     freopen ("curling.out","w",stdout);     cin>>r;
    ooxx=10;
    for (int i=1;i<=20;i++){
        if (i%2==1)t=cinn();
        if (i%2==0)t=cinm();
        if (t==false){ooxx=i;break;}
        ooxx/=2;
        if (i%2==0)work ();
    }
    cout<<sa<<':'<<sb<<endl;
    return 0;
}

#include <iostream>
using namespace std;
int pivot;
int f[50001][7];
float x;
 
int ak (int r[],int first,int end ){
    int i=first;
    int j=end;
    while (i<j){
          while (i<j&&r[i]<=r[j])j--;
          if (i<j){
             int t=r[i];
             r[i]=r[j];
             r[j]=t;i++;
          }
          while (i<j&&r[i]<=r[j])i++;
          if (i<j){
             int t=r[i];
             r[i]=r[j];
             r[j]=t;j--;
          }
    }
    return i;
}
 
void sort (int r[],int first,int end){
     if (first<end){
        pivot=ak (r,first,end);
        sort (r,first,pivot-1);
        sort (r,pivot+1,end);
     }
}
int xxx[7];
int main () {
    freopen ("count.in","r",stdin);
    freopen ("count.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>f[j][i];
            if (f[j][i]<1||f[j][i]>100)xxx[j]++;
        }
    }
    for (int i=1;i<=m;i++){
        sort (f[i],1,n);
    }
    float bb[7];
    float bbb[7];
    //cout<<p<<endl;
    //for (int i=1;i<=m;i++)cout<<xxx[i]<<endl;
    for (int i=1;i<=m;i++){
        int summ=0;
        int suma=0;
        int ooxx=0;
        int oxx=0;
        int nn=n-xxx[i];
        x=(n-xxx[i])/10.0;
        int p;
        if (x-int(x)>=0.5)p=x+1;
        else p=x;
        for (int j=p+1;j<=nn-p;){
            if (f[i][j]>=1&&f[i][j]<=100){
               summ+=f[i][j];
               ooxx++;
               j++;
            }
        }
        for (int j=1;j<=p;){
            if (f[i][j]>=1&&f[i][j]<=100){
               suma+=f[i][j];
               oxx++;
               j++;
            }
        }
        for (int j=nn-p+1;j<=nn;){
            if (f[i][j]>=1&&f[i][j]<=100){
               suma+=f[i][j];
               oxx++;
               j++;
            }
        }
        bb[i]=(suma+summ)/((oxx+ooxx)*1.0);
        bbb[i]=summ/((ooxx)*1.0);
        //printf ("%.2f %.2f\n",(suma+summ)/(n*1.0),summ/((n-2*p)*1.0));
    }
    for (int i=1;i<=m;i++)printf ("%.2f ",bb[i]);cout<<endl;
    for (int i=1;i<=m;i++)printf ("%.2f ",bbb[i]);cout<<endl;
    return 0;
}

希望有大牛可以指点下这两个错误程序。样例数据都过了，但是测试数据全×。无语……

标签：c++分类：C语言

NOIP选手之家——OIerHome.Com

时间：2010年10月18日作者：坏男孩查看次数:1,528 views评论次数：7

经常关注我的博客的人都知道，我前几天参加了全国NOIP，并以90分（高出分数线14分）的成绩顺利进入复赛。这样，我的目标就直指“一等奖”了。

我去年曾经有惊无险的拿到过一次“一等奖”，按照市教育局的规定：一个一等奖中考加15分，两个一等奖保送市一中理科实验班。这个诱惑是巨大的。于是我开始在网上拼命地做题，并发现了一个很好的NOI论坛——OIerHome.Com。

OIerHome.Com的创始人是一位同济大学的Pascal大牛。偶尔的一次机会和他聊上了，并交上了朋友。这个论坛正如它的名字一样——进去之后，一片橙色，着实感到十分温暖。进入论坛看了几个帖子之后，第一个感觉就是牛太多了。。特别的是，有好多台湾同胞的高手。虽然大部分都是Pascal版本的，但是OIerHome的创始人——Vistat也表示最近正在猛攻C++。

以下是OIerHome的创站历程：

第一阶段：QQ群

2008年8月4日，QQ会员达到VIP6。作为一项特权，VIP6会员可以创建一个500人的超级群，vistart作出决定，把广大信息学爱好者集合起来！

信息学爱好者QQ群（47711781）于2008年8月16日创建，初期招募35人；

2008年11月达到100人；

2009年3月达到200人；

2009年6月达到300人；

2009年8月达到400人；

2009年10月5日达到500人！

2009年6月25日，QQ群改名“交流心得-互帮互助”。

从创建到人满用了415天。QQ群不够用了。

第二阶段：论坛

2010年2月16日，vistart开始酝酿创建论坛，于是他找到了oibuddha，两人一拍即合，随即动手。

2010年3月底，论坛决定使用www.oierhome.com域名和Discuz!X1承载论坛。论坛名称依然沿用“交流心得-互帮互助”。

2010年4月，完成论坛版块设置。

2010年5月，完成用户设置。

现在看到的只是论坛的一个雏形，vistart与oibuddha努力协调工作进度，力争在2010年8月16日前完成（QQ群创建2周年）。

2010年10月15日，更换新的模板，更改板块，为大家提供更好的服务。

在OIerHome，也许你可能不能在这儿不能想在别的论坛里那么自由的回帖，也许不能在这儿看到美女，但是在这儿你可以享受到学习的乐趣，交到无数神牛朋友，解决更多复杂的难题。

最后，送给大家一个传送门：http://www.oierhome.com。如果有什么好的建议可以直接留言了。谢谢。

标签：NOIP分类：C语言

Pascal转C语言网站——深蓝评测系统

时间：2010年10月13日作者：坏男孩查看次数:1,767 views评论次数：6

对于我们这些NOIP的选手有一个问题——有些题目不会做的时候，就会想“百度一下”或者“Google”一下搜索题解。但是，有些题目的题解只有Pascal版本，没有C语言版本。这让人很头疼。

不过，在一次意外的访问，发现了一个网站：http://oj.oiers.cn 。这是深蓝评测系统，本来我是想刷刷水题，后来我发现这个网站竟然支持Pascal转换成C语言。不过转换的结果有一点小问题。。。翻译网址：http://oj.oiers.cn/utility/p2c/

比如这一段NOIP2008第一题的Pascal题解：

var
 a : array [0..13] of char;
 
 procedure init;
 var i : longint;
 begin
   for i := 1 to 13 do read(a[i]);
 end;
 
 procedure main;
 var i , j , t : longint;
 begin
   t := 0; j := 0;
   for i := 1 to 12 do
     if a[i] &lt;&gt; '-' then
     begin
       inc(j); t := t + (ord(a[i]) - 48) * j;
     end;
 
   t := t mod 11;
 
   if ((a[13] = 'X') and (t = 10)) or (ord(a[13]) - 48 = t) then
   begin
     writeln('Right');
     exit;
   end;
 
   for i := 1 to 12 do write(a[i]);
   if t = 10 then writeln('X') else writeln(t);
 end;
 
 begin
   init;
   main;
 end.

转换后的结果是：

#include <p2c/p2c.h>
 
Static Char a[14];
 
Static void init(void)
{
  long i;
 
  for (i = 1; i &lt;= 13; i++) {
    a[i] = getchar();
    if (a[i] == '\n')
      a[i] = ' ';
  }
}
 
Static void main_(void)
{
  long i;
  long j = 0, t = 0;
 
  for (i = 1; i &lt;= 12; i++) {
    if (a[i] != '-') {
      j++;
      t += (a[i] - 48) * j;
    }
  }
 
  t %= 11;
 
  if (a[13] == 'X' &amp;&amp; t == 10 || a[13] - 48 == t) {
    printf("Right\n");
    return;
  }
 
  for (i = 1; i &lt;= 12; i++)
    putchar(a[i]);
  if (t == 10)
    printf("X\n");
  else
    printf("%12ld\n", t);
}
 
main(int argc, Char *argv[])
{
  PASCAL_MAIN(argc, argv);
  init();
  main_();
  exit(EXIT_SUCCESS);
}

而真正的转换后的程序应该是：

#include <iostream>
using namespace std;
char a[14];
 
void init(void)
{
  long i;
 
  for (i = 1; i &lt;= 13; i++) {
    a[i] = getchar();
    if (a[i] == '\n')
      a[i] = ' ';
  }
}
 
void work(void)
{
  long i;
  long j = 0, t = 0;
 
  for (i = 1; i &lt;= 12; i++) {
    if (a[i] != '-') {
      j++;
      t += (a[i] - 48) * j;
    }
  }
 
  t %= 11;
 
  if (a[13] == 'X' &amp;&amp; t == 10 || a[13] - 48 == t) {
    printf("Right\n");
    return;
  }
  for (i = 1; i &lt;= 12; i++)
    putchar(a[i]);
  if (t == 10)
    printf("X\n");
  else
    printf("%d\n", t);
}
 
main()
{
  init();
  work();
  return 0;
}

仔细观察就可以看出端倪。每个程序也就改一点就行了。希望深蓝官方可以解决这些问题。
我想把这个代码弄到我的博客里来。。但不知道怎么移植。。唉~~希望有高人可以帮帮我！

标签：c++分类：C语言

二进制转十进制

二进制数第0位的权值是2的0次方，第1位的权值是2的1次方……
例如，设有一个二进制数：0110 0100，转换为10进制为：

下面是竖式：

01100 100 换算成十进制

第0位 0 x 2^0 = 0

第1位 0 x 2^1 = 0

第2位 1 x 2^2 = 4

第3位 0 x 2^3 = 0

第4位 0 x 2^4 = 0

第5位 1 x 2^5 = 32

第6位 1 x 2^6 = 64

第7位 0 x 2^7 = 0

————————–

(01100 100)B=(100)D

注：数字后面相应的字母表示不同的进位制。B表示二进制,O表示八进制，D表示十进制，H表示十六进制

二进制数第0位的权值是2的0次方，第1位的权值是2的1次方……　　例如，设有一个二进制数：0110 0100，转换为10进制为：
下面是竖式：
01100 100 换算成十进制
第0位 0 x 2^0 = 0
第1位 0 x 2^1 = 0
第2位 1 x 2^2 = 4
第3位 0 x 2^3 = 0
第4位 0 x 2^4 = 0
第5位 1 x 2^5 = 32
第6位 1 x 2^6 = 64
第7位 0 x 2^7 = 0

————————–

(01100 100)B=(100)D

注：数字后面相应的字母表示不同的进位制。B表示二进制,O表示八进制，D表示十进制，H表示十六进制。

十进制转二进制

1.整数部分除R取余

例：(125)D=(1111101)B

注：余数中最后得到的余数为最高位，最先得到的余数为最低位，从高到低依次排列。

2.小数部分乘R取整

例：(0.25)D

0.25

X 2

_______________

0.50 （整数部分0为高位）

X 2 ↓

_______________ ↓

1.00 （整数部分1为低位）

(0.25)D=(0.01)B

注：整数的转换是精确的，小数的转换可能出现无穷小数或循环小数的情况。此时需要进行舍入处理以截断，所以小数的转换可能略有偏差。箭头表示由高位到低位的趋势。

标签：NOIP分类：C语言

NOIP初赛知识点——原码，反码，补码

时间：2010年10月09日作者：坏男孩查看次数:1,670 views评论次数：2

大家都知道数据在计算机中都是按字节来储存了，1个字节等于8位（1Byte=8bit），而计算机只能识别0和1这两个数，所以根据排列，1个字节能代表256种不同的信息，即28（0和1两种可能，8位排列），比如定义一个字节大小的无符号整数（unsigned char），那么它能表示的是0～255（0~28-1）这些数，一共是256个数，因为，前面说了，一个字节只能表示256种不同的信息。别停下，还是一个字节的无符号整数，我们来进一步剖析它，0是这些数中最小的一个，我们先假设它在计算机内部就用8位二进制表示为00000000（从理论上来说也可以表示成其他不同的二进制码，只要这256个数每个数对应的二进制码都不相同就可以了），再假设1表示为00000001，2表示为00000010，3表示为00000011，依次类推，那么最大的那个数255在8位二进制中就表示为最大的数11111111，然后，我们把这些二进制码换算成十进制看看，会发现刚好和我们假设的数是相同的，而事实上，在计算机中，无符号的整数就是按这个原理来储存的，所以告诉你一个无符号的整数的二进制码，你就可以知道这个数是多少，而且知道在计算机中，这个数本身就是以这个二进制码来储存的。比如我给你一个2个字节大小的二进制码，首先声明它表示的是无符号的整数：00000000 00000010，我们把前面的0省略，换算一下，它表示的也是数值2，和前面不同的是，它占了2个字节的内存。不同的类型占的内存空间不同，如在我的电脑中char是1个字节，int是4个字节，long是8个字节（你的可能不同，这取决于不同的计算机设置），它们的不同之处仅仅是内存大的能表示的不同的信息多些，也就是能表示的数范围更大些（unsigned int能表示的范围是0~28*4-1），至于怎么算，其实都是一样的，直接把二进制与十进制相互转换，二进制就是它在计算机中的样子，十进制就是我们所表示的数（误解：不同的计算机储存的原理是不同的，取决于商家的喜好呢）。无符号的整数根本就没有原码、反码和补码。

只有有符号的整数才有原码、反码和补码的！其他的类型一概没有。虽然我们也可以用二进制中最小的数去对应最小的负数，最大的也相对应，但是那样不科学，下面来说说科学的方法。还是说一个字节的整数，不过这次是有符号的啦，1个字节它不管怎么样还是只能表示256个数，因为有符号所以我们就把它表示成范围：-128-127。它在计算机中是怎么储存的呢？可以这样理解，用最高位表示符号位，如果是0表示正数，如果是1表示负数，剩下的7位用来储存数的绝对值的话，能表示27个数的绝对值，再考虑正负两种情况，27*2还是256个数。首先定义0在计算机中储存为00000000，对于正数我们依然可以像无符号数那样换算，从00000001到01111111依次表示1到127。那么这些数对应的二进制码就是这些数的原码。到这里很多人就会想，那负数是不是从10000001到11111111依次表示-1到-127，那你发现没有，如果这样的话那么一共就只有255个数了，因为10000000的情况没有考虑在内。实际上，10000000在计算机中表示最小的负整数，就是这里的-128，而且实际上并不是从10000001到11111111依次表示-1到-127，而是刚好相反的，从10000001到11111111依次表示-127到-1。负整数在计算机中是以补码形式储存的，补码是怎么样表示的呢，这里还要引入另一个概念——反码，所谓反码就是把负数的原码（负数的原码和和它的绝对值所对应的原码相同，简单的说就是绝对值相同的数原码相同）各个位按位取反，是1就换成0，是0就换成1，如-1的原码是00000001，和1的原码相同，那么-1的反码就是11111110，而补码就是在反码的基础上加1，即-1的补码是11111110+1=11111111，因此我们可以算出-1在计算机中是按11111111储存的。总结一下，计算机储存有符号的整数时，是用该整数的补码进行储存的，0的原码、补码都是0，正数的原码、补码可以特殊理解为相同，负数的补码是它的反码加1。下面再多举几个例子，来帮助大家理解！

十进制　→　二进制　　（怎么算？要是不知道看计算机基础的书去）
47　　　→　101111

有符号的整数　　原码　　反码　　补码
47　　　　00101111　 00101111　00101111（正数补码和原码、反码相同，不能从字面理解）
－47　　　　10101111　　11010000　　11010001（负数补码是在反码上加1，符号位不参与运算）
再举个例子，学C语言的同学应该做过这道题：
把－1以无符号的类型输出，得什么结果？（程序如下）

#include
void main()
{
short int n=-1;
cout&lt;&lt;(unsigned short int)n&lt;&lt;ENDL;
}

首先在我的电脑中short int类型的储存空间是2个字节，你的可能不同，我说过，这取决于你的计算机配置。它能储存28*2＝65536个不同的数据信息，如果是无符号那么它的范围是0~65535（0~216-1），如果是有符号，那么它的范围是-32768~32767（-215~215-1）。这道题目中，开始n是一个有符号的短整型变量，我们给它赋值为-1，根据我们前面所说的，它在计算机中是以补码11111111 11111111储存的，注意前面说了是2个字节。如果把它强制为无符号的短整型输出的话，那么我们就把刚才的二进制把看成无符号的整型在计算机中储存的形式，对待无符号的整型就没有什么原码、反码和补码的概念了，直接把11111111 11111111转化成十进制就是65535，其实我们一看都是一就知道它是范围中最大的一个数了。呵呵，就这么简单。你个把上面的源代码编译运行看看，如果你的电脑short int也是两个字节，那就会和我得一样的结果。你可以先用这个语句看看：cout<<<endl;<>看看你的电脑里的短整型占多少的储存空间，也可以用sizeof来看其它任何类型所分配的储存空间。
最后提醒一句，关于数据如何在计算机中储存的，这里只适用于整型的数据，对于浮点型的是另一种方式，这里我们暂时就不深究了。
FeedBack:

1．为什么使用补码形式：

其实计算机中的数值用补码来表示，一是为了防止0有2个编码，其次就是为了把减法运算用加法运算表示出来，以达到简化电路的作用。具体内容请参看一些专业书籍，比如华中科技大出版的《逻辑设计》（呵呵，我大二的课本）。
为什么用补码表示有符号整数。比如8位整数表示的范围是-128~127，而不是-127~128呢？想过没有，为什么二进制10000000在原码和反码中表示0，在补码中它不表示0，保证了0表示的唯一性，但是它为什么表示负数，而不是整数，你也许会说，因为它符号位是1呀，表示负数呀，对，继续，+128我们用补码怎么表示，包括符号位，表示为010000000，超过了2个字节，如果截取低8位，那么是10000000，最高位（符号位）是1，表示的是一个负数，我们再看看-128的机器码是多少，原码110000000，反码101111111，补码110000000，截取低8位即10000000，表示的是一个负数。
其实呀，这些总结出来的东西都是玩巧，也并不是说非要这样实现，学了计算机逻辑原理，就知道，其实这样做是由于物理条件关系。因为运算器里这样做更容易实现计算。

2．

1
2
3

int x=-70;
int y=2;
int z=x&gt;&gt;y

z的值是多少？主要是不明白负数移位该怎么算？
在C语言中 int 是两个字节所以 70在计算机中表示为 0000 0000 0100 0110
-70用补码表示即 1111 1111 1011 1010
右移2位 C语言中采用的是算术右移
所以补进位和原符号位相同即 1111 1111 1110 1110
取反加一求它的相反数 0000 0000 0001 0010 等于 17
所以右移后的结果是 -17
有个规则如果左移1位相当于乘以2 右移1位相当于除以2 取整
我们验证一下用-70除以2*2 结果取整正好是我们推算的 -17
在C++中 int 是四个字节但是结果也是一样的原因自己可以推算一下
3. 在8位运算中65-15具体怎么通过补码计算啊~~~

15的原码是0000 1111 补码也是0000 1111

因为是正数符号位(最高位)为0

-15的原码是1000 1111(←注意这个地方你弄错了)符号为为1表示负
反码就是 1111 0000(注意原码反码补码之间转换的时候千万不要把符号位考虑进去) 补码就是 1111 0001
如果你已经求出了15的补码这里有个简便的方法求-15的补码:
直接把15的补码包含符号位一起求反即可即
15补码 1111 0001 那么-15的补码 0000 1110

补码计算的时候符号位是要直接参与二进制运算了而不是单独考虑
所谓多余8位的进位舍去其实就是比如补码1111 1111再加任意非0数原来这个补码表示的数就会发生溢出(比如加上 0000 0001原先符号位1表示负数加后表示正数)
这里也许你觉得没有必要因为本身只能容纳8位多余的当然要舍去
可是你可能不知道如果是反码进行运算的话不是舍去多余进位而是把多余的进位加到最低位称为循环进位

4。补码溢出如何处理

这就要看你处理数据的范围，比如我用8位二进制记录数据。
只能储存-128~127之间的数据，如果超过127或小于-128就会溢出。
比如127+1=-128 就是这个道理
就好象最大值和最小值连成了一个环，超过了循环计算
这样做才使得数据有规律性和周期性
为了实现这个所以补码是舍掉进位而反码是循环进位前面说过了
解决的办法就是如果8位的数据不过你就用16位的
如果整型不够就用长整型撒实在不行就用浮点型的

标签：NOIP分类：C语言