头像

lew2018

$\color{#32CD32}{羊村}$




在线 



lew2018
1个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 220, M = (N + 10000) * 2, INF = 1e8;

int n, m, S, T, s, t;
int h[N], e[M], f[M], ne[M], idx;
int d[N], q[N], cur[N], A[N];

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

bool bfs() {
    memset(d, -1, sizeof(d));
    d[S] = 0, q[0] = S, cur[S] = h[S];
    int hh = 0, tt = 0;
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
        int ver = e[i];
        cur[u] = i;
        if (d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            f[i] -= t, f[i^1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) {
        while (flow = find(S, INF)) r += flow;
    }
    return r;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    S = 0, T = n + 1;
    memset(h, -1, sizeof(h));
    for (int i = 1; i <= m; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, d - c);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (A[i] < 0) add(i, T, -A[i]);
        else if (A[i] > 0) add(S, i, A[i]), tot += A[i];
    }
    add(t, s, INF);
    if (dinic() < tot) puts("No Solution");
    else {
        int res = f[idx - 1];
        S = s, T = t;
        f[idx - 1] = f[idx - 2] = 0;
        printf("%d\n", res + dinic());
    }
    return 0;
}


活动打卡代码 AcWing 1613. 数独简单版

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 10;

char s[N][N];
int row[N][N], col[N][N], cell[4][4][N];

bool dfs(int x, int y) {
    if (y == 9) x++, y = 0;
    if (x == 9) {
        for (int i = 0; i < 9; i++) cout << s[i] << endl;
        return true;
    }
    for (int i = 0; i < 9; i++) {
        if (s[x][y] != '.') return dfs(x, y + 1);
        if (!row[x][i] && !col[y][i] && !cell[x/3][y/3][i]) {
            row[x][i] = col[y][i] = cell[x/3][y/3][i] = true;
            s[x][y] = i + '1';
            dfs(x, y + 1);
            row[x][i] = col[y][i] = cell[x/3][y/3][i] = false;
            s[x][y] = '.';
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < 9; i++) {
        cin >> s[i];
        for (int j = 0; j < 9; j++)
            if (s[i][j] != '.') {
                row[i][s[i][j]-'1'] = true;
                col[j][s[i][j]-'1'] = true;
                cell[i/3][j/3][s[i][j]-'1'] = true;
            }
    }
    dfs(0, 0);
    return 0;
}


活动打卡代码 AcWing 1230. K倍区间

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 100010;

typedef long long LL;

int n, k;
LL s[N], cnt[N], res;

int main() {
    read(n), read(k);
    for (int i = 1; i <= n; i++) {
        read(s[i]);
        s[i] += s[i-1];
    }
    cnt[0]++;
    for (int i = 1; i <= n; i++) {
        res += cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 426. 开心的金明

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
         if (ch == '-') f = -1;
         ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 30010;

int total, n;
int v[N], p[N];
int f[N];

int main() {
    read(total), read(n);
    for (int i = 1; i <= n; i++) {
        read(v[i]); read(p[i]); p[i] *= v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = total; j >= v[i]; j--)
            f[j] = max(f[j], f[j-v[i]] + p[i]);
    }
    cout << f[total] << endl;
    return 0;
}


活动打卡代码 AcWing 1414. 牛异或

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 1e5 + 10;

int n;
int s[N], son[N*21][2], End[N*21], idx;

void insert(int k, int id) {
    int p = 0;
    for (int i = 20; i >= 0; i--) {
        int u = (k >> i) & 1;
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    End[p] = id;
}

int query(int k) {
    int p = 0;
    for (int i = 20; i >= 0; i--) {
        int u = (k >> i) & 1;
        if (son[p][!u]) p = son[p][!u];
        else p = son[p][u];
    }
    return End[p];
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(s[i]);
        s[i] ^= s[i-1];
    }
    int res = -1, l, r;
    insert(s[0], 0);
    for (int i = 1; i <= n; i++) {
        int k = query(s[i]);
        if ((s[i] ^ s[k]) > res) {
            res = (s[i] ^ s[k]);
            l = k + 1, r = i;
        }
        insert(s[i], i);
    }
    cout << res << " " << l << " " << r << endl;    
    return 0;
}


活动打卡代码 AcWing 126. 最大的和

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 110;
int n, s[N][N];

int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int w; read(w);
            s[i][j] = s[i-1][j] + w;
        }
    int res = -300;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int f = 0;
            for (int k = 1; k <= n; k++) {
                int w = s[j][k] - s[i-1][k];
                f = max(f, 0) + w;
                res = max(res, f);
            }
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 126. 最大的和

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 110;
int n, s[N][N];

int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int w; read(w);
            s[i][j] = s[i-1][j] + w;
        }
    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int f = 0;
            for (int k = 1; k <= n; k++) {
                int w = s[j][k] - s[i-1][k];
                f = max(f, 0) + w;
                res = max(res, f);
            }
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 479. 加分二叉树

lew2018
2个月前
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
    x *= f;
}

const int N = 40;

int n;
int a[N], f[N][N], g[N][N];

void dfs(int l, int r) {
    if (l > r) return;
    int k = g[l][r];
    cout << k << " ";
    dfs(l, k - 1); dfs(k + 1, r);
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int len = 1; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if (len == 1) f[i][j] = a[i], g[i][j] = i;
            else {
                for (int k = i; k <= j; k++)  {
                    int left = k == i ? 1 : f[i][k-1];
                    int right = k == j ? 1 : f[k+1][j];
                    int score = left * right + a[k];
                    if (score > f[i][j]) {
                        f[i][j] = score;
                        g[i][j] = k;
                    }
                }
            }
        }
    cout << f[1][n] << endl;
    dfs(1, n);
    return 0;
}


活动打卡代码 AcWing 1402. 星空之夜

lew2018
2个月前

重点是hash的方式

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x) {
    x = 0; int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - 48);
        ch = getchar();
    }
}

#define x first
#define y second

typedef pair<int, int> PII;
const int N = 110;
const double eps = 1e-6;

int n, m;
int top;
PII q[N * N];
char g[N][N];

double get_dist(PII a, PII b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double get_hash() {
    double sum = 0;
    for (int i = 0; i < top; i++)
        for (int j = i + 1; j < top; j++)
            sum += get_dist(q[i], q[j]);
    return sum;
}

char get_id(double key) {
    static double hash[30];
    static int id = 0;
    for (int i = 0; i < id; i++)
        if (fabs(hash[i] - key) < eps)
            return i + 'a';
    hash[id++] = key;
    return id - 1 + 'a';
}

void dfs(int a, int b) {
    q[top++] = {a, b};
    g[a][b] = '0';
    for (int i = a - 1; i <= a + 1; i++)
        for (int j = b - 1; j <= b + 1; j++) {
            if (i == a && j == b) continue;
            if (i >= 0 && i < n && j >= 0 && j < m && g[i][j] == '1')
                dfs(i, j);
        }
}

int main() {
    read(m), read(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') {
                top = 0;
                dfs(i, j);
                char c = get_id(get_hash());
                for (int k = 0; k < top; k++)
                    g[q[k].x][q[k].y] = c;
            }
    for (int i = 0; i < n; i++) cout << g[i] << endl;
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

lew2018
2个月前
#include<iostream>
using namespace std;

const int N = 110;
int a[N], g[N], h[N];

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

    for(int i = 1; i <= n; i ++)
    {
        g[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                g[i] = max(g[i], g[j] + 1);
    }

    for(int i = n; i ; i --)
    {
        h[i] = 1;
        for(int j = n; j > i; j --)
            if(a[j] < a[i])
                h[i] = max(h[i], h[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        res = max(res, h[i] + g[i] - 1);
    }

    cout << n - res << endl;

    return 0;
}