2020 Multi-University Training Contest 3

7.28 勇于乱冲的杭电3

1004-Tokitsukaze and Multiple

题意

给定一个长度为 $n$ 的序列 $a$ ,可以两两间任意合并(合并为两数之和同时数组长度减一)。问最多能合并出多少个 $k$ 的倍数(可以不操作)。

思路

求模 $k$ 的前缀和,每次找前一个相同前缀和的位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
const int maxn = 1e6 + 5;
int sum[maxn],pos[maxn];
int solve(){
int n,a,q,cnt(0); sc(n); sc(q); rep(i,0,q) pos[i]=0;
int l=0; rep(i,1,n+1){
sc(a),sum[i]=sum[i-1]+a,sum[i]%=q;
if(!pos[sum[i]]&&sum[i]){ pos[sum[i]]=i; continue; }
if(!pos[sum[i]]&&!sum[i]&&!l){
l=i; cnt++; pos[sum[i]]=i; continue;
}
if(pos[sum[i]]<l){ pos[sum[i]]=i; continue; }
l=i; cnt++; pos[sum[i]]=i;
} return pf("%d\n",cnt);
}
int main(){
int _; sc(_); while(_--) solve();
}

1005-Little W and Contest

题意

给定能力为 $1$ 或 $2$ 的 $n$ 个人,从中选择 $3$ 个人组队,需要能力之和大于 $5$ 。一个队需要彼此不熟(也不能有共同的熟人)。输出初始方案数。之后有 $n-1$ 个询问,每次有两个人互相熟识,输出此时组队的所有方案数。

思路

初始状态就是 $cnt[1] * C ^ {2} _ {cnt[2]}+C ^ {3} _ {cnt[2]}$ 。每次询问减去这两个人($u$ 、$v$)所在的组所有的组队情况:

  • $u$ 组能力 $2$ 和 $v$ 组能力 $2$ 的人的组队
  • $u$ 组能力 $1$ 和 $v$ 组能力 $2$ 的人的组队
  • $u$ 组能力 $2$ 和 $v$ 组能力 $1$ 的人的组队

想要每次求出也很简单,只需要每个组记录能力为 $1$ 和 $2$ 的人数,每次并查集后将人数合并。

代码

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
48
49
#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;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int qpow(int a,int b,int mod){
int ans=1; while(b){
if(b&1) ans=1ll*ans*a%mod;
b>>=1; a=1ll*a*a%mod;
} return ans;
}
int jc[maxn],inv[maxn];
int C(int s,int x){
if(s>x) return 0;
return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod;
}
int vis[maxn],peo[2][maxn];
int find(int x){
return vis[x]==x?x:vis[x]=find(vis[x]);
}
int solve(){
int n,cnt[2]; sc(n); mst(cnt,0); mst(peo,0);
rep(i,1,n+1) sc(a[i]),a[i]&=1,cnt[a[i]]++,peo[a[i]][i]++,vis[i]=i;
int sum=1ll*cnt[1]*C(2,cnt[0])%mod+1ll*C(3,cnt[0]); if(sum>=mod) sum-=mod;
pf("%d\n",sum); rep(i,1,n){
int u,v; sc(u); sc(v); int c=find(u),d=find(v);
int tt=1ll*peo[0][c]*peo[0][d]%mod*(n-peo[0][c]-peo[1][c]-peo[0][d]-peo[1][d])%mod;
// u v 2 2
tt+=1ll*peo[1][c]*peo[0][d]%mod*(cnt[0]-peo[0][c]-peo[0][d])%mod; if(tt>=mod) tt-=mod;
tt+=1ll*peo[1][d]*peo[0][c]%mod*(cnt[0]-peo[0][c]-peo[0][d])%mod; if(tt>=mod) tt-=mod;
// u v 1 2 / 2 1
sum-=tt; if(sum<0) sum+=mod; pf("%d\n",sum);
vis[c]=d; rep(j,0,2) peo[j][d]+=peo[j][c];
// change
} return 0;
}
int main(){
jc[0]=inv[0]=1; rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod;
inv[maxn-1]=qpow(jc[maxn-1],mod-2,mod);
dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
int _; sc(_); while(_--) solve();
}

1006-X Number

题意

对于 $1\leq i\leq 9$,定义 $i$ 类型数为数位上 $i$ 出现次数严格多于其他数字。问 $l$ 到 $r$ 中有多少个 $d$ 类型数。

思路

数位 $dp$ 嗯搞。将数位上各数字数量情况传进去,用 $mx$ 记录最高位不为 $d$ 的数位数量。搜到最末时只需计算 $d$ 此时的数量是否大于 $mx$ 。

备注

如果单组开 $dp[20][20]$ 没啥问题,但多组就要清空反而更慢了。直接开 $dp[20][10][20]$ 可以直接用前面的。$sort$ 是为了去重( $map$ 里可以少存点东西),具体哪一位多少个是没有影响的,只需要记录相对数量。

代码

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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &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)
using namespace std;
typedef long long ll;
int a[20],cnt[10],d; // 位数 一般题目最大1e18
ll l,r; map<array<int,10>,ll> dp[20][10][20]; // 位数 数位 个数
ll dfs(int pos,int state,array<int,10> pre,int mx,int limit){
// pos位数 pre之前状态 与dp数组对应
// state各种情况包括前导零 具体看题目 limit前一位限制
rep(i,0,10) pre[i]=cnt[i];
sort(pre.begin(),pre.end()); // sort去重
if(pos==-1) return cnt[d]>mx; // 计数,具体看题目
if(!limit&&dp[pos][d][cnt[d]].count(pre)) return dp[pos][d][cnt[d]][pre];
int last=limit?a[pos]:9;
ll ans=0; rep(i,0,last+1){
if(!state||i) cnt[i]++;
ans+=dfs(pos-1,state&&!i,pre,i==d?mx:max(mx,cnt[i]),limit&&i==a[pos]);
if(!state||i) cnt[i]--; // cnt是全局的 到下一位就要减掉
}
if(!limit) dp[pos][d][cnt[d]][pre]=ans;
return ans;
}
ll slove(ll x){
int pos=0;
while(x){ a[pos++]=x%10; x/=10; }
array<int,10> tmp{0};
return dfs(pos-1,1,tmp,0,1);
}
int solve(){
scl(l),scl(r),sc(d); mst(cnt,0);
ll ans=slove(r)-slove(l-1);
return pf("%lld\n",ans);
}
int main(){
int _; sc(_); while(_--) solve();
}