牛客小白月赛59

A.我会开摆

• 题意
  • 给定n=4的方阵，问是否存在n=2的方阵中四个格子全是一个字符的情况
• 题解
  • 直接枚举所有点当n=2方阵的左上角，看是否符合题目要求
  • 注意：检查n=2的方阵时，要先排除某点为左上角没有n=2方阵情况
• 代码

#include <bits/stdc++.h>
using namespace std;
char a[5][5];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 1; i <= 4; i++)
        {
            for (int j = 1; j <= 4; j++)
            {
                cin >> a[i][j];
            }
        }
        int flag = 0;
        for (int i = 1; i <= 3; i++)
        {
            for (int j = 1; j <= 3; j++)
            {
                if (a[i][j] == '.' && a[i][j + 1] == '.' && a[i + 1][j] == '.' && a[i + 1][j + 1] == '.')
                {
                    flag = 1;
                    break;
                }
                if (a[i][j] == '#' && a[i][j + 1] == '#' && a[i + 1][j] == '#' && a[i + 1][j + 1] == '#')
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)
            {
                break;
            }
        }
        if (flag == 1)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

B.走廊的灯

• 题意
  • 路上有n盏灯，0代表灭的，1代表亮的，2代表闪烁，可以看成灭的也可以看成亮的
  • 问最长的状态一样的连续的灯的数量为多少
• 题解
  • 暴力，分两次遍历，第一次把2全部当作0，第二次把2全部当作1，找出最长的连续段即可
• 代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        string a;
        cin >> a;
        int len = a.size();
        int sum = 0;
        int maxn = 0;
        for (int i = 0; i < len; i++)
        {
            if (a[i] != '0')
            {
                sum++;
            }
            else
            {
                sum = 0;
            }
            maxn = max(maxn, sum);
        }
        sum = 0;
        for (int i = 0; i < len; i++)
        {
            if (a[i] != '1')
            {
                sum++;
            }
            else
            {
                sum = 0;
            }
            maxn = max(maxn, sum);
        }
        printf("%d\n", maxn);
    }
    return 0;
}

C.输出练习

• 题意
  • 从小到大输出区间[l,r]中，k的非负整数次方的值
  • l,r,k范围 [0,2^63)
• 题解
  • 除去特例的0,1；当k=2时，l=0,r=2^63-1，会有最多个输出，也才64个。所以直接暴力即可
  • 注意特判。k=1时，直接输出1即可，否则暴力和会炸；k=0时，0^0=1,但是0^1=0,0^2=0，即如果区间符合要求，那么k=0会有两个输出。麻麻麻这里WA麻了，好无语
  • 注意数据范围，while(k<=r)这样写会爆long long，所以我这里用java逃课
• 代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            BigInteger l, r, k;
            l = sc.nextBigInteger();
            r = sc.nextBigInteger();
            k = sc.nextBigInteger();
            BigInteger p = new BigInteger("0");
            BigInteger q = new BigInteger("1");
            boolean fuck = true;
            StringBuilder sb = new StringBuilder();
            if (k.compareTo(p) == 0) {
                if (l.compareTo(p) <= 0) {
                    sb.append(0+" ");
                    fuck = false;
                }
            }
            if (l.compareTo(q) <= 0 && r.compareTo(q) >= 0) {
                sb.append(1 + " ");
                fuck = false;
            }
            BigInteger pos=k;
            if (k.compareTo(p) != 0 && k.compareTo(q) != 0) {
                while (r.compareTo(k) >= 0) {
                    if (l.compareTo(k) <= 0 && r.compareTo(k) >= 0) {
                        sb.append(k + " ");
                        fuck = false;
                    }
                    k=k.multiply(pos);
                }
            }
            if(fuck)
            {
                System.out.println("None.");
            }else{
                System.out.println(sb);
            }
        }
    }
}

D.国际象棋

• 题意

  • 竖直放置的n*m的棋盘，每次选一列放一枚棋子，重力原因棋子落到最下面
  • 对于第i个放置的棋子，i为奇数时，其所放的颜色为黑色，偶数为白色棋子
  • k子连珠定义为：横竖撇捺四个方向存在某个方向有k个相同颜色棋子
  • 一共放t颗棋子，若出现k子连珠则游戏结束，保证有解，问游戏结束时放置了多少棋子

• 题解

  • 模拟题。

    水平方向，竖直方向，两个斜方向分别枚举看是否符合条件即可

• 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, t;
char a[1008][1008];
int judge(int x, int y)
{
    if (x >= 1 && x <= n && y >= 1 && y <= m)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int solve(int x, int y, int ch)
{
    //横
    int sum = 1;
    int xx = x, yy = y - 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        yy--;
    }
    xx = x, yy = y + 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        yy++;
    }
    //竖
    sum = 1;
    xx = x + 1, yy = y;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        xx++;
    }
    //左斜
    sum = 1;
    xx = x - 1, yy = y - 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        xx--, yy--;
    }
    xx = x + 1, yy = y + 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        xx++, yy++;
    }
    //右斜
    sum = 1;
    xx = x + 1, yy = y - 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        xx++, yy--;
    }
    xx = x - 1, yy = y + 1;
    while (1)
    {
        if (!judge(xx, yy))
        {
            break;
        }
        if (a[xx][yy] == ch)
        {
            sum += 1;
            if (sum >= k)
            {
                return 1;
            }
        }
        else
        {
            break;
        }
        xx--, yy++;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k >> t;
    int ans;
    int flag = 0;
    int sum = 0;
    int cnt = 0;
    map<int, int> mp;
    memset(a, '!', sizeof(a));
    while (t--)
    {
        ++cnt;
        cin >> ans;
        if (flag == 0)
        {
            sum++;
            int x = n - mp[ans];
            int y = ans;
            mp[ans]++;
            if (cnt % 2 == 1)
            {
                a[x][y] = '1';
            }
            else
            {
                a[x][y] = '0';
            }
            int pos = solve(x, y, a[x][y]);
            if (pos == 1)
            {
                flag = 1;
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}

E.弹珠碰撞

• 题意
  • 长度为n的线段上有m个弹珠，给定每个弹珠的方向左/右，及坐标
  • 弹珠每秒走一个单位，发生碰撞会停滞一秒，且两珠方向互换，多次碰撞停滞时间叠加
  • 当弹珠走到0，或者n+1认为掉落
  • 问线段上最后掉落的弹珠掉出所花的时间
• 题解
  • 碰撞转向直接看成穿过就好了，因为弹珠之间没有区别
  • 以某个向左走于位置i的弹珠为例，没有碰撞时时间为i-0，有碰撞需要记录在i左边且方向向右的弹珠数r，时间为i-0+r，从左往右边遍历遍记录答案和数量即可。某个向右走于位置i的弹珠，n+1-i+l，注意这里是逆序遍历。
  • 这类题经常就是这样的写法，相当于固定题型了
• 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int d[N], p[N];
int pos[N];
int main()
{
    memset(pos, -1, sizeof(pos));
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &d[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &p[i]);
        pos[p[i]] = d[i];
    }
    int maxn = 0;
    int ans = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (pos[i] == -1)
        {
            continue;
        }
        else if (pos[i] == 0)
        {
            maxn = max(maxn, i - 0 + ans);
        }
        else if (pos[i] == 1)
        {
            ans += 1;
        }
    }
    for (int i = n; i >= 1; i--)
    {
        if (pos[i] == -1)
        {
            continue;
        }
        else if (pos[i] == 1)
        {
            maxn = max(maxn, n + 1 - i + cnt);
        }
        else if (pos[i] == 0)
        {
            cnt += 1;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

F.困难卷积

• 题意
  • 
• 题解
  • trick题。如果我们直接暴力枚举两个数组，复杂度为O(n^2)炸了
  • 观察数据范围特征，数组的和范围在1e7以内，那么考虑与种类数有关，因为贪心构造一个数种类多的数组为0 1 … x，等差数列求和得到x=sqrt(2e7)，即数组中最多有sqrt(2e7)种数，此时遍历的复杂度已经降低了，所以开始考虑如何计算答案
  • 以同种类数分别分组a,b后，我们可以得到数num及其出现的次数cnt。那么对于某一组别a1和某一组别b1对于答案的贡献为(a1.cnt * b1.cnt * floor(sqrt(差))，那么只需要枚举a分组和b分组，时间复杂度为O(sqrt(2e7)^2)=O(2e7)
• 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N];
int main()
{
    map<int, int> m1, m2;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        m1[a[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
        m2[b[i]]++;
    }
    long long sum = 0;
    for (auto i : m1)
    {
        for (auto j : m2)
        {
            long long ans = sqrt(abs(i.first - j.first));
            sum += i.second * j.second * ans;
        }
    }
    printf("%lld\n", sum);
    return 0;
}