题目描述

阿强来到大街上，街上有 N 个人，编号为 1 ∼N 。简单起见，我们把每个人都看成一条线上的一个点。对每个合法的 i，第 i 个人的位置是 x_ixi​。

这些人当中恰好有一个感染了 COVID-19，但我们不知道是哪一个。当一个被感染的人和一个未被感染的人之间的距离不超过 2 时，病毒会从前者传播到后者。如果我们等待足够长的时间，会有一些人（这些人由第一个感染者确定）被感染；这些人的数量被称作最终被感染的人数。

阿强希望求出最终被感染的人数的最小和最大可能的值，也就是最好和最坏情况下这个数的值。

输入描述:

第一行包含一个整数T(1≤T≤2,000)(1≤T≤2,000)，表示数据组数。接下来是T组数据。
•每组数据的第一行包含一个整数N(2≤N≤8)(2≤N≤8)。
•第二行包含N个整数x_1,x_2, dots, x_n (0≤x_i≤10)x1​,x2​,…,xn​(0≤xi​≤10)，用空格隔开。

输出描述:

对于每组数据，输出一行包含两个整数，用空格隔开，表示最终被感染的人数的最小值和最大值。

示例1

输入

复制

3
2
3 6
3
1 3 5
5
1 2 5 6 7

输出

复制

1 1
3 3
2 3

 思路：本题数据不大，可以排序后枚举找出最小和最大的感染数

import java.util.Arrays;
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) {
			int n=cin.nextInt();
			int a[]=new int[n];
			
			for(int i=0;i 
阿强与网格 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
题目描述 
阿强在一个N行M列的网格中。
 阿强可以用两种方式移动：
 向下、向左、向上或向右移动，每次移动的代价为X。换句话说，如果您位于网格的单元格（i，j），则可以转到任意单元格（i+1，j），（i，j−1） ，（i−1，j）或（i，j+1），代价为X。
 
沿对角线向左下、向右下、向左上、向右上移动成本为Y。换句话说，如果你在网格的单元格（i，j）上，你可以去任意一个单元格（i+1，j−1） ，（i+1，j+1），（i−1，j−1） 或(i−1，j+1），代价为Y。
 
请你找到从阿强从左上角（1,1）到右下角（N，M）的最小成本。
 
阿强不能移出网格。
 
输入描述: 
 
第一行一个整数T(1≤T≤5∗105)(1leq T leq 5*10^5)(1≤T≤5∗105)表示数据组数。
 
接下来T行每行四个整数N,M,X,Y(1≤N,M,X,Y≤106)(1 leq N,M,X,Y leq 10^6)(1≤N,M,X,Y≤106)
 
输出描述: 
对于每组数据一行表示答案。
 
示例1
 
输入 
复制3 5 6 2 5 4 7 5 6 7 8 6 5
 
3
5 6 2 5
4 7 5 6
7 8 6 5
 
输出 
复制18 33 36
 
18
33
36
 
思路：本题可以通过数学方法来计算：
 
1.首先判断是走折线还是直线，判断条件：2x?y;
 
2.在走折线的过程中，如果不能一次折线到，那么再进行判断,x?y;
 
#include
using namespace std;

typedef long long ll;

int main(){
	ll t,n,m,x,y;
	
	scanf("%lld",&t);
	while(t-->0){
		scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
		
		ll sum=0;
		n--;m--;
		
		if(n==0||m==0){
			sum=((n==0)?m:n)*x;	
		}else{
			if(2*x>y){
				sum=((m>n)?n:m)*y;
				if(x>y){
					int r=abs(n-m)%2;
					sum+=(abs(n-m)-r)*y+r*x;
				}else{
					sum+=abs(n-m)*x;
				}
			}else{
				sum=(m+n)*x;
			}
		}
		
		printf("%lldn",sum);
	}
	return 0;
} 
 
生活大爆炸 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
题目描述 
有n个男孩和m个女孩参加戏剧俱乐部。要制作一部戏剧《生活大爆炸》，他们需要选择一组由t个演员组成的剧组，其中包括不少于4名男孩和不少于1名女孩。有多少种方法可以组成一个小组？当然，只有剧团组成不同的变体才被认为是不同的。
 
输入描述: 
 
一行包含三个整数n，m，t (4 ≤n≤30, 1 ≤m≤ 30, 5 ≤t≤n+m)(4 leq n leq 30, 1 leq m leq 30, 5 leq t leq n+m)(4 ≤n≤30, 1 ≤m≤ 30, 5 ≤t≤n+m).
 
输出描述: 
一行表示答案。
 
示例1
 
输入 
复制5 2 5
 
5 2 5
 
输出 
复制10
 
10
 
思路：本题就是求一个组合数乘积和，数据较小，我们可以先求出所有可能的组合数，再进行枚举求和即可
 
import java.util.Scanner;

public class Main {
	static long c[][]=new long[40][40];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(System.in);
		
		int n=cin.nextInt();
		int m=cin.nextInt();
		int t=cin.nextInt();
		
		init();
		
		long sum=0;
		for(int i=4;i<=n&&i 
Capslock 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
题目描述 
Caps lock是一种计算机键盘键。按此键可设置输入模式，默认情况下，键入的字母为大写。如果它是偶然按下的，它就会产生一些事故。
 
让我们考虑键入一个字符时Caps lock键意外打开的情况，如果：
 
1、它只包含大写字母；
 
2、除第一个字母外，所有字母都是大写的。
 
在这两种情况下，我们应该更改所有字母的大小写。例如，单词“hELLO”、“HTTP”、“z”的单词大小写应该改变。
 
编写一个应用上述规则的程序。如果无法应用规则，程序应保持单词不变。
 
输入描述: 
第一行包含一个由大写和小写字母组成的单词。单词的长度小于等于100。
 
输出描述: 
打印单词的处理结果。
 
示例1
 
输入 
复制cAPS
 
cAPS
 
输出 
复制Caps
 
Caps
 
示例2
 
输入 
复制Lap
 
Lap
 
输出 
复制Lap
 
Lap
 
思路：本题只用判断处第一位以外其他是否有小写字母，有则无需变换，没有就变换
 
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(System.in);
		String s=cin.next();
		char c[]=s.toCharArray();
		
		int flag=0;
		c[0]^=' ';
		for(int i=1;i='a'&&c[i]<='z') {
				flag=1;
				break;
			}
			c[i]^=' ';
		}
		
		if(flag==0)System.out.println(String.valueOf(c));
		else System.out.println(s);
	}

}
 
字节类型 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
题目描述 
阿强参加了一个编程大赛。他想要选用一个语言作为自己的主要编程语言。因为他喜欢非常大的数，所以他选用了java。它有一个非常大的整数数据类型，称为BigInteger。
 但是写了几道题后，Petya意识到并非所有任务都需要使用BigInteger类型。实际上有时候小范围的数更利于编程。这就是为什么会出现一个问题：“如果要存储正整数n，应该使用哪种整数类型？”
 阿强只知道5种整数类型：
 1） byte占用1个字节，允许存储来自 - 128至127
 2） short占用2个字节，允许存储来自的数字 - 32768至32767
 3） int占用4个字节，允许从中存储数字 - 2147483648至2147483647
 4） long占用8个字节，允许存储来自 - 9223372036854775808至9223372036854775807
 5） BigInteger可以存储任何整数，但它不是一个基元类型，使用它的操作要慢得多。
 对于上面给出的所有类型，边界值都包含在值范围内。
 从这个列表中，阿强想存储整数n,并且想选择占用字节数最小的类型。由于BigInteger的工作速度慢得多，阿强认为它是占用最多的一个。
 
输入描述: 
第一行包含一个正数n。它由不超过100位数字组成，不包含任何前导零。数字n不能表示为空字符串。
 
输出描述: 
 
一行包含一个字符串，字符串在"byte，short，int，long，BigInteger”中产生，表示能存储下n的占用字节数最小的类型
 
示例1
 
输入 
复制127
 
127
 
输出 
复制byte
 
byte
 
示例2
 
输入 
复制123456789101112131415161718192021222324
 
123456789101112131415161718192021222324
 
输出 
复制BigInteger
 
BigInteger
 
本题用python比较好写
 
Python:
 
n=eval(input())

if n >= -128 and n <= 127:
    print("byte")
elif n >=-32768 and n <=32767:
     print("short")
elif n >= -2147483648 and n <2147483647:
    print("int")
elif n >= -9223372036854775808 and n <=9223372036854775807:
    print("long")
else:
    print("BigInteger")

 
Java: 
 
import java.util.Scanner;

public class Main{
	static String ss[]= {"127","32767","2147483647","9223372036854775807"};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(System.in);
		
		String s=cin.next();
		if(s.length()<=3) {
			int t=Integer.valueOf(s);
			if(t>127)System.out.println("short");
			else System.out.println("byte");
		}else if(s.length()<=5) {
			int t=Integer.valueOf(s);
			if(t>32767)System.out.println("int");
			else System.out.println("short");
		}else if(s.length()<=10) {
			long t=Long.valueOf(s);
			if(t>2147483647)System.out.println("long");
			else System.out.println("int");
		}else if(s.length()<=19) {
			if(s.length()<19)System.out.println("long");
			else {
				if(s.compareTo(ss[3])<=0)System.out.println("long");
				else System.out.println("BigInteger");
			}
			
		}else System.out.println("BigInteger");
	}

}
 
完美主义 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
题目描述 
阿强采摘了一些苹果，并把他们分堆排成了一行，从左往右编号为第 1 … 푛 堆，其中第푖堆苹果有aia_iai​个。
 
完美主义者阿珍看到这些苹果，觉得他们摆放的非常杂乱。她要求阿强进行如下的操作。
 
对某堆苹果进行调整：阿强将会将第푖堆苹果调整成bib_ibi​个；
 
对阿珍询问做出答复：其中每次询问表示为[푙, 푟]，表示询问第푙堆到第푟堆之间的苹果数量是否满足al≤al+1≤⋯≤ar−1≤ara_l leq a_{l+1} leq dots leq a_{r-1} leq a_ral​≤al+1​≤⋯≤ar−1​≤ar​，如果满足则称为完美。
 
输入描述: 
 
第一行两个整数n, q (1≤n,q≤3∗105)(1 leq n, q leq 3*10^5)(1≤n,q≤3∗105)，表示苹果的堆数和操作的个数；
 
第二行n个整数表示aia_iai​。
 
以下푞行，每行3个整数，第一个整数为opt；
 
若opt = 1，之后两个整数i, bib_ibi​，表示将第푖堆苹果调整为bib_ibi​个；
 
若opt = 2，之后两个整数푙, 푟，表示对[푙, 푟]之间的苹果堆进行询问。
 
(1≤ai,bi≤109)(1 leq a_i,b_i leq 10^9)(1≤ai​,bi​≤109)
 
输出描述: 
输出一共푞行，每行一个 Yes 或者 No，表示每个询问对应区间是否完美。
 
示例1
 
输入 
复制7 4 1 2 2 4 3 4 5 1 1 4 2 1 7 2 6 7 2 4 7
 
7 4
1 2 2 4 3 4 5
1 1 4
2 1 7
2 6 7
2 4 7
 
输出 
复制No Yes No
 
No
Yes
No
 
本题数据比较水，暴力也能直接过hhh~重现赛的时候试了一下就过了，但是如果要严格的话，本题应该用到线段树+差分，我把我的暴力写法放出来吧，线段树还不太会，以后回来再补
 
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 q=cin.nextInt();
			long a[]=new long[n+1];
			
			for(int i=1;i<=n;i++)a[i]=cin.nextLong();
			
			while(q-->0) {
				int op=cin.nextInt();
				int l=cin.nextInt();
				int r=cin.nextInt();
				if(l<1)l=1;
				if(r>n)r=n;
				if(op==1)a[l]=r;
				else {
					
					int flag=0;
					for(int i=l+1;i<=r;i++) {
						if(a[i]