• Agri-Net

题意:给出图的邻接矩阵, 求最小生成树

分析:求MST最常用的方法是prim | kruskal, 我习惯用kruskal

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 101;
int maze[N][N], fa[N];
int n, m;

struct node{
    int x, y, z;
}a[N*N];

bool cmp(const node &x, const node &y){
    return x.z < y.z;
}

int find(int x){
    if(fa[x] != x){
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void solve(){
    sort(a, a+m, cmp);
    int ans = 0, cnt = 0;
    for(int i = 0; i < m; ++i){
        int fx = find(a[i].x);
        int fy = find(a[i].y);
        if(fx != fy){
            fa[fx] = fy;
            ans += a[i].z;
            ++cnt;
            if(cnt == n-1){
                printf("%d\n", ans);
                return ;
            }
        }
    }
}

int main(){
    freopen("agrinet.in", "r", stdin);
    freopen("agrinet.out", "w", stdout);
    scanf("%d", &n);
    m = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            scanf("%d", &maze[i][j]);
            if(i < j && maze[i][j]){
                a[m].x = i, a[m].y = j, a[m++].z = maze[i][j];
            }
        }
    }
    for(int i = 0; i < n; ++i){
        fa[i] = i;
    }
    solve();
    return 0;
}


  • Score Inflation

题意: 经典完全背包的背景

分析: 经典完全背包

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e4+10;
int dp[N];
int w[N], v[N];
int n, v_;

int maxab(int a, int b){
    if(a > b) return a;
    return b;
}

void solve(){
    for(int i = 0; i < n; ++i){
        for(int j = w[i]; j <= v_; ++j){
            dp[j] = maxab(dp[j-w[i]] + v[i], dp[j]);
        }
    }
    printf("%d\n", dp[v_]);
}

int main(){
   freopen("inflate.in", "r", stdin);
   freopen("inflate.out", "w", stdout);
   scanf("%d%d", &v_, &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &v[i], &w[i]);
    }
    solve();
    return 0;
}


  • Humble Numbers

题意:有n个prime数, 现在需要求第m个humble数, humble要求质因数只包含给出的n个prime中若干

分析: 刚开始由于没注意到数据的范围, 直接上set跟priority_queue, 后来发现memory efficiency是优化不掉的。 所以要从源头上改变。 每次构造一个新的humble数, 只要枚举n个prime数, 乘上当前的humble数, 找出最小的(大于当前humble数最大值)的数。 在枚举的时候为了提高效率, 不要每次暴力的从头开始枚举, 可以记录上一次记录的位置, 下次查找肯定是从当前位置之后找。

无法优化空间的代码, 过了11个测试点:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
vector<int > base;
set<LL > isExist;
priority_queue<LL, vector<LL>, greater<LL> > pq;
int n, m;

void solve(){
    pq.push(1LL);
    isExist.insert(1LL);
    int cnt = 0;
    while(true){
        LL p = pq.top();
        pq.pop(), ++cnt;
        if(cnt == m+1){
            printf("%lld\n", p);
            return ;
        }
        //if(cnt > m+1) continue;
        for(int i = 0; i < n; ++i){
            LL res = p*base[i];
            if(!isExist.count(res)){
                pq.push(res);
                isExist.insert(res);
            }
        }
    }
}

int main(){
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    scanf("%d%d", &n, &m);
    base.clear();
    int input;
    for(int i = 0; i < n; ++i){
        scanf("%d", &input);
        base.push_back(input);
    }
    solve();
    return 0;
}

AC的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N  = 1e5+10;
const int N_ = 1e2 + 1;
typedef long long LL;
//vector<LL > ans;
LL ans[N];
int cnt;
int n, m;
int base[N_], pos[N_];
//vector<int > base, pos;

void solve(){
    for(int i = 0; i < n; ++i){
        pos[i] = 0;
    }

    cnt = 0;
    ans[cnt++] = 1;
    LL min, minPos;
    while(cnt <= m){
        min = 1e20;
        for(int i = 0; i < n; ++i){
            while(base[i]*ans[pos[i]] <= ans[cnt-1]){
                pos[i]++;
            }
            if(base[i]*ans[pos[i]] < min){
                min = base[i]*ans[pos[i]];
                minPos = i;
            }
        }

        ans[cnt++] = min;
        ++pos[minPos];
    }
    printf("%lld\n", ans[cnt-1]);
}

int main(){
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%d", &base[i]);
    }
    solve();
    return 0;
}


  • A Game

题意:两个人玩一个取牌的游戏, 一堆牌排成一列,每张牌都有一个值, 现在两个人每次可以从两头中的任意一头抽一张牌, 并且累加上面的值。 两个人都用最优策略, 求先手能够累积都最大值。

分析: 经典dp问题。 对于当前人来说, 决策的依据在于:取完某一头的牌(牌面指为a), 剩下的局面让对手取走最优的情况之后, 可以可以取得剩下局面里面的牌面值为b, 其中a+b要最大 采用了记忆化的写法, 预处理一下sum

#include<cstdio>
#include<cstring>
#define maxab(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
const int N = 201;
int a[N];
int dp[N][N], sum[N][N];

int solve(int s, int e){
    if(dp[s][e] != -1) return dp[s][e];
    if(s == e) return a[s];

    dp[s+1][e] = solve(s+1, e);
    dp[s][e-1] = solve(s, e-1);
    int s1 = a[s] + sum[s+1][e] - dp[s+1][e];
    int s2 = a[e] + sum[s][e-1] - dp[s][e-1];
    if(s1 > s2) return s1;
    return s2;
}

int main(){
    freopen("game1.in", "r", stdin);
    freopen("game1.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
        sum[i][i] = a[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            sum[i][j] = sum[i][j-1] + a[j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int ans = solve(0, n-1);
    printf("%d %d\n", ans, sum[0][n-1] - ans);
    return 0;
}


相似文章


最近发表的文章

全部文章

评论区

comments powered by Disqus 回到顶部