首页 > 其他分享 >C. Mad MAD Sum(cf960)

C. Mad MAD Sum(cf960)

时间:2024-07-22 23:27:56浏览次数:17  
标签:ai Sum cf960 int Mad 数组 sum ll MAD

题意:定义MAD为数组中至少出现两次的最大数字,如果没有就是0.给定一个长度为n的数组a,sum=0,下面的过程将依次循环执行,直到a中的所有数字都变成0:

设置sum+=∑ai;设bi=MAD(a1,a2..ai),ai=bi

求过程结束后sum的值。

分析:经历操作一次后的数组是非递减的,以后每次都是将数组向右移动,为了防止数组从左往右,不含0的第一个数字在数组里只出现1此,我们可以再执行一次操作,所以只要执行两次操作就能知道剩下的操作次数。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
bool c[N];
ll n,a[N];
void g(){
	for(ll i=1;i<=n;i++)c[i]=false;
	ll ma=0;
	for(ll i=1;i<=n;i++){
		if(c[a[i]])ma=max(ma,a[i]);
		c[a[i]]=true;
		a[i]=ma;
	}
}
void sol(){
    cin>>n;
	ll ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans+=a[i];
	}
	g();
	for(ll i=1;i<=n;i++)ans+=a[i];
	g();
	for(ll i=1;i<=n;i++){
		ans+=(n-i+1)*a[i];
	}
	cout<<ans<<endl;
}
int main(){
	int t;cin>>t;
	while(t--)sol();
	return 0;
}

标签:ai,Sum,cf960,int,Mad,数组,sum,ll,MAD
From: https://blog.csdn.net/m0_74310050/article/details/140590655

相关文章

  • SMU Summer 2024 Contest Round 6
    AManyFormulas思路:二进制枚举voidsolve(){strings;cin>>s;intn=s.size();intm=pow(2,n-1);intans=0;for(inti=0;i<m;++i){intnow=0,sum=0;for(intj=0;j<n;++j){......
  • 计算机网络中的检验和(checksum)(包括计算文件的检验和附有c++代码)
    介绍:检验和(checksum),在数据处理和数据通信领域中,用于校验目的地一组数据项的和。它通常是以十六进制为数制表示的形式。如果校验和的数值超过十六进制的FF,也就是255.就要求其补码作为校验和。通常用来在通信中,尤其是远距离通信中保证数据的完整性和准确性。(此引用了检验和的百......
  • Python学习计划——2.3常用内置函数(len, max, min, sum, etc.)
    Python提供了许多内置函数,用于简化对数据结构的操作。以下是一些常用的内置函数及其详细说明。1.len()len()函数用于返回对象(如列表、元组、字符串、字典等)的长度(元素个数)。示例:#列表fruits=["apple","banana","cherry"]print(len(fruits))#输出:3#元组c......
  • Array Sum up increment. 1526, 3229
    1526.MinimumNumberofIncrementsonSubarraystoFormaTargetArrayYouaregivenanintegerarray target.Youhaveanintegerarray initial ofthesamesizeas target withallelementsinitiallyzeros.Inoneoperationyoucanchoose any subarray......
  • Mad MAD Sum(Round 960)
    #include<bits/stdc++.h>#defineintll#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdin......
  • C. Least Prefix Sum
    链接https://codeforces.com/problemset/problem/1779/C题目思路1-m的前缀和最小。那么显然知道[1,m-1]的前缀和更大,所以a[m]<0,同理a[m-1]+a[m]<0,...,a[2]+...+a[m]<0。采用大根堆优先队列管理其中的值,如果上面的任何一个大于零,弹出优先队列的top,减掉两倍的top,让他重新变成......
  • [CCPC2022 广东] XOR Sum
    数位dp看到这样求和价值的计算,考虑可不可以交换求和符号或者改变计算方式。这题中的位运算使我们考虑按位计算贡献,价值可以写成:\[f(A)=\sum_{i=0}2^i\timesc_i\times(k-c_i)\]其中\(c_i\)表示第\(i\)位上为\(1\)的\(a_i\)数量。题目第二个要求即\(f(A)=n\)。考......
  • A. Sum of Three
    原题链接题解要让abc不同,我们可以先固定ab取两个较小值,然后看看最大的c有没有重复code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;voidsolve(){intn;cin>>n;if(n<7){cout<<"NO\n";return;}......
  • 在 MacOS 上使用 chromadb 添加文档时出现 ONNXRuntimeError
    我正在尝试使用Chromadb运行Python脚本。创建集合,添加一些向量并得到。但出现错误。脚本:importchromadbclient=chromadb.Client()collection=client.create_collection(name="example")collection.add(documents=["Skyisunlimited.","Treeisaplant......
  • SMU Summer 2024 Contest Round 5
    SMUSummer2024ContestRound5RobotTakahashi思路按照Wi......