當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

9月——都已经9月了还不好好刷题？。。

發布時間：2025/4/9 编程问答 17 豆豆

生活随笔收集整理的這篇文章主要介紹了 9月——都已经9月了还不好好刷题？。。小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1 UVALive4513 （字符串hash

題目：在一個串中找到至少出現m次的最長的串。思路：直接hash，然后二分答案。 /* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio(false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxl=4e4+300; const ull hash1=123; int m; char s[maxl]; ull H[maxl]; ull xp[maxl]; ull gethash(int i,int L){return H[i]-H[i+L]*xp[L]; } int len; map<ull,vector<int> > mp; map<ull,int> cont; map<ull,vector<int> >::iterator it; ull val[maxl]; bool check(int l){for(int i=0;i<len-l+1;i++){val[i]=gethash(i,l);}sort(val,val+len-l+1);int c=0;for(int i=0;i<len-l+1;i++){if(i==0||val[i]!=val[i-1]) c=1;if(val[i]==val[i-1]) c++;if(c>=m) return true;}return false; } void getans(int l){mp.clear();for(int i=0;i+l<=len;i++){mp[gethash(i,l)].pb(i);} } void init(){xp[0]=1;for(int i=1;i<maxl;i++){xp[i]=xp[i-1]*hash1;} } int main(){freopen("/home/files/CppFiles/in","r",stdin);init();while(cin>>m,m){scanf("%s",s);len=strlen(s);H[len]=0;for(int i=len-1;i>=0;i--){H[i]=H[i+1]*hash1+(ull)s[i];}int l=0,r=len+1;while(r-l>1){int mid=(r+l)/2;if(check(mid)){l=mid;}else{r=mid;}}if(l==0){puts("none");continue;}getans(l);vector<int> pos;for(it=mp.begin();it!=mp.end();it++){if(it->se.size()>=m){sort(it->se.begin(),it->se.end());pos.pb(it->se.bk);}}sort(pos.begin(),pos.end());printf("%d %d\n",l,pos.bk);}return 0; } View Code

?2 POJ 3613 (經過k條邊的最短路

思路：floyd+倍增（快速冪思想）

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio(false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=1005; int N,T,S,E; int mp[maxn][maxn]; int dis[maxn][maxn]; int tmp[maxn][maxn]; int v[maxn]; int num=0; void setINF(int a[][maxn]){for(int i=0;i<num;i++){for(int j=0;j<num;j++){a[v[i]][v[j]]=INF;}} } void cp(int a[][maxn],int b[][maxn]){for(int i=0;i<num;i++){for(int j=0;j<num;j++){a[v[i]][v[j]]=b[v[i]][v[j]];}} } void floyd(int dis[][maxn],int a[][maxn],int b[][maxn]){for(int k=0;k<num;k++){for(int i=0;i<num;i++){for(int j=0;j<num;j++){if(dis[v[i]][v[j]]>a[v[i]][v[k]]+b[v[k]][v[j]]){dis[v[i]][v[j]]=a[v[i]][v[k]]+b[v[k]][v[j]];}}}} } void solve(){while(N){if(N&1){setINF(tmp);floyd(tmp,dis,mp);cp(dis,tmp);}setINF(tmp);floyd(tmp,mp,mp);cp(mp,tmp);N>>=1;} } bool used[maxn]; int main(){freopen("/home/files/CppFiles/in","r",stdin);cin>>N>>T>>S>>E;for(int i=0;i<maxn;i++){for(int j=0;j<maxn;j++){mp[i][j]=INF;}}for(int i=0;i<T;i++){int a,b,l;scanf("%d%d%d",&l,&a,&b);if(!used[a])v[num++]=a,used[a]=1;if(!used[b])v[num++]=b,used[b]=1;if(mp[a][b]>l){mp[a][b]=l;mp[b][a]=l;}}setINF(dis);for(int i=0;i<num;i++) dis[v[i]][v[i]]=0;solve();printf("%d\n",dis[S][E]);return 0; } View Code

3 CodeForces 25E（kmp

題目：給出三個字符串，求包含這三個字符串的字符串的最小長度。

思路：三個字符串全排列一下，計算前一個字符串和后一個字符串的最大重疊部分長度?？梢杂脻L動hash或者kmp。kmp雖然是從頭開始匹配的，但是最后得到的狀態肯定是最大的匹配長度，所以可以只要看最后的狀態就行了。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ */ #include <bits/stdc++.h> #define pb push_back #define se second #define fs first #define sq(x) (x)*(x) #define eps 0.000000001 #define LB lower_bound #define IINF (1<<29) #define LINF (1ll<<59) #define bk back() #define PB pop_back using namespace std; typedef long long ll; typedef pair<ll,ll> P;const int maxl=1e5+3000; char s[3][maxl]; int len[3]; int f[3][maxl]; void getFail(char *p,int *f){int m=strlen(p);f[0]=-1;f[1]=0;for(int i=1;i<m;i++){int j=f[i];while(j&&p[i]!=p[j]) j=f[j];f[i+1]=(p[i]==p[j]?j+1:0);} } int getmax(int x,int y){int i=0,j=0;while(i<len[x]&&j<len[y]){if(j==-1||s[x][i]==s[y][j]){i++,j++;}else{j=f[y][j];}}return j; } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);for(int i=0;i<3;i++){scanf("%s",s[i]);len[i]=strlen(s[i]);}for(int i=0;i<3;i++) getFail(s[i],f[i]);int ans=0;for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(i==j) continue;for(int k=0;k<3;k++){if(i==k||j==k) continue;int tmp=getmax(i,j);if(tmp==len[j]){tmp+=getmax(i,k);}else{tmp+=getmax(j,k);}ans=max(ans,tmp);}}}cout<<len[0]+len[1]+len[2]-ans<<endl;return 0; } View Code

?4 HDU 5348 （歐拉回路，dfs，刪邊

題目：給出一個圖，要求指定邊的方向，使得任意點的出度與入度之差小于等于1.

思路：首先，這個問題是肯定有解的。對于任意一個度為奇數的點，從該點開始dfs，將經過路徑上的邊都刪掉，直到下一個度數為奇的點為之，此時路徑中經過的所有點的度的奇偶性都沒有改變，而兩端點的度都變為了偶數。這樣下去一定可以使得度數全為偶數，并且只有兩端點的出入度差為1.然后再跑一遍歐拉回路就可以給所有的邊找定方向，由于歐拉回路每次有出必有進，所以對出入度只差沒有影響。

另外此題在實現上有幾個技巧，首先是建圖，用數組存邊可以使得正向邊和反向邊相鄰，并且可以通過位運算計算。其次，如果采用vector建圖的話，刪邊每次從back刪就是O(1)，否則會超時（當然也可以寫成鏈表，但是我一般都是用vector）。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio(false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxe=6e5+300; const int maxn=1e5+300; struct EDGE{int to;bool d; }es[maxe]; bool del[maxe]; int deg[maxn]; int eh=0; int ans[maxe]; vector<int> G[maxn]; int T; int n,m; void init(){eh=0;for(int i=0;i<=n;i++){G[i].clear();}memset(ans,0,sizeof ans);memset(del,0,sizeof del);memset(deg,0,sizeof deg); } void addedge(int from,int to){es[eh].to=to;es[eh].d=1;G[from].pb(eh++);es[eh].to=from;es[eh].d=0; G[to].pb(eh++);deg[from]++,deg[to]++; } set<int> d1; void dfs(int v){while(!G[v].empty()&&del[G[v].bk]) G[v].PB();deg[v]--;del[G[v].bk]=del[G[v].bk^1]=1;ans[G[v].bk/2]=es[G[v].bk].d;int to=es[G[v].bk].to;deg[to]--;if(deg[to]%2==0){d1.erase(to);return;}dfs(to); } void eular(int v){while(!G[v].empty()&&del[G[v].bk]) G[v].PB();if(G[v].empty()) return;deg[v]--;EDGE e=es[G[v].bk];del[G[v].bk]=del[G[v].bk^1]=1;ans[G[v].bk/2]=e.d;deg[e.to]--;G[v].PB();eular(e.to); } void solve(){d1.clear();for(int i=1;i<=n;i++){if(deg[i]%2) d1.insert(i);}while(d1.size()){int v=*d1.begin();d1.erase(v);dfs(v);}for(int i=1;i<=n;i++){if(deg[i]){eular(i);}} } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>T;while(T--){cin>>n>>m;init();for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);}solve();for(int i=0;i<m;i++){printf("%d\n",ans[i]);}}return 0; } View Code

?5 HDU 5409(橋，dfs，樹形dp

題目：求一個圖中的橋，以及被該橋隔開的點對，要求第一個點的標號盡量大，第二個點的標號盡量小，并且第一個點大于第二個點。

思路：首先有一個必須要注意到的地方是對于橋而言，兩邊的點就是所有的點，所以答案必然是沒有n的那一邊最大的點，以及比這個點大一的點。然后求橋就是直接上tarjan算法，現在問題就是求出一個橋的左右兩邊最大的點。這個可以通過樹形dp求解。對于每一個點，第一遍dfs記錄該點的子樹包含點的最大值和次大值，第二遍dfs算出這個點通過其父邊走到的那一邊的最大值，這個要就最大和次大值討論一下。然后dp的第一次dfs可以和tarjan寫在一起，第二次直接求出結果。

注意這圖并不是一棵樹，但是可以用一次dfs把它變成一棵樹，并且刪去不在樹上的邊（每條邊給定一個方向），這樣所有的橋必然在樹上，并且被該橋分開的雙連通分量位于橋的兩側。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ * 蒟蒻只能做幾個水題。。 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio(false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=2e5+3000; bool del[maxn]; int es[maxn]; int eh=0; vector<int> G[maxn]; void addedge(int from,int to){es[eh]=to;G[from].pb(eh++);es[eh]=from;G[to].pb(eh++); } int T,n,m; int low[maxn],dfn[maxn],clo,rmax[maxn],smax[maxn],maxid[maxn]; void tarjan_dfs(int v){dfn[v]=low[v]=++clo;for(int i=0;i<G[v].size();i++){int e=G[v][i];if(del[e]) continue;int u=es[e];del[e^1]=1;if(!dfn[u]){tarjan_dfs(u);low[v]=min(low[v],low[u]);if(max(u,rmax[u])>rmax[v]){smax[v]=max(u,rmax[u]);swap(smax[v],rmax[v]);maxid[v]=u;}else if(max(u,rmax[u])>smax[v]){smax[v]=max(u,rmax[u]);}}else{low[v]=min(low[v],dfn[u]);}} } int ans[maxn][2]; bool vis[maxn]; void work(int v,int from,int f){vis[v]=1;for(int i=0;i<G[v].size();i++){int e=G[v][i];if(del[e]||vis[es[e]]) continue;int u=es[e];if(u==maxid[v]){if(max(v,smax[v])>smax[u]){smax[u]=max(v,smax[v]);}}else{if(max(v,rmax[v])>smax[u]){smax[u]=max(v,rmax[v]);}}work(u,e,v);}if(f!=-1&&low[v]==dfn[v]){if(max(v,rmax[v])==n){ans[from/2][0]=max(f,smax[f]);ans[from/2][1]=max(f,smax[f])+1;}else{ans[from/2][0]=max(v,rmax[v]);ans[from/2][1]=max(v,rmax[v])+1;}} } void init(){clo=eh=0;memset(del,0,sizeof del);memset(dfn,0,sizeof dfn);memset(ans,0,sizeof ans);memset(smax,0,sizeof smax);memset(rmax,0,sizeof rmax);memset(vis,0,sizeof vis);for(int i=0;i<=n;i++)G[i].clear(); } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>T;while(T--){cin>>n>>m;init();for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);addedge(a,b);}tarjan_dfs(1);work(1,0,-1);for(int i=0;i<m;i++){printf("%d %d\n",ans[i][0],ans[i][1]);}}return 0; } View Code

?6 PKU 1655（求樹的重心，樹形dp

題目：求一個點，以這個點為根的樹的最大子樹最小。

思路：簡單的樹形dp（dfs？），然而看錯題wa了半個小時==，題目說要輸出number，我以為要輸出數量，結果尼瑪居然是要輸出編號。。。。

7? PKU1741（樹分治

題目：求一棵樹上路徑長度小于k的路徑條數。

思路：這是LTC的男人八題里比較簡單的一道。首先如果不是樹，而是鏈的話，我們可以想到一種分治算法（當然鏈的情況不分治更快），就是對于一個中點，對答案有貢獻的要么是跨越中點的路徑，要么是兩邊的路徑，那么每次從中點分開，進行分治的話復雜度是O(nlogn)，對于這個樹上的情況思路也是一樣的，但是樹上的分治有個比較特殊的地方是這個中點不太好找，需要跑一次dfs。然后對每個分開的子樹遞歸計算。我的實現總共用了5個遞歸，似乎可以少用一個（算子樹的節點數目的時候），但是沒想清楚怎么去，就索性直接又dfs了一遍。

另外，除了這種點分治，還可以使用邊分治，但是邊分治有一種難以避免的使復雜度大大增加的情況（處理方法似乎比較復雜），所以樹分治的首選還是點分治。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ * 蒟蒻只能做幾個水題。。 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=2e4+300; struct EDGE{int to,d; }; vector<int> G[maxn]; EDGE es[maxn]; int eh; int center,mins; bool vis[maxn]; vector<int> dis; int n,k; int cnt; int getCenter(int v,int f){int ssum=0,maxs=0;for(int i=0;i<G[v].size();i++){int e=G[v][i];int u=es[e].to;if(vis[u]||u==f) continue;int aa=getCenter(u,v);if(aa>maxs) maxs=aa;ssum+=aa;}if(max(maxs,cnt-ssum-1)<mins){center=v;mins=max(maxs,cnt-ssum-1);}return ssum+1; } void dfs(int v,int fore,int f){dis.pb(fore);for(int i=0;i<G[v].size();i++){int e=G[v][i];int u=es[e].to;if(vis[u]||u==f) continue;dfs(u,fore+es[e].d,v);} } void cont(int v,int f){cnt++;for(int i=0;i<G[v].size();i++){int e=G[v][i];int u=es[e].to;if(vis[u]||u==f) continue;cont(u,v);} } int cul(int v,int fore){int ans=0;dis.clear();dfs(v,fore,-1);sort(dis.begin(),dis.end());int p=0,q=dis.size()-1;while(p<=q){while(p<=q&&dis[q]+dis[p]>k) q--;if(p>q) break;ans+=q-p;p++;}return ans; } int solve(int v){vis[v]=1;int ans=0;ans+=cul(v,0);for(int i=0;i<G[v].size();i++){int e=G[v][i];int u=es[e].to;if(vis[u]) continue;ans-=cul(u,es[e].d);mins=1e8;cnt=0;cont(u,-1);getCenter(u,-1);ans+=solve(center);}return ans; } void addedge(int from,int to,int d){es[eh].to=to,es[eh].d=d;G[from].pb(eh++);es[eh].to=from,es[eh].d=d;G[to].pb(eh++); } void init(){eh=0;for(int i=0;i<=n;i++)G[i].clear();memset(vis,0,sizeof vis);dis.clear(); } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);while(cin>>n>>k){if(n==0&&k==0) break;init();for(int i=0;i<n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}mins=1e9;dfs(1,0,-1);cnt=0;cont(1,-1);getCenter(1,-1);cout<<solve(center)<<endl;}return 0; } View Code

8?PKU 1390（dp，巧妙思維

題目：若干染了色的盒子排成一排，相同顏色的盒子可以消去，獲益為消去的盒子數平方，求最大獲益。

思路：這個解法比較新穎。自己開始看這個題的之后想的是顏色相同的兩段配對，然后區間dp，然后自己立馬就找了個反例（最后消去的一塊可能來自于最初的多個塊，而不只是2個）。。然后就不會了。對于dp來說，如果出現解決不了的問題，就可以往升高維數的方向考慮。此題除了區間以外，考慮增加一維，表示最后一位與其后同色的配對有多少個（這種情況對應了消去后面k個同色塊之間的其他塊的決策），然后對于這種情況，要么在這個位置把積累的k個塊連同最后一個塊都消掉，要么繼續累計，但是這個累計只能累計到前面的某個同色塊。所以實際的復雜度遠不到O(n^4)，這樣就可以在時間內解決問題了。

?注意這題還有個神奇的優化：其實對于把值往前推的操作，值需要計算最近的同色的位置就行了（我得承認這和我想的有點不一樣==，但是把break提到外面就wa。。。依然是意義不明。。），然后就可以break，這么搞速度能提升到原來的4倍！！

?9 HDU 5001（概率dp，暴力枚舉。

題目：一個人在圖上任意一點開始隨機游走d步，問某點未被經過的概率。

思路：刪去一個點，然后計算在不經過該點的情況下最后到達其他點的概率和即是答案。

?10 Ural1519（插頭dp

題目：一個棋盤中有若干障礙，求經過所有非障礙格子的回路數目。

思路：cdq的論文例題，然而不會寫。。。。幾乎是照著隊友的代碼抄了一遍，毫無成就感。。。插頭dp。。。一定要再自己寫一道。。。。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ * 蒟蒻只能做幾個水題。。 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const ll hashsize=2e6; int n,m; int M[30][30]; int ex,ey; int bit[30]; int hashTab[hashsize]; int Snum[2]; ll dp[2][hashsize],ans; int state[2][hashsize]; bool idx; void hashCal(ll s,ll num){int hashpos=s%hashsize;while(hashTab[hashpos]!=-1){if(state[idx][hashTab[hashpos]]==s){dp[idx][hashTab[hashpos]]+=num;return;}hashpos++;if(hashpos==hashsize) hashpos=0;}hashTab[hashpos]=Snum[idx]++;state[idx][hashTab[hashpos]]=s;dp[idx][hashTab[hashpos]]=num; } void plug_dp(){for(int i=1;i<=n;i++){for(int k=0;k<Snum[idx];k++) state[idx][k]<<=2;for(int j=1;j<=m;j++){idx^=1;Snum[idx]=0;memset(hashTab,-1,sizeof hashTab);for(int k=0;k<Snum[1^idx];k++){int s=state[1^idx][k];int p=(s>>bit[j-1])%4;int q=(s>>bit[j])%4;ll num=dp[idx^1][k];if(!M[i][j]){if(!p&&!q){hashCal(s,num);}}else if(!p&&!q){if(M[i+1][j]&&M[i][j+1]){s+=(1<<bit[j-1])+(2<<bit[j]);hashCal(s,num);}}else if(!p&&q){if(M[i][j+1]) hashCal(s,num);if(M[i+1][j]){s+=(q<<bit[j-1])-(q<<bit[j]);hashCal(s,num);}}else if(p&&!q){if(M[i+1][j]) hashCal(s,num);if(M[i][j+1]){s+=(p<<bit[j])-(p<<bit[j-1]);hashCal(s,num);}}else if(p+q==2){int b=1;for(int t=j+1;t<=m;t++){int v=(s>>bit[t])%4;if(v==1) b++;if(v==2) b--;if(b==0){s-=(1<<bit[t]);break;}}s-=(1<<bit[j-1])+(1<<bit[j]);hashCal(s,num);}else if(p+q==4){int b=1;for(int t=j-2;t>=0;t--){int v=(s>>bit[t])%4;if(v==2) b++;else if(v==1) b--;if(b==0){s+=(1<<bit[t]);break;}}s-=(2<<bit[j-1])+(2<<bit[j]);hashCal(s,num);}else if(p==2&&q==1){s-=(2<<bit[j-1])+(1<<bit[j]);hashCal(s,num);}else if(p==1&&q==2){if(i==ex&&j==ey){ans+=num;}}}}} } void init(){for(int i=0;i<=15;i++)bit[i]=i<<1;dp[0][0]=1;Snum[0]=1; } void read(){char r[30];cin>>n>>m;for(int i=1;i<=n;i++){scanf("%s",r);for(int j=1;j<=m;j++){if(r[j-1]=='*'){M[i][j]=0;}else{M[i][j]=1;ex=i,ey=j;}}} } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout); init();read();plug_dp();cout<<ans<<endl;return 0; } View Code

?11 POJ 3635（最短路

題目：每個城市的油價不同，走一單位距離要消耗一單位油，油箱上限為c，問從s到e的最小花費。

思路：我們可以增加一維，用dis[i][j]表示在城市i有j的油量時的花費，然后這個題就轉換成了1e5個點的最短路。但是我一開始寫錯了，原因是這題要求的到e的最短路，而不是到所有點的最短路，那么首先擴展的時候，每一個點只需要增加1的油量（這是離這個點最近的點，再增加油量的時候等到下次擴展）。另外一旦擴展到了e，立即退出，此時e點必然是最短路，如果不退出勢必會把所有點的滿油量情況都試遍，雖然對于最壞情況兩種寫法是一樣的，但是對于隨機情況效率提升是非常大的。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ * 蒟蒻只能做幾個水題。。 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-3) #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=1005; struct EDGE{int to,d;EDGE(int to,int d):to(to),d(d){} }; struct A{int v,has,cost;bool operator < (const A &C)const{return cost>C.cost;}A(int v,int has,int cost):v(v),has(has),cost(cost){} }; vector<EDGE> G[maxn]; priority_queue<A> Q; int n,m; int cost[maxn][105]; int p[maxn]; int c,s,e; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>n>>m;for(int i=0;i<n;i++){scanf("%d",&p[i]);}for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);G[a].pb(EDGE(b,c));G[b].pb(EDGE(a,c));}int q;cin>>q;while(q--){int cont=0;while(!Q.empty()) Q.pop();scanf("%d%d%d",&c,&s,&e);memset(cost,0x3f,sizeof cost);cost[s][0]=0;Q.push(A(s,0,0));bool f=0;int ans;while(!Q.empty()){cont++;A now=Q.top();Q.pop();int v=now.v,t=now.has;if(v==e) break;if(cost[v][t]<now.cost) continue;if(t+1<=c){if(cost[v][t+1]>cost[v][t]+p[v]){cost[v][t+1]=cost[v][t]+p[v];Q.push(A(v,t+1,cost[v][t]+p[v]));}}for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(t>=e.d){if(cost[e.to][t-e.d]>cost[v][t]){cost[e.to][t-e.d]=cost[v][t];Q.push(A(e.to,t-e.d,cost[e.to][t-e.d]));}}}}if(cost[e][0]<1e8)printf("%d\n",cost[e][0]);else puts("impossible");}return 0; } View Code

?12 ZOJ 3820（樹的直徑，二分

題目：求兩點使得樹上任意一點到這兩點的最短距離中最長的最短。

思路：二分答案，可以注意到這兩點在樹的直徑上肯定是最優的，bfs判定一下即可。

/* * @author: Cwind * http://www.cnblogs.com/Cw-trip/ * 蒟蒻只能做幾個水題。。 */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.00000001 #define IINF (1<<29) #define LINF (1ll<<59) #define INF 1000000000 typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=2e5+300; int n; vector<int> G[maxn]; int dis[maxn]; vector<int> D; bool mark[maxn]; void bfs(int s){memset(dis,-1,sizeof dis);queue<int> Q;dis[s]=0;Q.push(s);while(!Q.empty()){int v=Q.front();Q.pop();for(int i=0;i<G[v].size();i++){int u=G[v][i];if(dis[u]==-1){dis[u]=dis[v]+1;Q.push(u);}}} } void getD(int v,int maxp){D.clear();while(1){D.pb(v);if(v==maxp) break;for(int i=0;i<G[v].size();i++){int u=G[v][i];if(dis[u]+1==dis[v]){v=u;break;}}} } bool vis[maxn]; void bfs_mark(int v,int rem){queue<P> Q;Q.push(P(v,rem));while(!Q.empty()){int u=Q.front().fs;int r=Q.front().se;mark[u]=1,vis[u]=1;Q.pop();for(int i=0;i<G[u].size();i++){int uu=G[u][i];if(!vis[uu]){if(r>0)Q.push(P(uu,r-1));}}} } int ans[2]; bool check(int p){if(p>=D.size()-1){ans[0]=1;ans[1]=2;return 1;}ans[0]=D[p];ans[1]=D[D.size()-1-p];if(ans[1]==ans[0]){ans[1]=D[p-1];}memset(mark,0,sizeof mark);memset(vis,0,sizeof vis);bfs_mark(ans[0],p);memset(vis,0,sizeof vis);bfs_mark(ans[1],p);for(int i=1;i<=n;i++){if(!mark[i]) return 0;}return 1; } int T; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>T;while(T--){cin>>n;for(int i=0;i<=n;i++)G[i].clear();for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);G[a].pb(b);G[b].pb(a);}if(n==2){puts("0 1 2");continue;}bfs(1);int maxd=0,maxp=0;for(int i=1;i<=n;i++){if(dis[i]>maxd){maxd=dis[i];maxp=i;}}bfs(maxp);maxd=0;int maxs=0;for(int i=1;i<=n;i++){if(dis[i]>maxd){maxd=dis[i];maxs=i;}}getD(maxs,maxp);int l=0,r=n-1;while(r-l>1){int mid=(r+l)/2;if(check(mid)){r=mid;}else{l=mid;}}check(r);printf("%d %d %d\n",r,ans[0],ans[1]);}return 0; } View Code

?13 PKU 3071(概率dp

題目：足球賽，每次比賽與相鄰的球隊進行，勝出的晉級。問最后獲勝希望最大的球隊是哪只。

思路：dp[i][j]=第i輪第j只球隊勝出的概率，注意到每輪每只球隊只能與特定范圍內的球隊比賽。

?14 SGU 495

題目：每次在n個盒子中隨機選一個，選m次后沒被選中的盒子期望個數是多少？

思路：由于每個盒子是一樣的，那么這個盒子被選中的期望次數就是它被選中的概率（1減一下即可），然后總的期望次數就是乘n。

?15 ZOJ 3329

題目：置三個色子，每次如果分別等于abc，就分數置零，否則加上擲出的點數，達到n以上退出，問期望步數。

思路：設出dp【0】然后方程變形一下可發現規律，參照：http://blog.csdn.net/xingyeyongheng/article/details/25639827

?16 HDU.4089（概率dp好題

題目：有n個人排名激活網游，我目前在第m位，對于每個人，有可能服務器出故障，他就得從最后開始繼續排，或者他激活成功了，那么就出隊。還有一種可能是系統直接崩潰，隊里的人都激活不了了。?！，F在我覺得如果我都排到前k了，結果系統崩潰了，這就是一件很坑爹的事情，問坑爹的概率。。。

思路：這題連kuangbin大神都說難啊。。。（hdu莫名奇妙改了這題的內存，導致以前能a的代碼基本都a不了了。。雖然滾動一下很簡單但是我莫名就是過不了，然后也不想再耗時間了。。。。）首先dp的狀態就是有i個人，目前排在第j位，到達目標狀態的概率。轉移方程還是很清楚，但是我們會發現轉移會出現環。聯想到之前設出一個值的做法呢？（腦洞不足。。。）但是這題是可以遞推的，首先在轉移中涉及i-1的部分是已經求得的。對于i的部分，涉及的是j-1的值，直接轉移會遇到1然后再要求最后一位的值的情況。但是我們可以把這個情況變換為之前求得的值?；镜南敕ㄊ沁@樣的：我們考慮減少人數（只有當有人激活成功的時候人數才會減少，同時考慮正好到某人崩潰的情況，注意只考慮一圈，因為最終跳出的情況對應了這一輪必然發生了某種變化），那么可以枚舉第一個激活成功的人的位置，可能是第1到第i-1個人，讓這個人激活之后就轉換成了i-1的情況。還有一種情況就是我到了第1，然后正好gg了（這種情況對應了人數始終沒有減少），如果人數一直沒有減少，轉了一圈也沒有gg，那么就回到了開始的情況（我們求解要避免這種無意義的循環）。這樣就可以求的我排在最后的情況，然后求得在第一的情況，問題順利解決。

/* * @author: Cwind */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-9) #define IINF (1<<29) #define LINF (1ll<<59) #define INF (1000000000) #define FINF (1e3) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=2005; int N,M,K; double p1,p2,p3,p4; double dp[2][maxn]; double c[maxn]; double pp[maxn]; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);while(scanf("%d%d%d%lf%lf%lf%lf",&N,&M,&K,&p1,&p2,&p3,&p4)!=EOF){if(p4<eps){puts("0.00000");continue;}memset(dp,0,sizeof dp);memset(c,0,sizeof c);memset(pp,0,sizeof pp);bool f=0;double p=p2/(1-p1);double p33=p3/(1-p1);double p44=p4/(1-p1);dp[f][1]=p44/(1-p);c[1]=p44;pp[0]=1.0;for(int i=1;i<=N;i++) pp[i]=p*pp[i-1];for(int i=2;i<=N;i++){for(int j=2;j<=K;j++) c[j]=p33*dp[f][j-1]+p44;for(int j=K+1;j<=i;j++) c[j]=p33*dp[f][j-1];double tmp=c[1]*pp[i-1];for(int j=2;j<=K;j++) tmp+=c[j]*pp[i-j];for(int j=K+1;j<=i;j++) tmp+=c[j]*pp[i-j];dp[f^1][i]=tmp/(1-pp[i]);dp[f^1][1]=p44+dp[f^1][i]*p;for(int j=2;j<i;j++){dp[f^1][j]=c[j]+dp[f^1][j-1]*p;}f^=1;}printf("%.5f\n",dp[f][M]);}return 0; } View Code

（并未ac）基本與kuangbin大神一致http://www.cnblogs.com/kuangbin/archive/2012/10/03/2710987.html

17 HDU 5442(最小表示法，后綴數組，kmp，二分

題目：求出一個串的最大表示，要求1）如果最大表示是唯一的，輸出起始位置和方向2）如果有兩種一樣的，那么輸出起始位置小的3）如果起始位置也一樣，輸出正向的。

思路：弱不會做。。?？戳藥追荽a，大概有兩種思路，一種是求出后綴數組后亂搞，一種是最小表示法。

本來想最小表示法是比較裸的，寫了一發后發現并不是這樣。最小表示法求出的是最小串的最小起始位置，對于正向而言這個結果正是想要的，但是逆向跑一遍就會發現求出的是（原串中）最后的位置。最小表示法求解主要就要解決這個問題。

我看到兩種搞法，一種是kmp，一種是二分（如果把起始位置往后推，最小表示還能在后面找到的話，最小起始位置就比當前位置小）。

二分感覺是挺自然的一種想法，速度也不差（佩服啊），kmp可以找匹配的最后位置，這個應該是非常重要的一個應用。

（代碼還沒寫。。。）

UPD:第一次寫完之后不明原因一直Ｔ，，，，遂放棄，今天又寫了一遍還是Ｔ．．．簡直日狗．．．然后終于發現ｈｄｕ的ｓｔｒｃａｔ不能ｃｏｐｙ自己．．．．．．但是本地運行好好的．．．．

/* * @author: Cwind */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-6) #define IINF (1<<29) #define LINF (1ll<<59) #define INF (1000000000) #define FINF (1e3) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxlen=1e5+30000; char r[maxlen]; char min1[maxlen],min2[maxlen]; char tmp[maxlen]; char rev[maxlen]; int fail[maxlen]; void getNext(char *s,int *fail,int len){int i=0,j=fail[0]=-1;while(i<len){while(j!=-1&&s[i]!=s[j]) j=fail[j];fail[++i]=++j;} }int MinimumRepresentation2(char *s,int len){ int i=0,j=1,k=0;while(i<len&&j<len&&k<len){int tag=s[(j+k)%len]-s[(i+k)%len];if(tag==0){k++;continue;}if(tag<0)j+=k+1;elsei+=k+1;if(i==j) j++;k=0;}return min(i,j); }int T; int n; int main(){ freopen("/home/files/CppFiles/in","r",stdin);//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);cin>>T;while(T--){cin>>n;scanf("%s",r);strcpy(rev,r);int len=n;for(int i=0;i<n-i-1;i++){swap(rev[i],rev[n-i-1]);}for(int i=len;i<len*2;i++){rev[i]=rev[i-len];}rev[len*2]=0;int p1=MinimumRepresentation2(r,len);for(int i=0;i<len;i++){min1[i]=r[(i+p1)%len];}min1[len]=0;int p2=MinimumRepresentation2(rev,len);for(int i=0;i<len;i++){min2[i]=rev[(i+p2)%len];}min2[len]=0;getNext(min2,fail,len);int i=0,j=0;int last=0;while(i<len*2-1){if(j==-1||min2[j]==rev[i]) i++,j++;else j=fail[j];if(j==len){last=i-len;}}int d=strcmp(min1,min2);if(d>0){printf("%d 0\n",p1+1);}else if(d<0){printf("%d 1\n",len-last);}else{if(p1+1<=len-last){printf("%d 0\n",p1+1);}else{printf("%d 1\n",len-last);}}}return 0; } View Code

18 CF 578/C

題目：求一個x使得數列ai-x的最大連續和的絕對值最小。

思路：裸三分，比賽的時候被卡精度簡直郁悶。。。題解還說了一種方法，感覺很巧妙：構造若干條直線，然后對應每個x的這個pron值就是對應的最高點和最低點之差，然后可以O（n）構造凸包（好像不是凸的？）求解。

http://codeforces.com/blog/entry/20368

19 HDU4219(概率ｄｐ

題目：給出一個樹，隨機指定樹上邊的長度，問最終樹上任意兩點間的距離不超過ｓ的概率．

思路：dp狀態為dp[i][j]表示第ｉ個節點下的最長鏈長度為ｊ時（子樹內長度都不超過ｓ的）概率．

/* * @author: Cwind */ //#pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-6) #define IINF (1<<29) #define LINF (1ll<<59) #define INF (1000000000) #define FINF (1e3) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxlen=520; const int maxn=70; int T,n,l,s; vector<int> G[maxn]; double dp[maxn][maxlen]; double tmp[maxlen]; double tmp2[maxlen]; double prob; void dfs(int v,int f){if(f!=-1&&G[v].size()==1){dp[v][0]=1;return;}dp[v][0]=-1;for(int i=0;i<G[v].size();i++){int u=G[v][i];if(u==f) continue;dfs(u,v);memset(tmp,0,sizeof tmp);for(int j=0;j<=s;j++){for(int a=0;a<=l;a++){if(j+a<=s){tmp[j+a]+=prob*dp[u][j];}}}if(dp[v][0]==-1){for(int j=0;j<=s;j++){dp[v][j]=tmp[j];}}else{memset(tmp2,0,sizeof tmp2);for(int j=0;j<=s;j++){for(int k=0;k<=s;k++){if(k+j>s) break;tmp2[max(k,j)]+=dp[v][j]*tmp[k];}}for(int j=0;j<=s;j++){dp[v][j]=tmp2[j];}}} } void init(){for(int i=0;i<=n;i++){G[i].clear();} } int cas=0; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);cin>>T;while(T--){cin>>n>>l>>s;init();memset(dp,0,sizeof dp);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);G[a].pb(b);G[b].pb(a);}prob=1.0/(l+1);dfs(1,-1);double ans=0;for(int i=0;i<=s;i++){ans+=dp[1][i];}printf("Case %d: %.6f\n",++cas,ans);}return 0; } View Code

?20 HDU4169(樹形背包

題目：在一個樹上選ｋ個點，使得沒有任何一點是另一點的祖先．求最大權值．

思路：挺簡單的一道ｄｐ，但是首先不能開全局數組，會爆內存．其次，有一個很關鍵的優化，就是在子樹中可能節點個數達到ｋ的是很少的，所以要記錄一下節點個數上限，這個優化可以從ｔｌｅ優化到只有１４００ｍｓ．．

/* * @author: Cwind */ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <map> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <stack> #include <functional> #include <set> #include <cmath> using namespace std; #define IOS std::ios::sync_with_stdio (false);std::cin.tie(0) #define pb push_back #define PB pop_back #define bk back() #define fs first #define se second #define sq(x) (x)*(x) #define eps (1e-6) #define IINF (1<<29) #define LINF (1ll<<59) #define INF (1000000000) #define FINF (1e3) typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> P;const int maxn=2e5; int n,k; vector<int> G[maxn]; int a[maxn]; int tmp[305]; int dfs(int v){int dp[305];memset(dp,-1,sizeof dp);dp[0]=0;for(int i=0;i<G[v].size();i++){int u=G[v][i];int num=dfs(u);for(int x=k;x>=0;x--){for(int j=1;j<=num;j++){if(j+x<=k&&dp[x]!=-1&&tmp[j]!=-1){dp[j+x]=max(dp[j+x],dp[x]+tmp[j]);}}}}dp[1]=max(dp[1],a[v]);for(int i=0;i<=k;i++){tmp[i]=dp[i];}for(int i=0;i<=k;i++){if(dp[i]==-1){return i;}} } void init(){for(int i=0;i<=n;i++){G[i].clear();} } int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);while(cin>>n>>k){init();for(int i=1;i<=n;i++){int x;scanf("%d%d",&x,&a[i]);G[x].pb(i);}dfs(0);if(tmp[k]==-1){puts("impossible");}else{printf("%d\n",tmp[k]);}}return 0; } View Code

轉載于:https://www.cnblogs.com/Cw-trip/p/4780036.html

總結

以上是生活随笔為你收集整理的9月——都已经9月了还不好好刷题？。。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：需求：过滤下面这个网页里共723行校对
下一篇：策略路由和路由策略的不同