本文共 4636 字，大约阅读时间需要 15 分钟。
1. 题目描述
1 /* 1362 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 using namespace std; 24 //#pragma comment(linker,"/STACK:102400000,1024000") 25 26 #define sti set 27 #define stpii set > 28 #define mpii map 29 #define vi vector 30 #define pii pair 31 #define vpii vector > 32 #define rep(i, a, n) for (int i=a;i =a;--i) 34 #define clr clear 35 #define pb push_back 36 #define mp make_pair 37 #define fir first 38 #define sec second 39 #define all(x) (x).begin(),(x).end() 40 #define SZ(x) ((int)(x).size()) 41 #define lson l, mid, rt<<1 42 #define rson mid+1, r, rt<<1|1 43 44 const int maxn = 30; 45 const int maxm = 60; 46 int c[maxn], s[maxn]; 47 int a[maxn], R[maxm]; 48 bool visit[maxm][maxm]; 49 int n, m, bound; 50 bool flag; 51 52 void init() { 53 rep(i, 1, maxn) 54 c[i] = c[i-1] + i*2-1; 55 rep(i, 1, maxn) 56 s[i] = 6 * c[i]; 57 } 58 59 inline bool judge(int x, int y) { 60 return y<=0 || y>bound || x<=0 || x>R[y]; 61 } 62 63 bool check(int x, int y, int n) { 64 if (x & 1) { 65 // straight triangle 66 int yy = y; 67 rep(i, 1, n+1) { 68 int xx = x, l = i*2-1; 69 rep(j, 0, l) { 70 if (judge(xx, yy) || visit[yy][xx]) return false; 71 ++xx; 72 } 73 ++yy; 74 } 75 } else { 76 // reverse triangle 77 int yy = y; 78 int c = 0; 79 per(i, 1, n+1) { 80 int xx = x + c * 2, l = i*2-1; 81 rep(j, 0, l) { 82 if (judge(xx, yy) || visit[yy][xx]) return false; 83 ++xx; 84 } 85 ++c; 86 ++yy; 87 } 88 } 89 return true; 90 } 91 92 void update(int x, int y, int n, bool delta) { 93 if (x & 1) { 94 // straight triangle 95 int yy = y; 96 rep(i, 1, n+1) { 97 int xx = x, l = i*2-1; 98 rep(j, 0, l) { 99 visit[yy][xx] = delta;100 ++xx;101 }102 ++yy;103 }104 } else {105 // reverse triangle106 int yy = y;107 int c = 0;108 per(i, 1, n+1) {109 int xx = x + c * 2, l = i*2-1;110 rep(j, 0, l) {111 visit[yy][xx] = delta;112 ++xx;113 }114 ++c;115 ++yy;116 }117 }118 }119 120 void dfs(int r, int dep) {121 if (dep > bound) {122 flag = true;123 return ;124 }125 126 int rr = r + 1, depp = dep;127 if (r == R[dep]) {128 rr = 1;129 ++depp;130 }131 132 if (visit[dep][r]) {133 dfs(rr, depp);134 } else {135 rep(i, 0, m) {136 int l = a[i];137 if (check(r, dep, l)) {138 update(r, dep, l, true);139 dfs(rr, depp);140 update(r, dep, l, false);141 if (flag) return;142 } else {143 break;144 }145 }146 }147 }148 149 bool judge1() {150 flag = false;151 bound = n;152 memset(visit, false, sizeof(visit));153 rep(i, 1, n+1)154 R[i] = 2*i-1;155 dfs(1, 1);156 return flag;157 }158 159 bool judge2() {160 flag = false;161 bound = n;162 memset(visit, false, sizeof(visit));163 rep(i, 1, n+1)164 R[i] = 2*i-1;165 dfs(1, 1);166 return flag;167 }168 169 bool judge3() {170 flag = false;171 bound = n*2;172 memset(visit, false, sizeof(visit));173 rep(i, 1, n+1) {174 R[i] = n*2 + 2*i-1;175 }176 rep(i, n+1, n*2+1) {177 rep(j, 1, 2*(i-n))178 visit[i][j] = true;179 R[i] = (n + n)*2;180 }181 dfs(1, 1);182 return flag;183 }184 185 void solve() {186 sort(a, a+m);187 rep(i, 0, m) {188 if (n%a[i] == 0) {189 puts("YES");190 return ;191 }192 }193 if (a[0] > n) {194 puts("NO");195 return ;196 }197 198 { // filter unnecessary199 int j = 1;200 201 rep(i, 1, m) {202 if (a[i] > n)203 break;204 bool flag = true;205 rep(k, 0, j) {206 if (a[i]%a[k] == 0) {207 flag = false;208 }209 }210 if (flag)211 a[j++] = a[i];212 }213 m = j;214 }215 216 if (judge1()) {217 puts("YES");218 return ;219 }220 221 if (judge2()) {222 puts("YES");223 return ;224 }225 226 if (judge3()) {227 puts("YES");228 return ;229 }230 231 puts("NO");232 }233 234 int main() {235 cin.tie(0);236 ios::sync_with_stdio(false);237 #ifndef ONLINE_JUDGE238 freopen("data.in", "r", stdin);239 freopen("data.out", "w", stdout);240 #endif241 242 int t;243 244 scanf("%d", &t);245 while (t--) {246 scanf("%d%d", &n,&m);247 rep(i, 0, m)248 scanf("%d", a+i);249 solve();250 }251 252 #ifndef ONLINE_JUDGE253 printf("time = %ldms.\n", clock());254 #endif255 256 return 0;257 }
转载于:https://www.cnblogs.com/bombe1013/p/5597201.html