第五届山东省ACM

D

类型: 线段树 区间更新

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q,T;

LL lazy[maxn];
LL sum[maxn];
bool flag[maxn];

void init(){
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
    memset(flag,false,sizeof(flag));
}

void PushDown(int p,int m){
    if(flag[p]){
        lazy[p<<1]=lazy[p<<1|1]=0;
        sum[p<<1]=sum[p<<1|1]=sum[p]=0;
        flag[p<<1]=flag[p<<1|1]=true;
        flag[p]=false;
    }
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

void setf(int p,int l,int r,int L,int R,int c){

    if(L<=l && r<=R){
        lazy[p]=0;
        sum[p]=0;
        flag[p]=true;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) setf(p<<1,l,mid,L,R,c);
    if(R>mid) setf(p<<1|1,mid+1,r,L,R,c);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

int main(){
    cin>>T;
    while(T--){
        init();
        scanf("%d%d",&N,&Q);
        int t,l,r,last=0;
        LL ans=0;
        for(int i=1;i<=Q;++i){
            scanf("%d%d%d",&t,&l,&r);
            ///先更新全部区间的值
            update(1,1,N,t-last,1,N);
            ///然后查询所需区间内的和
            ans+=Query(1,1,N,l,r);
            ///最后将所需区间内的值置为0
            setf(1,1,N,l,r,0);
            last=t;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

山东省第一届省赛

A: 可水可Trie,Trie解法

数据不大,因为题目没有给出字符串的大小,害怕暴力超时,所以用Trie写的.

#include<bits/stdc++.h>
using namespace std;
const int CHARSET=10,BASE='0',MAX_NODE=10100;
struct Trie{
    int tot,root,child[MAX_NODE][CHARSET];
    bool flag[MAX_NODE];
    bool has_prefix;
    bool is_root[MAX_NODE][CHARSET];
    Trie(){
        //printf("New Trie\n");
        memset(child[1],0,sizeof(child[1]));
        memset(is_root,false,sizeof(is_root));
        flag[1]=false;
        has_prefix=false;
        root=tot=1;
    }
    void insert(const char *str){
        int *cur=&root;
        char last_char;
        for(const char *p=str;*p;++p){
            cur=&child[*cur][*p-BASE];
            last_char=*p;
            if(is_root[*cur][last_char])has_prefix=true;
            if(*cur==0){
                *cur=++tot;
                memset(child[tot],0,sizeof(child[tot]));
                flag[tot]=false;
            }
        }
        flag[*cur]=true;
        is_root[*cur][last_char]=true;
    }

};
int main(){
    int n;
    while(~scanf("%d",&n) && n){
        Trie te;
        char str[10000];
        for(int i=0;i<n;++i){
            scanf("%s",str);
            if(!te.has_prefix){
                te.insert(str);
            }
        }
        if(te.has_prefix){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

B:思路比较清晰,就是写的时间长,我写了两份代码

单树(map)套结构体Point重载<+二分: 内存小,时间长

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Point{
    int x,y;
    bool operator < (const Point& a)const{
        if(x<a.x) return true;
        else if(x==a.x && y<a.y) return true;
        return false;
    }
    bool operator == (const Point& a)const{
        if(x==a.x && y==a.y) return true;
        return false;
    }

};
int N,kase=1;

int xx,yy;
char opt[10];

map<Point,bool> G;//x点集0,true为未删除,false为删除
map<Point,bool>::iterator it;

void init(){
    G.clear();
}

bool cmp(Point a,Point b){
    if(a.x<b.x && a.y<b.y)
        return true;
    return false;
}

void add(){
    G[(Point){xx,yy}]=true;
}

void find_(int a,int b){
    it=G.upper_bound((Point){a,b});
    if(it==G.end()){
        printf("-1\n");
        return;
    }
    Point nw=it->first;
    if(it->second && nw.x>xx && nw.y>yy){
        printf("%d %d\n",nw.x,nw.y);
    }else{
        do{
            it++;
            if(it==G.end()){printf("-1\n");return;}
            if(it->second && (it->first).x>xx && (it->first).y>yy){
                printf("%d %d\n",(it->first).x, (it->first).y);
                return;
            }
        }while(1);
    }
}

void remove_(){
    G[(Point){xx,yy}]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_(xx,yy);
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 904ms
Take Memory: 5752KB
Submit time: 2018-02-27 17:08:24
****************************************************/

树(map)+二分套树(map)+二分,代码少,时间短,内存大

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;

int N,kase=1;

int xx,yy;
char opt[10];

map<int,map<int,bool> > G;//x点集0,true为未删除,false为删除
map<int,bool>::iterator ity;
map<int,map<int,bool> >::iterator itx;

void init(){
    G.clear();
}

void add(){
    (G[xx])[yy]=true;
}

void find_(){
    itx=G.upper_bound(xx);
    while(1){
        if(itx!=G.end()){
            ity=(itx->second).upper_bound(yy);
            if(ity!=(itx->second).end() && ity->second){
                printf("%d %d\n",itx->first,ity->first);
                return;
            }
            if(ity!=(itx->second).end()){
                for(ity++;ity!=(itx->second).end();ity++){
                    if(ity->second){
                        printf("%d %d\n",itx->first,ity->first);
                        return;
                    }
                }
            }
        }else break;
        itx++;
    }
    printf("-1\n");
}

void remove_(){
    (G[xx])[yy]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_();
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 516ms
Take Memory: 12712KB
Submit time: 2018-02-27 17:24:44
****************************************************/

然后我百度一下原题,发现set直接删除就好…还是STL不太熟,内存小,用时也少,不过没第二份少

    #include <iostream>  
    #include <stdio.h>  
    #include <algorithm>  
    #include <set>  
    #include <string>  
    using namespace std;  

    int main()  
    {  
        pair<int,int>p;  
        int n;char str[10];  
        int c=1;  
        while(cin>>n&&n)  
        {  
            cout<<"Case "<<c++<<":"<<endl;  
            set< pair<int,int> >s;  
            while(n--)  
            {  
                scanf("%s",str);  
                scanf("%d%d",&p.first,&p.second);  
                if(str[0]=='a')  
                    s.insert(p);  
                else if(str[0]=='r')  
                    s.erase(p);  
                else if(str[0]=='f')  
                {  
                    set< pair<int,int> >::iterator it;  
                    it=s.lower_bound(p);//找到set中第一个比p大的元素的位置,找不到则为s.end()  
                    for(;it!=s.end();it++)  
                    {  
                        if(it->first>p.first&&it->second>p.second)//都大于才符合题意  
                        {  
                            cout<<it->first<<" "<<it->second<<endl;  
                            break;  
                        }  
                    }  
                    if(it==s.end())//找不到  
                        cout<<-1<<endl;  
                }  
            }  
            cout<<endl;  
        }  
        return 0;  
    }  

貌似还可以用线段树优化..

F**k

C:排序水过,别问我为啥写的那么麻烦…因为我半截才想到,懒得改了

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Query{
    int s,t;
};
int N,kase=1;
int main(){
    while(~scanf("%d",&N) && N){
        priority_queue<int,vector<int>,greater<int> > G[maxn];
        priority_queue<int,vector<int>,greater<int> > it;
        vector<Query> Q;
        for(int i=1;i<=N;++i){
            int s,t;
            scanf("%d%d",&s,&t);
            G[s].push(t);
            Q.push_back((Query){s,t});
        }
        printf("Case %d:\n",kase++);
        for(int i=0;i<Q.size();++i){
            int s=Q[i].s,t=Q[i].t;
            bool has_ans=false;
            for(int j=s+1;j<=309 && !has_ans;++j){
                it=G[j];
                while(!it.empty()){
                    int nw=it.top();it.pop();
                    if(nw>t){
                        has_ans=true;
                        printf("%d %d\n",j,nw);
                        break;
                    }
                }
            }
            if(!has_ans){
                printf("-1 -1\n");
            }
        }
        printf("\n");
    }
    return 0;
}

D:中途相遇法+负值二分

因为内置的lower_bound只能查找第一个大于等于的,而我们需要的是小于等于的,所以将所有的值变成负数插入到vector中即可.

这道题N^4肯定是不可行的.所以我们考虑用中途相遇法,

即先处理出任意两个值的和,然后遍历和数组,在原数组中查找是否存在一个值和当前和相加<=M,如果等于M,break即可.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int maxn=2000;
int N,M,KASE=1;
int arr[maxn];
vector<int> first;
int main(){
    while(~scanf("%d%d",&N,&M) && N+M){
        first.clear();
        int ans=0;
        for(int i=0;i<N;++i) scanf("%d",&arr[i]);
        for(int i=0;i<N;++i){
            for(int j=i;j<N;++j){
                first.push_back(-(arr[i]+arr[j]));
            }
        }
        sort(first.begin(),first.end());
        for(int i=0;i<first.size();++i){
            int need=M+first[i];
            if(need<=0) continue;
            else{
                int id=lower_bound(first.begin(),first.end(),-need)-first.begin();
                int nw=-(first[i]+first[id]);
                if(nw<=M) ans=max(ans,nw);
            }
            if(ans==M)break;
        }
        printf("Case %d: %d\n\n",KASE++,ans);
    }
    return 0;
}

G:排序水过

一开始没读懂题意时最难受的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100100;
int Dist[maxn],N;
int main(){
    while(~scanf("%d",&N) && N){
        for(int i=0;i<N;++i){
            scanf("%d",&Dist[i]);
        }
        sort(Dist,Dist+N);
        LL ans=0ll;
        for(int i=1;i<N;++i){
            ans+=((Dist[i]-Dist[i-1])<<1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

I:分别进行两个dfs即可,四方向和八方向

#include<bits/stdc++.h>
using namespace std;

int move1[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int move2[8][2]={{0,-1},{0,1},{-1,0},{1,0},
                 {1,-1},{1,1},{-1,-1},{-1,1}};
char mp[110][110];
int N,kase=1;
int vis1[110][110],vis2[110][110];

void init(){
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
}

bool check(int x,int y){
    if(x>=N || y>=N || x<0 || y<0 || mp[x][y]=='0')
        return false;
    return true;
}

void dfs4(int x,int y){
    if(!check(x,y) || vis1[x][y]) return;
    vis1[x][y]=1;
    for(int i=0;i<4;++i){
        int nx=x+move1[i][0],ny=y+move1[i][1];
        dfs4(nx,ny);
    }
}

void dfs8(int x,int y){
    if(!check(x,y) || vis2[x][y]) return;
    vis2[x][y]=1;
    for(int i=0;i<8;++i){
        int nx=x+move2[i][0],ny=y+move2[i][1];
        dfs8(nx,ny);
    }
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        for(int i=0;i<N;++i){
            scanf("%s",mp[i]);
        }
        int ans4=0,ans8=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(mp[i][j]=='1' && !vis1[i][j]){
                    ans4++,dfs4(i,j);
                }
                if(mp[i][j]=='1' && !vis2[i][j]){
                    ans8++,dfs8(i,j);
                }
            }
        }
        printf("Case %d: %d %d\n\n",kase++,ans4,ans8);
    }
    return 0;
}

E:大模拟

大模拟

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
const int maxn=35;
int N,kase=1;
char mp[maxn][maxn];
int vis[maxn][maxn][maxn][maxn][5];
///EWSN东西南北
int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
///saya更喜欢EWNS
int nt[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

bool check(int x,int y){
    if(x<0||y<0||x>=N||y>=N)return false;
    return true;
}
///返回当前的朝向在,数组为dis
int now_dir(int x,int y,int t){
    char str=mp[x][y];
    int in=0;
    if(str=='E') in=0;
    else if(str=='W') in=1;
    else if(str=='S') in=2;
    else in=3;
    in+=t;
    return in%4;
}

int dist(int x,int y,int tx,int ty){
    return (x-tx)*(x-tx)+(y-ty)*(y-ty);
}

int query_dir(int x,int y,int tx,int ty){
    int mind=INF,dir_=-1;
    for(int i=0;i<4;++i){
        int xx=x+nt[i][0],yy=y+nt[i][1];
        if(!check(xx,yy)) continue;
        int d=dist(xx,yy,tx,ty);
        if(mind>d){
            mind=d;
            dir_=i;
        }
    }
    ///返回第一个想走的方向
    return dir_;
}

int main(){
    while(scanf("%d",&N)!=EOF && N!=0){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<N;++i){
            scanf("%s",&mp[i]);
        }
        int x=0,y=0,tx=N-1,ty=N-1,step=0;
        int xx,yy,txx,tyy;
        printf("Case %d:\n",kase++);
        while(1){
            if(step>=100){
                printf("Not sure.\n");
                break;
            }
            if(tx==x&&ty==y){
                printf("Get the treasure! At step %d.\n",step);
                break;
            }
            ///saya第一步
            int saya=now_dir(x,y,step);
            xx=x+dis[saya][0],yy=y+dis[saya][1];
            if(check(xx,yy)){
                x=xx,y=yy;
            }
            ///saya第二步
            if(!(x==tx&&y==ty)){
                int goal=query_dir(x,y,tx,ty);
                xx=x+nt[goal][0],yy=y+nt[goal][1];
                if(check(xx,yy)){
                    x=xx,y=yy;
                }
            }
            ///宝藏走
            int tres=now_dir(tx,ty,step);
            txx=tx+dis[tres][0],tyy=ty+dis[tres][1];
            if(check(txx,tyy)){
                tx=txx,ty=tyy;
            }

            if(vis[x][y][tx][ty][step%4]){
                printf("Impossible. At step %d.\n",step);
                break;
            }else{
                vis[x][y][tx][ty][step%4]=1;
            }
            step+=1;
        }
        printf("\n");
    }
    return 0;
}

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;
}

LA 3902

【Link】

Network

【题解】

可将网络看成一棵树,将初始的VOD看做该树的根.距离该根k的叶节点可以忽略不计.其余的叶子结点记录在nodes数组表内,nodes[i]代表深度为i的叶子结点表.covered代表该叶子结点是第i个叶子结点是否可以使用VOD.gr代表邻接表.

最优选择放置服务器的方法是选择距离主机最远(k)的那个服务器上安装VOD即可.

【Code】

LA 3902.cpp

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000+10;
vector<int> gr[maxn],nodes[maxn];
int n,s,k,fa[maxn];
bool covered[maxn];

///无根树转有根树,计算fa数组,根据深度把--叶子节点--插入nodes表中
///u当前节点下标,f,当前节点父节点下标,d深度.
void dfs(int u,int f,int d){
    fa[u]=f;
    int nc=gr[u].size();
    ///距离根节点k距离以内的叶子结点不用记录
    if(nc==1 && d>k) nodes[d].push_back(u);
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f)dfs(v,u,d+1);
    }
}

void dfs2(int u,int f,int d){
    covered[u]=true;
    int nc=gr[u].size();
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f&&d<k)dfs2(v,u,d+1);///只覆盖到新服务器不超过k的结点 ///v!=f => 如果从f访问到u,那么就不能再从u回访f.深搜嘛.一路莽到底.
    }
}

int solve(){
    int ans=0;
    memset(covered,0,sizeof(covered));
    for(int d=n-1;d>k;--d){
        for(int i=0;i<nodes[d].size();++i){
            int u=nodes[d][i];
            if(covered[u])continue;///不考虑已经覆盖的点

            int v=u;
            for(int j=0;j<k;++j)v=fa[v];///找到相邻k级祖先,不可能有-1,因为之前已经把离根k的节点忽略了
            dfs2(v,-1,0);///在结点v设置服务器,然后通过对该服务器深搜
                         ///找到所有的叶子结点
            ans++;
        }
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&s,&k);///节点数,初始VOD服务器的编号和k
        for(int i=1;i<=n;++i){gr[i].clear();nodes[i].clear();}
        for(int i=0;i<n-1;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        dfs(s,-1,0);
        printf("%d\n",solve());
    }
    return 0;
}

手撸算法

楼教主的男人八题:
https://wenku.baidu.com/view/cb87fe8cb9d528ea81c779d1.html

远离之前的模板代码,从原理上开始手撸数据结构.

代码均上传至github仓库.

【Dijsktra 2017/5/26】

前向星+优先队列优化+路径回溯
Dijsktra.cpp

【并查集 2017/5/27】

路径压缩,启发式rank优化,将rank较小的并到rank大的集合.

Union-Find-Set.cpp

【树状数组 2017/6/21】

lowbit() x&(-x),前缀和,LA 4329

树状数组.cpp

【快速排序 2017/11/4】

java

import java.util.Random;

public class Quick
{
    private static int cnt=0;
    public static void sort(int[] a){
        Random rand = new Random();
        System.out.println("快排之前:");
        for(int i=0;i<20;++i){
            a[i]=rand.nextInt(100);
            System.out.print(a[i]+" ");
        }
        sort(a,0,a.length - 1);
    }
    public static void sort(int[] a,int lo,int hi){
        if(hi <= lo) return;
        int j = partition(a,lo,hi);//切分
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
    public static int partition(int[] a,int lo,int hi){
        //将数组切分为a[lo..i-1],a[i],a[i+1..hi]
        int i=lo,j=hi+1;//左右扫描指针
        int pt=a[lo];//切分元素
        while(true){
            //扫描左右,检查扫描是否结束并交换元素
            while(a[++i]<pt)if(i==hi) break;//扫描到最左边都没找到大于等于pt的
            while(a[--j]>pt)if(j==lo) break;
            if(i>=j) break;//指针重合
            swap(a,i,j);//没有问题,交换两值
        }
        swap(a,lo,j);//将作为基准的数放回正确的位置,切分为两部分,大于基准,小于基准
        return j;
    }
    public static void swap(int[] a,int x,int y){
        if(x == y) return;
        a[x]=a[x]^a[y];
        a[y]=a[y]^a[x];
        a[x]=a[x]^a[y];
        cnt++;
        System.out.println("\n第"+cnt+"次变化 "+x+" to "+y+" : ");
        for(int item: a){
            System.out.print(item+" ");
        }
    }
    public static void main(String[] args){
        int[] a=new int[20];
        sort(a);
        System.out.println("\n快排之后:");
        for(int item: a){
            System.out.print(item+" ");
        }
    }
}

C++

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;

int qpartition(int *a,int lo,int hi){
    int v=a[lo];
    int i=lo,j=hi+1;
    while(true){
        while(a[++i]<v)if(i==hi)break;
        while(a[--j]>v)if(j==lo)break;
        if(i>=j)break;
        swap(a[i],a[j]);
    }
    swap(a[lo],a[j]);
    return j;
}

void qsort(int *a,int lo,int hi){
    if(lo>=hi) return;
    int j=qpartition(a,lo,hi);
    qsort(a,lo,j-1);
    qsort(a,j+1,hi);
}

int main(){
    srand((unsigned)time(NULL));
    int a[20];
    for(int i=0;i<20;++i){
        a[i]=rand()%100;
        printf("%d ",a[i]);
    }
    printf("\n");
    qsort(a,0,19);
    for(int i=0;i<20;++i){
        printf("%d ",a[i]);
    }
    return 0;
}

Output:

快排之前:
29 41 75 80 82 60 0 51 10 57 26 5 84 70 60 78 10 29 11 56 
第1次变化 1 to 18 : 
29 11 75 80 82 60 0 51 10 57 26 5 84 70 60 78 10 29 41 56 
第2次变化 2 to 17 : 
29 11 29 80 82 60 0 51 10 57 26 5 84 70 60 78 10 75 41 56 
第3次变化 3 to 16 : 
29 11 29 10 82 60 0 51 10 57 26 5 84 70 60 78 80 75 41 56 
第4次变化 4 to 11 : 
29 11 29 10 5 60 0 51 10 57 26 82 84 70 60 78 80 75 41 56 
第5次变化 5 to 10 : 
29 11 29 10 5 26 0 51 10 57 60 82 84 70 60 78 80 75 41 56 
第6次变化 7 to 8 : 
29 11 29 10 5 26 0 10 51 57 60 82 84 70 60 78 80 75 41 56 
第7次变化 0 to 7 : 
10 11 29 10 5 26 0 29 51 57 60 82 84 70 60 78 80 75 41 56 
第8次变化 1 to 6 : 
10 0 29 10 5 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第9次变化 2 to 4 : 
10 0 5 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第10次变化 0 to 3 : 
10 0 5 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第11次变化 0 to 2 : 
5 0 10 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第12次变化 0 to 1 : 
0 5 10 10 29 26 11 29 51 57 60 82 84 70 60 78 80 75 41 56 
第13次变化 4 to 6 : 
0 5 10 10 11 26 29 29 51 57 60 82 84 70 60 78 80 75 41 56 
第14次变化 9 to 18 : 
0 5 10 10 11 26 29 29 51 41 60 82 84 70 60 78 80 75 57 56 
第15次变化 8 to 9 : 
0 5 10 10 11 26 29 29 41 51 60 82 84 70 60 78 80 75 57 56 
第16次变化 11 to 19 : 
0 5 10 10 11 26 29 29 41 51 60 56 84 70 60 78 80 75 57 82 
第17次变化 12 to 18 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 70 60 78 80 75 84 82 
第18次变化 13 to 14 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 60 70 78 80 75 84 82 
第19次变化 10 to 13 : 
0 5 10 10 11 26 29 29 41 51 60 56 57 60 70 78 80 75 84 82 
第20次变化 10 to 12 : 
0 5 10 10 11 26 29 29 41 51 57 56 60 60 70 78 80 75 84 82 
第21次变化 10 to 11 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 78 80 75 84 82 
第22次变化 16 to 17 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 78 75 80 84 82 
第23次变化 15 to 16 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 84 82 
第24次变化 18 to 19 : 
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 82 84 
快排之后:
0 5 10 10 11 26 29 29 41 51 56 57 60 60 70 75 78 80 82 84 

【动态规划-划分数 2017/11/16】

java

动态转移方程:

dp[i][j]: j的i划分数

j>=i: dp[i][j]=dp[i-1][j]+dp[i][j-i]

i>j: dp[i][j]=dp[i-1][j]

即有一个划分数为0时的目标状态是dp[i-1][j]

import java.util.*;
public class stlin {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n,m,M;
        n=in.nextInt();
        m=in.nextInt();
        M=in.nextInt();
        solve(n,m,M);
    }
    public static void solve(int n,int m,int M){
        int[][] dp=new int[m+1][n+1]; 
        //递推式=>dp[i][j]=dp[i-1][j](ai=0时对应的是i-1划分)+dp[i][j-i]()
        dp[0][0]=1;
        for(int i=1;i<=m;++i){
            for(int j=0;j<=n;++j){
                if(i>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=(dp[i-1][j]+dp[i][j-i])%M;
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

【矩阵链乘 2017/11/17】

输入保证有效,例:

6
30 35
35 15
15 5
5 10
10 20
20 25
结果: 15125

从每隔两个开始计算,即自底向上的动态规划.
仔细想一下吧,计算三个的时候,两个已经计算完成了,计算四个的时候,两个和三个已经计算完成了.

比如求((M1)(M2M3M4M5)),你就不需要再去递归求解M2M3M4M5,直接查表就可以了.

import java.util.*;

public class VeDP {
    public static final int MAXN=100;
    public static final int INF=0x3f3f3f3f;
    static int[] p=new int[MAXN+1];
    static int[][] m=new int[MAXN+1][MAXN+1];
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        int n;
        n=cin.nextInt();
        for(int i=1;i<=n;++i){//因为中间肯定相同
            p[i-1]=cin.nextInt();
            p[i]=cin.nextInt();
        }
        for(int l=2;l<=n;++l){
            for(int i=1;i<=n-l+1;++i){
                int j=i+l-1;
                m[i][j]=INF;
                for(int k=i;k<=j-1;++k){
                    m[i][j]=Math.min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
                }
            }
        }
        System.out.println(m[1][n]);
    }
}

【LIS 2017/11/18】

O(n^2) java:
dp[j]:以c[j]为结尾的最长子序列长度.

//O(n^2)
import java.util.*;
public class LIS {
    private static int[] c=new int[100000+1];
    private static int[] dp=new int[100000+1];
    public static void main(String[] args){
        int n;
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        for(int i=0;i<n;++i){
            c[i]=cin.nextInt();
        }
        /*
         * dp[j]: 以c[j]为结尾从0...i的LIS 
         */
        for(int i=1;i<n;++i){
            for(int j=0;j<i;++j){
                if(c[i]>=c[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        System.out.println(dp[n-1]+1);
    }
}

O(nlgn) c++:
二分搜索+dp 可以过51nod

//O(NlgN)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60000;

int c[maxn],l[maxn];
int n;

int lis(){
    l[0]=c[0];
    int length=1;

    for(int i=1;i<n;++i){
        if(l[length-1]<c[i]){
            l[length++]=c[i];
        }else{
            *lower_bound(l,l+length,c[i])=c[i];
        }
    }

    return length;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&c[i]);
    }

    printf("%d",lis());
    return 0;
}

【2017/11/19 最大正方形】

原题连接: AOJ-Lagest Square

dp[i][j]为向左上方扩展最大的边长.
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

Code C++:

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

int dp[maxn][maxn],G[maxn][maxn];
int n,m;

int main(){
    int maxedge=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            scanf("%d",&G[i][j]);
            if(G[i][j]==1)dp[i][j]=0;
            else dp[i][j]=1,maxedge=1;
        }
    }
    for(int i=1;i<n;++i){
        for(int j=1;j<m;++j){
            if(!G[i][j]){
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                maxedge=max(maxedge,dp[i][j]);
            }
        }
    }
    printf("%d\n",maxedge*maxedge);
    return 0;
}

【2017/11/19 最大子矩阵】

博客内写了题解
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;
}

【2017/11/25 筛法求euler】

#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;
}

【2018/1/8 开放式散列表】

/*
//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;
}

【2018/1/17 强连通分量算法 Tarjan】

详解Tarjan:
http://be-sunshine.cn/index.php/2018/01/17/tarjan-scc-algorithm/

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;

vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

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);

    printf("SCC个数: %d\n",scc_cnt);

    for(int i=0;i<n;++i){
        printf("点 %d 的 SCC 编号是: %d\n",i,sccno[i]);
    }
    return 0;
}
/*
6 6

1 0
0 4
4 5
5 1
1 2
2 3
*/

【2018/2/5 排列递推公式+容斥 组合数学】

原题以及题解连接

UVa 11806

#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7;
int T;

const int MAXK=500;
int C[MAXK+10][MAXK+10];
void init(){
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=0;i<=MAXK;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            //组合的一个递推公式
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}

int main(){
    init();
    cin>>T;
    for(int kase=1;kase<=T;++kase){
        int n,m,k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<16;++i){
            int nn=n,mm=m;
            int b=0;
            if(i&1){mm--;b++;}
            if(i&2){nn--;b++;}
            if(i&4){mm--;b++;}
            if(i&8){nn--;b++;}
            //奇数-偶数+
            if(b&1) sum=(sum+mod-C[nn*mm][k])%mod;
            else sum=(sum+C[nn*mm][k])%mod;
        }
        cout<<"Case "<<kase<<": "<<sum<<endl;
    }
    return 0;
}

【2018/2/6 O(n)素数筛法 线性筛法】

一道例题:
http://acm.hdu.edu.cn/showproblem.php?pid=1431

#include<bits/stdc++.h>
#define maxn 100001000
using namespace std;

bool valid[maxn];
int prime[maxn];
/*素数筛法 O(n),对于每个素数只标记一次*/
void getPrime(int n,int &tot,int ans[maxn]){
    memset(valid,true,sizeof(valid));
    for(int i=2;i<=n;++i){
        if(valid[i]){
            tot++;
            ans[tot]=i;
        }
        for(int j=1;((j<=tot) && (i*ans[j]<=n));++j){
            valid[i*ans[j]]=false;
            if(i%ans[j]==0) break;
        }
    }
}

int main(){
    clock_t t1 = clock();
    int tot=0;
    getPrime(100000000,tot,prime);
    clock_t t2 = clock();

    cout<<tot<<endl;
    cout<<prime[5760000]<<endl;
    cout<<"总运行时间为: "<<(double)(t2-t1)/ CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

【2018/3/10 逆元】

逆元递推式

适用于较小数据的情况

LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}

欧拉定理求逆元

如果mod p 不是素数时最好用这个,比较少见

long long euler(int p)  
{  
    long long ans=p,a=p;  
    long long i;  
    for(i=2;i*i<=a;i++)  
    {  
        if(a%i==0)  
        {  
            ans=ans/i*(i-1);  
            while(a%i==0)  
                a/=i;  
        }  
    }  
    if(a>1)  
        ans=ans/a*(a-1);  
    return ans;  
}  

long long eu=euler(mod)-1;  

long long inv(long long a)  
{  
    return Pow(a,eu);  
}  

费马小定理求逆元

a^(p-1)≡1(mod p)

a^(p-2)就是 a 关于p的逆元

前提 a与b互素

long long fast_mod(long long a,long long n,long long Mod){
    long long ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
} 

/*但p(即MOD)是素数时,inv[a]=fast_mod(a,p-2,p)*/

扩展欧几里得求逆元

void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inverse(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

费马小预处理阶乘逆元(一般用于直接求组合数)

ll inv[maxn+10],fac[maxn+10];
///预处理N!的逆元
//费马小定理
/*
 *假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
 *根据这个性质我们可以知道 a的逆元为a^(p-2)
 */
ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}

POJ 1182

【类型】

并查集

【Code】

#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=150000+10;
int N,K;
int T[MAX_N],X[MAX_N],Y[MAX_N];

//并查集
int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

void init(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}

//查询树的根
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

//合并x和y所属集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

void solve(){
    //初始化并查集
    //元素X,X+N,X+2N分别代表X-A,X-B,X-C
    init(N*3);
    int ans=0;
    for(int i=0;i<K;++i){
        int t=T[i];
        int x=X[i]-1,y=Y[i]-1;//将x,y转换为从下标为0开始编号的号码

        if(x<0||x>=N||y<0||y>=N){//不满足条件2
            ans++;
            continue;
        }

        if(t==1){
            if(same(x,y+N)||same(x,y+2*N)){
                ans++;
            }else{
                unite(x,y);
                unite(x+N,y+N);
                unite(x+2*N,y+2*N);
            }
        }else{
            if(same(x,y) || same(x,y+2*N)){
                ans++;
            }else{
                unite(x,y+N);
                unite(x+N,y+2*N);
                unite(x+2*N,y);
            }
        }
    }
    printf(“%d\n”,ans);
}

int main(){
    scanf(“%d%d”,&N,&K);
    for(int i=0;i<K;++i){
        scanf(“%d%d%d”,&T[i],&X[i],&Y[i]);
    }
    solve();
    return 0;
}

POJ 2255

【Tip】

前序中序求后序

【Code】

#include <iostream>  
#include <cstring>  

using namespace std;  

char TF[27];  
char TM[27];  

void TL( int p1, int p2, int q1, int q2, int root )  
{  
    if ( p1 > p2 ) return;  
    //q1,前序第一个,即根,root为中序中的根下标
    for ( root = q1 ; TM[root] != TF[p1] ; ++ root );
    //root-q1=左子树节点个数,因为有前序,所以不需要root
    //变量,这里的root做使用变量处理.
    //第一个递归,前两个变量是前序中左子树的区间,
    //后两个变量是中序中左子树的区间  
    TL( p1+1, p1+root-q1, q1, root-1, 0 );
    //前两个是前序中
    //右子树的区间,后两个是中序中右子树的区间  
    TL( p1+root-q1+1, p2, root+1, q2, 0 );  
    printf(“%c”,TM[root]);  
}  

int main()  
{  
    while (~scanf(“%s%s”,TF,TM)) {  
        int L = strlen(TF)-1;  
        TL( 0, L, 0, L, 0 );  
        printf(“\n”);  
    }  
    return 0;  

【补充】

修改题意为根据后序中序求先序.

#include <iostream>  
#include <cstring>  
     
using namespace std;  
      
char TA[27];  //后序
char TM[27];  //中序
      
void TL( int p1, int p2, int q1, int q2 )  
{  
    if ( p1 > p2 ) return;  
    printf(“%c”,TA[p2]);
    int i;    
    for ( i =  q1; TM[i] != TA[p2] ; ++ i );
    TL( p1, p2-q2+i-1, q1, i-1);
    TL( p2-q2+i, p2-1, i+1, q2 );  
   
}  
      
int main()  
{  
    while (~scanf(“%s%s”,TA,TM)) {  
        int L = strlen(TA)-1;  
        TL( 0, L, 0, L);  
        printf(“\n”);  
    }  
    return 0;  

UVa 442

【类型】

数据结构,栈,STL

【Tip】

这道题和四则运算入栈规则一样,是数字入栈,凡遇到 ‘)’ 则操作前两个字符(这里是矩阵).

矩阵链乘,A(m,n),B(n,d).A(n)==B(n)才成立.

注意.入栈顺序与出栈顺序是相反的,而矩阵链乘不满足乘法交换律.所以(AB)!=(BA)也存在(AB)有值(BA)无值.

(这道题没在每条语句执行结束时清空栈,意在.in数据全部有效?)(大雾

Continue reading “UVa 442”