头像

沧笙


访客:287

离线:8小时前


分享 gle

沧笙
12小时前
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

// 十字链表
struct Node{
    int u, d, l, r;
    int val;
    Node(){
        u = d = l = r = -1; val = 0;
    }
};
vector<Node> ten_list;
int R, C;

// 获取 一维的 id
int getId(int x, int y) { return x * (C + 1) + y; }

// 删除 x 节点
void erase(int x) {
   ten_list[ten_list[x].l].r = ten_list[x].r;
   ten_list[ten_list[x].r].l = ten_list[x].l;
   ten_list[ten_list[x].u].d = ten_list[x].d;
   ten_list[ten_list[x].d].u = ten_list[x].u;
   ten_list[x].val = 0;
}

vector<int> update(vector<int> &choosList, LL &ans, LL &origin) {

    vector<int> needErase;
    vector<int> newList, _newList;
    ans += origin;
    for(int i = 0, len = choosList.size(); i < len; ++ i) {
        int x = choosList[i];
        int neiNum = 0; int neiVal = 0;
        if(ten_list[ten_list[x].r].val != 0) { neiNum ++; neiVal += ten_list[ten_list[x].r].val; }
        if(ten_list[ten_list[x].l].val != 0) { neiNum ++; neiVal += ten_list[ten_list[x].l].val; }
        if(ten_list[ten_list[x].u].val != 0) { neiNum ++; neiVal += ten_list[ten_list[x].u].val; }
        if(ten_list[ten_list[x].d].val != 0) { neiNum ++; neiVal += ten_list[ten_list[x].d].val; }

        if(neiVal > ten_list[x].val * neiNum) { 
            origin -= ten_list[x].val; 
            // 需要删除
            needErase.push_back(x);
        }
    }

    for(auto x : needErase) {
        // 防止 re assert 现在很少用了  也可以不加
        assert(ten_list[x].r != -1); assert(ten_list[x].l != -1); assert(ten_list[x].u != -1); assert(ten_list[x].d != -1);
        if(ten_list[ten_list[x].r].val != 0) { _newList.push_back(ten_list[x].r); }
        if(ten_list[ten_list[x].l].val != 0) { _newList.push_back(ten_list[x].l); }
        if(ten_list[ten_list[x].u].val != 0) { _newList.push_back(ten_list[x].u); }
        if(ten_list[ten_list[x].d].val != 0) { _newList.push_back(ten_list[x].d); }
        erase(x);
    }

    for(auto it : _newList) newList.push_back(it);
    sort(newList.begin(), newList.end());
    newList.erase(unique(newList.begin(), newList.end()), newList.end());

    return newList;
}

int main(){

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

    for(int cases = 1; cases <= T; ++ cases){
        // 清空十字链表
        ten_list.clear();
        scanf("%d %d", &R, &C);
        // 预开空间
        ten_list.resize((R + 5) * (C + 5), Node());
        // 统计和
        LL origin = 0;
        for(int i = 1; i <= R; ++ i){
            for(int j = 1; j <= C; ++ j){
                scanf("%d", &ten_list[getId(i , j)].val);
                origin += ten_list[getId(i , j)].val;
            }
        }
        // 初始化十字链表
        for(int i = 1; i <= R; ++ i){
            ten_list[getId(i, 1)].l = getId(i, 0);
            for(int j = 1; j <= C; ++j){
                ten_list[getId(i , j - 1)].r = getId(i, j);
                ten_list[getId(i , j + 1)].l = getId(i, j);
            }
            ten_list[getId(i , C)].r = getId(i, C + 1);
        }

        for(int i = 1; i <= C; ++ i) {
            ten_list[getId(1 , i)].u = getId(0, i);
            for(int j = 1; j <= R; ++ j) {
                ten_list[getId(j - 1, i)].d = getId(j, i);
                ten_list[getId(j + 1, i)].u = getId(j, i);
            }
            ten_list[getId(R, i)].d = getId(R + 1, i);
        }

        vector<int> choosList;
        for(int i = 1; i <= R; ++ i){
            for(int j = 1; j <= C; ++ j){
                choosList.push_back(getId(i, j));
            }
        }

        LL ans = 0;
        while(true){
            choosList = update(choosList, ans, origin);
            // 不需要修改 直接break  防止 tle
            if(choosList.size() == 0) break;
        }

        printf("Case #%d: %lld\n", cases, ans);
    }
    return 0;
}



沧笙
14小时前
#include <iostream>
#include <cmath>

#define eps 1e-8

using namespace std;

double y;
double fx(int x){
    return 6 * pow(x, 7.0) + 8 * pow(x, 6.0) + 7 * pow(x, 3.0) + 5 * x * x - y * x;
}
double three(double l,double r){
    while(l + eps < r){
        double midl = (l + r) / 2.0;
        double midr = (midl + r) / 2.0;
        if(fx(midl) < fx(midr))
            r = midr;
        else 
            l = midl;
    }
    return l;
}
int main(){

    int T;
    cin >> T;

    while(T -- ){
        scanf("%lf", &y);
        int t = three(0, 100);
        printf("%.4f\n",fx(t));
    }
    return 0;
}



沧笙
1天前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 7, M = N << 1;

int n;
int h[N], e[M], ne[M], idx;
int col[N], cnt[N];
int sum, maxc;
int siz[N], son[N];
int flag;
long long ans[N];

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

void dfs(int u,int fa){
    siz[u] = 1;
    int maxn = 0;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        siz[u] += siz[j];
        if(siz[j] > maxn){
            maxn = siz[j];
            son[u] = j;
        }
    }
}

void count(int u,int fa,int val){
    cnt[col[u]] += val;
    if(cnt[col[u]] > maxc){
        maxc = cnt[col[u]];
        sum = col[u];
    }
    else if(cnt[col[u]] == maxc)
        sum += col[u];
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == fa || j == flag) continue;
        count(j, u, val);
    }
}
void dfs(int u,int fa,bool keep){
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == fa || j == son[u]) continue;
        dfs(j, u, false);
    }
    if(son[u]){
        dfs(son[u], u, true);
        flag = son[u];
    }
    count(u, fa, 1);
    ans[u] = sum;
    flag = 0;

    if(!keep){
        count(u, fa, -1);
        maxc = sum = 0;
    }
}

int main(){

    memset(h, -1, sizeof h);

    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ )
        scanf("%d", &col[i]);

    for(int i = 1;i < n;i ++ ){
        int a, b; scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1, 0);

    dfs(1, 0, 0);
    for(int i = 1;i <= n;i ++ )
        printf("%lld ", ans[i]);

    return 0;
}



分享 cdq

沧笙
2天前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define N 1000005

using namespace std;

typedef long long LL;

int n;
int a[N];
int ans[N];
struct Node{
    int op, a, b, id;
}q[N], tmp[N];

bool cmpa(const Node& n1, const Node& n2){
    if(n1.a == n2.a) return n1.op < n2.op;
    else return n1.a < n2.a;
}

bool cmpb(const Node& n1, const Node& n2){
    if(n1.b == n2.b) return n1.op > n2.op;
    else return n1.b > n2.b;
}

void solve(int l, int r){
    if(l == r) return ;

    int mid = l + r >> 1;
    solve(l, mid);

    sort(q + l, q + r + 1, cmpb);

    // merge(q + l, q + mid + 1, q + mid + 1, q + 1 + r, q0 + l, cmpb);//O(len)
    // for(int i = l;i <= r;i ++ ){//O(len)
    //     q[i] = q0[i];
    // }

    int cnt = 0;
    for(int i = l;i <= r;i ++ ){//O(len)
        if(q[i].op == 1 && q[i].a <= mid) ++ cnt;
        if(q[i].op == 2 && q[i].a >= mid+1) ans[q[i].id] += cnt;
    }

    for(int i = l;i <= r;i ++ ){//O(len)
        q[i] = tmp[i];
    }

    solve(mid + 1, r);
}

int main(){

    // ios::sync_with_stdio(0);

    cin >> n;

    for(int i = 1;i <= n;i ++ ){
        cin >> a[i];
        // insert
        q[i].a = i;
        q[i].b = a[i];
        q[i].op = 1;
        // query
        q[i + n].a = i;
        q[i + n].b = a[i];
        q[i + n].op = 2;
        q[i + n].id = i;
    }

    // 按 a 排序 给每个数分配唯一的时间轴
    sort(q + 1, q + 1 + 2 * n, cmpa);

    for(int i = 1;i <= 2 * n;i ++ )
        q[i].a = i;
    memcpy(tmp, q, sizeof q);
    solve(1, 2 * n);

    LL res = 0;
    for(int i = 1;i <= n;i ++ ){
        res += ans[i];
    }

    cout << res << endl;
    return 0;
}



沧笙
2天前
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#define N 505
#define Q 320005

using namespace std;

int n, m;
int tr[N][N];
int ans[Q];
struct Node{
    int op;
    int r, c, x;
    int r1, c1, r2, c2, k;
    int id;
}q[Q], lq[Q], rq[Q];

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

void updata(int x,int y,int v){
    for(int i = x;i <= n;i += lowbit(i))
        for(int j = y;j <= n;j += lowbit(j))
            tr[i][j] += v;
}

int query(int x,int y){
    int ans = 0;
    for(int i = x;i;i -= lowbit(i))
        for(int j = y;j;j -= lowbit(j)){
            ans += tr[i][j];
        }
    return ans;
}

void solve(int lv,int rv,int ql,int qr){
    if(lv > rv || ql > qr) return ;
    cerr << "solve: " << lv << " " << rv << " " << ql << " " << qr << endl;

    if(lv == rv){
        for(int i = ql;i <= qr;i ++ )
            if(q[i].op == 2){
                ans[q[i].id] = rv;
            }
        return ;
    }

    int mid = lv + rv >> 1;
    int nl = 0, nr = 0;
    for(int i = ql;i <= qr;i ++ ){
        if(q[i].op == 1){ // insert
            if(q[i].x <= mid) updata(q[i].r, q[i].c, 1), lq[ ++ nl] = q[i];
            else rq[ ++ nr] = q[i];
        }
        else if(q[i].op == 2){ // query
            int x1 = q[i].r1, y1 = q[i].c1, x2 = q[i].r2, y2 = q[i].c2;
            int t = query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1);
            // int t = query(q[i].r2, q[i].c2) - query(q[i].r2, q[i].c1-1) - query(q[i].r1-1, q[i].c2) + query(q[i].r1-1, q[i].c1-1);
            if(t >= q[i].k) lq[ ++ nl] = q[i];
            else{
                q[i].k -= t;
                rq[ ++ nr] = q[i];
            }
        }
    }

    for(int i = ql;i <= qr;i ++ )
        if(q[i].op == 1)
            if(q[i].x <= mid)
                updata(q[i].r, q[i].c, -1);

    for(int i = 1;i <= nl;i ++ ) q[ql + i - 1] = lq[i];
    for(int i = 1;i <= nr;i ++ ) q[ql + nl + i - 1] = rq[i];

    solve(lv, mid, ql, ql + nl - 1);
    solve(mid + 1, rv, ql + nl, qr);
}

int main(){
    scanf("%d%d", &n, &m);
    int t = 0;
    for(int i = 1;i <= n;i ++ )
        for(int j = 1;j <= n;j ++ ){
            scanf("%d", &q[ ++ t].x);
            q[t].id = t;
            q[t].r = i, q[t].c = j;
            q[t].op = 1;
        }

    for(int i = 1;i <= m;i ++ ){
        q[ ++ t].op = 2;
        q[t].id = t;
        scanf("%d%d%d%d%d", &q[t].r1, &q[t].c1, &q[t].r2, &q[t].c2, &q[t].k);
    }

    solve(0, 1e9, 1, t);

    for(int i = 1;i <= m;i ++ )
        printf("%d\n", ans[n * n + i]);
    return 0;
}



沧笙
2天前

整体二分(值域)

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

using namespace std;

const int N = 100010 + 10010;

int n, m;
int tr[N];
struct Node{
    int op; // op = 1 insert // op = 2 query
    int x, y, k;
    int id;// 第几个询问 ans[id];
    Node(int op = 0, int x = 0, int y = 0,int k = 0,int id = 0)
        :op(op), x(x), y(y), k(k), id(id){}
}q[N], lq[N], rq[N];
int ans[N];

// 树状数组 维护
int lowbit(int x){
    return x & -x;
}

void updata(int x,int v){
    for(;x <= n;x += lowbit(x)) tr[x] += v;
}

int query(int x){
    int res = 0;
    for(;x;x -= lowbit(x)) res += tr[x];
    return res;
}

void solve(int vl,int vr,int ql,int qr){
    // 防止re
    if(ql > qr || vl > vr) return ;

    // 如果vl == vr 则 [ql, qr] 所有查询操作的 ans 为 qr
    if(vl == vr){
        for(int i = ql;i <= qr;i ++ )
            if(q[i].op == 2)
                ans[q[i].id] = vr;
        return ;
    }

    // mid 二分 [vl, mid] -> update至树状数组中
    int mid = vl + vr >> 1;
    int nl = 0,nr = 0;
    for(int i = ql;i <= qr;i ++ ){
        if(q[i].op == 1){
            if(q[i].x <= mid){
                updata(q[i].y, 1);
                lq[ ++ nl] = q[i];
            }
            else rq[ ++ nr] = q[i];
        }else{
            int n = query(q[i].y) - query(q[i].x - 1);
            if(n >= q[i].k){
                lq[ ++ nl] = q[i];
            }
            else {
                q[i].k -= n;
                rq[ ++ nr] = q[i];
            }
        }
    }

    // 清空 树状数组
    for(int i = ql;i <= qr;i ++ )
        if(q[i].op == 1)
            if(q[i].x <= mid)
                updata(q[i].y, -1);


    for(int i = 1;i <= nl;i ++ ) q[ql + i - 1] = lq[i];
    for(int i = 1;i <= nr;i ++ ) q[ql + nl + i - 1] = rq[i];

    // 递归 分治左右两边
    solve(vl, mid, ql, ql + nl - 1);
    solve(mid + 1, vr, ql + nl, qr);
}

int main(){

    // 位置一定要 插入在前 查询在后
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++ ){
        int x;
        scanf("%d", &x);
        // 在第 i 个位置插入 x
        q[i] = Node(1, x, i);
    }

    int l, r, k;
    for(int i = 1;i <= m;i ++ ){
        scanf("%d%d%d", &l, &r, &k);
        q[i + n] = Node(2, l, r, k, i);
    }

    // 整体二分  值域二分
    solve(-1e9, 1e9, 1, n + m);

    for(int i = 1;i <= m;i ++ ) printf("%d\n", ans[i]);
    return 0;
}

参考 wzc大佬 的做法: orz

wzc 大佬的 这个 是跑的最快的 sto
我写的这样会多开两倍空间,可以参考wzc大佬利用快排的思想,每次交换 就可以省区空间跑的更快一些

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 50010;

int n, m;
struct A{
    int id, x;
}a[N];

struct Q{
    int id;
    int l, r, k;
}q[M], lq[M], rq[M];

int tr[N], ans[M];

inline bool cmp(const A &p, const A &q) {
    return p.x < q.x;
}

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

inline int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x))
        res += tr[x];
    return res;
}

inline void update(int x, int v) {
    for (; x <= n; x += lowbit(x))
        tr[x] += v;
}

void solve(int L, int R, int l, int r) {
    if (l > r || L > R) return ;

    if (L == R) {
        for(int i = l; i <= r; i ++ )
            ans[q[i].id] = a[L].x;
        return ;
    }

    int mid = (L + R) >> 1;

    for (int i = L; i <= mid; i ++ )
        update(a[i].id, 1);

    int t;
    int nl = 0, nr = 0;

    for(int i = l;i <= r;i ++ ){
        t = query(q[i].r) - query(q[i].l - 1);
        if(q[i].k <= t) lq[ ++ nl] = q[i];
        else{
            q[i].k -= t;
            rq[ ++ nr] = q[i];
        }
        // i -- , j ++ ;
    }

    for (int i = L; i <= mid; i ++ )
        update(a[i].id, -1);

    for(int i = 1;i <= nl;i ++ ) q[i + l - 1] = lq[i];
    for(int i = 1;i <= nr;i ++ ) q[i + l + nl - 1] = rq[i];
    solve(L, mid, l, nl + l - 1);
    solve(mid + 1, R, nl + l, r);
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }

    for (int i = 1; i <= m; i++) {
        q[i].id = i;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
    }

    sort(a + 1, a + 1 + n, cmp);

    solve(1, n, 1, m);

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}

省去 两倍空间的写法

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 50010;

int n, m;

struct A {
    int id, x;
}a[N];

struct Q {
    int id;
    int l, r, k;
}q[M];

int f[N], ans[M];

inline bool cmp(const A &p, const A &q) {
    return p.x < q.x;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += f[x];

    return res;
}

inline void update(int x, int y) {
    for (; x <= n; x += x & -x)
        f[x] += y;
}

void solve(int L, int R, int l, int r) {
    if (l > r)
        return;

    if (L == R) {
        for (int i = l; i <= r; i++)
            ans[q[i].id] = a[L].x;
        return;
    }

    int mid = (L + R) >> 1;

    for (int i = L; i <= mid; i++)
        update(a[i].id, 1);

    int i = l, j = r, t;

    while (i <= j) {
        while (i <= j && q[i].k <= query(q[i].r) - query(q[i].l - 1))
            i++;

        while (i <= j && q[j].k > (t = query(q[j].r) - query(q[j].l - 1))) {
            q[j].k -= t;
            j--;
        }

        if (i < j)
            swap(q[i], q[j]);
    }

    for (int i = L; i <= mid; i++)
        update(a[i].id, -1);

    solve(L, mid, l, j);
    solve(mid + 1, R, i, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }

    for (int i = 1; i <= m; i++) {
        q[i].id = i;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
    }

    sort(a + 1, a + 1 + n, cmp);

    solve(1, n, 1, m);

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}

主席树 (多棵权值线段树)

权值线段树
1.png
普通的主席树
2.png
省空间后的主席树
3.png
以下用的是省空间后的主席树

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e5 + 5;

int n, m;
int a[N];
vector<int> v;
struct Node{
    int l, r, sum;
}hjt[N * 40];
int cnt, root[N];

inline int getid(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }

// 插入pre 是历史版本 now 是当前版本  插入p
void insert(int l,int r,int pre,int &now,int p){
    hjt[now = ++ cnt] = hjt[pre];
    hjt[now].sum ++ ;

    if(l == r) return ;
    int mid = l + r >> 1;
    if(p <= mid) insert(l, mid, hjt[pre].l, hjt[now].l, p);
    else insert(mid + 1, r, hjt[pre].r, hjt[now].r, p);
}

int query(int l,int r,int L,int R,int k){
    if(l == r) return r;
    int mid = l + r >> 1;
    int tmp = hjt[hjt[R].l].sum - hjt[hjt[L].l].sum;
    if(k <= tmp) return query(l, mid, hjt[L].l, hjt[R].l, k);
    else return query(mid + 1, r, hjt[L].r, hjt[R].r, k - tmp);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("D:\\in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif

    clock_t c1 = clock();

    scanf("%d%d", &n, &m);

    // 先 离散化
    for(int i = 1;i <= n;i ++ ){
        scanf("%d", &a[i]);
        v.push_back(a[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 1;i <= n;i ++ )
        insert(1, n, root[i - 1], root[i], getid(a[i]));

    while(m -- ){
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", v[query(1, n, root[l - 1], root[r], k) - 1]);
    }

    // fflush(stdin);
    // cout << "Time:" << clock() - c1 << endl;

    return 0;
}


活动打卡代码 AcWing 5435. 并行课程 II

沧笙
13天前
class Solution {
public:
    const int INF = 10000;
    vector<int> dp;
    int minNumberOfSemesters(int n, vector<vector<int>>& edges, int k) {

        dp = vector<int>(1 << n, INF);

        for(auto& e : edges) e[0] -- , e[1] -- ;

        dp[0] = 0;
        for(int i = 0;i < 1 << n;i ++ ){
            vector<bool> st(n, true);
            for(auto& e : edges){
                int x = e[0], y = e[1];
                if(!(i >> x & 1)) st[y] = false;
            }

            int state = 0;
            for(int j = 0;j < n;j ++ )
                if(st[j] && !(i >> j & 1)) state += 1 << j;

            dfs(n, k, state, i, 0, 0);

        }

        return dp[(1 << n) - 1];
    }

    void dfs(int n,int k,int state,int i,int now,int start){
        if(!k || !state){
            dp[i | now] = min(dp[i | now], dp[i] + 1);
            return ;
        }

        for(int j = start;j < n;j ++ )
            if(state >> j & 1)
                dfs(n, k - 1,state - (1 << j), i, now + (1 << j), j + 1);
    }
};
class Solution {
public:
    int lowbit(int x){
        return x & (-x);
    }
    const int INF = 10000;
    vector<int> dp;
    vector<int> cnt, pre;
    int minNumberOfSemesters(int n, vector<vector<int>>& edges, int k) {
        int m = 1 << n;
        dp = vector<int>(m, INF);
        cnt = vector<int>(m, 0);
        pre = vector<int>(m, 0);

        for(int i = 1;i < m;i ++ )
            cnt[i] = cnt[i >> 1] + (i & 1);
        for(auto e : edges)
            pre[1 << (e[1] - 1)] |= (1 << (e[0] - 1));
        for(int i = 1;i < m;i ++ )
            pre[i] = pre[i ^ lowbit(i)] | pre[lowbit(i)];

        dp[0] = 0;
        for(int i = 1;i < m;i ++ )
            for(int j = i;j;j = (j - 1) & i){
                if(cnt[j] > k) continue;
                if((pre[j] & (i ^ j)) != pre[j]) continue;
                dp[i] = min(dp[i], dp[i ^ j] + 1);
            }

        return dp[m - 1];
    }
};


活动打卡代码 AcWing 166. 数独

沧笙
13天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 9;

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

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

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

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

bool dfs(int cnt){

    if(!cnt) return true;

    int x, y;
    int minv = 10;
    // 找一个最小的 minv 枚举这个最小值
    for(int i = 0;i < N;i ++ )
        for(int j = 0;j < N;j ++ ){
            if(str[i * 9 + j] == '.')
                if(minv > ones[get(i, j)]){
                    x = i,y = j;
                    minv = ones[get(i,j)];
                }
        }

    // 依次枚举 所有可选 的数
    for(int j = get(x,y);j; j -= lowbit(j)){
        int t = map[lowbit(j)];

        col[y] -= 1 << t;
        row[x] -= 1 << t;
        cell[x / 3][y / 3] -= 1 << t;
        str[x * 9 + y] = '1' + t;

        if(dfs(cnt - 1)) return true;

        // 恢复 现场
        col[y] += 1 << t;
        row[x] += 1 << t;
        cell[x / 3][y / 3] += 1 << t;
        str[x * 9 + y] = '.';
    }

    return false;
}

void work(){
    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';
                row[i] -= 1 << t;
                col[j] -= 1 << t;
                cell[i / 3][j / 3] -= 1 << t;
            }
            else cnt ++ ;
        }
    dfs(cnt);
}

int main(){

    for(int i = 0;i < N;i++) map[1 << i] = i;
    for(int i = 0;i < 1 << N;i ++ ){
        int res = 0;
        for(int j = i;j; j -= lowbit(j)) res ++ ;
        ones[i] = res;
    }

    while(cin >> str, str[0] != 'e'){
        init();
        work();
        cout << str << endl;
    }

    return 0;
}


活动打卡代码 AcWing 177. 噩梦

沧笙
14天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 810;

int n, m;
char g[N][N];
int st[N][N];
PII ghost[2];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool check(int x, int y, int step){

    if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 'X') return false;

    for (int i = 0; i < 2; i ++ )
        if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2)
            return false;

    return true;
}

int bfs(){

    memset(st, 0, sizeof st);

    int cnt = 0;
    PII boy, girl;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'M') boy = {i, j};
            else if (g[i][j] == 'G') girl = {i, j};
            else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};


    queue<PII> qa, qb;
    qa.push(boy);
    qb.push(girl);

    int step = 0;
    while (qa.size() || qb.size()){

        step ++ ;
        for (int i = 0; i < 3; i ++ )
            for (int j = 0, len = qa.size(); j < len; j ++ ){

                auto t = qa.front();
                qa.pop();
                int x = t.first, y = t.second;

                if (!check(x, y, step)) continue;

                for (int k = 0; k < 4; k ++ ){

                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step)){

                        if (st[a][b] == 2) return step;
                        if (!st[a][b]){

                            st[a][b] = 1;
                            qa.push({a, b});

                        }
                    }
                }
            }

        for (int i = 0; i < 1; i ++ )
            for (int j = 0, len = qb.size(); j < len; j ++ ){

                auto t = qb.front();
                qb.pop();

                int x = t.first, y = t.second;

                if (!check(x, y, step)) continue;

                for (int k = 0; k < 4; k ++ ){

                    int a = x + dx[k], b = y + dy[k];

                    if(check(a, b, step)){

                        if (st[a][b] == 1) return step;
                        if (!st[a][b]){

                            st[a][b] = 2;
                            qb.push({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]);

        printf("%d\n", bfs());
    }

    return 0;
}


活动打卡代码 AcWing 189. 乳草的入侵

沧笙
14天前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int n, m;
PII start;
char g[N][N];
int dist[N][N];

int bfs(){

    int ans = 0;

    memset(dist, -1, sizeof dist);
    queue<PII> q;
    q.push(start);
    dist[start.x][start.y] = 0;

    while(q.size()){

        auto t = q.front(); q.pop();

        for(int i = -1;i <= 1;i ++ )
            for(int j = -1;j <= 1;j ++ ){
                if(!i && !j) continue;
                int dx = t.x + i, dy = t.y + j;
                if(dx < 1 || dx > n || dy < 1 || dy > m) continue;
                if(dist[dx][dy] != -1) continue;
                if(g[dx][dy] == '*') continue;
                dist[dx][dy] = dist[t.x][t.y] + 1;
                ans = max(dist[dx][dy], ans);
                q.push({dx, dy});
            }
    }
    return ans;
}

int main(){

    cin >> m >> n >> start.y >> start.x;
    start.x = n + 1 - start.x;

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

    cout << bfs() << endl;

    return 0;
}