当前位置:网站首页>UPC2022暑期个人训练赛第19场(B,P)
UPC2022暑期个人训练赛第19场(B,P)
2022-07-30 13:19:00 【.Ashy.】
B: 数学 (math)
大意:
求 n(n<=1e12) 分解为连续整数和的方案数
思路:
非常巧妙的一道数学题
我们假设连续整数和的首项为 a a a ,一共有 n n n 项 ,和为 S S S
则一定满足
S = ( 首项 + 末项 ) ∗ n 2 S={(首项+末项)*n \over2} S=2(首项+末项)∗n
化简就是
2 ∗ S = ( 2 ∗ a + n − 1 ) ∗ n 2*S=(2*a+n-1)*n 2∗S=(2∗a+n−1)∗n
显然有两个未知数 a a a 和 n n n
如果我们枚举 a a a 和 n n n 一定会爆掉
1.分析 n n n 的范围:
n 是项数,当 a = 1 a=1 a=1时 n n n 最大 这时 2 ∗ S = ( n + 1 ) ∗ n 2*S=(n+1)*n 2∗S=(n+1)∗n
所以我们可以得到 n ∗ n < ( n + 1 ) ∗ n = 2 ∗ S n*n<(n+1)*n=2*S n∗n<(n+1)∗n=2∗S
所以 n < s q r t ( 2 ∗ S ) n<sqrt(2*S) n<sqrt(2∗S) n最大在 1.5e6 左右
2.分析 a a a 的范围:
而首项显然我们可以取到 a 2 a\over2 2a 所以枚举两个值显然不合适
最大为2e11
分析完复杂度后我们明显的可以看出要从 n n n下手,枚举所有的 n n n ,判断此时的首项是否合法即可
首项要是个正整数
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int NN = 1e6+10;
const int pp = 1e9+7;
typedef pair<int,int>PII;
ll n,ans;
int main()
{
cin>>n;
for(ll i=2;i<=sqrt(n*2);i++)
{
ll k=((n*2)-i*i+i)%(i*2);
if(k==0&&((n*2)-i*i+i)/(i*2)>0) ans++;
}
cout<<ans;
return 0;
}
问题 P: Count Interval
大意:
给出 N 个数,求满足下面式子的 l ,r 有多少组
∑ i = l r A i = k \displaystyle\sum_{i=l}^rA_i=k i=l∑rAi=k
思路
我们可以用前缀和优化一下,优化完了之后就是求满足 s u m [ r ] − s u m [ l − 1 ] = k sum[r]-sum[l-1]=k sum[r]−sum[l−1]=k的 l , r 有多少组
这个题就变成了典型的 A − B = k A-B=k A−B=k 问题;我们可以边存边计算,我们处理的每个数都是一个 A A A,贡献就是前面数里 B B B 的数量 也就是 A − K A-K A−K 的数量
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int NN = 1e6+10;
const int pp = 1e9+7;
typedef pair<int,int>PII;
ll sum[N];
ll n,k,t,ans;
map<ll,ll>mp;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>t;
sum[i]=sum[i-1]+t;
}
mp[0]=1;
for(int i=1;i<=n;i++)
{
ans+=mp[sum[i]-k];
mp[sum[i]]++;
// cout<<ans<<endl;
}
cout<<ans;
return 0;
}
边栏推荐
- 重保特辑|拦截99%恶意流量,揭秘WAF攻防演练最佳实践
- no matching host key type found. Their offer: ssh-rsa
- 【软考软件评测师】自动化测试章节下篇
- 正确处理页面控制器woopagecontroller.php,当提交表单时是否跳转正确的页面
- 湖仓一体电商项目(一):项目背景和架构介绍
- shell 编程规范与变量
- 434. 字符串中的单词数
- Decoding Redis' most overlooked high CPU and memory usage issues
- 阿里 P7 到底是怎样的水平?
- Raja Koduri澄清Arc GPU跳票传闻 AXG年底前新推四条产品线
猜你喜欢
随机推荐
IDEA 重复代码快速重构(抽取重复代码快捷键)
程序员修炼之道:务以己任,实则明心——通向务实的最高境界
如何判断自己是否适合IT行业?方法很简单
如何把Excel表格显示到邮件正文里?
学习笔记——七周成为数据分析师《第一周:数据分析思维》
CF1320E Treeland and Viruses
dolphinscheduler simple task definition and complex cross-node parameter transfer
人社部公布“数据库运行管理员”成新职业,OceanBase参与制定职业标准
【23考研】408代码题参考模板——链表
自动化测试的生命周期是什么?
Hu-cang integrated e-commerce project (1): project background and structure introduction
Logic Vulnerability----Permission Vulnerability
Apache Log4j2漏洞
R语言向前或者向后移动时间序列数据(自定义滞后或者超前的期数):使用dplyr包中的lag函数将时间序列数据向后移动一天(设置参数n为负值)
第42讲:Scala中泛型类、泛型函数、泛型在Spark中的广泛应用
干货分享:小技巧大用处之Bean管理类工厂多种实现方式
第十四天笔记
no matching host key type found. Their offer: ssh-rsa
一文读懂Elephant Swap,为何为ePLATO带来如此高的溢价?
datax开启hana支持以及dolphinscheduler开启datax任务









