return_dr 2022-03-19 13:40 采纳率: 66.7%
浏览 10
已结题

深搜+剪枝,不知道为啥错了

https://www.luogu.com.cn/problem/P1092

#include <map>
#include <cmath>
#include <iostream>
#include <memory.h>
#define endl '\n'
using namespace std;

int n;
int jinwei[30];
char a[4][30];
bool f[30];
map<char, int> p[4];

void input()
{
    cin >> n;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    return;
}

void debug()
{
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << p[i][a[i][j]] << ' ';
        cout << endl;
    }
    cout << endl;

    return;
}

void fuzhi()
{
    for (int i = 2; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            p[i][a[i][j]] = p[1][a[i][j]];
    return;
}

// 调整函数
bool jianzhi()
{
    fuzhi();
    if (p[1][a[1][1]] + p[2][a[2][1]] >= n)
        return 1;
    for (int i = n; i >= 1; i--)
    {
        int js = p[1][a[1][i]], bjs = p[2][a[2][i]], he = p[3][a[3][i]];
        if (f[js] == 0 || f[bjs] == 0 || f[he] == 0)
            continue;
        if ((js + bjs) % n != he && (js + bjs + 1) % n != he)
            return 1;
    }
    return 0;
}

bool judge()
{
    memset(jinwei, 0, sizeof(jinwei));
    fuzhi();
    // debug();
    for (int i = n; i >= 1; i--)
    {
        if ((p[1][a[1][i]] + p[2][a[2][i]] + jinwei[i]) % n == (p[3][a[3][i]]) % n)
            jinwei[i - 1] = floor((p[1][a[1][i]] + p[2][a[2][i]] + jinwei[i]) / n);
        else
            return 0;
    }
    return 1;
}

void dfs(int x)
{
    if (jianzhi())
        return;
    if (x == n)
    {
        if (judge())
        {
            for (int i = 65; i <= 64 + n; i++)
                cout << p[1][char(i)] << ' ';
            exit(0);
        }
        else
            return;
    }
    for (int i = n; i >= x; i--)
        if (!f[i])
        {
            f[i] = 1;
            p[1][a[1][i]] = i;
            dfs(x + 1);
            p[1][a[1][i]] = -1;
            f[i] = 0;
        }
    return;
}

int main()
{
    // #ifndef ONLINE_JUDGE
    //     freopen("debug.txt", "w", stdout);
    // #endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    input();
    dfs(1);

    return 0;
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 3月27日
    • 创建了问题 3月19日

    悬赏问题

    • ¥20 WPF MVVM模式 handycontrol 框架, hc:SearchBar 控件 Text="{Binding NavMenusKeyWords}" 绑定取不到值
    • ¥15 需要手写数字信号处理Dsp三个简单题 不用太复杂
    • ¥15 数字信号处理考试111
    • ¥100 关于#audobe audition#的问题,如何解决?
    • ¥15 allegro17.2生成bom表是空白的
    • ¥15 请问一下怎么打通CAN通讯
    • ¥20 如何在 rocky9.4 部署 CDH6.3.2?
    • ¥35 navicat将excel中的数据导入mysql出错
    • ¥15 rt-thread线程切换的问题
    • ¥15 高通uboot 打印ubi init err 22