提供网站建设工具,招聘网站制作公司,如何清空网站空间,工商红盾网查询系统题目是输入一个数字#xff0c;分解成三个数字的和#xff0c;这三个数字都不相同#xff0c;并且都不可以被三整除#xff0c;如果存在输出YES并且输出任意一组可能的三个数字#xff0c;否则输出NO
代码
#includebits/stdc.h
using namespace std;int main()
…题目是输入一个数字分解成三个数字的和这三个数字都不相同并且都不可以被三整除如果存在输出YES并且输出任意一组可能的三个数字否则输出NO
代码
#includebits/stdc.h
using namespace std;int main()
{int t;scanf(%d,t);while(t--){int x,y,z;int n;bool flagfalse;scanf(%d,n);for(x1;x10;x){for(yx1;y10;y){zn-x-y;if(x%3!0y%3!0z%3!0zy){printf(YES\n%d %d %d\n,x,y,z);flagtrue;break;}}if(flagtrue) break;}if(!flag) printf(NO\n);}return 0;
}
循环让第二个数字y等于x1就可以保证最开始两个数字就不相等还是这种方法最明了直接条件判断
赛时代码
#includebits/stdc.h
using namespace std;int ans[5];int main()
{int t;scanf(%d,t);while(t--){int n;bool flagfalse;scanf(%d,n);int tempn/3;if(n%30){if(temp%3!0){ans[0]temp-1,ans[1]temp,ans[2]temp1;while((ans[0]%30||ans[2]%30)ans[0]0){ans[0]-1;ans[2]1;}}else{ans[0]temp,ans[1]temp-1,ans[2]temp1;while((ans[0]%30||ans[2]%30||ans[0]ans[1])ans[0]0){ans[0]-1;ans[2]1;}}if(ans[0]ans[1]ans[2]nans[0]%3!0ans[2]%3!0ans[1]%3!0ans[0]!ans[1]ans[0]!ans[2]ans[1]!ans[2]) flagtrue;}else{int qn%3;ans[0]temp,ans[1]temp,ans[2]tempq;if(temp%3!0){ans[0]temp,ans[1]temp,ans[2]tempq;while((ans[0]%30||ans[2]%30||ans[0]ans[1])ans[0]0){ans[0]-1;ans[2]1;}}else{ans[0]temp-1,ans[1]temp1,ans[2]tempq;while((ans[0]%30||ans[2]%30||ans[0]ans[1]||ans[1]ans[2])ans[0]0){ans[0]-1;ans[2]1;}}if(ans[0]ans[1]ans[2]nans[0]%3!0ans[2]%3!0ans[1]%3!0ans[0]!ans[1]ans[0]!ans[2]ans[1]!ans[2]) flagtrue;}if(n3) flagfalse;if(flagtrue) {printf(YES\n);printf(%d %d %d\n,ans[0],ans[1],ans[2]);}else printf(NO\n);}return 0;
}
标签是暴力破解构造算法数学
仔细想了一下确实暴力就可以直接过
我比赛的时候想的方法确实比较繁琐哈哈
讨论输入的数字n是否能够被3整除把数字n除以3然后把这三个数字放在ans[0],ans[1],ans[2]里面保证中间的位置满足不被3整除然后调整ans[0],ans[2]这两个数字ans[0]--,ans[2],一个因子减少一另一个因子增加一和n保持不变所以可以满足条件也可以寻找到答案 另外一种解法
#includebits/stdc.h
using namespace std;int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);if(n%30){int zn-5;if(z%3!0z4) printf(YES\n1 4 %d\n,z);else printf(NO\n);}else{int ansn-3;if(ans%3!0ans2) printf(YES\n1 2 %d\n,ans);else printf(NO\n);}}return 0;
}
上面这种做法是找规律我们只需要输出一种符合条件的情况即可所以我们考虑一些特殊的数字比如说1和2这两个数字不相同并且两个数字的和是3如果数字n是可以被3整除的并且大于3的话如果是3的话剩下的那个数字只可以是0不符合条件剩下的那个数字就一定可以被3整除但是如果n不可以被3整除剩下的那个数也不可以被3整除如果可以被3整除的话n就可以被3整除了
有点绕
分两种特殊情况来考虑第一种特殊情况取x1,y2,这个时候假设n是不能被3整除的数字剩下的那个数字我们记为zz一定是不能被3整除的因为假设z可以被3整除加上3还是可以被3整除加上3就等于n了和假设矛盾所以z一定不能被3整除反证法注意需要满足z大于2这个条件
第二种情况就是取x1,y4,考虑n可以被3整除剩下的数字z一定是不可以被3整除的证明如下还是反证法就是假设z是可以被3整除的假设z3b,n3k,那么有53b3k移向可以得到5/3k-b两个整数的差不可能是小数所以矛盾所以z一定是不可以被3整除的
#includebits/stdc.h
using namespace std;int main()
{int t;scanf(%d,t);while(t--){int n;scanf(%d,n);if(n%30){int zn-5;if(z4) printf(YES\n1 4 %d\n,z);else printf(NO\n);}else{int ansn-3;if(ans2) printf(YES\n1 2 %d\n,ans);else printf(NO\n);}}return 0;
}
经过一通分析之后发现这样子其实更加简洁但是前期需要分析的更多一些
