头像

kukudewen


访客:986

离线:57分钟前


活动打卡代码 AcWing 1090. 绿色通道

kukudewen
22小时前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k)
{
    f[0] = 0;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && q[hh] < i - k - 1) hh ++ ;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = INF;
    for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]);

    return res <= m;
}

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

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

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}


活动打卡代码 AcWing 1090. 绿色通道

kukudewen
23小时前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k)
{
    f[0] = 0;
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (hh <= tt && q[hh] < i - k - 1) hh ++ ;
        f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = INF;
    for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]);

    return res <= m;
}

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

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

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}



活动打卡代码 AcWing 1087. 修剪草坪

kukudewen
23小时前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+100;

int a[N];
LL s[N];
int q[N];
LL f[N];   //f[i] 表示在前i头牛中所有合法法案的最大效率值
int n,m;

LL g(int x){
    return f[x-1] - s[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;

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

    int hh = 0, tt = 0;

    for(int i = 1; i<=n; i++){
        if(q[hh] < i-m) hh++;  //队头已经不在区间内
        f[i] = max(f[i-1], g(q[hh])+ s[i]);
        while(hh<=tt && g(q[tt]) <= g(i)) tt--;
        q[++tt] = i;
    }

    cout<<f[n];

    return 0;
}




活动打卡代码 AcWing 1091. 理想的正方形

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

using namespace std;

const int N = 1010, INF = 1e9;

int n, m, k;
int w[N][N];
int row_min[N][N], row_max[N][N];
int q[N];

void get_min(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}



int main()
{
    scanf("%d%d%d", &n, &m, &k);

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

    for (int i = 1; i <= n; i ++ )
    {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }

    int res = INF;
    int a[N], b[N], c[N];
    for (int i = k; i <= m; i ++ )
    {
        for (int j = 1; j <= n; j ++ ) a[j] = row_min[j][i];
        get_min(a, b, n);

        for (int j = 1; j <= n; j ++ ) a[j] = row_max[j][i];
        get_max(a, c, n);·  

        for (int j = k; j <= n; j ++ ) res = min(res, c[j] - b[j]);
    }

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 1089. 烽火传递

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

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

int n, m;
int w[N], q[N];
int f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - m) hh ++ ;
            f[i] = f[q[hh]] + w[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
        q[ ++ tt] = i;
    }

    int res = INF;
    for (int i = n - m + 1; i <= n; i ++ ) res = min(res, f[i]);

    printf("%d\n", res);

    return 0;
}



活动打卡代码 AcWing 135. 最大子序和

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

using namespace std;

const int N=300010;

int n,m;
int s[N],q[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }

    int res=-1e9;
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-m) hh++;
        res=max(res,s[i]-s[q[hh]]);
        while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
        q[++tt]=i;
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 166. 数独

#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)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

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

    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))
    {
        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()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    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;
}




活动打卡代码 AcWing 181. 回转游戏

/*
      0     1
      2     3
4  5  6  7  8  9  10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/

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

using namespace std;

const int N = 24;

int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

int oppsite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int q[N];
int path[100];

int f()
{
    static int sum[4];
    memset(sum, 0, sizeof sum);
    for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;

    int maxv = 0;
    for (int i = 1; i <= 3; i ++ ) maxv = max(maxv, sum[i]);

    return 8 - maxv;
}

void operate(int x)
{
    int t = q[op[x][0]];
    for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
    q[op[x][6]] = t;
}

bool dfs(int depth, int max_depth, int last)
{
    if (depth + f() > max_depth) return false;
    if (f() == 0) return true;

    for (int i = 0; i < 8; i ++ )
        if (last != oppsite[i])
        {
            operate(i);
            path[depth] = i;
            if (dfs(depth + 1, max_depth, i)) return true;
            operate(oppsite[i]);
        }

    return false;
}

int main()
{
    while (cin >> q[0], q[0])
    {
        for (int i = 1; i < 24; i ++ ) cin >> q[i];

        int depth = 0;
        while (!dfs(0, depth, -1)) depth ++ ;

        if (!depth) printf("No moves needed");
        else
        {
            for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
        }
        printf("\n%d\n", q[6]);
    }

    return 0;
}



活动打卡代码 AcWing 180. 排书

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

using namespace std;

const int N = 15;

int n;
int q[N];
int w[5][N];

int f()
{
    int cnt = 0;
    for (int i = 0; i + 1 < n; i ++ )
        if (q[i + 1] != q[i] + 1)
            cnt ++ ;
    return (cnt + 2) / 3;
}

bool dfs(int depth, int max_depth)
{
    if (depth + f() > max_depth) return false;
    if (!f()) return true;

    for (int len = 1; len <= n; len ++ )
        for (int l = 0; l + len - 1 < n; l ++ )
        {
            int r = l + len - 1;
            for (int k = r + 1; k < n; k ++ )
            {
                memcpy(w[depth], q, sizeof q);
                int x, y;
                for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
                for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
                if (dfs(depth + 1, max_depth)) return true;
                memcpy(q, w[depth], sizeof q);
            }
        }

    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> q[i];

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth ++ ;
        if (depth >= 5) puts("5 or more");
        else cout << depth << endl;
    }

    return 0;
}



活动打卡代码 AcWing 171. 送礼物

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

using namespace std;

typedef long long LL;

const int N = 46;

int n, m, k;
int w[N];
int weights[1 << 25], cnt = 1;
int ans;

void dfs1(int u, int s)
{
    if (u == k)
    {
        weights[cnt ++ ] = s;
        return;
    }

    dfs1(u + 1, s);
    if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);
}

void dfs2(int u, int s)
{
    if (u >= n)
    {
        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if ((LL)s + weights[mid] <= m) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, s + weights[l]);
        return;
    }

    dfs2(u + 1, s);
    if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);
}

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

    sort(w, w + n);
    reverse(w, w + n);

    k = n / 2 + 2;
    dfs1(0, 0);

    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights;

    dfs2(k, 0);

    cout << ans << endl;

    return 0;
}