題目鏈接https://qduoj.com/contest/28/problems，密碼：qdu1230

E題：

思路：先進行排序，然后去暴力模擬就可以，但可能WA了幾次，導致此題沒解出來，有點可惜

代碼：

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream>using namespace std;int a[3005]; int b[3005]; int main() {int n,m;cin>>n>>m;for(int t=0;t<n;t++){scanf("%d",&a[t]);}for(int t=0;t<m;t++){scanf("%d",&b[t]);}sort(a,a+n);sort(b,b+m);int ma=0,mb=0;int maxna=0;int maxnb=0;for(int t=0;t<n;t++){for(int j=t;j<n;j++){if(ma==5){break;}if(a[j]-a[t]<=3){ma++;}else{ma=0;break;}maxna=max(maxna,ma);if(j==n-1){ma=0;}}}for(int t=0;t<m;t++){for(int j=t;j<m;j++){if(mb==5){break;}if(b[j]-b[t]<=3){mb++;}else{mb=0;break;}maxnb=max(maxnb,mb);if(j==m-1){mb=0;}}}cout<<maxna<<endl;cout<<maxnb<<endl;if(maxna<=maxnb){cout<<"liangliang\\O..o\\"<<endl;}else{cout<<"gg/o..O/"<<endl;}return 0; }

F題：

思路：首先對于題目的理解不能有錯誤，是進行任意輪的命令判斷是否能到達，不是就執行那一輪命令，那我們不妨設進行了k輪，然后把每次的坐標變換記錄，判斷在k輪是否能到達，k的值為（a-每一次的變化量）/一輪的變換量

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream>using namespace std;string str;struct node {int x,y; }pos[1005]; int main() {int a,b;while(cin>>a>>b>>str){int len=str.length();int x=0,y=0;int flag=0;if(x==a&&y==b){cout<<"Yes"<<endl;continue;}for(int t=0;t<len;t++){if(str[t]=='U')y++;if(str[t]=='D')y--;if(str[t]=='L')x--;if(str[t]=='R')x++;pos[t].x=x;pos[t].y=y;//cout<<pos[t].x<<" "<<pos[t].y<<endl;}int k;for(int t=0;t<len;t++){if(x){k=(a-pos[t].x)/x;}else if(y){k=(b-pos[t].y)/y;}if(k<0)k=0;if(a==k*x+pos[t].x&&b==k*y+pos[t].y){flag=1;break;}}if(flag){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;}

G題:G題看一下數據量就會明白暴力必然超時，那如何去解，我們可以進行分組枚舉所有結果，然后，去另一個查找有多少個相等的。我們可以有1，4和2，3兩種分法，我們看1，4也十分容易超時，故選用2，3，然后把所有的結果分別放在兩個數組里。我們查找的時候用二分進行查找，故要先進行排序，然后我們在較小的里面找較大的，復雜度稍低，然后我們不應該是找是否存在，而應該找存在多少個，所以一個是找左邊的下標，一個找右邊的下標，這樣一減就是個數。還有一個問題，就是開數組的大小，我一開始開的是1e6和1e4，但是會溢出，我就試著跑了下，一個在1e6+1e4左右，另一個沒跑，直接就多開大算了。

代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring>using namespace std;int a[10400000]; int b[14005];int k1,k2; // 查找第一個相等的元素int findFirstEqual(int a[], int key) {int left = 0;int right = k1 - 1;while (left <= right) {int mid = (left + right) / 2;if (a[mid] >= key) {right = mid - 1;}else {left = mid + 1;}}if (left < k1 && a[left] == key) {return left;}return -1; } // 查找最后一個相等的元素int findLastEqual(int a[], int key) {int left = 0;int right = k1- 1;while (left <= right) {int mid = (left + right) / 2;if (a[mid] <= key) {left = mid + 1;}else {right = mid - 1;}}if (right >= 0 && a[right] == key) {return right;}return -1; } int main() {int T;cin>>T;int x1,x2,x3,x4,x5;for(int t=0;t<T;t++){k1=0;k2=0;scanf("%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5);for(int j1=-50;j1<=50;j1++){for(int j2=-50;j2<=50;j2++){for(int j3=-50;j3<=50;j3++){if(j1==0||j2==0||j3==0){continue;}a[k1++]=x1*j1*j1*j1+x2*j2*j2*j2+x3*j3*j3*j3; }}} for(int j1=-50;j1<=50;j1++){for(int j2=-50;j2<=50;j2++){if(j1==0||j2==0){continue;}b[k2++]=x4*j1*j1*j1+x5*j2*j2*j2;}}sort(a,a+k1);int sum=0;for(int j=0;j<k2;j++){int l,r;if(findFirstEqual(a,-b[j])!=-1&&findLastEqual(a,-b[j])!=-1){l=findFirstEqual(a,-b[j]);r=findLastEqual(a,-b[j]);sum+=r-l+1;}}cout<<sum<<endl;}return 0; }

H題：是codeforce一道題的簡化版，我的想法是去找原來的串，找原來的串可以通過最長的兩個，和最短的兩個來確定，通過拼接共有八中情況，由于題目說是有唯一存在，所以必然存在一種是兩者相同的，這就是原來的串，找到原來的串，由于數據范圍比較小，就可以暴力去找前綴和后綴了，標記一下，最后根據標記來判斷前綴和后綴

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;string str[305]; string s1[305],s2[305]; int vis[305]={0}; int main() {int n;cin>>n;for(int t=0;t<2*n-2;t++){cin>>str[t];}string len1[2],len_n[2];int k1=0,k2=0;for(int t=0;t<2*n-2;t++){if(str[t].length()==1){len1[k1++]=str[t];}if(str[t].length()==n-1){len_n[k2++]=str[t];}}string stand;string sss1[4],sss2[4];//八種情況sss1[0]=len1[0]+len_n[0];sss1[1]=len_n[0]+len1[0];sss1[2]=len1[1]+len_n[0];sss1[3]=len_n[0]+len1[1];sss2[0]=len1[0]+len_n[1];sss2[1]=len_n[1]+len1[0];sss2[2]=len1[1]+len_n[1];sss2[3]=len_n[1]+len1[1];for(int t=0;t<4;t++){for(int j=0;j<4;j++){if(sss1[t]==sss2[j]){stand=sss1[t];}}}// cout<<stand<<endl;string s[205];s[0]=stand[0];for(int t=1;t<n-1;t++){s[t]=s[t-1]+stand[t]; }for(int t=0;t<2*n-2;t++){for(int j=0;j<n-1;j++){if(str[t]==s[j]){vis[t]=1;}}}for(int t=0;t<2*n-2;t++){if(vis[t]==1){cout<<"P";}else{cout<<"S";}}cout<<endl;return 0; }

I題：

思路：狼和草是可以共存的群體，羊和狼草都不能共存，我們就可以分為兩大陣營，羊，狼草，然后他們的存在狀態總的有兩種，一在岸上，一種是在船上，當小的等于d時，如果兩大陣營的大的超過船的兩倍載重，就會出現混的情況，就會混亂，故當小的等于d時，多的必須小于等于2*d，當小的小于d是時，可以不斷的去運多的，就不必考慮多的數量，都可以運

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream>using namespace std;int main() {int a,b,c,d;while(cin>>a>>b>>c>>d){int maxn=max(a+c,b);int minn=min(a+c,b);if(minn==d&&maxn<=2*d||(minn<d)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0; }

?

?

?

?

?

轉載于:https://www.cnblogs.com/Staceyacm/p/10781863.html

總結

以上是生活随笔為你收集整理的QDU第一届程序设计大赛——E到I题解法（非官方题解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。