第二周 1.24-1.30

1.24

sbsbsbsbsbsb

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL x[2222], y[2222], d1[2222], d2[2222];
 7 int n;
 8 
 9 LL cal(LL x)
10 {
11     LL ret = 0LL;
12     for(int i = 0; i < n; i++)
13     {
14         if(d1[i] <= x) continue;
15         ret = max(ret, d2[i]);
16     }
17     return ret;
18 }
19 
20 int main(void)
21 {
22     LL x1, y1, x2, y2;
23     scanf("%d %I64d %I64d %I64d %I64d", &n, &x1, &y1, &x2, &y2);
24     for(int i = 0; i < n; i++) scanf("%I64d %I64d", x + i, y + i);
25     for(int i = 0; i < n; i++)
26     {
27         LL xx = x1 - x[i], yy = y1 - y[i];
28         d1[i] = xx * xx + yy * yy;
29         xx = x2 - x[i], yy = y2 - y[i];
30         d2[i] = xx * xx + yy * yy;
31     }
32     LL ans = cal(0);
33     for(int i = 0; i < n; i++)
34         ans = min(ans, d1[i] + cal(d1[i]));
35     printf("%I64d
", ans);
36     return 0;
37 }

Aguin

CF 617 E XOR and Favorite Number

逗号和自增混用，位运算和比较的优先级。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 1e5 + 10;
 8 int block, a[maxn], b[maxn];
 9 LL cnt[2222222];
10 LL ans[maxn];
11 
12 struct query
13 {
14     int id, l, r;
15 }Q[maxn];
16 
17 bool cmp(query A, query B)
18 {
19     if(A.l / block != B.l / block) return A.l / block < B.l / block;
20     return A.r < B.r;
21 }
22 
23 int main(void)
24 {
25     int n, m, k;
26     scanf("%d%d%d", &n, &m, &k);
27     for(int i = 1; i <= n; i++) scanf("%d", a + i), b[i] = b[i-1] ^ a[i];
28     for(int i = 0; i < m; i++) scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;
29     block = sqrt(n), sort(Q, Q + m, cmp);
30     LL tmp = 0LL;
31     int L = 1, R = 0;
32     for(int i = 0; i < m; i++)
33     {
34         while(R < Q[i].r) {cnt[b[R]]++; R++; tmp += cnt[k^b[R]];}
35         while(R > Q[i].r) {tmp -= cnt[k^b[R]]; R--; cnt[b[R]]--;}
36         while(L < Q[i].l) {L++; --cnt[b[L-2]]; tmp -= cnt[k^b[L-2]] + ((b[L-2] ^ b[R])== k ? 1LL : 0LL);}
37         while(L > Q[i].l) {tmp += cnt[k^b[L-2]] + ((b[L-2] ^ b[R]) == k ? 1LL : 0LL); cnt[b[L-2]]++; L--;}
38         ans[Q[i].id] = tmp;
39     }
40     for(int i = 0; i < m; i++) printf("%I64d
", ans[i]);
41     return 0;
42 }

Aguin

HDU 5613 Baby Ming and Binary image

DEBUG力丧失。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int G[33][333], ans[33][333], cpy[33][333];
 6 int n, m;
 7 
 8 int cal(int i, int j)
 9 {
10     int ret = 0;
11     for(int x = -1; x <= 1; x++)
12     {
13         for(int y = -1; y <= 1; y++)
14         {
15             int xx = i + x, yy = j + y;
16             if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
17             ret += ans[xx][yy];
18         }
19     }
20     return ret;
21 }
22 
23 bool judge(int r)
24 {
25     memset(ans, 0, sizeof(ans));
26     for(int i = 1; i < n - 1; i++) ans[i][0] = ( r & (1 << (i-1) ) ) ? 1 : 0 ;
27     for(int y = 0; y < m - 1; y++)
28     {
29         for(int x = 0; x < n - 2; x++)
30         {
31             int tmp = cal(x, y);
32             if(tmp == G[x][y]) continue;
33             if(tmp == G[x][y] - 1) ans[x+1][y+1] = 1;
34             else return false;
35         }
36         if(G[n-2][y] != cal(n-2, y) || G[n-1][y] != cal(n-1, y)) return false;
37     }
38     for(int x = 0; x < n; x++) if(cal(x, m-1)!=G[x][m-1]) return false;
39     return true;
40 }
41 
42 int main(void)
43 {
44     int T;
45     scanf("%d", &T);
46     while(T--)
47     {
48         scanf("%d%d", &n, &m);
49         for(int i = 0; i < n; i++)
50             for(int j = 0; j < m; j++)
51                 scanf("%d", &G[i][j]);
52         int cnt = 0;
53         for(int i = 0; i < (1 << (n-2)); i++)
54             if(judge(i)) cnt++, memcpy(cpy, ans, sizeof(cpy));
55         if(cnt == 1)
56         {
57             for(int i = 0; i < n; i++)
58             {
59                 for(int j = 0; j < m - 1; j++) printf("%d ", cpy[i][j]);
60                 printf("%d
", cpy[i][m-1]);
61             }
62         }
63         else if(cnt > 1) puts("Multiple");
64         else puts("Impossible");
65     }
66     return 0;
67 }

Aguin

1.25-1.29

什么都没干。

1.30

HDU 5616 Jam's balance

DP写挫。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int ok[2222], cpy[2222];
 6 
 7 int main(void)
 8 {
 9     int T;
10     scanf("%d", &T);
11     while(T--)
12     {
13         int N;
14         scanf("%d", &N);
15         memset(ok, 0, sizeof(ok));
16         ok[0] = 1;
17         for(int i = 0; i < N; i++)
18         {
19             int w;
20             scanf("%d", &w);
21             memcpy(cpy, ok, sizeof(cpy));
22             for(int j = 0; j <= 2000; j++)
23             {
24                 if(!cpy[j]) continue;
25                 ok[j+w] = 1;
26                 if(j > w) ok[j-w] = 1;
27                 else ok[w-j] = 1;
28             }
29         }
30         int M;
31         scanf("%d", &M);
32         while(M--)
33         {
34             int k;
35             scanf("%d", &k);
36             if(k > 2000) puts("NO");
37             else puts(ok[k] ? "YES" : "NO");
38         }
39     }
40     return 0;
41 }

Aguin