AcWing在线竞赛——第44场竞赛

第一题：AcWing 4317. 不同正整数的个数

个人认为最好的做法还是方法1哈希表

#include
#include
#include
#include
using namespace std;
int main()
{
    int n;
    cin>>n;
    unordered_set hash;
    while (n -- )
    {
        int x;
        cin >> x;
        if(x) hash.insert(x);
    }
    cout << hash.size()< 
其中代码参考了y总的视频
 
下面看一下其他做法，方法2排序
 
#include
#include
using namespace std;
int main (){
    int num,n;//num记录不同正整数个数
    int a[110];//比数据多几位
    cin>>n;
    for (int i = 0; i < n; i ++ ) scanf("%d",&a[i]);
    sort(a,a+n);//排序（记得头文件algorithm）
    for(int i=0;i 
 方法3集合容器set
 
其中set类型是一种排好序的数组，存进去的元素可以自动排序，且每个元素出现有且仅有一次
 
#include
using namespace std;
set num;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin >> x;
        if(x) num.insert(x);//x为正整数
    }
    cout< 
set集合自动判重，最后输出num大小即可
 
方法4数组
 
#include
using namespace std;
int main(){
    int n,a[601]={},num=0;//开辟全为零数组
    cin>>n;
    while (n -- ){
        int k;
        cin>>k;
        if(k>0) a[k]++;//出现正整数就改变数组，相同数字也只改变一个数组值
    }
    for(int i=1;i<=600;i++){
        if(a[i]!=0) num++;//记录不同数字个数
    }
    cout< 
类比这种，都是一种思想
 
 for(int i=0;i>a[i];
        if(a[i]>0) b[a[i]]++;
    }
    int num=0;
    for(int i=0;i<=600;i++)
    {
        if(b[i]>0) num++;
    }
 
简单题聊的差不多了进入下一题
 
AcWing 4318. 最短路径 
题目的最短路径可理解为除题目输入外的区域为障碍物，则题目给的路线即可能为最短，所以判断题目所给的路线是否为最短共有两个要求：
 
1.路线不能存在交叉，即不能重复，若重复则非最短路径
 
2.路线不能相邻，除来的方向之外的三个方向相邻也非最短路径
 
第一种方式
 
#include 
#include 
#include 

using namespace std;
const int N = 201,B=N/2;//上下左右四个方向各100，B为开始起点
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//四方向偏移值
bool st[N][N];//定义走过路线的方格
int get(char c)
{
    if(c=='U') return 0;//上0下2左3右1
    if(c=='R') return 1;
    if(c=='D') return 2;
    return 3;
}
int main()
{
    string str;
    cin >> str;
    bool res=true;//定义答案为true
    
    int x=B,y=B;//中心点位置
    st[x][y]=true;//开始格为true
    for(auto c:str)
    {
        int d=get(c);
        x+=dx[d],y+=dy[d];//下个坐标位置
        if(st[x][y]) res=false;//若格子被走过，标记为false
        for(int i=0;i<4;i++)
        if(i!=(d^2)&&st[x+dx[i]][y+dy[i]])//判断是否为相邻格子即判断是否为非来的方向的剩余三个方向相邻
        res=false;//若满足相邻或重复则返回false
        
        st[x][y]=true;
    }
    if(res) cout << "YES";
    else cout << "NO";
    return 0;
}

 
第二种方式：
 
个人觉得与第一种类似，该方法为首先给每一格子赋值为1，起始开始后，每一步判断下一步格子的数字多少，若为1，则该格子上下左右都加上1；若大于1，则返回NO
 
该方法参考了大佬们的思路。
 
#include 
#include 
#include 
using namespace std;

const int N = 201;
int st[N][N];
string r;
void dx(int x,int y)//定义函数给格子周围加1
{
    st[x][y+1]++;
    st[x][y-1]++;
    st[x][y]++;
    st[x+1][y]++;
    st[x-1][y]++;
}
int main (){
    cin>>r;
    int x=N/2,y=N/2;//中心点
    dx(x,y);
    for(int i=0;i1)
        {
            cout << "NO";
            return 0;
        }
        dx(x,y);
    }
    cout << "YES";
    
}
 
第三题在能力范围之外了，之后再说吧。
 
萌新第一次做题解，大佬勿喷<^_^>