2020牛客暑期多校训练营（第六场）

wenzhuan

发布于 2022-08-15 12:40:58

2760

发布于 2022-08-15 12:40:58

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

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

B-Binary Vector

思路

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

需要降到 O(n)

代码

#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 种颜色，需要给每条边上色。需要满足：

所有颜色出现次数相同
没有单色环
没有单色边

给出一种合法情况

思路

首先特判，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 开始搜防止出现负数非法访问。直接枚举转移。

代码

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

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

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

binary