[大山中学模拟赛] 2016.9.10
生活随笔
收集整理的這篇文章主要介紹了
[大山中学模拟赛] 2016.9.10
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
liao出了一場比賽 簡直想吃狗屎 說好的noip難度？我操
因為有四道題 我簡單的提一下就好了
| [HNOI2007]夢幻島寶珠 |
這一題liao也沒說怎么想到這種dp的 吃屎吧
F[i][j]表示2^i*j的重量 那么的話 F[30][1000]就夠了
然后對于重量為2^i 我們就對當前F[i][j]做一次采藥
然后對于怎么轉到下一個狀態 ，只用考慮兩種情況
1.限制重量轉成二進制對于當前位i來說是0的 但是j對于當前位是1的 顯然要進位 則F[i+1][j>>2+1]=max(F[i][j]);
2.其他的情況 F[i+1][j>>2]=max(F[i][j]);
每一次都保證以后合法 然后F[31][0]就是答案
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define Maxn 110 using namespace std; typedef long long LL; struct node {LL a,b,val;node(){a=b=val=0;} }A[Maxn]; bool Cmp(const node &x,const node &y){return x.b<y.b;} LL N,W; LL F[32][Maxn*10]; LL bit[Maxn]; int main() {while(scanf("%lld%lld",&N,&W)!=EOF){if(N==-1&&W==-1) break;for(LL i=1;i<=100;i++) A[i].a=A[i].b=A[i].val=0;for(LL i=1;i<=N;i++){scanf("%lld%lld",&A[i].a,&A[i].val);while(A[i].a%2==0) A[i].a/=2,A[i].b++;}sort(A+1,A+N+1,Cmp); LL l=1,r; memset(F,0,sizeof(F));bit[0]=1; for(LL i=1;i<=30;i++) bit[i]=bit[i-1]*2;for(LL i=0;i<=30;i++){if(A[l].b==i&&l<=N){r=l; while(A[r+1].b==A[r].b&&r<=N) r++;for(LL j=l;j<=r;j++)for(LL k=1000;k>=A[j].a;k--)F[i][k]=max(F[i][k],F[i][k-A[j].a]+A[j].val);l=r+1;}for(LL j=1000;j>=0;j--){if(((j&1)==1)&&((W&bit[i])==0)) F[i+1][(j>>1)+1]=max(F[i+1][(j>>1)+1],F[i][j]);else F[i+1][(j>>1)]=max(F[i+1][(j>>1)],F[i][j]);}}printf("%lld\n",F[31][0]);}return 0; } View Code?
| 跳蚤 |
第二題簡直惡心 因為是子串 所以我們草了個后綴數組之后 在字典序的表上 二分字典序二分長度 得出子串，,以當前sa[i]開始的子串
然后我們可以用height數組 得出前綴 那么想想 后面的不合法要切開的 就是與sa[i]公共前綴和公共前綴+1要切開
當然公共前綴還要看子串的長度 如果子串比較小 公共前綴比較大也不合法 也要切
然后就變成了很多條線段 要找出K-1個點斷開問可不可以
把左端點從左到右排序 當前下一條線段的右端點小于我當前的右端點 那么min一下右端點 就是在下一條的右端點切開
如果當前的左端點小于我的右端點 那么切不了 只好重新切一個
每一次切都按照最小的右端點切 這樣肯定最優 這個只可意會不可言傳
然后沒了 時間復雜度我也不知道多少不會算反正能過
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define Maxn 100010 using namespace std; int K; char st[Maxn]; int A[Maxn]; int N; int fir[Maxn],sec[Maxn],rank[Maxn],height[Maxn],R[Maxn],sa[Maxn]; void Rsort(int *use,int *in,int *out,int size,int num) {for(int i=0;i<=size;i++) R[i]=0;for(int i=1;i<=num;i++) R[use[in[i]]]++;for(int i=1;i<=size;i++) R[i]+=R[i-1];for(int i=num;i>=1;i--) out[R[use[in[i]]]--]=in[i]; } void SA() {for(int i=1;i<=N;i++) rank[i]=i;Rsort(A,rank,sa,200,N);rank[sa[1]]=1; for(int i=2;i<=N;i++) rank[sa[i]]=rank[sa[i-1]]+(A[sa[i-1]]!=A[sa[i]]);int p=0; int cnt=1;while(cnt<N){for(int i=1;i<=N;i++){fir[i]=rank[i];sec[i]=(i+(1<<p))>N?0:rank[(i+(1<<p))];sa[i]=i;}Rsort(sec,sa,rank,N,N);Rsort(fir,rank,sa,N,N);rank[sa[1]]=1; for(int i=2;i<=N;i++) rank[sa[i]]=rank[sa[i-1]]+(fir[sa[i]]!=fir[sa[i-1]]||sec[sa[i]]!=sec[sa[i-1]]);p++; cnt=rank[sa[N]];} } void Height() {int k=0;for(int i=1;i<=N;i++){if(k>0) k--;if(rank[i]!=1){int pos=sa[rank[i]-1];while(A[pos+k]==A[i+k]) k++;}height[rank[i]]=k;}}int fur[Maxn]; int main() {scanf("%d",&K);scanf("%s",st+1); N=strlen(st+1);for(int i=1;i<=N;i++) A[i]=st[i]-'a';SA();Height();int L=1; int R=N; pair<int,int>ans;while(L<=R){int mid=(L+R)>>1;int l=1; int r=N-sa[mid]+1; int ret=-1;while(l<=r){int m=(l+r)>>1;for(int i=1;i<=N;i++) fur[i]=N+1;int p=mid; int x,y,h; h=m;while(p<=N){x=sa[p]; y=sa[p]+h;fur[x]=min(fur[x],y);p++; h=min(h,height[p]);}int cnt=0; int minr=0;for(int i=1;i<=N;i++){if(fur[i]!=N+1){if(fur[i]==i){cnt=K+1; break;}if(minr<=i) minr=fur[i],cnt++;else minr=min(minr,fur[i]);}}if(cnt<K){ret=m; r=m-1;}else l=m+1;}if(ret==-1) L=mid+1;else{R=mid-1; ans=make_pair(mid,ret);}}for(int i=sa[ans.first];i<sa[ans.first]+ans.second;i++) printf("%c",st[i]);printf("\n");return 0; } /* 2 ababa ba 30% k<=5,len<=30 100% k<=100000,len<=100000 */ View Code?
| 排隊計劃 |
這道題其實應該想到的 逆序對就線段樹或者樹狀數組咯 然后發現每次改變pos這個位置的時候前面的逆序對個數不會影響 后面大于A[pos]這些位置的逆序對個數也不會影響 直接每次找出小于A[pos]的位置 然后改成INT_MAX 減掉答案就好了 我所說的逆序對個數是向右統計的
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<climits> #include<vector> #define Maxn 500010 using namespace std; typedef long long LL; const LL inf=1e9; LL N,M; LL A[Maxn]; LL tot=0; LL root; LL lc[Maxn*4],rc[Maxn*4],C[Maxn*4],Minx[Maxn*4];LL tr[Maxn]; LL low_bit(LL x){return x&(-x);} void Add(LL x) {while(x<=tot){tr[x]++;x+=low_bit(x);} } LL Q(LL x) {LL ans=0;while(x>=1){ans+=tr[x];x-=low_bit(x);}return ans; }void Link1(LL &u,LL L,LL R,LL k) {if(!u) u=++tot;if(L==R){Minx[u]=L; return ;}LL mid=(L+R)>>1;if(k<=mid) Link1(lc[u],L,mid,k);else Link1(rc[u],mid+1,R,k);if(!lc[u]) Minx[u]=Minx[rc[u]];else if(!rc[u]) Minx[u]=Minx[lc[u]];else{if(A[Minx[lc[u]]]>A[Minx[rc[u]]]) Minx[u]=Minx[rc[u]];else Minx[u]=Minx[lc[u]];} } void Clear() {memset(C,0,sizeof(C));memset(lc,0,sizeof(lc));memset(rc,0,sizeof(rc));memset(Minx,0,sizeof(Minx));root=tot=0; }LL ans[Maxn]; void Change(LL u,LL L,LL R,LL k) {if(L==R){Minx[u]=L; return ;}LL mid=(L+R)>>1;if(k<=mid) Change(lc[u],L,mid,k);else Change(rc[u],mid+1,R,k);if(A[Minx[lc[u]]]>A[Minx[rc[u]]]) Minx[u]=Minx[rc[u]];else Minx[u]=Minx[lc[u]]; } LL Query1(LL u,LL L,LL R,LL l,LL r) {if(L>R) return 0;if(L==l&&R==r) return Minx[u];LL mid=(L+R)>>1;if(r<=mid) return Query1(lc[u],L,mid,l,r);else if(l>mid) return Query1(rc[u],mid+1,R,l,r);else{LL k1=Query1(lc[u],L,mid,l,mid);LL k2=Query1(rc[u],mid+1,R,mid+1,r);return A[k1]>A[k2]?k2:k1;} } vector<LL>V; LL mp(LL x) {LL L=0; LL R=tot-1;while(L<=R){LL mid=(L+R)>>1;if(x==V[mid]) return mid;else if(x<V[mid]) R=mid-1;else L=mid+1;} } int main() {scanf("%lld%lld",&N,&M);for(LL i=1;i<=N;i++) scanf("%lld",&A[i]),V.push_back(A[i]);sort(V.begin(),V.end()); tot=unique(V.begin(),V.end())-(V.begin());for(LL i=N;i>=1;i--){ans[i]=Q(mp(A[i]));Add(mp(A[i])+1);}LL sum=0;for(LL i=1;i<=N;i++) sum+=ans[i];printf("%lld\n",sum);Clear();for(LL i=1;i<=N;i++) Link1(root,1,N,i);for(LL i=1;i<=M;i++){LL x; scanf("%lld",&x); LL pos=A[x];LL minx; while(A[minx=Query1(root,1,N,x,N)]<=pos&&pos!=INT_MAX){A[minx]=INT_MAX;Change(root,1,N,minx);sum-=ans[minx];}printf("%lld\n",sum);}return 0; } /* 6 2 160 163 164 161 167 160 2 3 */ View Code?
?
| [Zjoi2016]小星星 |
liao有病出了道容斥原理 我只知道這么一回事但沒做過題
怎么說好呢 樹上的每一個點都可以映射原圖上的每個點 ?只要判斷邊可不可以到就好
那么的話一共十七個點 我們想 不合法的情況肯定會重復映射 那么的話就是扣掉每一個點的并集 也就是容斥原理 那么用 不用扣點的再跑一次減去所有不合法的并集即可
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<vector> #define Maxn 20 using namespace std; typedef long long LL; struct node {LL x,y,next; }edge[Maxn*2]; LL len,first[Maxn]; void ins(LL x,LL y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;} LL N,M; bool v[Maxn][Maxn]; vector<LL>V; LL F[Maxn][Maxn]; void Dfs(LL x,LL fa) {for(LL k=first[x];k!=-1;k=edge[k].next){LL y=edge[k].y; LL s=0;if(y!=fa) Dfs(y,x);}for(LL i=0;i<V.size();i++){F[x][i]=1;for(LL k=first[x];k!=-1;k=edge[k].next){LL y=edge[k].y;if(y!=fa){LL sum=0;for(LL j=0;j<V.size();j++) if(v[V[i]][V[j]]) sum+=F[y][j];F[x][i]*=sum;}}} } int main() {scanf("%lld%lld",&N,&M); memset(v,0,sizeof(v));for(LL i=1;i<=M;i++){LL x,y; scanf("%lld%lld",&x,&y); v[x][y]=v[y][x]=1;}len=0; memset(first,-1,sizeof(first));for(LL i=1;i<N;i++){LL x,y; scanf("%lld%lld",&x,&y); ins(x,y); ins(y,x);} LL ans=0;for(LL i=0;i<(1<<N);i++){V.clear();for(LL j=1;j<=N;j++) if(!(i&(1<<(j-1)))) V.push_back(j);memset(F,0,sizeof(F)); Dfs(1,0);LL s=0; for(LL j=0;j<V.size();j++) s+=F[1][j];if(!((N-V.size())%2)) ans+=s;else ans-=s;}return printf("%lld\n",ans),0; } View Code?
轉載于:https://www.cnblogs.com/wohenshuai/p/5866107.html
總結
以上是生活随笔為你收集整理的[大山中学模拟赛] 2016.9.10的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java 基础知识 练习
- 下一篇： 合成存储方法，局部/全局变量