头像

松鼠爱葡萄




在线 



image_17.png

#include<iostream>

using namespace std;
const int N = 1e5 + 10;
int n, m, a[N];
typedef long long LL;
LL tr1[N], tr2[N];

int lowbit(int x) {
    return x & -x;
}

void add(LL tr[], int x, LL c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL psum(int x) {
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int b = a[i] - a[i - 1];
        add(tr1, i, b);
        add(tr2, i, (LL) b * i);
    }

    while (m--) {
        char op;
        LL l, r, d;
        cin >> op >> l >> r;
        if (op == 'Q') {
            cout << psum(r) - psum(l - 1) << endl;
        } else {
            cin >> d;
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, -(r + 1) * d);
        }
    }
}




#include<iostream>

using namespace std;
const int N = 1e4 + 10;
int n, m, vol;
int p[N], v[N], w[N], f[N];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m >> vol;

    for (int i = 1; i <= n; i++) p[i] = i;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            w[pb] += w[pa];
            v[pb] += v[pa];
            p[pa] = p[pb];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (p[i] == i)
            for (int j = vol; j >= v[i]; j--) {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
    }

    cout << f[vol] << endl;
}



#include<iostream>
#include<cstring>

using namespace std;
const int N = 4e4 + 10;
int n, m;
int p[N];

int get(int x, int y) {
    return x * n + y;
}

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n * n; i++) p[i] = i;
    int res = 0;
    for (int i = 1; i <= m; i++) {
        int x, y;
        char d;
        cin >> x >> y >> d;
        x--, y--;
        int a = get(x, y);
        int b = 0;
        if (d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);

        int pa = find(a), pb = find(b);
        if (pa == pb) {
            res = i;
            break;
        } else {
            p[pb] = pa;
        }
    }

    if (res) cout << res << endl;
    else puts("draw");
}



image_16.png

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans = INF;

void dfs(int u, int v, int s) {
    if (v + minv[u] > n) return;
    if (s + mins[u] >= ans) return;
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;

    if (!u) {
        if (v == n) ans = s;
        return;
    }

    for (int r = min(R[u + 1] - 1, (int) sqrt(n - v)); r >= u; r--)
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
            int t = 0;
            //红色圆形的面积
            if (u == m) t = r * r;
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}

int main() {
    cin >> n >> m;

    // v=r*r*h
    // s=2*r*h
    for (int i = 1; i <= m; i++) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    // u=m, R[u + 1] - 1要被用到
    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

    if (ans == INF) ans = 0;
    cout << ans << endl;

    return 0;
}




image_14.png

选择分支最少的格子

不能与行, 列, 九宫格有重复

位运算优化

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init() {
    for (int i = 0; i < N; i++)
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set) {
    //is_set=true, make (x, y) = t
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;

    //is_set=true, (x, y) 中 t已经不能用了
    //is_set=false, (x, y) 中 t可以用,row, col, cell 加入1
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

int lowbit(int x) {
    return x & -x;
}

int get(int x, int y) {
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt) {
    if (!cnt) return true;

    int minv = 10;
    int x, y;
    // 找出分支最少的格子
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (str[i * N + j] == '.') {
                int state = get(i, j);
                if (ones[state] < minv) {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i)) {
        // 100100100
        // 依次获取100, 10000, 1000000
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}

int main() {
    // log(1<<i) = i
    for (int i = 0; i < N; i++) map[1 << i] = i;
    // 0-80, 在二进制中1的个数
    for (int i = 0; i < 1 << N; i++)
        for (int j = 0; j < N; j++)
            ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e') {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i++)
            for (int j = 0; j < N; j++, k++)
                if (str[k] != '.') {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                } else cnt++;

        dfs(cnt);

        puts(str);
    }

    return 0;
}



image_12.png

一组一组搜索,尽量把前一组填满,然后开新组。
比如说, 我们一共有枚举了三个组ga, gb, gc和一个新组gnew, 那么考虑元素p[i]ga, gb已经把能加进来的元素都加进来了,p[i]还不在任何一个组(ga, gb) 内,就说明ga, gb考虑过,但基于最小组数的原则没有把p[i]加进来, 所以p[i]只能考虑加入到gc或者gnew


如果最后一组,新开的一组都能放,则放置在最后一组,因为答案求的是最小组数,所以尽可能少开新组。


组3:

放1,2, 3

放2, 1, 3

放3, 2, 1

都是一样的,所以求的是组合数

所以如何递归实现组合型枚举

我们按照从小到大顺序开始枚举


#include <cstring>
#include <iostream>

using namespace std;

const int N = 10;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i) {
    // 如果组内的p[group[j]]与正在枚举的p[i]  存在 >1 的公因子, 则不互质
    for (int j = 0; j < gc; j++)
        if (gcd( p[group[j]] , p[i] ) > 1)
            return false;
    return true;
}

// 组的序号g, 当前组内下标gc,当前一共tc个元素, 下标从start开始搜索
void dfs(int g, int gc, int tc, int start) {
    if (g >= ans) return;
    if (tc == n) ans = g;

    bool flag = true;
    // 从start开开始搜索, 并且没有被搜索过的下标i
    for (int i = start; i < n; i++)
        if (!st[i] && check(group[g], gc, i)) {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;

            flag = false;
        }

    if (flag) dfs(g + 1, 0, tc, 0);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];

    //第1组,组内有0个元素, 当前搜了0个元素, 从0号下标开始搜
    dfs(1, 0, 0, 0);

    cout << ans << endl;

    return 0;
}




g[i][j] 表示字符串word[i] word[j] 最小重合部分

//如果
//word[i]="0123456", word="456789x";
//那么
//k=4

for (int i = 0; i < n; i ++ )
    for (int j = 0; j < n; j ++ )
    {
        string a = word[i], b = word[j];
        for (int k = 1; k < min(a.size(), b.size()); k ++ )
            if (a.substr(a.size() - k, k) == b.substr(0, k))
            {
                g[i][j] = k;
                break;
            }
    }

对于word[j]去掉重合部分, 剩下的字符串就可以拼接在dragon 字符串后了

for (int i = 0; i < n; i++)
    if (g[last][i] && used[i] < 2)
        dfs(dragon + word[i].substr(g[last][i]), i);
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 21;

int n;
string word[N];
int g[N][N];
int used[N];
int ans;

void dfs(string dragon, int last) {
    ans = max((int) dragon.size(), ans);

    used[last]++;

    for (int i = 0; i < n; i++)
        if (g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);

    used[last]--;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k++)
                if (a.substr(a.size() - k, k) == b.substr(0, k)) {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i++)
        if (word[i][0] == start)
            dfs(word[i], i);

    cout << ans << endl;

    return 0;
}




image_10.png
image_11.png

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 200010;

int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int f[N], cnt[N];
bool st[N];

void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, T});

    memset(f, 0x3f, sizeof f);
    f[T] = 0;

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = rh[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (f[j] > f[ver] + w[i]) {
                f[j] = f[ver] + w[i];
                heap.push({f[j], j});
            }
        }
    }
}

int astar() {
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({f[S], {0, S}}); //按照估价函数排序

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.y.y, distance = t.y.x;
        cnt[ver]++;
        if (cnt[T] == K) return distance;

        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (cnt[j] < K)
                heap.push({distance + w[i] + f[j], {distance + w[i], j}});
                                //真实值 + 边的长度 + 估价函数(距离T的最短距离)
        }
    }

    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    scanf("%d%d%d", &S, &T, &K);
    if (S == T) K++;

    dijkstra();
    printf("%d\n", astar());

    return 0;
}




image_9.png

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;
const int N = 510, M = N * N;
int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs() {
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);

    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    char cs[5] = "\\/\\/";

    deque<pair<int, int>> q;
    q.push_back({0, 0});
    dist[0][0] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop_front();

        int x = t.first, y = t.second;
        if (st[x][y]) continue;

        if (x == n && y == m) return dist[x][y];

        st[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            //边长是n, 但会有n+1个点,所以是 a>n
            if (a < 0 || a > n || b < 0 || b > m) continue;

            int ga = x + ix[i], gb = y + iy[i];
            int w = (g[ga][gb] != cs[i]);
            int d = dist[x][y] + (g[ga][gb] != cs[i]);

            if (d <= dist[a][b]) {
                dist[a][b] = d;
                if (w == 0) q.push_front({a, b});
                else q.push_back({a, b});
            }
        }
    }
    return -1;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%s", g[i]);
        if (n + m & 1) puts("NO SOLUTION");
        else cout << bfs() << endl;
    }

}



image_8.png

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10, M = 1 << 10;

int n, m;
int g[1010];
int f[2][M][M];
vector<int> state;
int cnt[M];

bool check(int state) {
    for (int i = 0; i < m; i++)
        if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1)))
            return false;
    return true;
}

int count(int state) {
    int res = 0;
    for (int i = 0; i < m; i++)
        if (state >> i & 1)
            res++;
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            g[i] += (c == 'H') << j;
        }

    for (int i = 0; i < 1 << m; i++)
        if (check(i)) {
            state.push_back(i);
            cnt[i] = count(i);
        }

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < state.size(); j++)
            for (int k = 0; k < state.size(); k++)
                for (int u = 0; u < state.size(); u++) {
                    int a = state[j], b = state[k], c = state[u];
                    if (a & b | a & c | b & c) continue;
                    if (g[i] & b | g[i - 1] & a) continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
                }

    int res = 0;
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
            res = max(res, f[n & 1][i][j]);

    cout << res << endl;

    return 0;
}