题目传送门：https://ac.nowcoder.com/acm/contest/6290
A.数列下标（签到）
题目大意：
【牛客算法周周练15——A、B】
文章图片
解题思路：
纯模拟，从这个数开始向后遍历，找到第一个比它大的数，记录下标。给数组b初始化为0的话如果找不到比它更大的数直接就是0，不用额外处理。
AC代码：
#include
#define ll long long
using namespace std;
int main()
{
ll n=0;
ll a[10005]={0},b[10005]={0};
cin>>n;
for(int i=1;
i<=n;
i++)
scanf("%lld",&a[i]);
for(int i=1;
i<=n;
i++)
{
for(int j=i;
j<=n;
j++)
{
if(a[i] B.可持久化动态图上树状数组维护01背包(思维) 题目大意：
文章图片
解题思路：
思路很简单，就是一个纯思维，如果这个数是个负数，那么它再往前移动只会使这个数增大，所以如果这个位置上的是个负数，就直接删除负数。如果不是的话就删除第一个数字。这样能保证代价最小。
因为所有的负数都已经删除了，所以无论剩下的数字权值
在这里插入代码片使多少，都是在位置1的时候代价最小，所以就从位置1开始删，这样能保证所有删除的数字都在位置1上（删完会自动补上）。AC代码：
#include
#define ll long long
using namespace std;
int main()
{
ll n=0;
ll x;
cin>>n;
ll ans=0;
for(int i=1;
i<=n;
i++)
{
scanf("%lld",&x);
if(x<0)
ans+=i*x;
else
ans+=x;
}
printf("%lld\n",ans);
return 0;
}
推荐阅读
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- Codeforces Round #609 (Div. 2)——C. Long Beautiful Integer（思维）
- FZU - 2107题解
- ACM OJ 2036 多边形面积计算
- #|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化
- ACM|回文树（自动机）（练习和总结）
- acm|扩展欧几里德算法(附证明)
- ACM|[dsu] codeforces 375D. Tree and Queries
- ACM|codeforces 732-D. Exams （二分）