牛客月赛48（2022-04-22 19:00:00 至 2022-04-22 21:00:00）

牛客小白月赛48

目录

孤独的数组

博弈大师

可疑的区间

交替加乘

或与异或

孤独的树

给出一个长度为 nnn 的整数数组AAA，分别为A1,A2,...,AnA_1,A_2,...,A_nA1​,A2​,...,An​。牛牛可以对数组进行 *** 作，每次 *** 作选定一个下标 iii (1≤i≤n)(1\le i\le n)(1≤i≤n)，再确定一个整数 kkk (0

”孤独的数组“ 定义： 对于全部 i (2≤i≤n)i\ (2\le i\le n)i (2≤i≤n)，gcd(Ai−1,Ai)=1gcd(A_{i-1},A_i)=1gcd(Ai−1​,Ai​)=1。

如果无论怎么 *** 作都无法让数组变成孤独的，输出 −1-1−1。

第一行包括一个整数 nnn (2≤n≤105)(2\le n\le 10^5)(2≤n≤105) 表示数组的长度。

第二行包括 nnn 个整数，分别表示 A1,A2,...,AnA_1,A_2,...,A_nA1​,A2​,...,An​，(1≤Ai≤109)(1\le A_i\le 10^9)(1≤Ai​≤109) 。

输出一行，包含一个整数，表示最小的 *** 作次数。

示例1

复制2 1 2

2
1 2

复制0

0

gcd(1,2)=1gcd(1,2)=1gcd(1,2)=1，无需再 *** 作。

示例2

复制2 2 2

2
2 2

复制-1

-1

无论怎么 *** 作都无法让 gcd(A_1,A_2)=1gcd(A1​,A2​)=1，输出 −1-1−1。

思路：读题之后发现，如果数组中存在 gcd(Ai,Ai+1)！=1,那么就输出-1，否则就是0；因为题目给的 *** 作对变成孤独数组毫无作用。

import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		
		int flag=0;
		long a=cin.nextLong();
		for(int i=1;i1) {
				flag=1;
				break;
			}
			a=b;
		}
		
		if(flag==0)System.out.println(0);
		else System.out.println(-1);
	}

	private static long gcd(long a, long b) {
		// TODO Auto-generated method stub
		if(b==0)return a;
		return gcd(b,a%b);
	}

}

一堆数量为 nnn 的石子摆在牛牛和牛妹面前，由于双方都是博弈大师，它们打算一决高下。

经过双方讨论后决定的游戏规则：采取回合制游戏，双方轮流 *** 作一回合。第 iii 回合的 *** 作者会从石头堆中拿走 iii 个石子 ((( 第 111 回合拿走 111 个，第 222 回合拿走 222 个，以此类推 )))。若第 iii 回合的时候，石子的总数小于 iii，那么该回合的 *** 作者会输掉比赛。由于牛牛是个绅士牛，所以打算第一回合让牛妹先 *** 作，第二回合牛牛 *** 作，第三回合再次轮到牛妹 *** 作。

除此之外，牛牛拥有 aaa 张技能卡，牛妹拥有 bbb 张。

技能卡的作用：技能卡可以在任意时刻发动，每个回合任意一方可以发动多次，每次消耗一张卡。发动技能卡时，可以改变当前回合的 *** 作者。

例如第 iii 回合是牛牛 *** 作，此时无论谁发动该回合的第一张技能卡，第 iii 回合的 *** 作者就会变成牛妹。如果此时有人发动该回合的第二张卡，那么 *** 作者又会变成牛牛，以此类推，直到该回合双方都不再发动技能卡，此时 *** 作者再进行 *** 作。

需要注意的是，如果该回合使用了卡导致 *** 作者最终发生了改变，那么下一回合的初始 *** 作者也随之改变。例如：第一回合是牛妹 *** 作，牛牛使用了一张卡，这一回合实际 *** 作者是牛牛，那么第二回合的初始 *** 作者就会是牛妹。

问：双方都采取最佳策略，谁会是这场比赛的胜利者？

第一行包含一个整数 T (1≤T≤105)T\ (1\le T\le 10^5)T (1≤T≤105)，代表询问组数。

接下来 TTT 行，每行包含三个整数 n a b (1≤n≤1016,0≤a,b≤1016)n\ a\ b\ (1\le n\le10^{16},0\le a,b\le 10^{16})n a b (1≤n≤1016,0≤a,b≤1016)，分别代表 nnn 个石子，牛牛拥有 aaa 张技能卡，牛妹拥有 bbb 张技能卡。

输出包含 TTT 行，每行输出一个字符串，如果牛牛获胜，输出 “niuniu”，如果牛妹获胜，输出 ”niumei“。不包含引号。

示例1

复制3 1 0 0 1 1 0 3 0 1

3
1 0 0
1 1 0
3 0 1

复制niumei niuniu niumei

niumei
niuniu
niumei

对于 n=1,a=b=0n=1,a=b=0n=1,a=b=0 ，第 111 回合牛妹拿走 111 个石子，此时还有 000 个石子，第 222 回合石子数量小于 222 ，该回合 *** 作者是牛牛，牛牛输掉比赛，牛妹获胜。

对于 n=1,a=1,b=0n=1,a=1,b=0n=1,a=1,b=0，牛牛拥有一张技能卡，在第 111 回合的时候发动技能卡，让第 111 回合的 *** 作者变成自己，拿走 111 个石子，此时还有 000 个石子，第 222 回合轮到牛妹，石子数量小于 222，该回合的 *** 作者牛妹输掉比赛，牛牛获胜。

对于 n=3,a=0,b=1n=3,a=0,b=1n=3,a=0,b=1，牛妹拥有一张技能卡，第 111 回合牛妹拿走 111 个石子，第 222 回合牛妹发动技能卡，再次拿走 222 个石子，第 333 回合轮到牛牛，此时石子数量小于 333，该回合的 *** 作者牛牛输掉比赛，牛妹获胜。

思路：首先求出能够进行多少局，通过题意可知，他们每次拿的相当于一个等差数列，通过等差数列求和的式子可以算出局数。再对不同的局数进行判断：

        1.如果局数为奇数，那么在不使用技能卡的情况下是niumei获胜，这时候我们只需要判断niuniu能否逆转，也就是它的技能卡是否比niumei多。

        2.如果局数为奇数，那么在不使用技能卡的情况下是niuniu获胜，这时候我们只需要判断niumei能否逆转，也就是它的技能卡是否比niuniu多。

import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(System.in);
		
		int t=cin.nextInt();
		while(t-->0) {
			long n=cin.nextLong();
			long a=cin.nextLong();
			long b=cin.nextLong();
			
			long f=(long) Math.sqrt(n*2);
			
			if(f*(f+1)>n*2) {
				f=f-1;
			}
			
			if(f%2!=0) {
				if(a>b)System.out.println("niuniu");
				else System.out.println("niumei");
			}else {
				if(b>a)System.out.println("niumei");
				else System.out.println("niuniu");
			}
		}
		
		
	}

}

给出 nnn 个有趣的区间 [L1,R1],[L2,R2],...,[Ln,Rn][L_1,R_1],[L_2,R_2],...,[L_n,R_n][L1​,R1​],[L2​,R2​],...,[Ln​,Rn​]，编号分别为 1∼n1\sim n1∼n。给出一个整数 lenlenlen ，对于任意一段长度为 lenlenlen 的区间 [l,r],(r−l+1=len)[l,r],(r-l+1=len)[l,r],(r−l+1=len)，其中 lll 是正整数。其有趣值的定义为：与 [l,r][l,r][l,r] 有交集的有趣的区间个数。其权重的定义为：与 [l,r][l,r][l,r] 有交集的有趣的区间编号的总和。

例如有 333 个有趣的区间 [1,3],[2,4],[5,6][1,3],[2,4],[5,6][1,3],[2,4],[5,6]，编号分别为 1∼31\sim 31∼3。 [2,3][2,3][2,3] 的有趣值为 222 ( [2,3][2,3][2,3] 与 [1,3],[2,4][1,3],[2,4][1,3],[2,4] 有交集)，权重为 1+2=31+2=31+2=3。

牛牛选择了一段长度为 lenlenlen 的 [l,r],(r−l+1=len)[l,r],(r-l+1=len)[l,r],(r−l+1=len)，其中 lll 是正整数。牛牛会选择有趣值最大的区间，如果两个区间有趣值相同，那么牛牛会选权重最大的。

对于一段区间 [l,r],r−l+1=len[l,r],r-l+1=len[l,r],r−l+1=len ，其中 lll 是正整数。可能被牛牛选择，那么这段区间就是可疑的，请输出可疑的区间的个数。

第一行包含两个整数 n len (1≤n≤106,1≤len≤5×106)n\ len\ (1\le n\le10^6,1\le len\le5\times10^6)n len (1≤n≤106,1≤len≤5×106)，表示有趣的区间的个数和选择区间的长度。

接下来 nnn 行，每行包含两个整数 L,R (1≤L≤R≤5×106)L,R\ (1\le L\le R\le 5\times10^6)L,R (1≤L≤R≤5×106)，分别表示区间的左右端点。

输出包含一个整数，表示可疑区间的个数。

示例1

复制3 2 1 3 2 5 5 6

3 2
1 3
2 5
5 6

复制2

2

[1,2][1,2][1,2]：和第 1,21,21,2 个区间有交集，有趣值为 222，权重为 333。

[2,3][2,3][2,3]：和第 1,21,21,2 个区间有交集，有趣值为 222，权重为 333。

[3,4][3,4][3,4]：和第 1,21,21,2 个区间有交集，有趣值为 222，权重为 333。

[4,5][4,5][4,5]：和第 2,32,32,3 个区间有交集，有趣值为 222，权重为 555。

[5,6][5,6][5,6]：和第 2,32,32,3 个区间有交集，有趣值为 222，权重为 555。

其余长度为 222 的区间有趣值都小于 222。

有 222 个可疑区间 [4,5][4,5][4,5] 和 [5,6][5,6][5,6]。

思路：对与有趣值我们可以进行差分处理，而权重记录下来即可，然后遍历求解

import java.util.*;
import java.io.*;

public class Main{
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) {
			br=new BufferedReader(new InputStreamReader(in),16834);
			eat("");
		}
		
		public void eat(String s) {
			st=new StringTokenizer(s);
		}
		
		public String nextLine() {
			try {
				return br.readLine();
			}catch(IOException e) {
				return null;
			}
		}
		
		public boolean hasNext() {
			while(!st.hasMoreTokens()) {
				String s=nextLine();
				if(s==null)return false;
				eat(s);
			}
			return true;
		}
		
		public String next() {
			hasNext();
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
	static FastScanner cin=new FastScanner(System.in);
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	static int N=10000010;
	public static void main(String[] args) {
		int n=cin.nextInt(),len=cin.nextInt();
		long l[]=new long[N],r[]=new long[N];
		long lx[]=new long[N],rx[]=new long[N];
		
		for(int i=1;i<=n;i++) {
			int a=cin.nextInt();
			int b=cin.nextInt();
			l[a]++;r[b]++;
			lx[a]+=i;rx[b]+=i;
		}
		
		long sum=0,max=0;
		for(int i=1;i<=len;i++) {
			sum+=l[i];
			max+=lx[i];
		}
		
		long ans=sum,cnt=max,ff=1;
		for(int i=len+1;ians||(sum==ans&&max>cnt)) {
				ans=sum;cnt=max;ff=1;
			}else if(sum==ans&&max==cnt) {
				ff++;
			}
		}
		
		out.println(ff);
		out.flush();
	}
}

有一个长度 nnn 的数组 A1,A2,A3,...,AnA_1,A_2,A_3,...,A_nA1​,A2​,A3​,...,An​，可以对数组 AAA 进行任意排列。问：经过排列后，数组 AAA 进行"交替加乘”运算得到最大的结果是多少。

“交替加乘”运算规则：A1A_1A1​ 和 A2A_2A2​ 相加，相加后结果乘以 A3A_3A3​，相乘后结果再加上 A4A_4A4​，相加后结果乘以 A5A_5A5​，以此类推直到 AnA_nAn​。

数组 AAA 长度为 777 ，计算如：(((A1+A2)×A3+A4)×A5+A6)×A7(((A_1+A_2)\times A_3+A_4)\times A_5+A_6)\times A_7(((A1​+A2​)×A3​+A4​)×A5​+A6​)×A7​

数组 AAA 长度为 888 ，计算如：(((A1+A2)×A3+A4)×A5+A6)×A7+A8(((A_1+A_2)\times A_3+A_4)\times A_5+A_6)\times A_7+A_8(((A1​+A2​)×A3​+A4​)×A5​+A6​)×A7​+A8​

求取模前的最大结果，输出对 109+710^9+7109+7 取模。

第一行包括一个整数 nnn (2≤n≤105)(2\le n\le10^5)(2≤n≤105)，表示数组的长度。

第二行包括 nnn 个整数，分别表示 A1,A2,...,AnA_1,A_2,...,A_nA1​,A2​,...,An​，(1≤Ai≤109)(1\le A_i\le10^9)(1≤Ai​≤109) 。

输出一行，包含一个整数，表示 ( 取模前最大结果  mod  (109+7) )(\ 取模前最大结果\ \bmod\ (10^9+7)\ )( 取模前最大结果 mod (109+7) ) 。

示例1

复制3 3 2 2

3
3 2 2

复制12

12

取得最大结果的数组 AAA 一种排列为 [2,2,3][2,2,3][2,2,3]，最大结果是 (2+2)×3=12(2+2)\times 3=12(2+2)×3=12，对 109+710^9+7109+7 取模，输出 121212。

思路 ：对于交叉相乘得最大值，肯定是保证相乘的两个数越大越好，那么，加数应该是从大到小往后加，乘数应该是从小到大乘，这样才是最优解，其实如果不理解，也可以写一个全排列，然后模拟一下，就会发现规律了。

import java.util.*;
import java.io.*;

public class Main{
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) {
			br=new BufferedReader(new InputStreamReader(in),16834);
			eat("");
		}
		
		public void eat(String s) {
			st=new StringTokenizer(s);
		}
		
		public String nextLine() {
			try {
				return br.readLine();
			}catch(IOException e) {
				return null;
			}
		}
		
		public boolean hasNext() {
			while(!st.hasMoreTokens()) {
				String s=nextLine();
				if(s==null)return false;
				eat(s);
			}
			return true;
		}
		
		public String next() {
			hasNext();
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
	static FastScanner cin=new FastScanner(System.in);
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	static int mod=(int) (1e9+7);
	public static void main(String[] args) {
		int n=cin.nextInt();
		long a[]=new long[n];
		
		for(int i=0;i=0&&j=0)ans=(ans+a[i--])%mod;
		while(j

3
1 2 3
3 2 4
3 5 3

YES
NO
YES

import java.util.*;
import java.io.*;

public class Main{
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) {
			br=new BufferedReader(new InputStreamReader(in),16834);
			eat("");
		}
		
		public void eat(String s) {
			st=new StringTokenizer(s);
		}
		
		public String nextLine() {
			try {
				return br.readLine();
			}catch(IOException e) {
				return null;
			}
		}
		
		public boolean hasNext() {
			while(!st.hasMoreTokens()) {
				String s=nextLine();
				if(s==null)return false;
				eat(s);
			}
			return true;
		}
		
		public String next() {
			hasNext();
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
	static FastScanner cin=new FastScanner(System.in);
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	static boolean flag=false;
	static long c;
	public static void main(String[] args) {
		
		int t=cin.nextInt();
		while(t-->0) {
			flag=false;
			
			long a=cin.nextLong();
			long b=cin.nextLong();
			c=cin.nextLong();
			
			dfs(0,a,b);
			
			if(flag)out.println("YES");
			else out.println("NO");
		}
		out.flush();
	}
	private static void dfs(int u, long a, long b) {
		// TODO Auto-generated method stub
		if(a==c||b==c)flag=true;
		if(flag||u==6)return;
		dfs(u+1,a&b,b);
		dfs(u+1,a,a&b);
		dfs(u+1,a|b,b);
		dfs(u+1,a,a|b);
		dfs(u+1,a^b,b);
		dfs(u+1,a,a^b);
	}
	

}

输出一行包含一个整数，代表最少 *** 作次数。

4
2 8 2 1
1 2
2 3
3 4

2

如果对节点 222  *** 作，需要 333 次。对节点 111 和 333 分别 *** 作 111 次即可。

import java.util.*;
import java.io.*;

public class Main{
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream in) {
			br=new BufferedReader(new InputStreamReader(in),16834);
			eat("");
		}
		
		public void eat(String s) {
			st=new StringTokenizer(s);
		}
		
		public String nextLine() {
			try {
				return br.readLine();
			}catch(IOException e) {
				return null;
			}
		}
		
		public boolean hasNext() {
			while(!st.hasMoreTokens()) {
				String s=nextLine();
				if(s==null)return false;
				eat(s);
			}
			return true;
		}
		
		public String next() {
			hasNext();
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
	static FastScanner cin=new FastScanner(System.in);
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	
	static int N=100010;
	static Vector a[]=new Vector[N];
	static int val[]=new int[N];
	static long ans=0;
	
	public static void main(String[] args) {
		int n=cin.nextInt();
		
		for(int i=0;i<=n;i++)a[i]=new Vector<>();
		
		for(int i=1;i<=n;i++) {
			val[i]=cin.nextInt();
		}
		
		for(int i=1;i