牛客算法周周练8
A,小A买彩票
题意
小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。 0≤n≤30输入描述
一行一个整数N，为小A购买的彩票数量
输出描述
输出一个最简分数a/b，表示小A不亏本的概率。
若概率为1，则输出1/1，概率为0，则输出0/1。
解析
首先他要能不亏本，那么买一张的时候要买到3或者4，两张的时候要总和超过6，可以是33，34，43，44，24，42，这么多种情况，所以我们就不仅仅是考虑每一张都超过3，如果出现了一张1，来两张4就好了，所以我们考虑使用dp，来递推最多的可能性，之前都没有写过博客来讲一下dp，主要也是梳理一下自己对dp的认识关于dp
我对dp的认识主要是像背包问题这种，这个物体放进去还是不放.就像我现在背包已经装满了，装了i个物体，总质量为j，现在我要考虑是否要装第i+1个物体，如果没装满并且能装下，自然是直接装进去更好，那么如果装满了呢
我们用dp数组保存了每一种情况的最优解，也就是说假设我现在有2个物体a,b，a质量为1,价格为1，b质量为2，价格为2
我们先不管背包能装多少，首先可以得到dp[0][0]=0,也就是背包为空的时候,现在我们往后推我们dp数组为dp[1][1]也就是说之装一个物品，质量为1的时候显然只装一个a是最优解，然后我们递推，dp[1][2],也就是我们现在可以装的质量为2，还是只能装一个物体，如果我们不装物品b，那么dp[1][2]=dp[1][1]等于1，如果我们装物品2，那么我们就要在背包里腾出空间，拿出一个物品，然后装下物品2，dp[1][2]=dp[0][0]+2，这里就可以看到明显腾出空间再放入b更优，这样子一直往后推，当推到质量为我们所求的最大值的时候，得到的就一定是我们要的最优解。
好，梳理完了，我们来看现在这一题，我现在买了n张彩票，我现在要不亏本，那么我们最少就要中奖的总额达到3n，那么我们只要像前面一样，dp过去，然后在最后得到dp数组之和，将dp[n][3n]到dp[n][4*n]全部加起来就好了。
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[32][150];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int main(void){
ios::sync_with_stdio(false);
memset(dp,0,sizeof(dp));
int n;
cin>>n;
dp[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=n*4;++j){
if(j>=1)
dp[i][j]+=dp[i-1][j-1];
if(j>=2)
dp[i][j]+=dp[i-1][j-2];
if(j>=3)
dp[i][j]+=dp[i-1][j-3];
if(j>=4)
dp[i][j]+=dp[i-1][j-4];
}
}
ll a=0;
for(int i=3*n;i<=121;++i){ //3*n为成本
a+=dp[n][i];
}
ll b=pow(4,n);
ll c=a/gcd(a,b);
ll d=b/gcd(a,b);
cout<<c<<"/"<<d<<endl;
return 0;
}
B，[金]点石成金
题意
赛时提示：魔法值和财富值初始为0
帕秋莉掌握了一种金属性魔法
她决定去捡一些石头，施展点石成金魔法
帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金
对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（需要说明的是，就算魔法值不够，也可以操作，操作后魔法值归零）
否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少）
帕秋莉想知道，按照1-n的顺序以此操作每块石头，如何决策，可以使自己最后的收益值最大
只需要输出最大收益
收益值=财富值*魔法值
（提示：数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0）
输入描述
第一行一个整数n
接下来n行，每行四个数，分别代表对应石头的a,b,c,d值
输出描述
一个整数表示答案
这个题目我都不想写。。。。。。直接暴力dfs，处理一点细节就可以直接冲！！！
上图水文章
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
typedef long long ll;
ll a[N], b[N], c[N], d[N];
int n;
ll dfs(int number, ll money, ll mofa){
if(number == n + 1){
return money * mofa;
}
ll temp = mofa - b[number];
ll res = dfs(number + 1, money + a[number], temp < 0 ? 0 : temp);
temp = money - d[number];
res = max(res, dfs(number + 1, temp < 0 ? 0 : temp, mofa + c[number]));
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
}
ll res = dfs(1, 0, 0);
printf("%lld\n", res);
return 0;
}C.小阳的贝壳
题意
小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为 $col_i$。现在小阳有 3 种操作：1 l r x：给 [l,r][l,r] 区间里所有贝壳的颜色值加上 xx 。
2 l r：询问 [l,r][l,r] 区间里所有相邻贝壳 颜色值的差（取绝对值） 的最大值（若 l = rl=r 输出 0）。
3 l r ：询问 [l,r][l,r] 区间里所有贝壳颜色值的最大公约数。
输入描述
第一行输入两个正整数 n,mn,m，分别表示贝壳个数和操作个数。
第二行输入 n个数，表示每个贝壳的初始颜色。
第三到第 m + 2 行，每行第一个数为 opt，表示操作编号。接下来的输入的变量与操作编号对应。
输出描述
共 m 行，对于每个询问（操作 2 和操作 3）输出对应的结果。
解析
线段树，俺不会隔壁大佬的代码大佬的博客代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
int w,g,s;
}t[N<<2];
int a[N];
inline int my_max(int x,int y){//绝对值最值
return abs(x)>abs(y)?x:y;
}
inline void build(int now,int l,int r){
if(l==r){
t[now].w=t[now].g=t[now].s=(a[l]);
return;
}
int mid=(l+r)>>1;
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
t[now].w=my_max(t[now<<1].w,t[now<<1|1].w);
t[now].g=__gcd(t[now<<1].g,t[now<<1|1].g);
t[now].s=t[now<<1].s+t[now<<1|1].s;
}
inline void insert(int now,int l,int r,int x,int y){
if(l==r){
t[now].w=t[now].g=t[now].s=(t[now].w+y);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
insert(now<<1,l,mid,x,y);
}else{
insert(now<<1|1,mid+1,r,x,y);
}
t[now].w=my_max(t[now<<1].w,t[now<<1|1].w);
t[now].g=__gcd(t[now<<1].g,t[now<<1|1].g);
t[now].s=t[now<<1].s+t[now<<1|1].s;
}
inline int find1(int now,int l,int r,int lc,int rc){//区间绝对值最值
if(lc<=l&&r<=rc){
return t[now].w;
}
int mid=(l+r)>>1,res=0;
if(lc<=mid){
res=my_max(res,find1(now<<1,l,mid,lc,rc));
}
if(rc>mid){
res=my_max(res,find1(now<<1|1,mid+1,r,lc,rc));
}
return res;
}
inline int find2(int now,int l,int r,int lc,int rc){//区间gcd
if(lc<=l&&r<=rc){
return t[now].g;
}
int mid=(l+r)>>1,res=0;
if(lc<=mid){
res=__gcd(res,find2(now<<1,l,mid,lc,rc));
}
if(rc>mid){
res=__gcd(res,find2(now<<1|1,mid+1,r,lc,rc));
}
return res;
}
inline int find3(int now,int l,int r,int lc,int rc){//区间和
if(lc<=l&&r<=rc){
return t[now].s;
}
int mid=(l+r)>>1,res=0;
if(lc<=mid){
res=(res+find3(now<<1,l,mid,lc,rc));
}
if(rc>mid){
res=(res+find3(now<<1|1,mid+1,r,lc,rc));
}
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=n;i;--i){
a[i]-=a[i-1];
}
build(1,1,n);
while(m--){
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
if(opt==1){
int x;
scanf("%d",&x);
insert(1,1,n,l,x);
if(r<n){
insert(1,1,n,r+1,-x);
}
}else if(opt==2){
if(l==r){
puts("0");
continue;
}
printf("%d\n",abs(find1(1,1,n,l+1,r)));
}else{
if(l==r){
printf("%d\n",find3(1,1,n,1,l));
}else{
printf("%d\n",abs(__gcd(find3(1,1,n,1,l),find2(1,1,n,l+1,r))));
}
}
}
return 0;
}D.Forsaken喜欢字符串
待补E.Board
题意
恬恬有一个nx n的数组。她在用这个数组玩游戏：
开始时，数组中每一个元素都是0。
恬恬会做某些操作。在一次操作中，她可以将某一行的所有元素同时加上一个值，也可以将某一列的所有元素同时加上一个值。
在几次操作后，一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗？
输入描述
第一行一个整数n（1≤ n≤ 1000）。
接下来n行每行n个整数表示数组a。
第(i+1)行的第j个元素表示aij（aij=-1或0≤ aij ≤ 10000）。-1表示隐藏的元素。
输出描述
仅一个整数表示答案。
解析
这个题目就是每次我可以个一行或者一列都加上一，然后我现在隐藏了一个点的值，让你根据别的点的值来求出这个点，主要是考察思维，我上图理解一下就好了
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=1005;
int s[MAXN][MAXN];
int main(void){
ios::sync_with_stdio(false);
int n;
cin>>n;
int a,b;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin>>s[i][j];
if(s[i][j]==-1)
a=i,b=j;
}
}
int ans=0;
if(a==0||b==0)cout<<s[a][n-1]+s[n-1][b]-s[n-1][n-1];
else cout<<s[a][0]+s[0][b]-s[0][0];
return 0;
}完结撒花，又写（水）完了一篇长博客
基恩士成长空间 419人发布
