原題
A. Sorting with Twos
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array of integers?𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,��. In one operation, you do the following:
- Choose a non-negative integer?𝑚�, such that?2𝑚≤𝑛2�≤�.
- Subtract?11?from?𝑎𝑖��?for all integers?𝑖�, such that?1≤𝑖≤2𝑚1≤�≤2�.
Can you sort the array in non-decreasing order by performing some number (possibly zero) of operations?
An array is considered non-decreasing if?𝑎𝑖≤𝑎𝑖+1��≤��+1?for all integers?𝑖�?such that?1≤𝑖≤𝑛?11≤�≤�?1.
Input
The first line contains a single integer?𝑡�?(1≤𝑡≤1041≤�≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer?𝑛�?(1≤𝑛≤201≤�≤20) — the length of array?𝑎�.
The second line of each test case contains?𝑛�?integers?𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,��?— the integers in array?𝑎�?(0≤𝑎𝑖≤10000≤��≤1000).
Output
For each test case, output "YES" if the array can be sorted, and "NO" otherwise.
Example
input
Copy
8
5
1 2 3 4 5
5
6 5 3 4 4
9
6 5 5 7 5 6 6 8 7
4
4 3 2 1
6
2 2 4 5 3 2
8
1 3 17 19 27 57 179 13
5
3 17 57 179 92
10
1 2 3 4 0 6 7 8 9 10
output
Copy
YES YES YES NO NO NO YES YES
Note
In the first test case, the array is already sorted in non-decreasing order, so we don't have to perform any operations.
In the second test case, we can choose?𝑚=1�=1?twice to get the array?[4,3,3,4,4][4,3,3,4,4]. Then, we can choose?𝑚=0�=0?once and get the sorted in non-decreasing order array?[3,3,3,4,4][3,3,3,4,4].
In the third test case, we can choose?𝑚=0�=0?once and get the array?[5,5,5,7,5,6,6,8,7][5,5,5,7,5,6,6,8,7]. Then, we can choose?𝑚=2�=2?twice and get the array?[3,3,3,5,5,6,6,8,7][3,3,3,5,5,6,6,8,7]. After that, we can choose?𝑚=3�=3?once and get the sorted in non-decreasing order array?[2,2,2,4,4,5,5,7,7][2,2,2,4,4,5,5,7,7].
For the fourth and fifth test case, it can be shown that the array could not be sorted using these operations.
原題鏈接
傳送門?
代碼
#include<bits/stdc++.h>
using namespace std;int a[30];int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);bool flag=true;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){if(a[i-1]>a[i]&&i!=2&&i!=3&&i!=5&&i!=9&&i!=17){flag=false;break;}}if(flag==true) puts("Yes");else puts("No");memset(a,0,sizeof a);}return 0;
}總結
1.題目的意思是說，輸入一個數列，詢問我們能否經過一定的操作把該數列修改成一個非嚴格的升序數列
2.操作的具體步驟是，首先選擇一個非負的整數m，使得2^m<=n，n表示的是數列的長度，然后對數列里面1~2^m個元素，每一個元素進行減一的操作
3.如果可以得到非嚴格的上升序列，就輸出yes,否則輸出no
4.n的最大值是20，滿足條件的2的整數次冪是，1，2，4，8，16，可以發現如果超過可以修改的范圍的降序部分，就一定不能經過修改達到要求，此時輸出no
5.事實上，經過觀察可以發現，只要不是2的整數次冪數字作為下標對應的元素大于下一個元素，就無法實現修改，比如說給定一個數列，1 2 3 2 5，第三個數字3對應的下標是3（假設下標從1開始使用），下標3不是2的整數次冪，元素3大于下一個元素2，我們不能割裂的對元素3進行修改，假設我們要修改元素3，就一定會同時修改元素2，元素3和元素2之間的相對大小關系沒有發生改變（這里說的元素2指的是下標為4的元素2）?
6.根據上面的描述，使用循環進行條件判斷即可，注意a數組是全局變量，沒有使用的空間的數值都是0，a數組每使用一次都需要初始化一次，防止上一次輸入的數據對當前產生影響
