2020 Multi-University Training Contest 2

本文总阅读量次

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}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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啊

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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$ 进行转移

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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();
}