當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2019中山大学程序设计竞赛

發(fā)布時間：2024/10/5 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 2019中山大学程序设计竞赛小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

Problem A?

題意：有一個長度為n的隨機排列以及m個min、max操作。問最后一個操作的結(jié)果的期望 * n! 的結(jié)果。

題解：

枚舉k，考慮計算結(jié)果 >= k 的排列有幾個。

此時數(shù)字本質(zhì)上只有兩類，>= k 的以及 < k的?？梢?/span>2^n的枚舉每個位置的數(shù)是>=k還是<k，然后對于每一個狀態(tài)模擬一遍所有m個操作，如果結(jié)果為1，則說明該狀態(tài)是可行的。

接下來考慮每種狀態(tài)對應(yīng)幾個排列，若該狀態(tài)中有x個1，則對應(yīng)的排列個數(shù)為 x! * (n-x)! 個。現(xiàn)在已經(jīng)計算出結(jié)果 >= k 的排列有 f[k] 個，那么答案也就是所有 f[k] 的和。整體復(fù)雜度為 O((2^n) * m)

Problem B?Triangle

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=846

題意：給你?根棍子，問是否有其中三根能組成三角形

題解：斐波那契數(shù)列

定理：給定一個非空的由正整數(shù)構(gòu)成的多重集合?A，若?A中元素不能組成三角形三邊，則?A中的最大元素max?≥??，max?A≥F_|A| ，其中??是F_|A| ?是斐波那契數(shù)列的第?n項

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=5000000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp,sum; int a[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}if(n<3){cout<<"NO"<<"\n";continue;}if(n>60){cout<<"YES"<<"\n";continue;}sort(a+1,a+n+1);flag=0;for(int i=1;i<n-1;i++){if(a[i]-a[i+2]+a[i+1]>0){cout<<"YES"<<"\n";flag=1;break;}}if(!flag)cout<<"NO"<<"\n";}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem C?

題意：濤濤有一個n行m列的卡牌陣，每個位置是0或1，0代表卡牌背面朝上，1代表卡牌正面朝下，濤濤每次可以選擇一個小矩陣，把這個矩陣內(nèi)所有卡牌翻轉(zhuǎn)，問最后可以得到多少本質(zhì)不同的卡牌陣。

題解：

先計算出取一個矩形的方案是one=

再計算出取兩個不同矩形的方案是two=?

再減去重復(fù)的方案

考慮4種會重復(fù)的形狀，算出相應(yīng)系數(shù)

Problem D?Monitor

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=846

題意：在一個面積不超過n*m的矩形上，有p個矩形A，問之后的q個矩形B能否被之前的A全部覆蓋（每個B的點都在至少一個A中）

題解：樹狀數(shù)組（區(qū)間更新+區(qū)間查詢）

由于n*m,p,q的范圍過大，于是考慮O(n*m+p+q)的做法。

對于A類矩形(x1,y1,x2,y2)，我們只需要在(x1,y1),(x2+1,y2+1)處+1，在（x1,y2+1）(x2+1,y1)處-1

之后對整個面積求一個前綴和。則大于0的地方就是被A類矩形覆蓋的點。

把值大于0的地方變成1，再一次求一次前綴和，處理好后即可在O(1)的時間算出一個矩形內(nèi)被覆蓋的點的數(shù)量。

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=20000000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp; int x,y,x2,y2; int lowbit(int x){return x&(-x); } int a[N]; void updata(int x,int y,int k){if(x>n||y>m)return;a[(x-1)*m+y]+=k; } ll query(int x,int y){if(x==0||y==0)return 0;return a[(x-1)*m+y]; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~scanf("%d%d",&n,&m)){memset(a,0,sizeof(a));scanf("%d",&k);while(k--){scanf("%d%d%d%d",&x,&y,&x2,&y2);updata(x2+1,y2+1,1);updata(x,y,1);updata(x,y2+1,-1);updata(x2+1,y,-1);}for(int i = 1 ; i <=n ; i++)for(int j = 1 ; j <=m ; j++)a[(i-1)*m+j]=query(i,j-1)+query(i-1,j)-query(i-1,j-1)+a[(i-1)*m+j];for(int i = 1 ; i <=n ; i++)for(int j = 1 ; j <=m ; j++)a[(i-1)*m+j]=a[(i-1)*m+j]!=0;for(int i = 1 ; i <=n ; i++)for(int j = 1 ; j <=m ; j++)a[(i-1)*m+j]=query(i,j-1)+query(i-1,j)-query(i-1,j-1)+a[(i-1)*m+j];scanf("%d",&q);while(q--){scanf("%d%d%d%d",&x,&y,&x2,&y2);int res=query(x-1,y-1)-query(x-1,y2)-query(x2,y-1)+query(x2,y2);//cout<<res<<endl;printf("%s\n",(res==(x2-x+1)*(y2-y+1))?"YES":"NO");}}//cout << "Hello world!" << endl;return 0; }

Problem E?Coding Problem

http://acm.hdu.edu.cn/contests/contest_showproblem.php?cid=846&pid=1005

題意：將字符串每個字符ASCII的二進制翻轉(zhuǎn)碼組成的字符串以每6個一組輸出。

題解：模擬

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=2400000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; char str[N]; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){//scanf("%d",&n);cin>>str;int len=strlen(str);cnt=0;temp=0;for(int i=0;i<len;i++){for(int j=0;j<8;j++){sum=(str[i]&(1<<j))>0;temp=temp*2+sum;if((i*8+j+1)%6==0){printf("%d%c",temp,' ');temp=0;}}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem F?

題意：給一棵邊帶權(quán)的樹，定義兩個點之間的距離為路徑上邊權(quán)的 max – min。一開始樹上有一些黑點，其余的為白點，對于每個白點計算出距離它最遠的黑點到它的距離 dis[u]，現(xiàn)在要求再添加一個黑點，使得dis數(shù)組的最小值最大。

題解：首先需要計算出距離每個白點最遠的黑點到它的距離max_dis。將所有點按照這個距離從小到大排序得到一個有序序列p[1..n]。接下來枚舉一個將要變成黑點的白點，并且從小到大枚舉答案Ans，并加入所有max_dis <= Ans的白點，查詢當前點到所有已經(jīng)加入白點的最小距離，若該值大于 Ans 則說明Ans可以擴大。由于Ans 只會從1到n擴大一次，所以整體上的復(fù)雜度是線性的。

求最大距離和最小距離是經(jīng)典問題，可以直接利用點分治解決。

復(fù)雜度：Ο(n log^2?n )

Problem G?

題意：求至多對給定串修改一個字符情況下所有的中點不重復(fù)的對稱的回文的子串的平方的和最大是多少。

題解：計算出把第i個字符變成字符j的收益contr[i][j]。以及把第i個字符更改導(dǎo)致的損失del[i]。

字符串是對稱的，每次倍增考慮f[i][j]，即第j字符是否是長為2? – 1特殊串的中心。如果是則f[i][j]為1，不是為0.

現(xiàn)在分類討論這個以j為中心，長度為2^i-1的字符串。

定義左串是其左邊(2^(i-1)-1)的串，右串同理。

Problem H?Clumsy Keke

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=846

題意：給你一個立方塊堆的三視圖，求出它的體積(若有多個滿足，則求最大的那個)。

題解：枚舉+思維

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v,h; int ans,cnt,flag,temp,sum; int a[N][N],b[N][N],c[N][N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d%d%d",&n,&m,&h)){ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=m;i++)for(int j=1;j<=h;j++)scanf("%d",&b[i][j]);for(int i=1;i<=h;i++)for(int j=1;j<=n;j++)scanf("%d",&c[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=1;k<=h;k++)if(a[i][j]&&b[j][k]&&c[k][i])ans++;cout<<ans<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem I?Enlarge it

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=846

題意：輸入一個字符矩陣，把它放大k倍輸出。u題意：輸入一個字符矩陣，把它放大k倍輸出。

題解：模擬

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; char ditu[106][106]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(cin>>n>>m>>k){for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>ditu[i][j];for(int i=0;i<n*k;i++){for(int j=0;j<m;j++)for(int t=0;t<k;t++)cout<<ditu[i/k][j];cout<<endl;}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem J?

題意：給你一個零件，它是由兩個無限長的凸直棱柱A和B相交部分組成的，A的母線與B的母線垂直，求該零件的體積

Problem K?

題意：有n個人，開m次派對，每次派對每對人會相互認識對方。對于每一次派對，我們要求出新認識的pair的數(shù)量。

題解：只允許O(n log(n)+mlog(n))通過

因為是算數(shù)量，所以可以把相互認識當作有向邊，每個邊當作從小連向大的有向邊即可

對于每一個i，我們只用記錄它在每次派對數(shù)量的數(shù)量認識的最大值f[i]即可。因為一旦i認識了f[i]，那么說明它認識了i到f[i]的全部人。

用線段樹來維護一段區(qū)間上f值的max和sum即可

我們可以在線段樹上二分來用logn的效率來計算不需要再連邊的人。

總結(jié)

以上是生活随笔為你收集整理的2019中山大学程序设计竞赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Sonya and Informatic
下一篇： The Preliminary Cont