pearfl / blog Goto Github PK
View Code? Open in Web Editor NEWUsed for technical summary
Used for technical summary
本模板用于2019年5月安徽省程序设计竞赛
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
return b == 0 ? a : gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a*b/gcd(a,b);
}
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main(){
freopen("in","r",stdin);
clock_t st,ed;
st = clock();
/*………………*/
ed = clock();
printf("Use Time:%f\n",((double)(ed - st)/CLOCKS_PER_SEC));
return 0;
}
给一个数$ n$,让你找出一个只由
/*
input:
2
output:
10
对于输入整数 n 的每一个值,输出 m 的相应值,保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解,其中任何一个都是可以接受的
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll f;
void dfs(ll num,ll flag,ll step){
if(m) return ;
if((num % n == 0) && (num != 0)){
m = num;
return ;
}
if(step == 19){
return ;
}
dfs(num*10, 0, step + 1);
if(flag == 0){
dfs(num+1, 1, step);
}
}
int main(){
cin>>n;
m = 0;
dfs(0, 0, 1);
cout<<m<<endl;
return 0;
}
输入$n$,打印输出$1-n$的全排列
/*
input:
3
output:
6
123
132
213
231
312
321
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll vis[15];
ll ans[15];
void dfs(ll step){
//输出要求满足
if(step == n + 1){
for(ll i=1;i<=n;i++){
printf("%lld",ans[i]);
}
printf("\n");
return ;
}
for(ll i=1;i<=n;i++){
if(!vis[i]){
vis[i] = 1;
ans[step] = i;
dfs(step + 1);//取了
vis[i] = 0;
}
}
}
ll cnt;
int main(){
scanf("%lld",&n);
cnt = 1;
for(ll i=2;i<=n;i++){
cnt *= i;
}
printf("%lld\n",cnt);
dfs(1);
return 0;
}
/*
input:
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
output:
8
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int G[20][20];
bool vis[20];
int ans = 1000000000;
int n;
void dfs(int u, int cnt, int sum){
if(sum >= ans){
return ;
}
if(cnt == n){
ans = min(ans, sum + G[u][1]);
}
vis[u] = 1;
// 枚举当前城市可能到达的下一个城市
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i, cnt + 1, sum + G[u][i]);
}
}
vis[u] = 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>G[i][j];
}
}
dfs(1, 1, 0);
cout<<ans<<endl;
return 0;
}
首先输入一个整数
如果蒜头君能拼出正方形,输出"Yes",否则输出"No"。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int sum = 0;
int s1;
int le[4] = {0}, a[21], b[21] = {0};
bool ok = 0;
void dfs(int x, int j){
if(x == 4){
ok = 1;
return ;
}
if(ok){
return ;
}
if(le[x] > s1){
return ;
}
if(le[x] == s1){
dfs(x + 1, 1);
}else{
for(int f=j;f<=n;++f){
if(b[f] == 0){
b[f] = 1;
le[x] += a[f];
dfs(x, f + 1);
le[x] -= a[f];
b[f] = 0;
}
}
}
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum += a[i];
}
s1 = sum / 4;
if(sum % 4 != 0){
cout << "No";
return 0;
}
dfs(1, 1);
if(ok){
cout<<"Yes";
}else{
cout<<"No";
}
}
解决单源最短路径问题常用 Dijkstra 算法,用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心,逐层向外扩展(这一点类似于 bfs,但是不同的是,bfs 每次扩展一个层,但是 Dijkstra 每次只会扩展一个点),每次都会取一个最近点继续扩展,直到取完所有点为止。
注意:Dijkstra 算法要求图中不能出现负权边。
我们定义带权图$ G
从
并用
重复步骤 1 和 2,直到
如果最后
Dijkstra 算法的时间复杂度为$ \mathcal{O}(V^2)$,其中
Dijkstra 是解决无负边权的图的单源最短路问题,经常使用邻接表存储。
不优化的时间复杂度是
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, fail;
edge() {}
edge(int _v, int _w, int _fail) {
v = _v;
w = _w;
fail = _fail;
}
} e[M << 1];
int head[N], len;
void init() {
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w) {
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
for (int i = 0; i < n; ++i) {
int mi = inf;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] < mi) {
mi = dis[u = j];
}
}
if (mi == inf) {
return;
}
vis[u] = true;
for (int j = head[u]; ~j; j = e[j].fail) {
int v = e[j].v;
int w = e[j].w;
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}
int main() {
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
add2(u, v, w);
}
dijkstra(1);
cout << dis[n] << endl;
return 0;
}
用一个set来维护点的集合,这样的时间复杂度就优化到了
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
min_heap.insert(make_pair(0, s));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点,说明有顶点无法从源点到达,算法结束
return false;
}
// 获取堆顶元素,并将堆顶元素从堆中删除
set<PII, less<PII> >::iterator iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
// 先将对应的 pair 从堆中删除,再将更新后的 pair 插入堆
min_heap.erase(make_pair(dist[x], x));
dist[x] = dist[v] + e[j].w;
min_heap.insert(make_pair(dist[x], x));
}
}
}
return true; // 存储单源最短路的结果
}
我们在
这个代码的时间复杂度实际上会比用真正的堆要慢一点,因为有的点可能会入队多次,但是每一条边最多导致一次入队,所以这个算法的时间复杂度为
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
struct node {
int u;
int dist;
node(int _u, int _dist) : u(_u), dist(_dist) {}
bool operator < (const node &x) const {
return dist > x.dist;
}
}; // 记录点的结构体
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
priority_queue<node> min_heap;
dist[s] = 0;
min_heap.push(node(s, 0));
while (!min_heap.empty())
// 获取堆顶元素,并将堆顶元素从堆中删除
int v = min_heap.top().u;
min_heap.pop();
if (vst[v]) {
continue;
}
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
min_heap.push(node(x, dist[x]));
}
}
}
return true;
}
SPFA(Shortest Path Faster Algorithm)算法是单源最短路径的一种算法,通常被认为是 Bellman-ford 算法的队列优化,在代码形式上接近于宽度优先搜索 BFS,是一个在实践中非常高效的单源最短路算法。
在
1.初始队列中仅包含源点,且源点
2.取出队列头顶点
将
若
将
3.重复步骤 2 直到队列为空
最终$ d$ 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct edge{
int v, w, fail;
edge(){}
edge(int _v, int _w, int _fail){
v = _v;
w = _w;
fail = _fail;
}
}e[M << 1];
int head[N], len;
void init(){
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w){
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w){
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void spfa(int u){
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
vis[u] = false;
for(int j = head[u];~j;j = e[j].fail){
int v = e[j].v;
int w = e[j].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
int main() {
init();
int u, v, w;
cin>>n>>m;
while(m--){
cin>>u>>v>>w;
add2(u, v, w);
}
spfa(1);
cout<<dis[n]<<endl;
return 0;
}
但是
memset(in, 0, sizeof in);
in[u] = 1;
// 修改入队部分的操作
if(!vis[v]){
q.push(v);
vis[v] = true;
++in[v];
if(in[v] > n){
return true;
}
}
int g[N][N];
void floyd(int n) {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
对一个 有向无环图$ G $进行拓扑排序,是将
拓扑排序算法主要由以下两步循环执行,直到不存在入度为 0 的顶点为止。
选择一个入度为 0 的顶点并将它输出;
删除图中从顶点连出的所有边。
循环结束,若输出的顶点数小于图中的顶点数,则表示该图中存在回路,也就是无法进行拓扑排序;否则输出的顶点序列就是一个拓扑序列。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
int v, next;
int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v) {
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid++;
}
int n, m;
int indegree[MAX_N];
void topo(){
/* 如果要求为字典序,修改为
priority_queue <int, vector<int>, greater<int> > q;
*/
queue<int> q;
for(int i=1;i<=n;i++){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int now = q.front();
cout<<now<<endl;
q.pop();
for(int i=p[now];i!=-1;i=E[i].next){
int v = E[i].v;
indegree[v]--;
if(indegree[v] == 0){
q.push(v);
}
}
}
}
int main() {
init();
memset(indegree, 0, sizeof(indegree));
cin>>n>>m;
for(int i=0;i<m;i++){
int u, v;
cin>>u>>v;
insert(u, v);
indegree[v]++;
}
topo();
return 0;
}
若图
若该路径是一个环路,则称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
无向图
一个无向图
当无向图
一个无向图
有向图
这个代码每次仅将一个入度为0的元素放入队列中
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105][105], r[105];
void topu(int n){
int rr = 0, s = 0, flag = 0;
while(rr < n && !flag){
flag = 1;//1标记拓扑队列内没有元素
for(int i=0;i<n;i++){
if(r[i] == 0){
s++;// 进拓扑的元素+1
flag = 0; // 标记要开始新的拓扑
r[i]--; //更改入度
for(int j=0;j<n;j++){
// 扫描更改所有入度
if(a[i][j]){
r[j]--;
}
}
break;
}
}
}
if(s == n){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
int main() {
int n, m;
cin>>n>>m;
memset(a, 0, sizeof(a));
memset(r, 0, sizeof(r));
for(int i=0;i<m;i++){
int x, y;
cin>>x>>y;
if(!a[x][y]){
a[x][y] = 1;
r[y]++;
}
}
topu(n);
return 0;
}
解析
我们就可以将“当前传递过物品的人的集合、最后一个传递到的人”作为状态进行动态规划,用$dp[i][j]$表示这个状态的最小代价。
这里,我们就要用到状态压缩:把“传递过物品的人的集合”压缩为一个整数。我们用二进制表示这个集合,比如一共$5$个人,第
注意到
转移方程为$dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k])$,其中$a[j][k]$为从
因为开始时物品可以在任意一人手上,所以把$dp[1 << i][i]$置为
总的时间复杂度为
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[1 << i][i] = 0;
}
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
for (int k = 0; k < n; k++) {
if (!(i & (1 << k))) {
dp[i | 1 << k][k] =
min(dp[i | 1 << k][k], dp[i][j] + a[j][k]);
}
}
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) {
ans = min(ans, dp[(1 << n) - 1][i]);
}
有
因为路线是一个环,可以规定任意点为起点和终点,不妨设城市
初始时
时间复杂度为
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int s = 0; s < (1 << n); s++) {
for (int i = 0; i < n; i++) {
if (s & (1 << i)) {
for (int j = 0; j < n; j++) {
if (j != i && (s & (1 << j))) {
dp[s][i] =
min(dp[s][i], dp[s ^ 1 << i][j] + dist[j][i]);
}
}
}
}
}
int ans = INF;
for (int i = 1; i < n; i++) {
ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
}
给定一个
#include <iostream>
using namespace std;
int a[21][20];
int state[21];
int dp[21][1 << 20];
bool ok(int now){ //判断行内是否相交
return (now & (now >> 1)) == 0;
}
bool fit(int now, int i){ //判断选取状态是否和符合第i行的输入
return (now | state[i]) == state[i];
}
bool not_intersect(int now, int prev){ //判断状态now和状态prev能否放在相邻的行
return (now & prev) == 0;
}
int count(int now){ // 统计状态Now选取了多少个元素
int s = 0;
while(now){
s += (now & 1);
now >>= 1;
}
return s;
}
int main() {
int n, m;
cin >> n >> m;
// 行从 1 开始,列从 0 开始,这样后面处理起来方便
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
// 二维矩阵压成一维
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(a[i][j]){
state[i] += (1 << j);
}
}
}
// 最外层一共n行,行位元素集合为1<<m
// 找到一个可行的行以后,枚举上一行的所有状态
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<m);j++){
if(ok(j) && fit(j, i)){
for(int k=0;k<(1<<m);k++){
if(ok(k) && fit(k, i-1) && not_intersect(j, k)){
dp[i][j] = max(dp[i][j], dp[i-1][k] + count(j));
}
}
}
}
}
int ans = 0;
for(int i=0;i<(1<<m);i++){
ans = max(ans, dp[n][i]);
}
cout<<ans<<endl;
return 0;
}
例题:对于一串数$num$,比如$num=[1,3,4,7,1,4,3,8]$,可以将数组中连续若干个数合并为一组 gi。将这串数组分成至多$ k$组,当$k=4 $的时候,每组数的总和的最大值$max(gi)$最小是多少?
#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){
int now = 0, cnt = 0;
for(int i=0;i<n;++i){
if(now + a[i] > x){
++cnt;
now = a[i];
}else{
now += a[i];
}
}
return cnt <= k;
}
int cal(int l, int r){
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}else{
l = mid + 1;
}
}
return l;
}
int main() {
int ma = -inf, sum = 0;
cin >> n >> k;
for(int i=0;i<n;++i){
cin>>a[i];
ma = max(ma, a[i]);
sum += a[i];
}
cout<< cal(ma, sum) <<endl;
return 0;
}
01 分数规划是这样的一类问题,有一堆物品,每一个物品有一个收益 a i ,一个代价 bi,我们要求一个方案,使选择的 k 个元素 $ \frac{\sum{a_i}} { \sum{b_i}} ∑b_i ∑a_i $ 最大值
分数规划的基本**是,我们先假设:
$$
f(x) = \frac{\sum^{n}{0}{x_i}*{a_i}} { \sum^{n}{0}{x_i}*{b_i}}
$$
其中$x_i$ 只有两个取值 0, 1来表示是否选取第 i 个物品,并且
继续假设有一组 x 在 f(x) = v的时候,为最优解,上式变形如下:
$$
\sum^{n}{0}{x_i}{(a_i - vb_i)} = 0
$$
我们现在对 v二分,如果 v过大的时候,$\sum^{n}{0}{x_i}{(a_i - vb_i)} < 0$,我们无论如何怎么选择这 k个元素,都不会找到一组使得$\sum^{n}_{0}{x_i}{(a_i - vb_i)} >= 0$的x。而实际上,我们只需要对n个元素按照$a_i - v*b_i$ 排序后,选出最大的k个就是最大值了
反之,v过小的时候,$\sum^{n}_{0}{x_i}{(a_i - vb_i)} > 0$ ,那么我们就能根据选出来的最大的k个$a_i - v*b_i$ 的和来判断v和最后答案的关系,从而进行二分
double g(double v) {
for (int i = 0; i < n; ++i) { // 计算 a(x) - v * b(x)
tmp[i] = a[i] - v * b[i];
}
sort(tmp, tmp + n);
double sum = 0;
for (int i = n - k; i < n; ++i) { // 选择 k 个最大的比值
sum += tmp[i];
}
return sum;
}
double cal() {
double l = 0, r = 1e10;
while (r - l > eps) {
double mid = (l + r) / 2;
if (g(mid) > 0) {
l = mid;
} else {
r = mid;
}
}
return l;
}
三分法解决凸形或者凹形函数的极值
二分法解决连续不间断函数的零点
$$
请计算下面方程的的最大值 (0 \le \theta \le \frac{\pi}{2})
$$
$$
y = \frac{( - x + l * sin(θ)+\frac{d}{cos(θ)})}{tan(θ)}
$$
经过求导计算发现这个方程式凸函数,所以符合三分的使用要求,所以这道题目我们可以使用三分法来计算
#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1);
const double eps = 1e-9;
double x, y, l, d;
double f(double du){
return (-x + l*sin(du) + d / cos(du)) / tan(du);
}
double cal(){
double l = 0, r = pi / 2;
while(r - l > eps){
double mid = (l + r) / 2;
double mmid = (mid + r) / 2;
if(f(mid) < f(mmid)){
l = mid;
}else{
r = mmid;
}
}
return l;
}
int main() {
cin>>x>>l>>d;
printf("%.3lf\n", cal());
return 0;
}
给定一个包含
/*
input:
10 7
-3 -2 -4 4 8 9 3 -1 10 0
ouput:
4
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, s;
ll a[1000005];
int main(){
ll ans = 0;
cin>>n>>s;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++){
ll y = s - a[i];
ll l = i, r = n;
bool flag = false;
while(l <= r){
ll mid = (l + r) >> 1;
if(a[mid] == y){
flag = true;
break;
}else if(a[mid] < y){
l = mid + 1;
}else{
r = mid - 1;
}
}
if(flag){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
求解关于 x 的方程$ x + ln(x) = a$的解,其中
/*
input:
10
output:
7.929420
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
double a;
double f(double x){
return x + log(x) - a;
}
int main(){
cin>>a;
double l = 0,r = 1e9;
while(r - l > eps){
double mid = (l + r) / 2;
if(f(mid) <= 0){
l = mid;
}else{
r = mid;
}
}
printf("%.6lf\n", l);
return 0;
}
蒜头君有
/*
input:
3 4
output:
28
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main(){
ll n, m;
const ll mod = 1e9+7;
cin>>n>>m;
cout<<(ksm(m, n, mod) - (ksm(m-1, n-1, mod)*m)%mod + mod) % mod<<endl;
return 0;
}
/*
input:
8 8
12 3 14 12 14 20 4 8
output:
7
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10005;
int a[maxn];
int main(){
int n, k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
int l = 0, r = 100000001;
while(l < r){
int mid = (l + r)>>1;
int cnt = 0;
for(int i=0;i<n;i++){
cnt += a[i] / mid;
}
if(cnt >= k){
l = mid + 1;
}else{
r = mid;
}
}
cout<<r - 1<<endl;
return 0;
}
铁路线上有 n 个车站,假设这条铁路线是一条直线,其中每个站点的坐标为
蒜头君一共要开办 m 个连锁店,并且不希望连锁店离得太近,以使得整体的收益最大化。他希望他的连锁店之间的最近距离尽可能大,你能帮他算出这个最大的最近距离吗?
输入为$n、m、x[]$
/*
input:
5 4
5
7
10
28
9
output:
2
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
int a[maxn];
int n, m;
bool check(int mid){
int last = 0;
int cnt = 1;
while(last < n - 1){
int j;
for(j = last+1;j<n;++j){
if(a[j] - a[last] >= mid){
last = j;
++cnt;
break;
}
}
if(j == n){
break;
}
}
if(cnt >= m){
return 1;
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int l = 0, r = a[n-1];
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)){
l = mid + 1;
}else{
r = mid;
}
}
cout<<r - 1<<endl;
return 0;
}
快速计算2个数的最大公约数
// 可直接用__gcd(a, b)
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a%b);
}
时间复杂度为$O(logN)$,可以证明其递归层数不会超过$4.7851*lgonN+1.6723$
for (int i = 2; i <= n; i++) {
is_prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j +=i) {
is_prime[j] = false;
}
}
}
优化后时间复杂度比$O(NloglogN)$还要低
积性函数是满足下列性质的一类函数
$$
f(mn) = f(m)*f(n),∀gcd(m,n) = 1
$$
欧拉函数$ ϕ(n)$:小于等于 n 的所有数中与 n 互质的数的个数
例如$ϕ(10) = 4$,因为1,3,7,9均和10互质
欧拉函数为积性函数
$$
ϕ(x) = x(1 - (1/p1))(1 - (1/p2))(1 - (1/p3))\cdots*(1 - (1/pn)),其中 p_1,p_2 \cdots,p n 是 x 的所有质因数
$$
欧拉定理:若$a,b$互质,则有
$$
a^{ϕ(n)}≡ 1: (mod :n)
$$
特例:费马小定理
$$
a^{p-1}≡ 1: (mod :p)
$$
其他性质
$$
\displaystyle \sum^{}_{d|n}{ϕ(d) = n}
$$
求一个数的欧拉函数值
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
res = res / n * (n - 1);
}
cout << res << endl;
区间预处理欧拉函数
for (int i = 1; i <= n; i++) {
phi[i] = i;
}
for (int i = 2; i <= n; i++) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
欧拉函数例题:
$$
给定一个整数 n,请问有多少个整数 i满足条件:gcd(i, n) = 1,1 \leq i \leq n
$$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
int res = n;
for(int i=2;i*i<=n;i++){
if(n % i == 0){
res = res / i * (i-1);
while(n%i == 0){
n /= i;
}
}
}
if(n > 1){
res = res / n * (n-1);
}
cout<<res<<endl;
return 0;
}
矩阵乘法
struct matrix {
int n, m;
int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
matrix C;
C.n = A.n;
C.m = B.m;
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < B.m; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < A.m; ++k) {
C.a[i][j] += A.a[i][k] * B.a[k][j];
}
}
}
return C;
}
int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
// 2 个矩阵相乘
matrix C;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < n; ++k) {
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
}
}
}
return C;
}
matrix unit() {
// 返回一个单位矩阵
matrix res;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
res.a[i][j] = 1;
} else {
res.a[i][j] = 0;
}
}
}
return res;
}
matrix matrix_pow(matrix A, int n, int mod) {
// 快速求矩阵 A 的 n 次方
matrix res = unit(), temp = A;
for (; n; n /= 2) {
if (n & 1) {
res = matrix_mul(res, temp, mod);
}
temp = matrix_mul(temp, temp, mod);
}
return res;
}
const int maxn = 10010;
int minv[4 * maxn], a[maxn];
// id 表示结点编号,l, r 表示左右区间
void build(int id, int l, int r) {
if (l == r) {
minv[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
// pushup函数
minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
// 把 x 位置更为成为 v
void update(int id, int l, int r, int x, int v) {
if (l == r) {
minv[id] = v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(id << 1, l, mid, x, v);
} else {
update(id << 1 | 1, mid + 1, r, x, v);
}
pushup(id);
}
int query(int id, int l, int r, int x) {
if (l == r) {
return minv[id];
}
int mid = (l + r) >> 1;
if (mid <= x) {
return query(id << 1, l, mid, x);
} else {
return query(id << 1 | 1, mid + 1, r, x);
}
}
int query(int id, int l, int r, int x, int y) {
if (x <= l && r <= y) { // 如果完全包含,直接返回
return minv[id];
}
int mid = (l + r) >> 1;
int ans = inf;
if (x <= mid) {
ans = min(ans, query(id << 1, l, mid, x, y)); // 如果左区间包含,递归的查询左子树
}
if (y > mid) {
ans = min(ans, query(id << 1 | 1, mid + 1, r, x, y)); // 如果右区间包含,递归的查询右子树
}
return ans;
}
//getsum(r) - getsum(l-1)
int lowbit(int x){
return x & -x;
}
int getsum(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res += C[i];
}
return res;
}
void update(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
C[i] += v;
}
}
给定包含
每次操作把区间$ [l, r$] 上的数加上
我们对于数列做差分,得到差分序列
得到最后的差分序列,然后还原成原数列就可以了。
#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn], d[maxn];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
d[i] = a[i] - a[i-1];
}
int q;
cin>>q;
while(q--){
int l,r,v;
cin>>l>>r>>v;
d[l] += v;
d[r+1] -= v;
}
for(int i=1;i<=n;++i){
a[i] = a[i-1] + d[i];
cout<<a[i]<<" ";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int c[N << 4];
void update(int o, int l, int r, int x, int v){
if(x <= l && r <= x){
c[o] = v;
return;
}
int mid = l + r >> 1;
if(x <= mid){
update(o << 1, l, mid, x, v);
}
if(mid < x){
update(o << 1 | 1, mid + 1, r, x, v);
}
c[o] = max(c[o << 1] , c[o << 1 | 1]);
}
int query(int o, int l, int r, int x, int y){
if(x <= l && r <= y){
return c[o];
}
int mid = l + r >> 1;
int res = 0;
if(x <= mid){
res = max(res, query(o << 1, l, mid, x, y));
}
if(mid < y){
res = max(res, query(o << 1 | 1, mid + 1, r, x, y));
}
return res;
}
int main() {
int n, v, m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> v;
update(1, 1, n, i, v);
}
string s;
while(m--){
int x,y;
cin >> s;
cin >> x >> y;
if(s[0] == 'Q'){
cout<<query(1, 1, n, x, y)<<endl;
}else if(s[0] == 'U'){
update(1, 1, n, x, y);
}
}
return 0;
}
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+7;
int N,Q;
LL a[maxn],t[4*maxn],laz[4*maxn];
void build(int rt,int l,int r)
{
if(l==r)
{
t[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
t[rt]=t[rt<<1]+t[rt<<1|1];
}
void pushdown(int rt,int l,int r)
{
if(laz[rt]==0)
return;
int mid=(l+r)>>1;
t[rt<<1]+=laz[rt]*(mid-l+1);
laz[rt<<1]+=laz[rt];
t[rt<<1|1]+=laz[rt]*(r-mid);
laz[rt<<1|1]+=laz[rt];
laz[rt]=0;
}
void updata(int rt,int l,int r,int a,int b,LL c)
{
if(a<=l&&r<=b)
{
t[rt]+=c*(r-l+1);
laz[rt]+=c;
return;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(b<=mid)
updata(rt<<1,l,mid,a,b,c);
else if(a>mid)
updata(rt<<1|1,mid+1,r,a,b,c);
else
{
updata(rt<<1,l,mid,a,b,c);
updata(rt<<1|1,mid+1,r,a,b,c);
}
t[rt]=t[rt<<1]+t[rt<<1|1];
}
LL query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
return t[rt];
if(r<ql||l>qr)
return 0;
pushdown(rt,l,r);
int mid=(l+r)>>1;
return query(rt<<1,l,mid,ql,qr)+query(rt<<1|1,mid+1,r,ql,qr);
}
int main()
{
scanf("%d %d",&N,&Q);
for(int i=1;i<=N;i++)
scanf("%lld",&a[i]);
build(1,1,N);
while(Q--)
{
getchar();
char C=getchar();
int a,b;
scanf("%d %d",&a,&b);
if(C=='C')
{
LL c;
scanf("%lld",&c);
updata(1,1,N,a,b,c);
}
else
printf("%lld\n",query(1,1,N,a,b));
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1000005;
const int maxm = 10005;
char a[maxn],b[maxm];
int nex[maxm];
int n,m;
int kmp(){
int i1=0,i2=0,ans=0;
while(i1 < n){
if(i2 == -1 || a[i1] == b[i2]){
i1++;
i2++;
}
else i2 = nex[i2];
if(i2 == m){
i2 = 0;
ans++;
}
}
return ans;
}
void getnext(){
memset(nex,-1,sizeof(nex));
nex[0] = -1;
nex[1] = 0;
int i = 2;
int cn = 0;
while(i <= m){
if(b[i-1] == b[cn]){
nex[i++] = ++cn;
}else if(cn > 0){
cn = nex[cn];
}else{
nex[i++] = 0;
}
}
/*for(int j=0;j<5;j++){
cout<<nex[j]<<" ";
}*/
}
int main(){
//freopen("in","r",stdin);
int T;
scanf("%d",&T);
while(~(scanf("%s",a))){
if(a[0]=='#') break;
scanf("%s",&b);
//cin>>b>>a;
n = strlen(a);
m = strlen(b);
getnext();
cout<<kmp()<<endl;
}
return 0;
}
构造函数
bitset<n> b;
b有n位,每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则”b0”为”00000”;
bitset<n> b(unsigned long u);
b有n位,并用u赋值;如果u超过n位,则顶端被截除
如:bitset<5>b0(5);则”b0”为”00101”;
bitset<n> b(string s);
b是string对象s中含有的位串的副本
string bitval ( “10011” );
bitset<5> b0 ( bitval4 );
则”b0”为”10011”;
bitset<n> b(s, pos);
b是s中从位置pos开始位的副本,前面的多余位自动填充0;
string bitval (“01011010”);
bitset<10> b0 ( bitval5, 3 );
则”b0” 为 “0000011010”;
bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval (“11110011011”);
bitset<6> b0 ( bitval5, 3, 6 );
则”b0” 为 “100110”;
os << b
把b中的位集输出到os流
os >>b
输入到b中,如”cin>>b”,如果输入的不是0或1的字符,只取该字符前面的二进制位.
bool any( )
是否存在置为1的二进制位?和none()相反
bool none( )
是否不存在置为1的二进制位,即全部为0?和any()相反.
size_t count( )
二进制位为1的个数.
size_t size( )
二进制位的个数
flip()
把所有二进制位逐位取反
flip(size_t pos)
把在pos处的二进制位取反
bool operator[]( size_type _Pos )
获取在pos处的二进制位
set()
把所有二进制位都置为1
set(pos)
把在pos处的二进制位置为1
reset()
把所有二进制位都置为0
reset(pos)
把在pos处的二进制位置为0
test(size_t pos)
在pos处的二进制位是否为1?
unsigned long to_ulong( )
用同样的二进制位返回一个unsigned long值
string to_string ()
返回对应的字符串.
方法1(逆元求法):
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
int f[N], finv[N], inv[N];
void init(void) { //要求MOD是质数,预处理时间复杂度O(n)
inv[1] = 1;
for (int i=2; i<N; ++i) {
inv[i] = (MOD - MOD / i) * 1ll * inv[MOD%i] % MOD;
}
f[0] = finv[0] = 1;
for (int i=1; i<N; ++i) {
f[i] = f[i-1] * 1ll * i % MOD;
finv[i] = finv[i-1] * 1ll * inv[i] % MOD;
}
}
方法2:$C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)$
const int N = 2000 + 10;
const int MOD = 1e9 + 7;
int comb[N][N];
void init(void) { //对MOD没有要求,预处理时间复杂度O(n^2)
for (int i=0; i<N; ++i) {
comb[i][i] = comb[i
][0] = 1;
for (int j=1; j<i; ++j) {
comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
if (comb[i][j] >= MOD) {
comb[i][j] -= MOD;
}
}
}
}
方法3(Lucas定理,大组合数取模, HDOJ 3037为例):
ll f[N];
void init(int p) { //f[n] = n!
f[0] = 1;
for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;
}
ll pow_mod(ll a, ll x, int p) {
ll ret = 1;
while (x) {
if (x & 1) ret = ret * a % p;
a = a * a % p;
x >>= 1;
}
return ret;
}
ll Lucas(ll n, ll k, int p) { //C (n, k) % p
ll ret = 1;
while (n && k) {
ll nn = n % p, kk = k % p;
if (nn < kk) return 0; //inv (f[kk]) = f[kk] ^ (p - 2) % p
ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;
n /= p, k /= p;
}
return ret;
}
int main(){
init (p);
printf ("%I64d\n", Lucas (n + m, n, p));
return 0;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){
if(a == 0 && b == 0) return -1;
if(b == 0){
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b,a%b,y,x);
y -= a/b*x;
return d;
}
ll inv(ll a,ll n){
ll x,y;
ll d = extend_gcd(a,n,x,y);
if(d == 1) return (x%n+n)%n;
else return -1;
}
ll ksm(ll x,ll n,ll mod){
ll res = 1;
x = x % mod;
while(n > 0){
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
//m 中 选 n 个
ll getc(ll m,ll n){
ll mc=1,nc=1;
for(ll i=m;i>m-n;i--){
mc*=i;
mc%=mod;
}
for(ll i=n;i>=1;i--){
nc*=i;
nc%=mod;
}
return mc*inv(nc,mod)%mod;
}
又称牛顿二项式定理,是指两个整数的整数幂次的展开式。 $ \displaystyle (x+y)^n=\sum C_n^i x^{n-i}y^i=\binom n 0 x^n+\binom n 1 x^{n-1}y+\cdots+\binom n n y^n$
int par[MAX_N];
int rank[MAX_N];
//初始化n个元素
void init(int n){
for(int i=0;i<n;i++){
par[i] = i;
rank[i] = 0;
}
}
//查询树的根
int find(int x){
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
//合并x和y所属的集合
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x] == rank[y]) rank[x]++;
}
}
//判断x和y是否属于同一个集合
bool same(int x,int y){
return find(x) == find(y);
}
DFS
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
char field[105][105]; //园子
void dfs(int x,int y){
field[x][y]='.';
for(int dx = -1;dx <= 1;dx++){
for(int dy = -1;dy <= 1;dy++){
int nx=x+dx,ny=y+dy;
if(nx>=0 && nx<n && ny<m && ny>=0 && field[nx][ny] =='W') dfs(nx,ny);
}
}
return ;
}
void solve(){
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(field[i][j]=='W'){
dfs(i,j);
res++;
}
}
}
printf("%d\n",res);
}
void init(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",field[i]);
}
int main()
{
//freopen("input.txt","r",stdin);
init();
solve();
return 0;
}
BFS
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,step;
};
int vis[8][8];//8X8储存棋盘
int sx,sy,ex,ey,ans;
int to[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
//第一个8对应的是马的8种移动情况
//第二个2代表的是ch1横坐标和纵坐标变化时对应的数值
int check(int x,int y)
{
if(x<0 || y<0 || x>=8 || y>=8)//超出了棋盘的范围
return 1;//超出范围,返回1
if(vis[x][y])//非0为真 ,此处为检验该位置是否之前已经用过
return 1;//该位置以前使用过,返回1
return 0;//该位置没有超出范围且没有用过,返回0
}
void bfs()//void结尾不需要return
{
int i;
queue<node> Q;//队列容器
node a,next;//a和next变成结构体头
a.x = sx;//ch1横坐标
a.y = sy;//ch1纵坐标
a.step = 0;// 目前ch1的坐标变化步骤为0
vis[sx][sy] = 1;//将ch1目前坐标的位置的数值标志为1
Q.push(a);//将a整个扔进去,Q是node类型,只能向其中添加node类型的元素,
//node类型看作一个元素而一个node元素又包含其他的元素
while(!Q.empty())//若Q不空则运行
{
a = Q.front();//返回第一个元素,队顶元素
//访问queue队首元素,如例:q.front(),即最早被压入队列的元素
Q.pop();//弹出Q中的第一个元素,并且不会返回数值(出队)
if(a.x == ex && a.y == ey)//ch1是否到达ch2的坐标
{
ans = a.step;//把当前的步骤数赋给ans
}
for(i = 0;i<8;i++)
{
next = a;//pop已经弹出上一个队顶元素,现在是下一个
next.x+=to[i][0];//ch1的横坐标的变化
next.y+=to[i][1];//ch1的纵坐标的变化
if(check(next.x,next.y))//调用上面的实参函数check
continue;//如果返回为1,跳出本次循环,后面三步骤跳过
next.step = a.step+1;//目前进行过的步骤次数+1
vis[next.x][next.y] = 1;//将该位置变更状态为已经使用过的位置
Q.push(next);//将next整个扔进队列里面
}
}
return ;
}
int main()
{
char ch1[10],ch2[10];
while(~scanf("%s%s",ch1,ch2))//等价于!=EOF
{
//ASCII码
sx = ch1[0]-'a';//ch1横坐标
sy = ch1[1]-'1';//ch1纵坐标
ex = ch2[0]-'a';//ch2横坐标
ey = ch2[1]-'1';//ch2纵坐标
memset(vis,0,sizeof(vis));//将vis数组整个清零
bfs();//调用bfs函数
printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,ans);
}
return 0;
}
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
if(j>=c[i]){
dp[i][j] = max(dp[i-1][j-c[i]]+w[i], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
for(int i=1;i<=N;i++){
for(int j=V;j>=c[i];j--){
dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
}
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
if(j >= c[i]){
dp[i][j] = max(dp[i][j-c[i]]+w[i], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
for(int i=1;i<=N;i++){
for(int j=c[i];j<=V;j++){
dp[j] = max(dp[j-c[i]]+w[i], dp[j]);
}
}
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
for(int k=0;k<=n[i];k++){
if(j >= c[i]*k){
dp[i][j] = max(dp[i-1][j - c[i]*k] + w[i]*k, dp[i][j]);
}
}
}
}
for(int i=1;i<=N;i++){
for(int j=V;j>=0;j--){
for(int k=0;k<=n[i];k++){
if(j>=c[i]*k){
dp[j] = max(dp[j - c[i]*k]+w[i]*k, dp[j]);
}
}
}
}
二进制优化
#include <iostream>
using namespace std;
int n[110], c[110], w[110];
int nc[1000], nw[1000];
int dp[5010];
int main() {
int N, V;
cin >> N >> V;
for (int i = 1; i <= N; ++i) {
cin >> w[i] >> c[i] >> n[i];
}
int ncnt = 0;
// 二进制拆分
for (int i = 1; i <= N; ++i) {
int k;
// 找到最大的 k
for (k = 1; n[i] - (1 << k) + 1 > 0; ++k) {
nc[ncnt] = (1 << (k - 1)) * c[i];
nw[ncnt] = (1 << (k - 1)) * w[i];
++ncnt;
}
--k;
// 最后一组
nc[ncnt] = (n[i] - (1 << k) + 1) * c[i];
nw[ncnt] = (n[i] - (1 << k) + 1) * w[i];
++ncnt;
}
// 01 背包
for (int i = 0; i < ncnt; ++i) {
for (int j = V; j >= nc[i]; --j) {
dp[j] = max(dp[j], dp[j - nc[i]] + nw[i]);
}
}
cout << dp[V] << endl;
return 0;
}
更加易懂的二进制优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool dp[500005];
int n[10];
int nc[500005];
int flag = 0;
int main(){
freopen("dolls.in","r",stdin);
freopen("dolls.out","w",stdout);
memset(n, 0, sizeof(n));
memset(dp, false, sizeof(dp));
int V = 0;
int k = 0;
for(int i=1;i<=6;i++){
cin>>n[i];
if(n[i]) dp[i] = true;
V = V + n[i] * i;
}
if(V % 2 == 1){
cout<<"Can't be divided."<<endl;
return 0;
}
int ncnt = 0;
for(int i=1;i<=6;i++){
int c = n[i];
for(int k = 1;k <= c; k = k * 2){
++ncnt;
nc[ncnt] = k*i;
c -= k;
}
++ncnt;
nc[ncnt] = c * i;
}
dp[0] = true;
for(int i=1;i<=ncnt;i++){
for(int j=V/2;j>=nc[i];j--){
dp[j] |= dp[j - nc[i]];
if(dp[V/2]){
break;
}
}
if(dp[V/2]){
break;
}
}
if(dp[V/2]) cout<<"Can be divided."<<endl;
else cout<<"Can't be divided."<<endl;
return 0;
}
不要62
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<"["<<x<<"]"<<endl
#define bug printf("***********\n")
void read(int &x){
char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
int n,m;
int dp[10][2],a[10];
int dfs(int len,bool lead,bool limit){
if(len < 0) return 1;
if(dp[len][lead] != -1 && !limit) return dp[len][lead];
int ans = 0,i,e=limit?a[len]:9;
for(i=0;i<=e;i++){
if(!(lead && i == 2) && i != 4){
ans += dfs(len-1,i==6,limit&&i == e);
}
}
if(!limit){
dp[len][lead] = ans;
}
return ans;
}
int solve(int x){
int len = 0;
while(x){
a[len++] = x % 10;
x /= 10;
}
return dfs(len-1,0,1);
}
int main(){
//freopen("in","r",stdin);
while(~scanf("%d %d",&n,&m)){
if(n == 0 && m == 0) break;
memset(dp,-1,sizeof(dp));
memset(a,0,sizeof(a));
printf("%d\n",solve(m) - solve(n-1));
}
return 0;
}
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
//递归边界,既然是按位枚举,最低位是0,那么pos==-1说明这个数我枚举完了
if(pos==-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的,那么这里就需要你在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
/*常规写法都是在没有限制的条件记忆化,这里与下面记录状态是对应,具体为什么是有条件的记忆化后面会讲*/
int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
ll ans=0;
//开始计数
for(int i=0;i<=up;i++)//枚举,然后把不同情况的个数加到ans就可以了
{
if() ...
else if()...
ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
/*这里还算比较灵活,不过做几个题就觉得这里也是套路了
大概就是说,我当前数位枚举的数是i,然后根据题目的约束条件分类讨论
去计算不同情况下的个数,还有要根据state变量来保证i的合法性,比如题目
要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类,
前一位如果是6那么这意味就不能是2,这里一定要保存枚举的这个数是合法*/
}
//计算完,记录状态
if(!limit && !lead) dp[pos][state]=ans;
/*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)//把数位都分解出来
{
a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来,反正注意数位边界就行
x/=10;
}
return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
}
int main()
{
ll le,ri;
while(~scanf("%lld%lld",&le,&ri))
{
//初始化dp数组为-1,这里还有更加优美的优化,后面讲
printf("%lld\n",solve(ri)-solve(le-1));
}
}
for(int len = 1;len<=n;len++){//枚举长度
for(int j = 1;j+len<=n+1;j++){//枚举起点,ends<=n
int ends = j+len - 1;
for(int i = j;i<ends;i++){//枚举分割点,更新小区间最优解
dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
}
}
}
const int MAX_N = 10000; // Trie 树上的最大结点数
const int MAX_C = 26; // 每个结点的子结点个数上限
struct Trie {
int *ch[MAX_N]; // ch 保存了每个结点的 26 个可能的子结点编号,26 对应着 26 种小写字母,也就是说,插入的字符串全部由小写字母组成。初始全部为 -1
int tot; // 总结点个数(不含根结点),初始为 0
int cnt[MAX_N]; // 以当前结点为终端结点的 Trie 树中的字符串个数
void init() { // 初始化 Trie 树,根结点编号始终为 0
tot = 0;
memset(cnt, 0, sizeof(cnt));
memset(ch, 0, sizeof(ch)); // 将 ch 中的元素初始化为 NULL
}
void insert(char *str) {
int p = 0; // 从根结点(0)出发
for (int i = 0; str[i]; ++i) {
if (ch[p] == NULL) {
ch[p] = new int[MAX_C]; // 只有 p 当包含子结点的时候才去开辟 ch[p] 的空间
memset(ch[p], -1, sizeof(int) * MAX_C); // 初始化为 -1
}
if (ch[p][str[i] - 'a'] == -1) { // 该子结点不存在
ch[p][str[i] - 'a'] = ++tot; // 新增结点
}
p = ch[p][str[i] - 'a']; // 在 Trie 树上继续插入字符串 str
}
cnt[p]++;
}
int find(char *str) { // 返回字符串 str 的出现次数
int p = 0;
for (int i = 0; str[i]; ++i) {
if (ch[p][str[i] - 'a'] == -1) {
return 0;
}
p = ch[p][str[i] - 'a'];
}
return cnt[p];
}
};
/*
char now[MAX_LEN];
void dfs(int p, int len) {
if (cnt[p] > 0) {
now[len] = '\0';
while (cnt[p] --> 0) {
cout << now << endl;
}
}
for (int i = 0; i < 26; ++i) {
if (ch[p][i]) {
now[len] = 'a' + i;
dfs(ch[p][i], len + 1);
}
}
}
*/
求区间
解法:首选把
#include <iostream>
#include <vector>
using namespace std;
vector<int> breakdown(int x) {
vector<int> l;
for (int i = 2; i * i <= x; ++i) {
int cnt = 0;
while (x % i == 0) {
++cnt;
x /= i;
}
if (cnt) {
l.push_back(i);
}
}
if (x > 1) {
l.push_back(x);
}
return l;
}
int main() {
int a = 10, b = 20, x = 15;
vector<int> list = breakdown(x);
int ans = 0, len = list.size();
for (int i = 0; i < (1 << len); ++i) {
int cnt = 0, pp = 1;
for (int j = 0; j < len; ++j) {
if (i & (1 << j)) {
++cnt;
pp *= list[j];
}
}
ans += (b / pp - (a - 1) / pp) * ((cnt & 1) ? -1 : 1);
}
cout << ans << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Arbitrary_change(ll n,int m){
char s[100];
int i;
for(i=0;n>0;i++){
if(n%m<10){
s[i] = n%m + '0';
}else{
s[i] = n%m - 10 + 'A';
}
n /= m;
}
ll cnt = 0;
for(n=i;n>0;n--){
cnt = cnt * 10 + (s[n-1] - '0');
}
return cnt;
}
ll Ten_change(int n,string str){
ll ans = 0, sum = 1;
for(int i = str.length(); i > 0; i--){
if(str[i-1] >='A') ans = ans + (str[i - 1] - 'A'+10) * sum;
else ans = ans + (str[i - 1] - '0') * sum;
//cout<<ans<<endl;
sum *= n;
}
return ans;
//printf("%d\n", ans);
}
int main() {
int T;
cin>>T;
string x;
ll ans;
while(T--){
cin>>x;
ans = 0;
for(int i=2;i<=10;i++){
ans += Ten_change(i, x);
}
cout<<ans<<endl;
}
return 0;
}
1.简介:
Java中两个类BigDecimal(表示浮点数)和BigInteger(表示整数);
分别表示不可变的任意精度的整数和不可变的有符号的任意精度的十进制数(浮点数)。
主要用于高精度计算中。这两个类使得java中的大数,高精度运算变得很简单。
使用时注意每个单词首字母大写~新手很容易犯这个错/(ㄒoㄒ)/~~
使用这两个类的时候需要加上包 import java.math.*;
或是直接打:
import java.math.BigInteger;
import java.math.BigDecimal;
2.声明与赋值
通常以这种方法声明:
BigInteger a;
BigDecimal b;
也可将声明和赋值写在一起:
BigDecimal a=new BigDecimal("0");
还有常用的常量赋值方法:
A=BigInteger.ONE //=1
B=BigInteger.TEN //=10
C=BigInteger.ZERO //=0
相当于:
BigInteger A = BigInteger.valueOf(1);
BigInteger B = BigInteger.valueOf(10);
BigInteger C = BigInteger.valueOf(0);
具体用法如下;
int a = 3;
BigInteger b = BigInteger.valueOf(a);
//即b = 3;(int)
2.输入方法:
例:
while(cin.hasNext()) //等同于!=EOF
{
int n;
BigInteger m;
n=cin.nextInt(); //读入一个int;
m=cin.BigInteger();//读入一个BigInteger;
System.out.print(m.toString());
System.out.print(m);
}
3.一些基础运算:
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
BigInteger a, b;
int T;
Scanner in = new Scanner(System.in);
//Scanner cin = new Scanner(new BufferedInputStream(System.in));
T = in.nextInt();
for (int i = 1; i <= T; ++i) {
System.out.println("Case" + " " + i + ":");
a = in.nextBigInteger();
b = in.nextBigInteger();
if (i < T) {
System.out.println(a + " + " + b + " = " + a.add(b) );
System.out.println();
} else {
System.out.println(a + " + " + b + " = " + a.add(b));
}
}
}
}
a+b浮点数的例子:
import java.util.*;
import java.math.*;
public class Main{
public static void main(String []args){
BigDecimal a;
BigDecimal b;
a=new BigDecimal("0");
b=new BigDecimal("0");
Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
a=cin.nextBigDecimal();
b=cin.nextBigDecimal();
a=a.add(b);
String str=a.stripTrailingZeros().toPlainString();
//stripTrailingZeros()这个方法是用来去掉末尾的0的。
//toPlainString()这个方法是使字符串大数变成普通的数字字符组成的字符串,
//如果不使用这个方法很可能数字变成了科学计数法,带E的那种。
System.out.println(str);
}
}
}
Maven进行管理
<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<maven.compiler.source>1.7</maven.compiler.source>
<maven.compiler.target>1.7</maven.compiler.target>
<!--定义hadoop版本-->
<hadoop.version> 2.6.0-cdh5.15.1</hadoop.version>
</properties>
<!--引入cdh的仓库-->
<repositories>
<repository>
<id>cloudera</id>
<url>https://repository.cloudera.com/artifactory/cloudera-repos</url>
</repository>
</repositories>
<dependencies>
<!--添加hadoop依赖包-->
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-client</artifactId>
<version>${hadoop.version}</version>
</dependency>
<!--添加junit依赖包-->
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.11</version>
<scope>test</scope>
</dependency>
</dependencies>
Hadoop:提供分布式的存储(一个文件被拆分成很多个块,并且以副本的方式存储在各个节点中)和计算,是一个分布式的系统基础架构:用户可以在不了解分布式底层细节的情况下进行使用。
分布式文件系统:HDFS实现将文件分布式存储在很多的服务器上
分布式计算框架:MapReduce实现在很多机器上分布式并行计算
分布式资源调度框架:YARN实现集群资源管理以及作业的调度
常用的Hadoop发行版
Apache
优点:纯开源
缺点:不同版本/不同框架之间整合,常有jar冲突
优点:cm(cloudera manager) 通过页面一键安装各种框架
缺点:cm不开源、与社区版本有些出入
Hortonworks:HDP 企业发布自己的数据平台可以直接基于页面框架进行改造
优点:原装Hadoop、纯开源、支持tez
缺点:企业级安全不开源
解决单源最短路径问题常用 Dijkstra 算法,用于计算一个顶点到其他所有顶点的最短路径。Dijkstra 算法的主要特点是以起点为中心,逐层向外扩展(这一点类似于 bfs,但是不同的是,bfs 每次扩展一个层,但是 Dijkstra 每次只会扩展一个点),每次都会取一个最近点继续扩展,直到取完所有点为止。
注意:Dijkstra 算法要求图中不能出现负权边。
我们定义带权图$ G
从
并用
重复步骤 1 和 2,直到
如果最后
Dijkstra 算法的时间复杂度为$ \mathcal{O}(V^2)$,其中
Dijkstra 是解决无负边权的图的单源最短路问题,经常使用邻接表存储。
不优化的时间复杂度是
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, fail;
edge() {}
edge(int _v, int _w, int _fail) {
v = _v;
w = _w;
fail = _fail;
}
} e[M << 1];
int head[N], len;
void init() {
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w) {
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void dijkstra(int u) {
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
for (int i = 0; i < n; ++i) {
int mi = inf;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] < mi) {
mi = dis[u = j];
}
}
if (mi == inf) {
return;
}
vis[u] = true;
for (int j = head[u]; ~j; j = e[j].fail) {
int v = e[j].v;
int w = e[j].w;
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}
int main() {
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
add2(u, v, w);
}
dijkstra(1);
cout << dis[n] << endl;
return 0;
}
用一个set来维护点的集合,这样的时间复杂度就优化到了
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
min_heap.insert(make_pair(0, s));
dist[s] = 0;
for (int i = 0; i < n; ++i) {
if (min_heap.size() == 0) { // 如果小根堆中没有可用顶点,说明有顶点无法从源点到达,算法结束
return false;
}
// 获取堆顶元素,并将堆顶元素从堆中删除
set<PII, less<PII> >::iterator iter = min_heap.begin();
int v = iter->second;
min_heap.erase(*iter);
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
// 先将对应的 pair 从堆中删除,再将更新后的 pair 插入堆
min_heap.erase(make_pair(dist[x], x));
dist[x] = dist[v] + e[j].w;
min_heap.insert(make_pair(dist[x], x));
}
}
}
return true; // 存储单源最短路的结果
}
我们在
这个代码的时间复杂度实际上会比用真正的堆要慢一点,因为有的点可能会入队多次,但是每一条边最多导致一次入队,所以这个算法的时间复杂度为
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int w) { // 插入带权有向边
e[eid].v = v;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void insert2(int u, int v, int w) { // 插入带权双向边
insert(u, v, w);
insert(v, u, w);
}
int dist[MAX_N]; // 存储单源最短路的结果
bool vst[MAX_N]; // 标记每个顶点是否在集合 U 中
struct node {
int u;
int dist;
node(int _u, int _dist) : u(_u), dist(_dist) {}
bool operator < (const node &x) const {
return dist > x.dist;
}
}; // 记录点的结构体
bool dijkstra(int s) {
// 初始化 dist、小根堆和集合 U
memset(vst, 0, sizeof(vst));
memset(dist, 0x3f, sizeof(dist));
priority_queue<node> min_heap;
dist[s] = 0;
min_heap.push(node(s, 0));
while (!min_heap.empty())
// 获取堆顶元素,并将堆顶元素从堆中删除
int v = min_heap.top().u;
min_heap.pop();
if (vst[v]) {
continue;
}
vst[v] = true;
// 进行和普通 dijkstra 算法类似的松弛操作
for (int j = p[v]; j != -1; j = e[j].next) {
int x = e[j].v;
if (!vst[x] && dist[v] + e[j].w < dist[x]) {
dist[x] = dist[v] + e[j].w;
min_heap.push(node(x, dist[x]));
}
}
}
return true;
}
SPFA(Shortest Path Faster Algorithm)算法是单源最短路径的一种算法,通常被认为是 Bellman-ford 算法的队列优化,在代码形式上接近于宽度优先搜索 BFS,是一个在实践中非常高效的单源最短路算法。
在
1.初始队列中仅包含源点,且源点
2.取出队列头顶点
将
若
将
3.重复步骤 2 直到队列为空
最终$ d$ 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct edge{
int v, w, fail;
edge(){}
edge(int _v, int _w, int _fail){
v = _v;
w = _w;
fail = _fail;
}
}e[M << 1];
int head[N], len;
void init(){
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w){
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
void add2(int u, int v, int w){
add(u, v, w);
add(v, u, w);
}
int n, m;
int dis[N];
bool vis[N];
void spfa(int u){
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty()){
u = q.front();
q.pop();
vis[u] = false;
for(int j = head[u];~j;j = e[j].fail){
int v = e[j].v;
int w = e[j].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
int main() {
init();
int u, v, w;
cin>>n>>m;
while(m--){
cin>>u>>v>>w;
add2(u, v, w);
}
spfa(1);
cout<<dis[n]<<endl;
return 0;
}
但是
memset(in, 0, sizeof in);
in[u] = 1;
// 修改入队部分的操作
if(!vis[v]){
q.push(v);
vis[v] = true;
++in[v];
if(in[v] > n){
return true;
}
}
int g[N][N];
void floyd(int n) {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
1、下载virtualenv
pip install virtualenv
2、创建一个virtualenv工作目录
mkdir myproject_env
3、穿件一个python项目
virtualenv venv
4、启动virtualenv中的venv项目
cd venv\Scripts
activate
5、关闭virtualenv
需要在venv\Scripts内
deactivate
国内源:
新版ubuntu要求使用https源,要注意。
清华:https://pypi.tuna.tsinghua.edu.cn/simple
阿里云:http://mirrors.aliyun.com/pypi/simple/
**科技大学 https://pypi.mirrors.ustc.edu.cn/simple/
华中理工大学:http://pypi.hustunique.com/
山东理工大学:http://pypi.sdutlinux.org/
豆瓣:http://pypi.douban.com/simple/
临时使用:
可以在使用pip的时候加参数-i https://pypi.tuna.tsinghua.edu.cn/simple
例如:pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pyspider,这样就会从清华这边的镜像去安装pyspider库。
永久修改,一劳永逸:
Linux下,修改 ~/.pip/pip.conf (没有就创建一个文件夹及文件。文件夹要加“.”,表示是隐藏文件夹)
内容如下:
[global]
index-url = https://pypi.tuna.tsinghua.edu.cn/simple
[install]
trusted-host=mirrors.aliyun.com
windows下,直接在user目录中创建一个pip目录,如:C:\Users\xx\pip,新建文件pip.ini。内容同上。
第一步
将虚拟机中的网络模式改为net模式
第二步
在root权限下,进入vi/etc/hosts,将里面的地址更改为你自己定义的地址
你自己定义的地址 hadoop
127.0.0.1 localhost
网关查询方式:①、windows下 cmd下 ipconfg中的VMnet8有一个ipv4地址,网关是此地址最后一位改成2
②、也可在虚拟机中的编辑(左上角)中的虚拟网络编辑器,点击第二行VMnet8,然后点击 NAT设置,可以看到自己的网关和子网掩码
第三步
vi /etc/sysconfig/network #将里面的hostname更改为hadoop或其他名称
更改的名字与第二步中更改的名字相同
vi /etc/hosts #你自定义的地址 空格 你上面定义的名字
第四步
root权限下
# cd /etc/sysconfig/network-scripts
# vi ifcfg-etho
更改几个参数:
①、HWADDR:你当前机子的mac地址(ip addr中可以查找到)
②、CNBOOT = yes(若无请自己添加)
③、IPADDR(改成你之前自定义的地址)
④、GATEWAY(改成你虚拟机的网关)
⑤、DNS1 = 8.8.8.8, DNS0 = 114.114.114.114
第五步
关闭防火墙(仅centos7下适用)
# systemctl stop firewalld
# systemctl disable firewalld
第六步
reboot重启
本搭建适用的Hadoop相关版本:CDH
CDH相关软件包下载地址:http://archive.cloudera.com/cdh5/cdh/5/
Hadoop使用版本:hadoop-2.6.0-cdh5.15.1
Hadoop下载:wget http://archive.cloudera.com/cdh5/cdh/5/hadoop-2.6.0-cdh5.15.1.tar.gz
Hive使用版本:hive-1.1.0-cdh5.15.1
hadoop安装前置要求
Java 1.8+
ssh
hadoop-env.sh
export JAVA_HOME=/home/hadoop/app/jdk1.8.0_91
core-site.xml
<property>
<name>fs.defaultFS</name>
<value>hdfs://hadoop000:8020</value>
</property>
hdfs-site.xml
<property>
<name>dfs.replication</name>
<value>1</value>
</property>
<property>
<name>hadoop.tmp.dir</name>
<value>/home/hadoop/app/tmp</value>
</property>
slaves
hadoop000
启动hdfs
第一次执行的时候一定要格式化文件系统,不要重复执行: hdfs namenode -format
启动集群:$HADOOP_HOME/sbin/start-dfs.sh
如果发现jps ok,但是浏览器不OK? 十有八九是防火墙问题
查看防火墙状态:sudo firewall-cmd --state
关闭防火墙: sudo systemctl stop firewalld.service
hadoop软件包常见目录说明
bin:hadoop客户端名单
etc/hadoop:hadoop相关的配置文件存放目录
sbin:启动hadoop相关进程的脚本
share:常用例子
hadoop fs [generic options]
[-appendToFile ... ]
[-cat [-ignoreCrc] ...]
[-chgrp [-R] GROUP PATH...]
[-chmod [-R] <MODE[,MODE]... | OCTALMODE> PATH...]
[-chown [-R] [OWNER][:[GROUP]] PATH...]
[-copyFromLocal [-f] [-p] [-l] ... ]
[-copyToLocal [-p] [-ignoreCrc] [-crc] ... ]
[-count [-q] [-h] [-v] [-x] ...]
[-cp [-f] [-p | -p[topax]] ... ]
[-df [-h] [ ...]]
[-du [-s] [-h] [-x] ...]
[-get [-p] [-ignoreCrc] [-crc] ... ]
[-getmerge [-nl] ]
[-ls [-C] [-d] [-h] [-q] [-R] [-t] [-S] [-r] [-u] [ ...]]
[-mkdir [-p] ...]
[-moveFromLocal ... ]
[-moveToLocal ]
[-mv ... ]
[-put [-f] [-p] [-l] ... ]
[-rm [-f] [-r|-R] [-skipTrash] ...]
[-rmdir [--ignore-fail-on-non-empty]
hadoop常用命令:
hadoop fs -ls /
hadoop fs -put
hadoop fs -copyFromLocal
hadoop fs -moveFromLocal
hadoop fs -cat
hadoop fs -text
hadoop fs -get
hadoop fs -mkdir
hadoop fs -mv 移动/改名
hadoop fs -getmerge
hadoop fs -rm
hadoop fs -rmdir
hadoop fs -rm -r
1、复制源文件备份,进入目录/etc/apt下,备份sources.list文件
sources.list是包管理工具apt所用的记录软件包仓库位置的配置文件
# sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak
2、编译源列表文件
# sudo vim /etc/apt/sources.list
如果报错:sudo:vim:command not found,说明没装vim编辑器
3、查看新版本信息
# lsb_release -c
有些网上的方案不同,和更改apt安装源时用的系统不一样有关
4、将原有的内容注释掉,添加以下内容(也可以全部删除)
deb http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-security main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-updates main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-backports main restricted universe multiverse
deb http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
deb-src http://mirrors.aliyun.com/ubuntu/ bionic-proposed main restricted universe multiverse
5、更新软件列表
# sudo apt-get update
6、更新软件包
# sudo apt-get upgrade
HTTP的工作原理
HTTP协议采用请求/响应模型。客户端向服务器发送一个请求报文,服务器以一个状态作为响应。
以下是HTTP请求/响应的步骤:
例如,在浏览器地址栏键入URL,按下回车键后会经历以下流程:
1.浏览器向DNS服务器请求解析该URL中域名所对应的IP地址。
2.解析出IP地址后,根据该IP地址和默认端口80,同服务器建立TCP连接。
3.浏览器发出读取文件(URL中域名后面部分对应的文件)的HTTP请求,该请求报文作为TCP三次握手的第三个报文的数据发送给服务器。
4.服务器对浏览器请求做出响应,并把对应的HTML文本发送给浏览器。
5.释放TCP连接。
6.浏览器将该HTML文本并显示内容。
1.下载winutils.exe文件
1)下载 winutils.exe,地址为:
http://social.msdn.microsoft.com/Forums/windowsazure/en-US/28a57efb-082b-424b-8d9e-731b1fe135de/please-read-if-experiencing-job-failures?forum=hdinsight
2) 把这个文件放进 d:\winutil\bin
3) mapreduce的代码中添加这段,System.setProperty("hadoop.home.dir", "d:\winutil\")
2.这个空指针问题解决后,会有一个nativeIO问题,下载Native.java,在项目中创建一个包(package),名字最好取成org.apache.hadoop.io.nativeio,然后将NativeIO.java文件粘贴进去
特点:属于一种全家桶式的框架,在架构上很特别,都是基于插件式的增量开发模式,而且其并行运行能力非常出众
优点:
缺点:
当前只说明windows下Scrapy的安装过程
若直接安装
c:\pip install scrapy
很大可能会出现
Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": http://landinghub.visualstudio.com/visual-cpp-build-tools
上面的错误
因此我们按照下面步骤来进行安装
1.安装Wheel
c:\ pip install wheel
2.安装Twisted
https://www.lfd.uci.edu/~gohlke/pythonlibs/
去上面的链接中查找与自己操作系统以及Python版本相符的Twisted安装包,下载后进入whl文件所在路径执行以下命令
c:\pip install Twisted‑19.2.0‑cp37‑cp37m‑win_amd64.whl
(此处若失败可以尝试一下win32)
3.安装scrapy
在上面链接中找到scrapy的whl包下载,并安装
c:\pip install Scrapy-1.6.0-py2.py3-none-any.whl
完成安装后再命令行执行:
c:\scrapy -h
如果正常输出了scrapy的命令帮助信息则说明安装成功
4.运行scrapy项目
如果安装完成后运行scrapy项目报以下错误
no module named win32api
则表示Windows系统中,python因为原生并不能访问windows的api,所以需要额外安装pypiwin32库
pip install pypiwin32
我们可以通过scrapy内置的startproject
指令来快速构建scrapy
项目
startproject
的指令模式如下:
$ scrapy startscrapy startproject <项目名称>
项目必须以英文开头,多个单词之间可以用下划线(_
)为连接符,切记不要采用-
,否则会报错
当startproject
被成功执行后,将会在控制台看到以下的输出信息
New Scrapy project 'my_crawler', using template directory '/Users/ray/Projects/scrapy-courses/venv/lib/python3.7/site-packages/scrapy/templates/project', created in:
/Users/ray/Projects/scrapy-courses/my_crawler
You can start your first spider with:
cd my_crawler
scrapy genspider example example.com
意思是我们可以进入创建的项目的目录并执行scrapy genspider 项目名 目标网站
创建scrapy项目中的爬虫类。在此之前先让我们来了解以下startproject
指令为我们创建的哪些的文件,目录以及它们的作用是什么
展开“my_crawler”目录可以看到以下的目录结构:
my_crawler
├── my_crawler # 爬虫项目包目录
│ ├── __init__.py
│ ├── items.py # Item定义文件
│ ├── middlewares.py # 自定义中间件
│ ├── pipelines.py # 自定义管道
│ ├── settings.py # 项目配置文件
│ └── spiders # 蜘蛛类的存放目录
│ └── __init__.py
└── scrapy.cfg # Scrapy 运行配置
Scrapy给我们提供了两种类型的命令:项目命令(Project-specific)需要进入项目目录执行才可生效,全局命令则不需要进入项目。
所有的命令行工具都会以以下的调用格式提供:
$ scrapy <命令> [选项] [参数]
全局指令
Scrapy提供的全局命令主要包括以下这些:
scrapy startproject <项目名>
- 初始化爬虫项目,创建基本目录与必要的文件scrapy settings --get <配置项的名称>
- 在项目中运行时,该命令将会输出项目的设定值,否则输出Scrapy默认设定scrapy runspider <spider_file.py>
- 在未创建项目的情况下,运行一个编写在Python文件中的spiderscrapy shell
- 以给定的URL启动Scrapy指令外壳,可以在命令行中直接操作scrapy内置的python对象(也可以借助pycharm的调试器看到)scrapy fetch
- 初始化爬虫项目,创建基本目录与必要的文件使用Scrapy下载器(downloader)下载给定的URL,并将获取到的内容打印到控制台上scrapy view <项目名>
- 在浏览器中打开给定的URL,并用一个Scrapy spider获取目标URL并将结构显示到浏览器中scrapy version <-v>
- 输出Scrapy版本,配合-v运行时,该命令同时输出Python,Twisted以及平台的信息,方便bug提交出了startproject
是常用命令之外,只有fetch
和view
指令比较有用,其他的指令作用不大
项目命令
scrapy crawl <蜘蛛名>
- 使用指定的蜘蛛执行爬取scrapy genspider
- 在当前项目中创建spider。这仅仅是创建spider的一种快捷方法。该方法可以是使用提前定义好的模板来生成spider。scrapy list
- 列出当前项目中有多少个可用的蜘蛛(不实用)scrapy check [-l] <蜘蛛名>
- 运行contract检查。(无实际意义,不推荐使用)scrapy edit <蜘蛛名>
- 启用一个IDE编辑蜘蛛scrapy deploy [target:project | -l | -L]
- 将项目部署到Scrapyd服务scrapy bench
- 运行benchmark测试A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.