二〇二三 五月第四周

AcWing周赛 102周

https://www.acwing.com/activity/content/3257/

或运算

题目描述

给定两个长度为 n 的整数序列 a1, a2, … , an 以及 b1, b2, …, bn。
设 A = a1 or a2 or … or an，B=b1 or b2 or … or bn。
请你计算并输出 A+B 的值。
or 表示按位或运算。

输入格式

第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含 n 个整数 b1,b2,…,bn。

输出格式

一个整数，表示 A+B 的值。

输入样例

5
1 2 4 3 2
2 3 3 12 1

输出样例

22

import java.util.*;
public class Main
{
   public static void main(String[] args)
   {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       int[] a = new int[n];
       int[] b = new int[n];
       int suma = 0, sumb = 0;

       for (int i = 0; i < n; i++)
       {
           a[i] = in.nextInt();
           suma |= a[i];
       }
       for (int i = 0; i < n; i++)
       {
           b[i] = in.nextInt();
           sumb |= b[i];
       }

       System.out.println(suma + sumb);
   }
}

倍增

题目描述

给定一个长度为 n 的整数序列 a1, a2, …, an。
你可以对该序列进行任意次倍增操作（也可以不进行任何操作）。
每次倍增操作可以任选序列中的一个元素，并将其乘以 2 或乘以 3。
我们的目标是让序列中所有元素的值都相等。
请你判断，目标是否能够实现。

输入格式

第一行包含整数 n。
第二行包含 n 个整数 a1, a2, …, an。

输出格式

如果可以让序列中所有元素的值都相等，则输出 Yes，否则，输出 No。

输入样例

4
75 150 75 50

输出格式

Yes

数据范围

前 6
个测试点满足 2 ≤ n ≤ 10 。
所有测试点满足 2 ≤ n ≤ 10^5，1 ≤ ai ≤ 10^9 。

import java.util.*;
public class Main
{
   public static void main(String[] args)
   {
       Scanner in = new Scanner(System.in);
       boolean yn = true;
       int n = in.nextInt();
       int[] a = new int[n + 1];

       for (int i = 0; i < n; i++)
       {
           a[i] = in.nextInt();

           while (a[i] % 2 == 0) a[i] /= 2;
           while (a[i] % 3 == 0) a[i] /= 3;
       }
       a[n] = a[n - 1];

       for (int i = 0; i < n; i++)
       {
           if (a[i + 1] != a[i]) yn = false;
       }
       if(!yn) System.out.println("No");
       else System.out.println("Yes");
   }
}

AcWing周赛 105周

https://www.acwing.com/activity/content/3290/

极值数量

题目描述

给定一个长度为 n 的整数数组 a1, a2, …, an
如果一个元素左右两边均有相邻元素（也就是不位于数组的两端），且满足以下两个条件之一：

• 该元素的值严格大于其左右相邻元素的值
• 该元素的值严格小于其左右相邻元素的值

则称该元素为一个极值元素。
请你计算，给定数组中有多少个极值元素。

输入格式

第一行包含整数 n。
第二行包含 n 个整数 a1, a2, …, an。

输出格式

一个整数，表示极值元素的数量。

输入样例

3
1 2 3

输出格式

0

数据范围

前 3
个测试点满足 1 ≤ n ≤ 5
。
所有测试点满足 1 ≤ n ≤ 1000
，1 ≤ ai ≤ 1000

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();

        for (int i = 1; i < n - 1; i++)
            if(arr[i] > arr[i + 1] && arr[i] > arr[i - 1] || arr[i] < arr[i + 1] && arr[i] < arr[i - 1]) res++;
        System.out.println(res);
    }
}

核心元素

题目描述

给定一个长度为 n 的整数数组 a1,a2,…,an，数组中的每个元素都是一个 1 ∼ n 之间的整数。
我们规定，数组中出现次数最多的元素为数组的核心元素，例如数组 [1,1,1,2,3] 的核心元素为 1 。
此外，如果数组中出现次数最多的元素不唯一，则出现次数最多的元素中数值最小的那个元素为数组的核心元素，例如数组 [1,2,2,3,3] 的核心元素为 2。
对于 1 ≤ i ≤ n 的每个整数 i，请你计算有多少个给定数组的非空连续子数组的核心元素为 i。

输入格式

第一行包含整数 n。
第二行包含 n 个整数 a1, a2, …, an。

输出格式

共一行，输出 n 个整数，其中第 i 个整数表示给定数组中核心元素为 i 的非空连续子数组的数量

输入样例

4
1 2 1 

输出样例

7 3 0 0

数据范围

前 3 个测试点满足 1 ≤ n ≤ 10。
所有测试点满足 1 ≤ n ≤ 5000，1 ≤ ai ≤ n。

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] cnt = new int[5001];
        int[] cunt1 = new int[n + 1];
        int[] arr = new int[n + n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = in.nextInt();
        }
        for (int i = n + 1; i < n + n; i++)
        {
            arr[i] = 0;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Arrays.fill(cnt,0);
                for (int k = j; k < i; k++)
                {
                    if(arr[k] != 0) cnt[arr[k]]++;
                }
                cunt1[findCore(cnt)]++;
            }
        }

        for (int i = 1; i < n + 1; i++)
        {
            System.out.print(cunt1[i] + " ");
        }
    }

    public static int findCore(int[] times)
    {
        int max = 0;
        int core = 0;

        for (int i = 0; i < times.length; i++)
        {
            if(times[i] > max)
            {
                max = times[i];
                core = i;
            }
        }

        return core;
    }
}

矩阵扩张

题目描述

给定一个 1×1 的方格矩阵，方格为白色：

你需要对该矩阵进行 k 次扩张操作，并输出最终得到的矩阵。
扩张操作的具体规则如下。
首先，给定一个 n × n 的方格矩阵，其中的每个方格要么是白色，要么是黑色，称此矩阵为模板矩阵。
在进行扩张操作时，当前矩阵中的每个方格都将扩张为一个 n × n 的方格矩阵，其中：

• 每个白色方格扩张得到的方格矩阵与模板矩阵相同。
• 每个黑色方格扩张得到的方格矩阵只包含黑色方格。

下面举例进行说明。
令 n = 2, k = 3，模板矩阵如下所示：

每一次扩张时，每个白色方格会扩张为

每一次扩张时，每个黑色方格会扩张为

第 1 次扩张后，得到一个 2 × 2 的方格矩阵：

第 2 次扩张后，得到一个 2^2 × 2^2 的方格矩阵：

第 3 次扩张后，得到一个 2^3 × 2^3 的方格矩阵：

这就是最终得到的矩阵。

输入格式

第一行包含两个整数 n, k 。
接下来 n 行，每行包含 n 个字符，每个字符要么为 . 要么为 * ,其中第 i 行第 j 个字符用来描述模板矩阵第 i 行第 j 列的方格颜色，. 表示白色， * 表示黑色。
保证模板矩阵中至少包含一个白色方格。

输出格式

输出一个 n^k × n^k 的字符矩阵，用来表示最终得到的矩阵。
. 表示白色方格，* 表示黑色方格

输入样例

2 3
.*
..

输出样例

.*******
..******
.*.*****
....****
.***.***
..**..**
.*.*.*.*
........

数据范围

所有测试点满足 2 ≤ n ≤ 3，1 ≤ k ≤ 5。

#include <stdio.h>
#define N 250
int main()
{
	int n, m;
	char p[N][N], a[N][N], b[N][N];

	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%c", &p[i][j]);
		}
	}

	int l = 1;
	a[0][0] = '.';
	
	for (int i = 0; i < m; i++)
	{
		for(int j = 0; j < l; j++)
			for(int k = 0; k < l; k++)
				for(int x = 0; x < n; x++)
					for (int y = 0; x < n; y++)
					{
						char c = '*';
						if (a[j][k] == '.') c = p[x][y];
						b[j * n + x][k * n + y] = c;
					}

		l*= n;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				b[i][j] = a[i][j];
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("%c", a[i][j]);
		}
	}
}