发表于   |   分类于   |  

250

Description

定义大小为$N$的三角形, 是由若干个等大的圆形构成的, 高度和底宽为$N$,三角形的每个圆染三种颜色$r,g,b$,相接触的圆不能染同种颜色,问有$R$个$r$颜色的球, $G$个$g$颜色的球和$B$个$b$颜色的球, 最多能染多少个大小为$N$的三角形

Solution

稍加分析可以发现，每个三角形三个颜色的球要不是$x,x,x$,要不是$x,x,x+1$这种形式。先考虑$mod3=0$的情况，直接计算即可，$mod3=1$时，先当他们都相同，二分答案，然后check一下多出来的是否可以多出个数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
vector<LL> a;
struct FoxPaintingBalls {
    long long theMax(long long R, long long G, long long B, int N) {
        if (N == 1) return R + G + B;
        a.pb(R), a.pb(G), a.pb(B);
        sort(a.begin(), a.end());
        LL tot = (LL)N * (N + 1) / 2;
        LL x = tot / 3;
        if (tot % 3 == 0) return a[0] / x;
        LL ll = 0, ans = 0, rr = a[0] / x;
        while (ll <= rr) {
            LL mid = (ll + rr) >> 1ll;
            LL r = R - mid * x, g = G - mid * x, b = B - mid * x;
            if (r + g + b >= mid) {
                ans = mid;
                ll = mid + 1;
            }
            else rr = mid - 1;
        }
        return ans;
    }
};

500

Description

大小为$n\times m(n,m<30)$的矩阵, 有$L,P,.,$三种格子, 画两个互不相交的矩形, 使两个矩形$L$和$P$的差不超过$D$, 问这两个矩形最多能包含的$L$和$P$的和。

Solution

考虑一定存在一个分界线将其分为两个矩阵，先暴力$N^6$处理所有分界线，比如$l[i][j]表示第i列左边差为j的最大的花的和$，然后枚举两个矩形内部的差，再枚举分界线，暴力$N^5$计算即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>//enum
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 35;
int L[N][N * N + 1000], R[N][N * N + 1000], D[N][N * N + 1000], U[N][N * N + 1000];
inline void gao(int &x, int y) {
    if (x < y)  x = y;
}
struct FoxAndFlowerShopDivOne {
    int theMaxFlowers(vector <string> s, int maxDiff) {
        memset(L, 0xc0, sizeof(L));
        memset(R, 0xc0, sizeof(R));
        memset(U, 0xc0, sizeof(U));
        memset(D, 0xc0, sizeof(D));
        int n = s.size(), m = s[0].size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) 
                for (int k = i; k < n; ++k)
                    for (int l = j; l < m; ++l) {
                        int suml = 0, sump = 0;
                        for (int p = i; p <= k; ++p)
                            for (int q = j; q <= l; ++q) {
                                suml += s[p][q] == 'L';
                                sump += s[p][q] == 'P';
                            }
                        int sum = suml + sump, dif = suml - sump + 1000;
                        gao(D[i][dif], sum);
                        gao(R[j][dif], sum);
                        gao(U[k][dif], sum);
                        gao(L[l][dif], sum);
                    }
        for (int i = 1; i < n; ++i) 
            for (int j = 0; j < N * N + 1000; ++j)
                U[i][j] = max(U[i][j], U[i - 1][j]);
        for (int i = n - 2; i >= 0; --i)
            for (int j = 0; j < N * N + 1000; ++j)
                D[i][j] = max(D[i][j], D[i + 1][j]);
        for (int j = 1; j < m; ++j)
            for (int k = 0; k < N * N + 1000; ++k)
                L[j][k] = max(L[j][k], L[j - 1][k]);
        for (int j = m - 2; j >= 0; --j)
            for (int k = 0; k < N * N + 1000; ++k)
                R[j][k] = max(R[j][k], R[j + 1][k]);
        int ans = -1;
        for (int i = -n * m; i <= n * m; ++i)
            for (int j = -n * m; j <= n * m; ++j) {
                for (int h = 0; h < n - 1; ++h) 
                    if (abs(i + j) <= maxDiff)  ans = max(ans, U[h][i + 1000] + D[h + 1][j + 1000]);
                for (int l = 0; l < m - 1; ++l)
                    if (abs(i + j) <= maxDiff)  ans = max(ans, L[l][i + 1000] + R[l + 1][j + 1000]);
            }
        return ans;
    }
};

发表于   |   分类于   |  

250

Description

题意：一个长度最多$50$的字符串，每次操作可以交换相邻的两个字符，问，经过最多$MaxSwaps$次交换之后，最多能让多少个相同的字符连起来

Solution

枚举一个字符，让其他字符往这里即可，取最小即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct ColorfulChocolates {
    int maximumSpread(string chocolates, int maxSwaps) {
        int ans = 0;
        int n = chocolates.size();
        for (int i = 0; i < n; ++i) {
            string s = chocolates;
            int now = 1;
            vector<int> a;
            for (int j = i - 1; j >= 0; --j)
                if (s[j] == s[i])   a.pb(i - j - now), ++now;
            now = 1;
            for (int j = i + 1; j < n; ++j)
                if (s[j] == s[i])   a.pb(j - i - now), ++now;
            sort(a.begin(), a.end());
            int cnt = maxSwaps;
            int t = 1;
            for (int i = 0; i < a.size(); ++i)
                if (cnt - a[i] >= 0) {
                    cnt -= a[i];
                    ++t;
                }
            ans = max(ans, t);
        }
        return ans;
    }
};

450

Description

一个有向图，顶点标号$0\sim n-1$，每个点会选择优先走他能到达的编号最小的点，现在想通过去掉一些边使得可以从$0$走到$n-1$,求最少要去掉的边数

Solution

考虑类似于$floyd$的做法，$d[i][j]$表示$i$走到$j$需要最少删多少条边，直接$dp$即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>//dp
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55, inf = 1e6;
int d[N][N];
struct ColorfulWolves {
    int getmin(vector <string> colormap) {
        int n = colormap.size();
        for (int i = 0; i < n; ++i) {
            int now = 0;
            for (int j = 0; j < n; ++j) {
                if (colormap[i][j] == 'Y')  d[i][j] = now++;
                else d[i][j] = inf;
            }
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        return d[0][n - 1] == inf ? -1 : d[0][n - 1];
    }
};

发表于   |   分类于   |  

300

Description

有个机器人，从某一点出发，他只有碰到地形边缘或者碰到走过的点时才会改变运动方向，然后接着走，现在给出他的运动轨迹，判断他的运动是否合法，如果合法的话，那么整个地形的最小面积是多少。每次走的步数$\le 50$

Solution

先确定最大的最小的$x,y$,然后进行验证，如果走到重复的地方或者不应该转弯时转弯则不合法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
const int N = 205;
bool vis[N][N];
struct RotatingBot {
    int minArea(vector <int> moves) {
        int n = moves.size();
        int x = 100, y = 100;
        int mxx = 100, mxy = 100, mnx = 100, mny = 100;
        for (int i = 0; i < n; ++i) {
            int dir = i % 4;
            int tx = x + dx[dir] * moves[i];
            int ty = y + dy[dir] * moves[i];
            mxx = max(mxx, tx), mnx = min(mnx, tx);
            mxy = max(mxy, ty), mny = min(mny, ty);
            x = tx, y = ty;
        }
        x = 100, y = 100;
        vis[x][y] = 1;
        if (mxx > 151 || mxy > 151 || mnx < 49|| mxy < 49)  return -1;
        for (int i = 0; i <= 151; ++i) {
            vis[i][mxy + 1] = vis[i][mny - 1] = 1;
            vis[mxx + 1][i] = vis[mnx - 1][i] = 1;
        }
        for (int i = 0; i < n; ++i) {
            int dir = i % 4;
            for (int j = 0; j < moves[i]; ++j) {
                int tx = x + dx[dir];
                int ty = y + dy[dir];
                if (vis[tx][ty])    return -1;
                vis[tx][ty] = 1;
                x = tx, y = ty;
            }
            if (i != n - 1 && !vis[x + dx[dir]][y + dy[dir]])   return -1;
        }
        return (mxx - mnx + 1) * (mxy - mny + 1);
    }
};

500

Description

两个人在一个无限大的格子里轮流涂红蓝两色，第一个人先在$(0,0)$涂红，然后接下来的每一轮，对于所有的点$(x,y)$，如果$(x-1,y-1)$和$(x-2,y)$一个有另一个人的颜色，一个为空，那么就把这个点涂成自己的颜色，问经过$t$轮之后，某个区域的染色情况。

Solution

将前几轮的情况手画一下，是下图这个样子的。。

容易发现只有在$y\le x$这些格子才会被染色，然后发现按$y=-x+b$来看，奇数的没有被染色，偶数的有被染色的。且非常类似杨辉三角，其实杨辉三角奇数项才会被染色。这里有个神奇的结论$c[n][m]为奇数时当且仅当(n \& m) == m$，于是就做完了QvQ

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>//conclusion
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct CheckerExpansion {
    vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) {
        vector<string> ans;
        for (int i = 0; i < h; ++i) {
            string s = "";
            for (int j = 0; j < w; ++j) {
                LL x = x0 + j;
                LL y = y0 + h - i - 1;
                if (y > x) {
                    s += ".";
                    continue;
                }
                if ((x + y) % 2 == 0) {
                    LL n = (x + y) / 2;
                    LL m = abs(x - n);
                    if (n >= t) s += ".";
                    else if ((n & m) == m) {    //amazing 
                        if (n & 1)  s += "B";
                        else s += "A";
                    }
                    else s += ".";
                }
                else s += ".";
            }
            ans.pb(s);
        }
        return ans;
    }
};

发表于   |   分类于   |  

250

Description

有两个集合，每个集合有$N(N<50)$个锥面(表示为高$H$和底面半径$R$，均小于$10000$)。要求从集合$1$和集合$2$的笛卡尔积集合中选取最多的元素满足如下性质：

  • (1): Ha / Ra > Hb / Rb
  • (2): Ra < Rb

Solution

很显然的一个二分图匹配

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55;
int g[N][N], l[N], vis[N];
bool can(int u, int m) {
    for (int i = 0; i < m; ++i) {
        if (g[u][i] && !vis[i]) {
            vis[i] = 1;
            if (l[i] == -1 || can(l[i], m)) {
                l[i] = u;
                return 1;
            }
        }
    }
    return 0;
}
struct PointyWizardHats {
    int getNumHats(vector <int> th, vector <int> tr, vector <int> bh, vector <int> br) {
        int n = th.size(), m = bh.size();
        memset(l, -1, sizeof(l));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (th[i] * br[j] > tr[i] * bh[j] && tr[i] < br[j]) g[i][j] = 1;
            }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            memset(vis, 0, sizeof(vis));
            if (can(i, m))  ++ans;
        }
        return ans;
    }
};

600

Description

$A$和$B$博弈。 在$N\times N(N\le 13)$的矩阵上，有一些$H$格子， 一开始每个$H$格子里最多有一枚带权值的硬币。 每次小$B$选一个$H$格子，然后小$A$将硬币任意排列后，将该格子的硬币给小$B$。
排列后必须满足如下条件：

  • (1): 每个格子必须有最多一枚硬币，小$B$选的格子可以没有硬币
  • (2): 每一行，每一列,$H$的个数和硬币的个数之和必须是偶数

$B$想获得尽量多的权值，$A$想让对面获得尽量少的权值

Solution

观察到，如果$B$能获得$k$个硬币的话，一定获得的是权值最小的$k$的硬币。
考虑到$H$格子的情况，其实只有三种

  • (1)：没选择这个格子
  • (2): 选择了这个格子，下面没有硬币
  • (3): 选择了这个格子，下面有硬币

容易想到三进制压缩，考虑状压dp，用三进制状态表示，用记忆化搜索比较容易实现。枚举当前选择的格子，枚举两种有无硬币的情况即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
vector<pii> g;
const int N = 13, inf = 100;
struct MagicalHats {
    int p[N], r[N], c[N], dp[1594323];
    int n, m, totcoin, tothat, num;
    inline int gao(int mask, int i, int s) {// 0:not selected 1:no coin 2:has coin
        return mask + s * p[i];
    }
    inline int get(int mask, int i) {
        return (mask / p[i]) % 3;
    }
    int dfs(int mask, int cocnt, int hatcnt, int r[], int c[]) {
        if (~dp[mask]) return dp[mask];
        int &t = dp[mask];
        t = -inf;
        if (hatcnt == tothat) {
            if (cocnt != totcoin)   return t = -inf;
            for (int i = 0; i < n; ++i) 
                if (r[i] & 1)   return t = -inf;
            for (int i = 0; i < m; ++i)
                if (c[i] & 1)   return t = -inf;
            return t = 0;
        }
        for (int i = 0; i < tothat; ++i) {
            int x = g[i].F, y = g[i].S;
            int s = get(mask, i);
            if (!s) {//not selected
                int t1 = -inf, t2 = -inf, state;
                if (cocnt < totcoin) {//has coin
                    int cnt = 1;
                    if (hatcnt >= num)  cnt = 0;
                    state = gao(mask, i, 2);
                    r[x] += 2;
                    c[y] += 2;
                    t1 = dfs(state, cocnt + 1, hatcnt + 1, r, c) + cnt;
                    r[x] -= 2;
                    c[y] -= 2;
                }
                //no coin
                ++r[x];
                ++c[y];
                state = gao(mask, i, 1);
                t2 = dfs(state, cocnt, hatcnt + 1, r, c);
                --r[x];
                --c[y];
                if (t1 < 0) t = max(t, t2);
                if (t2 < 0) t = max(t, t1);
                t = max(t, min(t1, t2));
            }
        }
        return t;
    }
    int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses) {
        p[0] = 1;
        for (int i = 1; i < 13; ++i)    p[i] = p[i - 1] * 3;
        this -> n = board.size(), this -> m = board[0].size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (board[i][j] == 'H') g.pb(mp(i, j));
        this -> totcoin = coins.size(), this -> tothat = g.size(), this -> num = numGuesses;
        memset(dp, -1, sizeof(dp));
        int cnt = dfs(0, 0, 0, r, c);
        sort(coins.begin(), coins.end());
        if (cnt < 0)    return -1;
        int ans = 0;
        for (int i = 0; i < cnt; ++i)   ans += coins[i];
        return ans;
    }
};

发表于   |   分类于   |  

250

Description

有$N(N\le 50)$个数，每个数的可变范围是$[max(N-X,1),N+X]$。让这个数列严格递增的最小$X$是多少？

Solution

显然可以二分答案，然后二分一个$x$后，我们可以贪心判断，使得前面的数尽量小给后面数更大的变化空间即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55;
bool check(int x, vector<int> h) {
    int n = h.size();
    for (int i = 0; i < n; ++i) {
        if (!i) {
            if (h[i] - x >= 1)  h[i] -= x;
            else h[i] = 1;
        }
        else {
            if (h[i] + x > h[i - 1]) {
                int t = h[i - 1] + 1;
                h[i] = max(t, h[i] - x);
            }
            else return 0;
        }
    }
    return 1;
}
struct KingdomAndTrees {
    int minLevel(vector <int> heights) {
        int l = 0, r = 1e9;
        int ans = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, heights)) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        return ans;
    }
};

450

Description

有两个$N<50$个面的骰子，每个面的数字是$1\sim X$的唯一某个数。第一个骰子有些面是$0$。现在两个骰子同时投掷，请你把第一个骰子某些为$0$的面写上一些唯一的$1\sim X$的数字，让第一个骰子的胜率尽可能接近$0.5$。

Solution

其实就是考虑将一些数插入一些空里，是否能赢得$k$次，容易想到$dp$，$dp[i][j][k]$表示$前i个数放入j个空能否赢k次$。不妨对第二个数组排序，依次处理即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>//dp
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55;
bool dp[N][N * N];
struct KingdomAndDice {
    double newFairness(vector <int> firstDie, vector <int> secondDie, int X) {
        int n = firstDie.size();
        int now = 0, nd = 0;
        sort(secondDie.begin(), secondDie.end());
        for (int i = 0; i < n; ++i) {
            nd += firstDie[i] == 0;
            for (int j = 0; j < n; ++j)
                if (firstDie[i] > secondDie[j]) ++now;
        }
        secondDie.pb(X + 1);
        for (int i = 0; i <= nd; ++i)   dp[i][now] = 1;
        for (int i = 0; i < n; ++i) {
            int l = secondDie[i] + 1;
            int r = secondDie[i + 1] - 1;
            int cnt = r - l + 1;
            for (int j = 0; j < n; ++j)
                if (firstDie[j] >= l && firstDie[j] <= r)   --cnt;
            cnt = min(cnt, nd);
            for (int j = 0; j < cnt; ++j)
                for (int k = nd - 1; k >= 0; --k)
                    for (int p = 0; p <= n * n; ++p)
                        if (dp[k][p] && p + i + 1 <= n * n) dp[k + 1][p + i + 1] = 1;
        }
        double ans = now;
        double mn = 1000000;
        for (int k = 0; k <= n * n; ++k)
            for (int j = 0; j <= nd; ++j)   
                if (dp[j][k] && abs(n * n - k * 2) < mn)    ans = k, mn = abs(n * n - k * 2);
        return ans / n / n;
    }
};

发表于   |   分类于   |  

250

Description

$1\le x\le 10^5, 1\le y\le 10^5,x,y\in N$,给定$w$,随机选$x,y$求$\sum sqrt((x-y)^2+w^2)$的期望

Solution

枚举$x-y$即可，注意细节即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct Pillars {
    double getExpectedLength(int w, int x, int y) {
         double ans = 0.0;
         if (x < y) swap(x, y);
         int del = x - y;
         for (int d = 1 - y; d <= 0; ++d) {
            ans += (double)(y + d) * sqrt(1.0 * d * d + w * w);
         }
         for (int d = 1; d <= del; ++d) {
            ans += (double)y * sqrt(1.0 * d * d + w * w);
         }
         for (int d = del + 1; d < x; ++d) {
            ans += (double)(x - d) * sqrt(1.0 * d * d + w * w);
         }
         return ans / x / y;
    }
};

500

Description

给定一个$h\times w(h,w\le 10^6)$的矩阵，数字为别为$0\sim h\times w - 1$，给定一个$sum(sum\le 10^{12})$，求最小面积的子矩形，使得和等于$sum$

Solution

考虑面积的上界$s$,$s\times (s-1) / 2\ge sum$，于是得到上界是$10^6$级别的，枚举$n$，复杂度为$N\times logN$,显然是可以接受的。
设矩阵最上角为$x$，根据等差数列求和，显然可以列出$x$和$sum$的关系，判断是否满足即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct RectangularSum {
    long long minimalArea(int height, int width, long long S) {
        int s;
        for (s = 1; (LL)s * (s - 1) / 2 <= S; ++s);
        int ans = 1e7;
        for (int n = 1; n <= s && n <= height; ++n)
            for (int m = 1; n * m <= s && m <= width; ++m) {
                if (S * 2 % n != 0) continue;
                LL t = S * 2 / n - (LL)(n - 1) * m * width;
                if (t < 0 || t & 1) continue;
                if (t % m != 0) continue;
                t = t / m + 1 - m;
                if (t < 0 || t & 1) continue;
                t /= 2;
                int y = t % width, x = t / width;
                if (x >= 0 && x + n - 1 < height && y >= 0 && y + m - 1 < width)    ans = min(ans, n * m);
            }
        return ans == 1e7 ? -1 : ans;
    }
};

发表于   |   分类于   |  

250

Solution

考虑奇偶性，每次定一个可以变成该数的上下界，按二进制位考虑即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct KleofasTail {
    LL gao(LL x, LL k) {
        if (k > x)  return 0;
        if (k <= 1) return x - k + 1;
        LL kk = k + (k % 2 == 0);
        LL t = 0;
        while (k <= x) {
            t += min(x, kk) - k + 1;
            k <<= 1;
            kk = (kk << 1 | 1);
        }
        return t;
    }
    long long countGoodSequences(long long K, long long A, long long B) {
        return gao(B, K) - gao(A - 1, K);              
    }
};

500

Description

求满足大于$A(A\le 10^{15})$的且$digit1$至少出现$count1$次，$digit2$至少出现$count2次$的最小的数是多少？
$(count1+count2\le 15,digit1,digit2\le 10)$

Solution

很容易想到数位$dp$,常见数位$dp$套路，用一个$f$表示当前数是否与最小值相等，还有$cnt1个x1,cnt2个x2$没有用，是否成立。
正常转移即可，注意一点，除了$x1,x2,lim,lim+1$以外，其他数是没什么意义的，$dp$即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>//dp
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
int a[16];
LL ans;
struct FavouriteDigits {
    bool dfs(int p, bool f, int x1, int cnt1, int x2, int cnt2, LL now) {
        if (p == -1) {
            if (cnt1 <= 0 && cnt2 <= 0) {
                ans = now;
                return 1;
            }
            return 0;
        }
        int lim = f ? a[p] : 0;
        for (int i = lim; i <= 9; ++i) {
            if (f) {
                if (!(i == lim || i == x1 || i == x2 || i == lim + 1))  continue;
            }
            else {
                if (!(i == lim || i == x1 || i == x2))  continue;
            }
            int d1 = cnt1 - (i == x1);
            int d2 = cnt2 - (i == x2);
            if (!now && !x1)    d1 = cnt1;
            if (dfs(p - 1, f & (i == lim), x1, d1, x2, d2, now * 10 + i))   return 1;
        }
        return 0;
    }
    long long findNext(long long N, int x1, int cnt1, int x2, int cnt2) {
        if (x1 > x2)    swap(x1, x2), swap(cnt1, cnt2);
        int p = 0;
        while (N) {
            a[p++] = N % 10;
            N /= 10;
        }
        p = max(p, cnt1 + cnt2);
        dfs(p, 1, x1, cnt1, x2, cnt2, 0);
        return ans;
    }
};

发表于   |   分类于   |  

275

Description

让你构造一个长度为$n$的串，逆序数恰好为$m$且字典序比某字符串$string$大，请构造字典序最小的这样的串。

Solution

数据范围非常小，暴力搜索即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int M = 26;
string ans;
struct StrIIRec {
    string dfs(int n, int minInv, string minStr, set<char> S) {
        if (minInv > (n - 1) * n / 2)   return "";
        if (n == 1) return string(1, *S.begin());
        int cnt = 0;
        if (!minStr.size()) minStr = "a";
        for (set<char>:: iterator it = S.begin(); it != S.end(); it++) {
            if (*it >= minStr[0]) {
                set<char> f = S;
                f.erase(*it);
                string t;
                if (*it == minStr[0])   t = dfs(n - 1, minInv - cnt, string(minStr, 1), f);
                else t = dfs(n - 1, minInv - cnt, "", f);
                if (t.size())   return *it + t;
            }
            ++cnt;
        }
        return "";
    }
    string recovstr(int n, int minInv, string minStr) {
        set<char> S;
        for (int i = 0; i < 26; ++i)    S.insert('a' + i);
        string ans = dfs(n, minInv, minStr, S);
        return ans;
    }
};

500

Description

你可以在$H\times L$的网格上以$(x,0)$为起点画一条非水平的射线，$0\le x\le L$，且为整数。在这个射线上每次要取$k$个整数坐标。问一共可以取得多少个不同的坐标集合$(1\le H,L,K\le 2000)。$

Solution

暴力枚举$dx, dy$，当$gcd(dx,dy)=1$的时候这个就相当于枚举斜率啦，然后我们需要枚举$x$,显然枚举会超时，我们考虑只有当$x+=dx,y+=dy$的时候，点数才可能会发生变化，枚举即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 2005, M = 1e9 + 7;
int c[N][N];
struct Spacetsk {
    int countsets(int L, int H, int K) {
        if (K == 1) return (H + 1) * (L + 1) % M;
        c[0][0] = 1;
        for (int i = 1; i <= 2001; ++i) {
            c[i][0] = 1;
            for (int j = 1; j <= i; ++j)    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
        }
        int ans = 0;
        for (int i = 0; i <= L; ++i)    (ans += c[H + 1][K]) %= M;
        for (int dx = 1; dx <= L; ++dx)
             for (int dy = 1; dy <= H; ++dy) {
                if (__gcd(dx, dy) == 1) {
                    int sum = 0, cnt = 0;
                    for (int x = 0, y = 0; x <= L; x += dx, y += dy) {
                        if (y <= H) ++cnt;  
                        int num = min(dx, L - x + 1);
                        (sum += 1ll * num * c[cnt][K] % M) %= M;
                    }
                    (ans += sum * 2 % M) %= M;
                }
             }
        return ans;
    }
};

发表于   |   分类于   |  

250

Description

从一个字符串中找一字典序最大的字串

Solution

从左至右贪心即可

500

Description

有一个序列，每次可以将一个数$-1$需要花费$1$的代价，问最后使得序列满足$2a[i]\le a[i-1]+a[i+1]$

Solution

因为满足$a[i-1]-a[i]\ge a[i]-a[i+1]$,也就是说序列相邻两项差是递减的，所以每当不满足条件时暴力调整$a[i]$，直到不需要调整为止。想想极限数据调整次数即可直到复杂度是靠谱的。

1000

Description

求符合以下条件的序列个数

  • 1:长度为K
  • 2:每个元素大小不超过L
  • 3:每个数都是质数
  • 4:所有数异或和为0

$K\le{10^{9}},L\le{5\times{10^{4}}}$

Solution

基本的递推方程很容易列出来$f[i][j]$表示前$i$个数异或和为$j$的方案数
$f[i][x\otimes y]=\sum_{0\le x,y\le 2^{16}} f[i-1][x]\times f[1][y]$
$f[1][y]=1$当且仅当$y$为质数且$y\le L$
这样暴力递推显然是$O(KL^2)$的,$i$为偶数时分治一下可以做到$O(L^2\times logK)$的，复杂度还是不行
然后我们可以想到把这个东西搞成类似于FFT的东西。
设向量a,b,c,定义向量之间的运算$　\$,c=a \$ b　$
$c[i\otimes j]=\sum a[i]\times b[j],做变换tf,使得tf(a\$b)=tf(a)\times tf(b),逆变换dft(tf(x))=x$
设$a$向量，$a[i]$表示$i$堆石子异或和为$0\sim 2^{16}$的方案数，$a[1]$在素数位置处为$1$，其他位置为$0$
这样我们只需要用$logK$的时间算出$tf(a[1])^K$,在做逆变换得到$a[k]$即为答案
观察tf和dtf的性质，当只有一个元素时，$tf(x)=dtf(x)=x$
当有两个元素$X=(a,b),Y=(c,d)$时
$Z=X\$Y$
$Z[0]=X[0]\times Y[0]+X[1]\times Y[1]=ac+bd$
$Z[1]=X[0]\times Y[1]+X[1]\times Y[0]=ad+bc$
$另tf(a,b)=(a-b,a+b)$
则$tf(X)\times tf(Y) =(a-b,a+b)\times(c-d,c+d)$
$=((a-b)\times(c-d),(a+b)\times(c+d))$
$=(ac+bd-ad-bc,ac+bd+ad+bc)$
$=tf(ac+bd,ac-bd)$
$=tf((a,b)\$(c,d))$
$=tf(X\$Y)$
$有A，B两向量，用归纳法可证明出tf(A + B) = tf(A) + tf(B) $
$如果我们将X向量分成两段等长的向量X[1],X[2]$
我们归纳一下会发现$tf(X[1],X[2])=(tf(X1) - tf(X2), tf(X1) + tf(X2))$

$(X[1]-X[2])[i]=X[1][i]-X[2][i]$
$(X[1]+X[2])[i]=X[1][i]+X[2][i]$
$将A分为A[1],A[2],B分为B[1],B[2]$
$则依旧可以归纳证出tf( (A1,A2) \$ (B1,B2) ) = tf(A1,A2)\times{tf(B1,B2)}$
$即对任意向量A，B，tf(A\$B)=tf(A)\times{tf(B)}$
$说明当有两个元素时,tf(a,b)=(a-b,a+b)正好就是我们所需要的变换$
然后我们就可以用$tf(X[1],X[2])=(tf(X1) - tf(X2), tf(X1) + tf(X2))$来做啦
算出$tf(a[1])^K$,在做逆变换得到a[K]即为答案

还有不明白的可以看http://apps.topcoder.com/wiki/display/tc/SRM+518

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1<<16,M=1000000007;
ll a[N],inv2;
ll P(ll x,ll y){
	ll tmp=1ll;
	for(;y;y>>=1){
		if(y&1)	tmp=tmp*x%M;
		x=x*x%M;
	}
	return tmp;
}
void trans(int l,int r){
	if(l==r-1)	return ;
	int len=(r-l)/2;
	int mid=l+len;
	trans(l,mid),trans(mid,r);
	for(int i=l;i<mid;++i){
		ll x1=(a[i]-a[i+len]+M)%M,x2=(a[i]+a[i+len])%M;
		a[i]=x1,a[i+len]=x2;
	}
}
void reverse(int l,int r){
	if(r-l==1)	return ;
	int len=(r-l)/2;
	int mid=l+len;
	for(int i=l;i<mid;++i){
		ll x1=a[i],x2=a[i+len];
		a[i]=(x1+x2)*inv2%M;
		a[i+len]=(x2-x1)*inv2%M;
	}
	reverse(l,mid),reverse(mid,r);
}
class Nim{
        public:
        int count(int K, int L){
            inv2=P(2,M-2);
			for(int i=2;i<=L;++i)
				if(!a[i])
					for(int j=i+i;j<=L;j+=i)	a[j]=1;
			for(int i=2;i<=L;++i)	a[i]^=1;
			int Log=1;
			while(Log<=L)	Log<<=1;
			trans(0,Log);
			for(int i=0;i<Log;++i)	a[i]=P(a[i],K);
			reverse(0,Log);
			return a[0];
        }
}

Code

发表于   |   分类于   |  

题外话

这个题是cc 9月challenge的最后一题，当时没仔细考虑，以为这是个近似计算的题。。。赛后看了题解才猛然醒悟

codechef 3D Queries(MGCH3D)

Description

求$\sum_{i!=j} \frac{|A(X_i - X_j) + B(Y_i - Y_j) + C(Z_i - Z_j) + D|}{N(N-1)\sqrt{(X_i-X_j)^4 + (Y_i-Y_j)^4+(Z_i-Z_j)^4}}$
$2\le N \le 777777,1\le X, Y, Z, A, B, C\le 77$, $Q(1\le Q\le 77)$组询问,每次给$A, B, C, D$, 求上式的值。

Solution

$x, y, z$坐标都很小($1\le x, y, z\le 77$)，差的取值也很小，不妨构造多项式$A[N^2\times x + N\times y + z] += 1$, $B[N^2\times (77-x)+N\times (77 - y)+(77-z)]+=1$。令$N=77*2$
我们发现$A\times B=N^2\times (77+x[i]-x[j]) + N\times (77+y[i]-y[j]) + (77+z[i]-z[j])$
显然$x[i]-x[j],y[i]-y[j],z[i]-z[j]$我们可以通过，于是这题FFT一下就做完了= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 153;
const double PI = acos(-1.0);
double D[80][80][80];
namespace FFT {
  static const int W = 1 << 22;
  static const double PI = acos(-1.0);
  struct Complex {
    double x, y;
    Complex(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    Complex operator + (const Complex &t) const {return Complex(x + t.x, y + t.y);}
    Complex& operator += (const Complex &t) {x += t.x, y += t.y;return *this;}
    Complex operator - (const Complex &t) const {return Complex(x-t.x,y-t.y);}
    Complex& operator -= (const Complex &t) {x -= t.x, y -= t.y;return *this;}
    Complex operator * (const Complex &t) const {return Complex(x * t.x - y * t.y, x * t.y + y * t.x);}
    Complex operator / (const double &t) const {return Complex(x / t,y / t);}
    Complex& operator /= (const double &t) {x /= t, y /= t;return *this;}
    double real() {return x;}
    double imag() {return y;}
  };
  void fft(Complex a[], int n, int rev) {// rev=-1, reverse
      for (int i = 1, j = 0, k; i < n; ++i) {
          for (k = n >> 1; k > (j ^= k); k >>= 1);
          if (i < j) swap(a[i], a[j]);
      }
      for (int s = 1, ss = 2; s < n; s <<= 1,ss <<= 1) {
          Complex wn(cos(2 * PI * rev / ss), sin(2 * PI * rev / ss)), w;
          for (int i = 0, j ; i < n; i += ss) {
              for (j = i, w = 1; j < i + s; ++j, w = w * wn) {
                  Complex t = w * a[j + s];
                  a[j + s] = a[j] - t; 
                  a[j] = a[j] + t;
              }
          }
      }
      if (rev == -1) for (int i = 0; i < n; ++i) a[i] /= n;
  }
}
FFT::Complex A[FFT::W], B[FFT::W];
inline double sqrr(double x) {
    return x * x * x * x;
}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y, z; i <= n; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        --x, --y, --z;
        int t1 = N * N * x + N * y + z, t2 = N * N * (76 - x) + N * (76 - y) + (76 - z);
        A[t1].x += 1, B[t2].x += 1;
    }
    for (int i = 0; i <= 77; ++i)
        for (int j = 0; j <= 77; ++j)
            for (int k = 0; k <= 77; ++k)
                D[i][j][k] = sqrt(sqrr(i) + sqrr(j) + sqrr(k));
    FFT::fft(A, FFT::W, 1);
    FFT::fft(B, FFT::W, 1);
    for (int i = 0; i < FFT::W; ++i)    A[i] = A[i] * B[i];
    FFT::fft(A, FFT::W, -1);
    while (q--) {
        double ans = 0;
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        for (int i = 0; i < FFT::W; ++i) {
            int cnt = int(A[i].real() + 0.5);
            if (!cnt)   continue;
            int x = i / (N * N) - 76, y = i / N % N - 76, z = i % N - 76;
            if (!x && !y && !z) continue;
            ans += fabs(a * x + b * y + c * z + d) * cnt / D[abs(x)][abs(y)][abs(z)];
        }
        ans /= n, ans /= n - 1;
        printf("%.10lf\n", ans);
    }
    return 0;
}

总结

自己还是太年轻，一看范围小就想着想忽略近似计算和乱搞，犯了方向性的错误= =。。还是要多加思考QvQ