mushan_xiong

751

rerere

mushan_xiong
18小时前

## Java

import java.util.Arrays;
import java.util.Scanner;

/**
* Created by IntelliJ IDEA.
* User: zm
* Date: 2023/5/30
*/
public class Main {
static int N = 510,n,m,max = 0x3f3f3f;
static int[][] g = new int[N][N];//存放两点之间的距离
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
public static int dijkstra(){
Arrays.fill(dist,max);
dist[1] = 0;
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 1; j <= n; j++){
if(!st[j] && (t == -1 || dist[j] < dist[t])){
t = j;
}
}
st[t] = true;
for(int j = 1; j <= n; j++){
dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
}
}
if(dist[n] == max)return -1;
else return dist[n];
}

public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1; i <= n; i++) Arrays.fill(g[i],max);

while(m -- > 0){
int a = scan.nextInt();
int b = scan.nextInt();
int c = scan.nextInt();
g[a][b] = Math.min(g[a][b],c);//这个因为可能存在重边，所以泽出最短的
}
int res = dijkstra();
System.out.println(res);
}
}



## Java

import java.util.Scanner;
public class Main{
static int N = 100010,n,m,hh,tt,idx;
static int[] e = new int[N],ne = new int[N],h = new int[N];
static int[] q = new int[N];
static int[] d = new int[N];
public static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static boolean bfs(){
hh = 0; tt = -1;
for(int i = 1; i <= n; i++){
if(d[i] == 0){
q[++tt] = i;
}
}
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i]){
int s = e[i];
d[s] --;
if(d[s] == 0){
q[++tt] = s;
}
}
}
return tt == n - 1;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0; i < N; i++){
h[i] = -1;
}
while(m -- > 0){
int a = scan.nextInt();
int b = scan.nextInt();
d[b]++;
}
if(bfs()){
for(int i = 0; i < n; i++){
System.out.print(q[i] + " ");
}
}else{
System.out.println("-1");
}
}
}


## Java

import java.util.Scanner;
public class Main{
static int N = 100010,n,m,hh,tt,idx;
static int[] e = new int[N],ne = new int[N],h = new int[N];
static int[] d = new int[N],q = new int[N];
public static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static int bfs(){
hh = 0; tt = -1;
d[1] = 0;
q[++tt] = 1;
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; i!= -1; i = ne[i]){
int s = e[i];
if(d[s] == -1){
d[s] = d[t] + 1;
q[++tt] = s;
}
}
}
return d[n];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0; i < N; i++){
d[i] = -1;
h[i] = -1;
}
for(int i = 0; i < m; i++){
int a = scan.nextInt();
int b = scan.nextInt();
}
System.out.println(bfs());
}
}


## Java

import java.util.*;
public class Demo42 {
static int N = 100010,M = N * 2,idx,n;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static boolean[] st = new boolean[N];
static int ans = N;
public static void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static int dfs(int u){
int res = 0;
st[u] = true;
int sum = 1;
for(int i = h[u];i != -1 ; i = ne[i]){
int j = e[i];
if(!st[j]){
int s = dfs(j);
res = Math.max(res,s);
sum += s;
}
}
res = Math.max(res,n-sum);;
ans = Math.min(res,ans);
return sum;
}
public static void main(String[] ags){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1 ; i < N ; i++ ){
h[i] = -1;
}

for(int i = 0 ; i < n - 1 ; i ++){
int a = scan.nextInt();
int b = scan.nextInt();
}
dfs(1);
System.out.println(ans);
}
}



## Java

import java.util.Scanner;

/**
* Created by IntelliJ IDEA.
* User: zm
* Date: 2023/5/26
*/
public class Main {
static int N = 2010,n,m = 1000000007;
static int[][] c = new int[N][N];

public static void init() {
for (int i = 0; i < N; i++)
for (int j = 0; j <= i ; j++)
if(j == 0)c[i][j] = 1;
else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
init();
while(n -- > 0){
int a = scan.nextInt();
int b = scan.nextInt();
System.out.println(c[a][b]);
}
}
}



## C++

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
scanf("%d%d%s", &n, &m, str + 1);

p[0] = 1;
for(int i = 1; i <= n; i ++)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}

while(m --)
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

if(get(l1, r1) == get(l2, r2))  puts("Yes");
else                            puts("No");
}
return 0;
}


## Java

import java.util.Scanner;
public class Main{
static int N = 100010,P = 131;
static long[] h = new long[N];
static long[] p = new long[N];
public static long get(int l , int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
String s = scan.next();
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s.charAt(i - 1);
}
while(m -- > 0 ){
int l1 = scan.nextInt();
int r1 = scan.nextInt();
int l2 = scan.nextInt();
int r2 = scan.nextInt();
if(get(l1,r1) == get(l2,r2)) System.out.println("Yes");
else System.out.println("No");
}
}
}


## Java

import java.util.Scanner;
public class Main{
static int N = 100003,idx;
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] h = new int[N];
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
static void find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x){
System.out.println("Yes");
return;
}
}
System.out.println("No");
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
idx = 0;
for(int i = 0; i < N; i++)h[i] = -1;
while(n -- > 0){
String s = scan.next();
int a = scan.nextInt();
if(s.equals("I")){
}else{
find(a);
}
}
}
}


## C++

### 拉链法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100003;
int h[N], e[N], ne[N], idx;

void insert(int x)
{
int k = (x % N + N) % N;

e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

bool find(int x)
{
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
if(e[i] == x)
return true;

return false;
}

int main()
{
int n;
memset(h, -1, sizeof h);
scanf("%d", &n);
while(n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
if(op[0] == 'I')    insert(x);
else
{
if(find(x)) puts("Yes");
else        puts("No");
}
}
return 0;
}


### 开放寻址法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
int h[N];

int find(int x)
{
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x)
{
k ++;
if(k == N) k = 0;
}
return k;
}

int main()
{
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while(n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);
if(op[0] == 'I')    h[k] = x;
else
{
if(h[k] != null)    puts("Yes");
else                puts("No");
}
}
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int h[N], cnt, ph[N], hp[N];

void heap_swap(int a,int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t])            t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])    t = u * 2 + 1;
if (t != u)
{
heap_swap(t, u);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u / 2] > h[u])
{
heap_swap(u, u / 2);
u /= 2;
}
}

int main()
{
int n, m = 0;
scanf("%d", &n);
while (n--)
{
int k, x;
char op[10];
scanf("%s", op);
if (op[0] == 'I')
{
scanf("%d", &x);
m++, cnt++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, cnt --);
down(1);
}
else if (op[0] == 'D')
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt --);
down(k), up(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}


## Java

import java.util.*;
import java.io.*;
public class Main{
public static int qmi(int a, int k, int q){
int res = 1;
while(k != 0){
if((k & 1) == 1) res = (int)((long)res * a % q);
k >>= 1;
a = (int)((long)a * a % q);
}
return res;
}
public static void main(String[] args)throws IOException{
while(n -- > 0){
int a = Integer.parseInt(st[0]);
int k = Integer.parseInt(st[1]);
int q = Integer.parseInt(st[2]);

System.out.println(qmi(a,k,q));
}
}
}


## Java

import java.io.BufferedReader;
import java.io.IOException;
public class Main {
static int  N = 50010;
static int  n, m;
static int[] p = new int[N];
static int[] d = new int[N];
public static void main(String[] args)throws IOException {
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
for(int i =0 ; i < n; i++)p[i] = i;
int res = 0;
while(m -- > 0){
int t = Integer.parseInt(strs[0]);
int x = Integer.parseInt(strs[1]);
int y = Integer.parseInt(strs[2]);
if(x > n || y > n)res++;
else{
int px = find(x),py = find(y);
if(t == 1) {
if (px == py && (d[x] - d[y]) % 3 != 0) res++;
else if (px != py) {
p[px] = py;
d[px] = d[y] - d[x];
}
}else{
if(px == py && (d[x] - d[y] - 1) % 3 != 0)res++;
else if(px != py){
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
System.out.println(res);
}
static int find(int x){
if(p[x] != x){
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
}



## c++

#include <iostream>

using namespace std;

const int N = 50010;
int n, m;
int p[N], d[N];

int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}

int main()
{
scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i ++)  p[i]= i;

int res = 0;
while(m --)
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);

if(x > n || y > n)  res ++;
else
{
int px = find(x), py = find(y);
if(t == 1)
{
if(px == py && (d[x] - d[y]) % 3)   res ++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if(px == py && (d[x] - d[y] - 1) % 3)   res ++;
else if(px != py)
{
p[px] = p[y];
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d", res);
return 0;
}