头像

acwing_kai


访客:218

离线:2天前


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

#include <bits/stdc++.h>

using namespace std;
const int maxn = 110;
int n;
vector<int> ans;
int dep;
bool dfs(int now){
    if(now == dep) return ans.back() == n;
    bool vis[maxn] = {0};
    for(int i = ans.size() - 1; i >= 0; -- i)
        for(int j = i; j >= 0; -- j){
            int val = ans[i] + ans[j];
            if(vis[val] || val > n || val <= ans[now - 1]) continue;
            vis[val] = 1;
            ans.push_back(val);
            if(dfs(now + 1)) return true;
            ans.pop_back();
            vis[val] = 0;
        }

    return false;
}

int main(){
    while(scanf("%d", &n), n){
        ans.clear();
        dep = 1;
        ans.push_back(1);
        while(!dfs(1)){
            dep ++;
        }
        for(int i = 0; i < dep; ++ i) printf("%d ", ans[i]);
        cout << endl;
    }
    return 0;
}


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

#include <bits/stdc++.h>

using namespace std;

const int maxn = 25;
const int inf = 0x3f3f3f3f;

int n, m;
int mins[maxn], minv[maxn];
int r[maxn], h[maxn];
int ans = inf;

void init(){
    mins[0] = 0, minv[0] = 0;
    for(int i = 1; i <= 20; ++ i){
        mins[i] += mins[i - 1];
        mins[i] += 2 * i * i;
        minv[i] += minv[i - 1];
        minv[i] += i * i * i;
    }
}

void dfs(int dep, int v, int s){
    if(n - v < minv[dep]) return ;
    if(s + mins[dep] >= ans) return;
    if((2 * (n - v) / r[dep + 1]) + s >= ans) return;

    if(dep == 0){
        if(v == n) ans = min(ans, s);
        return;
    }

    for(int i = min((int)sqrt(n - v), r[dep + 1] - 1); i >= dep; i --){
        for(int j = min(h[dep + 1] - 1, (n - v) / i / i); j >= dep; j --){
            int now = 0;
            if(dep == m) now = i * i;
            r[dep] = i, h[dep] = j;
            dfs(dep - 1, v + i * i * j, s + 2 * i * j + now);
        }
    }
}

int main(){
    cin >> n >> m;
    init();
    r[m + 1] = h[m + 1] = inf;

    dfs(m, 0, 0);
    if(ans == inf) ans = 0;
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 167. 木棒

#include <bits/stdc++.h>

using namespace std;

const int maxn = 70;
int n, a[maxn], sum;
bool vis[maxn];
bool cmp(int x, int y){
    return x > y;
}
int cnt, len;

//拼接到第now根,当前第now根当前的长度,遍历的开始位置
bool dfs(int now, int rest, int pos){
    if(now == cnt) return true;
    if(rest == len) return dfs(now + 1, 0, 0);

    for(int i = pos; i < n; ++ i){
        if(vis[i]) continue;
        if(vis[i] == 0 && rest + a[i] <= len){
            vis[i] = 1;
            if(dfs(now, rest + a[i], i + 1)) return true;
            vis[i] = 0;
        }

        if(rest == 0) return false;
        if(rest + a[i] == len) return false;
        int j = i;
        while(j < n && a[j] == a[i]) j++;
        i = j - 1;
    }
    return false;
}

int main(){
    while(cin >> n, n){
        sum = 0;
        int maxx = 0, cnm = 0;
        for(int i = 0, x; i < n; ++ i){
            cin >> x;
            if(x > 50) continue;
            a[cnm] = x;
            sum += a[cnm], maxx = max(maxx, a[cnm]);
            cnm ++;
        }
        sort(a, a + n, cmp);
        n = cnm;
        int ans = sum;
        bool flag = 0;
        for(int i = maxx; i <= sum / 2; ++ i)
            if(sum % i == 0){
                cnt = sum / i;
                len = i;
                memset(vis, 0, sizeof(vis));
                if(dfs(0, 0, 0)){
                    flag = 1;
                    ans = len;
                    break;
                }
            }
        cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 166. 数独

#include <bits/stdc++.h>

using namespace std;

const int maxn = 9;

int row[maxn] , col[maxn] , cell[3][3];
char str[100];

int one_num[1 << maxn];//表示某一个数的二进制表示中有多少个‘1’
int Map[1 << maxn];/*
lowbit(101000) = 1000 = 8
但是我们需要的是第三位
所以我们令Map[8] = 3
相似的Map[0] = 0 , Map[2] = 1 , Map[4] = 2 ...
*/
inline int lowbit(int x){
    return x & -x;
}

void pre_init(){
    //初始化Map[]
    for(int i = 0 ; i < maxn ; ++ i)
        Map[1 << i] = i;
    //初始化one_num[]
    for(int i = 0 ; i < 1 << maxn ; ++ i){
        int s = 0;
        for(int j = i ; j ; j -= lowbit(j)) s ++;
        one_num[i] = s;
    }
}
int cnt; //有cnt个要填的格子
void init(){
    for(int i = 0 ; i < maxn ; ++ i) 
        row[i] = col[i] = (1 << maxn) - 1;
    for(int i = 0 ; i < 3 ; ++ i)
        for(int j = 0 ;  j < 3 ; ++ j)
            cell[i][j] = (1 << maxn) - 1;

    //将已经有的位置对应的行、列、九宫格状态改变
    cnt = 0;
    for(int i = 0 , pos = 0 ; i < maxn ; ++ i)
        for(int j = 0 ; j < maxn ; ++ j , ++ pos)
            if(str[pos] != '.'){
                int t = str[pos] - '1'; //1对应二进制第0位
                row[i] -= 1 << t;
                col[j] -= 1 << t;
                cell[i/3][j/3] -= 1 << t;
            }else cnt ++;
}
//求可选方案的交集
inline int get(int x , int y){
    return row[x] & col[y] & cell[x/3][y/3];
}

bool dfs(int num){
    if(!num) return true;
    //(1)、选择出可选方案数最少的格子
    int minn = 10;
    int x , y;
    for(int i = 0 ; i < maxn ; ++ i)
        for(int j = 0 ; j < maxn ; ++ j)
            if(str[i * 9 + j] == '.'){
                int t = one_num[get(i, j)];
                if(t < minn){
                    minn  = t , x = i , y = j;
                }
            }

    for(int i = get(x , y) ; i ; i -= lowbit(i)){
        int t = Map[lowbit(i)];

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

        if(dfs(num - 1)) return true;
        //恢复现场
        row[x] += 1 << t;
        col[y] += 1 << t;
        cell[x / 3][y /3] += 1 << t;
        str[x * 9 + y] = '.';
    }

    return false;
}

int main(){
    pre_init();
    while(cin >> str , str[0] != 'e'){
        init();
        dfs(cnt);
        cout << str << endl;
    }
    return 0;
}


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

#include <bits/stdc++.h>

using namespace std;

int n, w;
int c[20], cab[20];

bool  cmp(int x, int y){
    return x > y;
}

int ans;

void dfs(int now, int cnt){ //(当前遍历到的猫,已经租用了cnt辆缆车)
    if(cnt >= ans) return;
    if(now == n){
        ans = min(cnt, ans);
        return;
    }
    for(int i = 1; i <= cnt; ++ i){
        if(cab[i] + c[now] <= w){
            cab[i] += c[now];
            dfs(now + 1, cnt);
            cab[i] -= c[now];
        }
    }

    cab[cnt + 1] = c[now];
    dfs(now + 1, cnt + 1);
    cab[cnt + 1] = 0;
}

int main(){
    cin >> n >> w;
    for(int i = 0; i < n; ++ i) cin >> c[i];
    sort(c, c + n, cmp);
    ans = n;
    dfs(0, 0);
    cout << ans << endl;
}


活动打卡代码 AcWing 164. 可达性统计

/**
 * 逆拓扑排序
 * STL -> bitset 状态记录
 */
#include <bits/stdc++.h>

using namespace std;
const int maxn = 30005;

int head[maxn], Next[maxn], ver[maxn];
int n, m, tot = 1;
int deg[maxn];
bitset<maxn> f[maxn];

void add(int x,int y){
    ver[++ tot] = y;
    Next[tot] = head[x], head[x] = tot;
}

void topsort(){
    queue<int> q;
    for(int i = 1; i <= n; ++ i)
        if(deg[i] == 0) q.push(i), f[i][i] = 1;

    while(q.size()){
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i];
            f[y] |= f[x];
            deg[y] --;
            if(deg[y] == 0){
                f[y][y] = 1;
                q.push(y);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; ++ i) {
        int x, y;
        cin >> x >> y;
        deg[x] ++;
        add(y, x);
    }
    topsort();
    for(int i = 1; i <= n; ++ i)
        cout << f[i].count() <<endl;
    return 0;
}


活动打卡代码 AcWing 149. 荷马史诗

#include <bits/stdc++.h>

using namespace std;

int n, k;
typedef long long ll;
priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq; //<val, depth>

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) {
        long long x;
        cin >> x;
        pq.push({x, 0});
    }
    while((n - 1) % (k - 1) != 0) {
        pq.push({0, 0});
        n ++;
    };
    ll ans = 0;
    while(pq.size() > 1){
        int depth = 0;
        ll sum = 0;
        for(int i = 0; i < k; ++ i){
            ll val = pq.top().first;
            sum += val;
            depth = max(depth, pq.top().second);
            pq.pop();
        }
        ans += sum;
        pq.push({sum, depth + 1});
    }
    cout << ans << endl << pq.top().second;
    return 0;
}


活动打卡代码 AcWing 149. 荷马史诗

题目使用k进制隐含用k叉Huffman树进行哈夫曼编码压缩文章长度

所用算法和应用:

k叉Huffman树哈夫曼编码


k叉Huffman树节点数n与k的关系(不满足则补‘0’):
$$
(n - 1) \% (k - 1) == 0
$$

#include <bits/stdc++.h>

using namespace std;

int n, k;
typedef long long ll;
priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq; //<val, depth>

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) {
        long long x;
        cin >> x;
        pq.push({x, 0});
    }
    while((n - 1) % (k - 1) != 0) {
        pq.push({0, 0});
        n ++;
    };
    ll ans = 0;
    while(pq.size() > 1){
        int depth = 0;
        ll sum = 0;
        for(int i = 0; i < k; ++ i){
            ll val = pq.top().first;
            sum += val;
            depth = max(depth, pq.top().second);
            pq.pop();
        }
        ans += sum;
        pq.push({sum, depth + 1});
    }
    cout << ans << endl << pq.top().second;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

#include <bits/stdc++.h>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int> > pq;

int main(){
    cin >> n;
    for(int i = 0, x; i < n; ++ i) cin >> x, pq.push(x);
    int ans = 0;
    while(pq.size() > 1){
        int x1 = pq.top();
        pq.pop();
        int x2 = pq.top();
        pq.pop();
        pq.push(x1 + x2);
        ans += x1 + x2;
    }
    cout << ans<< endl;
    return 0;
}


活动打卡代码 AcWing 146. 序列

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

const int maxn = 2005;
int T, m, n;
int a[maxn], b[maxn], tmp[maxn];

void merge(){
    priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for(int i = 0; i < n; ++ i) pq.push({a[0] + b[i], 0});
    int cnt = 0;
    for(int i = 0; i < n; ++ i){
        int val = pq.top().first, pos = pq.top().second;
        pq.pop();
        tmp[cnt ++] = val;
        pq.push({val - a[pos] + a[pos + 1], pos + 1});
    }

    for(int i = 0; i < n; ++ i) a[i] = tmp[i];
}

int main(){
    cin >> T;
    while(T --){
        cin >> m >> n;
        for(int i = 0; i < n; ++ i) cin >> a[i];
        sort(a, a + n);
        for(int i = 1; i < m; ++ i){
            for(int j = 0; j < n; ++ j) cin >> b[j];
            sort(b, b + n);
            merge();
        }

        for(int i = 0; i < n; ++ i) cout << a[i] << " ";
        cout << endl;
    }
    return 0;
}