[原创]杂（模板）

2016-09-27 15:33:17 Tabris_ 阅读数：785

博客爬取于2020-06-14 22:39:13
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52681216

二维map这么开

map<int,map<int,int>>mmp;map<int,map<int,int> >mmp;

读入优化

1
2
3
4
5
6
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

四国以

printf("%*d",length+1,a[i][j]); //其中*号是位数 对应length是对应位数的数据 +1是数值之前的空格占一位
N!的长度求法N!的长度求法
利用斯特林公式,LL a = 0.5 * log10(2.0 * Pi * n) + n * log10(n * 1.0 / E) + 1;
Wiki链接

求逆序对数

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
int sum[N];
# define lowbit(x) (x&-x)
void update(int index,int val){for(int i=index;i<N;i+=lowbit(i))sum[i]+=val;}
int  getSum(int index){int ans=0;for(int i=index;i;i-=lowbit(i))ans+=sum[i];return ans;}

int a[N],b[N];

int findi(int *a,int len,int n){
    int l = 1,r = len,mid,ans=-1;
    while(l<=r){
        mid = (l+r)>>1;
        if(a[mid]>=n){
            ans = mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        LL ans = 0;
        Rep(i,1,n) a[i]=read(),sum[i]=0,b[i]=a[i];

        sort(b+1,b+n+1);
        int len = unique(b+1,b+n+1)-b-1;

        Per(i,n,1){
            int id = findi(b,len,a[i]);
            ans+=getSum(id);
            update(id,1);
        }
        printf("%d\n",ans);

    }
    return 0;
}

最长上升子序列相关

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
# include <iostream>
# include <algorithm>
# include <cmath>
# include <cstdio>
# include <cstring>
using namespace std;

typedef long long int LL ;

const LL MOD = 1e9+7;
const LL INF = 0xffffffff;
const int N  = 1e5+7;

int a[N];
int b[N]; //为以a[i]为结尾的最长上升子序列的长度
int c[N];

int findi(int *a,int len,int n)//若返回值为x,则a[x]>=n>a[x-1]
{
    int left=0,right=len,mid=(left+right)/2;
    while(left<=right){
        if(n>a[mid]) left=mid+1;
        else if(n<a[mid]) right=mid-1;
        else return mid;
        mid=(left+right)/2;
    }
    return left;
}

void filli(int *a,int n){
    for(int i=0;i<=n;i++)
        a[i]=1e9+7;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);

        filli(c,n+1);

        int i,j;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);

        c[0]=-1;
        c[1]=a[0];
        b[0]=1;
        for(i=1;i<n;i++){
            j=findi(c,n+1,a[i]);
            c[j]=a[i];
            b[i]=j;
        }

        printf("%d",b[0]);
        for(i=1;i<n;i++)
            printf(" %d",b[i]);
        puts("");
    }
    return 0;
}

单调队列 专题链接

1.单调队列：在一个双端对列中维护最后解的方法；

一般适用于：
在一个动态的范围内 对于一个限定长度的子区间进行处理最优解的过程
[解决浮动窗口的最优解]

注意： 顾名思义 一定要保证队列中元素的单调性

1
2
3
4
5
6
7
8
9
10
11
12
int deq[] ；//队列实体
int p[] ；//维护下标

int head =1，tail = 0； //用于维护双端对列的左右值、。

p[0]=p[++r]=0;//其实P[0] 是没有用的。。

while(l<=r && p[l] < i-k) l++;  //不满足子区间长度的需要出队列
tem =  当前最优解 ; //  一定要在更新之前计算  否则结果可能因为负值or other 出现错误
if( tem > mx )    mx=tem，以及需要进行的操作 ;
while(l<=r && 最优解需要的条件) r--;//更新最优解
p[++r]=i;

康拓展开 转自

康托展开

练习题目：NYOJ 139
　　>康托展开的公式是 X=an*(n-1)!+an-1*(n-2)!+…+ai*(i-1)!+…+a21!+a10! 其中，ai为当前未出现的元素中是排在第几个（从0开始）。
　　>这个公式可能看着让人头大，最好举个例子来说明一下。例如，有一个数组 s = [“A”, “B”, “C”, “D”]，它的一个排列 s1 = [“D”, “B”, “A”, “C”]，现在要把 s1 映射成 X。n 指的是数组的长度，也就是4，所以
X(s1) = a43! + a32! + a21! + a10!
关键问题是 a4、a3、a2 和 a1 等于啥？
a4 = “D” 这个元素在子数组 [“D”, “B”, “A”, “C”] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，“C” 是第2大的元素，"D"是第3大的元素，所以 a4 = 3。
a3 = “B” 这个元素在子数组 [“B”, “A”, “C”] 中是第几大的元素。"A"是第0大的元素，"B"是第1大的元素，“C” 是第2大的元素，所以 a3 = 1。
a2 = “A” 这个元素在子数组 [“A”, “C”] 中是第几大的元素。"A"是第0大的元素，"C"是第1大的元素，所以 a2 = 0。
a1 = “C” 这个元素在子数组 [“C”] 中是第几大的元素。“C” 是第0大的元素，所以 a1 = 0。（因为子数组只有1个元素，所以a1总是为0）
所以，X(s1) = 33! + 12! + 01! + 00! = 20

A B C | 0
A C B | 1
B A C | 2
B C A | 3
C A B | 4
C B A | 5

通过康托逆展开生成全排列

练习题目：HDU 1027
　　如果已知 s = [“A”, “B”, “C”, “D”]，X(s1) = 20，能否推出 s1 = [“D”, “B”, “A”, “C”] 呢？
　　因为已知 X(s1) = a43! + a32! + a21! + a10! = 20，所以问题变成由 20 能否唯一地映射出一组 a4、a3、a2、a1？如果不考虑 ai 的取值范围，有
33! + 12! + 01! + 00! = 20
23! + 42! + 01! + 00! = 20
13! + 72! + 01! + 00! = 20
03! + 102! + 01! + 00! = 20
03! + 02! + 201! + 00! = 20
等等。但是满足 0 <= ai <= n-1 的只有第一组。可以使用辗转相除的方法得到 ai，如下图所示：

知道了a4、a3、a2、a1的值，就可以知道s1[0] 是子数组[“A”, “B”, “C”, “D”]中第3大的元素 “D”，s1[1] 是子数组 [“A”, “B”, “C”] 中第1大的元素"B"，s1[2] 是子数组 [“A”, “C”] 中第0大的元素"A"，s[3] 是子数组 [“C”] 中第0大的元素"C"，所以s1 = [“D”, “B”, “A”, “C”]。
这样我们就能写出一个函数 Permutation3()，它可以返回 s 的第 m 个排列。

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
# include<iostream>
# include<algorithm>
# include<vector>
# include<cstdlib>
using namespace std;
class cantor{
public:
    int n;//字符串的长度
    string s;
    int pos;//字符串在全排列中的字典位置，从0开始
    vector<int>num;//所有的字符
    cantor(string s):s(s){n=s.size();}
    cantor(int n,int pos):n(n),pos(pos){
        int i;
        for(i=0;i<n;i++)
            num.push_back(i);
    }
    int fac(int);
    void encode();
    void decode();

};
int cantor::fac(int num){
    if(num==0) return 1;
        else return num*fac(num-1);
}
void cantor::encode(){
    int i,j,count;
    vector<int>vec(n);
    for(i=0;i<n;i++){
        count=0;
        for(j=i;j<n;j++)
            if(s[i]>s[j]) count++;
        vec[n-i-1]=count;
                }
    pos=0;
    for(i=0;i<s.size();i++)
        pos+=vec[i]*fac(i);
}
void cantor::decode(){
    int i;
    div_t divresult;
    for(i=n-1;i>=0;i--){
        divresult=div(pos,fac(i));求余数与除数
        s.push_back(num[divresult.quot]+'0');
        num.erase(num.begin()+divresult.quot);
        pos=divresult.rem;
            }
}
int main(){
    cantor test(4,2);
    test.decode();
    cout<<test.s<<endl;
}
/****************************************/
///这是我自己撸的  比上面的容易看的多
int jiecheng[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int a[10],b[10];

int Cantor_expansion(int a[],int len)
{
    int x=0;
    for(int i=0; i<len; i++)
        for(int j=i+1; j<len; j++)
            if(a[j]<a[i])
                x+=jiecheng[len-1-i];
    return x ;
}

bool h[len+5];//len就是序列长度
void Cantor_inexpansion(int x,int len)
{
    memset(h,0,sizeof(h));
    int ind ,tem;
    for(int i=0; i<len; i++)
    {
        ind = 0;
        tem = x/jiecheng[len-1-i];
        x  %=   jiecheng[len-1-i];
        for(int j=1; j<=len; j++)
        {
            if(h[j]) continue;
            if(ind==tem)
            {
                a[i]=j;
                break;
            }
            ind++;
        }
        h[a[i]]=1;
    }
    return ;
}

双调欧几里得旅行商问题

算法介绍
http://blog.csdn.net/zchahaha/article/details/51058738
http://www.mamicode.com/info-detail-523965.html

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
int dp[N][N];  //dp[i][j]为i点到1点，再从1点到j点的最短距离,
int d[N][N];   //d[i][j] 为 i->j的距离
struct point{
    int x, y;
}a[N];

int dis(int i, int j){
    int p,q;
    if(a[i].y>a[j].y)   q=(360+a[j].y-a[i].y)%360;
    else          q=(360+a[i].y-a[j].y)%360;
    p=abs(a[i].y-a[j].y)>q?q:abs(a[i].y-a[j].y);
    return (abs(a[i].x-a[j].x)*400+p);
}
int main()
{
    int _,n;
    scanf("%d",&_);
    while(_--){
        scanf("%d", &n);
        a[1].x=0,a[1].y=0;
        for(int i = 2; i <= n+1; i++) scanf("%d %d", &a[i].x, &a[i].y);

        for(int i = 1; i <= n+1; i++)
            for(int j = 1; j <= n+1; j++)
                d[i][j] = dis(i, j);

        dp[1][2] = d[1][2];
        for(int i = 3; i <= n+1; i++){
            for(int j = 1; j < i-1; j++)
                 dp[j][i] = dp[j][i-1] + d[i-1][i];

            dp[i-1][i] = 999999999;
            for(int j = 1; j < i-1; j++){
                int sum = dp[j][i-1] + d[j][i];
                if(dp[i-1][i] > sum)  dp[i-1][i] = sum;
            }
        }
        dp[n+1][n+1] = dp[n][n+1] + d[n][n+1];
        printf("%d\n", dp[n+1][n+1]+10*n);
    }
    return 0;
}

线性基

线性基讲义

基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

同样的，线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合S的某一个最小子集S1使得S1内元素相互异或得到的值域与原集合S相互异或得到的值域相同。

性质

  1. 线性基能相互异或得到原集合的所有相互异或得到的值。
  2. 线性基是满足性质1的最小的集合
  3. 线性基没有异或和为0的子集。

求线性基.

1
2
3
4
5
6
7
8
9
10
11
void Guass(){
    for (int i=1;i<=sz;i++)
        for (int j=63;j>=0;j--)
            if ((A[i]>>j)&1){
                if (!P[j]) {P[j]=A[i]; break;}
                else A[i]^=P[j];
            }

    for (int j=0;j<=63;j++) if (P[j]) r++;
}
r为极大无关组的大小

算术表达式 计算

中缀表达式

中心思想就是用两个栈来维护,一个用来存储符号,另一个用来存储数值.

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
/***
author: tabris
time  : 2017/2/17 17:03
这是在int范围内的整数计算的模板。
包括+-*/() 六个符号
*/
char a[111];
stack<int >num;//数值栈
stack<char >ch;//符号栈
//这个函数只接收+-号，+-号等级最低，运算符栈中除了括号外 都可以取出运算
void js1(){
    int num1,num2;  //从运算符栈中取一个运算符 对数值栈顶和次顶元素进行运算
    while(ch.top()!='('){
        num1 = num.top(); num.pop();
        num2 = num.top(); num.pop();
        if(ch.top()=='+') num2+=num1;
        if(ch.top()=='-') num2-=num1;
        if(ch.top()=='*') num2*=num1;
        if(ch.top()=='/') num2/=num1;
        num.push(num2);//将计算结果入数值栈
        ch.pop();//删除已经用过的符号
    }
}
//只接收*/运算符
void js2() {
    int num1,num2;  //栈中只有*/优先级大于*/
    while (ch.top()=='*' || ch.top()=='/') {
        num1 = num.top(); num.pop();
        num2 = num.top(); num.pop();
        if(ch.top()=='*') num2*=num1;
        if(ch.top()=='/') num2/=num1;
        num.push(num2);ch.pop();
    }
}

int solve(char *str){
    while(!ch.empty())   ch.pop();
    while(!num.empty()) num.pop();

    int len = strlen(str);
    int tem=0;
    bool flag = false;

    ch.push('(');
    strcat(str,".");
    for(int i=0;i<=len;i++){
        if(str[i]>='0'&&str[i]<='9'){
            flag = true;
            tem=(tem<<3)+(tem<<1)+str[i]-'0';
            continue;
        }
        if(flag){
            num.push(tem);
            tem = 0;
            flag = false;
        }
        if(str[i]=='+'||str[i]=='-'){
            js1();
            ch.push(str[i]);
        }
        else if(str[i]=='*'||str[i]=='/'){
            js2();
            ch.push(str[i]);
        }
        else if(str[i]=='('){
            ch.push(str[i]);
        }
        else if(str[i]==')'){
            js1();
            ch.pop();
        }
        else if(str[i]=='.'){
            js1();
            ch.pop();
        }
    }

    return num.top();
}

int main(){
    while(~scanf("%s",a))printf("%d\n",solve(a));
    return 0;
}

后缀表达式

后缀表达式也叫逆波兰表达式

参阅这里

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
# include<iostream>
# include<stack>
# include<stdio.h>
# include<string.h>
using namespace std;

int main(){
    string PostArray;
    int len,i,a,b;
    while(cin>>PostArray){
        stack<int> Stack;
        len = PostArray.length();
        for(i = 0;i < len;i++){
            //跳过空格
            if(PostArray[i] == ' '){
                continue;
            }
            //如果是数字则入栈
            if(PostArray[i] >= '0' && PostArray[i] <= '9'){
                Stack.push(PostArray[i] - '0');
            }
            //如果是字符则从栈读出两个数进行运算
            else{
                //算数a出栈
                a = Stack.top();
                Stack.pop();
                //算法b出栈
                b = Stack.top();
                Stack.pop();
                //进行运算（+ - * /）
                if(PostArray[i] == '+'){
                    Stack.push(a + b);
                }
                else if(PostArray[i] == '-'){
                    Stack.push(a - b);
                }
                else if(PostArray[i] == '*'){
                    Stack.push(a * b);
                }
                else if(PostArray[i] == '/'){
                    Stack.push(a / b);
                }
            }
        }//for
        printf("%d\n",Stack.top());
    }//while
    return 0;
}

多项式取模

对于两个多项式,求多项式的gcd，要求首项次数为1，多项式中的运算都%n

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
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 50000+7;
const int    MOD = 1e9+7;
const double eps = 1e-7;
const double Pi  = acos(-1.0);
const double E   = exp(1.0);

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}

template<typename T>inline T _gcd(T a,T b){return (b==0)?a:_gcd(b,a%b);}
template<typename T>inline T _lcm(T a,T b){return        a/_gcd(a,b)*b;}
LL qmod(LL a,LL b,LL c){LL ret=1ll;while(b){if(b&1)ret=ret*a%c;b>>=1,a=a*a%c;}return ret;}
/***********************************************************************/

# define vi vector<int>

int n;

int inv(int x){
    return qmod(x,n-2,n);
}

vi vimod(vi f,vi g){
    int fz = f.size(),gz = g.size();
    for(int i=0;i<fz;i++){
        if(fz-i-gz < 0) break;
        int a=f[i]*inv(g[0])%n;
        for(int j=0;j<gz;j++){
            int now=i+j;
            f[now]=((f[now]-a*g[j]%n)%n+n)%n;
        }
    }

    vi ans;
    int p=-1;
    for(int i=0;i<fz;i++)if(f[i]!=0){p=i;break;}
    if(p>=0) for(int i=p;i<fz;i++)ans.pb(f[i]);
    return ans;

}

vi gcd(vi f,vi g){
    if(g.size()==0) return f;
    return  gcd(g,vimod(f,g));
}
vi f,g;
int main(){
    int kcase = 0;
    while(~scanf("%d",&n)&&n){
        f.clear(),g.clear();
        int d,x;
        scanf("%d",&d);
        for(int i=0;i<=d;i++){
            scanf("%d",&x);
            f.pb(x);
        }
        scanf("%d",&d);
        for(int i=0;i<=d;i++){
            scanf("%d",&x);
            g.pb(x);
        }
        vi ans = gcd(f,g);
        int tmp = inv(ans[0]);
        printf("Case %d: %d",++kcase,ans.size()-1);
        for(int i=0;i<ans.size();i++){}

            printf(" %d",ans[i]*tmp%n);
        }
        puts("");
    }

    return 0;
}