头像

Dragon_Skies

江西省南康中学




离线:6小时前


活动打卡代码 AcWing 170. 加成序列

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 105;
int a[N] ,dep ,n;
inline bool dfs(int now) {
    if (now > dep) return false;
    if (a[now] == n) return true;
    bool use[N];
    memset(use ,false ,sizeof(use));
    for (int i = now; i >= 1; i--)
        for (int j = i; j >= 1; j--) {
            int t = a[i] + a[j];
            if (t > n || use[t] || t <= a[now]) continue;
            a[now + 1] = t;
            use[t] = true;
            if (dfs(now + 1)) return true;
            a[now + 1] = 0;
        }
    return false;
}
signed main() {
    a[1] = 1;
    while (~scanf("%d" ,&n) && n) {
        dep = 1;
        while (!dfs(1)) dep++;
        for (int i = 1; i <= dep; i++) printf("%d%c" ,a[i] ," \n"[i == dep]);
    }
}


活动打卡代码 AcWing 168. 生日蛋糕

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int N = 17 ,INF = 0x3f3f3f3f;
int ans = INF ,n ,m ,minv[N] ,mins[N] ,r[N] ,h[N];
inline void dfs(int now ,int v ,int s) {
    if (v + minv[now] > n) return ;
    if (s + mins[now] >= ans) return ;
    if (s + 2 * (n - v) / r[now - 1] >= ans) return ;
    if (now > m) {
        if (v == n) ans = s;
        return ;
    }
    for (int i = min(r[now - 1] - 1 ,(int)sqrt(n - v)); i >= m - now + 1; i--)
        for (int j = min(h[now - 1] - 1 ,(n - v) / i / i); j >= m - now + 1; j--) {
            r[now] = i ,h[now] = j;
            if (now == 1) dfs(now + 1 ,v + i * i * j ,s + 2 * i * j + i * i);
            else dfs(now + 1 ,v + i * i * j ,s + 2 * i * j);
        }
}
signed main() {
    scanf("%d%d" ,&n ,&m);
    for (int i = m; i >= 1; i--) {
        minv[i] = minv[i + 1] + (m - i + 1) * (m - i + 1) * (m - i + 1);
        mins[i] = mins[i + 1] + 2 * (m - i + 1) * (m - i + 1);
    }
    r[0] = h[0] = INF;
    dfs(1 ,0 ,0);
    if (ans == INF) ans = 0;
    printf("%d\n" ,ans);
    return 0;
}


活动打卡代码 AcWing 167. 木棒

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 70;
int a[N] ,n ,sum ,len ,t; bool use[N];
inline bool dfs(int now ,int used ,int last) {
    if (now >= t) return true;
    if (used == len) return dfs(now + 1 ,0 ,1);
    int failed = 0;
    for (int i = last; i <= n; i++)
        if (!use[i] && used + a[i] <= len && a[i] != failed) {
            use[i] = true;
            if (dfs(now ,used + a[i] ,i + 1)) return true;
            use[i] = false;
            failed = a[i];
            if (used == 0 || used + a[i] == len) return false;
        }
    return false;
}
inline bool cmp(int a ,int b) {return a > b;}
signed main() {
    while (~scanf("%d" ,&n) && n) {
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            sum += a[i];
        }
        sort(a + 1 ,a + n + 1 ,cmp);
        for (int i = a[1]; i <= sum; i++) {
            if (sum % i) continue;
            len = i; t = sum / len;
            memset(use ,0 ,sizeof(use));
            if (dfs(0 ,0 ,1)) {
                printf("%d\n" ,i);
                break;
            }
        }
        sum = len = t = 0;
    }
}


活动打卡代码 AcWing 166. 数独

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#define ceil cl
using namespace std;
const int N = 10 ,n = 9;
int row[N] ,col[N] ,ceil[4][4] ,lg[1 << N] ,ones[1 << N] ,a[N][N];
inline int lowbit(int x) {return x & (-x);}
inline void build() {
    for (int i = 1; i <= n; i++) lg[1 << (i - 1)] = i;
    for (int i = 1; i < (1 << n); i++)
        ones[i] = ones[i - lowbit(i)] + 1;
}
inline void rebuild() {
    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++)
            ceil[i][j] = (1 << n) - 1;
}
inline void draw(int x ,int y ,int t) {
    int v = 1 << (t - 1);
    a[x][y] = t;
    row[x] -= v;
    col[y] -= v;
    ceil[x / 3][y / 3] -= v;
}
inline void clear(int x ,int y) {
    int v = 1 << (a[x][y] - 1);
    a[x][y] = 0;
    row[x] += v;
    col[y] += v;
    ceil[x / 3][y / 3] += v;
}
inline int get(int x ,int y) {
    return row[x] & col[y] & ceil[x / 3][y / 3];
}
inline void print() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d" ,a[i][j]);
    puts("");
}
int x = 1 ,y = 1;
inline bool dfs(int cnt) {
    if (cnt == 0) {
        print();
        return true;
    } 
    int x ,y ,maxv = 10;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j] == 0) {
                int state = get(i ,j);
                if (ones[state] < maxv) {
                    maxv = ones[state];
                    x = i ,y = j;
                }
            }
    int state = get(x ,y);
    for (int i = state; i ; i -= lowbit(i)) {
        int t = lg[lowbit(i)];
        draw(x ,y ,t);
        if (dfs(cnt - 1)) return true;
        clear(x ,y);
    }
    return false;
}
char s[n * n];
signed main() {
    build();
    while (~scanf("%s" ,s)) {
        if (s[0] == 'e') break;
        rebuild();
        int cnt = 0;
        for (int w = 0 ,i = 0; i < n; i++)
            for (int j = 0; j < n; j++ ,w++)
                if (s[w] == '.') cnt++;
                else draw(i ,j ,s[w] - '0');
        dfs(cnt);
        memset(a ,0 ,sizeof(a));
    }
    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

#include <cstdio>
#include <cstring>
#include <cctype>
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
inline int max(int a ,int b) {return a > b ? a : b;}
inline int min(int a ,int b) {return a < b ? a : b;}
const int N = 2e4 + 5 ,M = 2e5 + 5 ,INF = 0x3f3f3f3f;
struct Edge {
    int to ,w ,next;
    Edge (int to = 0 ,int w = 0 ,int next = 0) :
        to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,cnt;
inline void add(int u ,int v ,int w) {
    G[++cnt] = Edge(v ,w ,head[u]); head[u] = cnt;
    G[++cnt] = Edge(u ,w ,head[v]); head[v] = cnt;
}
int color[N];
inline bool dfs(int now ,int c ,int mid) {
    if (color[now] != -1 && color[now] != c) return false;
    else if (color[now] != -1) return true;
    color[now] = c;
    for (int i = head[now]; i ; i = G[i].next) {
        if (G[i].w <= mid) continue;
        int v = G[i].to;
        if (!dfs(v ,!c ,mid)) return false;
    }
    return true;
}
inline bool check(int n ,int mid) {
    memset(color ,-1 ,sizeof(color));
    for (int i = 1; i <= n; i++)
        if (color[i] == -1)
            if (!dfs(i ,0 ,mid)) return false;
    return true;
}
int n ,m ,maxn;
signed main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        int u = read() ,v = read() ,w = read();
        add(u ,v ,w); maxn = max(maxn ,w);
    }
    int l = 0 ,r = maxn;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(n ,mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n" ,l);
    return 0;
}


活动打卡代码 AcWing 372. 棋盘覆盖

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 1e4 + 5 ,M = 6e4 + 5 ,INF = 0x3f3f3f3f;
struct Edge {
    int to ,w ,next;
    Edge (int to = 0 ,int w = 0 ,int next = 0) : to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,cnt;
inline void add(int u ,int v ,int w) {
    G[++cnt] = Edge(v ,w ,head[u]); head[u] = cnt;
    G[++cnt] = Edge(u ,0 ,head[v]); head[v] = cnt;
}
namespace ISAP {
    int n ,s ,t ,cur[N] ,dep[N] ,gap[N];
    inline void bfs() {
        memset(dep ,0 ,sizeof(dep));
        memset(gap ,0 ,sizeof(gap));
        queue <int> q;
        dep[t] = 1; gap[1] = 1; q.push(t);
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (int i = head[now]; i ; i = G[i].next) {
                int v = G[i].to;
                if (!dep[v]) {
                    dep[v] = dep[now] + 1;
                    gap[dep[v]]++;
                    q.push(v);
                }
            }
        }
    }
    inline int ISAP(int now ,int flow) {
        if (now == t) return flow;
        int rest = 0;
        for (int i = cur[now]; i ; i = G[i].next) {
            int v = G[i].to ,w = G[i].w;
            if (dep[now] == dep[v] + 1 && w) {
                int t = ISAP(v ,min(flow - rest ,w));
                G[i].w -= t; G[i ^ 1].w += t; rest += t;
                if (flow == rest) return flow;
            }
        }
        gap[dep[now]]--;
        if (gap[dep[now]] == 0) dep[s] = n + 1;
        dep[now]++;
        gap[dep[now]]++;
        return rest;
    }
    inline int ISAP() {
        bfs();
        int flow = 0;
        while (dep[s] <= n) {
            for (int i = 1; i <= n; i++) cur[i] = head[i];
            flow += ISAP(s ,INF);
        }
        return flow;
    }
}
int n ,k; bool g[105][105];
inline int num(int x ,int y) {
    return (x - 1) * n + y;
}
signed main() {
    cnt = 1;
    n = read(); k = read();
    ISAP::n = n * n; ISAP::s = ISAP::n + 1; ISAP::t = ISAP::n + 2;
    ISAP::n += 2;
    for (int i = 1; i <= k; i++) {
        int x = read() ,y = read();
        g[x][y] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (g[i][j]) continue;
            if (i + j & 1) add(num(i ,j) ,ISAP::t ,1);
            else {
                add(ISAP::s ,num(i ,j) ,1);
                if (i > 1 && !g[i - 1][j]) add(num(i ,j) ,num(i - 1 ,j) ,1);
                if (j > 1 && !g[i][j - 1]) add(num(i ,j) ,num(i ,j - 1) ,1);
                if (i < n && !g[i + 1][j]) add(num(i ,j) ,num(i + 1 ,j) ,1);
                if (j < n && !g[i][j + 1]) add(num(i ,j) ,num(i ,j + 1) ,1);
            }
        }
    printf("%d\n" ,ISAP::ISAP());
    return 0;
}


活动打卡代码 AcWing 378. 骑士放置

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 1e4 + 5 ,M = 1e5 + 5 ,INF = 0x3f3f3f3f;
struct Edge {
    int to ,w ,next;
    Edge (int to = 0 ,int w = 0 ,int next = 0) : to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,cnt;
inline void add(int u ,int v ,int w) {
    G[++cnt] = Edge(v ,w ,head[u]); head[u] = cnt;
    G[++cnt] = Edge(u ,0 ,head[v]); head[v] = cnt;
}
namespace ISAP {
    int n ,s ,t ,cur[N] ,dep[N] ,gap[N];
    inline void bfs() {
        memset(dep ,0 ,sizeof(dep));
        memset(gap ,0 ,sizeof(gap));
        queue <int> q;
        dep[t] = 1; gap[1] = 1; q.push(t);
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (int i = head[now]; i ; i = G[i].next) {
                int v = G[i].to;
                if (!dep[v]) {
                    dep[v] = dep[now] + 1;
                    gap[dep[v]]++;
                    q.push(v);
                }
            }
        }
    }
    inline int ISAP(int now ,int flow) {
        if (now == t) return flow;
        int rest = 0;
        for (int i = cur[now]; i ; i = G[i].next) {
            cur[now] = i;
            int v = G[i].to ,w = G[i].w;
            if (dep[now] == dep[v] + 1 && w) {
                int t = ISAP(v ,min(flow - rest ,w));
                G[i].w -= t; G[i ^ 1].w += t; rest += t;
                if (flow == rest) return flow;
            }
        }
        gap[dep[now]]--;
        if (gap[dep[now]] == 0) dep[s] = n + 1;
        dep[now]++;
        gap[dep[now]]++;
        return rest;
    }
    inline int ISAP() {
        bfs();
        int flow = 0;
        while (dep[s] <= n) {
            for (int i = 1; i <= n; i++) cur[i] = head[i];
            flow += ISAP(s ,INF);
        }
        return flow;
    }
}
int n ,m ,k; bool g[105][105];
inline int num(int x ,int y) {
    return (x - 1) * m + y;
}
const int dx[] = {0 ,-2 ,-2 ,-1 ,-1 ,1 ,1 ,2 ,2} ,dy[] = {0 ,-1 ,1 ,-2 ,2 ,-2 ,2 ,-1 ,1};
signed main() {
    cnt = 1;
    n = read(); m = read(); k = read();
    ISAP::n = n * m; ISAP::s = ISAP::n + 1; ISAP::t = ISAP::n + 2;
    ISAP::n += 2;
    for (int i = 1; i <= k; i++) {
        int x = read() ,y = read();
        g[x][y] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!g[i][j]) {
                if ((i + j) & 1) add(ISAP::s ,num(i ,j) ,1);
                else add(num(i ,j) ,ISAP::t ,1);
                if ((i + j) & 1)
                for (int k = 1; k <= 8; k++) {
                    int tx = i + dx[k] ,ty = j + dy[k];
                    if (tx < 1 || ty < 1 || tx > n || ty > m || g[tx][ty])
                        continue;
                    add(num(i ,j) ,num(tx ,ty) ,1);
                }
            }
    printf("%d\n" ,n * m - ISAP::ISAP() - k);
    return 0;
}


活动打卡代码 AcWing 376. 机器任务

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 205 ,M = 2405 ,INF = 0x3f3f3f3f;
struct Edge {
    int to ,w ,next;
    Edge (int to = 0 ,int w = 0 ,int next = 0) : to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,cnt;
inline void add(int u ,int v ,int w) {
    G[++cnt] = Edge(v ,w ,head[u]); head[u] = cnt;
    G[++cnt] = Edge(u ,0 ,head[v]); head[v] = cnt;
}
namespace ISAP {
    int n ,s ,t ,dep[N] ,gap[N] ,cur[N];
    inline void bfs() {
        memset(dep ,0 ,sizeof(dep));
        memset(gap ,0 ,sizeof(gap));
        queue <int> q;
        dep[t] = 1; gap[1] = 1; q.push(t);
        while (!q.empty()) {
            int now = q.front(); q.pop();
            for (int i = head[now]; i ; i = G[i].next) {
                int v = G[i].to;
                if (!dep[v]) {
                    dep[v] = dep[now] + 1;
                    gap[dep[v]]++;
                    q.push(v);
                }
            }
        }
    }
    inline int ISAP(int now ,int flow) {
        if (now == t) return flow;
        int rest = 0;
        for (int i = cur[now]; i ; i = G[i].next) {
            cur[now] = i;
            int v = G[i].to ,w = G[i].w;
            if (dep[now] == dep[v] + 1 && w) {
                int t = ISAP(v ,min(flow - rest ,w));
                G[i].w -= t; G[i ^ 1].w += t; rest += t;
                if (flow == rest) return flow;
            }
        }
        gap[dep[now]]--;
        if (gap[dep[now]] == 0) dep[s] = n + 1;
        dep[now]++;
        gap[dep[now]]++;
        return rest;
    }
    inline int ISAP() {
        int flow = 0;
        bfs();
        while (dep[s] <= n) {
            for (int i = 1; i <= n; i++) cur[i] = head[i];
            flow += ISAP(s ,INF);
        }
        return flow;
    }
}
int n ,m ,k;
signed main() {
    while (n = read()) {
        cnt = 1;
        m = read() ,k = read();
        ISAP::n = n + m; ISAP::s = ISAP::n + 1; ISAP::t = ISAP::n + 2;
        ISAP::n += 2;
        for (int i = 1; i <= n; i++) add(ISAP::s ,i ,1);
        for (int i = 1; i <= m; i++) add(n + i ,ISAP::t ,1);
        for (int i = 1; i <= k; i++) {
            int useless = read() ,u = read() ,v = read();
            if (u == 0 || v == 0) continue;
            add(u ,n + v ,1);
        }
        printf("%d\n" ,ISAP::ISAP());
        memset(head ,0 ,sizeof(head));
    }
    return 0;
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 1e5 + 5 ,M = 2e5 + 5;
struct Edge {
    int to ,w ,next;
    Edge (int to = 0 ,int w = 0 ,int next = 0) : to(to) ,w(w) ,next(next) {}
}G[M]; int head[N] ,cnt;
inline void add(int u ,int v ,int w) {
    G[++cnt] = Edge(v ,w ,head[u]); head[u] = cnt;
}
double f[N]; int d[N] ,n ,m;
inline double dp(int now) {
    if (now == n) return 0;
    if (f[now] >= 0) return f[now];
    f[now] = 0;
    for (int i = head[now]; i ; i = G[i].next) {
        int v = G[i].to ,w = G[i].w;
        f[now] += (dp(v) + w) / d[now];
    }
    return f[now];
}
signed main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        int u = read() ,v = read() ,w = read();
        add(u ,v ,w);
        d[u]++;
    }
    memset(f ,-1 ,sizeof(f));
    printf("%.2lf\n" ,dp(1));
    return 0;
}


活动打卡代码 AcWing 165. 小猫爬山

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 20 ,INF = 0x3f3f3f3f ;
int used[N] ,tot ,n ,a[N] ,w ,ans = INF;
inline void dfs(int now) {
    if (tot > ans) return ;
    if (now > n) {
        ans = min(ans ,tot);
        return ;
    }
    for (int i = 1; i <= tot; i++)
        if (used[i] + a[now] <= w) {
            used[i] += a[now];
            dfs(now + 1);
            used[i] -= a[now];
        }
    used[++tot] = a[now];
    dfs(now + 1);
    used[tot--] = 0;
}
inline bool cmp(int a ,int b) {return a > b;}
signed main() {
    scanf("%d%d" ,&n ,&w);
    for (int i = 1; i <= n; i++) scanf("%d" ,&a[i]);
    sort(a + 1 ,a + n + 1 ,cmp);
    dfs(1);
    printf("%d\n" ,ans);
    return 0;
}