蓝桥杯分治

P1226 【模板】快速幂

题目描述

给你三个整数 𝑎,𝑏,𝑝a,b,p，求 𝑎𝑏 mod 𝑝abmodp。

输入格式

输入只有一行三个整数，分别代表 𝑎,𝑏,𝑝a,b,p。

输出格式

输出一行一个字符串 a^b mod p=s，其中 𝑎,𝑏,𝑝a,b,p 分别为题目给定的值， 𝑠s 为运算结果。

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例解释

210=1024210=1024，1024 mod 9=71024mod9=7。

数据规模与约定

对于 100%100% 的数据，保证 0≤𝑎,𝑏<2310≤a,b<231，𝑎+𝑏>0a+b>0，2≤𝑝<2312≤p<231。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;public class Main {static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));static long nextLong() throws IOException{st.nextToken();return (long)st.nval;}public static void main(String[] args) throws IOException {// TODO Auto-generated method stublong a=nextLong();long b=nextLong();long q=nextLong();long a1=a,b1=b;long ans=1;while(b>0) {if(b%2==1) ans=(ans*a)%q;a=(a*a)%q;b=b>>1;}System.out.println(a1 + "^" + b1 + " mod " + q + "=" + ans);}}

P1010 [NOIP1998 普及组] 幂次方

题目描述

任何一个正整数都可以用 22 的幂次方表示。例如 137=27+23+20137=27+23+20。

同时约定次方用括号来表示，即 𝑎𝑏ab 可表示为 𝑎(𝑏)a(b)。

由此可知，137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)

进一步：

7=22+2+207=22+2+20 ( 2121 用 22 表示)，并且 3=2+203=2+20。

所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 1315=210+28+25+2+11315=210+28+25+2+1

所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入格式

一行一个正整数 𝑛n。

输出格式

符合约定的 𝑛n 的 0,20,2 表示（在表示中不能有空格）。

输入输出样例

输入 #1复制

1315

输出 #1复制

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

说明/提示

【数据范围】

对于 100%100% 的数据，1≤𝑛≤2×1041≤n≤2×104。

NOIP1998 普及组 第三题

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader f = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(f.readLine());calc(n);}static void calc(int n) {if(n == 0)return;int exp=0;while(n>=(1<<exp)){exp++;}exp--;n-=(1<<exp);if(exp==0||exp==2){System.out.print("2"+"("+exp+")");}if(exp==1){System.out.print("2");}if(exp>2){System.out.print("2"+"(");calc(exp);System.out.print(")");}if(n>0){System.out.print("+");calc(n);}}
} 

P1429 平面最近点对（加强版）

题目背景

P7883 平面最近点对（加强加强版）

题目描述

给定平面上 𝑛n 个点，找出其中的一对点的距离，使得在这 𝑛n 个点的所有点对中，该距离为所有点对中最小的

输入格式

第一行：𝑛n ，保证 2≤𝑛≤2000002≤n≤200000 。

接下来 𝑛n 行：每行两个实数：𝑥 𝑦x y ，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式

仅一行，一个实数，表示最短距离，精确到小数点后面 44 位。

输入输出样例

输入 #1复制

3
1 1
1 2
2 2

输出 #1复制

1.0000

说明/提示

数据保证 0≤𝑥,𝑦≤1090≤x,y≤109

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1000001;
const int INF = 2 << 20;
int n, temp[maxn];
struct Point 
{double x, y;
} S[maxn];
bool cmp(const Point &a, const Point &b) 
{if(a.x == b.x) return a.y < b.y;else return a.x < b.x;
}
bool cmps(const int &a, const int &b) { return S[a].y < S[b].y; }
double min(double a, double b) { return a < b ? a : b; }
double dist(int i, int j) 
{double x = (S[i].x - S[j].x) * (S[i].x - S[j].x);double y = (S[i].y - S[j].y) * (S[i].y - S[j].y);return sqrt(x + y);
}
double merge(int left, int right) 
{double d = INF;if(left == right) return d;if(left + 1 == right) return dist(left, right);int mid = left + right >> 1;double d1 = merge(left, mid);double d2 = merge(mid + 1, right);d = min(d1, d2);int i, j, k = 0;for(i = left; i <= right; i++)if(fabs(S[mid].x - S[i].x) < d) // 这里不太一样temp[k++] = i;sort(temp, temp + k, cmps);for(i = 0; i < k; i++)for(j = i + 1; j < k && S[temp[j]].y - S[temp[i]].y < d; j++) {double d3 = dist(temp[i], temp[j]);if(d > d3) d = d3;}return d;
}
int main() 
{scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%lf%lf", &S[i].x, &S[i].y);sort(S, S + n, cmp);return !printf("%.4lf\n", merge(0, n - 1));
}