目录
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;elsereturn 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;
}
