【CCF】模板生成系统 问题描述　　有一类节日的日期并不是固定的，而是以“a月的第b个星期c”的形式定下来的，比如说母亲节就定为每年的五月的第二个星期日。　　现在，给你a，b，c和y1, y2(1850 ≤ y1, y2 ≤ 2050)，希望你输出从公元y1年到公元y2年间的每年的a月的第b个星期c的日期。　　提示：关于闰年的规则：年份是400的整数倍时是闰年，否则年份是4的倍数并且不是100的倍数时是闰年，其他年份都不是闰年。例如1900年就不是闰年，而2000年是闰年。　　为了方便你推算，已知1850年1月1日是星期二。输入格式　　输入包含恰好一行，有五个整数a, b, c, y1, y2。其中c=1, 2, ……, 6, 7分别表示星期一、二、……、六、日。输出格式　　对于y1和y2之间的每一个年份，包括y1和y2，按照年份从小到大的顺序输出一行。　　如果该年的a月第b个星期c确实存在，则以"yyyy/mm/dd"的格式输出，即输出四位数的年份，两位数的月份，两位数的日期，中间用斜杠“/”分隔，位数不足时前补零。　　如果该年的a月第b个星期c并不存在，则输出"none"（不包含双引号)。样例输入5 2 7 2014 2015样例输出2014/05/112015/05/10评测用例规模与约定　　所有评测用例都满足：1 ≤ a ≤ 12，1 ≤ b ≤ 5，1 ≤ c ≤ 7，1850 ≤ y1, y2 ≤ 2050。提交代码之后得到90分，原因是运行超时。可能是处理数据大的时候运行时间长了#include <bits/stdc++.h> using namespace std; vector<string> tem; //模板保存 map<string,string> dict; //键值对字典 int m,n; string s; string key,val; //字符串替换处理 void strhandle(string str){ int begin,end,len; string k,v; while(str.find("{{ ") != string::npos){ begin = str.find("{{ ") + 3;//由于 {{ 占用了三个字符 len = str.find(" }}"); len -= begin; //总长度等于末尾位置减去起始位置 k = str.substr(begin,len); //用于查找的键 if(dict.find(k) == dict.end()) v = ""; else v = dict.find(k)->second; //真正的字典值 str.replace(begin-3,len+6,v); //替换字符串 } cout<<str<<endl; return; } int main(){ //freopen("input.txt","r",stdin); //!!!!!!!!!!!!!!!!!!! cin>>m>>n; getchar(); //要给出一个空行 for(int i=1;i<=m;i++) { getline(cin,s); //读取到s中 tem.push_back(s); //放到tem中 //cout<<i<<' '<<s; } //获取键值对字典 for(int i=1;i<=n;i++){ getline(cin,s); int pos = s.find_first_of(" "); //找到空格的位置 // 其实substr底层应该是for(i=0;i<pos;i++) key = s.substr(0,pos); //区间 [0,pos) 不包括pos位置的字符 val = s.substr(pos+1,s.length()); //不包括pos位置的字符到结束 while (val.find("\"") != string::npos) val.replace(val.find("\""),1,""); //处理双引号 //键值对插入map dict.insert(make_pair(key,val)); } //开始处理模板替换 for(int i=0;i<tem.size();i++){ //一行一行处理 s = tem[i]; strhandle(s); } return 0; }

【CCF】最优配餐 问题描述　　栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。　　栋栋的连锁店所在的区域可以看成是一个n×n的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的（红色标注）。　　方格图中的线表示可以行走的道路，相邻两个格点的距离为1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。　　送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费1块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。　　现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。输入格式　　输入的第一行包含四个整数n, m, k, d，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。　　接下来m行，每行两个整数xi, yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。　　接下来k行，每行三个整数xi, yi, ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置）　　接下来d行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。输出格式　　输出一个整数，表示最优送餐方式下所需要花费的成本。样例输入10 2 3 31 18 81 5 12 3 36 7 21 22 26 8样例输出29评测用例规模与约定　　前30%的评测用例满足：1<=n <=20。　　前60%的评测用例满足：1<=n<=100。　　所有评测用例都满足：1<=n<=1000，1<=m, k, d<=n^2。可能有多个客户在同一个格点上。每个客户的订餐量不超过1000，每个客户所需要的餐都能被送到。这个问题直接使用了bfs 广度优先搜索就可以，用visited[][] 标记访问过的坐标，把不能访问的坐标也标记成访问过的坐标就可以了。统计一下订餐坐标的总数量，以判断结束与否。当初提交时没有考虑n的范围，最终结果（100万）超出了int的范围，导致当初只有80分具体原因类似于这个提交为100分的代码如下，注释很详细：#include <bits/stdc++.h> using namespace std; const int N = 1005; //最大大小 const int DIRECTSIZE = 4; //上下左右四个方向 int order[N][N]; //某坐标位置的订单数 int visited[N][N] ; //某坐标是否已经访问过 struct direct{ //定义一个关于方向的结构体 int drow,dcol; }direct[DIRECTSIZE] = {{-1,0},{1,0},{0,-1},{0,1}}; struct node{ //用于记录每个坐标走了多少步 int row,col,step; node(){} node(int r,int c,int s){row = r,col = c,step = s;} }; queue<node> q; // 定义一个node队列 int coord = 0; //总坐标数量 long long ans = 0; //这里需要使用long long，因为有些系统上 long int 和 int 是相同的 //广度优先搜索 void bfs(int n){ //v用来保存所有数据，包括走到某点坐标时的步数 //front用以临时保存 node front,v; //如果队列中有元素，就一直执行 while(!q.empty()){ front = q.front(); //取出q中第一个元素 q.pop(); //删除q中第一个元素 //搜索该点的四个方位 for(int i=0;i<DIRECTSIZE;i++){ //注意这里下标是从0开始的 v.row = direct[i].drow + front.row; v.col = direct[i].dcol + front.col; v.step = front.step + 1; //坐标位置加一步 //判断是否超出方格图大小 if(v.row < 1 || v.row > n || v.col < 1 || v.col > n) continue; //跳出本次循环 //是否已经搜索过 if(visited[v.row][v.col]) continue; //如果有订单 if(order[v.row][v.col] != 0){ //因为 每一个订单每走一个单位的距离需要花费1块钱 ans += v.step * order[v.row][v.col]; //有可能坐标点不止一个订单 visited[v.row][v.col] = 1; //可以不加 coord--; //坐标数减少 if(coord == 0) return; //结束 } //把搜索过的地点标记 visited[v.row][v.col] = 1; //把没有走到头的v放进队列 q.push(v); } } } int main(){ //freopen("input.txt","r",stdin); //直接本地读取数据 int n,m,k,d,x,y,c; //用以接收的变量 //初始化变量 memset(order,0,sizeof(order)); memset(visited,0,sizeof(visited)); //输入 cin>>n>>m>>k>>d; for(int i=1;i<=m;i++){//输入分店坐标，分店坐标不能搜索 ，所以设置为true cin>>x>>y; q.push(node(x,y,0)); //把分店坐标压入队列中，以此为基础 //queue<node> q; visited[x][y] = 1; } for(int i=1;i<=k;i++) { cin>>x>>y; //订单坐标 cin>>c; //该坐标订单数量 if(order[x][y] == 0) //如果该坐标没有搜索过 coord++; //坐标数加1 order[x][y] += c; //把订单数赋给坐标位置 } for(int i=1;i<=d;i++) { cin>>x>>y; visited[x][y] = 1; //把不能通过的也标记成已搜索 } //开启广度优先搜索 bfs(n); cout<<ans<<endl; return 0; }参考100分的方法：http://blog.csdn.net/tigerisland45/article/details/54945267

【CCF】最大的矩形 问题描述　　在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。　　请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。输入格式　　第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。　　第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。输出格式　　输出一行，包含一个整数，即给定直方图内的最大矩形的面积。样例输入63 1 6 5 2 3样例输出10分析遇到这个题目第一反应就是暴力破解，看到数据范围并不是很大[1,10000]，所以就用暴力破解解决了。另外一种解法是使用STL的包装类vector，可以实现动态数据存储，不受限于数据的多少，不过我没有实现，另一种解法详细步骤在这里暴力破解代码#include <bits/stdc++.h> using namespace std; int main(){ int n,i,j; cin>>n; int height,max=0,area; int a[1001]; for(i=1;i<=n;i++) cin>>a[i]; //暴力破解 for(i=1;i<=n;i++){ height = a[i]; for(j=i;j>=1;j--){ if(a[j] < height) height=a[j]; area = height*(i-j+1); if(max < area) max=area; } } /* //暴力破解正向逆向都可以 for(int i=1; i<=n; i++) { height = a[i]; for(int j=i; j<=n; j++) { if(a[j] < height) height = a[j]; area = (j - i + 1) * height; if(area > max) max = area; } } */ cout<<max; return 0; }

C++中字符串转数字 CCF认证里有一题需要用到字符串转数字，于是我定义了一个string类型的变量，然后当做Char型数组用。但是在转换到整型数字时，发现了一点点问题。先看代码#include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int sum=0,j=1; //注意这个循环里 for(int i=0; i<(int)s.length()-1; i++){ sum += (s[i] - '0') * j++; //这里为什么不是sum += s[i] * j++，而是需要先减去'0'。否则结果偏大 } cout<<sum<<endl; return 0; }在这里字符（串）转int整型时需要先减去'0'，而且int整型转字符（串）时同样也需要在后面加上一个'0'，如下 char c; c = 10 % 3; c = c + '0'; //注释这一段之后输出的为 ASCII表中 1 所代表的特殊符号 cout<<c<<endl; //此时输出结果为 1看完这张表我就突然发现问题了当把字符转直接转换成十进制数字时，比如把字符'1'转换成1，此时字符'1'所对应的十进制数字其实是十进制当中的49，因此直接把字符当整型计算的话 得到的结果自然会偏大了。

【CCF】工资计算 问题描述　　小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为S元，则他应交的个人所得税按如下公式计算：　　1） 个人所得税起征点为3500元，若S不超过3500，则不交税，3500元以上的部分才计算个人所得税，令A=S-3500元；　　2） A中不超过1500元的部分，税率3%；　　3） A中超过1500元未超过4500元的部分，税率10%；　　4） A中超过4500元未超过9000元的部分，税率20%；　　5） A中超过9000元未超过35000元的部分，税率25%；　　6） A中超过35000元未超过55000元的部分，税率30%；　　7） A中超过55000元未超过80000元的部分，税率35%；　　8） A中超过80000元的部分，税率45%；　　例如，如果小明的税前工资为10000元，则A=10000-3500=6500元，其中不超过1500元部分应缴税1500×3%=45元，超过1500元不超过4500元部分应缴税(4500-1500)×10%=300元，超过4500元部分应缴税(6500-4500)×20%=400元。总共缴税745元，税后所得为9255元。　　已知小明这个月税后所得为T元，请问他的税前工资S是多少元。输入格式　　输入的第一行包含一个整数T，表示小明的税后所得。所有评测数据保证小明的税前工资为一个整百的数。输出格式　　输出一个整数S，表示小明的税前工资。样例输入9255样例输出10000评测用例规模与约定　　对于所有评测用例，1 ≤ T ≤ 100000。可以暴力破解，不要被数学蒙蔽了双眼另外注意审题，看清楚工资的计算法#include <bits/stdc++.h> using namespace std; int t,a,tax; int main(){ cin>>tax; for(int i=1;i<=1000000;i++) { a=i-3500; if(i <= 3500){ t = i; }else if(a<=1500){ t = i - a*0.03; }else if(a>1500 && a<=4500){ t = i - 1500*0.03 - (a-1500)*0.1; }else if(a>4500 && a<=9000){ t = i - 1500*0.03 - 3000*0.1 - (a-4500)*0.2; }else if(a>9000 && a<=35000){ t = i - 1500*0.03 - 3000*0.1 - 4500*0.2 - (a-9000)*0.25; }else if(a>35000 && a<=55000){ t = i - 1500*0.03 - 3000*0.1 - 4500*0.2 - 26000*0.25 - (a-35000)*0.3; }else if(a>55000 && a<=80000){ t = i - 1500*0.03 - 3000*0.1 - 4500*0.2 - 26000*0.25 - 20000*0.3 - (a-55000)*0.35; }else{ t = i - 1500*0.03 - 3000*0.1 - 4500*0.2 - 26000*0.25 - 20000*0.3 - 25000*0.35 - (a-80000)*0.45; } if(t == tax){ cout<<i<<endl; return 0; } } return 0; }

【CCF】数字排序 问题描述　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。输入格式　　输入的第一行包含一个整数n，表示给定数字的个数。　　第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。输出格式　　输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。样例输入125 2 3 3 1 3 4 2 5 2 3 5样例输出3 42 35 31 14 1评测用例规模与约定　　1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。#include <bits/stdc++.h> using namespace std; int num[1001]; int a[1001][2]={0}; void swap(int a[2],int b[2]){ int temp; for(int i=0;i<=1;i++){ temp = a[i]; a[i] = b[i]; b[i] = temp; } } int main(){ //freopen("./input/szpx.txt","r",stdin) ; int n,i,j; cin>>n; for(i=0;i<n;i++) cin>>num[i]; //整理数据存入 a[][]数组中 第一维是数字，第二维是次数 //个人喜好，用一维也行 for(i=0;i<n;i++){ for(j=1;j<=1000;j++){ //数字是从小到大的 if(num[i] == j){ a[j][0] = j; a[j][1] ++ ; } } } for(i=1;i<=1000;i++){ //查看哪个数的次数最多 for(j=i;j<=1000;j++){ //次数不相同 if(a[j][1] > a[i][1]){ //把次数由大到小排序 swap(a[i],a[j]); } //如果次数相同 while(a[i][1] == a[j][1]) { if(a[i][0] > a[j][0]){ swap(a[i],a[j]); } break; } } } //输出 for(i=1;i<=n && a[i][0]!=0;i++){ cout<<a[i][0]<<' '<<a[i][1]<<endl; } return 0; }

【CCF】最大波动 问题描述　　小明正在利用股票的波动程度来研究股票。小明拿到了一只股票每天收盘时的价格，他想知道，这只股票连续几天的最大波动值是多少，即在这几天中某天收盘价格与前一天收盘价格之差的绝对值最大是多少。输入格式　　输入的第一行包含了一个整数n，表示小明拿到的收盘价格的连续天数。　　第二行包含n个正整数，依次表示每天的收盘价格。输出格式　　输出一个整数，表示这只股票这n天中的最大波动值。样例输入62 5 5 7 3 5样例输出4样例说明　　第四天和第五天之间的波动最大，波动值为|3-7|=4。评测用例规模与约定　　对于所有评测用例，2 ≤ n ≤ 1000。股票每一天的价格为1到10000之间的整数。简单的一题，没什么说的#include <bits/stdc++.h> using namespace std; int main(){ int max,temp; int i,j,n,a[1001]; cin>>n; for(i=1;i<=n;i++){ cin>>a[i]; while(i>1){ j=i-1; temp = abs(a[i]-a[j]); max = temp>max ? temp:max; //三目运算，和if/else本质相同 break; } } cout<<max; return 0; }

【CCF】分蛋糕 问题描述　　小明今天生日，他有n块蛋糕要分给朋友们吃，这n块蛋糕（编号为1到n）的重量分别为a1, a2, …, an。小明想分给每个朋友至少重量为k的蛋糕。小明的朋友们已经排好队准备领蛋糕，对于每个朋友，小明总是先将自己手中编号最小的蛋糕分给他，当这个朋友所分得蛋糕的重量不到k时，再继续将剩下的蛋糕中编号最小的给他，直到小明的蛋糕分完或者这个朋友分到的蛋糕的总重量大于等于k。　　请问当小明的蛋糕分完时，总共有多少个朋友分到了蛋糕。输入格式　　输入的第一行包含了两个整数n, k，意义如上所述。　　第二行包含n个正整数，依次表示a1, a2, …, an。输出格式　　输出一个整数，表示有多少个朋友分到了蛋糕。样例输入6 92 6 5 6 3 5样例输出3样例说明　　第一个朋友分到了前3块蛋糕，第二个朋友分到了第4、5块蛋糕，第三个朋友分到了最后一块蛋糕。评测用例规模与约定　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 10000，1 ≤ ai ≤ 1000。坑点这一题的坑点（其实也是我没有注意审题）在于要求的是把编号最小的分给小朋友，而不是重量最小的。另外，题目要考虑最后一名小朋友，如果最后一名小朋友的蛋糕重量小于K但是大于0，也算是分到了蛋糕。不过我觉得队最后一名小朋友来说有失公正:)#include <stdio.h> #include<iostream> using namespace std; int main() { int n,k; int a[1000] = {0}; int temp; int all=0; int num=0; scanf("%d",&n); scanf("%d",&k); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } //得到a[]数组 for(int i=0;i<n;i++) { all = a[i] + all; if(all >= k){ all = 0; num++; } if(i == n-1 && all > 0) { num++; } } printf("%d",num); return 0; }