第二周 7.17-7.23

7.17

HDU 5456 Matches Puzzle Game

没有最丑只有更丑。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 int num[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
 8 LL dp[555][2][2][2][2];
 9 
10 int main(void)
11 {
12     int T;
13     scanf("%d", &T);
14     for(int kase = 1; kase <= T; kase++)
15     {
16         LL n, m;
17         scanf("%I64d %I64d", &n, &m);
18         memset(dp, 0, sizeof(dp));
19         dp[n-3][0][0][0][0] = 1;
20         for(int i = n - 3; i > 0; i--)
21         {
22             for(int p1 = 0; p1 <= 1; p1++)
23             for(int p2 = 0; p2 <= 1; p2++)
24             for(int p3 = 0; p3 <= 1; p3++)
25             for(int k = 0; k <= 1; k++)
26             for(int a = 0; a <= 9; a++)
27             for(int b = 0; b <= 9; b++)
28             {
29                 if(p1 || p2 && b) continue;
30 
31                 int c = a - k - b, nk = 0;
32                 if(c < 0) c += 10, nk = 1;
33                 if(p3 && c) continue;
34 
35                 int tot = num[a];
36                 if(!p2) tot += num[b];
37                 if(!p3) tot += num[c];
38                 if(tot > i) continue;
39 
40                 for(int pp1 = 0; pp1 <= 1; pp1++)
41                 for(int pp2 = 0; pp2 <= 1; pp2++)
42                 for(int pp3 = 0; pp3 <= 1; pp3++)
43                 {
44                     if(p1 && !pp1) continue;
45                     if(p2 && !pp2) continue;
46                     if(p3 && !pp3) continue;
47                     if(pp1 && !(a && !nk)) continue;
48                     if(!p2 && pp2 && !b) continue;
49                     if(!p3 && pp3 && !c) continue;
50                     if(pp1 && !pp2) continue;
51                     if(pp1 && !pp3) continue;
52                     dp[i-tot][pp1][pp2][pp3][nk] = (dp[i-tot][pp1][pp2][pp3][nk] + dp[i][p1][p2][p3][k]) % m;
53                 }
54             }
55         }
56 
57         printf("Case #%d: %I64d
", kase, dp[0][1][1][1][0]);
58 
59     }
60     return 0;
61 }
Aguin

7.18

HDU 5489 Removed Interval

一个BIT可以用三遍西西西

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <map>
 6 #include <vector>
 7 using namespace std;
 8 const int maxn = 1e5 + 10;
 9 int f[maxn], g[maxn], dp[maxn];
10 
11 // BIT
12 int c[maxn];
13 int lowbit(int s)
14 {
15     return s & (-s);
16 }
17 void modify(int i, int x)
18 {
19     while(i < maxn) c[i] = max(c[i], x), i += lowbit(i);
20     return;
21 }
22 int query(int i)
23 {
24     int ret = 0;
25     while(i > 0) ret = max(ret, c[i]), i -= lowbit(i);
26     return ret;
27 }
28 
29 struct node
30 {
31     int a, pos;
32 }p[maxn];
33 bool cmp(node A, node B)
34 {
35     if(A.a != B.a) return A.a < B.a;
36     return A.pos > B.pos;
37 }
38 
39 int main(void)
40 {
41     int T;
42     scanf("%d", &T);
43     for(int kase = 1; kase <= T; kase++)
44     {
45         int N, L;
46         scanf("%d %d", &N, &L);
47         for(int i = 1; i <= N; i++)
48         {
49             scanf("%d", &p[i].a);
50             p[i].pos = i;
51         }
52 
53         memset(c, 0, sizeof(c));
54         sort(p + 1, p + N + 1, cmp);
55         for(int i = 1; i <= N; i++)
56         {
57             int pos = p[i].pos;
58             f[pos] = query(pos) + 1;
59             modify(pos, f[pos]);
60         }
61 
62         memset(c, 0, sizeof(c));
63         for(int i = N; i; i--)
64         {
65             int pos = p[i].pos;
66             g[pos] = query(N - pos + 1) + 1;
67             modify(N - pos + 1, g[pos]);
68         }
69 
70         int ans = 0;
71         memset(c, 0, sizeof(c));
72         for(int i = N; i; i--)
73         {
74             int pos = p[i].pos;
75             if(N - pos - L >= 0) ans = max(ans, query(N - pos - L) + f[pos]);
76             modify(N - pos + 1, g[pos]);
77         }
78         ans = max(ans, query(N - L));
79         printf("Case #%d: %d
", kase, ans);
80 
81     }
82     return 0;
83 }
Aguin

HDU 5517 Triple

好久不见二维树状数组哦。

现已加入豪华午餐。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <map>
 6 using namespace std;
 7 typedef long long LL;
 8 typedef pair<int, int> pii;
 9 typedef pair<int, pii> piii;
10 int ma[111111], cb[111111];
11 map<piii, LL> M;
12 map<piii, LL>::reverse_iterator it;
13 
14 // 2D - BIT
15 const int maxn = 1e3 + 10;
16 int c[maxn][maxn];
17 int lowbit(int s)
18 {
19     return s & (-s);
20 }
21 void modify(int x, int y, int v)
22 {
23     for(int i = x; i < maxn; i += lowbit(i))
24         for(int j = y; j < maxn; j += lowbit(j))
25             c[i][j] += v;
26     return;
27 }
28 int query(int x, int y)
29 {
30     int ret = 0;
31     for(int i = x; i > 0; i -= lowbit(i))
32         for(int j = y; j > 0; j -= lowbit(j))
33             ret += c[i][j];
34     return ret;
35 }
36 
37 int main(void)
38 {
39     int t;
40     scanf("%d", &t);
41     for(int kase = 1; kase <= t; kase++)
42     {
43 
44         int n, m;
45         scanf("%d %d", &n, &m);
46 
47         memset(cb, 0, sizeof(cb));
48         memset(ma, 0, sizeof(ma));
49         for(int i = 1; i <= n; i++)
50         {
51             int a, b;
52             scanf("%d %d", &a, &b);
53             if(a == ma[b]) cb[b]++;
54             if(a > ma[b]) ma[b] = a, cb[b] = 1;
55         }
56 
57         M.clear();
58         for(int i = 1; i <= m; i++)
59         {
60             int c, d, e;
61             scanf("%d %d %d", &c, &d, &e);
62             if(cb[e])
63             {
64                 piii tmp = piii(ma[e], pii(c, d));
65                 M[tmp] = M[tmp] + cb[e];
66             }
67         }
68 
69         LL ans = 0;
70         memset(c, 0, sizeof(c));
71         for(it = M.rbegin(); it != M.rend(); it++)
72         {
73             LL cnt = (*it).second;
74             pii tmp = (*it).first.second;
75             int c = tmp.first, d = tmp.second;
76             if(!query(1001 - c, 1001 - d)) ans = ans + cnt;
77             modify(1001 - c, 1001 - d, 1);
78         }
79 
80         printf("Case #%d: %I64d
", kase, ans);
81 
82     }
83     return 0;
84 }
Aguin

昨天BC2周年没打。补个题。

1004平面最近点对没做过。顺便A了个板子题。

HDU 1007 Quoit Design

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
const double INF = 1e18;

struct point
{
    double x, y;
} p[maxn];

bool cmpx(point A, point B)
{
    return A.x < B.x;
}

bool cmpy(point A, point B)
{
    return A.y < B.y;
}

double dis(point A, point B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) +(A.y - B.y) * (A.y - B.y));
}

double cal(int l, int r)
{
    double d = INF;
    if(l == r) return d;
    if(l + 1 == r) return dis(p[l], p[r]);

    int mid = (l + r) >> 1;
    double d1 = cal(l, mid), d2 = cal(mid + 1, r);
    d = min(d1, d2);

    vector<point> v;
    for(int i = l; i <= r; i++)
        if(abs(p[mid].x - p[i].x) < d)
            v.push_back(p[i]);
    sort(v.begin(), v.end(), cmpy);

    int sz = v.size();
    for(int i = 0; i < sz; i++)
    {
        for(int j = i + 1; j < sz; j++)
        {
            if(v[j].y - v[i].y >= d) break;
            d = min(d, dis(v[i], v[j]));
        }
    }

    return d;
}

int main(void)
{
    int N;
    while(~scanf("%d", &N) && N)
    {
        for(int i = 1; i <= N; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
        sort(p + 1, p + 1 + N, cmpx);
        printf("%.2f
", cal(1, N) / 2);
    }
    return 0;
}
Aguin

HDU 5718 Oracle

最近比较背。于是简单题也写了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn = 1e7 + 10;
 6 char s[maxn];
 7 int cnt[10];
 8 
 9 int main(void)
10 {
11     int T;
12     scanf("%d", &T);
13     while(T--)
14     {
15         scanf("%s", s);
16         int l = strlen(s);
17 
18         memset(cnt, 0, sizeof(cnt));
19         for(int i = 0; i < l; i++) cnt[s[i]-'0']++;
20 
21         int c = 0;
22         for(int i = 1; i <= 9; i++) c += cnt[i];
23         if(c < 2) {puts("Uncertain"); continue;}
24 
25         int p = 0;
26         for(int i = 1; i <= 9; i++)
27         if(cnt[i]) {cnt[i]--, p = i; break;}
28 
29         int pos = 0;
30         for(int i = 0; i <= 9; i++)
31             while(cnt[i]--) s[pos++] = i + '0';
32         s[pos] = '0';
33 
34         s[0] += p;
35         for(int i = 0; i < pos; i++)
36             if(s[i] > '9') s[i] -= 10, s[i+1]++;
37 
38         if(s[pos] != '0') pos++;
39 
40         for(int i = pos - 1; i >= 0; i--) printf("%c", s[i]);
41         puts("");
42 
43     }
44 
45     return 0;
46 }
Aguin

HDU 5719 Arrange

无解情况比较多。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 const LL mod = 998244353;
 6 const int maxn = 1e5 + 10;
 7 int B[maxn], C[maxn];
 8 
 9 int main(void)
10 {
11     int T;
12     scanf("%d", &T);
13     while(T--)
14     {
15         int n;
16         scanf("%d", &n);
17         for(int i = 1; i <= n; i++) scanf("%d", B + i);
18         for(int i = 1; i <= n; i++) scanf("%d", C + i);
19 
20         LL ans = 1;
21         if(B[1] != C[1]) ans = 0;
22         for(int i = 2; i <= n; i++)
23         {
24             if(B[i] > B[i-1]) ans = 0;
25             if(C[i] < C[i-1]) ans = 0;
26             if(B[i] != B[i-1] && C[i] != C[i-1]) ans = 0;
27         }
28 
29         for(int i = 2; i <= n; i++)
30         {
31             if(B[i] != B[i-1] || C[i] != C[i-1]) continue;
32             LL tmp = C[i] - B[i] - i + 2;
33             if(tmp <= 0) ans = 0;
34             else ans = ans * tmp % mod;
35         }
36 
37         printf("%I64d
", ans);
38 
39     }
40 
41     return 0;
42 }
Aguin

HDU 5720 Wool

喜欢无脑丢set。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <set>
 5 using namespace std;
 6 typedef long long LL;
 7 typedef pair<LL, LL> pii;
 8 const int maxn = 1e5 + 10;
 9 LL a[maxn];
10 set<pii> S;
11 set<pii>::iterator it;
12 
13 int main(void)
14 {
15     int T;
16     scanf("%d", &T);
17     while(T--)
18     {
19         S.clear();
20         int n;
21         LL L, R;
22         scanf("%d %I64d %I64d", &n, &L, &R);
23         for(int i = 1; i <= n; i++) scanf("%I64d", a + i);
24         sort(a + 1, a + 1 + n);
25         for(int i = 2; i <= n; i++)
26         {
27             if(a[i] - a[i-1] + 1 > R || a[i] + a[i-1] - 1 < L) continue;
28             LL l = max(L, a[i] - a[i-1] + 1), r = min(R, a[i] + a[i-1] - 1);
29             S.insert(pii(l, r));
30         }
31 
32         LL ans = R - L + 1, tmp = 0;
33         for(it = S.begin(); it != S.end(); it++)
34         {
35             LL l = (*it).first, r = (*it).second;
36             if(r <= tmp) continue;
37             if(l <= tmp) ans -= r - tmp;
38             else ans -= r - l + 1;
39             tmp = r;
40         }
41 
42         printf("%I64d
", ans);
43 
44     }
45     return 0;
46 }
Aguin

HDU 5721 Palace

删点就换了个无穷远点。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long LL;
 7 const int maxn = 1e5 + 10;
 8 const LL INF = 1e18;
 9 
10 struct point
11 {
12     int id;
13     LL x, y;
14 } p[maxn];
15 
16 bool cmpx(point A, point B)
17 {
18     return A.x < B.x;
19 }
20 
21 bool cmpy(point A, point B)
22 {
23     return A.y < B.y;
24 }
25 
26 LL dis(point A, point B)
27 {
28     return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
29 }
30 
31 LL m;
32 point p1, p2;
33 LL cal(int l, int r)
34 {
35     LL d = INF;
36     if(l == r) return d;
37     if(l + 1 == r)
38     {
39         d = dis(p[l], p[r]);
40         if(d < m) p1 = p[l], p2 = p[r], m = d;
41         return d;
42     }
43 
44     int mid = (l + r) >> 1;
45     LL d1 = cal(l, mid), d2 = cal(mid + 1, r);
46     d = min(d1, d2);
47 
48     vector<point> v;
49     for(int i = l; i <= r; i++)
50         if((p[mid].x - p[i].x) * (p[mid].x - p[i].x) < d)
51             v.push_back(p[i]);
52     sort(v.begin(), v.end(), cmpy);
53 
54     int sz = v.size();
55     for(int i = 0; i < sz; i++)
56     {
57         for(int j = i + 1; j < sz; j++)
58         {
59             if((v[j].y - v[i].y) * (v[j].y - v[i].y) >= d) break;
60             d = min(d, dis(v[i], v[j]));
61             if(d < m) m = d, p1 = v[i], p2 = v[j];
62         }
63     }
64 
65     return d;
66 }
67 
68 int main(void)
69 {
70     int T;
71     scanf("%d", &T);
72     while(T--)
73     {
74         int N;
75         scanf("%d", &N);
76         for(int i = 1; i <= N; i++) scanf("%I64d %I64d", &p[i].x, &p[i].y);
77         sort(p + 1, p + 1 + N, cmpx);
78         for(int i = 1; i <= N; i++) p[i].id = i;
79 
80         m = INF;
81         LL ans = cal(1, N) * (N - 2);
82         point M;
83         M.x = M.y = 1e8;
84         int a = p1.id, b = p2.id;
85         swap(M, p[a]);
86         ans = ans + cal(1, N);
87         swap(M, p[a]);
88         swap(M, p[b]);
89         ans = ans + cal(1, N);
90 
91         printf("%I64d
", ans);
92 
93     }
94     return 0;
95 }
Aguin

HDU 5722 Jewelry

想了半天整数扫描线怎么搞……其实浮点数的板，右端点+1就可以了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <map>
  5 #include <vector>
  6 #include <algorithm>
  7 using namespace std;
  8 typedef long long LL;
  9 const int maxn = 1e5 + 10;
 10 map< int, vector<int> > M;
 11 map< int, vector<int> >::iterator it;
 12 
 13 // segment_tree
 14 int a[maxn<<1];
 15 int cnt[maxn<<3], sum[maxn<<3];
 16 struct seg
 17 {
 18     int l, r, h, f;
 19     seg(){}
 20     seg(int L, int R, int H, int F): l(L), r(R), h(H), f(F){}
 21 }S[maxn<<1];
 22 bool cmp(seg A, seg B)
 23 {
 24     return A.h < B.h;
 25 }
 26 void gather(int p, int tl, int tr)
 27 {
 28     if(cnt[p]) sum[p] = a[tr] - a[tl-1];
 29     else if(tl == tr) sum[p] = 0;
 30     else sum[p] = sum[p<<1] + sum[p<<1|1];
 31 }
 32 void modify(int p, int tl, int tr, int l, int r, int v)
 33 {
 34     if(tr < l || r < tl) return;
 35     if(l <= tl && tr <= r) cnt[p] += v;
 36     else
 37     {
 38         int mid = (tl + tr) >> 1;
 39         modify(p<<1, tl, mid, l, r, v);
 40         modify(p<<1|1, mid+1, tr, l, r, v);
 41     }
 42     gather(p, tl, tr);
 43 }
 44 
 45 int main(void)
 46 {
 47     int T;
 48     scanf("%d", &T);
 49     while(T--)
 50     {
 51         int n, x;
 52         scanf("%d %d", &n, &x);
 53         M.clear();
 54         for(int i = 1; i <= n; i++)
 55         {
 56             int y;
 57             scanf("%d", &y);
 58             M[y].push_back(i);
 59         }
 60 
 61         int p1 = 0, p2 = 0;
 62         for(it = M.begin(); it != M.end(); it++)
 63         {
 64             int now = (*it).first;
 65             vector<int> tmp = (*it).second;
 66             int sz = tmp.size();
 67             if(sz < x) continue;
 68             sort(tmp.begin(), tmp.end());
 69             for(int i = 0; i < sz - x + 1; i++)
 70             {
 71                 int x1, x2, y1, y2;
 72                 x1 = i ? tmp[i-1] + 1 : 1;
 73                 x2 = tmp[i];
 74                 y1 = tmp[i+x-1];
 75                 y2 = i == sz - x ? n : tmp[i+x] - 1;
 76                 a[p1++] = x1, a[p1++] = x2 + 1;
 77                 S[p2++] = seg(x1, x2 + 1, y1, 1);
 78                 S[p2++] = seg(x1, x2 + 1, y2 + 1, -1);
 79             }
 80         }
 81 
 82         LL ans = 0;
 83         sort(a, a + p1);
 84         int sz = unique(a, a + p1) - a;
 85         sort(S, S + p2, cmp);
 86         memset(cnt, 0, sizeof(cnt));
 87         memset(sum, 0, sizeof(sum));
 88         for(int i = 0; i < p2; i++)
 89         {
 90             int l = lower_bound(a, a + sz, S[i].l) - a + 1;
 91             int r = lower_bound(a, a + sz, S[i].r) - a;
 92             modify(1, 1, sz, l, r, S[i].f);
 93             ans = ans + sum[1] * (S[i+1].h - S[i].h);
 94         }
 95 
 96         printf("%I64d
", ans);
 97 
 98     }
 99     return 0;
100 }
Aguin
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Aguin/p/5679678.html