首页 > 其他分享 >每日一题 第七期 Codeforces Round 929 (Div. 3) Editorial

每日一题 第七期 Codeforces Round 929 (Div. 3) Editorial

时间:2024-03-17 14:32:51浏览次数:32  
标签:10 int 第七期 bmod Codeforces 929 test YES include

Turtle Tenacity: Continual Mods

D. Turtle Tenacity: Continual Mods

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output
Given an array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​, determine whether it is possible to rearrange its elements into b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1​,b2​,…,bn​, such that b 1   m o d   b 2   m o d   …   m o d   b n ≠ 0 b_1 \bmod b_2 \bmod \ldots \bmod b_n \neq 0 b1​modb2​mod…modbn​=0.

Here x   m o d   y x \bmod y xmody denotes the remainder from dividing x x x by y y y. Also, the modulo operations are calculated from left to right. That is, x   m o d   y   m o d   z = ( x   m o d   y )   m o d   z x \bmod y \bmod z = (x \bmod y) \bmod z xmodymodz=(xmody)modz. For example, 2024   m o d   1000   m o d   8 = ( 2024   m o d   1000 )   m o d   8 = 24   m o d   8 = 0 2024 \bmod 1000 \bmod 8 = (2024 \bmod 1000) \bmod 8 = 24 \bmod 8 = 0 2024mod1000mod8=(2024mod1000)mod8=24mod8=0.
Input

The first line of the input contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n n n ( 2 ≤ n ≤ 1 0 5 2 \le n \le 10^5 2≤n≤105).

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​ ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai​≤109).

The sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
Output

For each test case, output “YES” if it is possible, “NO” otherwise.

You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.

题面翻译

给定一个长度为 n n n 的数组 a a a。你需要将其重新排列成数组 b b b,判断是否存在一种方案使得 b 1   m o d   b 2   m o d   …   m o d   b n ≠ 0 b_1 \bmod b_2 \bmod \dots \bmod b_n \ne 0 b1​modb2​mod…modbn​=0。

样例 #1

样例输入 #1

8
6
1 2 3 4 5 6
5
3 3 3 3 3
3
2 2 3
5
1 1 2 3 7
3
1 2 2
3
1 1 2
6
5 2 10 10 10 2
4
3 6 9 3

样例输出 #1

YES
NO
YES
NO
YES
NO
YES
NO

Note

In the first test case, rearranging the array into b = [ 1 , 2 , 3 , 4 , 5 , 6 ] b = [1, 2, 3, 4, 5, 6] b=[1,2,3,4,5,6] (doing nothing) would result in 1   m o d   2   m o d   3   m o d   4   m o d   5   m o d   6 = 1 1 \bmod 2 \bmod 3 \bmod 4 \bmod 5 \bmod 6 = 1 1mod2mod3mod4mod5mod6=1. Hence it is possible to achieve the goal.

In the second test case, the array b b b must be equal to [ 3 , 3 , 3 , 3 , 3 ] [3, 3, 3, 3, 3] [3,3,3,3,3], which would result in 3   m o d   3   m o d   3   m o d   3   m o d   3 = 0 3 \bmod 3 \bmod 3 \bmod 3 \bmod 3 = 0 3mod3mod3mod3mod3=0. Hence it is impossible to achieve the goal.

In the third test case, rearranging the array into b = [ 3 , 2 , 2 ] b = [3, 2, 2] b=[3,2,2] would result in 3   m o d   2   m o d   2 = 1 3 \bmod 2 \bmod 2 = 1 3mod2mod2=1. Hence it is possible to achieve the goal.

AC代码:

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;

int t;
int n;
int a[N];
int main()
{
    cin >> t;
	while(t --)
	{
		cin >> n;
		int flag = 0;
		for(int i = 1; i <= n; i ++)
		{
			cin >> a[i];
		}
		sort(a + 1, a + 1 + n);
		if(a[1] != a[2]) puts("YES");
		else {
			for(int i = 2; i <= n; i ++)
			{
				if(a[i] % a[1] != 0) flag = 1;
			}
			if(flag) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

标签:10,int,第七期,bmod,Codeforces,929,test,YES,include
From: https://blog.csdn.net/2301_80882026/article/details/136781591

相关文章

  • Codeforces Round 934 (Div. 2)
    CodeforcesRound934(Div.2)A-DestroyingBridges解题思路:完全图每个点的连边数为\(n-1\)。\(k<n-1\):都可到达。\(k\geqn-1\):将点\(1\)的边删完,只能呆在点\(1\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=......
  • Codeforces Round 908 (Div. 2)
    CodeforcesRound908(Div.2)A-SecretSport解题思路:有一说一,没看很懂,感觉最后赢的就是赢了。。。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingpiii=pair<ll,pa......
  • Codeforces 1948G MST with Matching
    因为贡献是两个之和,考虑固定下一个,求解另一个的最优。\(\text{MST}\)似乎找不到什么好的办法固定,便考虑固定下最大匹配。对于树的最大匹配,考虑到因为树也是二分图,所以树的最大匹配\(=\)最小点覆盖。考虑如果知道了最小点覆盖内的点,那就说明如果一条边两个端点都不在点集中,是......
  • Educational Codeforces Round 163 A-E
    A.SpecialCharacters构造。形如\(A\)和\(B\)这类单个字符构成的字符串对答案的贡献为\(0\),而\(AA\)和\(AAAA\)这类多个相同字符构成的字符串对答案的贡献固定为\(2\)​,则无法构造出奇数值,由第二类字符串拼接即可构造出偶数值。时间复杂度:\(O(n)\)。#include<bit......
  • Codeforces 1948E Clique Partition
    考虑到有\(|i-j|\),所以肯定是让相邻的一部分在一个团里。考虑构造出一个最长长度的,后面类似复制几遍即可。考虑到\(|k-1|=k-1\),且因为\(a_i\)为一个排列,差的绝对值至少为\(1\),所以只考虑两端最长长度也只可能为\(k\)。不妨先假设最长长度为\(k\)来构造。那么......
  • Codeforces-1005C
    https://codeforces.com/problemset/problem/1005/C一、代码目录#include<bits/stdc++.h>usingnamespacestd;voidsolve(){inta[122222],n,ans=0;map<int,int>m;scanf("%d",&n);for(inti=0;i<n;i++){......
  • Educational Codeforces Round 163 (Rated for Div. 2)
    EducationalCodeforcesRound163(RatedforDiv.2)A-SpecialCharacters解题思路:一个相同的连续段会贡献两个特殊字符,所以答案一定是偶数,找个不同的数分隔开即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll......
  • Codeforces Round 933 (Div. 3)赛后总结
    CodeforcesRound933(Div.3)B从边缘开始计算,因为边缘肯定只能一个一个减,就可以遍历得到答案.代码C只要对mapie特判,然后判断map和pie的个数就是答案了。D(记忆化搜索)可以通过二维数组来标记搜索状态,将已经出现过的状态直接返回,极大减少时间。#include<bits/stdc++.h>......
  • Codeforces Round 933 (Div. 3) A - G 题解
    CodeforcesRound933(Div.3)A-RudolfandtheTicketSolution因为\(n\)很小,直接枚举\(b_i+c_j\)所产生的所有数字Code#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,m,k;cin>>n>>m>>k;intans=0;......
  • CodeForces 1874E Jellyfish and Hack
    洛谷传送门CF传送门显然\(\text{fun}(P)_{\max}=\frac{|P|(|P|+1)}{2}\)。考虑大力dp,设\(f_{i,j,k}\)为\(|P|=i\),\(P_1=j\),\(\text{fun}(P)=k\)的排列\(P\)的个数。此时\(|L|=j-1,|R|=i-j\)。转移枚举\(L_1,R_1,\text{fun}(L),\text{fun}(R......