首页 > 编程语言 > 详细

分治算法

时间:2020-02-05 11:07:48      阅读:56      评论:0      收藏:0      [点我收藏+]

p1226 【模板】快速幂||取余运算

模板题 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int (int b,int q,int k)
{
int ans=1,base=b;
while(q) {
if(q&1) ans=1ll*ans*base%k;
base=1ll*base*base%k;
q>>=1;
}
return ans%k;
}
int main()
{
int b,q,k;
scanf("%d%d%d",&b,&q,&k);
printf("%d^%d mod %d=%dn",b,q,k,q_pow(b,q,k));
}

p1010 幂次方

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
void solve(int n)
{
int temp=n,a[50],len=0;
while(temp) {
a[len++]=temp%2;
temp/=2;
}
int flag=0;
for(int i=len-1;i>=0;i--) {
if(a[i]==1&&flag==0) {
flag=1;
}
else if(a[i]==1&&flag==1) {
printf("+");
}
if(a[i]==1) {
if(i==0) {
printf("2(0)");
}
else if(i==1) {
printf("2");
}
else if(i==2) {
printf("2(2)");
}
else {
printf("2(");
solve(i);
printf(")");
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
solve(n);
printf("n");
}

P1908 逆序对

写这一个,也会了归并排序 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
大专栏  分治算法="line">37
38
39
40
41
42
43
44

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e5+7;
int a[maxn],p[maxn],n;
long long ans=0;
void msort(int s,int t)
{
if(s>=t) return ;
int mid=s+t>>1;
msort(s,mid);
msort(mid+1,t);
int i=s,j=mid+1,k=0;
while(i<=mid&&j<=t) {
if(a[i]>a[j]) {
p[k++]=a[j++];
ans+=(mid-i+1);
}
else{
p[k++]=a[i++];
}
}
while(i<=mid) {
p[k++]=a[i++];
}
while(j<=t) {
p[k++]=a[j++];
}
for(int i=0;i<k;i++) {
a[s+i]=p[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
msort(1,n);
printf("%lldn",ans);

}

P1498 南蛮图腾

分治画图 不过要提前弄为’ ‘; null和空并不一样 php也学过 还有一点就是转义字符 ‘‘;
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2000][5000];
void dfs(int n,int x,int y,int c,int k)
{
if(n==1) {
s[x][y]='/';
s[x][y+1]='\';
s[x+1][y-1]='/';
s[x+1][y]='_';
s[x+1][y+1]='_';
s[x+1][y+2]='\';
return ;
}
dfs(n-1,x,y,c/2,k/2);
dfs(n-1,x+c/2,y-k/4,c/2,k/2);
dfs(n-1,x+c/2,y+k/4,c/2,k/2);
}
int main()
{
int n;
scanf("%d",&n);
int c=2,k=4;
for(int i=2;i<=n;i++) {
c*=2; k*=2;
}

for(int i=1;i<=c;i++) {
for(int j=1;j<=k;j++) {
s[i][j]=' ';
}
}
dfs(n,1,k/2,c,k);
for(int i=1;i<=c;i++) {
for(int j=1;j<=k;j++) {
printf("%c",s[i][j]);
}
printf("n");
}
}

分治算法

原文:https://www.cnblogs.com/lijianming180/p/12262596.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!