3192. 出现次数最多的数

题意：简单题，统计出现次数最多的那个数，如果相等直接输出最小的即可。

思路：直接模拟即可

代码：

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        mp[x]++;
    }
    int ans=0,idx=0;
    for(auto item:mp) {
        int x=item.first;
        int y=item.second;
        if(y>ans) ans=y,idx=x;
        else if(y==ans) idx=min(idx,x);
    }
    cout<<idx<<'\n';
    return 0;
}

3193. ISBN号码

题意：如题描述
思路：模拟即可

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int len=s.size();
    int k=1;
    int ans=0;
    for(int i=0;i<len-1;i++) {
        if(s[i]>='0'&&s[i]<='9') {
            ans=ans+k*(s[i]-'0');
            k++;
         //   cout<<s[i]<<" "<<ans<<'\n';
        }
    }
    
    ans%=11;
    int f=1;
    //cout<<ans<<'\n';
    if(ans==10) {
        if(s[len-1]!='X') f=0;
    }
    else {
        if(ans!=(s[len-1]-'0')) f=0;
    }
    if(f) puts("Right");
    else {
        if(ans!=10)s[len-1]=ans+'0';
        else s[len-1]='X';
        cout<<s<<'\n';
    }
    return 0;
}

3194. 最大的矩形

题意：找去一段连续区间能够组成的最大矩形面积
思路：经典单调栈思路。详情可以转移到另外一篇博客查看

注意：
初始化h[0],h[n+1]为-1，而tt栈顶每次维护一个单调栈即初始化为0，
因为条件为假如左边没有比起小的元素那么tt减到0,stk[0]=0,第一个元素已经初始化为0，肯定不会比当前元素大，所以其答案也正好为-1,即如果存在则答案为左边比起小的最大下标，不存在为-1

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int h[N];
int stk[N];
int l[N],r[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>h[i];
    }
    h[0]=h[n+1]=-1;
    int tt=0;
    stk[0]=0;
    for(int i=1;i<=n;i++) {
        while(h[stk[tt]]>=h[i])tt--;
        l[i]=stk[tt];
        stk[++tt]=i;
    }
    tt=0;
    stk[0]=n+1;
    for(int i=n;i>=1;i--) {
        while(h[stk[tt]]>=h[i]) tt--;
        r[i]=stk[tt];
        stk[++tt]=i;
    }
    int res=0;
    for(int i=1;i<=n;i++) {
        res=max(res,h[i]*(r[i]-l[i]-1));
    }
    cout<<res<<'\n';
    return 0;
}

3195. 有趣的数

题意：如连接所示
思路：分类看待问题，将0，1看做一类，将2，3看做一类满足，0必在1前面，而2也必在3前面，对于其中的一类，假设0有k中取值，那么1则有n-k取值 同理2，3。预处理出组合数，求其从2到n-2的和即可，

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
const int mod=1e9+7;
typedef long long LL;

LL f[N][N];

void init()
{
    for(int i=0;i<N;i++) {
        for(int j=0;j<=i;j++){
            if(!j)f[i][j]=1;
            else f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
        }
    }
}

int main()
{
    init();
    int n;
    cin>>n;
    LL ans=0;
    
    for(int i=2;i<=n-2;i++) {
        ans=(ans+1LL*(f[n-1][i]*(i-1)%mod*1LL*(n-i-1)%mod)%mod)%mod;
    }
    cout<<ans<<'\n';
    return 0;
    
}

3196. I’m stuck!

题意：走迷宫问题，要满足以下两个条件，其中第一个为从起始点出发能到达该点，并且从该点不能到达终点，问该种类型的点的个数。

思路：正向dfs1标记所有能够到达的点，反向dfs2标记掉能够从终点到达该点，如何通过反向边到达该点即满足，对上下左右四个方向编号，那么上下分别为0，2 即假设一个点(x1,y1)能够从上方到达(x2,y2)，那么判断(x2,y2)能否通过下方到达(x1,y1)即可。注意图论中广泛存在反向边取的方法为对2进行异或，

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=55;

string mp[N];
bool st1[N][N],st2[N][N];
int r,c;
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

bool ok(int x,int y,int k){
    if(mp[x][y]=='+') return true;
    if(mp[x][y]=='S'||mp[x][y]=='T') return true;
    if(mp[x][y]=='-'&&(k==1||k==3)) return true;
    if(mp[x][y]=='|'&&(k==0||k==2)) return true;
    if(mp[x][y]=='.'&&k==2) return true;
    return false;
}

void dfs1(int x,int y)
{
    st1[x][y]=true;
    for(int i=0;i<4;i++){
        int ex=x+dx[i];
        int ey=y+dy[i];
        if(ex<1||ex>r||ey<1||ey>c) continue;
        if(mp[ex][ey]=='#'||st1[ex][ey]) continue;
        if(ok(x,y,i)) dfs1(ex,ey);
    }
}

void dfs2(int x,int y){
    st2[x][y]=true;
    for(int i=0;i<4;i++) {
        int ex=x+dx[i];
        int ey=y+dy[i];
        if(ex<1||ex>r||ey<1||ey>c) continue;
        if(mp[ex][ey]=='#'||st2[ex][ey]) continue;
        if(ok(ex,ey,i^2)) dfs2(ex,ey);
    }
}

int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++) {
        cin>>mp[i];
        mp[i]=" "+mp[i];
    }
    int tx,ty;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(mp[i][j]=='S') dfs1(i,j);
            else if(mp[i][j]=='T'){
                dfs2(i,j);
                tx=i;
                ty=j;
            }
        }
    }
    if(!st1[tx][ty]) return puts("I'm stuck!")*0;
    int res=0;
    
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++) {
            if(st1[i][j]&&!st2[i][j]) res++;
        }
    }
    cout<<res<<'\n';
    return 0;
    
}