头像

zhaodaxing


访客:1290

离线:17小时前


活动打卡代码 AcWing 109. 天才ACM

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 500005;

int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];

ll sq(ll x){
    return x * x;
}

bool check(int l, int mid, int r){
    for (int i = mid; i < r; i ++)
        t[i] = w[i];
    sort(t + mid, t + r);
    int i = l, j = mid, k = 0;
    while(i != mid && j != r)
        if(t[i] < t[j])
            tmp[k ++] = t[i ++];
        else
            tmp[k ++] = t[j ++];
    while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素
    while (j != r) tmp[k ++ ] = t[j ++ ];
    ll sum = 0;                             // 计算校验值
    for (i = 0; i < m && i < k; i ++ , k -- )
        sum += sq(tmp[i] - tmp[k - 1]);
    return sum <= T;    
}

int main()
{
    int K;
    scanf("%d", &K);
    while (K -- )
    {
        scanf("%d %d %lld\n", &n, &m, &T);
        for (int i = 0; i < n; i ++ )
            scanf("%lld", &w[i]);
        ans = 0;
        int len;
        int start = 0, end = 0;
        while (end < n)
        {
            len = 1;
            while (len)
            {
                if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法
                {
                    end += len, len <<= 1;
                    if (end >= n) break ;               // 一个小剪枝,如果 end >= n,那么直接跳出
                    for (int i = start; i < end; i ++ ) // 在 check 时,已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可
                        t[i] = tmp[i - start];          // 复制的时候注意下标变换,tmp 是从 0 开始存的,t 是从 start 开始存的
                }
                else    len >>= 1;
            }
            start = end;
            ans ++ ;
        }
        printf("%d\n", ans);
    }
    return 0;
}



活动打卡代码 AcWing 292. 炮兵阵地

#include <iostream>
#include <vector>
using namespace std;
//f[i][j][k] 表示 已经摆完前i 行, 第i - 1行状态为j, 第 i行的状态 为k
const int N = 12, M = 1 << 12;
int f[2][M][M];
vector<int> state;
int cnt[M];
int n, m;
int g[N];
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 ++) res += state >> i & 1;
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 0; 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 = 0; i < n + 2; 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[u], b = state[j], c = state[k];//a表示i - 2行状态  b表示i - 1行状态 , c表示 i 行状态 
                    if(a & b || b & c || a & c) continue;
                    if(g[i] & c) continue;
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[c]);
                }
    cout << f[n + 1 & 1][0][0] << endl;
    return 0;
}


活动打卡代码 AcWing 292. 炮兵阵地

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

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

int n, m;
int g[1010];
int f[2][M][M];//f[i][j][k] 表示已经摆完前i行,第i - 1行的状态为j, 第i行的状态为k
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 ++) // 第 i - 1 行的状态
            for(int k = 0; k < state.size(); k ++) // 第 i 行的状态
                for(int u = 0; u < state.size(); u ++) // 第 i - 2行的状态
                {
                    int a = state[j], b = state[k], c = state[u];// a表示 i - 1行的,b 表示 第 i行的状态, c 表示 i - 2行的状态
                    if(a & b | b & c | a & 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;
}


活动打卡代码 AcWing 327. 玉米田

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];

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

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++){
            int t;
            cin >> t;
            w[i] += !t * (1 << j);
        }
    for(int i = 0; i < 1 << m; i ++ )
        if(check(i))
            state.push_back(i);
    for (int i = 0; i < state.size(); i ++)
        for(int j = 0; j < state.size(); j ++){
            int a = state[i], b = state[j];
            if(!(a & b))
                head[i].push_back(j);
        }
    f[0][0] = 1;
    for(int i = 1; i <= n + 1; i ++)
        for(int j = 0; j < state.size(); j ++)
            if(!(state[j] & w[i]))
                for(int k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
    cout << f[n + 1][0] << endl;
    return 0;
}


活动打卡代码 AcWing 1064. 小国王

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
LL f[N][K][M];
vector<int> state;
vector<int> head[M];
int cnt[N];
int n, m;

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

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


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

    for(int i = 0; i < state.size(); i ++)
        for(int j = 0; j < state.size(); j ++){
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b)) 
                head[i].push_back(j);
        }
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int a = 0; a < state.size(); a ++ )
                for (int b : head[a])
                {
                    int c = cnt[state[a]];
                    if (j >= c)
                        f[i][j][a] += f[i - 1][j - c][b];
                }
    cout << f[n + 1][m][0] << endl;
    return 0;

}


新鲜事 原文

左撇子,才发现自己码了半年代码,左手是正常指法,右手是一指禅,可怕是的,一指禅竟然还能盲打。速度还挺快的。现在已经在慢慢回归正常指法。。。练习,练习,练习。。。


活动打卡代码 AcWing 286. 选课

#include <iostream>
using namespace std;
const int N = 310;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int f[N][N];

void dfs(int u){
    for(int i = h[u]; ~i; i = ne[i]){
        int son = e[i];
        dfs(son);

        for(int j = m - 1; j >= 0; j --)
            for(int k = 1; k <= j; k ++ )
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }

    for(int i = m; i; i --) f[u][i] = f[u][i - 1] + w[u];
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n;i ++){
        int father;
        cin >> father >> w[i];
        add(father, i);
    }

    m ++;
    dfs(0);

    cout << f[0][m] << endl;
    return 0;
}



#include <iostream>
#include <cstring>
using namespace std;
const int N = 6010;
int h[N], ne[N], e[N], w[N], idx;
int f[N][2];
bool st[N];
int n;

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

void dfs(int u){
    f[u][1] = w[u];

    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        dfs(j);

        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++ ){
        int a, b;
        cin >> a >> b;
        add(b, a);
        st[a] = true;
    }
    int root = 1;
    while(st[root]) root ++;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}


活动打卡代码 AcWing 284. 金字塔

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 310, mod = 1e9;
int f[N][N];
char str[N];
int main(){
    cin >> str + 1;
    int n = strlen(str + 1);
    if(n % 2 == 0) cout << 0 << endl;
    else{
        for(int len = 1; len <= n; len +=2)
            for(int l = 1; l + len -1 <= n; l ++ ){
                int r = l + len - 1;
                if(len == 1) f[l][r] = 1;
                else if(str[l] == str[r]){
                    for(int k = l; k < r; k += 2)
                        if(str[k] == str[r])
                            f[l][r] = (f[l][r] +(LL)f[l][k] * f[k + 1][r - 1]) % mod;
                }
            }
        cout << f[1][n] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 283. 多边形

#include <iostream>
using namespace std;

const int N = 110, INF = 32768;

int n;
int w[N];
char c[N];
int f[N][N], g[N][N];

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

    for(int len = 1; len <= n; len ++ )
        for(int l = 1; l + len - 1 <= 2 * n; l ++ ){
            int r = l + len - 1;
            if(len == 1) f[l][r] = g[l][r] = w[l];
            else{
                f[l][r] = -INF, g[l][r] = INF;
                for(int k = l; k < r; k ++ ){
                    char op = c[k + 1];
                    int minl = g[l][k], minr = g[k + 1][r];
                    int maxl = f[l][k], maxr = f[k + 1][r];
                    if(op == 't'){
                        f[l][r] = max(f[l][r], maxl + maxr);
                        g[l][r] = min(g[l][r], minl + minr);
                    }else{
                        int x1 = maxl * maxr, x2 = maxl * minr, x3 = minl * maxr, x4 = minl * minr;
                        f[l][r] = max(f[l][r], max(max(x1, x2), max(x3, x4)));
                        g[l][r] = min(g[l][r], min(min(x1, x2), min(x3, x4)));
                    }

                }
            }
        }

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

        cout << res << endl;

        for(int i = 1; i <= n; i ++ )
            if(res == f[i][i + n - 1])
                cout << i << ' ';
        return 0;
}