ALDS1_4_C Dictionary

原题连接: https://vjudge.net/problem/Aizu-ALDS1_4_C

题型: 开放式散列表(可以用c++库函数做,但那样就忒没诚意了是啊吧 :triumph: )

PS:对于散列表性能影响最大的一般是散列函数.如果出现TLE,证明散列函数出问题了,改改试试.

Code:

/*
//alds1_4_c:Dictionary
//算法:开放地址法散列表
//Time: 2018/1/8 星期一
*/
#include<stdio.h>
#include<string.h>

const int M=1000003;
const int L=14;

char H[M][L];

//对于每个字符返回的定义值
int getChar(char ch){
    if(ch=='A') return 1;
    if(ch=='C') return 2;
    if(ch=='D') return 3;
    if(ch=='T') return 4;
    return 0;
}
//对于字符串返回的初始散列值
long long getKey(char str[]){
    long long len=strlen(str),sum=0,p=1;
    for(int i=0;i<len;++i){
        sum+=p*getChar(str[i]);
        //每次获取定义值后p*5,相当于转换成五进制,不会冲突
        p*=5;
    }
    return sum;
}

//开放式散列值计算式: h(k,i)=(h1(k)+i*h2(k))%M
int h1(int key){
    return key%M;
}
//为了保证不会递归冲突(即往下算结果始终相同),必须使h2(key)与M互素
//TLE最好的情况就是改这个函数= =
//目前可以AC的: 1+(key%(M-1))
//(1+key)%(M-1)
int h2(int key){
    return (1+key)%(M-1);
}

//查找
//-1表示找到
//h表示找到第一个可插入点
int find(char str[]){
    long long key=getKey(str),i,h;
    for(i=0;;++i){
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0) return -1;
        else if(strlen(H[h])==0) return h;
    }
    return 0;
}

//插入
void insert(char str[]){
    int key=find(str);
    if(key!=-1) strcpy(H[key],str);
}

int main(){
    for(int i=0;i<M;++i) H[M][0]='\0';
    char str[L],com[L];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s %s",com,str);

        if(com[0]=='i'){
            insert(str);
        }else{
            if(find(str)==-1)
                printf("yes\n");
            else
                printf("no\n");
        }
    }

    return 0;
}

AOJ NTL_1_D Euler’s Phi Function & 欧拉函数相关

欧拉函数: 提供1到N中与N互质的数的个数.

定义和简单性质

欧拉函数用希腊字母φ(Phi)表示,φ(N)表示N的欧拉函数.

对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1).

性质

1.对于素数p,φ(p)=p-1,对于两个素数p,q φ(pq)=(p-1)*(q-1)

欧拉函数是积性函数,但不是完全积性函数.

证明:

函数的积性即:
若m,n互质,则φ(mn)=φ(m)φ(n).由“m,n互质”可知m,n无公因数,所以:
φ(m)φ(n)=m(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)·n(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
其中p1,p2,p3…pn为m的质因数,p1′,p2′,p3’…pn’为n的质因数,而m,n无公因数,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
互不相同,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
均为mn的质因数且为mn质因数的全集,所以:
φ(mn)=mn(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
所以:
φ(mn)=φ(m)φ(n).

即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立(n与m互质).

2.对于一个正整数N的素数幂分解N=P1^q1P2^q2…*Pn^qn.

则 φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N)(d是N的质因数).

根据性质二,我们可以在O(sqrt(n))的时间内暴力求出一个数的欧拉函数值.

如果我们要求1000000以内所有数的欧拉函数,怎么办.

上面的方法复杂度将高达O(N*sqrt(N)).

暴力方法:

#include<iostream>
#include<algorithm>
using namespace std;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int a[10]={2,10,100,1000,5,7,9,11,12,13};
    for(int i=0;i<10;++i)
        cout<<euler(a[i])<<endl;
    return 0;
}

结果:

我们可以将这个方法和筛法求素数的想法结合,试用筛法求出1~n内各个数字的euler(n).

φ(n)=n(1-1/p1)(1-1/p2)….(1-1/pk)
其中p1、p2…pk为n的所有素因子(这个素因子是由整数素分得来的)。
比如:φ(12)=12
(1-1/2)(1-1/3)=4。

比如求10以内所有数的φ值:

1.设一数组phi[11],赋初值phi[1]=1,phi[2]=2…phi[10]=10

2.然后从2开始循环

把2的倍数的φ值(1-1/2),则phi[2]=21/2=1,phi[4]=41/2=2,phi[6]=61/2=3….;

再是3,3的倍数的φ值(1-1/3),则phi[3]=32/3=2,phi[6]=3*2/3=2,phi[9]=…..;

再5,再7…因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n*(1-1/p1)(1-1/p2)….(1-1/pk)的运算

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

///筛法求euler(1)~euler(n)
const int maxn=101;
int euler_1_n[maxn];

void a_euler(){
    euler_1_n[1]=1;
    for(int i=2;i<maxn;++i) euler_1_n[i]=i;
    for(int i=2;i<maxn;++i){
        if(euler_1_n[i]==i){
            for(int j=i;j<maxn;j+=i){
                euler_1_n[j]=euler_1_n[j]/i*(i-1);
            }
        }
    }
}

int main(){
    a_euler();
    for(int i=1;i<101;++i)
        cout<<euler_1_n[i]<<endl;

    return 0;
}

AOJ NTL_1_D Euler’s Phi Function

这道题数值范围是1e10,没超过int.而且只需要求一个数的euler.
O(lgn)暴力即可.

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int n;
    cin>>n;
    cout<<euler(n)<<endl;

    return 0;
}

数论 – 幂乘以及取模相关推导

幂乘都很熟悉了.将n的乘法降为lgn的乘法次数.

mod相关

:arrow_forward:计算加法时,每项加一次执行一次%M

:arrow_forward:计算减法时,给被减数加上M之后先算减法后算%M

:arrow_forward:计算乘法时,每相乘一次执行一次%M,这样做的理由如下

设a除以M的余数和商分别为ar,aq.
b除以M的余数和商分别为br,bq.
a*b =(aq*M+ar)*(bq*M+br)
    =aq*bq*M^2+ar*bq*M+aq*br*M+ar*br
    =(aq*bq*M^+ar*bq+aq*br)*M+ar*br

故 (a*b)%M = ar*br
             = a%M*b%M

:arrow_forward:除法相对复杂,具体可以通过费小马定理求解.

幂乘模板题:

NTL_1_B:Power

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const ull md=1000000007;

ll mod_pow(ull x,ull n,ull mod){
    ull res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    ull m,n;
    scanf("%llu %llu",&m,&n);
    printf("%lld\n",mod_pow(m,n,md));
    return 0;
}

AOJ ALDS1_11_D Connected Components

Connected Components

Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

In the first line, two integer n and m are given. n is the number of users in the SNS and m is the number of relations in the SNS. The users in the SNS are identified by IDs 0, 1, …, n-1.

In the following m lines, the relations are given. Each relation is given by two integers s and t that represents s and t are friends (and reachable each other).

In the next line, the number of queries q is given. In the following q lines, q queries are given respectively. Each query consists of two integers s and t separated by a space character.

Output

For each query, print “yes” if t is reachable from s through the social network, “no” otherwise.

Constraints

  • 2 \leq n \leq 100,000
  • 0 \leq m \leq 100,000
  • 1 \leq q \leq 10,000

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no

求连通分量,对每一个连通分量进行染色.不在同一个联通分量的肯定无法联系.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
const int maxn=100000;
const int NIL=-1;
int n;
vector<int> G[maxn];
int color[maxn];

void dfs(int r,int c){
    stack<int> S;
    S.push(r);
    color[r]=c;
    while(!S.empty()){
        int u=S.top();S.pop();
        for(int i=0;i<G[u].size();++i){
            int v=G[u][i];
            if(color[v]==NIL){
                color[v]=c;
                S.push(v);
            }
        }
    }
}

void setColor(){
    int id=1;
    for(int i=0;i<n;++i){
        color[i]=NIL;
    }
    for(int u=0;u<n;++u){
        if(color[u]==NIL) dfs(u,id++);
    }
}

int main(){
    int s,t,m,q;

    cin>>n>>m;

    for(int i=0;i<m;++i){
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    setColor();

    cin>>q;
    for(int i=0;i<q;++i){
        cin>>s>>t;
        if(color[s]==color[t]){
            puts("yes");
        }else{
            puts("no");
        }
    }

    return 0;
}

AOJ DPL_3 B Largest Rectangle

Largest Rectangle

Given a matrix (H × W) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s.

Input

H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W

In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H × W matrix, are given.

Output

Print the area (the number of 0s) of the largest rectangle.

Constraints

  • 1 ≤ H, W ≤ 1,400

Sample Input

4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

Sample Output

6

最大子矩阵(直方图)的变形.

首先需要把每一行都预处理成距离第0行的高度的表.然后每一行都相当于一个直方图,对每个直方图求可以围成的所有矩形面积,用maxv维护最大矩形的值.

例 处理前:
    0 0 1 0 0
    1 0 0 0 0
    0 0 0 1 0
    0 0 0 1 0

After 处理后:
    1 1 0 1 1
    0 2 1 2 2
    1 3 2 0 3
    2 4 3 0 4

Code:

#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
#define MAX 1400
using namespace std;

struct Rectangle { int height; int pos; };

int getLargestRectangle(int size,int buffer[]){
    stack<Rectangle> S;
    int maxv=0;
    //通过后一位向前面的计算
    //这里用到的DP大概是无参数getLargestRectangle里面的预处理
    //这里用到的更多是思维吧,对每一行进行计算,最后求出最大值.
    buffer[size]=0;

    for(int i=0;i<=size;++i){
        Rectangle rect;
        rect.height=buffer[i];
        rect.pos=i;
        if(S.empty()){
            S.push(rect);
        }else{
            if(S.top().height < rect.height){
                S.push(rect);
            }else if(S.top().height > rect.height){
                int target=i;
                while(!S.empty() && S.top().height >= rect.height){
                    Rectangle pre=S.top();S.pop();
                    int area=pre.height*(i-pre.pos);
                    maxv=max(maxv,area);
                    target=pre.pos;
                }
                rect.pos=target;
                S.push(rect);
            }
        }
    }
    //printf("\nmaxv: %d\n",maxv);
    return maxv;
}

int H,W;
int buffer[MAX][MAX];
int T[MAX][MAX];

int getLargestRectangle(){
    //预处理每个点离他最近的上边未被污染地板的高度
    for(int j=0;j<W;++j){
        for(int i=0;i<H;++i){
            if(buffer[i][j]){
                T[i][j]=0;
            }else{
                T[i][j]=(i>0)?T[i-1][j]+1:1;
            }
        }
    }
    /*
    例:
        0 0 1 0 0
        1 0 0 0 0
        0 0 0 1 0
        0 0 0 1 0

    After:
        1 1 0 1 1
        0 2 1 2 2
        1 3 2 0 3
        2 4 3 0 4
    */
    int maxv=0;
    //传入两个值 W,列数,处理后T[i]第i行的首地址
    for(int i=0;i<H;++i){
        maxv=max(maxv,getLargestRectangle(W,T[i]));
    }

    return maxv;
}

int main(){
    scanf("%d %d",&H,&W);
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            scanf("%d",&buffer[i][j]);
        }
    }

    printf("%d\n",getLargestRectangle());
    return 0;
}