nefu 1849 两数之和

map统计一下个数就行。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,s,a[N];
map<int,int>vis;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        vis[a[i]]++;
    }
    cin>>s;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[s-a[i]])
        {
            if(s-a[i]==a[i])
            {
                if(vis[a[i]]==1)continue;
                else {flag=1;break;}
            }
            else {flag=1;break;}
        }
    }
    if(flag==1)printf("Yes\n");
    else printf("No\n");
    return 0;
}

nefu 1857 六花的素数（1）

这题看起来好像是素数筛打表什么的，那是迷惑你的，其实是贪心，只要求出x最多能拆成多少个最小素数2，拆了之后可能还剩1或者剩0，那都不用管了。

#include <bits/stdc++.h>
using namespace std;
int n,x;
long long ans;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            ans=ans+x/2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

nefu 1860 黑猫大战桐乃

说起来你可能不信，这题签到题难度，比赛的时候我忘记之前学过的巴什博弈了，自己纸上手工打表找规律找了好几十分钟，还WA了一发…看看我比赛写的AC代码：

#include <bits/stdc++.h>
using namespace std;
long long n,k;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>k)
    {
        if(k==1)
        {
            if(n%2==0)printf("MeiMeiSaiGao\n");
            else printf("HeiMaoSaiGao\n");
        }
        else
        {
            if(k>=n)printf("HeiMaoSaiGao\n");
            else
            {
                if(k==2)
                {
                    if(n%3==0)printf("MeiMeiSaiGao\n");
                    else printf("HeiMaoSaiGao\n");
                }
                else
                {
                    if(k==n-1)printf("MeiMeiSaiGao\n");
                    else printf("HeiMaoSaiGao\n");
                }
            }
        }
    }
    return 0;
}

嗯，我们再对比一下用巴什博弈模板写的AC代码：（所以还是要时常复习之前学过的东西啊）

#include <bits/stdc++.h>
using namespace std;
long long n,m;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        if(n%(m+1)==0)printf("MeiMeiSaiGao\n");//后手必胜
        else printf("HeiMaoSaiGao\n");
    }
    return 0;
}

nefu 1858 六花的素数（2）

这题竟然要用哥德巴赫猜想（1e7以内显然是正确的，嗯，因为打表出来验证了一下就是正确的）
哥德巴赫猜想：任何一个大于2的偶数都可以拆成两个素数之和。
其他的看代码注释吧，应该写得很详细了。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,x,mx,mx1,mx2,cnt,ans,prime[N];
bool flag[N];
void get_prime()
{
    memset(flag,1,sizeof(flag));
    flag[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(flag[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            flag[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>n)
    {
        ans=0;
        while(n--)
        {
            cin>>x;
            if(x<=3)
            {
                if(x==1)mx=0;
                if(x==2||x==3)mx=1;
            }
            else//x>=4时
            {
                if(x&1)//x是奇数，拆成两个数为奇数+偶数，而这两个数又要尽可能的出现素数，所以要让那个偶数为2
                {
                    //x不拆的情况，直接判断x是否为素数
                    if(flag[x])mx1=1;
                    else mx1=0;
                    //x拆成2个数的情况，其中一个数是偶数素数2，判断另一个数x-2是否为素数
                    if(flag[x-2])mx2=2;
                    else mx2=1;
                    mx=max(mx1,mx2);
                }
                else mx=2;//哥德巴赫猜想，x>=4的偶数必然能拆分成两个素数，贡献素数个数为2
            }
            ans=ans+mx;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1850 矩阵距离

将原矩阵中1的位置入队，之后依次将其出队开始BFS，记录最短步数。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N][N];
int n,m,ans[N][N],vis[N][N];
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct node
{
    int x,y,flag,cnt;//flag是为了区分原矩阵中的某个位置的元素是0还是1
};
queue<node>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='1')
            {
                q.push({i,j,1,0});
                vis[i][j]=1;
            }
        }
    while(!q.empty())//开始BFS
    {
        node tmp=q.front();q.pop();
        int x=tmp.x;
        int y=tmp.y;
        ans[x][y]=tmp.cnt;
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0)
            {
                q.push({nx,ny,0,tmp.cnt+1});
                vis[nx][ny]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            j==m?printf("%d\n",ans[i][j]):printf("%d ",ans[i][j]);
    return 0;
}