当前位置:网站首页>Blue Bridge Cup 2022 13th provincial competition real topic - block painting
Blue Bridge Cup 2022 13th provincial competition real topic - block painting
2022-07-07 01:43:00 【Choice~】
Write it at the front
I went online to search the solutions of other bloggers , Because I really can't understand d p [ i ] = d p [ i − 1 ] ⋅ 2 + d p [ i − 3 ] dp[i] = dp[i-1]\cdot2+dp[i-3] dp[i]=dp[i−1]⋅2+dp[i−3] How is this state transition equation obtained ( Maybe I'm too stupid ), Most of their explanations are cursory, and the ending is a little vague , As a vegetable dog, I'm really hard to understand ! After thinking for a long time, I came up with my own idea of solving this problem , It is different from the mainstream state transition equation on the Internet, but it can also solve problems .
Blue Bridge Cup 2022 True title of the 13th provincial competition in - Building block painting
The time limit : 1Sec Memory limit : 256MB Submit : 623 solve : 135
Title Description
Xiao Ming has recently become addicted to building block painting , There are two types of building blocks , Respectively I type ( The size is 2 Unit area ) and L type ( The size is 3 Unit area ):
meanwhile , Xiao Ming has an area of 2 × N Canvas of , Canvas by 2 × N individual 1 × 1 Regional composition . Xiao Ming needs to fill the canvas with the above two kinds of building blocks , He wanted to know how many different ways there were ? The building blocks can rotate freely , And the direction of the canvas is fixed .
Input
Enter an integer N, Represents the canvas size .
Output
Output an integer for the answer . Because the answer can be big , So output it to 1000000007 The value after taking the mold .
Sample input copy
3
Sample output copy
5
Tips
The five cases are shown in the figure below , The color is just to identify different building blocks :
For all test cases ,1 ≤ N ≤ 10000000.
Their thinking 1️⃣:
Ah , However, when it is a game, it is impossible to measure another data , What a pity , But the idea is right when writing , unfortunately a[2][1] Write the wrong .
Ideas :a[i][0]:i The stacking method of building blocks ,a[i][1]:i The stacking method of adding a small square .
Such as :
perhaps
No matter how these three pieces are put , All call a[3][0].
If there is a small square on the right on this basis, it is called a[3][1], Note that the small square can be one row above the fourth column or one row below the fourth column ( If it's hard to find the picture, I won't give it , Imagine for yourself )
The dynamic programming equation is given :
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;
Canvas size is i The arrangement of , Both a[i][0] Value :
- Consider one less piece first I The arrangement of type a building blocks , Both a[i-1][0], Then add a piece I Type block is OK ,
- Consider one less piece L The arrangement of type a building blocks , Both a[i-2][1], Then add a piece L Type block is OK ,
- Consider two less I The arrangement of type a building blocks , Both a[i-2][0], Add two I Type building blocks , Be careful , Two pieces must be added horizontally , If it's vertical , It is equivalent to the first type of arrangement , repeated .
- When it comes to missing more building blocks , You will find that no matter how you line up , The arrangement will repeat the above , in other words , The above three cases cover a[i][0] All the arrangements of .
So there is :
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
a[i][1] The arrangement of , You can draw and write by yourself .
Write the initial state :
a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;
Give the complete code :
#include<stdio.h>
#define mod 1000000007
long int a[10000001][2];
int main()
{
int n;
a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;
scanf("%d",&n);
if(n==1)printf("1");
else if(n==2)printf("2");
else {
for(int i=3;i<=n;i++){
a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;
}
printf("%ld",a[n][0]%mod);
}
return 0;
}
Disintegration thinking 2️⃣:
First of all, this problem must be done with dynamic programming , It is also in line with the idea of dynamic programming , No aftereffect is also satisfied, so we can do better with dynamic programming .
How do you think about this question , First, it is a two-dimensional matrix pattern , And there is arrangement or order , So if we want to use two dimensions dp It's really not easy to do it , Fortunately, we use one dimension to simplify the process of building blocks , But how to simplify it .
Let's first look at the case given by the topic :
First, let's look directly at the third order , The first and second we can find I There are ways to put the type-A building blocks together 2 Species , Or watch one or four , then L The splicing method of type a building blocks is 1 Look at three and five ( If you turn the two of them upside down, it's a kind of ), Then we might as well think simply, so the recursive formula is :dp[i]=dp[i-1]*2+dp[i-3];
The method of proof is the thought process we just had , We treat two-dimensional matrices as one-dimensional , therefore I Type a building block is equal to 1 A square , So we remember as i-1,L Type a building block is equal to 1.5 A square , however L Type a building block cannot appear alone , Must appear in pairs , So we remember as i-3, And because of I There are two ways for type a building blocks to appear in one position , So we multiply by two ,L The only way for a block to appear is to multiply it by 1, It's over .
But we still need to initialize the first three :
When i be equal to 1 When dp Namely 1, There's nothing to that , You can only put one I The type is the same no matter how you put it .
When i be equal to 2 When dp yes 2, Because you can put two I type , It can be placed horizontally or vertically 2 Kind of .
When i be equal to 3 It's the situation in the topic dp be equal to 5,
Reference code :
#include<stdio.h>
#include<string.h>
#define mod 1000000007
int dp[10000005];
int main()
{
int n;
scanf("%d",&n);
memset(dp,0,sizeof(dp));
dp[1]=1,dp[2]=2,dp[3]=5;
for(int i=4;i<=n;i++)
{
dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod;
}
printf("%d\n",dp[n]);
return 0;
}
Their thinking 3️⃣:
State means
The key to solving this problem is to use dynamic programming , Define a one-dimensional array d p dp dp , d p [ i ] dp[i] dp[i] The size of the storage canvas is 2 × i 2\times i 2×i The number of filling methods of building blocks .
State initialization
It's not hard to find out :
- When the canvas size is 2 × 1 2\times 1 2×1 when , Only one... Can be put down I Type building blocks , therefore d p [ 1 ] = 1 dp[1] =1 dp[1]=1.
When the canvas size is 2 × 2 2\times 2 2×2 when , Only two... Can be put down I Type building blocks , But the building blocks can rotate , As shown in the figure below , therefore d p [ 2 ] = 2 dp[2] = 2 dp[2]=2
When the canvas size is 2 × 3 2\times3 2×3 when , As shown in the title , There are five ways , therefore d p [ 3 ] = 5 dp[3] = 5 dp[3]=5
Situation combing
Before combing the state transition equation , Think about , There are only a few situations when the building block painting appears at the end and conforms to the meaning of the topic ?
Situation 1 : Use alone I Type building block splicing
It is entirely possible to use a separate Splice in the tail of any building block painting that conforms to the meaning of the topic , Make the building blocks draw the total length + 1.
Situation two : Use two I Type building block splicing
Use It can also be spliced to the tail of any building block painting that conforms to the meaning of the topic , Draw the total length of its building blocks + 2.
Situation three : Use two L Type building block splicing
Use or Splice to the tail of any building block that conforms to the meaning of the topic , Draw the total length of its building blocks +3, But note that there are two kinds of L The splicing methods of type a building blocks belong to different ways , Therefore, it needs to be calculated separately !
Situation four : Use two L Type building blocks and i ( 1 , 2 , 3 , . . . . n ) i(1,2,3,…n) i(1,2,3,…n) individual I Type building block splicing
The most easily overlooked situation ! Use I Type building blocks and Two L T-shaped building blocks can also complete splicing .
Don't forget what happens after the flip :
State transition equation
Situation 1 : Use alone I Type building block splicing , d p [ i ] + = d p [ i − 1 ] dp[i] += dp[i-1] dp[i]+=dp[i−1]
Situation two : Use two I Type building block splicing , d p [ i ] + = d p [ i − 2 ] dp[i]+=dp[i-2] dp[i]+=dp[i−2]
Situation three : Use two L Type building block splicing , d p [ i ] + = 2 ⋅ d p [ i − 3 ] dp[i]+=2\cdot dp[i-3] dp[i]+=2⋅dp[i−3]
Situation four : In case 4, there is only i > = 4 i>=4 i>=4 Only when , The specific discussion is as follows :
if i = = 4 i4 i4 , Only exist with a length of 4 The splicing of , hypothesis d p [ 0 ] = 1 dp[0]=1 dp[0]=1, in other words d p [ 4 ] + = d p [ 0 ] ⋅ 2 dp[4]+=dp[0]\cdot 2 dp[4]+=dp[0]⋅2
if i = = 5 i5 i5, The length of existence is 4 , 5 4,5 4,5 The splicing of , namely d p [ 5 ] + = ( d p [ 0 ] + d p [ 1 ] ) ⋅ 2 dp[5] += (dp[0]+dp[1])\cdot 2 dp[5]+=(dp[0]+dp[1])⋅2
if i = = 6 i 6 i6, Continue to deduce that there is : d p [ 6 ] + = ( d p [ 0 ] + d p [ 1 ] + d p [ 2 ] ) ⋅ 2 dp[6]+=(dp[0]+dp[1]+dp[2])\cdot 2 dp[6]+=(dp[0]+dp[1]+dp[2])⋅2
if i = = 7 i7 i7, Derivation has : d p [ 7 ] + = ( d p [ 0 ] + d p [ 1 ] + d p [ 2 ] + d p [ 3 ] ) ⋅ 2 dp[7]+=(dp[0]+dp[1]+dp[2]+dp[3])\cdot 2 dp[7]+=(dp[0]+dp[1]+dp[2]+dp[3])⋅2
According to the above derivation , It's not hard to find out d p [ i ] + = ( d p [ 0 , 1 , 2 , . . . , i − 4 ] ) ⋅ 2 dp[i]+=(dp[0,1,2,…,i-4])\cdot 2 dp[i]+=(dp[0,1,2,…,i−4])⋅2, So you can define a variable s u m sum sum Storage d p [ 0 , 1 , 2 , . . i ] dp[0,1,2,…i] dp[0,1,2,…i] Value , stay i i i Update while increasing s u m sum sum Value , The initial conditions s u m = 0 sum=0 sum=0.
Return results
Final d p [ N ] dp[N] dp[N] Is the value of the title , The problem was solved in this way .
We need to pay attention to : Only... Is used in the following code a 1 , a 2 , a 3 a1,a2,a3 a1,a2,a3 Represent the d p [ i − 1 ] , d p [ i − 2 ] , d p [ i − 3 ] dp[i-1],dp[i-2],dp[i-3] dp[i−1],dp[i−2],dp[i−3].
Code writing
#include <iostream>
#include <math.h>
#define ll long long
// #include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
ll n, a1, a2, a3;
a1 = 5;
a2 = 2;
a3 = 1;
cin >> n;
ll sum = 0;
for (ll i = 4; i <= n; ++i) {
ll val = 0;
val += a1;
val += a2;
val += (a3 * 2L);
if (i >= 4) {
val += sum * 2 + 2;
sum += a3;
}
val %= MOD;
a3 = a2;
a2 = a1;
a1 = val;
}
cout << a1;
return 0;
}
At the end 🧐
If you don't understand anything , You can comment or send me a private message ,
If it works for you , Just give this konjaku a good comment .
边栏推荐
- AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
- 云呐|工单管理办法,如何开展工单管理
- 454-百度面经1
- WCF Foundation
- Telnet,SSH1,SSH2,Telnet/SSL,Rlogin,Serial,TAPI,RAW
- What does front-end processor mean? What is the main function? What is the difference with fortress machine?
- Make Jar, Not War
- curl 命令
- Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
- JS Es5 can also create constants?
猜你喜欢
云呐|工单管理软件,工单管理软件APP
Appium automation test foundation uiautomatorviewer positioning tool
对C语言数组的再认识
域分析工具BloodHound的使用说明
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
Dark horse notes - create immutable sets and streams
Let's see how to realize BP neural network in Matlab toolbox
tansig和logsig的差异,为什么BP喜欢用tansig
C language - array
Yunna - work order management system and process, work order management specification
随机推荐
我如何编码8个小时而不会感到疲倦。
[signal and system]
Appium基础 — Appium Inspector定位工具(一)
Comparison of picture beds of free white whoring
Amway wave C2 tools
AcWing 345. 牛站 题解(floyd的性质、倍增)
C语言实例_5
LeetCode:1175. 质数排列
Make Jar, Not War
AcWing 1140. Shortest network (minimum spanning tree)
Can't you understand the code of linked list in C language? An article allows you to grasp the secondary pointer and deeply understand the various forms of parameter passing in the function parameter
黑马笔记---异常处理
Share a general compilation method of so dynamic library
Use nodejs to determine which projects are packaged + released
LeetCode:1175. Prime permutation
How to prevent overfitting in cross validation
js如何快速创建一个长度为 n 的数组
Dark horse notes - create immutable sets and streams
AcWing 1140. 最短网络 (最小生成树)
JS ES5也可以創建常量?