henhen敲

9330

henhen敲
8个月前

henhen敲
10个月前
卡特兰数 只不过需要在（1， 0） 和 （0， 1）处分别做一下
（n-m）/(m+n)

import java.util.Scanner;

class Main{

public static void main(String[] args) {
int m, n, t;
Scanner in = new Scanner(System.in);
t = in.nextInt();
int cnt = 1;
while(cnt<=t){
n = in.nextInt();
m = in.nextInt();
System.out.print("Case #"+ cnt++ +": ") ;
System.out.println(String.format("%.8f", (n-m)*1.0/(m+n)));
}
}
}


henhen敲
10个月前
取石子游戏不同玩法的解决方案


import java.util.*;
import java.io.*;

class Main{

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}

static Integer[] a;
static boolean[] st;
static int length, n, sum;
static void swap(int i,int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static void reverse()
{
int i = 0;
int j = n - 1;
while(i <= j)
{
swap(i,j);
i ++;
j --;
}
}
public static boolean DFS(int c, int cur, int start){
if(c*length==sum) return true;
if(cur==length) return DFS(c+1, 0, 0);
if(cur>length) return false;
for(int i=start; i<n; i++){
if(st[i]) continue;
st[i] = true;
if(DFS(c, cur+a[i], i+1)) return true;
st[i] = false;
if(cur==0) return false;
if(cur+a[i]==length) return false;
while(i<n-1&&a[i]==a[i+1]) i++;
}
return false;
}

public static void main(String[] args) throws Exception{
n = nextInt();
while(n!=0){
a = new Integer[n];
st = new boolean[n];
length = sum = 0;

for(int i=0; i<n; i++){
a[i] = nextInt();
length = Math.max(length, a[i]);
sum += a[i];
}
Arrays.sort(a);//这里用Arrays.sort(a,(o1, o2)->o2-o1;就会超时
reverse();
while(length<=sum){
if(sum%length==0&&DFS(0, 0, 0)) break;
length++;
}
out.println(length);
n = nextInt();
}
out.close();
}
}


henhen敲
10个月前
import java.io.*;

class Main{
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
public static void main(String[] args)throws Exception{
int n = nextInt();
int[][] g = new int[n][n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
g[i][j] = nextInt();
int[][] f = new int[1<<n][n];
for(int i=2; i<(1<<n); i++)
for(int j=0; j<n; j++)
if(((i>>j)&1)==1){
int m = i - (1<<j);
int min = 0x3f3f3f3f;
int t, k;
for(k=m, t=0; k!=0; k>>=1, t++)
if((k&1)==1)
min = Math.min(min, f[m][t]+g[t][j]);
f[i][j] = min;

}
int ans = 0x3f3f3f3f;
for(int i=1; i<n; i++)
ans = Math.min(ans, f[(1<<n)-1][i] + g[i][0]);
out.print(ans);
out.close();
}
}


henhen敲
10个月前
/**

* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

前序遍历

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> ans = new ArrayList<>();
while(root!=null||!stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop().right;
}
return ans;
}
}

中序遍历

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> ans = new ArrayList<>();
while(root!=null||!stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return ans;
}
}

后序遍历

class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> ans = new ArrayList<>();
HashMap<TreeNode, Integer> map = new HashMap<>();
while(root!=null||!stack.isEmpty()){
while(root!=null){
stack.push(root);
map.put(root, map.getOrDefault(root, 0)+1);
root = root.left;
}
root = stack.pop();
int flag = map.get(root);
if(flag<2){
stack.push(root);
map.put(root, map.getOrDefault(root, 0)+1);
root = root.right;
}
else{
root = null;
}
}
return ans;
}
}


henhen敲
10个月前
import java.io.*;

class Main{
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}

static boolean[] r, c, a45, a135;
static char[][] g;
static int n;

public static void DFS(int i, int j, int cnt){
if(i==n&&cnt==0){
for(int x=0; x<n; x++){
for(int y=0; y<n; y++)
out.print(g[x][y]);
out.println("");
}
out.println("");
return;
}
if(i==n) return;
g[i][j] = '.';
DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt);
if(!r[i]&&!c[j]&&!a45[j-i+n]&&!a135[i+j]){
r[i] = true;
c[j] = true;
a45[j-i+n] = true;
a135[j+i] = true;
g[i][j] = 'Q';
DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt-1);
r[i] = false;
c[j] = false;
a45[j-i+n] = false;
a135[j+i] = false;
}
}

public static void main(String[] args)throws Exception{
n = nextInt();
r = new boolean[n];
c = new boolean[n];
a45 = new boolean[2*n];
a135 = new boolean[2*n];
g = new char[n][n];
DFS(0, 0, n);
out.close();
}

}


henhen敲
11个月前
悬线法 通俗的讲 就是从矩阵中每一点发出一条射线 要么撞到障碍点 要么撞到矩阵边界 然后求出以该射线的长度


import java.io.*;
import java.util.*;

class Main{
static PrintWriter  out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt() throws Exception{
in.nextToken();
return (int)in.nval;
}
static String next()throws Exception{
in.nextToken();
return in.sval;
}

public static void main(String[] args) throws Exception{
int n, m;
n = nextInt(); m = nextInt();
int[][] g =new int[n][m];
int max = 0;
int[][] left, right, up;
left = new int[n][m];
right = new int[n][m];
up = new int[n][m];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
String t = next();
g[i][j] = t.equals("F")?1:0;
left[i][j] = j; right[i][j] = j;
up[i][j] = 1;
}

for(int i=0; i<n; i++)
for(int j=1; j<m; j++)
if(g[i][j]!=0&&g[i][j-1]!=0) left[i][j] = left[i][j-1];

for(int i=0; i<n; i++)
for(int j=m-2; j>=0; j--)
if(g[i][j]!=0&&g[i][j+1]!=0) right[i][j] = right[i][j+1];

for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(g[i][j]!=0){
int l, r;
l = left[i][j]; r = right[i][j];
if(i>0&&g[i-1][j]!=0){
up[i][j] = up[i-1][j] + 1;
l = Math.max(l, left[i-1][j]);
r = Math.min(r, right[i-1][j]);
}
left[i][j] = l;
right[i][j] = r;
max = Math.max((r-l+1)*up[i][j], max);
}

out.println(max*3);
out.close();
}
}


henhen敲
11个月前
import java.io.*;
import java.util.*;

class Main{
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
static int[] a, path;
static int n;

static void DFS(int d, int st){
if(d>=n){
for(int i=0; i<n; i++) out.print(path[i]+" ");
out.println("");
return;
}
for(int i=0; i<n; i++){
if(i>0&&((st>>(i-1))&1)==0&&a[i]==a[i-1]) continue;
if(((st>>i)&1)==0){
path[d] = a[i];
DFS(d+1, st+(1<<i));
}
}

}

public static void main(String[] args)throws Exception{
n = nextInt();
a = new int[n];
path = new int[n];
for(int i=0; i<n; i++) a[i] = nextInt();
Arrays.sort(a);
DFS(0, 0);
out.close();
}
}



henhen敲
11个月前
只考虑两组情况就行 然后依次迭代 a是有序的
a1, a2, a3,……, an;

b1, b2, b3,……, bn;

import java.io.*;
import java.util.*;

class Main{
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
static class Pair{
int first, second;
public Pair(int first, int second){
this.first = first;
this.second = second;
}
}

static int[] a, b, c;
static int n, m;

static void merge(){
PriorityQueue<Pair> heap = new PriorityQueue<>((o1, o2)->o1.second-o2.second);
for(int i=0; i<n; i++) heap.offer(new Pair(0, a[0]+b[i]));
for(int i=0; i<n; i++){
Pair e = heap.poll();
int f = e.first; int s = e.second;
c[i] = s;
if(f<n-1)heap.offer(new Pair(f+1, s - a[f] + a[f+1]));
}
for(int i=0; i<n; i++) a[i] = c[i];
}

public static void main(String[] args)throws Exception{
int T = nextInt();
while(T--!=0){
m = nextInt(); n = nextInt();
a = new int[n]; b = new int[n]; c = new int[n];
for(int i=0; i<n; i++)a[i] = nextInt();
Arrays.sort(a);
for(int i=0; i<m-1; i++){
for(int j=0; j<n; j++)b[j] = nextInt();
merge();
}
for(int i=0; i<n; i++) out.print(a[i]+" ");
out.println("");
}
out.close();
}
}



henhen敲
11个月前
import java.io.*;
import java.util.*;

class Main{

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt() throws Exception{
in.nextToken();
return (int)in.nval;
}

public static void main(String[] args)throws Exception{
int n = nextInt();
long[] a = new long[n];
long sum = 0;
for(int i=0; i<n; i++){
a[i] = nextInt();
sum += a[i];
}
long ave = sum / n;
a[n-1] = ave - a[n-1];
for(int i=n-2; i>0; i--)
a[i] = ave + a[i+1] - a[i];

a[0] = 0;
Arrays.sort(a);
long res = 0;
for(int i=0; i<n; i++) res += Math.abs(a[i] - a[n/2]);
out.print(res);
out.close();
}
}