• T1
  • 題目
  • 思路
• T2
  • 題目
  • 思路
• T3
  • 題目
  • 思路
• T4
  • 題目
  • 思路
• T5
  • 題目
  • 思路
• 總結

---

https://cn.vjudge.net/contest/183263#overview

T1

題目

給出一串數字，把它們截成n段，如果有一種截法能保證n是奇數，每一段里都有奇數個數并且每一段的頭尾均為奇數，則輸出“Yes”,否則輸出“No”.

思路

這是一道非常地道的水題，就算是像我這樣的蒟蒻18分鐘也能AC。思考如下：分成奇數份，每份有奇數個，總數必定是奇數。如果n是偶數可以直接輸出“No”。那么當n%2==1的時候，第一個數肯定得是奇數，否則不管怎么截，一定是偶數作為第一段的第一個。同理最后一個數也得是奇數。在這樣的情況下，你會發現這串數字不用截就已經符合本題的要求，1（奇數）段，奇數個，首尾奇數，直接輸出“Yes”就可以了。故代碼如下：沒有縮進，請見諒。

#include<bits/stdc++.h> using namespace std; int a[101]; int main() { int n,i; cin>>n; for (i=1;i<=n;i++) cin>>a[i]; if (n%2==0||a[1]%2==0||a[n]%2==0) cout<<"No"; else cout<<"Yes"; }

就是這樣。

T2

題目

在平面直角坐標系中有很多點（i,a[i]）,其中i=1,2,3,4,5,6,7……,a[i]由你輸入。在坐標系中若能找到兩條平行直線（注意：必須是兩條！！！），使所有的點都在直線上，則輸出“Yes”,否則輸出“No”.(注意：如果所有點都在一條直線上，輸出“No”.)

思路

必須要兩條直線，那么在1,2,3三個點中，必有兩個點的連線是符合條件的，否則就不止兩條直線了。枚舉三個解析式，通過一個布爾數組存儲一個點是否已經被直線穿過了，然后用O（n）的四次循環爆搜，最后輸出。這里請無視我布爾數組的名字，上午做題想了3個多小時沒想出這道題，又訂正了一下午，搞來搞去直到接近18：00才把這道題A了，實在不爽，原諒我吧。具體請看代碼。我代碼風格比較毒，大家可以格式化后觀看。

#include<bits/stdc++.h> using namespace std; double a[1001];bool fucked[1001];//用實數定義，操作簡便易行 int main() { int n,i,j,x,y;double k,b,b1; cin>>n; for (i=1;i<=n;i++) scanf("%lf",&a[i]); x=1;y=2; for (i=1;i<=3;i++){if (a[x]==a[y]) {k=0;b=a[x];}//具體討論k=0，避免0作為分母else //計算函數解析式，直接套公式{k=(a[y]-a[x])/(y-x);b=(a[x]*y-a[y]*x)/(y-x);}for (j=1;j<=n;j++) if (k*j+b==a[j]) fucked[j]=1;//判斷第一條直線穿過哪些點for (j=1;j<=n;j++) if (fucked[j]==0) break;//找到第一個沒有被穿過的點if (j>n) {cout<<"No";return 0;}//如果j>n，說明所有點在一條直線上，輸出“No”b1=a[j]-k*j;//k相同，通過第一個沒有被穿過的點的坐標找出第二條直線的bfor (j=1;j<=n;j++) if (k*j+b1==a[j]) fucked[j]=1;//第二條直線for (j=1;j<=n;j++) if (fucked[j]==0) break;//繼續找沒有被穿過的點。if (j>n) {cout<<"Yes";return 0;}//這一次說明兩條直線穿過了所有點，符合題目條件，可能與上面重復了，不知道大佬們能如何優化。for (j=1;j<=n;j++) fucked[j]=0;//初始化if (i==1) y++;//第一次1，2，第二次1，3；第三次2，3else if (i==2) x++; } cout<<"No"; }

T3

題目

本題是SPJ。對于一個字符串來說，一個合并所需花費是這么算的：首先把字符串的每個字符拆開，然后進行合并。對于每一次合并，將t合并到s時，對于t里的每一個字符，計算它在s里出現了多少次，把這些數字統統相加，最終的和就是所求結果。本題中輸入合并的最小花費，讓你輸出符合該條件的一個字符串。具體看樣例輸入輸出的下面樣例解釋。

思路

這題是spj,當然怎么簡單怎么來了。首先我們可以發現，在合并時不同種類字符不互相影響，所有的花費對于每個字母來說都是獨立的，并且對于相同數量的同種字母來說，不管怎么合并，所需的花費都是一樣的，并且合并的花費S和字母數量n滿足S=（n*n-n）/2;
因此有如下代碼。我先找很多a，算出它們合并的花費，用一個過程找出最多能合并多少a，然后減掉合并a所用的花費，用剩下的來算b，c……一路推上去，直到n=0為止。

#include<bits/stdc++.h> using namespace std; void digui(int n,char c) { int i=2,j; if (n==0) return; while ((i*i-i)/2<=n) i++; for (j=1;j<=i-1;j++) printf("%c",c); i--; digui(n-(i*i-i)/2,c+1); } int main() { int n; cin>>n; digui(n,'a'); }

這個代碼提交上去WA了。為什么WA？我在這里強調一點：特判！特判！特判！重要的事情一定要說三遍！當時這個問題因為輸入n=0時沒有特判坑了我三個小時，最后我還是沒有A這題。我一直搞到晚上有人提醒我沒有特判0。我加上了0的特判，并且優化了代碼：

#include<bits/stdc++.h> using namespace std; void digui(int n,char c) {int i=sqrt(n),j;//這里i=sqrt(n)是一個優化，if (n==0) return;while ((i*i-i)/2<=n) i++;//在這句當中這里i只需要加一點就能停止循環for (j=1; j<=i-1; j++) printf("%c",c);i--;digui(n-(i*i-i)/2,c+1); } int main() {int n;cin>>n;if (n==0) cout<<"a";//不要忘記特判！digui(n,'a'); }

然后就A了。這題也坑了我一天。

T4

題目

看到這個題目我直接被搞暈了，以為這是我并沒有學過的向量。這只是一道字符串找規律題。輸入n，輸出2^n*2^n的正方形方陣，每一個元素都是“+”或者“*”，+代表+1，*代表-1。對于每兩行來講，它們當中同位置不同字符的數量剛好等于該行字符數的一半。（我往簡單了講）只要輸出符合條件的一個方陣即可。

思路

最終我還是找到了規律，對于每一個正方形，分成四個角遞歸，左上，右上，左下的元素完全相同，右下的所有元素均與其他三個方向相反。具體請看代碼。這個代碼輸入9的時候要18秒才能出結果，我怕超時，但是還是提交了，沒想到A了。我用一個bool類型的變量控制每一塊的字符是相同還是相反。

#include<bits/stdc++.h> using namespace std; char c[513][513]; void search(int x1,int y1,int x2,int y2,bool b)//遞歸左上角坐標，右下角坐標，判定正負變量 { if (x1>=x2||y1>=y2) return; if (x2-x1==1&&y2-y1==1) {if (b==1) {c[x1][y1]='+';c[x1][y2]='+';c[x2][y1]='+';c[x2][y2]='*';}else {c[x1][y1]='*';c[x1][y2]='*';c[x2][y1]='*';c[x2][y2]='+';}} else //當時提交之前下面這一塊+1錯了，輸入2以上的數字就會崩掉，后來改了一下A了{search(x1,y1,(x1+x2)/2,(y1+y2)/2,b);//遞歸左上角search((x1+x2)/2+1,y1,x2,(y1+y2)/2,b);//遞歸左下角search(x1,(y1+y2)/2+1,(x1+x2)/2,y2,b);//遞歸右上角search((x1+x2)/2+1,(y1+y2)/2+1,x2,y2,!b);//遞歸右下角} } int main() { int n,i,j; cin>>n; if (n==0) printf("+"); else{search(1,1,1<<n,1<<n,true);for (i=1;i<=1<<n;i++){for (j=1;j<=1<<n;j++) printf("%c",c[i][j]);printf("\n");}} }

T5

題目

輸入一串數據,令f(n)=在這串數據中能被n整除的數據的個數(n是質數),以下m行每行兩個數字,詢問從l至r所有質數的f函數之和.

思路

我寫了一個O（n^2）的代碼，因為嚇人的數據范圍在第18個點T了。具體就是算出f[i]之后用一個sum數組來儲存i之前的數字的函數返回值的和，詢問時只要求sum[r[i]]-sum[l[i]]即可。還有求質數的時候一定要用篩法!否則時間復雜度太高鐵定會T！代碼如下,今天搞了一下午用最大的數據直接暴力搞定了.可以定義一個常數等于10000005.

#include<bits/stdc++.h> using namespace std; int a[1000010],f[10000010]={0},l,r,tong[10000010]={0};bool p[10000010]; int main() { int n,m,i,j,da=-100000; cin>>n; for (i=1;i<=n;i++){scanf("%d",&a[i]);tong[a[i]]++;//利用桶來做這題} p[1]=1; for (i=2;i<=10000005;i++) if (p[i]==0){for (j=i;j<=10000005;j+=i){p[j]=1;f[i]+=tong[j];//j一定是i的倍數,用這樣的方法不需要再從1到n循環一遍,就不會超時了} } for (i=2;i<=10000005;i++) f[i]+=f[i-1];//在計算詢問的最終結果的時候也不用一遍一遍循環 cin>>m; for (i=1;i<=m;i++){scanf("%d%d",&l,&r);if (l!=10000005) l=min(l,10000004);r=min(r,10000004);printf("%d\n",f[r]-f[l-1]);//f這個數組表示的是數據i及之前的所有數據的函數和} }

總結

總體來說這5題還是比較好懂的，至少我全讀懂了，會不會做是另外一回事，反正我能訂正問題不大。我在現場3小時30分鐘之內A了第一題和第四題，依然做得非常糟糕。總之還好啦.

總結

以上是生活随笔為你收集整理的奋斗群群赛2总结与心得的全部內容，希望文章能夠幫你解決所遇到的問題。

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