Codeforces Round #829 (Div. 2) C1. Make Nonzero Sum (easy version)

news/2024/11/24 1:07:39/

 

翻译:

这是这个问题的简单版本。不同之处在于,在这个版本中,数组不能包含零。只有两个版本的问题都解决了,你才能进行hack。

给定一个数组[𝑎1,𝑎2,…𝑎𝑛],由整数−1和1组成。您必须将这个数组的一个分区构建到段集[𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑘,𝑟𝑘],具有以下属性:

表示所有元素的交错和𝑖-th段的𝑠𝑖:𝑠𝑖=𝑎𝑙𝑖−𝑎𝑙𝑖+ 1 +𝑎𝑙𝑖+ 2−𝑎𝑙𝑖+ 3 +…±𝑎𝑟𝑖。例如,数组[1,0,−1,1,1]中段[2,4]的元素交替和等于0−(−1)+1=2。
𝑠𝑖对所有分区段的和应该等于零。
注意,每个𝑠𝑖不一定等于零,这个属性是𝑠𝑖在所有分区段上的和。

片段的集合(𝑙1𝑟1],[𝑙2𝑟2],…,[𝑙𝑘,𝑟𝑘)被称为分区长度的数组𝑎𝑛如果1 =𝑙1≤𝑟1,𝑙2≤𝑟2,…,𝑙𝑘≤𝑟𝑘=𝑛𝑟𝑖+ 1 =𝑙𝑖所有𝑖= 1 + 1,2,…𝑘−1。换句话说,数组的每个元素必须只属于一个段。

您必须用上面描述的属性构建给定数组的分区,或者确定这样的分区不存在。

注意,不需要最小化分区中的段数。

输入
每个测试包含多个测试用例。第一行包含测试用例的数量𝑡(1≤𝑡≤10000)。测试用例的描述如下。

每个测试用例的第一行包含一个整数𝑛(1≤𝑛≤200000)—数组𝑎的长度。

每个测试用例的第二行包含𝑛整数𝑎1,𝑎2,…,𝑎𝑛(𝑎𝑖是−1或1)-给定数组的元素。

可以保证𝑛在所有测试用例中的总和不超过200000。

输出
对于每个测试用例,如果所需的分区不存在,则打印−1。否则,打印一个整数𝑘—分区中的段数。

然后在以下𝑘行的𝑖-th中打印两个整数𝑙𝑖和𝑟𝑖—𝑖-th段的描述。应满足以下条件:

1到𝑘的每个𝑖,𝑙𝑖≤𝑟𝑖。
从1到(𝑘−1)的每个𝑖对应𝑙𝑖+1=𝑟𝑖+1。
𝑙1 = 1,𝑟𝑘=𝑛。
如果数组中有多个正确的分区,打印其中任何一个分区。

例子
inputCopy
4
4
1 1 1 1
6
-1 1 1 1 1 1
3.
1 1 1
1
1
outputCopy
1
1 - 4
2
1 3
4 - 6
-1
-1
请注意
在第一个测试用例中,我们可以构建一个长度为4的分段。这段的和等于1−1+1−1=0。

在第二个测试用例中,我们可以构建长度为3的两个段的分区。第一个段的和等于−1−1+1=−1,第二个段的和等于1−1+1=1。所以,总和等于- 1+1=0。

在第三和第四个测试用例中,可以证明没有必要的分区。

题意:将该数组分段,然后分段和按照公式来计算,所以相同的就分到一个,等于0,不相同的单个分,每次都是0,只需要判断一个n是不是奇数,奇数的话,怎么加减都不会是0。

代码实现:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
int a[200005];
void solv(){cin>>n;for (int i =1; i<=n; i++) {cin>>a[i];}if (n%2) {printf("-1\n");return;}vector<pair<int, int>>q;for (int i =1; i<n; i+=2) {if (a[i]==a[i+1]) {q.push_back({i,i+1});}else{q.push_back({i,i});q.push_back({i+1,i+1});}}printf("%lu\n",q.size());for (int i =0; i<q.size(); i++) {printf("%d %d\n",q[i].first,q[i].second);}
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {solv();}return 0;
}


http://www.ppmy.cn/news/541271.html

相关文章

Codeforces Round #829——无EF,以后有时间再发这个

目录 A&#xff1a;Technical Support B&#xff1a;Kevin and Permutation C1 &#xff1a;Make Nonzero Sum (easy version) C2&#xff1a;Make Nonzero Sum (hard version) D&#xff1a;Factorial Divisibility E&#xff1a;Wish I Knew How to Sort A&#xff1a;…

CodeForces Round #829 (div.2) A~C2

A. Technical Support 题意&#xff1a; 给定一个只包含 Q, A 的字符串&#xff0c;问每个 Q(问题) 能否匹配所有 A(回答)。 思路&#xff1a; 一个 Q 可以对应多个 A&#xff0c;可以允许 A 没有对应的 Q&#xff0c;即允许在 A 之前没有 Q. 代码如下&#xff1a; #incl…

Codeforces Round #829 (Div. 1) D.The Beach(最短路/流量为1的费用流)

题目 n*m(n*m<3e5)的网格图&#xff0c;由空地、石头和1*2的床组成&#xff0c; Andrew想在网格图上找一个1*2的空地用来放床&#xff0c;他可以把别人的床进行如下挪动&#xff1a; ①花费p(1<p<1e9)的代价&#xff0c;以床的一个端点为轴不动&#xff0c; 将另一…

Codeforces Round #829 (Div. 2) D. Factorial Divisibility

Codeforces Round #829 (Div. 2) D. Factorial Divisibility Let’s create an array [ c n t 1 , c n t 2 , … , c n t x ] [cnt_1,cnt_2,…,cnt_x] [cnt1​,cnt2​,…,cntx​] where c n t i cnt_i cnti​ equals to number of elements equals to i in the initial arra…

Codeforces Round #829 (Div. 2) A-E

废话&#xff1a;本来前50分钟kill完了A B C1 D的时候是前300&#xff0c;看着C2过的人很少就想着摆了&#xff0c;结果刷了会儿视频一看我都排到700了&#xff0c;这才开始做C2&#xff0c;结果到最后C2卡线过的&#xff0c;E应该能过也没时间想了。直接排名干到700了。 Code…

Codeforces Round #829 (Div. 2)部分题解A B C1 E

原题地址&#xff1a;Dashboard - Codeforces Round #829 (Div. 2) - Codeforces A. Technical Support 题意&#xff1a; 有一个只包含“Q”和"A"的字符串&#xff0c;Q代表问题&#xff0c;A代表回答&#xff0c;有问必有答&#xff0c;也就是Q后面一…

Codeforces Round #829 (Div. 2)——(ABC1)题解

一、解题思路 1.A. Technical Support——1754A 题目分析&#xff1a;题目给定了一串字符串&#xff0c;字符串包含了两种字符一个为‘Q’表示问题&#xff0c;另一个字符A表示回答问题&#xff0c;题目要求输出是否对于每个问题&#xff0c;都做出了解答&#xff0c;若是输出…

windows微信协议|PC微信协议829版

最新windows协议|PC微信协议829版采用最新算法,达到非常稳定的效果&#xff0c;自己研发&#xff0c;功能多&#xff0c;并发量高&#xff0c;稳定好用&#xff0c;不掉线&#xff0c;不封号。mmtls是基于1.3的tls协议简化修改而来&#xff0c;根据某公司的描述&#xff0c;这种…