13.树状数组
#include<cstdio>
#include<cstring>
#define lowerBit(x) (x&(-x))
int num[10000];
int n;
void UpDate(int x,int y)//把第x个数加y
{
while (x <= n)
{
num[x] += y;
x = x+lowerBit(x);
}
}
int Query(int x)//求从1到x的和
{
int sum = 0;
while (x > 0)
{
sum += num[x];
x = x-lowerBit(x);//x&(x-1)
}
return sum;
}
int main()
{
scanf ("%d",&n);
memset(num,0,sizeof(num));
for (int i = 1 ; i <= n ; i++)
{
int t;
scanf ("%d",&t);
UpDate(i,t);
}
int m;
scanf ("%d",&m);
while (m--)
{
int x,y;
scanf ("%d %d",&x,&y);//看不懂
printf ("%d
",Query(y)-Query(x-1));
}
return 0;
}
14.线段树//看不懂
struct Node//不要左右子节点指针的做法
{
int L,R;
int minV,maxV;
int Mid()
{
return (L+R)/2;//还有这操作
}
};
Node tree[800010];//4倍叶子节点数量就够
void BuildTree(int root, int L, int R)
{
tree[root].L = L;
tree[root].R = R;
tree[root].minV = INF;//这是为什么？到底哪个是大的
tree[root].maxV = -INF;//那个是小的？
if(L!=R)
{
BuildTree(2*root+1, L, (L+R)/2);
BuildTree(2*root+2, (L+R)/2+1, R);
}
}
void Insert(int root, int i, int v)
//将第i个数，其值为v，插入线段树
{
if(tree[root].L == tree[root].R)//成立则亦有tree[root].R==i
{
tree[root].minV = tree[root].maxV = v;
return ;
}
tree[root].minV = min(tree[root].minV , v);
tree[root].maxV = max(tree[root].maxV , v);
if(i <= tree[root].Mid())
Insert(2*root + 1, i, v);
else
Insert(2*root + 2, i, v);
}
void Query(int root, int s, int e)
//查询区间[s,e]中的最大值和最小值，如果更优就记录在全局变量里
{
if( tree[root].minV >= minV && tree[root].maxV <= maxV )
return;
if( tree[root].L == s && tree[root].R == e )
{
minV = min( minV, tree[root].minV );
//minV = min( minV, tree[root].minV );
maxV = max( maxV, tree[root].maxV );
return ;
}
if( e <= tree[root].Mid() )
Query( 2*root + 1, s, e );
else if( s > tree[root].Mid() )
Query( 2*root + 2, s, e );
else
{
Query( 2*root + 1, s, tree[root].Mid() );
Query( 2*root + 2, tree[root].Mid() + 1, e );
}
}
15.KMP
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//S: a b a b b a b a b a d a b a b a a a b a b a a
// j
// T: a b a b a a a b a b a a
// next :-1 0 0 1 2 3 1 1 2 3 4 5
char s[1000], t[1000];
int next[1000] = {-1, 0, 0, 1, 2, 3, 1, 1, 2, 3, 4, 5};
int Kmp(char* s, int n, char* t, int m) {
int i = 0, j = 0;
while(i < n) {
if(j == -1 || s[i] == t[j]) {
++i; ++j;
if(j == m) {
return i - m + 1;
}
}
else {
j = next[j];
}
}
return -1;
}
int main()
{
//ababababadababaaababaa
//ababaaababaa
//ababcabcacbab
//abc
scanf("%s%s", s, t);
int l1 = strlen(s);
int l2 = strlen(t);
printf("第一个匹配的位置%d
", Kmp(s, l1, t, l2));
return 0;
}
//next[i]: 0 -> i-1 最大的前缀和后缀匹配的长度 0 -> n-1
//S: a b a b b a b a b a d a b a b a a a b a b a a
//T: a b a b a a a b a b a a
// -1 0 0 1 2 3 1 1 2 3 4 5
//从头选择next[j]个字符和从尾向前选择next[j]个字符是相等的
//
//1>, S串和T串前面这些字符是相等的
//2>, T串前面字符有next[j]前缀和后缀匹配的长度
16.二分图
这个算法的主要思想还是“递归”，通过递归腾出位置来让更多的人匹配，以达到匹配人数最大化
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[500+5]; //女和哪个男配对
bool fr[505][505]; //可用vector<int> d[505]代替
bool vis[505]; //标记数组，表示这个人搜索过
int k,n,m;
bool find(int x) //寻找x男生，返回：能否找到人去匹配
{
for (int i = 1 ; i <= m ; i++)
{
if (fr[x][i] && !vis[i])
{
vis[i] = true; //首先标记
if (f[i] == -1) //如果该女生没有和别人匹配
{
f[i] = x; //则和该男生匹配
return true; //表示匹配完成
}
else if (find(f[i])) //如果该女生匹配的男生可以找到其他的女生匹配
{
f[i] = x;//递归的思想
return true;
}
}
}
return false;
}
int main()
{
while (~scanf ("%d",&k) && k)
{
scanf ("%d %d",&n,&m);
memset(f,-1,sizeof(f)); //初始化，表示没有和任何人配对
memset(fr,false,sizeof(fr)); //初始化
for (int i = 1 ; i <= k ; i++)
{
int x,y;
scanf ("%d %d",&x,&y);
fr[x][y] = true;
}
int ans = 0; //表示已经配对的男生数
for (int i = 1 ; i <= n ; i++)
{
memset(vis,false,sizeof(vis));
if (find(i))
ans++;
}
printf ("%d
",ans);
}
return 0;
}
17.字典树模板
1 #include<cstdio> 2 #include<cstring> 3 #define idx(x) (x-'a') 4 struct Node 5 { 6 int v; 7 Node *next[26]; //指向某个节点，作为其子节点之一 8 void init() 9 { 10 v = 0; //当前节点有多少人公用 11 for (int i = 0 ; i < 26 ; i++) 12 next[i] = NULL; 13 } 14 }Trie[100000]; //事先把内存分配好了 15 int ant; //下一个节点要保存到的位置 16 void insert(char str[]) 17 { 18 Node *p = &Trie[0]; //现在执行到的节点 19 int l = strlen(str); 20 for (int i = 0 ; i < l ; i++) 21 { 22 if (p->next[idx(str[i])] == NULL) 23 { 24 p->next[idx(str[i])] = &Trie[ant]; 25 ant++; 26 Trie[ant].init(); //随手初始化下一个节点 27 Trie[ant-1].v = 1; 28 p = &Trie[ant-1]; 29 } 30 else 31 { 32 p->v++; 33 p = p->next[idx(str[i])]; 34 } 35 } 36 } 37 38 int Query(char str[]) //char *str 39 { 40 int length = 0; 41 Node p = Trie[0]; 42 int l = strlen(str); 43 for (int i = 0 ; i < l ; i++) 44 { 45 if (p.next[idx(str[i])] == NULL) //到此节点没有公共前缀的串了 46 { 47 break; 48 } 49 else 50 { 51 length++; 52 p = *p.next[idx(str[i])]; 53 } 54 } 55 return length; 56 } 57 58 int main() 59 { 60 int n,m; 61 char str[20]; 62 while (~scanf ("%d %d",&n,&m)) 63 { 64 ant = 1; 65 Trie[ant].init(); 66 for (int i = 1 ; i <= n ; i++) 67 { 68 scanf ("%s",str); 69 insert(str); //建树 70 } 71 for (int i = 1 ; i <= m ; i++) 72 { 73 scanf ("%s",str); //m次查询，查str的最长公共前缀 74 printf ("%d ",Query(str)); 75 } 76 } 77 return 0; 78 } 79 /* 80 3 5 81 abac 82 abcd 83 accc 84 85 a 86 ab 87 abe 88 bc 89 aca 90 91 92 */