**此文章持续更新，直至寒假没有每日一题！！！！
Week 1：
货仓选址
在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数N。
第二行N个整数A1~AN。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例：
4
6 2 9 1
输出样例：
12
思路：中位数到各个点的距离最短
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a[100000];
// sit表示确定的商店的位置，distance用来计算到商店的总的距离
int sits=0,distance=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n) // 将数组排序
if(n&1) sit=a[n/2]; //位运算判断是有奇数个还是有偶数个数字
else sit=(a[n/2]+a[n/2-1])/2;
for(int i=0;i<n;i++) distance+=fabs(sit-a[i]);
cout<<distance;
return 0;
数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n，表示数字三角形的层数。
接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30
思路：这是一道非常简单的动态dp，有两个基本的思路。一是从上向下的寻找路径，但是需要考虑的是边界的问题；二是从下向上的寻找路径，不需要考虑边界问题。
将已经走过的路径和作为一个集合，没走一步筛选出数值最大的集合继续向上查找。最后一定走到00位置的数，即为集合的最终值。代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a[500][500];
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;k<=i;j++)
cin>>a[i][j];
int road[500][500] // 此数组即为所走路径的集合
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)
road[i][j]=max(road[i+1][j+1]+a[i][j],road[i+1][j]+a[i][j]);
cout<<road[0][0];
return 0;
Week 2
蛇形矩阵
输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n*m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行，包含两个整数n和m。
输出格式
输出满足要求的矩阵。
矩阵占n行，每行包含m个空格隔开的整数。
数据范围
1≤n,m≤100
输入样例：
3 3
输出样例：
1 2 3
8 9 4
7 6 5
思路：记录下四个方向的偏移量，撞墙即转弯；
#include<iostream>
using namespace std;
int main(){
int n,q[110][110],m;
cin>>n>>m;
int dx[]={
-1,0,1,0},dy[]={
0,1,0,-1}; //将二维的偏移量存储下来
int x=0,y=0,d=1;
for(int i=1;i<=n*m;i++){
q[x][y]=i;
int a=x+dx[d],b=y+dy[d];
if(a<0||a>=n||b<=||b>=m||q[a][b]){
d=(d+1)%4;
a=x+dx[d],b=y+dy[d];
}
x=a,y=b;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<q[i][j]<<' ';
}
cout<<endl;
}
return 0;
红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
输入样例：
6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
0 0
输出样例：
45
方法一：先提供一个我自己写的新手好理解的方法笨笨的方法
依然需要上一道题中的偏移量数组，之后从初始位置出发，在判断下一个位置可以走的时候向下遍历并标记，知道全部遍历，这里就用到了递归（对于一个新手来说 ，我是现在才发现原来要各走各的路径肯定是要用到递归）
#include<iostream>
#include<cstring>
using namespace std;
const int dx[]={
-1,0,1,0},dy[]={
0,1,0,-1};
int num[20][20]={
0};
int W,H;
void road(int x,int y,char str[][20],int num[][20]){
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(str[a][b]=='.'&&num[a][b]==0&&a>=0&&a<H&&b>=0&&b<W){
//条件一定要写全
num[a][b]=1;
road(a,b,str,num);
}
}
}
int main(){
while(1){
cin>>W>>H;
if(W==0&&H==0) break;
int x,y,count=1;
memset(num,0,sizeof(num));
char str[20][20];
memset(str,0,sizeof(str));
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>str[i][j];
if(str[i][j]=='@')
x=i,y=j;
}
}
road(x,y,str,num);
for(int i=0;i<H;i++){
for(int j=0;j<W;j++)
if(num[i][j]==1) count++;
}
cout<<count<<endl;
}
}
//宽度搜索的方法
#include <iostream>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
int n, m;
char g[N][N];
int bfs(int sx, int sy)
{
queue<PII> q;
q.push({
sx, sy});
g[sx][sy] = '#';
int res = 0;
int dx[] = {
-1, 0, 1, 0}, dy[] = {
0, 1, 0, -1};
while (q.size())
{
auto t = q.front();
q.pop();
res ++ ;
for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
g[x][y] = '#';
q.push({
x, y});
}
}
return res;
}
int main()
{
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i ++ ) cin >> g[i];
int x, y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '@')
{
x = i;
y = j;
}
cout << bfs(x, y) << endl;
}
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/686360/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//深度搜索
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];
int dx[] = {
-1, 0, 1, 0}, dy[] = {
0, 1, 0, -1};
int dfs(int x, int y)
{
int res = 1;
g[x][y] = '#';
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
res += dfs(a, b);
}
return res;
}
int main()
{
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i ++ ) cin >> g[i];
int x, y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '@')
{
x = i;
y = j;
}
cout << dfs(x, y) << endl;
}
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/686360/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
回文平方
回文数是指数字从前往后读和从后往前读都相同的数字。
例如数字 12321 就是典型的回文数字。
现在给定你一个整数 B，请你判断 1∼300 之间的所有整数中，有哪些整数的平方转化为 B 进制后，其 B 进制表示是回文数字。
输入格式
一个整数 B。
输出格式
每行包含两个在 B 进制下表示的数字。
第一个表示满足平方值转化为 B 进制后是回文数字那个数，第二个数表示第一个数的平方。
所有满足条件的数字按从小到大顺序依次输出。
数据范围
2≤B≤20,
对于大于 9 的数字，用 A 表示 10，用 B 表示 11，以此类推。
输入样例：
10
输出样例：
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696
这是一道比较简单的判断回文数的题目，其中包括了进位制的转换。
#include<iostream>
using namespace std;
char get(int n){
if(n<=9) return n+'9';
return n-10+'A';
}
string base(int n,int b){
string num;
while(n) {
num+=get(n%b),n/b;} //当进位制大于9时用大写的英文字母表示
reverse(num.begin(),num.end());
return num;
}
bool check(string num){
for(int i=0,j=num.size()-1;i<j;i++,j--)
if(num[i]!=num[j])
return false;
return true;
int main(){
int b;
cin>>b;
for(int i=1;i<=300;i++){
auto num+=base(i*i,b) //auto 可自动识别变量类型并定义
if(check(num))
cout<<base(i,b)<<' '<<num<<endl;
}
return 0;
剪绳子
有N根绳子，第i根绳子长度为Li，现在需要M根等长的绳子，你可以对N根绳子进行任意裁剪（不能拼接），请你帮忙计算出这M根绳子最长的长度是多少。
输入格式
第一行包含2个正整数N、M，表示原始绳子的数量和需求绳子的数量。
第二行包含N个整数，其中第 i 个整数Li表示第 i 根绳子的长度。
输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。
数据范围
1≤N,M≤100000,
0<Li<109
输入样例：
3 4
3 5 4
输出样例：
2.50
样例解释
第一根和第三根分别裁剪出一根2.50长度的绳子，第二根剪成2根2.50长度的绳子，刚好4根。
思路：这里用到二分法。如果直接寻找绳子的长度是不好找到的但是如果我们给定绳子的长度进而来判断是否可是取得m个绳子，那么这就好判断了，所以本题用到了二分法。
这里有一个小技巧，如果保留k位小说的话l与r之间的精度小于1e-（k+2）即可
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 100010;
double L[N];
int n,m;
bool check(double mid){
int count=0;
for(int i=0;i<n;i++) count+=L[i]/mid;
return count>=m;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>L[i];
sort(L,L+n);
double l=0,r=L[n-1];
while(r-l>1e-4){
double mid=(l+r)/2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf",l);
return 0;
}
分巧克力
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
形状是正方形，边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6
输出样例：
2
标签：整数二分
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n , k;
int h[N], w[N];
bool check(int mid){
long long count=0;
for(int i=0;i<n;i++){
count+=(long long )h[i] / mid * (w[i] / mid);
if(count>=k) return true;
}
return false;
}
int main(){
cin>>n>>k;
for (int i = 0; i < n; i ++ ) cin>>h[i]>>w[i];
int l=1,r=1e5;
while(l<r){
int mid=(l+r+1)>>1; //避免出现死循环
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
校门外的树（简单暴力法）
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。
现在要把这些区域中的树（包括区域端点处的两棵树）移走。
你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
输入文件的第一行有两个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
数据范围
1≤L≤10000,
1≤M≤100
输入样例：
500 3
150 300
100 200
470 471
输出样例：
298
#include<iostream>
using namespace std;
int a[10000]={
0};
int main(){
int L,M;
cin>>L>>M;
fill(a,a+L+1,1);
for(int i=0;i<M;i++){
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++) a[i]=0;
}
int count=0;
for(int i=0;i<=L;i++) if(a[i]==1) count++;
cout<<count;
return 0;
}
奖学金
多字排序
#include<iostream>
#include<algorithm>
using namespace std;
struct student{
int num;
int Chinese;
int math;
int English;
int sorce;
};
bool cmp(student a,student b){
if(a.sorce!=b.sorce) return a.sorce>b.sorce;
else if(a.Chinese!=b.Chinese) return a.Chinese>b.Chinese;
else return a.num<b.num;
}
int main(){
int n;
cin>>n;
student a[305];
for(int i=1;i<=n;i++){
a[i].num=i;
cin>>a[i].Chinese>>a[i].math>>a[i].English;
a[i].sorce=a[i].Chinese+a[i].math+a[i].English;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=5;i++){
cout<<a[i].num<<' '<<a[i].sorce<<endl;
}
return 0;
}
十三号星期五
十三号星期五真的很不常见吗？
每个月的十三号是星期五的频率是否比一周中的其他几天低？
请编写一个程序，计算 N 年内每个月的 13 号是星期日，星期一，星期二，星期三，星期四，星期五和星期六的频率。
测试的时间段将会开始于 1900 年 1 月 1 日，结束于 1900+N−1 年 12 月 31日。
一些有助于你解题的额外信息：
1900 年 1 月 1 日是星期一。
在一年中，4 月、6 月、9 月、11 月每个月 30 天，2 月平年 28 天，闰年 29 天，其他月份每个月31天。
公历年份是 4 的倍数且不是 100 的倍数的年份为闰年，例如 1992 年是闰年，1990 年不是闰年。
公历年份是整百数并且是 400 的倍数的也是闰年，例如1700年，1800年，1900年，2100年不是闰年，2000年是闰年。
输入格式
共一行，包含一个整数 N。
输出格式
共一行，包含七个整数，整数之间用一个空格隔开，依次表示星期六，星期日，星期一，星期二，星期三，星期四，星期五在十三号出现的次数。
数据范围
1≤N≤400
输入样例：
20
输出样例：
36 33 34 33 35 35 34
插入通用算法之前记录一个公式：拉姆拉尔森公式：
W= (d+2m+3(m+1)/5+y+y/4-y/100+y/400+1)%7
数学大佬请移步：https://www.cnblogs.com/SeekHit/p/7498408.html
#include<iostream>
#include<algorithm>
using namespace std;
int a[2][12]={
{
31,29,31,30,31,30,31,31,30,31,30,31},
{
31,28,31,30,31,30,31,31,30,31,30,31}};
int b[7]={
0};
int main(){
int n; cin>>n;
int num=13,year=1900,k;
while(n--){
if(year%4==0&&year%100!=0||year%400==0)
k=0; else k=1;
for(int j=0;j<12;j++) {
b[num%7]++;
num+=a[k][j];
}
year++;
}
for (int i = 6, j = 0; j < 7; i++, j++) {
cout << b[i % 7] << " ";
}
return 0;
}
京公网安备 11010502036488号