2020牛客暑期多校训练营(第六场)

7.27 充分发挥嘴题技能的牛客6

B-Binary Vector

思路

面向样例合理猜测,猜递推公式是 $F(n)=F(n-1)*(2^n-1)/2^n$

需要降到 $O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
const int maxn = 2e7 + 5;
const int mod = 1e9 + 7;
int z[maxn],m[maxn],p[maxn],w[maxn],a[maxn];
int solve(){
int n; sc(n); return pf("%d\n",a[n]);
}
int main(){
p[1]=2; rep(i,2,maxn) p[i]=2ll*p[i-1]%mod;
w[1]=500000004; rep(i,2,maxn) w[i]=1ll*w[1]*w[i-1]%mod;
z[1]=1; rep(i,2,maxn) z[i]=1ll*z[i-1]*(p[i]-1+mod)%mod;
m[1]=500000004; rep(i,2,maxn) m[i]=1ll*m[i-1]*w[i]%mod;
rep(i,1,maxn) a[i]=1ll*z[i]*m[i]%mod;
rep(i,2,maxn) a[i]^=a[i-1];
int _; sc(_); while(_--) solve();
}

C-Combination of Physics and Maths

题意

给定一个 $n*m$ 大小的矩阵,任意选择行列组成子矩阵,使子矩阵和和最后一列之和的商最大

思路

最优解一定是分母尽量大,而分子尽量小。所以当选择某行作为最底行时,它以上的所有数字都应被选上,所以对每列做一下前缀和,然后再 $n^2$ 暴力求一下最大值就好

G-Grid Coloring

题意

给定一个 $n*n$ 的矩阵,有 $k$ 种颜色,需要给每条边上色。需要满足:

  1. 所有颜色出现次数相同
  2. 没有单色环
  3. 没有单色边

给出一种合法情况

思路

首先特判,$n=1$ 、$k=1$ 还有颜色不能均匀分配的显然不行。对于剩下的合法涂色数,将各边从 $1-2n(n+1)$ 进行编号(左到右上到下),然后按编号从 $1-k$ 循环涂色即可

备注

代码五分钟,特判一小时

H-Harmony Pairs

题意

给定 $N$ ,$N\leq 1e100$ 。问 $1-N$ 中有多少个 $(A, B)$ 对满足 $A$ 的数位和大于 $B$ 的数位和且 $A\leq B$ 。

思路

数位 $dp$ 。$dp[pos][d][la][lb]$ 中,$pos$ 表示第 $pos$ 位,$d$ 表示 $B-A$ ,$la$ 表示当前是否有 $A=B$ ,$lb$ 表示当前是否有 $B=N$ 。$d$ 开到 $2000$ 且从 $1000$ 开始搜防止出现负数非法访问。直接枚举转移。

代码

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
#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 mod = 1e9 + 7;
int a[105]; // 位数 一般题目最大1e18
ll dp[105][2005][2][2];
char s[105];
ll dfs(int pos,int d,int la,int lb){
if(pos==-1) return d>1000;
if(dp[pos][d][la][lb]!=-1) return dp[pos][d][la][lb];
ll ans=0; rep(i,0,la?a[pos]+1:10) rep(j,0,lb?i+1:10)
ans+=dfs(pos-1,d+j-i,la&&i==a[pos],lb&&j==i),ans%=mod;
return dp[pos][d][la][lb]=ans;
}
ll slove(){
mst(dp,-1);
// 多组数据只用最开始mst一次 因为保证边界就可以了
int pos=0,len=strlen(s);
dep(i,len-1,0) a[pos++]=s[i]-'0';
return dfs(pos-1,1000,1,1);
}
int solve(){
scs(s); return pf("%lld\n",slove());
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}