代码模板（new)

1.树状数组：题目：UVA1428

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<string>
 5 #include<cstring>
 6 #include<numeric>
 7 #include<vector>
 8 #include<map>
 9 #include<queue>
10 #include<set>
11 #include<cmath>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int>PII;
15 typedef pair<ll,ll>PLL;
16 
17 //树状数组和线段树是一样的下标均是从1开始的。。。这个一定不能出错。。。
18 
19 const int maxn=1e5+10;
20 
21 int tree[maxn+10];//树状数组。。。
22 int l[maxn+10],r[maxn+10];
23 
24 int lowbit(int x){//求解一个数二进制最后一个1的位置。。。
25     return x&(-x);
26 }
27 //树状数组求和不同于线段树每一次直接拿出来，树状数组的求和有可能每一次要进行加减的操作。。。
28 
29 int sum(int x){//注意x均是tree树状数组的下标。。。
30     int res=0;
31     while(x>0){//通过lowbit找只有最后一个1的数的值，我们只需要确定二进制存在1那么就继续遍历操作。。。
32         res+=tree[x];
33         x-=lowbit(x);//eg:x=7那么之后加上6，之后加上4，之后x为0，跳出循环。。。结束操作。。。
34     }
35     return res;//直接求出和。。
36 }
37 
38 void add(int x,int d){//这一步是增加操作。。。是从树根往上面进行操作。。。
39     while(x<maxn){
40         tree[x]+=d;//将当前的结点加上去。。。是从下往上加的。。。
41         x+=lowbit(x);//x是树的下标。。。
42     }
43 }
44 
45 //l[i],r[i]记录的都是比i位置数字要小的数字的个数。。。
46 
47 int main(){
48     int T;
49     cin>>T;
50     ll ans;
51     while(T--){
52         int a[maxn];
53         int n;
54         cin>>n;
55         for(int i=1;i<=n;i++){
56             cin>>a[i];
57         }
58         memset(tree,0,sizeof(tree));
59         memset(l,0,sizeof(l));
60         for(int i=1;i<=n;i++){
61             l[i]=sum(a[i]);
62             add(a[i],1);//个数均加一
63         }
64         memset(tree,0,sizeof(tree));
65         memset(r,0,sizeof(r));
66         for(int i=n;i>=1;i--){
67             r[i]=sum(a[i]);
68             add(a[i],1);
69         }
70         ans=0;
71         for(int i=2;i<n;i++){
72             ans=ans+l[i]*(n-r[i]-i)+r[i]*(i-1-l[i]);
73         }
74         cout<<ans<<endl;
75     }
76 
77     return 0;
78 }

View Code

2.MST:Kruskal算法。

HDU1863

 1 //题目HDU1863
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<string>
 6 #include<cstring>
 7 #include<numeric>
 8 #include<vector>
 9 #include<map>
10 #include<queue>
11 #include<set>
12 #include<cmath>
13 using namespace std;
14 typedef long long ll;
15 typedef pair<int,int>PII;
16 typedef pair<ll,ll>PLL;
17 
18 //目前只会写kruskal算法就ok啦。
19 
20 
21 
22 const int maxn=111;
23 
24 int father[maxn];
25 int n,m;//村庄个数是m,
26 
27 struct Edge{
28     int from,to;
29     ll cost;
30     bool operator <(const Edge &rhs)const{
31         return cost<rhs.cost;
32     } 
33 }E[maxn*maxn];
34 
35 void init(){
36     for(int i=1;i<=m;i++){
37         father[i]=i;
38     }
39 }
40 
41 int find(int x){
42     return father[x]==x?x:find(father[x]);
43 }
44 
45 void Uni(int a,int b){
46     int f1=find(a);
47     int f2=find(b);
48     if(f1==f2)return;
49     //if(f1>f2)swap(f1,f2);
50     father[f2]=f1;
51 }
52 
53 bool solve(int a,int b){//就是查找是不是同一个父亲，是不是在同一颗树中
54     return find(a)==find(b);
55 }
56 
57 ll kruskal(){
58     ll res=0;
59     sort(E+1,E+n+1);
60     for(int i=1;i<=n;i++){//这里是遍历每一个边。。。
61         if(solve(E[i].from,E[i].to))continue;
62         Uni(E[i].from,E[i].to);
63         res+=E[i].cost;
64     }
65     return res;
66 }
67 
68 int main(){
69     
70     while(cin>>n&&cin>>m){
71         if(n==0)break;
72         init();
73         for(int i=1;i<=n;i++){
74             cin>>E[i].from>>E[i].to>>E[i].cost;
75         }
76         ll res=kruskal();
77         for(int i=1;i<=m;i++){
78             if(!solve(i,1)){
79                 res=-1;
80                 break;
81             }
82         }
83         if(res==-1){
84             cout<<"?"<<endl;
85         }else{
86             cout<<res<<endl;
87         }
88 
89     }
90     return 0;
91 }

View Code

注意数组：

1 int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

View Code

或者：

1 int dir[4][2]={-1,0,1,0,0,1,0,-1};

View Code