20170903模擬賽
失蹤人口回歸
這次比賽真心喪，還好有T1，不然早就爆0了。
T1:
卡片(card)
【題目描述】
lrb喜歡玩卡牌。他手上現在有張牌，每張牌的顏色為紅綠藍中的一種。現在他有兩種操作。一是可以將兩張任意位置的不同色的牌換成一張第三種顏色的牌；二是可以將任意位置的兩張相同顏色的牌換成一張該顏色的牌。兩個操作后都可以將生成的牌放到任意位置。現在他想知道，最后一張牌可能是什么顏色的。
【輸入描述】
第一行輸入一個，表示卡牌數量。
第二行輸入一個由’B’,’G’,’R’組成的長度為的字符串，分別表示卡牌的顏色為藍色、綠色、紅色中的一種。
【輸出描述】
輸出’B’,’G’,’R’中的若干個字母，按字典序輸出。代表可能的最后一張牌的顏色。
【樣例】
|
輸入1 |
輸出1 |
|
2 RB |
G |
|
輸入2 |
輸出2 |
|
3 GRG |
BR |
|
輸入3 |
輸出3 |
|
4 BBBB |
B |
【數據范圍】
n<=200
題解：傻逼判斷題吧，會if和for就能A吧。
由于第二種操作，所有張數大于二的牌都默認等于2，
（一）如果所有顏色都有，顯然可以合成所有顏色；
（二）如果只有一種顏色，顯然只有這種；
（三）如果有兩種顏色張數大于二，同（一）；
（四）如果出現0 1 2的情況，則可以合成0和1兩種；
（五）如果出現0 1 1的情況，則可以合成0一種；
應該就這些了吧
代碼：
#include<cstdio> #define Fn "card" char s[205]; int main(){ freopen(Fn".in","r",stdin); freopen(Fn".out","w",stdout); int n; bool r=0,g=0,b=0,r2=0,g2=0,b2=0; scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++) switch(s[i]){ case 'R':if(!r)r=1;else if(!r2)r2=1;break; case 'G':if(!g)g=1;else if(!g2)g2=1;break; case 'B':if(!b)b=1;else if(!b2)b2=1; } if(r&&g&&b||(int)(r2)+g2+b2>1){puts("BGR");return 0;} if((int)(r)+g+b==1){if(r)puts("R");if(g)puts("G");if(b)puts("B");return 0;} if(r2&&(g||b)){puts("BG");return 0;} if(g2&&(r||b)){puts("BR");return 0;} if(b2&&(r||g)){puts("GR");return 0;} if(g&&b){puts("R");return 0;} if(g&&r){puts("B");return 0;} if(r&&b){puts("G");return 0;} }
（寫的賊丑）
T2：
取數(win)
【題目描述】
lrb目前有個數字，他想知道這個數中選出若干個數，平均數減中位數的最大值是多少。可以證明，對于一個遞增數列，如果是平均數減中位數最大時的中位數，表示在兩邊分別取相鄰數字的數量，表示以為中位數，在兩側各取相鄰個數時平均數減中位數的值，那么為關于的單峰函數。
【輸入描述】
第一行為，為數字個數。
第二行有個數，分別代表個數字。
【輸出描述】
輸出一個數，為平均數減中位數的最大值，保留兩位小數。
【樣例】
|
輸入 |
輸出 |
|
4 1 2 3 4 |
0.33 |
題解：
首先取奇數個數顯然不會比取偶數個數劣。因為多取一個數導致中位數在中間取平均值會導致中位數更偏向平均數。
其次在確定了中位數后，對于一個最優解的中位數，它向兩邊拓展時必然是一個單峰函數（題目中已告知），否則會有一個位置取中位數比它更優。所以我們可以直接枚舉中位數，對于每個位置三分這個位置的最優解/較優解并更新答案即可。
三分！！！！
看到了單峰函數沒想到三分我也是醉了
不了解三分的可以看一下這位神犇的博客：http://blog.csdn.net/pi9nc/article/details/9666627
代碼：
#include<cstdio> #include<algorithm> #define mid1 ((rt-lt)/3+lt) #define mid2 (rt-(rt-lt)/3) #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) #define r register #define Fn "win" typedef long long ll; typedef double d; using std::sort; double h; int n,a[100005]; ll pre[100005]; inline int read(){ r int x=0,f=1;r 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; } d check(ll w,ll l){ ll sum=pre[w]-pre[w-l-1]+pre[n]-pre[n-l]; return (d)sum/(d)(l*2+1)-(d)a[w]; } int main(){ freopen(Fn".in","r",stdin); freopen(Fn".out","w",stdout); n=read(); if(n<3){puts("0.00");return 0;} for(r int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+1+n); for(r int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i]; for(r int i=1;i<=n;i++){ r ll lt=0,rt=min(i-1,n-i); while(lt<rt) if(check(i,mid1)>check(i,mid2))rt=mid2-1; else lt=mid1+1; h=max(h,check(i,lt)); } printf("%.2lf\n",h); return 0; }
（一寫三分就想用宏）
T3：
密碼(key)
【題目描述】
lrb去柜員機取錢，并輸入了他的四位密碼。但是這一切都被一個黑幫拍攝了下來。幸好，這一次他的銀行卡里并沒有剩余任何錢。lrb知道了他的賬戶被異常登錄后十分害怕，然后修改了他的密碼。從此以后他為了不被看出密碼，他開始“徐晃”。但這一切還是被拍攝了下來，拍攝多次以后，這個黑幫找到了你，希望你在一秒內幫他算出lrb的可能使用的密碼數量。
【輸入描述】
第一行輸入一個，為lrb被拍攝的動作次數。
接下來行，每行第一個數為，表示lrb接下來的手指移動次數，接下來為一個長度為的數字串，表示lrb手指經過的軌跡。lrb手指經過的位置，可能沒有按，也有可能按了多次。
【輸出描述】
輸出一行，為可能的密碼數量。
【樣例】
|
輸入 |
輸出 |
|
2 3 123 3 234 |
5 |
|
解釋 |
|
|
lrb可能用的是2222,2223,2233,2333,3333五種密碼 |
|
題解：
（話說學長們就是這樣互D的嗎）
首先可以在O（10L）的時間內預處理出對于每一位向后的第一個某個數字的位置。然后就可以O（10000）暴力dfs每種密碼后用O（n）的時間進行check，最后統計進答案即可。有一個加快程序的小技巧是在暴力dfs每種密碼時不枚舉那些相鄰兩位數相同的密碼，而是將它們表示為權值直接加入答案。另外這題的空間比較緊張，如果比較虛的可以像我一樣動態開點：
char *s; s=new char[len+5]; scanf("%s",s+1);
不過指針這東西真別多用，用不好后果很慘重。
代碼：
#include<cstdio> #include<cstring> #define r register #define Fn "key" typedef unsigned short us; const us temp[5]={0,1,3,3,1}; int n,ans; us l[1005]; char *s[1005]; char a[5]; struct AriM{ us last[10]; void init(){memset(last,0,10*sizeof(us));} }*suf[1005]; inline us read(){ r us x=0;r short f=1;r 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; } inline bool check(int st){ int cnt,h; for(r int i=1;i<=n;i++){ for(cnt=1,h=0;cnt<=st;cnt++) if(suf[i][h].last[a[cnt]])h=suf[i][h].last[a[cnt]];else break; if(cnt<=st)return 0; } return 1; } inline void dfs(int st){ for(r char i=0;i<10;i++) if(i!=a[st-1]){ a[st]=i; if(check(st))ans+=temp[st]; if(st<4)dfs(st+1); } } int main(){ freopen(Fn".in","r",stdin); freopen(Fn".out","w",stdout); n=read(); for(r int i=1;i<=n;i++){ l[i]=read(); s[i]=new char[l[i]+5]; suf[i]=new AriM[l[i]+5]; scanf("%s",s[i]+1); r AriM t;t.init(); for(r int j=l[i];j>=0;j--){ suf[i][j]=t; if(j)t.last[s[i][j]-'0']=j; } } a[0]=-1; dfs(1); printf("%d\n",ans); return 0; }
T4：
三角之戀(tri)
【題目描述】
給出平面上的個等腰直角三角形。每個三角形用個整數描述。一個三角形的3個頂點分別是,和。
你的任務是計算這些三角形覆蓋的總面積。
【輸入描述】
第一行為，為三角形個數。
接下來每行三個數，用于描述一個三角形。
【輸出描述】
輸出一個數，為這些三角形覆蓋的總面積，保留一位小數。
【樣例】
|
輸入 |
輸出 |
|
5 -5 -3 6 -1 -2 3 0 0 2 -2 2 1 -4 -1 2 |
24.5 |
題解：
解決這題需要離散化并用掃描線。
首先需要離散每個三角形的(x,y),(x+m,y)(x,y+m)三個點，以便于后面計算答案。
然后我們將每個三角形記做一個只有底部線段，并且右端點不斷向縮小的線。在更新時直接暴力排序每個線段并踢出會被某個其他線段覆蓋的線段，然后將y坐標不斷往上推，在過程中暴力計算每個離散長方形的面積，如果某個長方形沒被完全覆蓋，那么就減去沒覆蓋的部分的面積。這樣就可以在的時間復雜度內算出答案。
掃描線真的難打，打了一個小時，看來熟練度還是不夠啊！
代碼：
#include<bits/stdc++.h> #define lb(x,y,z) (lower_bound(x+1,x+y+1,z)-x) #define r register #define Fn "tri" using namespace std; typedef long long ll; struct AriM{ int x,y,x2,m,tx,ty; }l[5005],s[10005]; int n,cntx,cnty,cnts,th; int X[10005],Y[10005]; ll ans; bool used[10005]; inline int read(){ r int x=0,f=1;r 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 cmp(const AriM &a,const AriM &b){ if(a.y!=b.y)return a.y<b.y; if(a.x!=b.x)return a.x<b.x; return a.tx<b.tx; } void solve(){ int t=Y[th+1]-Y[th],rt; for(r int i=s[1].x,j=1;X[i]<=s[cnts].x2;i++){ while(j<cnts&&i>=s[j+1].x)j++; if(X[i]>=s[j].x2)continue; rt=min(X[i+1],s[j].x2); ans+=2ll*(rt-X[i])*t; if(rt>s[j].x2-t) if(X[i]<s[j].x2-t)ans-=(ll)(rt-s[j].x2+t)*(rt-s[j].x2+t); else ans-=(ll)(rt-X[i])*(rt-X[i])+2ll*(X[i]-s[j].x2+t)*(rt-X[i]); } th++; for(r int i=1;i<=cnts;i++) if(s[i].ty<th)used[i]=0; else used[i]=1,s[i].x2=X[s[i].tx]-Y[th]+Y[s[i].y]; r int lt=cnts;cnts=0; for(r int i=1;i<=lt;i++) if(used[i])s[++cnts]=s[i]; } int main(){ freopen(Fn".in","r",stdin); freopen(Fn".out","w",stdout); n=read(); for(r int i=1;i<=n;i++){ l[i].x=read();l[i].y=read();l[i].m=read(); X[++cntx]=l[i].x;X[++cntx]=l[i].x+l[i].m; Y[++cnty]=l[i].y;Y[++cnty]=l[i].y+l[i].m; } sort(X+1,X+cntx+1); sort(Y+1,Y+cnty+1); cntx=unique(X+1,X+cntx+1)-X-1; cnty=unique(Y+1,Y+cnty+1)-Y-1; X[cntx+1]=Y[cnty+1]=2e9; for(r int i=1;i<=n;i++){ l[i].tx=lb(X,cntx,l[i].x+l[i].m); l[i].ty=lb(Y,cnty,l[i].y+l[i].m); l[i].x=lb(X,cntx,l[i].x); l[i].y=lb(Y,cnty,l[i].y); l[i].x2=X[l[i].tx]; } sort(l+1,l+n+1,cmp); l[n+1].y=cnty+1; s[cnts=1]=l[1];th=l[1].y;s[0].x2=-2e9; for(r int i=2;i<n+2;i++){ while(cnts&&l[i].y>th)solve(); th=max(th,l[i].y); r bool f=0; for(r int j=1;j<=cnts;j++) if(l[i].x<s[j].x){ if(l[i].x2<=s[j-1].x2)break; for(r int k=cnts;k>=j;k--)s[k]=s[k-1]; s[j]=l[i]; r int lt=cnts;cnts=j; for(r int k=j+1;k<=lt;k++) if(s[k].x2>s[j].x2)s[++cnts]=s[k]; f=1; } if(!f&&l[i].x2>s[cnts].x2)s[++cnts]=l[i]; } printf("%I64d.%c\n",ans/2,ans&1?'5':'0'); return 0; }
浙公網安備 33010602011771號