首页 > 其他分享 >盖世计划--北京营--0731--C班模拟

盖世计划--北京营--0731--C班模拟

时间:2024-11-09 15:58:28浏览次数:1  
标签:0731 -- sum long int 盖世 ll 数位

A. 数位和(digit)

题意:

设 \(f(x)\) 为 \(x\) 的数字和。例如 \(f(158)=1+5+8=14\)。

给定一个长度为 \(N\) 的正整数序列 \(A\),求 \(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i+A_j)\)。

分析:

首先明确 \(f(x)\) 为 \(x\) 的数位和

举例情况:

若有两个数分别为:\(12,21\)。

\[f(12+21)=f(12)+f(21)=3 \]

可以发现两个数相加的数位和可以转化为第一个数的数位和第二个数数位和相加。

但总有特殊情况如:

这两个数分别为:\(53,27\)。

\[f(53+27)=f(80)=8 \]

\[f(53)+f(27)=8+9=17 \]

可以发现这两个数的数位相加时在个位上进了一位,就不符合上面的情况了,那该怎么办呢?

仔细思考进位数位和的贡献是什么?

相当于此位变为 \(0\) 和更高的一位 \(+1\),则是对总答案相当于贡献了 \(-9\)。

那么我们就明确了计算的过程

设 \(g(a,b)\) 表示 \(a+b\) 进位个数

\[f(a+b)=f(a)+f(b)-9\times g(a,b) \\ f(a)+f(b)=\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i)+f(A_j)=2N \times \sum_{i=1}^{N}f(A_i) \\ 9\times g(a,b)=9 \times \sum_{i=1}^{N}\sum_{j=1}^{N}g(A_i,A_j) \]

第二个式子为什么是 \(2n\) 呢?因为它作 \(a_i\) 时加了 \(n\) 次,它作 \(a_j\) 时被加了 \(n\) 次。

那怎么求 \(g(a,b)\) 呢?

对于两个数 \(a,b\),如果 \(a+b\) 在第 \(x\) 位上发生了进位,那么有 \(a+b\ge10^x\)。

那么我们就可以枚举 \(x\),按照每个前 \(x\) 位的数的大小排序,再枚举 \(j\),二分找到第一个 \(a_j+a_k\ge10^i\) 的数的下标 \(k\),\(k\) 后面的数就全是可以进位的,然后就可以 \((n-k+1)\) 求出 \(g(a,b)\) 的个数了。

时间复杂度为 \(O(n\log{n})\)。

下面见代码(有注释不要担心):

注:十年OI一场空,不开long long 见祖宗

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll x;
ll a[20][200005];//a[前几位的数][第几个数] 
ll ans=0;
ll p(ll x){//计算数位和 
	ll sum=0;	
	while(x){
		sum+=x%10;
		x/=10;
	}
	return sum;
}

int main() {
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		ans+=2*n*p(x);//先不考虑进位,单纯地都加上 
		ll mod=10;
		for(int y=1;y<=15;y++){
			a[y][i]=x%mod;//前i的数为记录起来 
			mod*=10;
		}
	}	
	ll w=1;
	for(int i=1;i<=15;i++){//枚举前i位 
		w*=10;
		sort(a[i]+1,a[i]+1+n);//对前i位的数的大小进行排序 
		for(int j=1;j<=n;j++){//对每个数进行排序 
		
			//统计加上a[i][j]后大于等于10^i的个数 
			ll k=n+1-(lower_bound(a[i]+1,a[i]+1+n,w-a[i][j])-a[i]);
			ans-=9*k;//减去进位减少的贡献 
		}
	}
	
	cout<<ans; 
	
    return 0;
}

B. T2--集合变换(trans)

暴力搜索,但要剪枝,考虑如果我们搜到了 \(1\) 就没有必要向下递归了,这样就成了没有只有一个儿子的节点,能省下很大时间,如果 \(k/ge m\) 说明我们 \(m\) 耗尽也只能搜到 \(1\),直接剪掉。

我们对初始值分解质因数,我的因数的因数也只能是我们因数,所以我们只要分解一次即可。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=5e5+10;
const int mod=1e9+7;
using namespace std;

int x,k,m;
int d[N],top;
int cnt;
int ans;

void dfs(int z,int x){
	if(z==k||x==1){
		cnt++;
		ans+=x;
		if(cnt>=m){
			exit(0);
		}
		return;
	}
	
	for(int i=1;i<=top&&d[i]<=x;i++){
		if(x%d[i]==0){
			dfs(z+1,d[i]);
		}
	}
} 

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	
	cin>>x>>k>>m;
	
	if(k>=m){
		cout<<m;
		return 0;
	}
	
	for(int i=1;i*i<=x;i++){
		if(x%i==0){
			d[++top]=i;
			if(i*i!=x){
				d[++top]=x/i;	
			}
		}
	}
	sort(d+1,d+top+1);
	dfs(0,x);
	cout<<ans;	
	return 0;
}

标签:0731,--,sum,long,int,盖世,ll,数位
From: https://www.cnblogs.com/sadlin/p/18536886

相关文章

  • 批量计算遥感影像NDVI:Python代码
      本文介绍基于Python中的gdal模块,批量基于大量多波段遥感影像文件,计算其每1景图像各自的NDVI数值,并将多景结果依次保存为栅格文件的方法。  如下图所示,现在有大量.tif格式的遥感影像文件,其中均含有红光波段与近红外波段(此外也可以含有其他光谱波段,有没有都不影响);我们希望,批......
  • VMware vCenter Server 6.7U3w 下载
    VMwarevCenterServer6.7U3w(安全更新)-ESXi集中管理软件集中式控制vSphere环境请访问原文链接:https://sysin.org/blog/vmware-vcenter-6/查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgVMwarevCenterServer是一款高级服务器管理软件,提供了一个集中式平......
  • AMC2024 12A 题目笔记
    题目编号按照AoPS。√√√√√√√××√.×√√√√.√√√.....P6对啦!首先注意到答案应该是一个正的加两个负的。暴力枚举所有合法的三元组,算得\(10-6-1=\boxed{\mathbf{(B)}\3}\)。☆经验:枚举一个数\(n\)的分解\(x\timesy\timesz\)是可以接受的。A......
  • CodeforceTon Round 4 div1 + div2 题解
    题解A-EDreamissofar~A.BeautifulSequence检查每一位对应的数字是否小于等于位置,如果可以说明这个数字可以移动到对应位置上,遍历即可#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidsolve(){ intn; cin>>n; vector<int>a......
  • VMware ESXi 6.7 U3u (ESXi670-202403001) 下载
    VMwareESXi6.7U3u(ESXi670-202403001)下载VMwareESXi6ExtendSupportRelease请访问原文链接:https://sysin.org/blog/vmware-esxi-6/查看最新版。原创作品,转载请保留出处。作者主页:sysin.org产品简介VMwareESXi:专门构建的裸机Hypervisor了解可直接安装到您的物......
  • 六、MyBatis-Plus高级用法(1):最优化持久层开发
    一、MyBatis-Plus快速入门1.1简介课程版本:3.5.3.1MyBatis-Plus......
  • 被复线远传节点机JR-IPAM-1600
    产品描述JR-IPAM-1600J是一款被复线远传节点机,通过传统双绞线电缆(被复线\网线\对数电缆\矿用电缆等),用户就可以快速组成一个高速的传输网、局域网。它具有传输速率高、运行稳定、快速安装部署的特点,设备特有的AUTO工作模式,能够自动侦测线路和远端设备情况,自动调整到最佳性能。......
  • 【黑马python:函数进阶】81-84
    目录一、函数的多个返回值二、函数的多种传参方式1.函数参数种类1.1位置参数与关键字参数1.2缺省参数1.3不定长参数三、函数作为参数传递四、匿名函数一、函数的多个返回值如果一个函数要有多个返回值,该如何书写代码?按照返回值的顺序,写对应顺序的多个变量接......
  • python+flask计算机毕业设计个人碳足迹系统的设计与实现(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、选题背景关于碳足迹的研究,现有研究多集中在宏观层面的碳排放总量分析以及企业层面的碳足迹管理等方面。例如,许多研究聚焦于国家或大型企业的碳......
  • python+flask计算机毕业设计好骑行打卡园app系统(程序+开题+论文)
    文件加密系统的设计与实现tp835本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容好骑行打卡园app系统毕业设计相关内容说明一、选题背景随着骑行运动在全球范围内的日益流行,与之相关的数字化服务......