1.标題： 購物單
小明剛剛找到工作，老闆人很好，隻是老闆夫人很愛購物。老闆忙的時候經常讓小明幫忙到商場代為購物。小明很厭煩，但又不好推辭。
這不，XX大促銷又來了！老闆夫人開出了長長的購物單，都是有打折優惠的。
小明也有個怪癖，不到萬不得已，從不刷卡，直接現金搞定。
現在小明很心煩，請你幫他計算一下，需要從取款機上取多少現金，才能搞定這次購物。
取款機隻能提供100元面額的紙币。小明想盡可能少取些現金，夠用就行了。
你的任務是計算出，小明最少需要取多少現金。
以下是讓人頭疼的購物單，為了保護隐私，物品名稱被隐藏了。
-----------------
**** 180.90 88折
**** 10.25 65折
**** 56.14 9折
**** 104.65 9折
**** 100.30 88折
**** 297.15 半價
**** 26.75 65折
**** 130.62 半價
**** 240.28 58折
**** 270.62 8折
**** 115.87 88折
**** 247.34 95折
**** 73.21 9折
**** 101.00 半價
**** 79.54 半價
**** 278.44 7折
**** 199.26 半價
**** 12.97 9折
**** 166.30 78折
**** 125.50 58折
**** 84.98 9折
**** 113.35 68折
**** 166.57 半價
**** 42.56 9折
**** 81.90 95折
**** 131.78 8折
**** 255.89 78折
**** 109.17 9折
**** 146.69 68折
**** 139.33 65折
**** 141.16 78折
**** 154.74 8折
**** 59.42 8折
**** 85.44 68折
**** 293.70 88折
**** 261.79 65折
**** 11.30 88折
**** 268.27 58折
**** 128.29 88折
**** 251.03 8折
**** 208.39 75折
**** 128.88 75折
**** 62.06 9折
**** 225.87 75折
**** 12.89 75折
**** 34.28 75折
**** 62.16 58折
**** 129.12 半價
**** 218.37 半價
**** 289.69 8折
--------------------
需要說明的是，88折指的是按标價的88%計算，而8折是按80%計算，餘者類推。
特别地，半價是按50%計算。
請送出小明要從取款機上提取的金額，機關是元。
答案是一個整數，類似4300的樣子，結尾必然是00，不要填寫任何多餘的内容。
解題思路：先用word查找替換掉沒有資訊，處理為有用的資訊，之後寫程式即可。
180.90 8.8
10.25 6.5
56.14 9
104.65 9
100.30 8.8
297.15 5
26.75 6.5
130.62 5
240.28 5.8
270.62 8
115.87 8.8
247.34 9.5
73.21 9
101.00 5
79.54 5
278.44 7
199.26 5
12.97 9
166.30 7.8
125.50 5.8
84.98 9
113.35 6.8
166.57 5
42.56 9
81.90 9.5
131.78 8
255.89 7.8
109.17 9
146.69 6.8
139.33 6.5
141.16 7.8
154.74 8
59.42 8
85.44 6.8
293.70 8.8
261.79 6.5
11.30 8.8
268.27 5.8
128.29 8.8
251.03 8
208.39 7.5
128.88 7.5
62.06 9
225.87 7.5
12.89 7.5
34.28 7.5
62.16 5.8
129.12 5
218.37 5
289.69 8 #include<cstring>
#include<cstdio>
int main()
{
double ans,a,b;
ans=0;
while(scanf("%lf%lf",&a,&b)!=EOF)
{
ans+=a*b*0.1;
printf("%lf",ans);
}
return 0;
} 2标題：等差素數列
2,3,5,7,11,13,....是素數序列。
類似：7,37,67,97,127,157 這樣完全由素數組成的等差數列，叫等差素數數列。
上邊的數列公差為30，長度為6。
2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數等差數列。
這是數論領域一項驚人的成果！
有這一理論為基礎，請你借助手中的計算機，滿懷信心地搜尋：
長度為10的等差素數列，其公差最小值是多少？
注意：需要送出的是一個整數，不要填寫任何多餘的内容和說明文字。
解題思路：直接暴力枚舉即可，跑了兩分鐘......電腦風扇呼呼地轉。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int isprime(int x)
{
int i;
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
return 0;
}
}
return 1;
}
int main()
{
int i,j,k;
int flag;
for(k=30;k<=10000;k++)///對公差進行暴力，最小公差就是樣例所給的30
{
flag=0;
for(i=2;i<=1000000;i++)
{
if(isprime(i))///枚舉所有的素數
{
for(j=1;j<10;j++)//找該素數之後公差為k的十個數是否也是素數
{
if(!isprime(i+j*k))
{
break;
}
}
if(j==10)
{
flag=1;
break;
}
}
}
if(flag)
{
break;
}
}
printf("%d\n",k);
return 0;
} 4标題：方格分割
6x6的方格，沿着格子的邊線剪開成兩部分。
要求這兩部分的形狀完全相同。
如圖：p1.png, p2.png, p3.png 就是可行的分割法。
試計算：
包括這3種分法在内，一共有多少種不同的分割方法。
注意：旋轉對稱的屬于同一種分割法。
請送出該整數，不要填寫任何多餘的内容或說明文字。
解題思路：DFS搜尋，這裡搜尋的是一條分割線。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int vis[7][7];
int ans=0;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int DFS(int x,int y)
{
int i,x1,y1;
if(x==0||y==0||x==6||y==6)///搜尋到邊界，說明形成了分割線
{
ans++;
return 0;
}
for(i=0;i<4;i++)
{
x1=x+dir[i][0];
y1=y+dir[i][1];
if(x1<0||x1>6||y1<0||y1>6)
{
continue;
}
if(!vis[x1][y1])
{
vis[x1][y1]=1;
vis[6-x1][6-y1]=1;
DFS(x1,y1);
vis[x1][y1]=0;///回溯撤回标記
vis[6-x1][6-y1]=0;
}
}
}
int main()
{
memset(vis,0,sizeof(vis));
vis[3][3]=1;
DFS(3,3);
printf("%d\n",ans/4);
return 0;
} 5标題：取數位
求1個整數的第k位數字有很多種方法。
以下的方法就是一種。
// 求x用10進制表示時的數位長度
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
// 取x的第k位數字
int f(int x, int k){
if(len(x)-k==0) return x%10;
return _____________________; //填空
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
對于題目中的測試資料，應該列印5。
請仔細分析源碼，并補充劃線部分所缺少的代碼。
注意：隻送出缺失的代碼，不要填寫任何已有内容或說明性的文字。
解題思路：這道題一看就是要讓我們來補充遞歸調用的代碼，這個題分析f函數，如果x用10進制表示時的數位長度和所求的一樣長，就傳回個位數，如果不一樣長，那麼應該截取到一樣長，也就是x/10。同時len()函數也是遞歸實作功能，這也提示了我們。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
// 求x用10進制表示時的數位長度
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
// 取x的第k位數字
int f(int x, int k){
if(len(x)-k==0) return x%10;///取最後一位
return f(x/10,k); //填空
}
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
} 6标題：最大公共子串
最大公共子串長度問題就是：
求兩個串的所有子串中能夠比對上的最大長度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最長的公共子串是"abcd",是以最大公共子串長度為4。
下面的程式是采用矩陣法進行求解的，這對串的規模不大的情況還是比較有效的解法。
請分析該解法的思路，并補全劃線部分缺失的代碼。
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
printf("%d\n", f("abcdkkk", "baabcdadabc"));
解題思路：最長公共子序列的模闆題
9标題： 分巧克力
兒童節那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。
小明一共有N塊巧克力，其中第i塊是Hi x Wi的方格組成的長方形。
為了公平起見，小明需要從這 N 塊巧克力中切出K塊巧克力分給小朋友們。切出的巧克力需要滿足：
1. 形狀是正方形，邊長是整數
2. 大小相同
例如一塊6x5的巧克力可以切出6塊2x2的巧克力或者2塊3x3的巧克力。
當然小朋友們都希望得到的巧克力盡可能大，你能幫小Hi計算出最大的邊長是多少麼？
輸入
第一行包含兩個整數N和K。(1 <= N, K <= 100000)
以下N行每行包含兩個整數Hi和Wi。(1 <= Hi, Wi <= 100000)
輸入保證每位小朋友至少能獲得一塊1x1的巧克力。
輸出
輸出切出的正方形巧克力最大可能的邊長。
樣例輸入：
2 10
6 5
5 6
樣例輸出：
2
資源約定：
峰值記憶體消耗（含虛拟機） < 256M
CPU消耗 < 1000ms
解題思路：我們知道，在1~100000之間的任何一個數x，将各個大塊的巧克力按照邊長為x的正方形進行切割，如果切割的塊數大于等于K，就能夠實作每個小朋友都有一份的目标。我們要找的是最大的那個x，而想要找到這個x我們不能暴力，那就需要對這個區間采用二分法來查找。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
int n,k;
struct cho
{
int h;
int w;
}c[N];
int judge(int len)
{
int sum=0;
int i;
for(i=0;i<len;i++)
{
sum+=(c[i].h/len)*(c[i].w/len);///等分切割蛋糕
if(sum>=k)///能夠分割出來
{
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
int low=1;
int high=100000;
int mid;
int i;
for(i=0;i<n;i++)
{
scanf("%d%d",&c[i].h,&c[i].w);
}
while(low<high-1)///二分查找最大的
{
mid=(low+high)/2;
if(judge(mid))
{
low=mid;///還可以更大
}
else
{
high=mid;///太大了，不符合目标
}
}
printf("%d\n",mid-1);
return 0;
} 10标題： k倍區間
給定一個長度為N的數列，A1, A2, ... AN，如果其中一段連續的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍數，我們就稱這個區間[i, j]是K倍區間。
你能求出數列中總共有多少個K倍區間嗎？
-----
以下N行每行包含一個整數Ai。(1 <= Ai <= 100000)
輸出一個整數，代表K倍區間的數目。
例如，
輸入：
5 2
1
2
3
4
5
程式應該輸出：
6
CPU消耗 < 2000ms
解題思路：這道題從題意中看出應該使用字首和但一般的兩重循環來限制區間的方法必然會造成時間超限，這裡因為有取模運算，實際上是有規律的。計算字首和然後取餘k, 如果前i項和取餘k與前j項和取餘k後相同，那麼i到j這個區間和為k的倍數，因為餘數相等，是以這個一定成立（sum[r] - sum[l-1]）% k == 0，是以這個區間是符合條件的。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long int
using namespace std;
ll a[100010];
ll cnt[100010];///字首和取餘後i的個數
ll sum[100010];///存字首和
int main()
{ ll ans=0;
int n,k,i;
memset(sum,0,sizeof(sum));
memset(cnt,0,sizeof(cnt));
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];//構成字首和
}
for(i=1;i<=n;i++)
{
cnt[sum[i]%k]++;
}
for(i=0;i<k;i++)
{
if(cnt[i])
{
ans+=(cnt[i]*(cnt[i]-1))/2; ///排列組合中的C(n,2)
}
}
printf("%lld",ans+cnt[0]);
return 0;
} 作者：王陸