8.18测试总结

· · 算法·理论

8.18测试总结

T638908 宾果

得分:40

应得:100

考点:数字转换为行/列

行=(x-1)/n+1;

列=(x-1)%n+1;

错误思路:模拟（ＴＬＥ了）

正确思路:使用多个计数器进行统计，如果有任意一个计数器＝＝n,输出

正确代码:


#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,t;
int a[2005],b[2005],c,d;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    if(t<n)
    {
        cout<<-1<<endl;
        return 0;
    }
    for(int i=1;i<=t;i++)
    {
        int x;
        cin>>x;
        int h=(x-1)/n+1,l=(x-1)%n+1;
        a[h]++;
        b[l]++;
        if(h==l)
        {
            c++;
        }
        if(h+l==n+1)
        {
            d++;
        }
        if(a[h]==n||b[l]==n||c==n||d==n)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

T641930 长度为n的第k个排列

得分:0

应得:100

考点:DFS全排列

爆0原因:电脑关机，代码丢失QAQ

正确思路:使用DFS进行全排列ay

核心代码(DFS):


void dfs(int u){
    if(u==n+1){
        sum++;
        if(sum==k)for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        return ;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]!=1){
            a[u]=i;
            vis[i]=1;
            dfs(u+1);
            vis[i]=0;
        }
    }
}

正确代码:


#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,k,sum;
int a[15];
int vis[15];
void dfs(int u){
    if(u==n+1){
        sum++;
        if(sum==k)for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        return ;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]!=1){
            a[u]=i;
            vis[i]=1;
            dfs(u+1);
            vis[i]=0;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    dfs(1);
    return 0;
}

T638280 兜兜转转还是你

得分:40

应得:100

考点:BFS(广度优先搜索)

错误思路:骗分

正确思路:使用BFS查询是否有>=4的路径

核心代码(BFS):


void bfs(int x,int y){
    mp[x][y]=1;
    q.push({x,y});
    while(q.size()){
        node k=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=k.x+dx[i],yy=k.y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy])continue;
            mp[xx][yy]=1;
            if(xx==sx+1&&yy==sy||xx==sx-1&&yy==sy||xx==sx&&yy==sy+1||xx==sx&&yy==sy-1){
                cout<<"Yes"<<endl;
                f=1;
                return ;
            }
            q.push({xx,yy});
        }
    }
}

正确代码:


#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct node{
    int x,y;
};
int n,m;
vector<int>mp[1000005];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
queue<node>q;
int sy,sx;
bool f=0;
void bfs(int x,int y){
    mp[x][y]=1;
    q.push({x,y});
    while(q.size()){
        node k=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=k.x+dx[i],yy=k.y+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||mp[xx][yy])continue;
            mp[xx][yy]=1;
            if(xx==sx+1&&yy==sy||xx==sx-1&&yy==sy||xx==sx&&yy==sy+1||xx==sx&&yy==sy-1){
                cout<<"Yes"<<endl;
                f=1;
                return ;
            }
            q.push({xx,yy});
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        mp[i].push_back(0);
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='#')
            {
                mp[i].push_back(1);
            }
            else if(c=='.')
            {
                mp[i].push_back(0);
            }
            else
            {
                sx=i;
                sy=j;
                mp[i].push_back(1);
            }
        }
    }
    for(int i=0;i<4;i++)
    {
        int x=sx+dx[i];
        int y=sy+dy[i];
        if(x<1||x>n||y<1||y>m) 
        {
            continue;
        }
        if(!mp[x][y])
        {
            while(q.size())
            {
                q.pop();
            }
            bfs(x,y);
            if(f==1)
            {
                return 0;
            }
        }
    }
    cout<<"No";
    return 0;
}