树状数组,C语言复习笔记

作者: 新金沙平台  发布:2019-09-27

Problem DescriptionLet’s play a game.We add numbers 1,2...n in increasing order from 1 and put them into some sets.
When we add i,we must create a new set, and put iinto it.And meanwhile we have to bring [i-lowbit 1,i-1] from their original sets, and put them into the new set,too.When we put one integer into a set,it costs us one unit physical strength. But bringing integer from old set does not cost any physical strength.
After we add 1,2...n,we have q queries now.There are two different kinds of query:
1 L R:query the cost of strength after we add all of [L,R](1≤L≤R≤n)
2 x:query the units of strength we cost for putting x(1≤x≤n) into some sets.InputThere are several cases,process till end of the input.
For each case,the first line contains two integers n and q.Then q lines follow.Each line contains one query.The form of query has been shown above.
n≤10^18,q≤10^5OutputFor each query, please output one line containing your answer for this querySample Input10 21 8 92 6Sample Output92Hintlowbit =i&.It means the size of the lowest nonzero bits in binary of i. For example, 610=1102, lowbit =102= 210When we add 8,we should bring [1,7] and 8 into new set.When we add 9,we should bring [9,8] and 9 into new set.So the first answer is 8 1=9.When we add 6 and 8,we should put 6 into new sets.So the second answer is 2.题意:每次查询有两种操作 op1:求加入L~R的数时所消耗的单元 op2:求将x加入集合或移动到其它集合所消耗的单元(即由x引起消耗的单元)思路:op1:每次加入一个数i 那么会移动[i-lowbit 1 , i-1] ,总的消耗是i-(i-lowbit 1=lowbit 所以每次加入一个数对应的消耗是2的幂次,那么求L~R即可以枚举幂次,即: ans =(n/(1<<i)-n/(1<<*(1<<i) 解释一下,n/(1<<i)-n/(1<<表示长为2^i的消耗的数的个数,例如:n=10 , 包含长为2的数是2,6,10 为什么4,8不是,因为它们虽然是2的倍数,但更是4的倍数,包含更长的区间了,所以这部分要减去。 op2:由树状数组可知 [i-lowbit 1 , i-1] 是以i为根节点对应的区间,如果假如的数能够移动i ,那么这个数对应的孩子区间一定包含i ,所以从x向上一直找父节点即可。代码如下:

完数

图片 1图片 2

 1 /* 2 题目:一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2+3.编程 3     找出1000以内的所有完数。 4 */ 5  6 /* 7 *  @author: 成鹏致远  8 *  @net: http://infodown.tap.cn 9 */10 11 #include <stdio.h>12 13 int main(void)14 {15     static int k[10];16     int i,j,n,s;17     for(j=2;j<1000;j  )18     {19         n=-1;20         s=j;21         for(i=1;i<=j/2;i  )22         {23             if==0) //因子24             {25                 n  ;26                 s=s-i; //减到0则是完数27                 k[n]=i;28             }29         }30         if(s==0)31         {32             printf("%d 是一个完数 n%d=",j,j);33             for(i=0;i<n;i  )34                 printf("%d ",k[i]);35             printf("%d n",k[n]);36         }37     }38 39     return 0;40 }

View Code

许多初学C指针的同学想在函数内部修改作为参数传递进来的指针的值。看以下代码。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;typedef long long LL;LL lowbit{    return x&(-x);}LL query(LL x,LL n){    LL ans=0;    while(x<=n)    {        ans  ;        x =lowbit;    }    return ans;}LL cal{    LL ans=0;    LL tmp=1;    for(LL i=0; tmp<=x; i  )        ans =-x/(tmp<<1))*tmp,tmp<<=1;    return ans;}int main(){    LL n,q;    while(scanf("%lld%lld",&n,&q)!=EOF)    {        while(q--)        {            int op;            scanf("%d",&op);            if(op==1)            {                LL x,y;                scanf("%lld%lld",&x,&y);                LL ans=cal-cal(x-1);                printf("%lldn",ans);            }            else            {                LL x;                scanf("%lld",&x);                LL ans=query;                printf("%lldn",ans);            }        }    }    return 0;}

贪心算法用例

图片 3图片 4

  1 /*  2 编程解决如下问题。  3   请在整数n=742683613984中删除8个数字,使得余下的数字按原次序组成的新数最小。要求如下:  4   整数n和删除数字的个数“8”在源程序中完成赋值,程序直接输出运行结果;  5   程序结果输出先后被删除的数字和删除后所得的最小数。  6   (提示:整数n可以以字符数组的方式定义、赋值和处理)  7   8   编写思路:  9   在前9位数字中寻找最小数字a1,记下该最小数字的位置b1,a1前面所有数字是该删除的, 10   个数m=b1-1,然后从a1后面开始继续操作,变为删除8-m个数字,从a1后8-m 1个数字中找最小值a2, 11   记下b2,删除a1与a2之间的数字,个数b2-b1-1。m=m b2-b1-1.如此下去直至m=8,停止操作, 12   输出a1a2……及最后一个a和之后的数字。 13  14   程序一是正确的,程序二是错误的 15   一和二的差别主要是在删除字符序列的顺序上 16 */ 17  18 /* 19 *  @author: 成鹏致远  20 *  @net: http://infodown.tap.cn 21 */ 22  23 //程序一:贪心算法 24  25 #include <string.h> 26 #include <stdio.h> 27  28  int main() 29 { 30   int i,m=8,t=0; 31   char p[10]; 32   char s[]="742683613984"; 33   for (i=0;i<12;i  ) 34   { 35         while(t&&p[t-1]>s[i]&&m) //用p数组中的每一个元素和当前s[i]比较 36         { 37             t--,m--; //进入循环意味着s[i]比p[--t]小,需要将p[--t]输出,并且m-1 38             printf("%c",p[t]); 39             if //未删除所有符合条件的元素之前,用逗号将各元素分开 40             printf(","); 41         } 42         p[t  ]=s[i]; //p数组依次暂存前一位比后一位小的数字 43   } //循环结束后p数组中存储着最小的四位数 44         p[t]=0; //字符数组结束 45         printf("n"); 46         puts; 47         return 0; 48 } 49          50            51   52 /* 53 //程序二:这个是错误的,程序一和程序二的差别在删除字符序列的顺序 54  55     #include <stdio.h> 56     #include <stdlib.h> 57      58      void main() 59      { 60          char *s="742683613984"; 61          printf;  62          //去掉8个相当于取4个 63          int a,b,c,d;//下标 64          int aa,bb,cc,dd;//某位数字 65          int ka,kb,kc,kd;//最小值对应的下标 66          int min=10000;//当取4个时,设定初始最小值为5位数 67          int num;//组和的值 68          for(a=0;a<=8;a  ) 69          { 70              for(b=1;b<=9;b  ) 71              { 72                  for(c=2;c<=10;c  ) 73                  { 74                      for(d=3;d<=11;d  ) 75                      { 76                          if  &&  &&   )//保证不重复和先后顺序 77                          { 78                              aa=s[a]-'0';bb=s[b]-'0';cc=s[c]-'0';dd=s[d]-'0';//字符型转换为整数 79                              num=aa*1000 bb*100 cc*10 dd;//求组和数 80                              if (num<min)//选择最小值以及下标 81                              { 82                                  min=num; 83                                  ka=a;kb=b;kc=c;kd=d;//最小值对应的下标 84                              } 85                          } 86                      } 87                  } 88              } 89         } 90       91      for(int i=0;i<=11;i  )//输出去掉的数 92      { 93          if(i!=ka && i!=kb && i!=kc && i!=kd) 94              printf("%ct",s[i]);  95      } 96      printf("n%dn",min);//输出最小值  97      system; 98 } 99 100 101 */102   

View Code

1234567891011121314151617181920 typedefint(chara[],intnLength); inttotal(chara[],intnLength) { intnTotal=0; for(inti=0;i<nLength; i) nTotal =a[i]; returnnTotal; } intmain() { chara[]="abcde"; intnLength=strlen; funcfp; fp=total; printf("%dn",fp(a,nLength)); return0; }

题目链接

判断日期为一年中的第几天

图片 5图片 6

 1 /* 2 * 计算该日在本年中是第几天,注意闰年问题 3 * 以3月5日为例,应该先把前两个月的加起来,然后再加上5天即本年的第几天 4 * 特殊情况,闰年且输入月份大于3时需考虑多加一天 5 */ 6  7 /* 8 *@author: 成鹏致远  9 *@net: http://infodown.tap.cn10 */11 12 #include <stdio.h>13 #include <stdbool.h>14 15 struct year_mon_day16 {17     int year;18     int mon;19     int day;20 };21 22 int main()23 {24     int i;25     int sum;//总天数26     bool flag = false;//闰年标志27     struct year_mon_day ymd;28     29     printf("Pls input year,mon day:");30     scanf("%d%d%d",&ymd.year,&ymd.mon,&ymd.day);31     32     switch33     {34         case 1:35             sum = 0;36             break;37         case 2:38             sum = 31;39             break;40         case 3:41             sum = 59;42             break;43         case 4:44             sum = 90;45             break;46         case 5:47             sum = 120;48             break;49         case 6:50             sum = 151;51             break;52         case 7:53             sum = 181;54             break;55         case 8:56             sum = 212;57             break;58         case 9:59             sum = 243;60             break;61         case 10:62             sum = 173;63             break;64         case 11:65             sum = 304;66             break;67         case 12:68             sum = 334;69             break;70         default:71             printf("data error n");72             return 1;73     }74     sum  = ymd.day;75 76     if(ymd.year/100 || (ymd.year%4 && ymd.year0 != 0))77     {78         flag = true;79     }80     81     if(1==flag && ymd.mon>2)82     {83         sum  ;84     }85 86     printf("%d年%d月%d日 是%d年的第%d天 n",ymd.year,ymd.mon,ymd.day,ymd.year,sum);87 88     return 0;89 }

View Code

在论坛里经常见到一些新人对指针提出一些问题,作为一个经历过许多错误后的新手,我想把自己的经历说出来,避免让后来人继续这样的错误。
在讲解指针之前,需要理解一下内存空间。内存是随机存取器,计算机上电后便利用内存进行运转。其有一定的容量,为了标识每个存储单元的位置,我们为内存设置了内存地址。内存的具体组织结构可以参考计算机组成原理。
指针是一种指向某种类型的特殊的型别。一般用*定义。如int*p,这样就定义了一个指向int类型的指针。指针用于指向某块内存空间,该内存空间里面存放了其所指向的内存地址。所以,在使用指针之前,必须明白这指针指向了什么内存空间,给指针赋值可以使用取地址符,如p=&a;每次需要访问指针所指向的内容时,便使用解引用符号*进行访问。如:printf(“%d”,*p);
上面简单介绍了下指针的定义,赋值等操作。下面介绍下一些新手容易迷糊的地方吧。
1.char*str1=”abcd”;charstr2[]=”abcd”;的区别
C标准没有规定这两种定义字符串的方式的差别。但是,指针类型的字符串一般不允许修改。如:str1[0]=’c’;这样的语句会导致运行时错误。错误类型:不允许写入什么的。据说,在某些编译器中可以设置成可以修改的。
2.指针/数组作为参数进行传递
在C语言中,参数是使用值传递的。
intfunc;当调用者调用该函数的时候将传递一个值给a,这个a只是你传递进去的参数的一个副本。而数组传递的时候,会退化为指针,其将数组的首地址复制给形参。看下面的一个例子。

分解质因数

图片 7图片 8

 1 /* 2 题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。 3 程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: 4 如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。 5 如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n, 6   重复执行第一步。 7 如果n不能被k整除,则用k 1作为k的值,重复执行第一步。 8 */ 9 10 #include <stdio.h>11 #include <math.h>12 13 main()14 {15     int n,i;16     printf("please input a number:n");17     scanf("%d",&n);18     printf("%d=",n);19     for(i=2;i<=sqrt;i  )20     {21         while(n!=i)22         {23             if(n%i==0)24             {25                 printf("%d*",i);26                 n=n/i;27             }28             else29                 break;30         }31     }32     printf("%d n",n);33 }

View Code

函数指针和指针函数
在计算机内存中,所有的数据都有唯一的地址,当然可运行的程序也是有地址的。函数代码是程序的算法指令部分,它们和数组一样也占用存储空间,都有相应的地址。可以使用指针变量指向数组的首地址,也可以使用指针变量指向函数代码的首地址,指向函数代码首地址的指针变量称为函数指针。定义形式为:函数类型;如:int(chara[],intnlength)。不过,我们经常会遇到这样的定义方式:typedefint(chara[],intnlength);其实使用typedef主要是为了定义函数指针方便,不需要每次都敲那么的代码。(其实懒也是技术驱动的一种动力啊!)我这里就简单的介绍点东西。在搞算法的时候,函数指针大有用处,可以用它实现很多beautiful算法。比如那些自动机等等。

函数区间求最大值

图片 9图片 10

 1 /* 2 编程:设x取值为区间[1,20]的整数,求函数f=x-sin- cos的最大值 3 要求使用自定义函数实现f功能 4 */ 5  6 /* 7 *  @author: 成鹏致远  8 *  @net: http://infodown.tap.cn 9 */10 11 #include "stdio.h"12 #include "math.h"13 double f()14 {15    int i;16    double max=0,x;17    for(i=1;i<=20;i  )18    {19      x=i-sin-cos;20      if(x-max>1e-6)21        max=x;22    }23    return max;24 25 }26 main()27 {28     printf("%lf",f;29     getchar();30 }

View Code

动态开辟数组
指针可以用来分配内存,作为数组来使用。
开辟一维数组:int*pArr=malloc(10*sizeof;释放空间:free;
开辟二维或者多维数组需要分级申请内存:int**pArr;
pArr=malloc(sizeof;
for(i=0;i<3;i )
*=malloc(sizeof;
当然释放空间的时候也需要分级释放咯; for(i=0;i<3;i )free);

猴子吃桃问题

图片 11图片 12

 1 /* 2 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个 3     第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下 4     的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少。 5 1.程序分析:采取逆向思维的方法,从后往前推断。 6 */ 7  8 /* 9 *  @author: 成鹏致远 10 *  @net: http://infodown.tap.cn11 */12 13 #include <stdio.h>14 15 int main(void)16 {17     int day,x1,x2;18     day=9;19     x2=1;20     while(day>0)21     {22         x1=(x2 1)*2;23         x2=x1;24         day--;25     }26     printf("the total is %d n",x1);27 28     return 0;29 }

View Code

C/C code?

古代买鸡问题

图片 13图片 14

 1 /* 2 编程解决如下问题:鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一。 3 百钱买百鸡,问鸡翁,鸡母,鸡雏各几何? 4  5 解决方案:数学问题,先用数学方法解决 6 1、设鸡翁、鸡母、鸡雏分别a、b、c只 7 2、5a 3b c/3=100 8 3、a b c=100 9 4、解得:b=/4;10        c=/4;11 12 */13 14 /*15 *  @author: 成鹏致远 16 *  @net: http://infodown.tap.cn17 */18 19 #include<stdio.h>20 21 void main()22 {23     int a,b,c;24     for(a=0;a<20;a  )25     {26         b=(100-7*a)/4;27         c=(300 3*a)/4;28         if(a b c==100&&a>=0&&b>=0&&c>=0)29         {30                 printf("%d,%d,%dn",a,b,c);31         }32     }33 }

View Code

1234567891011121314151617 voidCreateList(LinkNode**header) { inti=0; =(LinkNode*)malloc(sizeof); ->Elem=10; ->next=NULL; } intmain() { PLinkListhead=NULL; CreateList(&head); if(head!=NULL) printf("%dn",head->Elem); free; return0; }

本文由新金沙平台发布于新金沙平台,转载请注明出处:树状数组,C语言复习笔记

关键词: 新金沙平台

上一篇:从头开始,负载均衡原理
下一篇:没有了