xyw_6

free programing

194

fangshi
Kazimierz

xyw_6
1天前

# 八皇后问题

#include<iostream>
using namespace std;

const int N = 30;

int n , m ;
char g[N][N];
bool col[N] , dg[N] , udg[N];

void dfs(int u ){           //表示行;
if(u == n + 1){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
printf("%c", g[i][j]);
puts("");
}
puts("");
return ;
}
for(int i=1; i<=n; i++){            //列搜索;
if( !col[i] && !dg[u - i + n] && !udg[ i + u] ){        // u代表 y , i 代表 x . dg 斜线的b = u - i + n; udg 反斜线的 b = u + i;
col[i] = dg[u - i + n ] = udg[i + u] = true;
g[u][i] = 'Q';                    //  u = i + b;  --- > u - i = b ;         -- > u- i + n ;
dfs(u + 1);
col[i] =  dg[u - i + n ] = udg[i + u] = false;
g[u][i] = '.';
}
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
g[i][j] = '.';
dfs(1);
return 0;
}


xyw_6
1天前

# 排列数字

import java.util.Scanner;

public class Main {
static int N = (int) 10e4 + 10;
static int n ;
static boolean [] st = new boolean[N];
static int[] path = new int[N];
static Scanner s = new Scanner(System.in);
public static void main(String[] args) {
n = s.nextInt();
dfs(1);
}
static void dfs(int u){
if(u == n + 1){
for (int i = 1; i <=n ; i++) {
System.out.print(path[i]);
}
System.out.println();
}
for (int i = 1; i <=n ; i++) {
if(!st[i]){
st[i] = true;
path[u] = i;
dfs(u + 1);
st[i] = false;
}
}
}
}


### u 代表当前放的是第几个位置

if(!st[i]) 是判断这个数字是否

xyw_6
1天前

# 约数个数

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

public class Main {
static int N = (int) 10e4 + 10;
static int n;
static HashMap<Integer, Integer> primes = new HashMap<>();
static int[] a = new int[N];
static int mod = (int)1e9 + 7;
static Scanner s = new Scanner(System.in);

public static void main(String[] args) {
n = s.nextInt();
input(n);
long ans = 1;
for (Integer key : primes.keySet())
ans =(ans * (primes.get(key) + 1)) % mod;
System.out.println(ans );
}

public static void input(int n) {
while (n-- != 0) {
int x;
x = s.nextInt();
getDivisor(x);
}
}

public static void getDivisor(int x) {
for (int i = 2; i <= x / i; i++)
while (x % i == 0) {
x /= i;
setValue(i);
}
if( x > 1) setValue(x);
}
public static void setValue(int i ){
int p = primes.get(i) == null ? 0 : primes.get(i);
primes.put(i, p + 1);                   //  求出约数i 和 指数 p + 1;
}
}


for (int i = 2; i <= x / i; i++)
while (x % i == 0) {
x /= i;
setValue(i);
}
if( x > 1) setValue(x);
getDivisor 方法 是一个很重要的

N = p1^a1 * p2^a2 * p3^a3 * …… * pk ^ ak;

n那么一共有多少种组合呢？

for (Integer key : primes.keySet())
ans =(ans * (primes.get(key) + 1)) % mod;

xyw_6
2天前

# 快速排序

### 时间复杂度 O(nlogn)

#include<iostream>

using namespace std;

const int N = 1000010;

int n ,m;
int a[N];

void  sort(int l , int r){
if(l >= r) return ;

int tem = a[l + r >> 1 ] , i = l -1 , j = r + 1;
while(i < j ){
do i++ ; while(tem > a[i]);
do j-- ; while(tem < a[j]);
if(i < j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
sort(l, j);
sort(j + 1 , r);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++)     scanf("%d", a + i);
sort(1 , n);
for(int i=1; i<=n; i++) printf("%d ", a[i]);
return 0;
}


### 本质就是让基准数归位

保证基准数左区间严格小于等于基准数



xyw_6
2天前

# 约数个数

### 时间复杂度O(nsqrt(n))

import java.util.Scanner;
import java.util.Arrays;
public class Main {
static int  N = (int)10e4 + 10;
static int n ;
static Scanner s = new Scanner(System.in);
public static void main(String [] arsg) {
n = s.nextInt();
input(n);
}
public static void input(int n){
while(n -- != 0) {
int x ;
x = s.nextInt();
fun(x);
}
}
public static void fun(int n) {
int [] a = new int [N] ;
int cnt = 0;
for(int i= 1; i<= n / i; i++ ) {
if(n % i == 0) {
a[++cnt] = i;
if(i != n / i) a[++cnt] = n /i ;
}
}
Arrays.sort(a , 1, cnt + 1);
for(int i=1; i<=cnt; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}


### 这里最重要的方法是 fun() 方法

 枚举 1 到 sqrt(n) 之间所有的数;
原理还是利用较小的约数得到较大的约数
但是需要注意的是 因为约数是成对出现的
当 i = 根号下n 时 另外一个约数 也是 根号n
你得到的约数其实是一个 , 所以你需要单判;


xyw_6
2天前

# 线性筛

### 时间复杂度O(n)

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

public  class  Main {
static int N = (int) 10e7 + 10;
static int n, cnt ;
static int[] primes = new int[N];
static boolean[] st = new boolean[N];

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
n = s.nextInt();
isPrimes();
int [] a  = new int[N];
Arrays.sort(a , 1  , 3);
System.out.println(cnt);
}

static void isPrimes() {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[++cnt] = i;
for (int j = 1; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}

}


### 主要思路 筛出区间所有质数 , 直接查表; 所以是O(n)的时间复杂度;

 *  is_Primes 方法的核心思路就是利用较小的质数作为合数最小质因子筛掉 ,
* 将不是质数的合数作为下标直接映射到 boolean 数组中 , 所以质数都可以直接查表;
* 最关键的就是筛质数 , 重在分析循环 for(int i=1; primes[j] * i <= n; i++)
*判断部分也可以写成       *primes[j] <= n / i ;
* 其实意思是一样的 , 就是想要筛掉1 - n 直接所有的合数;
* 这个循环退出有两种可能
* 1、i % primes[j] != 0 时 那么 primes[j] 是 primes[j] * i
* 的最小质因数;
*      i % primes[j] == 0 是 primes[j] 是 i 的最小质因数 ,
* 也是 primes[j] * i 的最小质因数;
* 2、primes[j] <= n / i 这样保证了 primes[j]
*只会是属于 0 - n 之间的数; 因为 0 < primes[j] * i && primes[j] * i <= n;
* 这就是线性筛的基本思路.


### 以后质数题只用它！

xyw_6
2天前

import java.util.HashMap;
import java.util.Scanner;

public class Main {
static int N = 1000010;
static int n;
static Scanner s = new Scanner(System.in);

public static void main(String[] args) {
n = s.nextInt();
while (n-- != 0) {
int t = s.nextInt();
primesFactor(t);
}
}

static void primesFactor(int t) {
for (int i = 2; i <= t / i; i++)
while (t % i == 0) {
t /= i;
set( i , primes);
}
if (t > 1)
set(t , primes);
for (Integer key : primes.keySet())
System.out.println(key + " " + primes.get(key));
System.out.println();
}
public static  void set(int i , HashMap<Integer , Integer> primes){
int p = primes.get(i) == null ? 0  : primes.get(i);
primes.put(i , p + 1);
}
}


### 拿Java写算法一个字难受！

for (int i = 2; i <= t / i; i++)
while (t % i == 0) {
t /= i;
set( i , primes);
}

1 和任何数都能整除!

xyw_6
2天前

### 时间复杂度 O(n)

import java.util.Scanner;

public class Main{
static int N = 100010;
static int n , top , x;
static int [] st = new int[N];
static Scanner s = new Scanner(System.in);
public static void main(String [] args){
n = s.nextInt();
while(n -- != 0){
x = s.nextInt();
while(top != 0 && st[top] >= x) top --;
if(top > 0) System.out.print(st[top] +" ");
else System.out.print(-1 + " ");
st[++top] = x;
}
}
}


1、Ax >= Ay
2、x < y

xyw_6
3天前

### 时间复杂度

O(sqrt(n))  因为最多只要枚举到 sqrt(n) 所以 对于一个晒一个来说只需要sqrt(n);

import java.util.Scanner;

public class Main {
static int  n , m ;
static Scanner s = new Scanner(System.in);

public static void main(String[] args) {
n = s.nextInt();
while(n -- != 0){
m = s.nextInt();
boolean flag = true;
for (int i = 2; i <= m /i ; i++) {
if(m % i == 0 && (flag = false))
break;
}
if(flag && m != 1) System.out.println("Yes");
else System.out.println("No");
}
}
}


### 试除法 , 重点在于试除 Y总在为什么只要枚举到

    sqrt(n) 这个值应该已经说明的很清楚了, 唯一
要注意的一点的就是 1 这个数是不会被循环筛掉
的 , 所以一定要注意输出的时候单判一下.


xyw_6
5天前

#### 时间复杂度

O(n^2) 支持的数据范围大概是 10^4 左右;

#### C++ 代码


#include<iostream>

using namespace std;

const int N =  10010;

int n , m ,ans;
int dp[N] , v[N] , w[N];

int main(){
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)     scanf("%d%d",&v[i],&w[i]);

for(int i=1; i<=n; i++)         //  遍历物品
for(int j=1; j<=m; j++)     // 遍历容量;
if(j >= v[i])
dp[j] = max(dp[j-v[i]] + w[i] , dp[j]);
for(int i=1; i<=m; i++)
ans = max(dp[i] , ans);
cout << ans ;
return  0;
}