import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int N = 250;//最大矩阵3^5 < 250
char[][] num = new char[n][n];//模板
for (int i = 0; i < n; i++) {
num[i] = sc.next().toCharArray();
}
char[][] res = new char[N][N];
res[0][0] = '.';
char[][] temp = new char[N][N];
int s = 1;//矩阵大小，初始为1
for (int p = 0; p < k; p++) {
//扩展k次
for (int i = 0; i < s; i++) {
for (int j = 0; j < s; j++) {
for (int l = 0; l < n; l++) {
for (int r = 0; r < n; r++) {
char c = '*';
if (res[i][j] == '.') {
c = num[l][r];
}
temp[i * n + l][j * n + r] = c;
}
}
}
}
s *= n;
for (int i = 0; i < s; i++) {
System.arraycopy(temp[i], 0, res[i], 0, temp[i].length);
}
}
for (int i = 0; i < s; i++) {
for (int j = 0; j < s; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
int[] count;
int[] res = new int[n+1];
for (int i = 0; i < n; i++) {
int max = 0;
count = new int[n+1];
for (int j = i; j < n; j++) {//子数组
count[num[j]]++;
if (count[max] < count[num[j]] || (count[max] == count[num[j]] && max > num[j])) {
max = num[j];
}
res[max]++;
}
}
for (int i = 1; i <= n; i++) {
if (i != 1) {
System.out.print(" ");
}
System.out.print(res[i]);
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
int res = 0;
for (int i = 1; i < n - 1; i++) {
if ((num[i] > num[i-1] && num[i] > num[i+1]) || (num[i] < num[i-1] && num[i] < num[i+1])) {
res++;
}
}
System.out.println(res);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
/**
* 定义一个超级源点，超级源点连接每一个超市，距离为0，需求转变为求超级源点到每一个点的距离
* @author 86185
*
*/
public class Main{
//题目变量
static int n, m, a, b, c, k, x, q, y;
//树
static int[] target, length, ne, h;
static int index = 0;
static int[] dist;
static int N = 300010;
static boolean[] bool;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
//初始化数组
target = new int[N];
length = new int[N];
ne = new int[N];
h = new int[N];
dist = new int[N];
bool = new boolean[N];
Arrays.fill(h, -1);
Arrays.fill(dist, 0x3f3f3f3f);
dist[0] = 0;
for (int i = 0; i < m; i++) {
s = reader.readLine().split(" ");
a = Integer.parseInt(s[0]);
b = Integer.parseInt(s[1]);
c = Integer.parseInt(s[2]);
add(a, b, c);
add(b, a, c);
}
k = Integer.parseInt(reader.readLine());
for (int i = 0; i < k; i++) {
x = Integer.parseInt(reader.readLine());
add(0, x, 0);
}
SPFA();
q = Integer.parseInt(reader.readLine());
for (int i = 0; i < q; i++) {
y = Integer.parseInt(reader.readLine());
System.out.println(dist[y]);
}
}
private static void add(int a, int b, int c) {
// TODO Auto-generated method stub
target[index] = b;
length[index] = c;
ne[index] = h[a];
h[a] = index++;
}
private static void SPFA() {
// TODO Auto-generated method stub
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.offer(new Node(0, 0));
while (!queue.isEmpty()) {
Node node = queue.poll();
int distance = node.distance;
int ver = node.ver;
if (bool[ver]) {
continue;
}
bool[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int t = target[i];
if (dist[t] > distance + length[i]) {
dist[t] = distance + length[i];
queue.offer(new Node(dist[t], t));
}
}
}
}
}
class Node implements Comparable<Node>{
int distance;
int ver;
public Node(int distance, int ver) {
this.distance = distance;
this.ver = ver;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return this.distance - o.distance;
}
}
线段树
import java.util.Scanner;
public class Main {
static int n, m;
static int[] num;
static Tree[] tree;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
tree = new Tree[4*n];
for (int i = 0; i < 4*n; i++) {
tree[i] = new Tree();
}
build(1, 0, n - 1);
int l, r, d;
String[] s;
m = sc.nextInt();
sc.nextLine();
for (int i = 0; i < m; i++) {
s = sc.nextLine().split(" ");
l = Integer.parseInt(s[0]);
r = Integer.parseInt(s[1]);
if (s.length == 3) {
//增值操作
d = Integer.parseInt(s[2]);
if (l <= r) {
add(1, l, r, d);
}else {
add(1, l, n-1, d);
add(1, 0, r, d);
}
}else {
//求最小值操作
if (l <= r) {
System.out.println(query(1 ,l, r));
}else {
System.out.println(Math.min(query(1, l, n-1), query(1, 0, r)));
}
}
}
}
private static void build(int node, int left, int right) {
// TODO Auto-generated method stub
tree[node].l = left;
tree[node].r = right;
if (left == right){
tree[node].min = num[left];
return;
}
int mid = (left + right) >> 1;
build(node << 1, left, mid);
build(node << 1 | 1, mid + 1, right);//左移一位后，最后一位一定为0
pushup(node);
}
//修改只是进行上调
private static void pushup(int node) {
// TODO Auto-generated method stub
tree[node].min = Math.min(tree[node<<1].min, tree[node<<1|1].min);
}
private static void add(int node, int start, int end, int d) {
// TODO Auto-generated method stub
if (tree[node].l >= start && tree[node].r <= end) {
tree[node].min += d;
tree[node].lazy += d;
return;
}
pushdown(node);
int mid = (tree[node].l + tree[node].r) >> 1;
if (start <= mid) {
add(node << 1, start, end, d);
}
if (end > mid) {
add(node << 1 | 1, start, end, d);
}
pushup(node);
}
//获取值是进行下调
private static void pushdown(int node) {
// TODO Auto-generated method stub
Tree root = tree[node];
Tree left = tree[node<<1];
Tree right = tree[node<<1|1];
left.min += root.lazy;
left.lazy += root.lazy;
right.min += root.lazy;
right.lazy += root.lazy;
root.lazy = 0;
}
private static long query(int node, int start, int end) {
// TODO Auto-generated method stub
if (tree[node].l >= start && tree[node].r <= end){
return tree[node].min;
}
pushdown(node);
int mid = (tree[node].l + tree[node].r) >> 1;
long res = 0x3f3f3f3f;
if (start <= mid) {
res = Math.min(res, query(node << 1, start, end));
}
if (end > mid) {
res = Math.min(res, query(node << 1 | 1, start, end));
}
return res;
}
}
class Tree{
int l, r;
long min, lazy;
}
注意：末项为a
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int res = 0;
if (a % 2 == 0) {
res = (a - n) / -2 + 1;
}else {
res = (a - 1) / 2 + 1;
}
System.out.println(res);
}
}
注意数的位数，需要使用long类型
移位操作符也需要注意是long类型
二进制减法
(1111)2 - (100)2 = (1011)2
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
int length1 = Long.toBinaryString(a).length();
int length2 = Long.toBinaryString(b).length();
int count = 0;
for (int i = length1 - 1; i <= length2; i++) {
for (int j = 0; j <= i - 2; j++) {
long res = (1L << i) - 1 - (1L << j);//使用长整型数据L
if (res >= a && res <= b) {
count++;
}
}
}
System.out.println(count);
}
}
//注意时间，如果输出是使用String进行拼接会超时
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
int max = num[n-1];
int[] res = new int[n];
res[n-1] = 0;
for (int i = n-2; i >= 0; i--) {
if (num[i] > max) {
max = num[i];
res[i] = 0;
continue;
}
max = Math.max(max, num[i]);
res[i] = max - num[i] + 1;
}
for (int i = 0; i < n; i++) {
if (i != 0) {
System.out.print(" ");
}
System.out.print(res[i]);
}
}
}
