目录
1.购物单
2.等差素数列
3.承压计算
4.方格分割
5.日期问题
6.包子凑数
7.全球变暖
8.k倍区间
1.购物单
题目解析：就是将折扣字符串转化为数字，进行相加求和。
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
double sum = 0.0;
while(1)
{
double price;
string ignore;
string discount;
double dis = 0.0;
cin >> price >> ignore >> discount;
if(ignore == "0") break;
if(discount == "半价") discount = "5折";
//截取字符
discount = discount.substr(0, discount.size() - 2);
for(int i = 0; i < discount.size(); i++)
{
dis += (discount[i] - '0') * pow(10, -i - 1);
}
sum += dis * price;
}
//面额刚好100整除
if((int)sum % 100 == 0)
cout << (int)sum << endl;
else
{
cout << (int)sum / 100 * 100 + 100 << endl;
}
return 0;
}这题目数据太长了，输入很麻烦。那么就不讲武德。因为上面代码没错但是运行超级麻烦。这种简单题目直接不讲武德。
#include <iostream>
using namespace std;
int main()
{
// 请在此输入您的代码
double sum = 180.90*0.88+10.25*0.65+56.14*0.9+104.65*0.9+100.30*0.88+297.15*0.5+26.75*0.65+130.62*0.5+240.28*0.58+270.62*0.8+115.87*0.88+247.34*0.95+73.21*0.9+101.00*0.5+79.54*0.5+278.44*0.7+199.26*0.5+12.97*0.9+166.30*0.78+125.50*0.58+84.98*0.9+113.35*0.68+166.57*0.5+42.56*0.9+81.90*0.95+131.78*0.8+255.89*0.78+109.17*0.9+146.69*0.68+139.33*0.65+141.16*0.78+154.74*0.8+59.42*0.8+85.44*0.68+293.70*0.88+261.79*0.65+11.30*0.88+268.27*0.58+128.29*0.88+251.03*0.8+208.39*0.75+128.88*0.75+62.06*0.9+225.87*0.75+12.89*0.75+34.28*0.75+62.16*0.58+129.12*0.5+218.37*0.5+289.69*0.8;
if((int)sum % 100 == 0)
cout << (int)sum;
else
{
int a = (int)(sum+100)/100*100;
cout << a << endl;
}
return 0;
}2.等差素数列
首先将素数全部放到数组当中，然后再用set进行查看是否是素数，f函数用首先确定首项，在确定公差，最后判断是否每项是否是素数，看在set中可不可以找到。
#include <iostream>
#include<vector>
#include<set>
using namespace std;
vector<int> a(5000);
set<int> g;
bool isprime(int x)
{
for(int i = 2; i < x / 2; i++)
{
if(x % i == 0)
return false;
}
return true;
}
int f(vector<int> a, int n)
{
for(int i = 0; i < n; i++)//算首项
{
int first = a[i];
for(int d = 1; d < a[n-1] - first; d++)
{
int m = first;
for(int j = 1; j < 10; j++)
{
m += d;
//求和不是素数
if(g.find(m) == g.end())
break;
if(j == 9)
return d;
}
}
}
}
int main()
{
a[0] = 2, a[1] = 3;
g.insert(2);
g.insert(3);
int index = 2;
int t = 5;
while(index < 5000)
{
//将2-5000的素数都放到set;
if(isprime(t))
{
a[index++] = t;
g.insert(t);
}
t++;
}
//f返回最小公差；
cout << f(a, 5000) << endl;
return 0;
}3.承压计算
题目解析：这个题目看懂题目意思就已经够烦了，就是将上面的数平均分给下面的数，因为最小重量是2086458231，这个垃圾数字处理。
#include <iostream>
#include<algorithm>
using namespace std;
long long a[30][30];
int main()
{
long long factor = 1;
//2的30次方。是为了避免小数。
for(int i = 0; i < 30; i++)
{
factor = factor * 2;
}
for(int i = 0; i < 29; i++)
{
for(int j = 0; j <= i; j++)
{
long long m = 0;
cin >> m;
a[i][j] = m * factor;
}
}
for(int i = 0; i < 29; i++)
{
for(int j = 0; j <= i; j++)
{
long long half = a[i][j] / 2;
a[i + 1][j] += half;
a[i + 1][j + 1] += half;
}
}
//最后一行排序
sort(a[29], a[29] + 30);
cout << a[29][29] / 2 << endl;
return 0;
}4.方格分割
题目解析：本质是递归回溯深搜算法，找规律，是不是方格都是中心对称的，那么递归起点就在中心点，进行上下左右的排查，最后还要回溯，还有因为题目要求是中心对称也是一种方法，所以方法数最后要除以4.
#include <iostream>
using namespace std;
//上下左右方位
int d[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int vis[7][7];
int ret = 0;
void dfs(int x, int y)
{
//递归出口
if(x == 0 || x == 6 || y == 0 || y == 6)
{
ret++;
return;
}
vis[x][y] = 1;
vis[6 - x][6 - y] = 1;
//上下左右
for(int i = 0; i < 4; i++)
{
int nx = x + d[i][0];
int ny = y + d[i][1];
//边界处理
if(nx > 6 || nx < 0 || ny > 6 || ny < 0)
continue;
if(!vis[nx][ny])
{
dfs(nx, ny);
}
}
//回溯
vis[x][y] = 0;
vis[6 - x][6 - y] = 0;
}
int main()
{
dfs(3, 3);
//因为旋转对称是同一种分隔方式
cout << ret / 4 << endl;
return 0;
}5.日期问题
题目解析: 细节很多，逻辑很缜密，自己代码走读一下，就可以找到细节。
#include <iostream>
#include <string>
#include<sstream>
#include<set>
using namespace std;
bool isleap(int a)
{
if((a % 4 == 0 || a % 100 != 0) && a % 400 == 0)
return true;
else
return false;
}
void is(int n, string& s)
{
stringstream ss;
ss << n;
ss >> s;
}
string f(int year, int month, int day)
{
if(year >= 0 && year <= 59) year += 2000;
if(year >= 60 && year <= 99) year += 1900;
if(month < 1 || month > 13) return " ";
if(day < 1 || day > 31) return " ";
//计算闰年
bool _isleap = isleap(year);
switch(month)
{
//考虑闰月
case 2:
if(_isleap && day > 29) return " ";
if(!_isleap && day > 28) return " ";
break;
case 4:
if(day > 30) return " ";
break;
case 6:
if(day > 30) return " ";
break;
case 9:
if(day > 30) return " ";
break;
case 11:
if(day > 30) return " ";
break;
default:
break;
}
//将数字变会字符串
string _a, _b, _c;
is(year, _a);
is(month, _b);
is(day, _c);
//处理前导0；
if(_b.size() == 1) _b = '0' + _b;
if(_c.size() == 1) _c = '0' + _c;
return _a + "-" + _b + "-" + _c;
}
int main()
{
string in;
cin >> in;
//将字符串转化为数字；
int a, b, c;
a = (in[0] - '0') * 10 + (in[1] - '0') ;
b = (in[3] - '0') * 10 + (in[4] - '0') ;
c = (in[6] - '0') * 10 + (in[7] - '0') ;
//年月日
string case1 = f(a, b, c);
//月日年
string case2 = f(b, c, a);
//日月年
string case3 = f(c, b, a);
set<string> ans;
if(case1 != " ") ans.insert(case1);
if(case2 != " ") ans.insert(case2);
if(case3 != " ") ans.insert(case3);
for(set<string>::iterator it = ans.begin(); it != ans.end(); it++)
{
cout << *it << endl;
}
return 0;
}6.包子凑数
题目解析：就是找钱的变形，使用动态规划。
#include <iostream>
using namespace std;
//dp[i]表示凑不到i种蒸笼凑不齐的方案数
int main()
{
int n;
cin >> n;
int dp[20000] = {0};
int a[101];
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
dp[0] = 1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 10001; j++)//10001是最大凑包子数目；
{
if(dp[j])
{
dp[j + a[i]] = 1; //dp[4] = 1; dp[5] = 1
}
}
}
int flag = 0, num = 0;
for(int i = a[n-1]; i < 10001; i++)
{
if(dp[i] == 1)
num++;
if(dp[i] == 0)
num = 0;
if(num == a[0])
{
flag = 1;
break;
}
}
if(flag == 0)
cout << "INF" << endl;
else
{
num = 0;
for(int i = 0; i < 10001; i++)
{
if(dp[i] == 0)
num++;
}
cout << num << endl;
}
return 0;
}7.全球变暖
题目解析：递归深搜fullfill问题，
#include <iostream>
using namespace std;
#define N 1000
int ret = 0;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char IslandSea[N][N];
void dfs(char IslandSea[N][N], int x, int y)
{
for(int k = 0; k < 4; k++)
{
int xx = dx[k] + x;
int yy = dy[k] + y;
if(xx >= 0 && xx < 7 && yy >= 0 && yy < 7)
{
if(IslandSea[xx][yy] == '.')
return;
}
}
ret++;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> IslandSea[i][j];
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(IslandSea[i][j] == '#')
{
dfs(IslandSea, i, j);
}
}
}
cout << ret << endl;
return 0;
}8.k倍区间
题目解析：读清楚题目，本质就是前缀和。cnt用来记录余数个数，将任意两个相同的余数进行组合一定会得到一种区间。
#include <iostream>
using namespace std;
#include<map>
map<int, int> cnt;//存放余数
int a[100000];
int dp[100000];//前缀和
int main()
{
int n, k;
long long count = 0;
cin >> n >> k;
dp[0] = 0;
cnt[0] = 1;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
dp[i] = (dp[i - 1] + a[i] ) % k;//k的倍数
cnt[dp[i]]++;//记录一下。cnt[0]为刚好被k整除的个数。
}
for(int i = 0; i < k; i++)
{
count += (long long) cnt[i] * (cnt[i] - 1) / 2;
}
cout << count << endl;
return 0;
}
