D. Divide and Summarize(思维)

「爱情、让人受尽委屈。」 2021-07-16 18:07 387阅读 0赞

[题目][Link 1]

思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判断，当时直接爆栈了，才发现这里无限递归了下去。细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    ll sum[Max];
    map<ll, int> ma;
    
    void check(int l, int r)
    { 
    	int f = 1;
    	int k = lst[l];
    	for (int i = l;i <= r;i++)if (k != lst[i]) {  f = 0; }
    	if (f){ ma[sum[r] - sum[l - 1]]++;return;}
    	ma[sum[r] - sum[l - 1]]++;
    	double mid = double((double)lst[l] + lst[r]) / 2;
    	int j;
    	for (int i = l;i <= r;i++)if (mid >= lst[i])j = i;
    	check(l, j);check(j+1, r);
    }
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, m;cin >> n >> m;
    		ma.clear();
    		for (int i = 1;i <= n;i++)cin >> lst[i];
    		sort(lst + 1, lst + 1 + n);
    		for (int i = 1;i <= n;i++)sum[i] = sum[i - 1] + lst[i];
    		check(1, n);
    		for (int i = 1;i <= m;i++)
    		{ 
    			int s;cin >> s;if (ma[s])cout << "YES" << endl;
    			else cout << "NO" << endl;
    		}
    	}
    }

[Link 1]: https://codeforc.es/contest/1461/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，387人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1305 Pairwise Sum and Divide

[1305 Pairwise Sum and Divide][] ![ok.png][] 题目来源： [1305 Pairwise Sum and Divide]: ht

左手的ㄟ右手/ 2024年02月17日 22:55/ 0 赞/ 43 阅读

相关分治策略Divide and Conquer

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，通常是递归算法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直

曾经终败给现在/ 2022年09月25日 11:18/ 0 赞/ 160 阅读

相关 hdu--6060--RXD and dividing

RXD and dividing Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/52428

傷城~/ 2022年06月10日 01:11/ 0 赞/ 141 阅读

相关 Divide and parallelize large data problems with Rcpp

by [Błażej Moska][B_a_ej Moska], computer science student and data science intern Got s

港控/mmm°/ 2022年06月02日 08:25/ 0 赞/ 188 阅读

相关 uva 10375 - Choose and divide(组合数）

[题目连接：uva 10375 - Choose and divide][uva 10375 - Choose and divide] 题目大意：给出p，q，s和r

Love The Way You Lie/ 2022年05月12日 22:14/ 0 赞/ 177 阅读

相关 1372 D. Omkar and Circle (思维、前缀和)

[题目][Link 1] 思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总

素颜马尾好姑娘i/ 2021年07月16日 19:14/ 0 赞/ 381 阅读

相关 D. Divide and Sum (组合数、思维)

[添加链接描述][Link 1] 对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。看例子 a1 a2 a3 a4 a5

痛定思痛。/ 2021年07月16日 18:48/ 0 赞/ 356 阅读

相关 1455D Sequence and Swaps（思维）

D. Sequence and Swaps time limit per test 1.5 seconds memory limit per test

本是古典何须时尚/ 2021年07月16日 18:42/ 0 赞/ 337 阅读

相关 D. Divide and Summarize(思维)

[题目][Link 1] 思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判

「爱情、让人受尽委屈。」/ 2021年07月16日 18:07/ 0 赞/ 388 阅读

相关 D. Tokitsukaze, CSL and Stone Game （思维、game）

[题目][Link 1] 思路：先手必输的情况： 1.有两个以上两堆石子数目相同。 2.有3堆以上石子数目相等、有两堆0石子。 3.有一个两堆数

今天药忘吃喽~/ 2021年07月16日 12:13/ 0 赞/ 383 阅读