link:http://acm.hdu.edu.cn/showproblem.php?pid=4696
结论:只要有一个1,就能表示所有的正整数。
思路:好有趣!好有趣! ٩̋(๑˃́ꇴ˂̀๑)۶!
注意到,每一个强连通分量都是一根棒棒糖(一根链 + 一个环)。
把环拆成一条很长很长的链。然后根据尺取思想,只要有1,任何正整数都可以被表示粗来!
#include <iostream> #include <cstdio> using namespace std; const int NICO = 1000000+10; int n, q; int a[NICO], c[NICO]; int main() { while(~scanf("%d %d", &n, &q)) { for(int i=1;i<=n;i++) { scanf("%d", &a[i]); } int ok = 0; for(int i=1;i<=n;i++) { scanf("%d", &a[i]); if(a[i] % 2) ok = 1; } for(int i=1;i<=q;i++) { scanf("%d", &c[i]); printf("%s ", (ok||c[i]%2==0) && (c[i]>0) ?"YES":"NO"); } } }