实小社团练习赛15
本文总阅读量次
7985,2765,3484,7602
T1
模拟
多想例子测试,犯错的想数据不全.
T2
计数+枚举
因为变量最多有20个值,如果直接枚举,
仔细阅读,发现题目要求的是结果等于偶数的方案数。那我们不妨求出一个变量偶数和奇数出现的次数,那么每个变量状态只有2个,则
大致算法框架:
...
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 +=乘法原理计算满足条件的方案数;
}
}
...
提示
不想用
int num[256][2];
注意数据范围,测试数据要全面。
T3
数论:算数基本定理
用分解质因数求出1~N的因数出现个数(计数),然后用算术基本定理计算结果。
算术基本定理
例如,100分解质因数为
T4
深搜
对每一根竹子,有
- 去组合
长度 - 去组合
长度 - 去组合
长度 - 放弃这根竹子
也就是只考虑合并,缩短和延伸只在方案出来的时候,跟目标值进行差值计算,所有组合方案都考虑过,自然也找到了最优解
时间复杂度,深搜算法大致如下:
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,合并次数);
}