简单acm模板.docx

杂乱小模板状态dp小技巧x&-x是取x的最后一个1的位置。x-=x&-x是去掉x的最后一个1。读入外挂int nxt_int()/ neg or pos char ch; int flag = 0, tmp = 0; for (ch = getchar(); ch 9; ch = getchar() if (ch = int(-) break; if (ch = int(-) flag = 1; else tmp = int(ch) - 0; for (ch = getchar(); 0 = ch & ch = 9; ch = getchar() tmp = tmp * 10 + int(ch) - 48; return (flag) ? -tmp : tmp; 关于N个小球放M个盒子解答之白肉版图片：TMD,刚才论坛好像出问题了，半天都发不出去，烦。n个球放入m个箱子里，有多少种不同的放法（不一定是球和箱子，也可能是其他的元素与其他的放置位置,例如N个人分到M个单位，每班至少一人，里面已经暗中说明球不同，单位不同）看似很简单的问题其实非常复杂，球是否相同，箱是否相同？是否允许有空盒不难看出一共8类情况1）球同，盒同，无空箱2）球同，盒同，允许空箱3）球同，盒不同，无空箱4)球同，盒不同，允许空箱5)球不同，盒相同，无空箱6）球不同，盒相同，允许空箱7)球不同，盒不同，无空箱6）球不同，盒不同，允许空箱-先来看3,4.这个就是最典型的公考中经常遇见的插板法（关于插板法的解释我懒的说了，自己搜，论坛百度都容易找的到）只是需要注意是否允许空箱3的公式是把n个球排成一排，（一种方法），它们中间有n-1个空。取m-1个小棍，放到空上，就把它们分成m部分，由于小棍不相邻，所以没有空箱子。它的方法数有C(N-1,M-1),也就是球减1里面挑M-1个箱子做组合4的公式在3的基础上升华出来的，为了避免空箱子，先在每一个箱子假装都放一个球，这样就有n+m个球，C（n+m-1,m-1)，多了M个元素而已-关于1,2类情况，本来我想教大家一个特殊三角形的，但画起来比较麻烦，速度还不如穷举快，所以就略了，愿意学的我还是可以教他，不会真的还不如穷举来的快。个人建议还是用最常见的凑数法，而且公考中不会出现球和盒子数字比较大的情况。法，例如7个相同球放入4个相同盒子，每盒至少一个（1号情况），则先4个盒子每个放1个，多余3个。只需要考虑这3个球的去处就OK,由于盒子相同，所以只需要凑数就OK,不必考虑位置。比如300，211，111只有三种例如7个相同球放入4个相同盒子，可以空盒，则还是凑数，大的化小的，小的化更小的。0，0，0，70，0，1，60，0，2，50，0，3，40，1，1，50，1，2，40，1，3，30，2，2，31，1，1，41，1，2，31，2，2，211种1，2，3，4公考常见类型，必须学会！-1234都是球相同的情况。但如果球不同怎么办？先来分析最特殊的8号：N球不同，M箱不同，允许空。每个球都有M种选择，N个球就有M的N次方分法。关于5，6，7这情况，我先教大家一个非常特殊的三角形，这个你在狗哥百度非常难以找的到的，秘传型，一般人我不会告诉他的。我画了个图，如果看不到的话直接看这个地址/upload/1245501262x1996894379.jpg看起来很复杂，其实很简单第一左右两边都是1，第几行就有几个数，比如第5行就是1XXX1第2 S（n,k)=S(n-1,k-1)+k*S(n-1,k)，含义是第N排的第K个数等于他上一排的上一个位置数字加上一排的同样位置数字的K倍例如S（7，3）就是第7排第3个数字，所以他等于上排第6排第2个数字+第6排第3个位置*3所以画图的话，明显第1排是1，第2排1，1，推理第3排（左右两边都是1，只有中间那个数字没确定）所以S(3,2)=第2排第1个数字+第2排第2个数字两倍=1+1*2=3，所以第3排数字就是1,3,1.同理S(4,2)=S(3,1)+2*S(3,2)=1+2*3=7,S(4,3)=S(3,2)+3*S(3,3)=3+3*1=6.如此类推三角形-当遇见类型5即：N不同球，M同箱子，无空箱。一共有S(N,M)种分法，比如7个不同球，4个相同箱子，每个箱子至少一个，则看三角形的第7行，第4个数字多少。而类型6，N不同球，M同箱，允许空的时候（在类型5的基础上允许空箱）。明显是N个球不变，一个空箱子都没有+有一个空箱子+有两个空箱子+有三个空箱子+，都装在一个箱子。说的简单点一共有就是S(N,1)+S(N,2)+S(N,3)+.S(N,M)=也就是说第N排开始第1个数字一直加到第M个数字就是总的分法-而类型7同样是在类型5的基础上升华，因为5是箱同的，而7箱不同，所以箱子自身多了P(M,M)=M!倍可能所以类型7的公式就是M!乘以S(N,M)/*筛法打素数表*/*函数作用是打不超过n的所有素数*注意n不能超过上限 会数组越界和超时*返回值是素数表中素数个数 _prime储存素数*_prime一定是数组的指针*/int print_prime(int n,int *_prime)bool sign200000;memset(sign,0,sizeof(sign);sign1=true;/对于认为1是素数的题我们可以把这句话注释掉int i,j,k;for(i=4;i=n;i+=2)signi=true;for(i=3;i=n;i+=2)if(!signi)k=2*i;for(j=i*i;j=n;j+=k)signj=true;memset(_prime,0,sizeof(_prime);int num=0;for(i=1;i1;return ans;判断是不是质数bool is_prime(int x)int i;if(x2&x%2=0)return false;for(i=3;i*ix;i+=2)if(x%i=0)return false;return true;/*最大公约数和最小公倍数*/long long gcd(long long a,long long b)long long temp;while(b)temp=b;b=a%b;a=temp;return a;long long lcm(long long a,long long b)return a /gcd(a,b) *b;/*格式化输入输出*/a 符号 作用 %d 十进制有符号整数 %u 十进制无符号整数 %f 浮点数 %s 字符串 %c 单个字符 %p 指针的值 %e 指数形式的浮点数 %x, %X 无符号以十六进制表示的整数 %o 无符号以八进制表示的整数 %g 自动选择合适的表示法 说明: (1). 可以在%和字母之间插进数字表示最大场宽。 例如: %3d 表示输出3位整型数, 不够3位右对齐。 %9.2f 表示输出场宽为9的浮点数, 其中小数位为2, 整数位为6, 小数点占一位, 不够9位右对齐。 %8s 表示输出8个字符的字符串, 不够8个字符右对齐。 如果字符串的长度、或整型数位数超过说明的场宽, 将按其实际长度输出。 但对浮点数, 若整数部分位数超过了说明的整数位宽度, 将按实际整数位输出; 若小数部分位数超过了说明的小数位宽度, 则按说明的宽度以四舍五入输出。 另外, 若想在输出值前加一些0, 就应在场宽项前加个0。 例如: %04d 表示在输出一个小于4位的数值时, 将在前面补0使其总宽度 为4位。 如果用浮点数表示字符或整型量的输出格式, 小数点后的数字代表最大宽度, 小数点前的数字代表最小宽度。 例如: %6.9s 表示显示一个长度不小于6且不大于9的字符串。若大于9, 则 第9个字符以后的内容将被删除。 (2). 可以在%和字母之间加小写字母l, 表示输出的是长型数。 例如: %ld 表示输出long整数 %lf 表示输出double浮点数 (3). 可以控制输出左对齐或右对齐, 即在%和字母之间加入一个- 号可 说明输出为左对齐, 否则为右对齐。 例如: %-7d 表示输出7位整数左对齐 %-10s 表示输出10个字符左对齐 2. 一些特殊规定字符 /*立方之和和*/13+23+.+n3=n2(n+1)2/4=n(n+1)/22/*平方之和*/1/6*n*(n+1)*(2*n+1);/*k次方之和*/*完全数*-/16 228 3496 48128 533550336 68589869056 7137438691328 82305843008139952128 92658455991569831744654692615953842176 10191561942608236107294793378084303638130997321548169216 1113164036458569648337239753460458722910223472318386943117783728128 1214474011154664524427946373126085988481573677491474835889066354349131199152128/*/*/*梅森素数*/nMnMn的位数12312371353124712735138191461713107167195242876831214748364710961230584300921369395119108961897001944956211127111071622592760102881273312127170141183884105727391352168647976611505715115714607531137992031728127183151,279104079321168729087386162,203147597991697771007664172,281446087557132836351687183,217259117086909315071969194,2531907970073504849911,281204,4232855425426085806071,332219,6894782202782257541112,917229,9413460882827894635512,9932311,2132814112016963921913,3762419,9374315424799680414716,0022521,7014486791665118827516,5332623,2094028741157792645116,9872744,49785450982401122867113,3952886,24353692799543343820725,96229110,50352192831346551500733,26530132,04951274027673006131139,75131216,09174609310381552844765,05032756,839174135906544677887227,83233859,433129498125500142591258,716341,257,787412245773089366527378,632351,398,269814717564451315711420,921362,976,221623340076729201151895,932373,021,377127411683024694271909,526386,972,5934370757449241937912,098,9603913,466,9179249477382562590714,053,94640*20,996,0111259768958556820476,320,43041*24,036,5832994104297339694077,235,73342*25,964,9511221646305770772477,816,23043*30,402,4573154164756529438719,152,05244*32,582,6571245750260539678719,808,35845*37,156,66720225440630822092711,185,27246*42,643,80116987351656231475112,837,06447*43,112,60931647026969715251112,978,189/*KMP*/void getnext(char str,int next)int len=strlen(str);int i=0;nexti=-1;int j=-1;while(ilen)if(j=-1|stri=strj)i+;j+;nexti=j;elsej=nextj;int KMP(char str1,char str2,int pos,int next)int len1=strlen(str1);int len2=strlen(str2);int i,j;i=pos;j=0;while(ilen1&jlen2)if(j=-1|str1i=str2j)i+;j+;elsej=nextj;if(j=len2)return i-len2;return -1;/树状数组/Codeint lowbit(int x)/计算lowbit return x&(-x);void add(int i,int val)/将第i个元素更改为val while(i0) s+=ci; i-=lowbit(i); return s;/* 关于分割平面的探讨*/1.直线(Line)分割平面由于第n条直线与前n-1条直线相交于n-1个点，这n-1个点将第n条直线划分为n个部分，而这第n条直线的两边分别有L(n-1)和n个部分。故L(n)=L(n-1)+n L(0) = 12.一次折线(Zig)分割平面由于一条一次折线相对于两条直线相交少了两个部分，所以Z(n) = L(2n) - 2n Z(0) = 23.Z型折线(Zig-zag)分割平面Z型线与三条之间很相似，但是有两条平行，这样就少了1个部分，如果再将有两条直线平行的三条直线变为Z型的话，则又将少4个部分，这样每个Z型折线比三条直线分平面形成的部分少5个。故ZZ(n) = L(3n)-5nP.S.对于2,3而言由于后面的图形与前面的图形相交时要获得尽量多的区间，所以交点不会在顶点处，既然不在顶点处，那么本来这个图形相比直线而言少了几个区间，与其他图形相交后仍然少那几个区间4.圆(Circle)相交第n个圆与前n-1个圆相交于2(n-1)个点，这2(n-1)个点将第n个圆划分为2(n-1)个圆弧，这每条弧都将原来的一个旧区域一分为二。故C(n) = C(n-1) + 2(n-1) C(0) = 15.平面(Flat)分割空间第n个平面与前n-1个平面有n-1条交线，这n-1条交线分割第n个平面为L(n-1)个区域，则在这个平面的两侧分别把空间分为F(n-1)和L(n-1)个区域，故F(n) = F(n-1) + L(n-1)6.对没有三条对角线交于一点的凸多边形，计算各边和对角线组成的互不重叠的区域个数 我们从各区域的顶点总数和所有区域的内角和的总和两个角度进行分析： 设：Nk为区域中k边形的个数。 角度1：各区域顶点总数(包括重复计算的数目)的等式为 3N3 + 4N4 + . + mNm = 4C(n,4) + n(n-2) (等式1) 其中m是各区域边数的最大值，n是凸多边形的顶点数。 左式表示的各区域顶点总数来自两个方面： 由于每两条对角线(或四个顶点)决定一个内部区域的顶点,因此区域的顶点数是4C(n,4),即每个内部顶点在左式中计数4次(总是四个区域公共一个顶点).又因为在计算中,凸多边形的每个顶点(为n-2个三角型的公共顶点)重复计数