codeforces 1036B - Diagonal Walking v.2【思维+构造】

题意：起点(0,0)，终点(n,m)，走k步，可以走8个方向，问能不能走到，能走到的话最多能走多少个斜步。

解题思路：起点是固定的，我们主要分析终点。题目要求走最多的斜步，斜步很明显有一个性质就是不会改变n和m的相对奇偶性。就是走斜步的话，n和m要么+1要么-1，如果一开始n和m奇偶性不同，那么只走斜步最后奇偶性怎么都不会相同。因为起点始终是(0,0)，所以如果终点(n,m)的n和m奇偶性不同，那么肯定要走一个直步，而且只需要走一次直步。为什么只需要一次直步呢，我们可以随便画一条斜线，可以发现如果给一次走直步的机会，那么这条斜线上任意点的上下左右我们都可以到达。

也就是说，足够的斜步，可以让我们从(0,0)到达所有n与m奇偶性相同的点。再加上一个直步的话，就可以到达所有点了。而如果(n,m)本身奇偶性相同，但是与k不同，那么就是从起点到达(n,m)后，如果只走斜步，是没法刚好返回终点的。此时最优的方法就是把一个斜步化成两个直步，用来改变k与(n,m)的奇偶关系。

总结起来就是当n与m奇偶性不同的时候，--n,--k，否则--n,--m,k-=2。

判断k>=n是否成立，不成立说明走不到，成立直接输出k。

附ac代码：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn = 1e3 + 10;

 4 typedef long long ll;

 5 int nu[maxn][11];

 6 int ans[2][555];

 7 void sp(ll *a, ll *b)

 8 {

 9     *a = *a ^ *b;

10     *b = *a ^ *b;

11     *a = *a ^ *b;

12 }

13 int main()

14 {

15     int q;

16     scanf("%d", &q);

17     ll n, m, k;

18     while(q--)

19     {

20         scanf("%lld %lld %lld", &n, &m, &k);

21         if(n < m)

22         {

23             sp(&n, &m);

24         }

25        // printf("%lld %lld\n", n, m);

26         if((n&1) != (m&1))

27         {

28             --n;

29             --k;

30         }

31         else if((n&1) != (k&1))

32         {

33             n -= 1;

34             m -= 1;

35             k -= 2;

36         }

37         if(k >= n)

38         {

39             printf("%lld\n", k);

40         }

41         else

42         {

43             puts("-1");

44         }

45     }

46     return 0;

47 }

巴特西

codeforces 1036B - Diagonal Walking v.2【思维+构造】

最新文章

热门文章