[XUPT_ACM]寒假第一次比赛题解
寫在前面：本次比賽共11題，設計的是A-E是簡單題，F-H為中等題，I-K為難題，考慮到比賽的友好性，我們并沒有將題目難度打亂，而是基本上按照從簡單到難來排序。比賽的總體出題和預期的差不多，其中B題出題數較少而實際上B題是比較簡單的一道題（可能是題目沒看懂吧），而J題的過題數比預計的要多很多（看來大家數學都不錯）。
比賽地址：https://vjudge.net/contest/280657
下面就對比賽的題目做一下簡單的解答（題目方法不唯一，給出的解法僅供參考）：
神秘連接
A題? ???B題? ? ?C題??? ?D題? ? ?E題? ? ?F題? ? ?G題?????H題??? ?I題? ? ?J題? ? ?K題
?
A題
題意：
魔法球可以用魔法晶體來合成：
黃=2*黃(晶體)
綠=1*黃(晶體)+1*藍(晶體)
藍=3*藍(晶體)
已知有A個黃色晶體B個藍色晶體，要得到x黃y綠z藍個魔法球，問最少還差幾個晶體。
分析：
算出x黃y綠z藍個魔法球所需的黃色晶體AS和藍色晶體總數BS，如果不夠就在結果中加上(AS-A)和(BS-B)。
注意要用long long！
參考代碼：
#include <cstdio> #include <iostream> // 注意要用long long typedef long long ll; using namespace std;ll a,b,as=0,bs=0; ll x,y,z,ans=0;int main() {cin >> a >> b;cin >> x >> y >> z;// 計算所需的黃色晶體和藍色晶體數量as=2*x+y;bs=3*z+y;// 如果不夠就更新答案if (as>a) ans+=(as-a);if (bs>b) ans+=(bs-b);cout << ans << endl;return 0; }?
B題
題意：
這個題意可能比較難理解，其實就是有從左到右n個塔，然后相鄰兩個塔之間a-b層是相通的。問從?ta塔fa層 到?tb塔fb層 的最少步數，移動一次算一步。
分析：
這里我分了以下幾種情況：
1.在同一個塔里的：abs(fa-fb)
2.不在一個塔里的：
（fa<a）：先走到a層，再走到tb塔，再走到fb層：abs(fa-a)+abs(ta-tb)+abs(fb-a)
（fa>b）：先走到b層，再走到tb塔，再走到fb層：abs(fa-b)+abs(ta-tb)+abs(fb-b)
? ? 其他? ?：直接走到tb塔，再走到fb層：abs(ta-tb)+abs(fa-fb)
參考代碼：
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> using namespace std;int n,h,a,b,k,ans; int ta,fa,tb,fb;int main() {cin >> n >> h >> a >> b >> k;while(k--){ans=0;cin >> ta >> fa >> tb >> fb;if (ta==tb)// 直接走到fb層ans=abs(fa-fb);elseif (fa<a)// 先走到a層，再走到tb塔，再走到fb層ans=abs(fa-a)+abs(ta-tb)+abs(fb-a);else if (fa>b)// 先走到b層，再走到tb塔，再走到fb層ans=abs(fa-b)+abs(ta-tb)+abs(fb-b);else// 直接走到tb塔，再走到fb層ans=abs(ta-tb)+abs(fa-fb);cout << ans << endl;}return 0; }?
C題
題意：
鍵盤被偷了，鍵盤編號是x,x+1....x+n-1。已知還剩下的鍵盤編號，問最少丟失的鍵盤數目。
分析：
直接令剩下鍵盤編號中最小的為x最大的為x+n-1，于是總鍵盤數就為最大-最小+1，丟失的鍵盤數目就是 最大-最小+1-n 。
參考代碼：
#include <cstdio> #include <iostream> #include <algorithm> using namespace std;int n; int a[1005];int main() {cin >> n;for (int i=1;i<=n;i++)cin >> a[i];// 排序sort(a+1,a+n+1);cout << a[n]-a[1]+1-n << endl;return 0; }?
D題
題意：
玩游戲拿數字，先手要使最后剩下數字最小，后手相反，拿到只剩下一個為止。
分析：
先手肯定拿最大，后手肯定拿最小。當然純暴力就可以了，不過有一個稍微優雅一點的解法。我們先排序，然后排完序之后的最中間那個數字就是剩下的數字（偶數的話是中間偏左），直接輸出這個數字就是最終結果。
參考代碼：
#include <cstdio> #include <iostream> #include <algorithm> using namespace std;int n; int a[1005];int main() {cin >> n;for (int i=1;i<=n;i++)cin >> a[i];// 排序sort(a+1,a+n+1);// a[(n+1)/2]就是中間的數cout << a[(n+1)/2] << endl;return 0; }?
E題
題意：
用1*2的地磚鋪地板，只能橫著鋪，可以碎成兩個1*1。中間有一個矩形不用鋪，給出位置。
分析：由于只能橫著鋪，就不用考慮怎么鋪了，只要考慮需要幾個1*1的即可。
我們把拖拉機（中間矩形）的上下和左右分開來考慮。
對于拖拉機上下：每一行需要的1*1就是m%2，而上有(x1-1)行，下有(n-x2)行，總共有(x1-1+n-x2)行
對于左右：每一行需要的1*1，左邊需要(y1-1)%2，右邊需要(m-y2)%2，而總共有(x2-x1+1)行
綜上所述：sum(1*1的個數)=(x1-1+n-x2)*(m%2)+(x2-x1+1)*((y1-1)%2+(m-y2)%2)
最終的答案：(sum+1)/2;
參考代碼：
#include <cstdio> #include <iostream> using namespace std;int n,m,x1,x2,y1,y2; int sum=0;int main() {cin >> n >> m >> x1 >> y1 >> x2 >> y2;// 1*1的總數sum=(x1-1+n-x2)*(m%2)+(x2-x1+1)*((y1-1)%2+(m-y2)%2);cout << (sum+1)/2 << endl;return 0; }?
F題
題意：
你有一種特殊的筆，你需要偽造簽名，問你能不能偽造？
分析：
暴力枚舉每個位置，用vis來標記。每次遇到'#'我們都有兩種處理方法。
之前沒標記過的（第一次遇到）：這個點必為特殊筆的左上角，涂色，如果發現涂色的地方有一處不是'#'，則不可能偽造。
之前標記過的（不是第一次遇到）：可以這個點為左上角涂色（也可以不涂），如果可以涂則涂色（這是貪心的思想）。
枚舉完還可以偽造則說明可以 偽造。
參考代碼：
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std;int n,m; char Map[1005][1005]; int vis[1005][1005]; // 以某個位置為左上角涂色 int dir[9][2]={ {0,0},{0,1},{0,2},{1,0},{1,2},{2,0},{2,1},{2,2} };int main() {memset(vis,0,sizeof(vis));// 讀入cin >> n >> m; getchar();for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)scanf("%c",&Map[i][j]);getchar();}// 遍歷找'#'for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){// 為'#'但未標記if (Map[i][j]=='#' && !vis[i][j]){// 越界，不可能涂色，不能偽造if (i>n-2 || j>m-2){printf("NO");return 0;}// 以(i,j)為左上角涂色，若不可以則說明不能偽造for (int k=0;k<9;k++){int nx=i+dir[k][0],ny=j+dir[k][1];vis[nx][ny]=1;if (Map[nx][ny]!='#'){printf("NO");return 0;}}}// 為'#'已標記else if (Map[i][j]=='#'){// 判斷能否涂色int flag=1;for (int k=0;k<9;k++){int nx=i+dir[k][0],ny=j+dir[k][1];if (Map[nx][ny]!='#'){flag=0;break;}}// 若能涂色就涂色if (flag)for (int k=0;k<9;k++){int nx=i+dir[k][0],ny=j+dir[k][1];vis[nx][ny]=1;} }}// 遍歷結束，可以涂色printf("YES\n");return 0; }?
G題
題意：
問你掃雷怎么樣才能贏。
分析：
其實就是看這個棋盤符不符合規則。我們可以碰到一個雷就把周圍一圈的數字都減一，如果最后整個棋盤只有雷和0（包括.)，就說明符合規則。
參考代碼：
#include <cstdio> #include <iostream> using namespace std;int n,m; // 周圍一圈 int dir[8][2]={ {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1} }; char Map[105][105]; bool flag=true;// 判斷是否在棋盤內 bool judge(int x,int y) {if (x>=0 && x<n && y>=0 && y<m)return true;else return false; }int main() {// 讀入scanf("%d%d",&n,&m); getchar();for (int i=0;i<n;i++)scanf("%s",Map[i]);for (int i=0;i<n;i++)for (int j=0;j<m;j++)if (Map[i][j]=='*'){// 把周圍一圈都減一for (int k=0;k<8;k++){int nx=i+dir[k][0],ny=j+dir[k][1];// 周圍一圈不是雷if (judge(nx,ny) && Map[nx][ny]!='*'){ // 如果減完小于0了，那就肯定不能贏了，直接令flag=falseif (Map[nx][ny]!='0' && Map[nx][ny]!='.')Map[nx][ny]--;elseflag=false;}}}// 判斷能不能贏for (int i=0;i<n;i++)for (int j=0;j<m;j++)// 必須只有雷和0(包括.)if (Map[i][j]!='*' && Map[i][j]!='0' && Map[i][j]!='.'){flag=false;break;}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;return 0; }?
H題
題意：
形如[:|||:]的就是手風琴字符串，刪除字符串s中字符，使其變成手風琴，如果可以輸出長度。
分析：
判斷能不能變成手風琴就是要確定'[' , ':' , ':' , ']'的位置p1,p2,p3,p4。
其中p4>p3>p2>p1
'[' 直接找最左邊的，']' 直接找最右邊的確定位置。
':' 就找 '[' 右邊第一個和 ']' 左邊第一個
然后再找p2-p3之間的?'|'
參考代碼：
#include <cstdio> #include <iostream> #include <string> using namespace std;string s; int p1=-1,p2=-1,p3=-1,p4=-1,ans=4;int main() {cin >> s;// 找最左邊的'['位置for (int i=0;i<s.length();i++){if (s[i]=='['){p1=i;break;}}// 沒找到，輸出-1if (p1==-1){cout << -1 << endl;return 0;}// 找'['后第一個':'for (int i=p1+1;i<s.length();i++){if (s[i]==':'){p2=i;break;}}// 沒找到，輸出-1if (p2==-1){cout << -1 << endl;return 0;}// 找最右邊的']'for (int i=s.length()-1;i>=0;i--){if (s[i]==']'){p4=i;break;}}// 沒找到或者在左側':'左邊，輸出-1if (p4==-1 || p4<=p2){cout << -1 << endl;return 0;}// 找右側':'for (int i=p4-1;i>=0;i--){if (s[i]==':'){p3=i;break;}}// 沒找到或者在左側':'左邊，輸出-1if (p3==-1 || p3<=p2){cout << -1 << endl;return 0;}// 找兩個':'中間的'|'for (int i=p2+1;i<=p3-1;i++)if (s[i]=='|')ans++;cout << ans << endl;return 0; }?
I題
題意：
這個題目就是給你n個范圍[Li,Ri]，然后把這些范圍分成兩堆（不能為空），每堆和另外一堆都不能有重合，最后輸出每一個范圍放在哪一堆（沒有輸出-1）。
分析：
我們先將這些范圍按照L從小到大排序，然后依次放到堆1，堆2，先放1再放2，再放1，不斷重復。其中如果放1或者2不可以的話就放回原來那堆。例如前一個范圍放的是堆1，現在的范圍本應該放堆2，但是放堆2會和堆1沖突，于是我們將其放回堆1（放了肯定不會產生沖突）。依次類推直到放完所有的，如果最后有一個堆為空就說明不存在解，輸出-1。
參考代碼：
#include <cstdio> #include <iostream> #include <algorithm> using namespace std;struct node {int l,r;int id; }a[100005];//lmax控制堆1的最大值，rmax控制堆2的最大值 int ans[100005],lmax,rmax;//按照L升序，L相同R小的在前 int cmp(node a1,node a2) {if (a1.l==a2.l)return a1.r<a2.r;elsereturn a1.l<a2.l; }//flag1標記堆1不為空，flag2標記堆2不為空 int T,n,flag1,flag2;int main() {cin >> T;while(T--){lmax=rmax=0; flag1=flag2=0;scanf("%d",&n); a[0].id=2;//記錄idfor (int i=1;i<=n;i++){scanf("%d%d",&a[i].l,&a[i].r);a[i].id=i;}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++){//放堆1if (i==1 || ans[a[i-1].id]==2){//放堆1不沖突if (a[i].l>rmax){ans[a[i].id]=1;//重要！！！一開始只寫了a[i].r，而沒有考慮到a[i].r可能小于a[i-1].rlmax=max(lmax,a[i].r);flag1=1;}//沖突，放堆2else{ans[a[i].id]=2;rmax=max(rmax,a[i].r);flag2=1;}}//放堆2else{//放堆2不沖突if (a[i].l>lmax){ans[a[i].id]=2;rmax=max(rmax,a[i].r);flag2=1;}//沖突，放堆1else{ans[a[i].id]=1;lmax=max(lmax,a[i].r);flag1=1;}}}//兩堆都有if (flag1 && flag2){for (int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");}//只有1堆elseprintf("-1\n");}return 0; }?
J題
題意：
數學題，題目很簡單，問敏敏學姐能不能逃走。
分析：
這題是隊友出的，我只是個數論渣渣啊。
老師肯定是在圓上繞圈圈的，然后老師的角速度就是v2/R。
然后學姐可以在某個Rx上和老師一起保持同樣的速度繞圈圈，這個時候學姐的角速度是v1/Rx=v2/R。
于是乎，一起繞圈圈的時候學姐的Rx=v1*R/v2。
然后呢學姐現在如果和老師一起繞圈圈他最近可以距離圈圈的邊緣(R-Rx)，即和老師保持最遠距離(R+Rx)，此時老師，中心和學姐是在一條直線上的。
然后現在就是學姐能不能逃走的關鍵了，如果她能在最短距離(R-Rx)里逃走那就成功了，此時老師要繞半個圓來抓學姐。
于是學姐的時間就是：(R-Rx)/v1
老師繞圈的時間就是：(pi*R)/v2，tips：這個pi有很多方法計算，也可以手寫多寫幾位
比較一下兩個時間就知道學姐能不能逃脫了，嘿嘿。
參考代碼：
#include <cstdio> #include <iostream> #include <cmath> const double pi=atan(1.0)*4; using namespace std;double R,v1,v2,Rx,t1,t2;int main() {while(cin >> R >> v1 >> v2){Rx=v1*R/v2;t1=(R-Rx)/v1;t2=(pi*R)/v2;if (t1<=t2)cout << "Yes" << endl;elsecout << "No" << endl;}return 0; }?
K題
題意：
哦這題就是防ak的，其實我也不咋會。
分析：
好像是個貪心來著。
參考代碼：
這里是大佬的解答：
https://blog.csdn.net/maxichu/article/details/47867991
轉載于:https://www.cnblogs.com/Radium1209/p/10415328.html
總結
以上是生活随笔為你收集整理的[XUPT_ACM]寒假第一次比赛题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 01 前端篇（标签）
- 下一篇： opentack-openstack组件