网站中的图片必须用 做吗,我的深圳app官网下载,绝唯cms网站管理系统,wordpress 函数教程视频题目
2990:符号三角形 总时间限制: 1000ms 内存限制: 65536kB 描述 符号三角形的第1行有n个由“”和”-“组成的符号 #xff0c;以后每行符号比上行少1个#xff0c;2个同号下面是”“#xff0c;2个异号下面是”-“ 。计算有多少个不同的符号三角形#xff0c;使其所含”…题目
2990:符号三角形 总时间限制: 1000ms 内存限制: 65536kB 描述 符号三角形的第1行有n个由“”和”-“组成的符号 以后每行符号比上行少1个2个同号下面是”“2个异号下面是”-“ 。计算有多少个不同的符号三角形使其所含”“ 和”-“ 的个数相同。
n7时的1个符号三角形如下: 输入 每行1个正整数n24,n0退出. 输出 n和符号三角形的个数. 样例输入 15 16 19 20 0 样例输出 15 1896 16 5160 19 32757 20 59984
理解
字符串由±符号组成两两异或运算±-–得到少一个字符的下一行一直到一行只有一个字符。 问最后字符三角形±号数量相同的情况有几种。 1.枚举 3位时加的情况有 0000 ±0011 ±0102 ±-0113 -1004 -±1015 –1106 —1117 就是0到7对应的二进制用异或运算得到所有行符号。 3216是偶数有可能有±符号的数量相同的字符三角形。 但是5432115奇数就不可能±号数相同。 负号或加号数等于3216的一半就是一样。 或者3*(31)/43也可以。
代码
#include bits/stdc.h using namespace std; int x,l,r; bool k[25][25]; void view(int n,int d){ coutd“长”nendl; for(int i1;in;i){ for(int j1;jn-i1;j)coutk[i][j] “; coutendl; } } int setk(int n,int d){ int he0;//正号或负号数 for(int in;i1d;i–){//转换成对应二进制 k[1][i]d%2;//如果是1是就是正号或符号 hek[1][i]; d/2; } for(int i2;in;i)//第二行开始 for(int j1;jn-i1;j){ k[i][j]k[i-1][j]^k[i-1][j1];//当前行的正负号 hek[i][j]; } return he;// } int main(){ freopen(“data.cpp”,“r”,stdin); while(cinxx){ memset(k,0,sizeof(k)); r0; for(int i0;ix;i)rpow(2,i);//二进制几位全是1时对应的十进制数 int he0,f; if((x*(x1)/2)%2!1) for(int d0;dr;d){ //coutdendl; fsetk(x,d); if(fx*(x1)/4){//正号或符号的数时三角形的一半就对 //view(x,d); he; } } coutx” heendl; } return 0; }
递归回溯
把所有可能数转换成对应二进制有些麻烦。可以用递归回溯。 该位置成1 递归调用传递正号或负号数下位在深一层成1一直到最后一位下一位。 此时没有字符可以成1计算下几行如果正号或负号数等于n*(n1)/4(n个符号)就多个正负号数一样字符三角形。 递归出口是比字符数多两个。 递归后回到上一层刚才成1的字符再变回0就可以凑出所有的二进制数。也达到了枚举的效果。只是不用每次将整数转换成二进制只多一层就能多个二进制。
递归回溯代码
#include bits/stdc.h using namespace std; int x,he; bool k[25][25]; void go(int n,int f){//n是从几位开始f是正号或负号数 if(fx*(x1)/4)return;//超过一半就作废剪枝 if(n**x1**)return;//超过x位2个数是递归出口 for(int in;ix;i){//每次遍历当前位到最后一位 k[1][i]1;//成1 go(i1,fk[1][i]);//递归下一位而且改变符号数 k[1][i]0;//恢复 } for(int i2;ix;i)//二行开始计算剩下的符号 for(int j1;jx-i1;j){ k[i][j]k[i-1][j]^k[i-1][j1]; fk[i][j]; } if(fx*(x1)/4){//全部n位递归后如果正负号数相等 he; } } int main(){ //freopen(“data.cpp”,“r”,stdin); while(cinxx){ memset(k,0,sizeof(k)); he0; if((x*(x1)/2)%2!1)go(1,0); coutx heendl; } return 0; }
