十大免费行情软件网站下载百度搜索榜

3
1 1
1 3
5 8

1
4
8

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n+1];int[] b=new int[n+1];int[] c=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();}for(int j=1;j<=n;j++) {b[j]=scan.nextInt();}for(int k=1;k<=n;k++) {c[k]=scan.nextInt();}int sum=0;scan.close();for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {for(int k=1;k<=n;k++) {if(a[i]<b[j]&&b[j]<c[k]) {sum++;}}}}System.out.println(sum);}
}

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n+1];int[] b=new int[n+1];int[] c=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();}for(int j=1;j<=n;j++) {b[j]=scan.nextInt();}for(int k=1;k<=n;k++) {c[k]=scan.nextInt();}scan.close();int s=0;int[] ab=new int[n+1];int[] bc=new int[n+1];Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);for(int i=1;i<n+1;i++) {for(int j=1;j<n+1;j++) {if(b[i]>a[j]) {ab[i]++;}}}for(int i=1;i<n+1;i++) {//  int s=0;for(int j=1;j<n+1;j++) {if(b[i]<c[j]) {bc[i]++;}}}int sum=0;for(int i=1;i<n+1;i++) {sum+=ab[i]*bc[i];}System.out.println(sum);}
}

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int[] a=new int[n];int[] b=new int[n];int[] c=new int[n];for(int i=0;i<n;i++) {a[i]=scan.nextInt();}for(int j=0;j<n;j++) {b[j]=scan.nextInt();}for(int k=0;k<n;k++) {c[k]=scan.nextInt();}scan.close();Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);long sum=0;int p=0,q=0;for(int i=0;i<n;i++) {while(p<n&&a[p]<b[i]) {p++;}while(q<n&&c[q]<=b[i]) {q++;}sum+=((long)p*(n-q));}System.out.println(sum);}
}

2 10
6 5
5 6

2

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int k=scan.nextInt();int[] len=new int[n];int[] wid=new int[n];for(int i=0;i<n;i++) {len[i]=scan.nextInt();wid[i]=scan.nextInt();}scan.close();int l=1,r=100001,ans=0;while(l<=r) {int sum=0;int mid=(l+r)/2;for(int i=0;i<n;i++) {sum+=(len[i]/mid)*(wid[i]/mid);}if(sum>=k) {l=mid+1;ans=mid;}else {r=mid-1;}}System.out.println(ans);}
}

5
5 1 3 2 1 

25

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();long sum=0,h;PriorityQueue<Long> q=new PriorityQueue<Long>();for(int i=0;i<n;i++) {h=scan.nextLong();q.add(h);}scan.close();while(q.size()>1) {long a=q.peek();q.poll();if(q.peek()!=null) {long b=q.peek();q.poll();long c=a+b;sum+=c;q.add(c);}	}System.out.println(sum);}
}

答疑：

题目描述

有 n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：

1. 首先进入办公室，编号为 i的同学需要 si毫秒的时间。
2. 然后同学问问题老师解答，编号为 i的同学需要 aiai​ 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可 以忽略。
4. 最后同学收拾东西离开办公室，需要 ei毫秒的时间。一般需要 1000 秒、2000 秒或 3030 秒，即 ei 取值为 10000，20000 或 30000。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。

输入描述

输入第一行包含一个整数 n，表示同学的数量。

接下来 nn 行，描述每位同学的时间。其中第 i行包含三个整数 si, ai​, ei，意义如上所述。

其中有 ，1≤n≤1000，1≤si≤60000，1≤ai≤106，ei∈10000,20000,300001≤n≤1000，1≤si​≤60000，1≤ai​≤106，ei​∈10000,20000,30000，即 ei一定是 10000、20000、30000 之一。

输出描述

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

输入输出样例

示例

输入

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

输出

280000

运行限制

• 最大运行时间：3s
• 最大运行内存: 128M

文章问的是发消息时刻的和，当而不是发消息的时间，注意审题

 

import java.util.*;
//class C{
//	long a;
//	long b;
//	public C(long a,long b) {
//		this.a=a;
//		this.b=b;
//	}
//}
public class 答疑 {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int[][] a=new int[n][2];for(int i=0;i<n;i++) {int s=scan.nextInt();int b=scan.nextInt();a[i][1]=scan.nextInt();a[i][0]=s+b;}Arrays.sort(a,(b,c) -> b[0]+b[1]-c[0]-c[1]);long sum=0;for(int i=0;i<n;i++) {sum+=(long)a[i][0]*(n-i)+a[i][1]*(n-i-1);}System.out.println(sum);}
}

美丽的区间：

题目描述

给定一个长度为 nn 的序列 a1,a2,⋯ ,ana1​,a2​,⋯,an​ 和一个常数 SS。

对于一个连续区间如果它的区间和大于或等于 SS，则称它为美丽的区间。

对于一个美丽的区间，如果其区间长度越短，它就越美丽。

请你从序列中找出最美丽的区间​。

输入描述

第一行包含两个整数 n,Sn,S，其含义如题所述。

接下来一行包含 nn 个整数，分别表示 a1,a2,⋯ ,ana1​,a2​,⋯,an​。

10≤N≤10510≤N≤105，1×ai≤1041×ai​≤104，1≤S≤1081≤S≤108。

输出描述

输出共一行，包含一个整数，表示最美丽的区间的长度。

若不存在任何美丽的区间，则输出 00。

输入输出样例

示例 1

输入

5 6
1 2 3 4 5

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

尺取法：http://t.csdn.cn/q7Yqs

import java.util.*;
public class 最美的区间 {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];int s=scan.nextInt();for(int i=0;i<n;i++) {a[i]=scan.nextInt();}int l=0,r=0,sum=0,len=n+1;for(;r<n;r++) {sum+=a[r];while(l<=r&&sum>=s) {if(len>r-l+1) {len=r-l+1;}sum-=a[l];l++;}}if(len==n+1) {len=0;}System.out.println(len);}
}

杨辉三角形：

题目描述

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯

给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？

输入描述

输入一个整数 NN。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 2020​​ 的评测用例，1≤N≤101≤N≤10​； 对于所有评测用例，1≤N≤10000000001≤N≤1000000000。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

 该列起始的数    行数=列数*2

import java.util.*;
public class 杨辉三角形 {public static int n;public static long f(long a,long b) {	//通过数学排列公式计算出该处杨辉三角形的值long res=1;for(long i=a,j=1;j<=b;i--,j++) {res=res*i/j;if(res>n) {return res;}}return res;}public static void main(String[] args) {Scanner scan=new Scanner(System.in);n=scan.nextInt();scan.close();for(int k=16;k>=0;k--) {	//从第16列开始循环，每次循环列数减1int l=2*k;				//二分的左边界和右边界int r=n;while(l<=r) {int mid=(l+r)/2;long rr=f(mid,k);	//通过函数获取得到mid行k列的杨辉三角形的值为多少if(rr>n) {	r=mid-1;}else if(rr<n){l=mid+1;}else {				//rr等于n,将二维坐标转化为一维输出System.out.println((long)(mid+1)*mid/2+k+1);return;}}}}
}

谈判：

题目描述

在很久很久以前，有 nn 个部落居住在平原上，依次编号为 11 到 nn。第 ii 个部落的人数为 titi​。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

输入描述

输入的第一行包含一个整数 nn，表示部落的数量。

第二行包含 nn 个正整数，依次表示每个部落的人数。

其中，1≤n≤1000，1≤ti≤1041≤n≤1000，1≤ti​≤104。

输出描述

输出一个整数，表示最小花费。

输入输出样例

示例 1

输入

4
9 1 3 5

输出

31

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();PriorityQueue<Long> q=new PriorityQueue<Long>(); for(int i=0;i<n;i++) {long b=scan.nextLong();q.add(b);}scan.close();long sum=0,k=0;while(q.size()>0) {long c=q.peek();q.poll();if(q.peek()!=null) {long d=q.peek();q.poll();k=c+d;sum+=k;q.add(k);}}System.out.println(sum);}
}

一元三次方程求解：

题目描述

有形如：ax3+bx2+cx+d=0ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，da，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在 −100−100 至 100100 之间)，且根与根之差的绝对值 ≥1≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 22 位。

提示：记方程 f(x)=0f(x)=0，若存在 22 个数 x1x1​ 和 x2x2​，且x1<x2x1​<x2​，f(x1)×f(x2)<0f(x1​)×f(x2​)<0，则在 (x1，x2)(x1​，x2​)之间一定有一个根。

输入描述

输入一行，44 个实数 a,b,c,da,b,c,d。

输出描述

输出一行，33 个实根，从小到大输出，并精确到小数点后 22 位。

输入输出样例

示例 1

输入

1 -5 -4 20

输出

-2.00 2.00 5.00

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.*;
public class 一元三次方程求解 {static double a;static double b;static double c;static double d;public static double f(double x) {			//带入x求方程的值double v=Math.pow(x, 3)*a+Math.pow(x,2)*b+x*c+d;return v;}public static double find(double l,double r) {		//找到区间内的解double mid=(l+r)/2;while(r-l>0.001) {if(f(mid)==0) {return mid;}else if(f(mid)*f(l)<0) {r=mid;}else {l=mid;}mid=(l+r)/2;}return mid;}public static void main(String[] args) {Scanner scan=new Scanner(System.in);a=scan.nextDouble();b=scan.nextDouble();c=scan.nextDouble();d=scan.nextDouble();scan.close();int flag=0;for(double s=-100;s<=100&&flag!=3;s++) {if(f(s)==0) {flag++;System.out.printf(String.format("%.2f",s)+" ");}if(f(s)*f(s+1)<0) {System.out.printf(String.format("%.2f", find(s,s+1))+" ");}}}
}

删除字符：

题目描述

给定一个单词，请问在单词中删除 tt 个字母后，能得到的字典序最小的单词是什么？

输入描述

输入的第一行包含一个单词，由大写英文字母组成。

第二行包含一个正整数 tt。

其中，单词长度不超过 100100，tt 小于单词长度。

输出描述

输出一个单词，表示答案。

输入输出样例

示例 1

输入

LANQIAO
3

输出

AIAO

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

首先要知道什么是字典序，顾名思义，查字典的序列，要保证序最小，如果前面比后面大，则删除前面的，如果后面的大则删除后面的

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);String str=scan.nextLine();int n=scan.nextInt();scan.close();StringBuffer s=new StringBuffer(str);while(n>0) {if(s.charAt(0)>=s.charAt(1)) {s.deleteCharAt(0);n--;}else {s.deleteCharAt(1);n--;}}System.out.println(s);}
}

付账问题：

题目描述

几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。

现在有 nn 个人出去吃饭，他们总共消费了 SS 元。其中第 ii 个人带了 aiai​元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 SS 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的"偏差有多大"。形式化地说，设第 ii 个人付的钱为 bibi​ 元，那么标准差为 :

S=1n∑i=1n(bi−1n∑i=1nbi)2S=n1​∑i=1n​(bi​−n1​∑i=1n​bi​)2

输入描述

第一行包含两个整数 n、Sn、S；

第二行包含 nn 个非负整数 a1, ⋯ , ana1​, ⋯, an​。

其中，n≤5×105,0≤ai≤109n≤5×105,0≤ai​≤109 。

输出描述

输出最小的标准差，四舍五入保留 4 位小数。

保证正确答案在加上或减去 10−910−9 后不会导致四舍五入的结果发生变化。

输入输出样例

示例

输入

5 2333
666 666 666 666 666

输出

0.0000

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

只通过了百分之八十，剩下的超时，实在没想到好的想法

import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();long s=scan.nextLong();long[] a=new long[n];for(int i=0;i<n;i++) {a[i]=scan.nextInt();}scan.close();Arrays.sort(a);double ans = 0,avg;avg=1.0*s/n;		//总的平均值for(int i=0;i<n;i++) {double avgg=1.0*s/(n-i);	//算出当前的平均值，即为每个人应该付的钱数if(a[i]<avgg) {        //第i个钱的多少*当前人数<当前的总额，即第i个钱小于当前的平均值ans+=(a[i]-avg)*(a[i]-avg);        //小于当前平均值，则这个钱全部付掉，累加到方差s-=a[i];                //第i个钱全部付出，还需要再付的总钱数，递推后i+1到n个数，直到不用将钱都付掉}else {                    //当前的钱数超过平均值ans+=(avg-avgg)*(avg-avgg)*(n-i);                //（平均付的钱数-平均应该钱数）的平方 后n-i个人累加到方差break;}}System.out.printf("%.4f\n",Math.sqrt(ans/n));}
}

最大子矩阵：

问题描述

小明有一个大小为 N×MN×M 的矩阵, 可以理解为一个 NN 行 MM 列的二维数组。

我们定义一个矩阵 mm 的稳定度 f(m)f(m) 为 f(m)=max⁡(m)−min⁡(m)f(m)=max(m)−min(m), 其中 max⁡(m)max(m) 表示矩阵 mm 中的最大值, min⁡(m)min(m) 表示矩阵 mm 中的最小值。

现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵, 同时他还希望这个子矩阵的面积越大越好 (面积可以理解为矩阵中元素个数)。

子矩阵定义如下: 从原矩阵中选择一组连续的行和一组连续的列, 这些行列交点上的元素组成的矩阵即为一个子矩阵。

输入格式

第一行输入两个整数 N,MN,M, 表示矩阵的大小。

接下来 NN 行, 侮行输入 MM 个整数，表示这个矩阵。

最后一行输入一个整数 limit, 表示限制。

辎出格式

输出一个整数. 分别表示小明选择的子矩阵的最大面积。

样例输入

3 4
2 0 7 9
0 6 9 7
8 4 6 4
8

样例输出

6

样例说明

满足稳定度不大于 8 的且面积最大的子矩阵总共有三个, 他们的面积都是 6 (粗体表示子矩阵元素)

2 0 7 9

0 6 9 7

8 4 6 4

2 0 7 9

0 6 9 7

8 4 6 4

2 0 7 9

0 6 9 7

8 4 6 4

评测用例规模与约定

对于所有评测用例, 0≤0≤ 矩阵元素值, limit ≤105≤105 。

运行限制

• 最大运行时间：5s
• 最大运行内存: 512M

翻硬币：

题目描述

小明正在玩一个"翻硬币"的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo;

如果同时翻转左边的两个硬币，则变为：oooo***oooo。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入描述

两行等长的字符串，分别表示初始状态和要达到的目标状态。

每行的长度<1000。

输出描述

一个整数，表示最小操作步数。

输入输出样例

示例

输入

**********
o****o****

输出

5

运行限制

• 最大运行时间：1s
• 最大运行内存: 64M

import java.util.*;
public class  翻硬币  {public static void main(String[] args) {Scanner scan=new Scanner(System.in);String str1=scan.nextLine();String str2=scan.nextLine();scan.close();char[] a=new char[str2.length()];a=str1.toCharArray();char[] b=new char[str2.length()];b=str2.toCharArray();int sum=0;for(int i=0;i<str1.length()-1;i++) {if(a[i]!=b[i]) {a[i]=b[i];if(a[i+1]=='o') {a[i+1]='*';}else {a[i+1]='o';}sum++;}}System.out.println(sum);}}

卡牌：

问题描述

这天, 小明在整理他的卡牌。

他一共有 nn 种卡牌, 第 ii 种卡牌上印有正整数数 i(i∈[1,n])i(i∈[1,n]), 且第 ii 种卡牌 现有 aiai​ 张。

而如果有 nn 张卡牌, 其中每种卡牌各一张, 那么这 nn 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 mm 张空白牌, 他可以在上面写上数 ii, 将其当做第 ii 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bibi​ 张。

请问小明最多能凑出多少套牌?

输入格式

输入共 3 行, 第一行为两个正整数 n,mn,m 。

第二行为 nn 个正整数 a1,a2,…,ana1​,a2​,…,an​ 。

第三行为 nn 个正整数 b1,b2,…,bnb1​,b2​,…,bn​ 。

输出格式

一行, 一个整数表示答案。

样例输入

4 5
1 2 3 4
5 5 5 5

样例输出

3

样例说明

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,43,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定

对于 30%30% 的数据, 保证 n≤2000n≤2000;

对于 100%100% 的数据, 保证 n≤2×105;ai,bi≤2n;m≤n2n≤2×105;ai​,bi​≤2n;m≤n2 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

http://t.csdn.cn/5OsEz

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();long m=scan.nextLong();int[][] a=new int[n][2];for(int i=0;i<n;i++) {a[i][0]=scan.nextInt();}for(int i=0;i<n;i++) {a[i][1]=scan.nextInt();}scan.close();Arrays.sort(a,Comparator.comparingInt(b->b[0]));long k=m;while(a[0][1]>0&&m>0) {int d=a[0][0];int c=a[0][1];a[0][0]++;a[0][1]--;m--;Arrays.sort(a,Comparator.comparingInt(b->b[0]));//if(d==a[0][0]&&c==a[0][1]) {//    break;//}}System.out.println(a[0][0]);}
}

但是上述方法中，时间复杂度为N^N^logN,已经远远超过十的八次方了

没AC，，，看看佬们的代码

import java.util.*;
import java.io.*;public class Main {static final int N = (int) 2e5 + 10;static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static final PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int[] a = new int[N], b = new int[N];static int n;static long m;static boolean check(int mid) {long tm = m;//模拟分配for (int i = 1; i <= n; i++) {if (mid > a[i] && b[i] >= mid - a[i]) {tm -= mid - a[i];} else if (mid > a[i] && b[i] < mid - a[i]) return false;//牌不够使用了if (tm < 0) return false;}return true;}public static void main(String[] args) throws IOException {String[] ss = br.readLine().trim().split(" ");n = Integer.parseInt(ss[0]);m = Long.parseLong(ss[1]);ss = br.readLine().trim().split(" ");for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(ss[i - 1]);ss = br.readLine().trim().split(" ");for (int i = 1; i <= n; i++) b[i] = Integer.parseInt(ss[i - 1]);int minh = a[1] + b[1];for (int i = 2; i <= n; i++) minh = Math.min(minh, a[i] + b[i]);//二分牌的套数int l = 0, r = minh;while (l < r) {int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}out.println(l);out.close();}
}

统计字符串：

题目描述

如果一个字符串 SS 恰好可以由某个字符串重复 KK 次得到，我们就称 SS 是 KK 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 33 次得到，所以 abcabcabc 是 33 次重复字符串。

同理 aaaaaa 既是 22 次重复字符串、又是 33 次重复字符串和 66 次重复字符串。

现在给定一个字符串 SS，请你计算最少要修改其中几个字符，可以使 SS 变为一个 KK 次字符串？

输入描述

输入第一行包含一个整数 KK。

第二行包含一个只含小写字母的字符串 SS。

其中，1≤K≤105,1≤∣S∣≤1051≤K≤105,1≤∣S∣≤105。其中 ∣S∣∣S∣ 表示 SS 的 长度。

输出描述

输出一个整数代表答案。如果 SS 无法修改成 KK 次重复字符串，输出 −1−1。

输入输出样例

示例 1

输入

2
aabbaa

输出

2

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

统计子矩阵：

问题描述

给定一个 N×MN×M 的矩阵 AA, 请你统计有多少个子矩阵 (最小 1×11×1, 最大 N×M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK ?

输入格式

第一行包含三个整数 N,MN,M 和 KK.

之后 NN 行每行包含 MM 个整数, 代表矩阵 AA.

输出格式

一个整数代表答案。

样例输入

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

样例输出

19

样例说明

满足条件的子矩阵一共有 19 , 包含:

大小为 1×11×1 的有 10 个。

大小为 1×21×2 的有 3 个。

大小为 1×31×3 的有 2 个。

大小为 1×41×4 的有 1 个。

大小为 2×12×1 的有 3 个。

评测用例规模与约定

对于 30%30% 的数据, N,M≤20N,M≤20.

对于 70%70% 的数据, N,M≤100N,M≤100.

对于 100%100% 的数据, 1≤N,M≤500;0≤Aij≤1000;1≤K≤2500000001≤N,M≤500;0≤Aij​≤1000;1≤K≤250000000.

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

 

import java.util.*;
public class 统计子矩阵 {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int k=scan.nextInt();int[][] a=new int[n+1][m+1];int[][] s=new int[n+1][m+1];for(int i=1;i<n+1;i++) {for(int j=1;j<m+1;j++) {a[i][j]=scan.nextInt();s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];			//求二维数组前缀和}}scan.close();long sum=0;for(int li=1;li<=n;li++) {for(int ri=li;ri<=n;ri++) {for(int lj=1;lj<=m;lj++) {for(int rj=lj;rj<=m;rj++) {if(li>=1&&lj>=1) {if(s[ri][rj]-s[ri][lj-1]-s[li-1][rj]+s[li-1][lj-1]<=k) {sum++;}	}}}}}System.out.println(sum);}
}

时间复杂度为N^4

 

 

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int k=scan.nextInt();int[][] a=new int[n+1][m+1];for(int i=1;i<n+1;i++) {			//预处理每一列的前缀和for(int j=1;j<m+1;j++) {a[i][j]=scan.nextInt();a[i][j]+=a[i-1][j];			}}scan.close();long ans=0;for(int i=1;i<n+1;i++) {						//控制的是从第几行开始for(int j=i;j<n+1;j++) {					//控制的是到第几行//从第i行到j行，每一列看做一个数字a[j][1:m]-a[i-1][1:m]for(int l=1,r=1,sum=0;r<=m;r++) {		//控制的是列，以双指针作为控制条件sum+=a[j][r]-a[i-1][r];while(sum>k) {sum-=a[j][l]-a[i-1][l];l++;}ans+=r-l+1;}}}System.out.println(ans);}
}

但是Java的输入是有劣势的，和上一题一样，输入过于占用时间，仍有三个未通过，来看一下大佬的代码：

import java.io.*;
import java.util.*;public class Main {static int N = 510;static long a[][] = new long[N][N];static int n, m;static long k;public static boolean check(int x1, int y1, int x2, int y2){long t = a[x2][y2] - a[x2][y1-1] - a[x1-1][y2] + a[x1-1][y1-1];return t <= k;}public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));StreamTokenizer stmInput = new StreamTokenizer(br);stmInput.nextToken();n = (int)stmInput.nval;stmInput.nextToken();m = (int)stmInput.nval;stmInput.nextToken();k = (long)stmInput.nval;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {stmInput.nextToken();a[i][j] = (long)stmInput.nval;a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; }}long ans = 0;for(int x1 = 1; x1 <= n; x1++) {for(int x2 = x1; x2 <= n; x2++) {// 固定行后，枚举列for(int y2 = 1, y1 = 1; y2 <= m; y2++){while(y1 <= y2 && !check(x1, y1, x2, y2)){y1++; // 使得在列y1和y2之间的子矩阵都满足要求}ans += y2 - y1 + 1; // 累加子矩阵的个数}}}bw.write(ans + "\n");bw.flush();bw.close();br.close();}
}