跟老外做网站,广州seo技术培训,爱客crm登录,金泉网网站建设题干#xff1a;
小a有n个数#xff0c;他想把他们划分为连续的权值相等的k段#xff0c;但他不知道这是否可行。
每个数都必须被划分
这个问题对他来说太难了#xff0c;于是他把这个问题丢给了你。
输入描述:
第一行为两个整数n,q#xff0c;分别表示序列长度和询问…题干
小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个数保证
保证数据完全随机 解题报告 刚开始以为二分复杂度是正确的写了一个就AC了但是后来一想发现不对啊复杂度成了O(q^2logn)、、、大概是数据水了吧 而且我这种解法根本不适合有负数存在的情况、、因为sum数组就不单调了呀。
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int MAX 100000 5 ;
ll a[MAX];
ll sum[MAX];
int main()
{int n,q,k;cinnq;for(int i 1; in; i) scanf(%lld,ai),sum[i] sum[i-1] a[i];while(q--) {scanf(%d,k);if(sum[n] % k ! 0) {puts(No);continue;}int every sum[n] / k;int cur 0,flag 1;for(int i 1; ik; i) {int pos lower_bound(sum1,sumn1,cur every) - sum;if(sum[pos] ! curevery) {flag0;break;}cur every;}if(flag 1) puts(Yes);else puts(No);}// 2 3 6 5 9return 0 ;}
标程其实也差不多啦复杂度o(因子个数*N q) 其实就是打表算的对于这题其实打表比较合适因为q比n大且题干中说了数据保证随机所以最好是打表然后o(1)查询
#includecstdio
#includecstring
#includealgorithm
#define LL long long
using namespace std;
const int MAXN 2 * 1e6 10, INF 1e9 10;
inline int read() {char c getchar(); int x 0, f 1;while(c 0 || c 9) {if(c -) f -1; c getchar();}while(c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}
int a[MAXN];
bool ans[MAXN];
int main() {int N read(), Q read();LL sum 0;for(int i 1; i N; i) a[i] read(), sum a[i];for(int i 1; i N; i) {if(sum % i ! 0) {ans[i] 0; continue;}LL cur 0, k 0;for(int j 1; j N; j) {cur a[j];if(cur sum / i) cur 0, k;}ans[i] (cur 0 k i);}while(Q--) {int x read();puts(!ans[x] ? No : Yes);}
}
数据保证随机的意思是 sum 的因子不会太多构造数据可以达到1e5级别 另外可能有一个坑点因为有负数的存在如果当前数大于了 sum/k 了是不能直接跳出的这是针对标程的解法的用前缀和就不存在这个问题
还是要注意一下负数啊各种题中尤其是那种说 int范围的。比如这题 不对啊我那种方法其实修改一下也是正确的用set维护一个pair前缀当前下标然后每次二分查找pair那个值上一次查找的下标这样找到的就是pair那个值那个下标后面的值或者pair大于那个值下标无所谓我们在if判断一下是否是第一种就可以了。
