牛客算法周周练8
闲扯
A题当时在想排列组合,然后看了下过题数,这要是排列组合也太不科学了...
E题是2019宁夏区域赛现场赛的原题,好像是B题,数据都没变,原代码直接ac
D不会,看不懂,看懂了想扇死自己,一个纯暴力map............
C的写2的那种情况以为是直接写一个线段树,然后直接查改,然后没想到这东东是差分...然后3的那种情况没想到是差分做的,当时没理解2的那种情况的引导
B没啥说的,第一眼想这是dp,我去,这咋dp,哦,数据范围30,那没了,直接爆搜
A---小A买彩票
题意:小A买n张彩票,然后每张中的金额为1,2,3,4之一,然后每种等可能出现,也就是 ,每张彩票3元,问不亏本的概率是多少,然后输出其分数形式
题解: 这个就是答案,因为n比较小,所以可以直接pow()算次方
比如n=2的时候,存在 6种情况,然后每种出现的可能都是
,所以相加就是
然后我们可以写一个dp数组,来求解组合出同一种金额有多少种可能
然后把大于3*n的金额数的可能求和
#include<bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(false);
#define pb push_back
#define ll long long
#define mod 1e9+7
using namespace std;
ll dp[31][121]={0};//表示赚的数目
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
IOS
dp[0][0]=1;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=4*n;j++)
{
if(j-1>=0)
dp[i][j]+=dp[i-1][j-1];
if(j-2>=0)
dp[i][j]+=dp[i-1][j-2];
if(j-3>=0)
dp[i][j]+=dp[i-1][j-3];
if(j-4>=0)
dp[i][j]+=dp[i-1][j-4];
}
}
ll a=0;
for(int i=n*3;i<=121;i++)
a+=dp[n][i];
ll b=pow(4,n);
ll c=a/gcd(a,b);
ll d=b/gcd(a,b);
printf("%lld/%lld\n",c,d);
return 0;
}B---「金」点石成金
题意:给n个元素,每个元素有4个属性
(1)增加ai的财富，消耗bi的魔法
(2)回复ci的魔法，减少di的财富
然后:收益值=财富值*魔法值
另外:数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0
求最大收益值
题解:数据比较小,直接爆搜
每次判断是增加财富,还是增加魔法,再注意数值大小就行
#include<bits/stdc++.h>
#define MAX_INT ((unsigned)(-1)>>1)
#define MIN_INT (~MAX_INT)
#define pi 3.1415926535898
typedef long long ll;
#define inf 0x3f3f3f3f
#define infmax 0x3f3f3f3f3f3f3f3f
using namespace std;
ll read()
{
ll c=0;int flag=1;
char s;
while((s=getchar())>'9'||s<'0')if(s=='-')flag=-1;
c=s-'0';
while((s=getchar())<='9'&&s>='0') c=c*10+s-'0';
return c*flag;
}
ll a[20],b[20],c[20],d[20];
ll ans=0;
int n;
void dfs(int i,ll p,ll q)//第i块石头,p魔法，q财富
{
if(i==n+1){
ans=max(ans,p*q);
return;
}
//if(p>0){
if(p-b[i]<0)//选择增加a财富
dfs(i+1,0,q+a[i]);
else dfs(i+1,p-b[i],q+a[i]);
//}
if(q-d[i]<0)//增加c魔法
dfs(i+1,p+c[i],0);
else dfs(i+1,p+c[i],q-d[i]);
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
dfs(1,0,0);
cout<<ans;
return 0;
}
C---小阳的贝壳
题意:有n个数,然后m个操作
1 l r x：给 [l,r]区间里所有贝壳的颜色值加上 x 。
2 l r：询问[l,r]区间里所有相邻贝壳 颜色值的差（取绝对值） 的最大值（若 l = r输出 0）。
3 l r ：询问 [l,r][l,r] 区间里所有贝壳颜色值的最大公约数。
题解:
数学的能力有限解释不清
转一下别人的
#include<bits/stdc++.h>
#define ls rt << 1
#define rs ls | 1
using namespace std;
const int MAXN = 1e5 + 5;
int sum[MAXN * 4], max_[MAXN * 4]; // sum是求和数组， max_是最大值
int gc[MAXN * 4], p[MAXN]; // gc是最大公约数， p是差分数组
int n, m;
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
void push_up(int rt) { 操作
sum[rt] = sum[ls] + sum[rs];
max_[rt] = max(max_[ls], max_[rs]);
gc[rt] = gcd(gc[ls], gc[rs]);
}
void build(int rt, int l, int r) { // 建树
if (l == r) {
sum[rt] = p[l];
max_[rt] = gc[rt] = abs(p[l]); // 注意要加绝对值
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(rt);
}
void update(int rt, int X, int l, int r, int w) { // 更新操作
if (l == r) {
p[l] += w;
sum[rt] = p[l];
max_[rt] = gc[rt] = abs(p[l]); // 加绝对值
return;
}
int mid = (l + r) >> 1;
if (mid >= X) update(ls, X, l, mid, w);
else update(rs, X, mid + 1, r, w);
push_up(rt);
}
int sum_query(int rt, int L, int R, int l, int r) { // 区间求和
if (l >= L && r <= R) return sum[rt];
int mid = (l + r) >> 1, res = 0;
if (mid >= L) res += sum_query(ls, L, R, l, mid);
if (mid < R) res += sum_query(rs, L, R, mid + 1, r);
return res;
}
int max_query(int rt, int L, int R, int l, int r) { // 区间最大值
if (l >= L && r <= R) return max_[rt];
int mid = (l + r) >> 1, res = 0;
if (mid >= L) res = max(res, max_query(ls, L, R, l, mid));
if (mid < R) res = max(res, max_query(rs, L, R, mid + 1, r));
return res;
}
int gcd_query(int rt, int L, int R, int l, int r) { // 区间最大公约数
if (l >= L && r <= R) return gc[rt];
int mid = (l + r) >> 1, res = 0;
if (mid >= L) res = gcd(res, gcd_query(ls, L, R, l, mid));
if (mid < R) res = gcd(res, gcd_query(rs, L, R, mid + 1, r));
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
for (int i = n; i >= 1; i--) p[i] -= p[i - 1]; // 差分数组
build(1, 1, n);
while (m--) {
int L, R, W, op;
scanf("%d%d%d", &op, &L, &R);
if (op == 1) {
scanf("%d", &W);
update(1, L, 1, n, W); 更新L
if (R < n) update(1, R + 1, 1, n, -W); // 更新R + 1
}
else if (op == 2) {
if (L == R) { cout << 0 << endl; continue; }
cout << max_query(1, L + 1, R, 1, n) << endl;
}
else
cout << gcd(sum_query(1, 1, L, 1, n), gcd_query(1, L + 1, R, 1, n)) << endl;
}
}
D---Forsaken喜欢字符串
题意:佩服出题人能把题目写的这么复杂.......那个公式看懵了
输入n个长度为k的字符串,然后m次查询,输入x,len,每次查询第x个串种长度为len的子串,在其他串里出现的次数,最后再乘以len,再求出的答案不能包括第x个串的子串
题解:map,map,map
直接先把所有串的子串都求一下,然后统计每种子串的出现的数量
然后对于每次查询的时候,求一下当前串种长度为len的所有的子串,然后再用第x个串中的每种子串,在所有串中的总数减去在第x个串里出现的数量最后乘以len
#include<bits/stdc++.h>
#define ll long long
const int maxn=5e4+5;
using namespace std;
map<string,int>a,aa;
int main(){
int n,k,q;
string s[maxn];
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=k;j++)
for(int t=0;t<=k-j;t++) a[s[i].substr(t,j)]++;
}
cin>>q;
for(int i=1;i<=q;i++){
int x,l;
ll ans=0;
cin>>x>>l;
aa.clear();
for(int j=0;j<=k-l;j++)
aa[s[x].substr(j,l)]++;
for(int j=0;j<=k-l;j++)
ans+=a[s[x].substr(j,l)]-aa[s[x].substr(j,l)];
cout<<ans*l<<endl;
}
}
//code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43833751E---Board
题意:数组中每一个元素都是0,可以将某一行的所有元素同时加上一个值，也可以将某一列的所有元素同时加上一个值,在几次操作后，一个元素被隐藏了,隐藏的数是几?-1表示隐藏的元素
题解:她正着生成一个矩阵,那我们可以反着把这个矩阵还原为,除-1元素所在位置以外的矩阵其他元素为0,然后如果每次还原位置经过-1元素的位置,-1元素同样也减减,最后输出-1元素位置的结果*(-1)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+5;
int a[N][N];
int main()
{
int n;
int ti, tj;
cin>>n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin>>a[i][j];
if (a[i][j] == -1)
{
ti = i;
tj = j;
a[i][j] = 0;
}
}
}
int minn;
for (int i = 1; i <= n; i++)
{
minn = 9999999;
for (int j = 1; j <= n; j++)
{
if (i != ti || j != tj)
{
minn = min(minn, a[i][j]);
}
}
for (int j = 1; j <= n; j++)
{
a[i][j] -= minn;
}
}
for (int j = 1; j <= n; j++)
{
minn = 9999999;
for (int i = 1; i <= n; i++)
{
if (i != ti || j != tj)
minn = min(minn, a[i][j]);
}
for (int i = 1; i <= n; i++)
{
a[i][j] -= minn;
}
}
cout<<-a[ti][tj]<<endl;
return 0;
}
查看2道真题和解析
投递微众银行等公司7个岗位 >