2022牛客寒假算法基础集训营(一)全部题解
A 九小时九个人九扇门 dp
题意:
一个数字的数字根是指:将该数字各数位上的数字相加得到一个新的数,直到得到的数字小于 $10$ 为止.。设置小于 $10$ 的数字,其数字根就为其本身。
$k$ 个人能够打开门上数字为d的一扇数字门,当且仅当这 $k$ 个人的腕表数字之和的数字根恰好为 $d$。
$(1<=n<=1e5,1<ai<=1e9)$
题解:
状态
$dp[i][j]$ 表示考虑了前 $i$ 个数,选择了一些数字使得数字根为 $j$ 的方案数
转移方程
不加当前位使得数字根为 $j$ 的方案数为上一位继承来
$dp[i][j] += dp[i - 1][j];$
加上当前位使得数字根为 $f(a[i]10+j)$ 的方案数为上一位继承来
$dp[i][f(a[i]10+j)] += dp[i - 1][j];$
当前位的方案数+1
$dp[i][f(a[i])]++;$
|
H 牛牛看云 思维
题意:
求
$n$ $n$
$Σ$ $Σ$ $∣ai+a j −1000∣$
$i$=1 $j$=$i$
$(0<ai<=1000, n<=1000000)$
题解:
因为这个 $n$ 很打,$ai$很小
就从 $ai$ 入手
记录 $ai$ 的个数枚举 $ai$
直接计算答案
假如$ai==aj$ ans=自己和自己+自己和别人 $/2$ (因为 $j$ 是从 $i$ 开始的 所以 $/2$
$ai!=aj$ ans=$cnt[ai]*cnt[aj]/2$
vector<int> g[N]; |
F 中位数切分 思维
题意:
给定一个长为 $n$ 的数组 $a$ 和一个整数 $m$,求最多可以划分成多少段,使得每一段的中位数都大于等于$m$。$(1<ai, m<=1e9, 1<=n<=1e5)$
题解:
原数组大于等于m的记为1,记录 $cnt1$ 个
小于的记为-1,记录 $cnt2$ 个
当一段的 $sum>=1$ 的时候这一段中位数就 $>=m$
然后就去拿 $1$ 的去中和 $-1$, 最大的段数就是先把负数中和了使得 $sum==0$ 再加上一个$1$,假如$cnt1-cnt2<=0$则不存在,不然段数为 $cnt1-cnt2$个 。
|
I B站与各唱各的 数学
题意:
题解:
打表呜呜呜
最小值是
下一个数是210
就发现是素数的乘积$2,23,23*5$
因为素数乘积的数不是素数,那么他的因子也少
那么$H(x)$就大
因为素数 $x$ 的欧拉函数等于 $x-1$,那么最大值就是范围内最大的素数的$H(x)=(x-1)/x$
$ps:$牛客题解上说 $1e9$ 以内最大的两个素数间隔是 $282$ 就直接暴力找
|
D 牛牛做数论 数学
题意:
有 $n$ 位人在翻唱一首共 $m$ 句的歌曲,人不交流。一句歌词被所有人唱或者没被人唱这句歌词无效,让成功唱出的句子数尽可能多,求期望唱成功的句子数量对1e9 +7取模的结果。
$(1<=t<=1e4,1<=n, m<=1e9,)$
题解:
$m$ 句歌词相互独立
设唱的概率为 $pi$ 不唱的概率为 $(1-pi)$
那么答案就是失败的概率就是$(p1p2p3…pn)$+$(1-p1)(1-p2)…(1-pn)$
那么成功的概率就是$1-(p1p2p3…pn)$+$(1-p1)(1-p2)…(1-pn)$
最大化成功就是最小化石板就要使得pi都为$1/2$ 其实是猜的不过可以验算几个
那么答案就等于$m(1-(1/2)^n2)$
|
B 炸鸡块君与FIFA22 倍增/分块/线段树【补】
题目链接
【补】
题意:
打游戏胜利将使得分加一、失败使分减一、平局使分不变。若你当前的排位分是 $3$ 的整倍数(包括0倍),则若下一局游戏失败,你的排位分将不变(而不是减一)
给定一个游戏结果字符串和若干次询问,你需要回答这些询问。
$(1<=l, r<=n,q<=2e5,0<=s<=1e9)$
题解:
$n,q$ 很大就想到要预处理
每次询问每段的答案发现只和首位的初始值%3的值有有关
那么预处理从每一位开始以初始值为 $0, 1, 2$开始向后进行操作,但是不能 $n*n$
所以就想到暴力分块
假如在同一个分块里就直接暴力模拟
不在的话
就在一整块和另一块以%3的值结果来转移
|
待补
K 冒险公社 dp【补】
题目链接
【补】
qwq
发现,第 $i$ 个预测和 $[1,i−3]$ 的所有岛都没有关系,明显符合 dp 的无后效性
$dp[i][i1][i2][i3]$表示已经走了 $i$ 座山绿岛的最大数量,$i1, i2, i3$表示$i,i-1, i-2$的颜色
$dp[i][i1][i2][i3]$是从合法状态的$dp[i−1][i2][i3][i4]$转移过来
using namespace std;
const int N=1e5+5;
int dp[N][5][5][5];
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
int n; cin>>n;
string s; cin>>s; s='.'+s;
for(int i=3; i<=n; i++) for(int j=0; j<3; j++)for(int k=0; k<3; k++) for(int l=0; l<3; l++) dp[i][j][k][l]=-1;
for(int j=0; j<3; j++)for(int k=0; k<3; k++) for(int l=0; l<3; l++) {
dp[2][j][k][l]=0;
//if(j==1) dp[2][j][k][l]++;
if(j==1) dp[2][j][k][l]++;
if(k==1) dp[2][j][k][l]++;
}
int ans=-1;
for(int i=3; i<=n; i++) {
for(int l=0; l<3; l++) {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
for(int l1=0; l1<3; l1++) {
if(dp[i-1][j][k][l1]==-1) continue;
int R=0, G=0;
R=(l==0)+(j==0)+(k==0);
G=(l==1)+(j==1)+(k==1);
//cout<<R<<" "<<G<<endl;
if(s[i]=='R'&&G<R) dp[i][l][j][k]=max(dp[i][l][j][k], dp[i-1][j][k][l1]+(l==1));
if(s[i]=='G'&&G>R) dp[i][l][j][k]=max(dp[i][l][j][k], dp[i-1][j][k][l1]+(l==1));
if(s[i]=='B'&&G==R) dp[i][l][j][k]=max(dp[i][l][j][k], dp[i-1][j][k][l1]+(l==1));
}
}
}
}
}
for(int i=0; i<3; i++)for(int j=0; j<3; j++) for(int k=0; k<3; k++)
ans=max(ans, dp[n][i][j][k]);
cout<<ans<<endl;
return 0;
}
G ACM is all you need 【待补】
总结
Qwq