勵(lì)志用盡量少的代碼做高效表達(dá)

---

題目（提交）鏈接——>UVa-10940

---

問題分析

本題的時(shí)間要求是3s，但極限數(shù)據(jù)量為50W*50W，一般來說，3s的時(shí)間只能支持不到三千萬次的運(yùn)算，也就是說，即使以O(shè)(n)為復(fù)雜度做運(yùn)算，也無法滿足題意。
分析到這里，我們很容易想到本題的思路是：找出規(guī)律，推公式或預(yù)處理。

---

預(yù)處理：
首先使用基本方法打印出前100個(gè)數(shù)字的結(jié)果： 1 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72
規(guī)律一下就出來了。 直接用預(yù)處理的方式暴力存入數(shù)組，完成AC。

推公式：
寫了幾個(gè)發(fā)現(xiàn)規(guī)律f(n)=f(2^m+k)=2*k。

---

---

預(yù)處理代碼：

#include<bits/stdc++.h> using namespace std; int a[500005]; int main() {a[1]=1; //預(yù)處理打表，結(jié)果放入a數(shù)組。預(yù)先存入1。 int x = 0, i = 2; //i為a數(shù)組的下角標(biāo)，從2開始遍歷 int flag = 1; while(flag) {int x1 = pow(2, x++); //x1是循環(huán)的次數(shù)，分別等于1,2,4,8.... int num = 2; //num將賦值給a數(shù)組，分別等于2,4,6,8... for(int j = 0; j < x1; j++, num+=2) {a[i++] = num;if(i >= 500001) { flag=0; break; } //break退出for循環(huán)， flag=0退出while循環(huán) }}//以下為輸入輸出。 int n; while(cin>>n && n) {cout << a[n] << endl;} return 0;}

---

推公式代碼：

#include <bits/stdc++.h> int main(){int n; while (scanf("%d",&n) != EOF && n){if (n == 1){ printf("1\n"); continue; }int cnt = 1;while (cnt < n) cnt <<= 1;int ans = (n-cnt/2)*2;printf("%d\n",ans);} return 0;}

---

總結(jié)：

1、很經(jīng)典的技巧題，在數(shù)據(jù)量極大時(shí)，一定采用預(yù)處理(打表)或找規(guī)律的方式解題。

總結(jié)

以上是生活随笔為你收集整理的10行代码AC——UVa 10940(Throwing cards away II 数学规律+约瑟夫环)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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