T1 网络连接

一眼哈希表

思路

给一个哈希表，h[string]=int表示一个ip(string)被第i个服务机建立连接。

判断是否合法后，如果是服务机，那么进行判断，如果ip所对应的哈希表已经有值了，那么就输出FAIL否则我们连上去，如果是用户机，判断ip是否建立连接，如果建立连接就输出ip哈希表对应的值即可。

我没有用sscanf所以花了很多时间在特判ERR上。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#define x first
#define y second
#define INF 0x3f3f3f3f
#define speedup (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e4 + 10;

map<string, int> h;
string x[10];
string op, ad;

long long toint(string a) // string转int，自带的atoi()似乎不支持ll
{
    LL x = 0;
    for (int i = 0; i < a.size(); i++)
    {
        x = x * 10 + a[i] - '0';
    }
    return x;
}

bool checkip(int i)
{
    int cnt = 0, idx = 1, cntt = 0;
    bool punc = 0;
    for (int i = 0; i < 10; i++)
        x[i] = ""; // x[i]表示ip中第i个数字
    cin >> op >> ad;
    for (int i = 0; i < ad.size(); i++)
    {
        if (ad[i] == '.') // 标志着一个数字结束了
        {
            if (punc)
                return false;
            cnt++;
            idx++;
        }
        else if (ad[i] == ':' && (cnt != 3))
            return false;
        else if (ad[i] == ':' && cnt == 3)
            punc = true, idx++;
        else if (isdigit(ad[i]))
            x[idx] = x[idx] + ad[i];
        if (!isdigit(ad[i])) // 一堆特判
            cntt++;
    }
    if (!punc || cntt != 4)
        return false;
    for (int j = 1; j <= idx; j++)
    {
        LL tmp = (long long)toint(x[j]);
        if ((j != idx && (tmp < 0 || tmp > 255)) || (j == idx && (tmp < 0 || tmp > 65535)))
            return false;
        if (x[j] != "0" && x[j][0] == '0') // 保留字符串，方便判断前导零
            return false;
        if (x[j] == "")
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        bool t = checkip(i);
        if (t == 0)
        {
            puts("ERR");
            continue;
        }
        if (op == "Server")
        {
            if (h[ad])
            {
                puts("FAIL");
                continue;
            }
            else
            {
                puts("OK");
                h[ad] = i;
                continue;
            }
        }
        else
        {
            if (!h[ad])
            {
                puts("FAIL");
                continue;
            }
            else
            {
                printf("%d\n", h[ad]);
                continue;
            }
        }
    }

    return 0;
}

T3 Being awesome ism

题面竟然是传播宗教（

别考虑太复杂，直接判断即可，时间复杂度$O(Tnm)$

分n种情况

• 全是P，无解，输出MORTAL
• 全是A，不用动，输出0
• 有靠边缘的一行或者一列全是A，那么只需要直接pia下来，输出1
• 有地图中间一行或者一列全是A，分别往两边pia一下，输出2
• 角落中四个点任意一个是A，先pia成一行，再pia下来，输出2
• 在边缘上有一个点是A，先上下pia成一行，再pia过去，输出3
• 中间有一个点是，先左右pia成一行，再上下pia一下，输出4

代码一一对应上述情况

#include <iostream>

using namespace std;

const int N = 65;

char g[N][N];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, m;
        cin >> n >> m;
        bool is_no = 1, is_all = 1;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                cin >> g[i][j];
                if(g[i][j] == 'A') is_no = false;
                if(g[i][j] == 'P') is_all = false;
            }
        if(is_no)
        {
            puts("MORTAL");
            continue;
        }
        else if(is_all)
        {
            puts("0");
            continue;
        }
        bool is_r = 1;
        for(int j = 1; j <= m; j ++)
        {
            if(g[1][j] == 'P') 
            {
                is_r = false;
                break;
            }
        }
        if(is_r) 
        {
            puts("1");
            continue;
        }
        is_r = 1;
        for(int j = 1; j <= m; j ++)
        {
            if(g[n][j] == 'P') 
            {
                is_r = false;
                break;
            }
        }
        if(is_r) 
        {
            puts("1");
            continue;
        }
        bool is_c = 1;
        for(int j = 1; j <= n; j ++)
        {
            if(g[j][1] == 'P') 
            {
                is_c = false;
                break;
            }
        }
        if(is_c)
        {
            puts("1");
            continue;
        }
        is_c = 1;
        for(int j = 1; j <= n; j ++)
        {
            if(g[j][m] == 'P') 
            {
                is_c = false;
                break;
            }
        }
        if(is_c)
        {
            puts("1");
            continue;
        }

        if(g[1][1] == 'A' || g[1][m] == 'A' || g[n][1] == 'A' || g[n][m] == 'A')
        {
            puts("2");
            continue;
        }
        bool flg = 1, is_can = 0;


        for(int i = 1; i <= n; i ++)
        {
            flg = 1;
            for(int j = 1; j <= m; j ++)
            {
                if(g[i][j] == 'P')
                {
                    flg = 0;
                    break;
                }
            }
            if(flg)
            {
                is_can = 1;
                break;
            } 
        }
        if(is_can) 
        {
            puts("2");
            continue;
        }
        for(int i = 1; i <= m; i ++)
        {
            flg = 1;
            for(int j = 1; j <= n; j ++)
            {
                if(g[j][i] == 'P')
                {
                    flg = 0;
                    break;
                }
            }
            if(flg)
            {
                is_can = 1;
                break;
            } 
        }
        if(is_can) 
        {
            puts("2");
            continue;
        }

        flg = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(g[i][1] == 'A' || g[i][m] == 'A')
            {
                flg = 1;
                break;
            }
        }
        if(flg) 
        {
            puts("3");
            continue;
        }
        flg = 0;
        for(int i = 1; i <= m; i ++)
        {
            if(g[1][i] == 'A' || g[n][i] == 'A')
            {
                flg = 1;
                break;
            }
        }
        if(flg) 
        {
            puts("3");
            continue;
        }


        else 
        {
            puts("4");
            continue;
        }
    }

    return 0;
}