A：气球上升

知识点：数学

思路：对于每个气球，就是用 v*(t-ti)这个公式求，下面是推导：

• 首先要求出剪短绳子后有多少时间飞，就是 t-ti。
• 最后 ×v得出最终高度。

找到最大的 maxn 和最小的 pos 输出。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,maxn=INT_MIN,pos;
int main(){    
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        int v,ti;cin>>v>>ti;
        if(maxn<v*(t-ti)){
            maxn=v*(t-ti);
            pos=i;
        }
    }
    cout<<pos;
    return 0;
}

B：Cow Cash G

知识点：背包问题

思路：令dp[i] [j]表示前i种货币能拼凑出金额为j的方案总数，则可列出如下表格：

可以看出dp[i] [j]=dp[i-1] [j]+dp[i] [j-a[i]] （j>=a[i]）

​ dp[i] [j]=dp[i-1] [j] （j<a[i]）

参考代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[26],dp[26][10001],ans;
//dp[i][j]:前i种货币能拼凑出金额为j的方案总数 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i][0]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j>=a[i]){
                dp[i][j]=dp[i-1][j]+dp[i][j-a[i]];
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    } 
    cout<<dp[n][m];
    return 0;
}

C：舞会

知识点：深度优先搜索、动态规划

思路：首先找到唯一的树根root，再从根节点深搜自己的儿子。

设dp[x] [0]表示以x为根的子树，且x不参加舞会的最大快乐值

​ dp[x] [1]表示以x为根的子树，且x参加了舞会的最大快乐值

则dp[x] [0]=max(dp[y] [1],dp[y] [0]) （y是x的儿子）

​ dp[x] [1]+=dp[y] [0]; （y是x的儿子）

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,w[6006],fa[6006],root=1,dp[6006][2];
vector<int> e[6006];
void dfs(int x){
    dp[x][1]=w[x];
    for(int y:e[x]){
        dfs(y);
        dp[x][0]+=max(dp[y][1],dp[y][0]);
        dp[x][1]+=dp[y][0];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        e[v].push_back(u);
        fa[u]=1;
    }
    while(fa[root])root++;
    dfs(root);
    printf("%d",max(dp[root][0],dp[root][1]));
    return 0;
}

D：单词方阵

知识点：深度优先搜索

思路：①找出首字母't';

②找出字母't'旁边的'u'字母，用全局变量k来记录扩展方向

③依次沿着k方向记录其字母的位置存在结构体数字中。

④若直至到'.'的字符完全无误的匹配，则将结构体数组记录的坐标进行标记，然后返回

⑤最后看看是否打标记，若打标记，则输出"tuling.",否则输出'*'.

参考代码：

#include <iostream>
using namespace std;
char c[111][111],st[]="tuling.";
int n,vis[111][111],k,dir[][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
struct point{
    int x,y;
}p[111];//储存位置坐标 
void dfs(int x,int y,int cur){
    p[cur].x=x,p[cur].y=y;//把当前的x,y储存起来
    if(cur==6){
        for(int i=0;i<7;i++)//进行标记
            vis[p[i].x][p[i].y]=1;
        return;
    }
    int xx=x+dir[k][0],yy=y+dir[k][1];
    if(c[xx][yy]==st[cur+1])
        dfs(xx,yy,cur+1);    
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(c[i][j]=='t'){
                for(k=0;k<8;k++)
                    if(c[i+dir[k][0]][j+dir[k][1]]=='u') //代表可以从i,j的位置进行搜索
                        dfs(i,j,0); //x,y位置p储存0代表第几个单词 
            }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(vis[i][j]) cout<<c[i][j];
            else cout<<'*'; 
        }
        cout<<endl;
    }
    return 0;
}