拼多多笔试
一二题哪位大佬给个思路
知道会爆零,但是这两个都感觉就差一点了
知道会爆零,但是这两个都感觉就差一点了
全部评论
第一题不用dp,因为要求最大值的情况下求最小操作数,而最大值必然为len/3,按mod3的余数分类讨论就好

#include <cstdio>
(31159)#include <iostream>
using namespace std;
int a[1000010];
long long deal(int begin,int end)
{
long long ans = 0;
for(int i=begin+1;i<=end-1;i++)
{
int left = i-begin+1;
int right = end - i;
long long tmp = ((left)*right+left-1)*a[i];
ans+=tmp;
ans%=10000007;
}
ans += (a[begin]+a[end])*(end-begin);
return ans;
}
int main() {
int n;
cin>>n;
long long ans=0;
int beg =1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i] == a[i-1])
{
ans += deal(beg,i-1);
ans = ans%10000007;
beg = i;
}
}
ans += deal(beg,n);
ans = ans%10000007;
cout<<ans;
}
// 64 位输出请用 printf("%lld")
A写DP但是只有64
B枚举右端点,一边维护以该右端点可行的区间和,一边更新答案即可
C枚举第一组,然后每次O(n) check该分组是否可行
D当时猜了个结论,掰下的两块巧克力,其中一块要么全拿走,要么直接扔掉,写了个O(n^4)的dp,就过了
代码在我写的题解里面,但是还是不知道为什么A出不来
第一题dp,第二题数组长度为n,1到n遍历,每次遍历表示从第i个数开始,求取第i个数到数组末尾的所有子数组和
第一题100第二题64太难了
第一题用前缀和处理了一下暴力过了
第一题dp,dp[i]表示以第i个字符结尾的字符串最小操作数
第二题先按相邻的值相等,将数据分组,然后求组内所有子数组和,最后把每组结果求和就行
后面两题没看,第二题没注意余10的7次方,写了一个多小时才a
只有第二题a了😭,用动态规划能做
拼多多几道题
相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享