河南工大2024新生周賽（7）----命題人 劉義 題解
問題 A: 圓：
這是一個數學題，畫圖可得，4 個圓時，分割成 14 個區域，可以推導出結論：當圓為0個時，區域數為1個，當圓有x個的時候，區域數有x*x-x+2;
#include<bits/stdc++.h> using namespace std; #define int long long int n; signed main(){ int a,b;//a為圓的個數，b為區域數 cin>>n; while(n--) { cin>>a; if(a==0) b=1; else b=a*a-a+2; cout<<b<<" "; } return 0; }
問題 B: 旅人分寶：
這是一個經典的海盜分金問題，每個旅人只會選擇一個對自己最有利的情況，并且要求50%以上的同意，所以當老大給一半的人每一個人一個金幣，他們就會同意了。
#include<bits/stdc++.h> using namespace std; int t; int n,x; int main() { cin>>t; while(t--) { cin>>n>>x; if(x%2==0) { cout<<n-x/2+1<<endl; } else { cout<<n-x/2<<endl; } } return 0; }
問題 C: A*B：
經典的高精度乘法：
#include <stdio.h> #include <string.h> //翻轉函數 void reverse (int d[510], int len) { int temp, mid = len/2; for (int i = 0, j = len - 1; i < mid, j >= mid; i++, j--) { temp = d[i]; d[i] = d[j]; d[j] = temp; } } int main () { char s1[2005], s2[2005]; int a[2005], b[2005], c[4010] = {0}; scanf("%s", s1); scanf("%s", s2); int lena = strlen(s1); int lenb = strlen(s2); int lenc = lena + lenb; //將char的1轉為int的1 for (int i = 0; i < lena; i++) { a[i] = s1[i] - '0'; } for (int i = 0; i < lenb; i++) { b[i] = s2[i] - '0'; } reverse(a, lena); reverse(b, lenb); //核心代碼 for (int i = 0; i < lenb; i++) { for (int j = 0; j < lena; j++) { c[i+j] += b[i] * a[j]; c[i+j+1] += c[i+j] / 10; c[i+j] = c[i+j] % 10; } } //處理前導0 lenc = lenc - 1; while (c[lenc] == 0 && lenc >= 1) { lenc--; } //輸出 for (int i = lenc; i >= 0; i--) { printf("%d", c[i]); } return 0; }
問題 D: 時間加速器：
首先考慮暴力做法，即枚舉最終答案ans，對于第一個可行的ans一定是最優解（在ans時間內可以完成在ans+t(t>=0)的時間內也就一定可以完成）由于N<=500000的數據范圍絕對會TLE，因此需要優化。
接下來考慮優化，由于之前提到的性質，設f(i)表示在i時間內有無可能完成，那么f數組必定滿足單調性。那么我們可以二分最終答案ans，對于每一個ans對其進行暴力check：對于每一件任務，如果它能在ans天內完成（完成度<=ans*a），那么就不必使用時間加速器，接下來處理必須使用時間加速器的情況，當i號任務不能被直接完成時，我們需要用((x[i]-a*mid)%b==0?(x[i]-a*mid)/b:(x[i]-a*mid)/b+1;)次時間加速器進行完成，最后只需看時間加速器使用總數是否小于等于mid即可。
#include<iostream> #define int long long using namespace std; int n,a,b,x[600006]; bool check(int mid)//判斷函數 { int tot=0; for(int i=1;i<=n;i++) { if(x[i]<=mid*a)continue; else { if((x[i]-mid*a)%b==0)tot+=(x[i]-mid*a)/b; else tot+=((x[i]-mid*a)/b+1); } } return tot<=mid; } signed main() { cin>>n>>a>>b; for(int i=1;i<=n;i++)cin>>x[i]; int l=0,r=1e9,mid; while(l<=r)//二分搜索 { mid=(l+r)/2; if(check(mid))r=mid-1; else l=mid+1; } cout<<l<<endl; return 0; }
問題 E: 切巧克力：
輸入
4 2
4 5 6
1
輸出
19
如果先切橫的，結果就是1+2?4+2?5+2?6=311+2?4+2?5+2?6=31。
如果先切豎的，結果就是4+5+6+1?4=194+5+6+1?4=19。
顯然先切豎的更優。
由此，可以得出一個結論：先切代價大的。
于是，思路就出來了。先把兩個數組從大到小排序，然后兩個數組挨個比較，較大的就在答案上加上這個代價（要乘上切了多少刀），再把指針往后挪一位，直到全部算完即可。
#include<iostream> #include<cmath> #include<algorithm> using namespace std; int n, m; int a[10005], b[10005];//橫線和豎線的代價 int main() { cin >> n >> m; int s1 = 1, s2 = 1;//s1和s2可以是a數組和b數組的指針，也可以是橫縱分成的塊數 for (int i = 1; i <= n-1; i++) { cin >> a[i]; } for (int i = 1; i <= m - 1; i++) { cin >> b[i]; } for(int i=1;i<=n-1;i++) { for(int j=1;j<=n-1-i;j++) { if(a[j]<a[j+1]) { int t; t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(int i=1;i<=m-1;i++) { for(int j=1;j<=m-1-i;j++) { if(b[j]<b[j+1]) { int t; t=b[j]; b[j]=b[j+1]; b[j+1]=t; } } } long long ans = 0; for (int i = 2; i < n + m; i++) { if (a[s1] > b[s2]) ans += s2 * a[s1++];//選擇大的，這里s2表示塊數，s1指針后移一位 else ans += s1 * b[s2++];//同理，和上面相反 } cout << ans << endl; return 0; }
問題 F: 建房子：
構建一個01背包。
思路是將體力看做背包 將石子看做物品 然后就很自然地得出了本題的狀態轉移方程：
f[j]=max(f[j],f[j-w[i]]+v[i])
#include<stdio.h> #include<bits/stdc++.h> using namespace std; int n,V,c; int v[100001],l[100001];//v：石頭體積 l；所需的體力 int dp[100001]; int main() { scanf("%d %d %d",&V,&n,&c); int sum=0; for(int i=1;i<=n;i++) { scanf("%d %d",&v[i],&l[i]); sum+=v[i]; } if(sum<V)//若石子總體積<V { printf("Impossible"); return 0; } for(int i=1;i<=n;i++) { for(int j=c;j>=l[i];j--) { dp[j]=max(dp[j],dp[j-l[i]]+v[i]); } } for(int i=0;i<=V;i++)//從小到大搜 第一個大于V的直接輸出 { if(dp[i]>=V) { printf("%d",c); return 0; } } printf("Impossible"); return 0; }
問題 G: 命運之橋：
此題可以用排序做（高檔一點的模擬）
核心思想：兩個人相遇轉身，相當于交換靈魂后繼續走
最大值：最靠近端點兩個人各自向對方走,時間較長的那個人的時間
最小值：所有人中走完橋最小值中的最大值
#include<iostream> #include<cmath> #include<algorithm> using namespace std; int l, a[100001]; int main() { int n; scanf("%d",&l); scanf("%d",&n); if (!n) { printf("0 0\n"); return 0; } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + 1 + n); //從小到大排序（算最長時間時可能方便一些） int max_time, min_time; for (int i = 1; i <= n; i++) { min_time = max(min(a[i], l + 1 - a[i]), min_time);//最短時間就是所有人中走完橋最小值中的最大值 } max_time = max(l + 1 - a[1], a[n]);//最長時間就是最靠近端點兩個人各自向對方走, printf("%d %d", min_time, max_time); return 0; }
問題 H: 惡魔：
一個惡魔能殺掉的最大個數應該為兩側小于它血量的第一個的惡魔能殺掉的個數 + 1，先固定左側，用單調棧維護一下該側比當前惡魔更小的第一個位置，右側同理
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n; int a[N],l[N],r[N]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; stack<int>s; for(int i=1;i<=n;i++)//左邊 { while(!s.empty()&&a[s.top()]>a[i]) s.pop(); if(!s.empty()) l[i]=l[s.top()]+1; else l[i]=0; s.push(i); } reverse(a+1,a+1+n);//反轉一次，開始做右邊 stack<int>s1; for(int i=1;i<=n;i++)//右邊 { while(!s1.empty()&&a[s1.top()]>a[i]) s1.pop(); if(!s1.empty()) r[i]=r[s1.top()]+1; else r[i]=0; s1.push(i); } for(int i=1;i<=n;i++) { cout<<l[i]+r[n-i+1]<<" "; } return 0; }
浙公網安備 33010602011771號