POJ 2186

Tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100000+10;
/*
  有n只牛,牛之间存在一些关系,比如a认为b很受欢迎
,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据
给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?

解:
  对于一个有向无环图来说,其中有且仅有一个点出度为零
,那么这个特殊的点,可以由其他任何点到达。那么接下来我
们直接对所给的图进行强连通分量划分,然后把每个强连通分
量看做一个点,判定出度为零的点有几个,如果有一个就输出
这个点对应的强连通分量含有的节点个数,否则为零。
*/
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int vis[maxn];

stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    ///如果点从1开始计数,这里改成-1即可
    G[u-1].push_back(v-1);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    ///缩点,同一scc缩到同一点中
    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j){
            ///如果i到G[i][j]这条边不在强连通分量中
            ///说明是一个连接外面的点
            if(sccno[i]!=sccno[G[i][j]]){
                vis[sccno[i]]++;
            }
        }
    }

    int sum=0,ans=0,cnt=0;
    for(int i=1;i<=scc_cnt;++i){
        if(!vis[i]){
            ///如果出度是0,则是一个边界点
            sum++;
            ans=i;
        }
    }
    ///如果只有一个点的话,代表存在一个万人敬仰团体
    if(sum==1){
        for(int i=0;i<n;++i){
            if(sccno[i]==ans){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }else{
        printf("0\n");
    }
    return 0;
}
/*
3 3
1 2
2 1
2 3

1
*/

POJ 1961

Link

https://vjudge.net/problem/UVALive-3026

Type: KMP-Next数组

题意

给你一个字符串,输出这个字符串中所有的周期子串最后一个字符的下标和周期长度

题解

前置

关于Next数组

(1) Next数组记录的是如果当前字符不匹配,跳到哪个字符进行再次匹配.

(2) j=Next[k]表示第 j 个字符和第 k 个字符一样.

(3) j=Next[k]表示前 j 个字符和后 j 个字符一样

即 1~j-1 和 k-j+1~k 这两个子串相等

正文

即我们求出该字符串的Next数组后我们可以判断当前 (i-Next[i]) 是否能被 i 整除.

即 i%(i-Next[i]) 是否等于0.

i-Next[i]为该子串的长度,如果可以整除则证明该子串为循环节,循环节长度为 i-Next[i] ,循环次数为 i/(i-Next[i]).

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
char ts[maxn];
int n,kase=1;
int Next[maxn];
void getNext(){
    int j=0,k=-1;
    Next[0]=-1;
    while(j<n){
        if(k==-1 || ts[j]==ts[k]) Next[++j]=++k;
        else k=Next[k];
    }
}
void print(){
    for(int i=1;i<=n;++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int main(){
    while(~scanf("%d",&n)){
        if(!n)break;
        scanf("%s",ts);
        getNext();
        //print();
        printf("Test case #%d\n",kase++);
        for(int i=2;i<=n;++i){
            if(Next[i]<=0) continue;
            if(i%(i-Next[i])==0){
                printf("%d %d\n",i,i/(i-Next[i]));
            }
        }
        printf("\n");
        getchar();
    }
    return 0;
}

POJ 3090

Link

https://vjudge.net/problem/POJ-3090

Type: 欧拉函数

题意

第一象限的点(x,y),给定一个N,问你,(0,0)~(N,N)范围中有多少连接原点且连线上没有整数坐标的点?

题解

想到如果两个数互质,则他与原点的连线上,必然没有整数点.

然后原题转换成该范围内有多少个点的 x与y互质

这个与poj2478这道题求法一样,有一点不同的是,(x,y)存在的同时也会存在(y,x) 并且会同时存在(1,0)(0,1)(1,1)这三个点,所以答案是

Farey[n]*2+3

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000+100;
int phi[maxn];
int Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n,kase=1,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d %d %d\n",kase++,n,Farey[n]*2+3);
    }
    return 0;
}

POJ 2478

Link

https://vjudge.net/problem/POJ-2478

Type: 欧拉函数

题意

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

其中分子与分母互质.

目标是求Fn中的最简分数有多少个

题解

仔细观察会发现因为所有分数分子分母都是互素的
设n为分母,相同分母n的最简分数的个数就等于与n互质的数的个数.
分母从2开始计数

答案就是2~n的phi(k)的和

注意和斐波那契一样,Farey序列也会超过long long

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000+100;
LL phi[maxn];
LL Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(LL i=2;i<maxn;++i){
        if(!phi[i]){
            for(LL j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)&&n){
        printf("%lld\n",Farey[n]);
    }
    return 0;
}

POJ 2407

Link

https://vjudge.net/problem/POJ-2407

Type: 欧拉函数

题意

求小于n 且与n互质的数的个数

题解

简单欧拉,但因为是十亿的数据量,所以不能预处理

Code

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

int phi(int n){
    int ans=n;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            ans=ans-ans/i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        ans=ans-ans/n;
    }
    return ans;
}

int main(){
    int n;
    while(cin>>n&&n){
        cout<<phi(n)<<endl;
    }
    return 0;
}

POJ 2769

可以暴力,不明所以的玄学复杂度
我觉得复杂度大概是 O(100000*log(300))

/*
我以为这道题有公式...
谁知道他要靠暴力???
而且每次枚举前还memset????
复杂度真的可以么...
*/

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000+100;

bool exist[100010];
int num[maxn];
int T;

int main(){
    scanf("%d",&T);
    while(T--){
        int N;
        scanf("%d",&N);
        for(int i=1;i<=N;++i){
            scanf("%d",&num[i]);
        }
        for(int j=1;;++j){
            bool is=true;
            memset(exist,false,sizeof(exist));
            for(int k=1;k<=N;++k){
                if(exist[num[k]%j]){
                    is=false;
                    break;
                }
                exist[num[k]%j]=true;
            }
            if(is){
                printf("%d\n",j);
                break;
            }
        }
    }
    return 0;
}

poj 3370

【鸽巢原理】
题意: 给你两个整数c和n,以及n个整数,问这n个整数中是否有一些整数和为c的倍数.

同样可以证明,当c<=n时,同样可以使用鸽巢原理证明有连续的序列和为c的倍数.

另外有一点是,Sigma ai最大可能100000^2.所以要用long long存.

PS:这道题用G++提交就超时了…C++提交无事.WTF

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
long long sum[maxn];
int num;
int r[maxn];
int c,n;
int main(){
    while(~scanf("%d%d",&c,&n)&&c&&n){
        memset(r,0,sizeof(r));
        int k=0,l=1;
        sum[0]=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&num);
            sum[i]=sum[i-1]+num;

            int remainder=sum[i]%c;
            if(remainder==0){
                k=0;
                l=i;
            }else if(r[remainder]){
                k=r[remainder];
                l=i;
            }else r[remainder]=i;
        }
        printf("%d",k+1);
        for(int i=k+2;i<=l;++i){
            printf(" %d",i);
        }
        printf("\n");
    }
    return 0;
}

POJ 1067

【威佐夫博弈】

//威佐夫博弈
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        int k=max(n,m)-min(n,m);
        int ak=k*(1+sqrt(5))/2;
        int bk=ak+k;
        if(min(n,m)==ak&&max(n,m)==bk){
            printf("0\n");
        }else{
            printf("1\n");
        }
    }
    return 0;
}

CCF 2016-12/4 & POJ 1738

类型: 石子合并问题
算法: GarsiaWachs算法。时间复杂度为O(n^2),平衡树来优化,使得最终复杂度为O(nlogn),也可以用动态规划,等等学一下再补充.

GarsiaWachs算法(摘自别人的blog):

具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W,Lemma X,Lemma Y,Lemma Z。
只能说一个概要吧:
设一个序列是A[0..n-1],每次寻找最小的一个满足A[k-1]<=A[k+1]的k,(方便起见设A[-1]和A[n]等于正无穷大)
那么我们就把A[k]与A[k-1]合并,之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。
有定理保证,如此操作后问题的答案不会改变。
举个例子:
186 64 35 32 103
因为35<103,所以最小的k是3,我们先把35和32删除,得到他们的和67,并向前寻找一个第一个超过67的数,把67插入到他后面
186 64(k=3,A[3]与A[2]都被删除了) 103
186 67(遇到了从右向左第一个比67大的数,我们把67插入到他后面) 64 103
186 67 64 103 (有定理保证这个序列的答案加上67就等于原序列的答案)
现在由5个数变为4个数了,继续!
186 (k=2,67和64被删除了)103
186 131(就插入在这里) 103
186 131 103
现在k=2(别忘了,设A[-1]和A[n]等于正无穷大)
234 186
420
最后的答案呢?就是各次合并的重量之和呗。420+234+131+67=852,哈哈,算对了。

证明嘛,基本思想是通过树的最优性得到一个节点间深度的约束,之后
证明操作一次之后的解可以和原来的解一一对应,并保证节点移动之后他所在的
深度不会改变。详见TAOCP。

具体实现这个算法需要一点技巧,精髓在于不停快速寻找最小的k,即维护一个“2-递减序列”
朴素的实现的时间复杂度是O(n*n),但可以用一个平衡树来优化(好熟悉的优化方法),使得最终复杂度为O(nlogn)


解题思路:(这是我找到的一个关于GarsiaWachs算法的解释)

      1. 这类题目一开始想到是DP, 设dp[i][j]表示第i堆石子到第j堆石子合并最小得分.

         状态方程: dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

         sum[i]表示第1到第i堆石子总和. 递归记忆化搜索即可.

      2. 不过此题有些不一样, 1<=n<=50000范围特大, dp[50000][50000]开不到这么大数组.

         问题分析:

         (1). 假设我们只对3堆石子a,b,c进行比较, 先合并哪2堆, 使得得分最小.

              score1 = (a+b) + ( (a+b)+c )

              score2 = (b+c) + ( (b+c)+a )

              再次加上score1 <= score2, 化简得: a <= c, 可以得出只要a和c的关系确定,

              合并的顺序也确定.

         (2). GarsiaWachs算法, 就是基于(1)的结论实现.找出序列中满足stone[i-1] <=

              stone[i+1]最小的i, 合并temp = stone[i]+stone[i-1], 接着往前面找是否

              有满足stone[j] > temp, 把temp值插入stone[j]的后面(数组的右边). 循环

              这个过程一直到只剩下一堆石子结束.

        (3). 为什么要将temp插入stone[j]的后面, 可以理解为(1)的情况

             从stone[j+1]到stone[i-2]看成一个整体 stone[mid],现在stone[j],

             stone[mid], temp(stone[i-1]+stone[i-1]), 情况因为temp < stone[j],

             因此不管怎样都是stone[mid]和temp先合并, 所以讲temp值插入stone[j]

             的后面是不影响结果.

代码实现:

///186 64 35 32 103
///GarsiaWachs算法。时间复杂度为O(n^2),平衡树来优化,使得最终复杂度为O(nlogn)
/*
设序列是stone[],从左往右,找一个满足
stone[k-1] <= stone[k+1]的k,找到后合
并stone[k]和stone[k-1],再从当前位置
开始向左找最大的j,使其满足
stone[j] > stone[k]+stone[k-1],
插到j的后面就行。一直重复,直到只剩下
一堆石子就可以了。在这个过程中,可以假设
stone[-1]和stone[n]是正无穷的。
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005;

int stone[maxn];
int N,ans,T;
///186 64 35 32 103
void combine(int k){
    int tmp=stone[k]+stone[k-1];
    ans+=tmp;
    for(int i=k;i<T-1;++i)
        stone[i]=stone[i+1];
    T--;
    int j=0;
    for(j=k-1;j>0&&stone[j-1]<tmp;--j)
        stone[j]=stone[j-1];
    stone[j]=tmp;
    while(j>=2&&stone[j]>=stone[j-2]){
        int d=T-j;
        combine(j-1);
        j=T-d;
    }
}

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=0;i<N;++i) scanf("%d",&stone[i]);
        T=1;
        ans=0;
        for(int i=1;i<N;++i){
            stone[T++]=stone[i];
            while(T>=3&&stone[T-3]<=stone[T-1]){
                combine(T-2);
            }
        }
        while(T>1)combine(T-1);
        printf("%d\n",ans);
    }
    return 0;
}
///186 64 35 32 103

POJ 3468

类型: 线段树区间更新.

题目连接: POJ炸了,用virtual judge的链接
:earth_africa:POJ-3468

题意: 给你N个数,Q个操作,操作有两种,‘Q a b ’是询问a~b这段数的和,‘C a b c’是把a~b这段数都加上c。

题解: 区间问题,首先想到线段树,这里我们建两个线段树.data,datb.
data用来维护区间所更新的值.
datb则用来维护区间的和.
计算的时候只需要 每部分的区间和 + 每部分更新的值 即为最终答案.(百度说这叫Lazy思想.)

github:
:earth_africa:POJ-3468.cpp

Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
///区间更新
typedef long long ll;

const int DAT_SIZE=(1<<18)-1;
const int MAX_N=100000+10;
const int MAX_Q=100000+10;

int N,Q;
int A[MAX_N];
char T[MAX_Q];
int L[MAX_Q],R[MAX_Q],X[MAX_Q];

///线段树,a维护区间应加值,b维护区间和
ll data[DAT_SIZE],datb[DAT_SIZE];

///对区间[a,b]同时加x
///k是节点编号,对应的区间是[l,r)
void add(int a,int b,int x,int k,int l,int r){
    if(a<=l&&r<=b){
        data[k]+=x;
    }else if(l<b && a<r){
        datb[k]+=(min(b,r)-max(a,l))*x;
        add(a,b,x,(k<<1)+1,l,(l+r)>>1);
        add(a,b,x,(k<<1)+2,(l+r)>>1,r);
    }
}

///计算[a,b)的和
ll sum(int a,int b,int k,int l,int r){
    if(b<=l || a>=r){
        return 0;
    }else if(a<=l && r<=b){
        return data[k]*(r-l)+datb[k];
    }else{
        ll res=(min(b,r)-max(a,l))*data[k];
        res+=sum(a,b,(k<<1)+1,l,(l+r)>>1);
        res+=sum(a,b,(k<<1)+2,(l+r)>>1,r);
        return res;
    }
}

///下标0开头的线段树初始化
///开区间[a,b)
void solve(){
    for(int i=0;i<N;++i){
        add(i,i+1,A[i],0,0,N);
//        printf("\nadd: %d -> %d\n",i,A[i]);
    }
    for(int i=0;i<Q;++i){
        if(T[i]=='C'){
            add(L[i],R[i]+1,X[i],0,0,N);
        }else{
            printf("%lld\n",sum(L[i],R[i]+1,0,0,N));
        }
    }
}

int main(){
    while(scanf("%d%d",&N,&Q)==2){
        memset(data,0,sizeof(data));
        memset(datb,0,sizeof(datb));
        for(int i=0;i<N;++i){
            scanf("%d",&A[i]);
        }
        ///区间是[0...N)所以要减一
        for(int i=0;i<Q;++i){
            scanf("%*c%c",&T[i]);
            if(T[i]=='C'){
                scanf("%d%d%d",&L[i],&R[i],&X[i]);
                L[i]-=1;R[i]-=1;
            }else{
                scanf("%d%d",&L[i],&R[i]);
                L[i]-=1;R[i]-=1;
            }
        }
        solve();
    }
    return 0;
}