藍橋杯2015題解（c++版）
-
一個串的子串是指該串的一個連續的局部。如果不要求連續，則可稱為它的子序列。
比如對串： “abcdefg” 而言，“ab”,“abd”,“bdef” 等都是它的子序列。
特别地，一個串本身，以及空串也是它的子序列。
對兩個串而言，可以有許多的共同的子序列，我們關心的是：它們所共同擁有的長度最大的子序列是多長。以下代碼實作了這個問題的求解。請填寫劃線部分缺失的代碼。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; inline max(int a, int b) { return a>b?a:b; } int f(char* x, char* y) { if(strlen(x)==0) return 0; if(strlen(y)==0) return 0; if(*x == *y) return f(x+1, y+1) + 1; return max(f(x+1,y),f(x,y+1)); } int main(){ // Q1 printf("%d\n", f("ac","abcd")); //2 printf("%d\n", f("acebbcde1133","xya33bc11de")); //5 return 0; } -
曆史上有許多計算圓周率pai的公式，其中，格雷戈裡和萊布尼茨發現了下面的公式：
pai = 4*(1-1/3+1/5-1/7 …)
這個公式簡單而優美，但美中不足，它收斂的太慢了。
如果我們四舍五入保留它的兩位小數,那麼：
累積了1項和是：4.00
累積了2項和是：2.67
累積了3項和是：3.47
。。。
請你寫出它累積了100項的和是多少（四舍五入到小數後兩位）。
注意：隻填寫該小數本身，不要填寫任何多餘的說明或解釋文字。
// 頭檔案參考上面
int main(){
double sum = 0.0;
int flag = 1;
for(int i=1;i<=100;i++){
sum += (1.0/i)*flag;
flag *= -1;
}
printf("%.2f",4*sum);
return 0;
}
-
如果x的x次幂結果為10（參見【圖1.png】），你能計算出x的近似值嗎？
顯然，這個值是介于2和3之間的一個數字。
請把x的值計算到小數後6位（四舍五入），并填寫這個小數值。
注意：隻填寫一個小數，不要寫任何多餘的符号或說明。
double ans = 2.0; while(ans < 3.0){ ans += 0.0000001; if(fabs(pow(ans,ans) - 10) < 0.00001){ printf("%.8f",ans); break; } } -
今有7對數字：兩個1，兩個2，兩個3，…兩個7，把它們排成一行。
要求，兩個1間有1個其它數字，兩個2間有2個其它數字，以此類推，兩個7之間有7個其它數字。如下就是一個符合要求的排列：
17126425374635
當然，如果把它倒過來，也是符合要求的。
請你找出另一種符合要求的排列法，并且這個排列法是以74開頭的。
//Q4 此題最優做法是 草稿紙來排列
-
勾股定理，西方稱為畢達哥拉斯定理，它所對應的三角形現在稱為：直角三角形。
已知直角三角形的斜邊是某個整數，并且要求另外兩條邊也必須是整數。
求滿足這個條件的不同直角三角形的個數。
【資料格式】
輸入一個整數 n (0<n<10000000) 表示直角三角形斜邊的長度。
要求輸出一個整數，表示滿足條件的直角三角形個數。
例如，輸入：
5
程式應該輸出：
1
再例如，輸入：
100
程式應該輸出：
2
再例如，輸入：
3
程式應該輸出：
long long sum = 0;//累計個數 long long n; cin >> n; while(1){ for(long long i=1;i<n;i++) { long long j=sqrt(n*n-i*i); if(j*j==n*n-i*i) sum++; } break; } printf("%lld\n",sum/2);-
你一定聽說過“數獨”遊戲。
如【圖1.png】，玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，并滿足每一行、每一列、每一個同色九宮内的數字均含1-9，不重複。
數獨的答案都是唯一的，是以，多個解也稱為無解。
本圖的數字據說是芬蘭數學家花了3個月的時間設計出來的較難的題目。但對會使用計算機程式設計的你來說，恐怕易如反掌了。
本題的要求就是輸入數獨題目，程式輸出數獨的唯一解。我們保證所有已知資料的格式都是合法的，并且題目有唯一的解。
格式要求：
輸入9行，每行9個數字，0代表未知，其它數字為已知。
輸出9行，每行9個數字表示數獨的解。
-
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int a[10][10] = {0};
//檢查行列是否合格
bool check_col_row(int x,int y,int n){
for(int i=1;i<=9;i++){
if(a[x][i] == n || a[i][y] == n){
return false;
}
}
return true;
}
//檢查同色九宮格
int check_range(int x){
if(x >= 1 && x <= 3){
return 1;
}
else if(x >= 4 && x <= 6){
return 4;
}
else{
return 7;
}
}
bool check_block(int x,int y,int n){
int r = check_range(x);
int c = check_range(y);
for(int i=r;i<=r+2;i++){
for(int j=c;j<=c;j++){
if(a[i][j] == n){
return false;
}
}
}
return true;
}
void dfs(int x,int y)
{
if(x>9){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
printf("%d",a[i][j]);
}
printf("\n");
}
exit(0);
}
if(a[x][y] == 0){
//此處沒有填數字
for(int i=1;i<=9;i++){
if(check_block(x,y,i) && check_col_row(x,y,i)){
a[x][y] = i;
dfs(x+(y+1)/10,(y+1)%10);
}
}
a[x][y] = 0;
}else{
dfs(x+(y+1)/10,(y+1)%10);
}
}
int main(){
//Q6 DFS+check
string s;
for(int i = 1;i<=9;i++){
cin >> s;
for(int j=1;j<=9;j++){
char ss = s.at(j-1); //将j-1的字元化為整數
a[i][j] = ss-'0';
}
}
dfs(1,1);
return 0;
}
-
G将軍有一支訓練有素的軍隊，這個軍隊除開G将軍外，每名士兵都有一個直接上級（可能是其他士兵，也可能是G将軍）。現在G将軍将接受一個特别的任務，需要派遣一部分士兵（至少一個）組成一個敢死隊，為了增加敢死隊隊員的獨立性，要求如果一名士兵在敢死隊中，他的直接上級不能在敢死隊中。
請問，G将軍有多少種派出敢死隊的方法。注意，G将軍也可以作為一個士兵進入敢死隊。
輸入格式
輸入的第一行包含一個整數n，表示包括G将軍在内的軍隊的人數。軍隊的士兵從1至n編号，G将軍編号為1。
接下來n-1個數，分别表示編号為2, 3, …, n的士兵的直接上級編号，編号i的士兵的直接上級的編号小于i。
輸出格式
輸出一個整數，表示派出敢死隊的方案數。由于數目可能很大，你隻需要輸出這個數除10007的餘數即可。
樣例輸入1
3
1 1
樣例輸出1
4
樣例說明
這四種方式分别是：
- 選1；
- 選2；
- 選3；
-
選2, 3。
樣例輸入2
7
1 1 2 2 3 3
樣例輸出2
40
#include <iostream> #include <cstdio> #include <cmath> #include <iomanip> #include <string.h> #include <vector> using namespace std; typedef long long ll; const int maxn=1e5+7; const int mod=1e9+7; const double p1=acos(-1); int dp[maxn][2]; vector<int> v[maxn]; int n; void dp_rule(int root){ for(int i=0;i<v[root].size();i++){ dp_rule(v[root][i]); dp[root][1]*=dp[v[root][i]][0]; dp[root][0]*=(dp[v[root][i]][0]+dp[v[root][i]][1]); dp[root][1]%=mod; dp[root][0]%=mod; } } int main(){ fill((int *)dp,(int *)dp+maxn*2,1); //先全部初始化為1 scanf("%d",&n); int x; for(int i=2;i<=n;i++){ scanf("%d",&x); v[x].push_back(i); } dp_rule(1); cout<<(dp[1][0]+dp[1][1]-1)%mod<<endl; return 0; }
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)