实小社团练习赛15


本文总阅读量

7985,2765,3484,7602

T1

模拟
多想例子测试,犯错的想数据不全.

T2

计数+枚举
因为变量最多有20个值,如果直接枚举,207=1280000000,必然超时。
仔细阅读,发现题目要求的是结果等于偶数的方案数。那我们不妨求出一个变量偶数和奇数出现的次数,那么每个变量状态只有2个,则27=128,那么就不会超时了,对每种符合要求的情况,使用加乘原理计算。
大致算法框架:

...
for(int B = 0; B < 2; B++)
  for(int E = 0; E < 2; E++)
  for(int S = 0; S < 2; S++)
  for(int I = 0; I < 2; I++)
  for(int G = 0; G < 2; G++)
  for(int O = 0; O < 2; O++)
  for(int M = 0; M < 2; M++) {
    if ((B + E + S + S + I + E) * (G + O + E + S) * (M + O + O)是不是偶数) {
      result +=乘法原理计算满足条件的方案数;
    }
  }
...

提示
不想用AZ对应126025,数组可以开大一点,然后可以直接访问,例如:

int num[256][2];

注意数据范围,测试数据要全面。

T3

数论:算数基本定理
用分解质因数求出1~N的因数出现个数(计数),然后用算术基本定理计算结果。
算术基本定理
例如,100分解质因数为100=2255=2252,那么因数个数为(2+1)(2+1)=9,多算一个是因为还有0次方,原理是乘法原理。

T4

深搜
N最大才8,读题可知,是一道组合题,可以考虑用DFS
对每一根竹子,有4种选择:

  1. 去组合A长度
  2. 去组合B长度
  3. 去组合C长度
  4. 放弃这根竹子
    也就是只考虑合并缩短延伸只在方案出来的时候,跟目标值进行差值计算,所有组合方案都考虑过,自然也找到了最优解
    时间复杂度O(48),深搜算法大致如下:
void dfs(int i, int x, int y, int z, int 合并次数){
    if(i > n){
        if(x&&y&&z){
            ans=min(ans,abs(x-a)+abs(y-b)+abs(z-c)+(合并次数-3)*10);  //想想为什么要减3
        }
        return;
    }
    dfs(i+1,x+l[i],y,z,合并次数+1);  //l数组为保存竹子长度的数组
    dfs(i+1,x,y+l[i],z,合并次数+1);
    dfs(i+1,x,y,z+l[i],合并次数+1);
    dfs(i+1,x,y,z,合并次数);
}

本站总访问量