23年oppo提前批B组笔试真题-小欧的卡牌

小欧的卡牌

题目描述

小欧有 n 张卡牌,第 i 张卡牌的正面写了个数字 ai,背面写了个数字 bi。小欧对于每张卡牌可以选择一面向上,她希望最终向上的数字之和为 3 的倍数。你能告诉小欧有多少方案吗?由于答案过大,请对 10 ^ 9 + 7 取模.

输入描述

第一行输入一个正整数 n,代表卡牌数量。

接下来的 n 行,每行输入两个正整数 ai 和 bi,代表第 i 张卡牌的正面和背面的数字. 1 <= n <= 10^5 1 <= ai,bi <= 10^9

输出描述

一个整数,代表方案数对 10^9 + 7 取模的值

输入示例
3
1 2
2 3
3 2
输出示例
3

思路:

看起来比较唬人的一道题目,但是使用动态规划很容易解决

首先针对输入卡牌的值我们可以全部进行对3取模处理,因为实际上每个数对3取模后剩的数才会影响到最终和是否能整除3

然后采用动态规划。

动态规划三部曲:

dp数组的设计与具体含义:dp[i][j]代表从第一张到第i张卡牌数之和等于j的情况数

dp数组状态转移方程:dp[i][j] = dp[i-1][(j-card[i][0]+3)%3]+dp[i-1][(j-card[i][1]+3)%3] j属于{0,1,2}(card[i] [0]表示第i张正面的数,card[i] [1]表示第i张反面的数)

dp数组初始化: dp[0][0]=1,即第0张牌和为0的情况数为1

滚动数组优化:

由于i层dp数组的状态完全依赖于i-1层,与i-2、i-3等均无关,所以此处使用2层即可,具体看代码实现

import java.lang.*;
import java.util.*;
​
​
public class Main {
​
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] card = new int[n][2];
        for(int i = 0;i<n;i++){
            card[i][0] = in.nextInt()%3;
            card[i][1] = in.nextInt()%3;
        }
        int[][] dp = new int[2][3];
        dp[0][0] = 1;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<3;j++){
                dp[1][j] = (dp[0][(j-card[i][0]+3)%3] + dp[0][(j-card[i][1]+3)%3])%((int)1e9+7);
            }
            dp[0] = Arrays.copyOf(dp[1],3);
        }
        System.out.println(dp[1][0]);
    }
}

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 21:50:05       145 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 21:50:05       159 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 21:50:05       133 阅读
  4. Python语言-面向对象

    2024-07-20 21:50:05       145 阅读

热门阅读

  1. Django已经登录但是还是提示登录

    2024-07-20 21:50:05       29 阅读
  2. Go语言入门之函数

    2024-07-20 21:50:05       28 阅读
  3. swift小知识点

    2024-07-20 21:50:05       26 阅读
  4. 项目中MyBatis要引入的内容

    2024-07-20 21:50:05       30 阅读
  5. ccf-csp认证--仓库规划

    2024-07-20 21:50:05       28 阅读
  6. Kraken代码阅读(一)

    2024-07-20 21:50:05       24 阅读
  7. Oracle数据库 v$access

    2024-07-20 21:50:05       26 阅读
  8. ZooKeeper 部署

    2024-07-20 21:50:05       28 阅读
  9. 【Webpack】提高打包速度

    2024-07-20 21:50:05       28 阅读
  10. Python(re模块的具体使用)

    2024-07-20 21:50:05       32 阅读
  11. 2024 暑假友谊赛 2

    2024-07-20 21:50:05       29 阅读