A：跑步

知识点：最大公约数、最小公倍数、递归、函数

解题思路：要三位同学在第x天相遇，就需要求出三个数的最小公倍数，可以先求出两个的最小公倍数，其结果与第三个数再求出最小公倍数即可。注意假设两个数为a,b则，ab=最大公约数(a，b)最小公倍数(a，b)，故最小公倍数(a，b)=a*b/最大公约数(a，b)，而最大公约数需要使用辗转相除法(递归来解决)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int gcd(int x,int y){
    if(x%y==0) return y;
    return gcd(y,x%y);
} 
int main(){
    cin>>a>>b>>c;
    int x=a*b/gcd(a,b);
    int y=x*c/gcd(x,c);
    cout<<y; 
    return 0;
}

B：文具购买

知识点：枚举

解题思路：题目要求a，b，c的最小值尽可能大，所以就要让它们的最小值越接近n/14越好，如果a，b，c的最小值为n/14时无解，则让a，b，c的最小值为n/14−1，以此类推，直到有解为止。所以a从n/14开始往下枚举最小值然后依次枚举b，c，一旦遇到有解就输出，结束程序。此时的解就是最优解。注意枚举范围，b从a到n/4，c从a到n/3。最后如果无解，输出−1。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;//n元钱
int main() {
    cin>>n;
    for(int i=n/14; i>=0; i--) {
        for(int j=i; j<=n/4; j++) {
            for(int k=i; k<=n/3; k++) {
                if(i*7+j*4+k*3==n) {
                    cout<<i<<' '<<j<<' '<<k<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<-1;
    return 0;
}

C：序列

知识点：贪心

解题思路：题目让我们求在 [li,ri]中至少有ci个数。我们可以将所有的区间按右端点的大小，从小到大排列。如果当前区间已经满足了它的要求，那么它其中的数的位置可以随意摆放，又因为它之后的区间的右端点的值比当前区间右端点大，所以我们贪心地选择当前区间最右端的数，可以尽量满足后面区间的条件。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,f[1001],maxn,ans;
struct node{
    int l,r,c;
    bool operator<(const node& b)const{
        return r<b.r;//按照右区间进行排序 
    }
}a[1001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r>>a[i].c;
        maxn=max(maxn,a[i].r);
    }
    sort(a+1,a+1+n);
    //贪心策略：尽量靠后的放数字
    for(int i=1;i<=n;i++){
        int cnt=0;//统计个数
        for(int j=a[i].r;j>=a[i].l;j--){
            if(f[j]){
                cnt++;
                if(cnt>=a[i].c){
                    break;    
                }
            }
        } 
        if(cnt<a[i].c){//个数不足 
            for(int j=a[i].r;j>=a[i].l;j--){
                if(!f[j]){
                    f[j]=1;
                    cnt++;
                    if(cnt>=a[i].c){
                        break;
                    }
                }
            } 
        }
    } 
    for(int i=1;i<=maxn;i++){
        if(f[i])ans++;
    }
    cout<<ans;
    return 0;
}

D：棋盘

知识点：递归、深度优先搜索

解题思路：

对于每个已经到达的位置，若其金币超过记忆数组的存储数据，则不需要深搜，因为这一步不是最优解，前面已经走过比本次更优的解。然后记录到达该位置的最优解，若走到了终点就进行答案判断结束搜索。最后考虑新的坐标，若其未越界未被访问，就考虑：

下一个块没有颜色 对于当前状态，有以下状态以及操作: (1) 当前踩的块是被施法过的，不能施法，继续寻找其他扩展块 (2) 当前踩的块没有被施法过，对下一个块染成和当前块一样的颜色，代价+2 下一个块有颜色 对于当前状态，有以下状态以及操作: (1) 当前块与下一个块颜色相同，扩展且无需任何代价 (2) 当前块与下一个块颜色相同，扩展且无需任何代价

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;//n*n矩阵 m个数据
int a[1001][1001];//存放数据
bool b[1001][1001];//标记
int c[1001][1001];//最小花费金币
int d[][2]={{0,1},{0,-1},{1,0},{-1,0}};
int ans=INT_MAX;//答案 
void dfs(int x,int y,int money,bool magic){
    if(money>=c[x][y]) return;
    c[x][y]=money;
    if(x==n&&y==n){
        ans=min(ans,money);
        return;
    }
    for(int i=0;i<4;i++){
        int xx=x+d[i][0],yy=y+d[i][1];
        //未越界 未来过  
        if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!b[xx][yy]){
            if(a[xx][yy]==-1 && magic)  continue;//新的位置是无色 上一次使用过魔法
            b[xx][yy]=1;
            if(a[xx][yy]==-1){//新位置为无色 
                a[xx][yy]=a[x][y];
                dfs(xx,yy,money+2,1);//这个位置使用过魔法了 
                a[xx][yy]=-1;    
            }else{
                if(a[xx][yy]==a[x][y]) dfs(xx,yy,money,0);
                else dfs(xx,yy,money+1,0);
            }             
            b[xx][yy]=0; 
        } 
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=-1;
            c[i][j]=INT_MAX;
        }
    }
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        a[x][y]=z;
    }
    //1,1的位置搜索money为0,上一次没使用魔法0
    dfs(1,1,0,0);
    if(ans==INT_MAX)cout<<-1;
    else cout<<ans;
    return 0;
}