BZOJ4052: [Cerc2013]Magical GCD 鏆村姏+RMQ

 

BZOJ2796: [Poi2012]Fibonacci Representation 鏆村姏

 

BZOJ1607: [Usaco2008 Dec]Patting Heads 杞绘媿鐗涘ご

BZOJ3522: [Poi2014]Hotel

棰樿В:

鑰冭檻涓変釜鐐瑰湪鏍戜笂鐨勫舰鎬:

(1)鎴愪竴鏉¢摼(鍏跺疄灏辨槸涓績鏄笁涓偣涓殑涓涓偣)

(2)瀛樺湪涓涓敮涓涓績杩炴帴涓変釜鐐癸紝涓斾腑蹇冨埌涓変釜鐐圭殑璺緞闄や簡涓績涔嬪涓嶇浉浜

(瀹氫箟鑷繁鑴戣ˉ涓涓嬪惂...)

鏄剧劧鍙湁鍦(2)鎯呭喌涓,骞朵笖鍞竴涓績鍒颁笁涓偣鐨勮矾寰勯暱搴︾浉绛夋墠鑳芥弧瓒虫潯浠.

鎴戜滑鐩存帴鏋氫妇鍞竴涓績,浠ュ叾涓烘牴鍋氭湁鏍规爲,鍒欎笁涓偣蹇呴』鍒嗗竷鍦ㄤ笉鍚岀殑瀛愭爲涓,涓旀繁搴︾浉鍚.

杩欎釜灏卞緢瀹规槗鎼炰簡,鐪嬩唬鐮佹悶鎼炲氨琛屼簡.

浠g爜:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
#define N 5010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
int sum1[N];
ll sum2[N];
struct Array{
    int a[N],t[N],tclock;
    inline int operator[](int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        return a[x];
    }
    inline void add(int x){
        if(t[x]!=tclock){
            t[x]=tclock;
            a[x]=0;
        }
        ++a[x];
    }
}temp;
 
int max_dep;
inline void dfs(int x,int fa,int dep){
    temp.add(dep);
    max_dep=max(max_dep,dep);
    for(int j=head[x];j;j=next[j])
        if(end[j]!=fa)
            dfs(end[j],x,dep+1);
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    int i,j,k,a,b;
    for(i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        make(a,b);
    }
    ll ans=0;
    int son;
    for(i=1;i<=n;++i){
        memset(sum1,0,sizeof sum1);
        memset(sum2,0,sizeof sum2);
        for(son=1,j=head[i];j;j=next[j],++son){
            ++temp.tclock;
            max_dep=0;
            dfs(end[j],i,1);
            for(k=1;k<=max_dep;++k){
                if(son>=3)
                    ans+=sum2[k]*temp[k];
                sum2[k]+=temp[k]*sum1[k];
                sum1[k]+=temp[k];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

BZOJ1704: [Usaco2007 Mar]Face The Right Way 鑷姩杞韩鏈

棰樿В:

棣栧厛鏋氫妇$k$,閭f垜浠渶瑕佺煡閬撶粰瀹$k$,鏈灏戣繘琛屽灏戞鎿嶄綔.

鏄剧劧搴旇浠庡皬鍒板ぇ杩涜鎵弿,鑰冭檻褰撳墠浣嶇疆$i$,鑻ラ鑹蹭笉瀵,鍒欏弽杞$[i,i+k-1]$.

鐒跺悗鍐嶅垽瀹氬墿涓嬬殑浣嶇疆棰滆壊瀵逛笉瀵.

杩欎釜杩囩▼鍙互鍒╃敤鍗曡皟闃熷垪杞绘澗瀹炵幇,璇︽儏瑙佷唬鐮.

浠g爜:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 5010
bool a[N];
int q[N],fr,ta;
int main(){
    int n;
    scanf("%d",&n);
    int i,j;
    char s[10];
    for(i=1;i<=n;++i){
        scanf("%s",s);
        a[i]=(s[0]=='F');
    }
    int ans=0x3f3f3f3f,temp,k;
    for(i=1;i<=n;++i){
        fr=ta=0;
        for(temp=0,j=1;j+i-1<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0){
                q[ta++]=j;
                ++temp;
            }
        }
        bool ok=1;
        for(j=n+2-i;j<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0)
                ok=0;
        }
        if(ok){
            if(temp<ans){
                ans=temp;
                k=i;
            }
        }
    }
    cout<<k<<" "<<ans<<endl;
    return 0;
}

BZOJ1819: [JSOI]Word Query鐢靛瓙瀛楀吀 鏆村姏+Trie鏍

鎬濊矾:

瀵逛簬姣忔璇㈤棶,鏆村姏鏋氫妇鎵鏈夌紪杈戣窛绂讳负1鐨勪覆,鐒跺悗鐢═rie鍒ゆ柇瀛樹笉瀛樺湪骞跺垽閲.

濡堝憖杩欐槸\(O(10000*26*20*20)=10^8\),灞呯劧涔熻兘杩.

鍏跺疄鐢℉ash鎰熻灏卞ソ澶氫簡.

鏈夋病鏈夋洿濂界殑鏂规硶?鐩墠娌℃兂鍑烘潵.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

int ch[200010][26],end[200010],vis[200010],cnt;
char s[21],ss[22];

int tclock;
inline bool judge(int len){
	int p=0;
	for(int i=0;i<len;++i){
		if(!ch[p][ss[i]-'a'])return 0;
		p=ch[p][ss[i]-'a'];
	}
	if(!end[p])return 0;
	if(vis[p]!=tclock)return vis[p]=tclock,1;else return 0;
}

int main(){
	int n,m;scanf("%d%d",&n,&m);
	register int i,j,k;
	
	int len,p,y;
	while(n--){
		scanf("%s",s);
		len=strlen(s),p=0;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y])ch[p][y]=++cnt;
			p=ch[p][y];
		}
		end[p]=1;
	}
	
	int id;
	while(m--){
		scanf("%s",s);
		len=strlen(s);
		
		p=0;
		bool find=1;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y]){find=0;break;}
			else p=ch[p][y];
		}
		if(find&&end[p]){puts("-1");continue;}
		
		int re=0;
		++tclock;
		
		if(len>1){
			for(i=0;i<len;++i){
				id=0;
				for(j=0;j<i;++j)ss[id++]=s[j];
				for(j=i+1;j<len;++j)ss[id++]=s[j];
				re+=judge(len-1);
			}
		}
		for(i=0;i<len;++i)for(j=0;j<26;++j)if(j!=s[i]-'a'){
			memcpy(ss,s,sizeof s),ss[i]='a'+j;
			re+=judge(len);
		}
		for(i=0;i<=len;++i)for(j=0;j<26;++j){
			id=0;
			for(k=0;k<i;++k)ss[id++]=s[k];
			ss[id++]='a'+j;
			for(k=i;k<len;++k)ss[id++]=s[k];
			re+=judge(len+1);
		}
		
		printf("%d\n",re);
	}
	return 0;
}

BZOJ1570:[JSOI2008]Blue Mary鐨勬梾琛 鏆村姏+缃戠粶娴

鎬濊矾:

鏆村姏鏋氫妇绛旀,鐒跺悗灏嗙偣鍒嗗眰,杈规绘槸浠庤灞傝繛鍚戜笅涓灞.

鐒跺悗鍒ゆ柇鏈澶ф祦鏄笉鏄弧瓒抽鎰.

鍏蜂綋杩炶竟鐪嬩唬鐮.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=50*100;
    static const int E=2450*100*2;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V],gap[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        bfs(T),memcpy(cur,head,sizeof cur);
        int re=0,Min,ins,i,u=S;
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
struct Edge{
    int u,v,f;
}E[2510];
 
#define get(x,dep) ((dep-1)*n+x)
int main(){
    int n,m,T;scanf("%d%d%d",&n,&m,&T);
    register int i,j;
    for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f);
     
    int re;
    for(re=1;;++re){
        Stg.reset();
        for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
        for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
        for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
        int now=Stg.Maxflow(0,n*(re+1)+1);
        //printf("%d\n",now);
        if(now>=T)break;
    }
     
    printf("%d\n",re);
     
    return 0;
}

BZOJ2338:[HNOI2011]鏁扮煩褰 鏆村姏+璁$畻鍑犱綍

鎬濊矾:

棣栧厛鎼炲嚭鎵鏈夌殑绾挎,鐒跺悗涓偣鐩稿悓鐨勬斁鍦ㄤ竴璧,骞朵笖闀垮害鐩稿悓鐨勬斁鍦ㄤ竴璧.

閭d箞,涓偣鐩稿悓骞朵笖闀垮害鐩稿悓,杩欎袱涓嚎娈靛氨鑳藉鏋勬垚涓涓煩褰.

杩欐牱鐨勭嚎娈典笉浼氳秴杩嘰(O(n)\)鏉,鎵浠ユ垜浠彲浠ョ洿鎺ユ毚鍔涙灇涓.

(鍏跺疄鎴戣寰楀彲浠ユ妸鎵鏈夌殑绾挎浠ヤ腑鐐逛负鍘熺偣杩涜鏋佽搴忔帓搴,鐒跺悗鎴戜滑灏辨槸瑕佹壘鍑轰袱鏉$嚎娈典娇寰楀畠浠箣闂寸殑澶硅灏藉彲鑳芥帴杩90,杩欏ぇ姒傚氨鍙互绾挎ф壂鎻忎簡.)

鏈唬鐮佸畬鍏ㄩ伩鍏嶄簡绮惧害闂!閫熸潵鐐硅禐!

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Point&B)const{return(x!=B.x)?x<B.x:y<B.y;}
    bool operator!=(const Point&B)const{return(x!=B.x)||(y!=B.y);}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
};
LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
LL Getans(Point p1,Point p2,Point q1,Point q2){
    LL res=Cross(p1-q1,p1-q2);
    return res<0?-res:res;
}
 
int gcd(int a,int b){return(!b)?a:gcd(b,a%b);}
 
struct Double{
    int x,y;
    Double(){}
    Double(int _x,int _y):x(_x),y(_y){}
 
    bool operator<(const Double&B)const{return(LL)x*B.y<(LL)y*B.x;}
};
 
 
#define N 1510
struct Segment{
    Point P1,P2;LL dis;
    bool insequal(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return 0;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return 0;
        return 1;
    }
    bool operator<(const Segment&B)const{
        if(P1.x+P2.x!=B.P1.x+B.P2.x)return P1.x+P2.x<B.P1.x+B.P2.x;
        if(P1.y+P2.y!=B.P1.y+B.P2.y)return P1.y+P2.y<B.P1.y+B.P2.y;
        return dis<B.dis;
    }
    bool operator==(const Segment&B)const{return insequal(B)&&dis==B.dis;}
}S[N*N>>1];int id;
 
int x[N],y[N],n;
 
inline LL sqr(int x){
    return(LL)x*x;
}
 
int main(){
    scanf("%d",&n);register int i,j,k,p;for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
 
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)++id,S[id].P1=Point(x[i],y[i]),S[id].P2=Point(x[j],y[j]),S[id].dis=sqr(x[i]-x[j])+sqr(y[i]-y[j]);
     
    sort(S+1,S+id+1);
 
    LL res=0;
    for(i=1;i<=id;i=j+1){
        for(j=i;j!=id&&S[j]==S[j+1];++j);
        for(k=i;k<=j;++k)for(p=k+1;p<=j;++p)res=max(res,Getans(S[k].P1,S[k].P2,S[p].P1,S[p].P2));
    }
 
    cout<<res<<endl;
 
    return 0;
}

BZOJ3251:鏍戜笂涓夎褰 鏁板+鏆村姏

鎬濊矾:

鑰冭檻涓嶅瓨鍦ㄤ笁瑙掑舰鐨勬儏鍐:涔熷氨鏄,浠绘剰閫夋嫨涓変釜鏁,鎬绘湁涓涓渶澶х殑鏁颁笉灏忎簬鍓╀笅涓や釜鏁扮殑鎬诲拰.

鎴戜滑鎯冲埌涓涓殑鏁板垪:鏂愭尝閭e鏁板垪.

閭d箞鏉冨煎潎鍦ㄩ鐩粰瀹氭暟鎹寖鍥村唴鐨勬暟鍒楁湁澶氶暱?鑷冲鏈塡(log(Max)\)椤.

濡傛灉瓒呰繃杩欎簺椤,灏变細鍦ㄤ袱涓暟涔嬮棿鎻掑叆鏌愪竴涓暟,閭d箞杩欎笁涓暟灏辨槸蹇呭畾婊¤冻涓夎褰㈡潯浠剁殑.(鏈夌偣鎰忚瘑娴)

鎬讳箣濡傛灉鎬诲叡鏈変笉瓒呰繃\(log(Max)\)涓暟鏆村姏鍒ゅ畾,鍚﹀垯鐩存帴杈撳嚭\(Y\).

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int w[N];
 
int pa[N][16],dep[N];
inline void dfs(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,dfs(end[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=15;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
int seq[51],id;
 
inline bool judge(int a,int b,int c){
    long long A=a,B=b,C=c;
    return A+B>C&&B+C>A&&A+C>B;
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&w[i]);
     
    int a,b;for(i=1;i<n;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=15;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
     
    int t;
    while(m--){
        scanf("%d%d%d",&t,&a,&b);
        if(t==0){
            int Lca=lca(a,b),nums=dep[a]+dep[b]-2*dep[Lca]+1;
            if(nums<=40){
                for(id=0;a!=Lca;a=pa[a][0])seq[++id]=w[a];
                for(;b!=Lca;b=pa[b][0])seq[++id]=w[b];
                seq[++id]=w[Lca];
                bool ok=0;
                for(i=1;i<=id;++i)for(j=i+1;j<=id;++j)for(k=j+1;k<=id;++k)if(judge(seq[i],seq[j],seq[k]))ok=1;
                if(ok)puts("Y");else puts("N");
            }else puts("Y");
        }else w[a]=b;
    }
     
    return 0;
}

BZOJ1406:[AHOI2007]瀵嗙爜绠 鏁板+鏆村姏

鎬濊矾:

浠(x\)鏄竴涓彲琛岀瓟妗,鏈塡(x^2\%n=1\),鍗砛((x-1)(x+1)=kn(k\in{Z})\).

鏄剧劧鎴戜滑鍙互浠(x-1=k_1n_1,x+1=k_2n_2,k=k_1k_2,n=n_1n_2\).(浜ゆ崲涓涓嬩篃鏄彲浠ョ殑)

閭d箞鎴戜滑灏卞彲浠ユ灇涓炬墍鏈夌殑\(n_1\),鐪嬩竴鐪嬩粬鑳藉琛ㄨ揪鍑虹殑\(x+1\)鎴栨槸\(x-1\)鏄笉鏄竴涓悎娉曠瓟妗.鎴戜滑鐢ㄤ竴涓搱甯岃〃鏉ユ敮鎸佹彃鍏.鏈鍚庤緭鍑哄嵆鍙.

 

浣嗘槸鎴戜滑鍙戠幇鏋氫妇鎵鏈夌殑\(n_1\)(n鐨勭害鏁)鏄剧劧鏄瓒呮椂鐨.鍥犳鎴戜滑鍙灇涓綷(n_1\geq{\sqrt{n}}\)鐨刓(n_1\).杩欐牱鍗曟鏋氫妇鐨勫鏉傚害涓篭(\sqrt{n}\),鑰屼笖杩欐牱鐨勭害鏁伴潪甯稿皯,杩欐牱灏卞彲浠ラ氳繃浜.

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=(1e5)+7;
struct HashSet{
    int head[mod],v[200010],next[200010],ind;
    void reset(){ind=0,memset(head,-1,sizeof head);}
    void insert(int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(v[j]==x)return;
        v[ind]=x,next[ind]=head[ins],head[ins]=ind++;
    }
}S;
 
int n;
void Solve(int x){
    for(int d=x;d<n-1;d+=x)if((long long)d*(d+2)%n==0)S.insert(d+1);
    for(int d=x;d<=n;d+=x)if(d-2>=1&&(long long)d*(d-2)%n==0)S.insert(d-1);
}
int main(){
    scanf("%d",&n);
    if(n==1)puts("NONE");
    else{
        S.reset(),S.insert(1);
        for(int i=1;i*i<=n;++i)if(n%i==0)Solve(max(i,n/i));
        sort(S.v,S.v+S.ind);
        for(int i=0;i<S.ind;++i)printf("%d\n",S.v[i]);
    }
     
    return 0;
}