链接:https://www.nowcoder.com/acm/contest/181/C
来源:牛客网
题目描述
小a有n个数,他想把他们划分为连续的权值相等的k段,但他不知道这是否可行。
每个数都必须被划分
这个问题对他来说太难了,于是他把这个问题丢给了你。
输入描述:
第一行为两个整数n,q,分别表示序列长度和询问个数。 第二行有n个数,表示序列中的每个数。 接下来的q行,每行包含一个数k,含义如题所示。
输出描述:
输出q行,每行对应一个数Yes或者No,分别表示可行/不可行
示例1
输入
5 3 2 1 3 -1 4 3 2 1
输出
Yes No Yes
备注:
对于的数据,
对于的数据,
对于的数据,
设ai表示数列中的第i个数,保证
保证数据完全随机
解题思路:
如果sum/k不能除尽的话则肯定不能划分;能除尽的话,p=sum/k,则前i(1~k)组的和为p,2p,3p,……kp(sum),用set存,再用find函数查找
ac代码:
#include <iostream>
#include <set>
#define ll long long int
using namespace std;
set<ll> st;
bool check(ll temp,ll sum)
{
ll p=temp;
while(1)
{
if(st.find(temp)==st.end())
return 0;
if(temp==sum)
return 1;
temp+=p;
}
}
int main()
{
ll n,q,sum=0,num,k,i;
scanf("%lld %lld",&n,&q);
for(i=0;i<n;i++)
{
scanf("%lld",&num);
sum+=num;
st.insert(sum);
}
for(i=0;i<q;i++)
{
scanf("%lld",&k);
if(sum%k!=0)
{
puts("No");
continue;
}
else
{
puts(check(sum/k,sum)?"Yes":"No");
}
}
return 0;
}