算法练习蓝桥
算法练习（蓝桥）
算法练习
1.
小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0,0)， 东南角坐标为 (W,0)， 西北角坐标为
(0,H)， 东北角坐标为 (W,H)。其中 W, H 都是整数。他在 n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 0 到 H，总共测试 (W+1)×(H+1) 个点。给定信号塔的位置，请问这 (W+1)×(H+1) 个点中有多少个点被信号覆盖。
因为都是整数，所以可以把坐标图看成W列H行的二维数组，利用a a+b b<=R的点在圆上，因为信号塔可能会重合，所以先将所有信号塔涉及到的数组位置值标记为1，最后遍历获取数组所有值的和，就是信号覆盖点
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int W = scan.nextInt();
int H = scan.nextInt();
int n = scan.nextInt();
int R = scan.nextInt();
int[][] arr = new int[W+1][H+1];
int count = 0;
for(int i = 0; i < n; i++){
int x = scan.nextInt();
int y = scan.nextInt();
for(int m = 0; m <= W; m++){
for(int j =0; j <= H; j++){
if((x-m)*(x-m)+(y-j)*(y-j)<=R*R){
arr[m][j] = 1;
}
}
}
}
for(int i = 0; i <= W; i++){
for(int j =0; j <= H; j++){
count += arr[i][j];
}
}
System.out.println(count);
}
}2.
给定一个长度为 NN 的数列，A1,A2,⋯ANA1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1,⋯AjAi,Ai+1,⋯Aj ( i≤ji≤j ) 之和是 KK 的倍数，我们就称这个区间 [i,j][i,j] 是 K 倍区间。
你能求出数列中总共有多少个 KK 倍区间吗？
这道题我看到的时候一开始想的是双重for循环把每个区间的和求出来然后进行判断再累计个数，但是这个方法耗时太大，只能通过两个案例，数量比较庞大的案例没法通过，所以看了一个大佬的解析：
①前缀和：是每一个都是前面累加的（第一个是0+第一个） ②前缀和%K==>可以找到K=0，它一定是K的倍数 ③理解一个东西：任意两个前缀和的差值就是一个区间 ④而前缀和的差值为0，也一定是K的倍数 ⑤（3，3，3，3）—>任意两个组合：（n*(n-1)/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();
long[] arr = new long[N+1];
int[] cnt = new int[100001];
long num = 0;
for(int i = 1; i <= N; i++){
int s = scan.nextInt();
arr[i] = arr[i-1] + s;
}
cnt[0] = 1;
for(int i = 1; i <= N; i++){
num += cnt[(int)(arr[i]%K)]++;
}
System.out.println(num);
}
}