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();
}