链接:http://www.codeforces.com/gym/100861/attachments/download/3976/20082009-acmicpc-neerc-moscow-subregional-contest-en.pdf

题意:给一个火柴棒的罗马不等式

你要移一根火柴,使得它变为等式

求所有方案,输出顺序任意

罗马数字规则不解释了..

注意字母之间有空格可以移过去当"I"或者"-"

注意II+I=+I

可以把"+"的横抽出来,放在原来+的右边,就是

II+I=III就成立了

这个东西,其实我觉得是画出来更好看规则...

大概是,可以把I和-拿走,也可以执行

+ 拿走变成 -或者I

L 可以拿走一根变成 I

= 可以拿走一根变成 -

当然,反之增加也是同理,增加I或者-,或者是上面反操作

当然,X可以变成V,V也能变成X

做法:

搜索哪个被拿掉,再放在某个位置

判定是否合法(写了个表达式求值)

然后特判好所有X<-->V即可

第二个AC,好开心呢

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[205];
vector<string> ans;
map<string,int> ma;
int n;
string build_string()
{
    string b;
    b.resize(n);
    int i;
    int sum=0;
    for (i=0;i<n;i++)
    {
        if (a[i]!=' ')
        {
            b[sum++]=a[i];
        }
    }
    b.resize(sum);
    return b;
}
int number(string a)
{
    if (ma.find(a)==ma.end())
    {
        return 0;
    }
    return ma[a];
}
string b;
int calc(int l,int r)
{
    int i;
    for (i=r-2;i>l;i--)
    {
        if (b[i]=='=')
        {
            return -999999999;
        }
        if (b[i]=='+')
        {
            int ans1=calc(l,i);
            if (ans1==-999999999) return -999999999;
            int ans2=number(b.substr(i+1,r-(i+1)));
            if (ans2==0) return -999999999;
            return ans1+ans2;
        }
        if (b[i]=='-')
        {
            int ans1=calc(l,i);
            if (ans1==-999999999) return -999999999;
            int ans2=number(b.substr(i+1,r-(i+1)));
            if (ans2==0) return -999999999;
            return ans1-ans2;
        }
    }
    int t=number(b.substr(l,r-l));
    if (t==0) return -999999999;
    return t;
}
void check()
{
    b=build_string();
    int i;
    for (i=0;i<b.length();i++)
    {
        if (b[i]=='=')
        {
            int t1=calc(0,i);
            if (t1==-999999999) return;
            int t2=calc(i+1,b.length());
            if (t2==-999999999) return;
            if (t1!=t2) return;
            ans.push_back(b);
            return;
        }
    }
}
void insert_one()
{
    int i;
    for (i=0;i<n;i++)
    {
        if (a[i]=='X') continue;
        if (a[i]=='L') continue;
        if (a[i]=='+') continue;
        if (a[i]=='V') continue;
        if (a[i]=='=') continue;
        if (a[i]=='-')
        {
            a[i]='+';
            check();
            a[i]='=';
            check();
            a[i]='-';
        }
        if (a[i]=='I')
        {
            a[i]='+';
            check();
            a[i]='L';
            check();
            a[i]='I';
        }
        if (a[i]==' ')
        {
            a[i]='I';
            check();
            a[i]='-';
            check();
            a[i]=' ';
        }
    }
}
void erase_one()
{
    int i;
    for (i=1;i<n;i+=2)
    {
        if (a[i]==' ') continue;
        if (a[i]=='X') continue;
        if (a[i]=='V') continue;
        if (a[i]=='-')
        {
            a[i]=' ';
            insert_one();
            a[i]='-';
        }
        if (a[i]=='I')
        {
            a[i]=' ';
            insert_one();
            a[i]='I';
        }
        if (a[i]=='L')
        {
            a[i]='I';
            insert_one();
            a[i]='L';
        }
        if (a[i]=='+')
        {
            a[i]='I';
            insert_one();
            a[i]='-';
            insert_one();
            a[i]='+';
        }
        if (a[i]=='=')
        {
            a[i]='-';
            insert_one();
            a[i]='=';
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ma["I"]=1;
    ma["II"]=2;
    ma["III"]=3;
    ma["IV"]=4;
    ma["V"]=5;
    ma["VI"]=6;
    ma["VII"]=7;
    ma["VIII"]=8;
    ma["IX"]=9;
    ma["X"]=10;
    ma["XI"]=11;
    ma["XII"]=12;
    ma["XIII"]=13;
    ma["XIV"]=14;
    ma["XV"]=15;
    ma["XVI"]=16;
    ma["XVII"]=17;
    ma["XVIII"]=18;
    ma["XIX"]=19;
    ma["XX"]=20;
    ma["XXI"]=21;
    ma["XXII"]=22;
    ma["XXIII"]=23;
    ma["XXIV"]=24;
    ma["XXV"]=25;
    ma["XXVI"]=26;
    ma["XXVII"]=27;
    ma["XXVIII"]=28;
    ma["XXIX"]=29;
    ma["XXX"]=30;
    ma["XXXI"]=31;
    ma["XXXII"]=32;
    ma["XXXIII"]=33;
    ma["XXXIV"]=34;
    ma["XXXV"]=35;
    ma["XXXVI"]=36;
    ma["XXXVII"]=37;
    ma["XXXVIII"]=38;
    ma["XXXIX"]=39;
    ma["XL"]=40;
    ma["XLI"]=41;
    ma["XLII"]=42;
    ma["XLIII"]=43;
    ma["XLIV"]=44;
    ma["XLV"]=45;
    ma["XLVI"]=46;
    ma["XLVII"]=47;
    ma["XLVIII"]=48;
    ma["XLIX"]=49;
    ma["L"]=50;
    ma["LI"]=51;
    ma["LII"]=52;
    ma["LIII"]=53;
    ma["LIV"]=54;
    ma["LV"]=55;
    ma["LVI"]=56;
    ma["LVII"]=57;
    ma["LVIII"]=58;
    ma["LIX"]=59;
    ma["LX"]=60;
    ma["LXI"]=61;
    ma["LXII"]=62;
    ma["LXIII"]=63;
    ma["LXIV"]=64;
    ma["LXV"]=65;
    ma["LXVI"]=66;
    ma["LXVII"]=67;
    ma["LXVIII"]=68;
    ma["LXIX"]=69;
    ma["LXX"]=70;
    ma["LXXI"]=71;
    ma["LXXII"]=72;
    ma["LXXIII"]=73;
    ma["LXXIV"]=74;
    ma["LXXV"]=75;
    ma["LXXVI"]=76;
    ma["LXXVII"]=77;
    ma["LXXVIII"]=78;
    ma["LXXIX"]=79;
    ma["LXXX"]=80;
    ma["LXXXI"]=81;
    ma["LXXXII"]=82;
    ma["LXXXIII"]=83;
    ma["LXXXIV"]=84;
    ma["LXXXV"]=85;
    ma["LXXXVI"]=86;
    ma["LXXXVII"]=87;
    ma["LXXXVIII"]=88;
    ma["LXXXIX"]=89;
    scanf("%s",a);
    int i;
    n=strlen(a);
    n*=2;
    n++;
    for (i=n/2-1;i>=0;i--)
    {
        a[i*2+1]=a[i];
    }
    for (i=0;i<=n;i+=2)
    {
        a[i]=' ';
    }
    erase_one();
    for (i=1;i<n;i+=2)
    {
        if (a[i]=='V')
        {
            a[i]='X';
            check();
            a[i]='V';
        }
        if (a[i]=='X')
        {
            a[i]='V';
            check();
            a[i]='X';
        }
    }
    sort(ans.begin(),ans.end());
    for (i=0;i<ans.size();i++)
    {
        if ((i==0)||(ans[i]!=ans[i-1]))
        {
            printf("%s\n",ans[i].c_str());
        }
    }
    return 0;
}