8.15 柠檬微趣题目相当难

第一题九连环

#include <iostream>
#include <vector>
using namespace std;
void down(vector<bool> &arr, int n);
void up(vector<bool> &arr, int n){
    if(arr[n]) return ;
    if(n == 2 && !arr[1]){
        cout << "U1,2" << endl;
        arr[2] = true;
        arr[1] = true;
        return ;
    }
    up(arr, n-1);
    for(int i=n-2; i>0; i--) down(arr, i);
    cout << 'U' << n << endl;
    arr[n] = true;
}
void down(vector<bool> &arr, int n){
    if(!arr[n]) return ;
    up(arr, n-1);
    if(n == 2 && arr[1]){
        cout << "D1,2" << endl;
        arr[2] = false;
        arr[1] = false;
        return ;
    }
    for(int i=n-2; i>0; i--) down(arr, i);
    cout << 'D' << n << endl;
    arr[n] = false;
}
int main(){
    int num;
    cin >> num;
    vector<bool> arr(num+1, true);
    down(arr, num);
    for(int i=num-2; i>0; i-=2) up(arr, i);
    return 0;
}

第二题闯关

这一题最简单

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int player, n;
    cin >> player >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++){
        cin >> arr[i];
        arr[i] = player - arr[i];
    }
    int res = arr[0], left = 1, right = 1, sum = arr[0], l = 1;

    for(int i=1; i<n; i++){
        if(sum < 0) sum = arr[i], l = i+1;
        else sum += arr[i];
        if(sum > res){
            res = sum;
            left = l,
            right = i+1;
        }
    }
    cout << left << ' ' << right << ' ' << res << endl;
}

第三题九宫格

最后改出来了不知道能过多少

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
static vector<int> s_rgRightAnswer = {1, 2, 3, 4, 5, 6, 7, 8, 0};
static vector<int> s_rgBeginState = {};

const static char* DIRECTION_UP = "up";
const static char* DIRECTION_RIGHT = "right";
const static char* DIRECTION_DOWN = "down";
const static char* DIRECTION_LEFT = "left";

int dir_x[4] = {1, -1, 0, 0};
int dir_y[4] = {0, 0, 1, -1};
string st,en;
vector<string> res;
vector<string> direct{"down", "up", "right", "left"};

string getStr(vector<int>& arr){
    string str = "";
    for(auto &it:arr)
        str += '0' + it;
    return str;
}

void getAns(){
    if(st == en) return ;

    queue<string> que;
    que.push(st);
    unordered_map<string, vector<string>> hashMap;
    vector<string> tem;
    hashMap[st] = tem;

    while(!que.empty()){
        string cur = que.front();
        que.pop();
        int ind1 = cur.find('0');
        tem = hashMap[cur];

        for(int i=0; i<4; i++){
            int x = ind1 / 3 + dir_x[i];
            int y = ind1 % 3 + dir_y[i];
            int ind2 = x*3 + y;
            if(ind2 > 8 || ind2 < 0) continue;

            string temp(cur);

            swap(temp[ind1], temp[ind2]);
            if(hashMap.find(temp) != hashMap.end()) continue;

            tem.push_back(direct[i]);
            hashMap[temp] = tem;

            if(temp == en){
                res = tem;
                return ;
            };
            que.push(temp);
        }
    }

}

void printResult(vector<string> rgDirections)
{
    for (string direction : rgDirections)
    {
        cout << direction << endl;
    }
}

int main(int argc, const char * argv[])
{
    int x;
    while (s_rgBeginState.size() != 9)
    {
        cin >> x;
        s_rgBeginState.push_back(x);
    }
    st = getStr(s_rgBeginState);
    en = getStr(s_rgRightAnswer);
    vector<string> tem;
    getAns();
    printResult(res);
    return 0;
}