20170910校内训练
CCT
最近學校又發(fā)了n本五三題霸，BBS看到后十分高興。但是，當他把五三拿到手后才發(fā)現，他已經刷過這些書了！他又認真地看了一會兒，發(fā)現新發(fā)的這些五三是2017版的，而他刷的是2016版的。現在他想找出所有他沒有刷過的題來刷。每本五三都有m道題，并且它的特征（即它和去年版本的五三的差距）可以用一個m位二進制數來代表，二進制位上的1代表該題不同，0代表該題相同。比如4（100）就代表題目3和去年的有不同、5（101）就代表題目1和題目3和去年的有不同。而BBS熱衷于給自己找麻煩，他要選擇連續(xù)一段的幾本五三一起刷，并且要求，所有選擇的五三的特征中的所有m位中每一位出現1的次數都相同。他又想去刷最多的書，請你告訴他，他最多能刷多少本書？
輸入格式：
第一行為兩個整數 n、m，接下來的n行為 n 個整數，表示每本五三的特征。
輸出格式：
一個整數，表示BBS最多能刷幾本書。
| 樣例輸入 | 樣例輸出 |
| 7 3 7 6 7 2 1 4 2 | 4 |
?
樣例解釋：
這7本五三的特征分別為111,110,111,010,001,100,010。選擇第3本至第6本五三，這些五三的特征中每一位都出現了2次1。當然，選擇第4本到第6本也是可以的，這些五三的特征中每一位都出現了1次1。只是這樣子BBS刷的書的數量就少了，他就會不高興。
數據范圍：
對于 100%的數據：1<=n<=100000，1<=m<=30。?
首先是題意的轉換，怎么去尋找最大的距離
那么我們看例子
7 3 7 6 7 2 1 4 2轉化為2進制
111
110
111
010
001
100
010
每位求前綴和
111
221
332
342
343
443
453
分別減去最右邊的數
000
110《----
110
120
010
110《----
120
就可以發(fā)現是2和6是最遠的相同數字，那么只用6-2=4即可算出答案
那究竟是為什么呢？
顯然，如果一個區(qū)間[x,y]能滿足要求，那么b[y][i]-b[x-1][i]（b數組是前綴和數組，1<=i<=m）必須相等
設b[y][i]=b[x-1][i]+z，那么b[y][i]-b[y][1]=(b[x-1][i]+z)-(b[x-1][1]+z)=b[x-1][i]-b[x-1][1]
這樣就證明了上面那個猜想
這樣問題就轉成了，給定一個矩陣a[n][m]，求對于a[i][j]，找出與它相同的，k最小的a[k][j]（1<=j<=m）
如果不是一個矩陣，而是一個數組，那么隨便做
是矩陣我們就需要對a[i][j](1<=j<=m)進行哈希成一個數，存一下它的最小值
為了避免沖突，我們需要拉鏈
注意，（1）ans至少為1，因為只要有數，它的答案至少都是1。（2）給hash加入00000這種情況
#include<iostream> #include<cstdio> using namespace std; const int mod=5000007; int a[100101],b[100010][32],ans=0,m,n,k=0; int hash[5000010],g[100100][31],next[100100],fro[100100]; void ins(int x,int y) {for(int i=hash[x];;i=next[i])if(!i){ next[++k]=hash[x];hash[x]=k;fro[k]=y;for(int j=1;j<=m;j++)g[k][j]=b[y][j]-b[y][1];break;}else{bool ok=0;for(int j=1;j<=m;j++)if(g[i][j]!=b[y][j]-b[y][1]){ok=1;break;}if(!ok)break;} } int Find(int x,int y) {for(int i=hash[x];i;i=next[i]){bool ok=0;for(int j=1;j<=m;j++)if(g[i][j]!=b[y][j]-b[y][1]){ok=1;break;}if(!ok)return y-fro[i];} } int main() {//freopen("cct.in","r",stdin);freopen("cct.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]=b[i-1][j]+((a[i]>>(j-1))&1);ins(0,0);for(int i=1;i<=n;i++){int tot=0;for(int j=1;j<=m;j++)tot=(tot+(b[i][j]-b[i][1])*j)%mod;ins(tot,i);}for(int i=1;i<=n;i++){int tot=0;for(int j=1;j<=m;j++)tot=(tot+(b[i][j]-b[i][1])*j)%mod;ans=max(ans,Find(tot,i));}printf("%d",ans);return 0; } View CodeMHM
?????? LGL今天一共要上n節(jié)課，這n+1節(jié)課由0標號至n。由于過度勞累，除了第0節(jié)課和第n節(jié)課，LGL還打算睡上m節(jié)課，所以他做了一個睡覺計劃表。通過小道消息，LGL得知WQ今天會在學校中檢查，所以他想少睡k節(jié)課。但是由于某些原因，他又想使相鄰的兩節(jié)睡覺的課之間上的課數量的最小值最大。由于他很困，所以他請你來幫他計算這個值。
輸入格式：
第一行為三個整數 n、m、k，接下來的m行為m個整數ai，表示睡覺計劃表中LGL想要睡覺的課。
輸出格式：
一個整數，表示題目所求的值。
?
| 樣例輸入 | 樣例輸出 |
| 25 5 2 14 11 17 2 21 | 3 |
樣例解釋：
選擇第2節(jié)和第14節(jié)不睡覺，這樣子相鄰的兩節(jié)睡覺的課之間上的課數量的最小值為3，即第17節(jié)和第21節(jié)之間和第21節(jié)到第25節(jié)之間。沒有答案更大的刪除方案。
數據范圍：
對于100%的數據：1<=n<=109，0<=k<=m<=50000，0<ai<n。
跳石頭，二分答案+check
?
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m,k,a[50010]; bool check(int x) {int y=0,z=k;for(int i=1;i<=m+1;i++){if(a[i]-a[y]-1<x)z--;else y=i;}if(z>=0)return 1;return 0; } int main() {//freopen("mhm.in","r",stdin);freopen("mhm.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++)scanf("%d",&a[i]);a[0]=0;a[m+1]=n;sort(a,a+m+2);int l=0,r=n+1;while(l<r){int mid=(l+r)/2;if(check(mid))l=mid+1;else r=mid;}printf("%d",l-1);return 0; } View CodeAAFA
?YYH有n道題要做。每一道題都有一個截止日期t，只要在該日期之前做完，他的父親LRB就會獎勵他w元錢。令人驚訝的是，每一道題他都只需要1秒來做。請問他最多能從父親那里拿到多少錢？
輸入格式：
第一行為一個整數 n，接下來的n行每一行都有兩個數ti和wi，分別表示第i題的截止日期和獎勵。
輸出格式：
一個整數，表示YYH的最大獲利。
?
| 樣例輸入 | 樣例輸出 |
| 3 2 10 1 5 1 7 | 17 |
樣例解釋：
第1秒做第3道題，第2秒做第1道題。
數據范圍：
對于 100%的數據：1<=n、ti 、wi <=100000。
從后往前遍歷時間軸，如果該秒有題，那么把該秒的獎勵加入大根堆，然后對于每一秒，取出最大的值表示做這道題
因為對于某個時間，在這個時間以前都是可以做這道題的，所以很明顯，對于每一秒，取最大值即可
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> using namespace std; priority_queue<int> q; int n;long long ans=0ll; struct xxx{int t,w; }f[100100]; bool cmp(xxx a,xxx b){return a.t>b.t;} int main() { // freopen("aafa.in","r",stdin);freopen("aafa.out","w",stdout);scanf("%d",&n);int y=1;for(int i=1;i<=n;i++)scanf("%d%d",&f[i].t,&f[i].w);sort(f+1,f+n+1,cmp);for(int i=100000;i>=1;i--){while(i==f[y].t){q.push(f[y].w);y++;}if(!q.empty()){ans+=(long long)q.top();q.pop();}}cout<<ans;return 0; } View CodeZZI
?????? YYH拿到了父親給的錢欣喜若狂，把這些錢拿來造了n棟房子。現在他要給這些房子通電。他有兩種方法：第一種是在房間里搭核電發(fā)電機發(fā)電，對于不同的房子，他需要花不同的代價Vi；，第二種是將有電的房子i的電通過電線通到沒電的房子j中，這樣子他需要花的代價為aij。他現在請你幫他算出他最少要花多少錢才能讓所有的房子通上電。
輸入格式：
第一行為一個整數 n。接下來的n行為 n 個整數vi，再接下來的n行每行n個數，第i行第j列的數表示aij。
輸出格式：
一個整數，表示最小代價。
| 樣例輸入 | 樣例輸出 |
| 4 4 4 3 | 9 |
?
樣例解釋：
在第4棟房子造核電發(fā)電機，再將其他三棟房子通過電線連向它。
數據范圍：
對于 100%的數據：1<=n<=300，1<=vi，aij<=100000，保證aii=0，aij=aji。?
建一個0號節(jié)點，把每個節(jié)點向它連一條權值為Vi的無向邊，對于每兩個點，連一條權值為a[i][j]的無向邊，跑最小生成樹
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[310][310],d[310],ans=0; bool used[310]; int main() {//freopen("zzi.in","r",stdin);freopen("zzi.out","w",stdout);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i][0]);a[0][i]=a[i][0];a[0][0]=0;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);memset(d,127,sizeof(d));d[0]=0;for(int i=0;i<=n;i++){int u=-1;for(int j=0;j<=n;j++)if(!used[j]&&(u==-1||d[j]<d[u]))u=j;ans+=d[u];used[u]=1;for(int v=0;v<=n;v++)d[v]=min(d[v],a[u][v]);}printf("%d",ans);return 0; } View Code轉載于:https://www.cnblogs.com/lher/p/7507178.html
總結
以上是生活随笔為你收集整理的20170910校内训练的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： bzoj 4012: [HNOI2015
- 下一篇： zTree插件使用