$T1$

考试错误：一遍过，无。

思路：

$1$.要想让差值>$k$,最好的方法是用最大值减最小值，如果大于$k$,输出最大值。

$2$.否则选最大值和次大值，输出次大值。

$3$.为了方便，我们可以使用sort(a+1,a+n+1)排序。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N];
signed main(){
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1,a+n+1);
    if(a[n]-a[1]>k) cout << a[n];
    else cout << a[n-1];
}

$T2$

考试错误:在计算s1,s2的时候没有取余，导致数据溢出，只得了$50$分。

思路：

$1$.这一题虽然位数多，但是可以不用高精度。

$2$.更具乘法定律：在和相同的情况下，差越大，乘积越小。

$3$.输入两个字符串$a$,$b$.

$4$.所以我们定义两个变量s1、s2，s1负责存储$^2$每一位的最小值，s2存储$^2$最大值。在每次存储$^2$的时候都需要取余，不然会溢出。

$5$.最后取余并输出。

2:*10+a[i]/b[i]

代码：

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int mod=998244353;
signed main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
    int n;
    cin >> n;
    string a,b;
    cin >> a >> b;
    int s1=0,s2=0;
    for(int i=0;i<a.size();i++){
    	s1=(s1*10+max(a[i],b[i])-'0')%mod;
    	s2=(s2*10+min(a[i],b[i])-'0')%mod;
	}
    cout << (int)(((s1%mod)*(s2%mod))%mod);
}

$T3$

考试错误：骗了$30$分，没有发生错误。

$DP$思路：

$1$.状态表示:f[i]以$i$为结尾的合法区间数量。flag[a[i]]: 第$i$个气球上次出现的位置

$2$.初始化:f[1]=flag[a[1]]=1。

$3$状态计算：循环从$2$到$n$,每次定义一个$j$=flag[a[i]],再让flag[a[i]]=$i$，随后开始计算↓。

$4$.状态转移方程：

if(!j) f[i]=min(i,f[i-1]+1);
if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1);
if(i-j>k) f[i]=min(i-j,f[i-1]+1);

$5$.答案：f[1]+......+f[n]。

完整代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+20;
int flag[N],a[N],f[N];
signed main(){
    freopen("balloon.in","r",stdin);
    freopen("balloon.out","w",stdout);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    f[1]=1,flag[a[1]]=1;
    int sum=1;
    for(int i=2;i<=n;i++){
        int j=flag[a[i]];
        flag[a[i]]=i;
        if(!j) f[i]=min(i,f[i-1]+1);
        if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1);
        if(i-j>k) f[i]=min(i-j,f[i-1]+1);
        sum+=f[i];
    } 
    cout << sum;
}

$T4$

错误原因：骗了$10$分，没有错误。

思路：

$1$.定义符号栈，数字栈并遍历字符串。

$2$.遇到'&','|','!'，加入符号栈。

$3$.遇到't','f','('，加入数字栈。

$4$.遇到')'则一直弹出数字栈并存到一个字符串中，直到遇到'(' (左括号不存)；

$5$.再根据符号栈栈顶运算符进行运算，并将结果存入数字栈，随后弹出符号栈。

$6$.最后输出数字栈栈顶元素。

代码：

#include <bits/stdc++.h>
using namespace std;
vector<char> num,jjcc;
void solve(){
    string s;
    cin >> s;
    bool flag=0;
    string t;
    for(int i=0;i<s.size();i++){
        bool ans=0;
        if(s[i]==',') continue;
        if(s[i]=='t'||s[i]=='f'||s[i]=='(') num.push_back(s[i]);
        if(s[i]=='!'||s[i]=='&'||s[i]=='|') jjcc.push_back(s[i]);
        if(s[i]==')'){  
            char v=jjcc.back();
            jjcc.pop_back();
            if(num.back()=='t') ans=1;
            if(num.back()=='f') ans=0;
            if(v=='!'){
                if(ans) num.push_back('f');
                else num.push_back('t');
            }else{
                while(num.back()!='('){
                    bool c;
                    if(num.back()=='t') c=1;
                    else if(num.back()=='f') c=0;
                    if(v=='|') ans=ans||c;
                    else if(v=='&') ans=ans&&c; 
                    num.pop_back();
                }
                num.pop_back();
                if(ans) num.push_back('t');
                if(!ans) num.push_back('f');
            }
        }
    }
    if(num.back()=='t'){
        cout << "true\n";
    }if(num.back()=='f'){
        cout << "false\n";
    }
}
int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    int ccccc;
    cin >> ccccc;
    while(ccccc--){
        solve();
    }
}

$T5$

考试错误：对搜索理解的不深刻，没有做这一题，以后要多做题，多思考。

思路：

DFS暴搜题，用洪水填充算法每次将一个部落用搜索全设为$0$,最后看搜了几次就是几个部落。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[110][110];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int n,m;
void dfs(int x,int y){
    a[x][y]=0;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<1||nx>n||ny<1||ny>m) continue;
        if(a[nx][ny]==0) continue;
        dfs(nx,ny);
    }
}
int main(){
    freopen("ymx.in","r",stdin);
    freopen("ymx.out","w",stdout);
    cin >> n >> m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin >> c;
            if(c-'0'!=0) a[i][j]=1;
            else a[i][j]=0;
        }
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                dfs(i,j);
                cnt++;
            }
        }
    }
    cout << cnt;
}

$T6$

考试错误：$DP$题，没有做出来。

$DP$思路:

状态表示：f[i]:从第$i$个数到第$n$个数至少要删除几个数。

初始化：f[n]=1。

状态计算：

//删：f[i+1]+1。
//不删:f[i+a[i]+1](这里要保证i+a[i]<=n)
//状态转移方程：f[i]=min(f[i+1]+1,f[i+a[i]+1]);

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+20;
int a[N],f[N];
signed main(){
    freopen("summary.in","r",stdin);
    freopen("summary.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    f[n]=1;
    for(int i=n-1;i>=1;i--){
        if(i+a[i]<=n) f[i]=min(f[i+1]+1,f[i+a[i]+1]);
        else f[i]=f[i+1]+1;
    }
    cout << f[1];
}

感谢观看!

THANK YOU TO WATCH!