20170910模擬賽
啊啊啊lrb巨神出題不按難度排序坑死人啦！！！
忠告：正向做題，否則AK！
rk11，總體還是有一定進步，但是我可以300的！！！！！！
不說了，都是淚~
T1：（大喪題）
CCT
最近學(xué)校又發(fā)了n本五三題霸，BBS看到后十分高興。但是，當(dāng)他把五三拿到手后才發(fā)現(xiàn)，他已經(jīng)刷過這些書了！他又認真地看了一會兒，發(fā)現(xiàn)新發(fā)的這些五三是2017版的，而他刷的是2016版的。現(xiàn)在他想找出所有他沒有刷過的題來刷。每本五三都有m道題，并且它的特征（即它和去年版本的五三的差距）可以用一個m位二進制數(shù)來代表，二進制位上的1代表該題不同，0代表該題相同。比如4（100）就代表題目3和去年的有不同、5（101）就代表題目1和題目3和去年的有不同。而BBS熱衷于給自己找麻煩，他要選擇連續(xù)一段的幾本五三一起刷，并且要求，所有選擇的五三的特征中的所有k位中每一位出現(xiàn)1的次數(shù)都相同。他又想去刷最多的書，請你告訴他，他最多能刷多少本書？
輸入格式：
第一行為兩個整數(shù) n、m，接下來的n行為 n 個整數(shù)，表示每本五三的特征。
輸出格式：
一個整數(shù)，表示BBS最多能刷幾本書。
|
樣例輸入 |
樣例輸出 |
|
7 3 7 6 7 2 1 4 2 |
4 |
樣例解釋：
這7本五三的特征分別為111,110,111,010,001,100,010。選擇第3本至第6本五三，這些五三的特征中每一位都出現(xiàn)了2次1。當(dāng)然，選擇第4本到第6本也是可以的，這些五三的特征中每一位都出現(xiàn)了1次1。只是這樣子BBS刷的書的數(shù)量就少了，他就會不高興。
數(shù)據(jù)范圍：
對于 100%的數(shù)據(jù)：1<=n<=100000，1<=k<=30。
原題：[usaco2007 March Gold]Balanced Lineup
題解：
首先可以知道，對于一個特征值a1a2a3..am,可以用(a1-a1)(a2-a1)(a3-a1)...(am-a1)表示它，再做一遍前綴和，得到(s1-s1)(s2-s1)(s3-s1)...(sm-s1)。容易證明，對于兩個相同的狀態(tài)，他們經(jīng)過處理后的前綴和是一樣的。
可以設(shè)t1=s1s2...sm,t2=(s1+x)(s2+x)...(sm+x)，則兩數(shù)之間的差為xx...x，滿足條件
處理后，t1=(s1-s1)(s2-s1)...(sm-s1),t2=(s1+x-s1-x)(s2+x-s1-x)...(sm+x-s1-x)=(s1-s1)(s2-s1)...(sm-s1)，即t1=t2。
所以當(dāng)兩個前綴和pre[i],pre[j]相同的時候，可以推出[i,j-1]或[i+1,j]是合法的區(qū)間。
所以可以直接開一個set記錄一種前綴和第一次出現(xiàn)的位置，邊遍歷邊更新即可。
代碼：
#include<cstdio> #include<set> #define max(a,b) (a>b?a:b) using std::set; int n,m,ans; struct AriM{ int x; int dig[32]; friend bool operator<(AriM a,AriM b){ for(int i=1;i<m;i++) if(a.dig[i]!=b.dig[i])return a.dig[i]<b.dig[i]; return 0; } }t; set<AriM>s; int pre[100005][32]; inline int read(){ int x=0,f=1;char c=getchar(); for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar()); return x*f; } int main(){ freopen("cct.in","r",stdin); freopen("cct.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1,x=read();j<=m;j++) pre[i][j]=pre[i-1][j]+x&(1<<(j-1)); s.insert(t); for(int i=1;i<=n;i++){ t.x=i; for(int j=1;j<m;j++)t.dig[j]=pre[i][j]-pre[i][j+1]; set<AriM>::iterator it=s.find(t); if(it==s.end())s.insert(t); else ans=max(ans,i-(*it).x); } printf("%d\n",ans); return 0; }
T2：
MHM
LGL今天一共要上n節(jié)課，這n節(jié)課由0標號至n。由于過度勞累，除了第0節(jié)課和第n節(jié)課，LGL還打算睡上m節(jié)課，所以他做了一個睡覺計劃表。通過小道消息，LGL得知WQ今天會在學(xué)校中檢查，所以他想少睡k節(jié)課。但是由于某些原因，他又想使相鄰的兩節(jié)睡覺的課之間上的課數(shù)量的最小值最大。由于他很困，所以他請你來幫他計算這個值。
輸入格式：
第一行為三個整數(shù) n、m、k，接下來的m行為m個整數(shù)ai，表示睡覺計劃表中LGL想要睡覺的課。
輸出格式：
一個整數(shù)，表示題目所求的值。
|
樣例輸入 |
樣例輸出 |
|
25 5 2 14 11 17 2 21 |
3 |
樣例解釋：
選擇第2節(jié)和第14節(jié)不睡覺，這樣子相鄰的兩節(jié)睡覺的課之間上的課數(shù)量的最小值為3，即第17節(jié)和第21節(jié)之間和第21節(jié)到第25節(jié)之間。沒有答案更大的刪除方案。
數(shù)據(jù)范圍：
對于100%的數(shù)據(jù)：1<=n<=109，1<=k<=m<=50000，0<ai<n。
原題：noip2015提高組d2t1
題解：傻逼二分，check，輸出答案（這么水的題我居然打炸了）
細節(jié)見代碼：
#include<cstdio> #include<algorithm> #define mid (l+r>>1) int n,m,k,l,r,a[50005]; inline int read(){ int x=0,f=1;char c=getchar(); for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar()); return x*f; } bool check(int x){ for(int i=1,pos=0,cnt=0;i<=m;i++) if(a[i]-pos<=x){if(++cnt>k)return 0;} else pos=a[i]; return 1; } int main(){ freopen("mhm.in","r",stdin); freopen("mhm.out","w",stdout); n=r=read();m=read();k=read(); for(int i=1;i<=m;i++)a[i]=read(); std::sort(a+1,a+m+1);a[++m]=n; while(l<=r)check(mid)?l=mid+1:r=mid-1; printf("%d\n",l-1); return 0; }
T3：
AAFA
YYH有n道題要做。每一道題都有一個截止日期t，只要在該日期之前做完，他的父親LRB就會獎勵他w元錢。令人驚訝的是，每一道題他都只需要1秒來做。請問他最多能從父親那里拿到多少錢？
輸入格式：
第一行為一個整數(shù) n，接下來的n行每一行都有兩個數(shù)ti和wi，分別表示第i題的截止日期和獎勵。
輸出格式：
一個整數(shù)，表示YYH的最大獲利。
|
樣例輸入 |
樣例輸出 |
|
3 2 10 1 5 1 7 |
17 |
樣例解釋：
第1秒做第3道題，第2秒做第1道題。
數(shù)據(jù)范圍：
對于 100%的數(shù)據(jù)：1<=n、ti 、wi <=100000。
（原創(chuàng)題）
題解：
首先可以按照截止時間把作業(yè)排序，然后從前往后掃描。
當(dāng)選到第i個的時候，若已選數(shù)量小于截止時間，則選該任務(wù)一定比不選要優(yōu)。
若已選數(shù)量等于截止時間，則考慮能否用該任務(wù)替代以前所選的最小收益任務(wù)，可以直接把已選任務(wù)丟進一個小根堆，直接與堆頂元素比較即可。
代碼：
#include<cstdio> #include<algorithm> #include<queue> using std::priority_queue; typedef long long ll; struct AriM{ int t,w; friend bool operator<(AriM a,AriM b){ return a.t<b.t; } }a[100005]; priority_queue<int,std::vector<int>,std::greater<int> >q; int n; ll ans,sz; template<typename T>T read(){ T x=0,f=1;char c=getchar(); for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar()); for(;c>='0'&&c<='9';x=x*10+c-48,c=getchar()); return x*f; } int main(){ freopen("aafa.in","r",stdin); freopen("aafa.out","w",stdout); n=read<int>(); for(int i=1;i<=n;i++)a[i].t=read<ll>(),a[i].w=read<ll>(); std::sort(a+1,a+1+n); for(int i=1;i<=n;i++,sz=q.size()) if(sz<a[i].t)q.push(a[i].w); else if(sz==a[i].t&&q.top()<a[i].w) q.pop(),q.push(a[i].w); while(!q.empty())ans+=q.top(),q.pop(); printf("%I64d\n",ans); return 0; }
T4：
ZZI
YYH拿到了父親給的錢欣喜若狂，把這些錢拿來造了n棟房子。現(xiàn)在他要給這些房子通電。他有兩種方法：第一種是在房間里搭核電發(fā)電機發(fā)電，對于不同的房子，他需要花不同的代價Vi；，第二種是將有電的房子i的電通過電線通到?jīng)]電的房子j中，這樣子他需要花的代價為aij。他現(xiàn)在請你幫他算出他最少要花多少錢才能讓所有的房子通上電。
輸入格式：
第一行為一個整數(shù) n。接下來的n行為 n 個整數(shù)vi，再接下來的n行每行n個數(shù)，第i行第j列的數(shù)表示aij。
輸出格式：
一個整數(shù)，表示最小代價。
|
樣例輸入 |
樣例輸出 |
|
4 4 4 3 |
9 |
樣例解釋：
在第4棟房子造核電發(fā)電機，再將其他三棟房子通過電線連向它。
數(shù)據(jù)范圍：
對于 100%的數(shù)據(jù)：1<=n<=300，1<=vi，aij<=100000，保證aii=0，aij=aji。
經(jīng)典的供電問題，但我沒打過233
題解：
仔細讀題，可以證明最優(yōu)方案一定由x個發(fā)電機和(n-x)條電線組成，符合MST的性質(zhì)。
于是考慮新增加一個0號節(jié)點，與1~n號節(jié)點連權(quán)值為vi的雙向邊，節(jié)點i和節(jié)點j之間連權(quán)值為aij的雙向邊，直接跑一遍prim即可。
代碼：
#include<cstdio> #define inf 0x3f3f3f3f #define min(a,b) (a<b?a:b) int n; int d[305],map[305][305]; bool used[305]; inline int read(){ int x=0,f=1;char c=getchar(); for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar()); return x*f; } int prim(){ int res=0; for(;;){ int pos=-1,lim=inf; for(int i=1;i<=n;i++) if(!used[i]&&d[i]<lim) lim=d[i],pos=i; if(pos<0)return res; res+=d[pos];used[pos]=1;d[pos]=0; for(int i=1;i<=n;i++) if(!used[i])d[i]=min(d[i],map[pos][i]); } } int main(){ freopen("zzi.in","r",stdin); freopen("zzi.out","w",stdout); n=read(); for(int i=1;i<=n;i++)d[i]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=read(); printf("%d\n",prim()); return 0; }
浙公網(wǎng)安備 33010602011771號