2020 Multi-University Training Contest 2

wenzhuan

发布于 2022-08-15 12:24:45

2510

发布于 2022-08-15 12:24:45

文章被收录于专栏：你会烧尽还是结冰

7.23 状态极差的杭电2

1001-Total Eclipse

题意

给定一个 n 个点的图，每个点有一权值 b ，每次选择 k 个相互连通的点，使其中每个点权值减一，问最少需要多少操作可以使所有的点权值都为 0（每次选择的 k 必须最大）

思路

先将节点按权值从大到小排序，然后依次遍历点 id_i ，将之前遍历过且与 id_i 不在同一联通块内的点 v 与 id_i 合并，并将父亲设为 id_i ，每个点对答案的贡献为 b_i-b_{father_i}

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int a[maxn],b[maxn],f[maxn],fa[maxn];
int tot,vis[maxn],head[maxn];
int nex[maxn<<1],to[maxn<<1];
void add(int u,int v){
    nex[++tot]=head[u];
    head[u]=tot; to[tot]=v;
}
int find(int x){ 
    return f[x]==x?x:f[x]=find(f[x]);
}
int cmp(int x,int y){
    return b[x]>b[y];
}
int solve(){
    int n,m; sc(n); sc(m); ll ans(0);
    rep(i,1,n+1) a[i]=f[i]=i,sc(b[i]),vis[i]=fa[i]=0;
    sort(a+1,a+n+1,cmp); while(m--){
        int u,v; sc(u); sc(v);
        add(u,v); add(v,u);
    } rep(i,1,n+1){
        int ind=a[i]; vis[ind]++;
        for(int j=head[ind];~j;j=nex[j]){
            if(!vis[to[j]]) continue;
            int t=find(to[j]);
            if(t==ind) continue;
            f[t]=fa[t]=ind;
        }
    } rep(i,1,n+1) ans+=b[i]-b[fa[i]];
    rep(i,0,tot+1) head[i]=-1; tot=0;
    return pf("%lld\n",ans);
}
int main(){
    mst(head,-1); int _; sc(_); while(_--) solve();
}

1006-The Oculus

题意

每个数都有唯一的斐波那契表示，即 A=\sum_{i=1}^nb[i] * F_i ，b[i] 为 0 或 1 且相邻为不同为 1 。给定 A 、B 、C 的斐波那契表示，C=A * B ，但是 C 的斐波那契表示中有一个 1 被替换为了 0 ，求此位数

思路

考虑直接嗯搞。根据哈希思想，利用一个大质数/双模数就降低被卡的可能，改成大质数就过了（没过我就写双模去了）

坑点

C 是 2e6 的，别开小了

补充

自然溢出就能过的，只是我们最开始的单模不能过罢了

1010-Lead of Wisdom

题意

有 n 个装备 k 个类型，每个装备有 a 、b 、c 、d 四种属性，要求每种类型选一个且使得 Sum=(100+\sum a) * (100+\sum b) * (100+\sum c) * (100+\sum d)

思路

嗯搜我自己也不知道为啥正着搜就t啊

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
struct node{ int a,b,c,d; };
vector<node>vv[55];
int n,k; ll ans;
void dfs(int t,int A,int B,int C,int D){
    if(!t) return ans=max(ans,1ll*A*B*C*D),(void)0;
    int sz=vv[t].size(); if(!sz) return dfs(t-1,A,B,C,D);
    rep(i,0,sz) dfs(t-1,A+vv[t][i].a,B+vv[t][i].b,C+vv[t][i].c,D+vv[t][i].d);
}
int solve(){
    sc(n); sc(k); ans=0; 
    rep(i,1,n+1){
        int t,a,b,c,d; sc(t); 
        sc(a); sc(b); sc(c); sc(d);
        vv[t].push_back({a,b,c,d});
    } dfs(k,100,100,100,100);
    rep(i,1,k+1) vv[i].clear();
    return pf("%lld\n",ans);
}
int main(){
    int _; sc(_); while(_--) solve();
}

1012-String Distance

题意

给定 1e5 的串 S 和 20 的 T ，1e5 的询问，每次给定 l 和 r ，求 S_l 到 S_r 和 T 的 lcs 长度

思路

lcs 标配 dp ？预处理出对于每个 i 位第 j 个字符最先出现的位置（记为 pos[j][i]），利用 pos 进行转移

代码

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
char s[maxn],t[25]; int n,m;
int pos[26][maxn],dp[25][25];
int lcs(int l,int r){
    mst(dp,0x3f); dp[0][0]=l-1;
    rep(i,0,m) rep(j,0,i+1){
        dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
        if(dp[i][j]>=r) continue;
        dp[i+1][j+1]=min(dp[i+1][j+1],pos[t[i+1]-'a'][dp[i][j]+1]);
    } dep(i,m,1) rep(j,i,m+1) if(dp[j][i]<=r) return i;
    return 0;
}
void solve(){
    scs(s+1); n=strlen(s+1);
    scs(t+1); m=strlen(t+1);
    dep(i,n,1){
        if(i==n) rep(j,0,26) pos[j][n+1]=n+1;
        rep(j,0,26) pos[j][i]=pos[j][i+1];
        pos[s[i]-'a'][i]=i;
    }
    int q; sc(q); while(q--){
        int l,r; sc(l); sc(r);
        int sub=2*lcs(l,r);
        pf("%d\n",r-l+1+m-sub);
    }
}
int main(){
    int _; sc(_); while(_--) solve();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度