青岛区域赛备战--模板及复习--简单算法

青岛区域赛备战—模板及复习—简单算法

1、快速幂
2、LIS及其变形

快速幂

1
2
3
4
5
6
7
LL Pow(LL a, LL n, LL mod)
{
LL t = 1;
for (; n; n >>= 1, a = (a * a % mod))
if (n & 1) t = (t * a % mod);
return t;
}

LIS

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

int a[100100],ans[100100];
int LIS(int n){
ans[0]=a[0];
int len=1;
for(int i=1;i<n;i++){
if(a[i]>ans[len-1])
ans[len++]=a[i];
else{
int pos=lower_bound(ans,ans+len,a[i])-ans; //在答案里找第一个比a[i]大的位置
ans[pos]=a[i];
}
}
return len;
}
在从小到大的排序数组中,

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

点分治

点分治还是很有意思的,不过自己看博客还是比较吃力的,看了好久。
基本思想:
找一颗树上的重心(所有以此点为根的子树中最大子树最小的那个根结点)
分治解决。(这是关键。)
详细解释一下:一开始结点数为n,朴素算法O($n^2$),若找重心分治处理就是O($log(n)$)层,每次合并时间是(这里是O(nlog(n)+n) 排序+找最远可行对)不定。
那最终就是O(nlog(n)log(n)).
最终的决定权基本在合并算法的手里,能合并,就能处理。
需要注意的是

1
ans-=solve(v,w);

要减掉没有经过根的点

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<queue>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF=0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int N=10010;
const int M=40010;
int head[N];
int top;
struct Edge
{
int val;
int to;
int next;
}edge[M];
void addedge(int a,int b,int c)
{
edge[top]=Edge{c,b,head[a]};
head[a]=top++;
}
void init()
{
top=0;
memset(head,-1,sizeof(head));
}
int k;
int root,sim[N],S,mxson[N];
int MX,vis[N];
void getroot(int u,int fa){
sim[u]=1;mxson[u]=0;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
int w=edge[i].val;
if(v==fa||vis[v]) continue;
getroot(v,u);
sim[u]+=sim[v];
mxson[u]=max(mxson[u],sim[v]);
}
mxson[u] = max(mxson[u],S-sim[u]);
if(mxson[u]<MX){
MX=mxson[u];
root=u;
}
}
LL ans;
int id;
int dis[N]; //到重心的距离
void getdis(int u,int fa,int dist) //点u到root的距离
{
dis[id++] = dist;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;int w=edge[i].val;
if(v==fa||vis[v]) continue;
getdis(v,u,dist+w);
}
}
int solve(int u,int len){ //排序找符合的点
id=0;
clr(dis,0);
getdis(u,0,len);
sort(dis,dis+id);
int L=0,R=id-1;
int tmp=0;
while(L<R){
if(dis[R]+dis[L]<=k){tmp+=R-L;L++;}
else R--;
}
return tmp;
}
void Divide(int u){
ans+=solve(u,0);
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;int w=edge[i].val;
if(vis[v]) continue;
ans-=solve(v,w);
S=sim[v];root=0;
MX=INF;getroot(v,0);
Divide(root);
}
}
int main()
{
int n;
while(scanf("%d%d",&n,&k),n+k){
init();
int a,b,c;
for(int i=1;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
clr(vis,0);
S=n,MX=INF;
root=0;ans=0;
getroot(1,0);
Divide(root);
printf("%lld\n",ans);
}
return 0;
}

LGV

在这里插入图片描述

注意条件转移。

-------------本文结束-------------