2021年Robocom 复赛题解

题目

A: **题意:  给定三个数，要求变成另外三个数。有两个操作，①任选一个数 + 40,其他两个数 -20；②任选一个数 -40，其他两个数 +20. 输出最少的操作次数，无解输出-1.

思路: 直接bfs暴力骗分(bushi) ①衍化操作3.通过操作1和操作2，可以使得某个数+60，另一个数-60，剩余的不变。 ②判断可行解: 可以简化操作，都除以20，就变成+2,-1,-1.  首先满足差值之和为0，dx + dy + dz = 0.  而且差值都是20的倍数。  而且需要 %3 同余，因为 2 == -1,1 == -2(模 3) 然后还是不会做。看了官方题解。 因为dx + dy + dz = 0,所以必定是一正两负或者两正一负。可以通过取负号变成一正两负。 那么就有 a < b < 0 < c. 先执行操作2，会导致b先到达0，至少是同时到达.因为操作不会改变三者的和，仍然是0. 那么就剩下a和c需要变了。此时满足-a = c且都是3的倍数，有解，否则无解。  可以证明-a = c,因为操作过程中三者的和不变,a + b + c = 0,b = 0.  可以证明a和c都是3的倍数。因为a、b、c在操作时始终%3相等，所以当b = 0，a和c%3也 = 0，都是3的倍数。 时间复杂度: O(1),思维题 代码:**

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>a>>b>>c>>x>>y>>z;
    int t1 = a - x;
    int t2 = b - y;
    int t3 = c - z;
    if(t1 % 20 || t2 % 20 || t3 % 20 || t1+t2+t3 ) //预判
    {
    	cout