当前位置:网站首页>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;
}
边栏推荐
- 逻辑漏洞----权限类漏洞
- 腾讯称电竞人才缺口200万;华为鸿蒙3.0正式发布;乐视推行每周工作4天半?...丨黑马头条...
- 创意loadingjs特效小点跳跃动画
- 一文读懂Elephant Swap,为何为ePLATO带来如此高的溢价?
- for循环的3个表达式执行顺序
- 20220729 证券、金融
- R语言向前或者向后移动时间序列数据(自定义滞后或者超前的期数):使用dplyr包中的lag函数将时间序列数据向后移动一天(设置参数n为负值)
- el-table中el-table-column下的操作切换class样式
- AT4108 [ARC094D] Normalization
- 忆联:激活数据要素价值潜能,释放SAS SSD创新红利
猜你喜欢
程序员修炼之道:务以己任,实则明心——通向务实的最高境界
高性能数据访问中间件 OBProxy(三):问题排查和服务运维
自从外包干了四年,基本废了...
域名抢注“卷”到了表情包?ENS逆势上涨的新推力
jsArray array copy method performance test 2207292307
第十五天笔记
一本通循环结构的程序设计第一章题解(1)
05 | login background: based on the password login mode (below)
Self-tuning PID self-tuning control 】 【
腾讯称电竞人才缺口200万;华为鸿蒙3.0正式发布;乐视推行每周工作4天半?...丨黑马头条...
随机推荐
Eleven BUUCTF questions (06)
干货分享:小技巧大用处之Bean管理类工厂多种实现方式
重保特辑|拦截99%恶意流量,揭秘WAF攻防演练最佳实践
Markdown 1 - 图文音视频等
leetcode207.课程表(判断有向图是否有环)
人社部公布“数据库运行管理员”成新职业,OceanBase参与制定职业标准
odoo--qweb模板介绍(一)
BUUCTF刷题十一道(06)
创意loadingjs特效小点跳跃动画
域名抢注“卷”到了表情包?ENS逆势上涨的新推力
Greenplum 6.0有哪些不可错过的硬核升级与应用?
How to solve the problem that the page does not display the channel configuration after the EasyNVR is updated to (V5.3.0)?
【微信小程序】一文带你搞懂小程序的页面配置和网络数据请求
判断链表是否有环
jsArray array copy method performance test 2207292307
Analysis of AI recognition technology and application scenarios of TSINGSEE intelligent video analysis gateway
学习笔记——七周成为数据分析师《第一周:数据分析思维》
EasyNVS cloud management platform function reconstruction: support for adding users, modifying information, etc.
SyntaxError: EOL while scanning string literal
【软考软件评测师】自动化测试章节下篇