D. Walk on Matrix

7953 단어 비트 연산구조
D. Walk on Matrix

라벨

  • 구조

    • 제목의 뜻을 간단명료하게 밝히다.

  • 만약에 숫자 행렬이 있다고 가정하면 매번 아래로 또는 오른쪽으로 갈 수 있다. 왼쪽 상단에서 오른쪽 하단으로 가는 숫자와 가장 많은 숫자가 얼마냐고 물으면 이것은 분명히 dp이다.
  • 지금 너에게 숫자와 묻지 않고 경로의 모든 수를 &해라. 만약 dp가 틀렸다면.dp의 결과가 x라고 가정하면 정답은 y이다.
  • 현재 k를 정합니다. |y-x|=k
    • 를 만들 행렬을 만들어야 합니다.

    사고의 방향

  • 우선 우리는 언제 dp가 틀렸는지 생각한다.가설 행렬 중 하나의 점(x, y)이 10101이다.이때 최대 두 가지 선택이 (x-1, y) 또는 (x, y-1)에서 옮겨진다.다시 가설(x-1, y)은 10000이고 (x, y-1)은 101이며 다음과 같다
    •         ?    10000
       101   10101
  • 그러면 dp에서 (x-1, y) 위치의 10000을 선택하면 10000, (x, y-1) 위치의 101을 선택하면 101을 얻고, dp, (x, y)점에 따라 101이 아니라 10000을 선택한다.
  • 현재 행렬이 이렇다고 가정한다
    •         ?    10000    ?
       101   10101   100
  • 10101의 결과는 10000이고 100은 왼쪽을 선택할 때 0을 얻는다.만약 10101이 101을 선택해서 101을 얻었다면 마지막에 얻은 결과는 100이다.이를 통해 알 수 있듯이 dp는 더 높은 위치를 1로 하는 수를 우선적으로 선택할 것이다.
  • 우리는 dp의 이 약점을 잡아 dp의 결과는 0이고 정확한 결과는 k이다.이제 어떻게 구성할지 생각해 보자.
  • 위의 예에서 첫 줄의 세 번째 수를 0
    • 에 기입하면
           ?    10000    0
      101   10101   100
  • 그럼 왼쪽 상단 생각 안 하는 거?dp의 결과는 0이다.지금 어떻게 기입해야 할지 고려 중입니까?dp의 결과는 여전히 0이다.우리는 10000과 101을 이상으로 만들기만 하면 된다?값이 변하지 않으면 된다.분명히111111로 채워서 10000과 101이 변하지 않게 할 수 있습니다.
    •       10101   10000    0
       101    10101   100
  • 이런 행렬, dp의 답은 0.지금 우리는 어떻게 정답을 k로 할 것인가를 생각해 보자.분명히 여기는 왼쪽에서 오른쪽으로 세 개의 경로가 있는데 각각 
    • ____
     |              0
      ____
  
|             
|_______              0

________
        |             0
        |
  • 위에서 알 수 있듯이 우리는 두 번째 경로만 조작할 수 있고 두 번째 경로의 결과는 k이다.
  • 아까의 사고방식을 이용하여 우리는 k에 10···0(대형)을 더하여 어느 한 걸음에 10···0을 다르거나 큰 10···0을 잘못 선택할 수 있다.아래의 이 삼각형은 바로 10···0+k가 위의 것을 선택하면 10··0이 되고 왼쪽의 k를 선택하면 k가 된다.
    •        ?      10···0
       k      10···0+k
  • 그러면 우리는 처음에 예를 들어 생각한 것을 본떠서 계속 작성할 수 있다
    •       ?      10···0     0
      k      10···0+k   k
  • 이렇게 해서 두 가지 경로의 & 모두 0입니다. 우리는 지금 왼쪽 상단만 확인하면 됩니까?위의 예를 들면?1111··111로 채우면 됩니다.
  • 당연히 10···0+k도 채울 수 있는데, 가능하면?아래와 오른쪽의 수는 변하지 않으면 된다.
  • 10···0은 구체적으로 얼마인지에 대해 제목은 k<=1e5, 그럼 2117>1e5 2^{17}>1e5 217>1e5, 21172^{17}217을 쓰면 된다.왼쪽 상단에 218-302^{18}-1218-3-1을 채우면 된다(당연히 217+k2^{17}+k217+k도 가능하다).예: 
    •       2^18-1   2^17     0
      k        2^17+k   k
  • 여기 확장해 주세요. 제목에 행렬의 길이를 규정했기 때문에 우리가 구성해야 합니다.그러면 우리는 아래의 구조에 따라 
    •       2^18-1    0       0   0   0
      2^18-1    0       0   0   0
      2^18-1   2^17     0   0   0
      k        2^17+k   k   k   k

    세로로 000k, 가로로 1111000k로 채우면 된다.

    주의 사항

  • 없음

    • 총결산

  • 제목이 어떤 방식이 틀렸는지 알려주면 이런 방법이 어떤 상황에서 틀렸는지 생각해야 한다.

    • AC 코드

    #pragma GCC optimize(2)
#include
#include
#include
#include 
#include
#include
#include
#include	
#include
#include
#include
using namespace std;

const int maxn = 1000 + 10;

void solve()
{
	int k;
	cin >> k;
	cout << "2 3" << endl;
	cout << ((1 << 18)-1) << " " << (1 << 17) <<" " << "0" << endl;
	cout << k << " " << ((1 << 17) + k) << " " << k << endl;
}
	
int main()
{
	//freopen("Testin.txt", "r", stdin);
	solve();
	return 0;
}
    [프로그래머스/파이썬] (그래프) 가장 먼 노드
    Azure에서 SQL 연결 문자열의 사용자 이름과 암호를 관리하도록 합니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage