加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

解析表达式语法

发布时间:2020-12-15 07:33:41 所属栏目:Java 来源:网络整理
导读:解析表达式语法 [ made by Ameiyo ] 说白了就是暴力。 A: CF778B - Bitwise Formula B: CF552E - Vanya and Brackets C: CF39A - C*++ Calculations D: CF89B - Widget Library E: CF7E - Defining Macros F: CF217C - Formurosa G: CF172E - BHTML+BC

解析表达式语法

[ made by Ameiyo ]


说白了就是暴力。


A: CF778B - Bitwise Formula

B: CF552E - Vanya and Brackets

C: CF39A - C*++ Calculations

D: CF89B - Widget Library

E: CF7E - Defining Macros

F: CF217C - Formurosa

G: CF172E - BHTML+BCSS

H: CF115D - Unambiguous Arithmetic Expression

I: CF582E - Boolean Function


A

每一位都是独立的,对每一位单独考虑。枚举问号是 0 或 1,按顺序模拟得到两个情况下 1 的个数,分情况给两个答案赋值即可。

重点还是在模拟。

#include <cstdio>
#include <cctype>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,a,b) for (reg int i = (a),i##end = (b); i <= i##end; ++i)
#define dep(i,i##end = (b); i >= i##end; --i)

template <typename _typer> inline _typer read() {
    _typer init = 0;
    char ch = getchar(),k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 5005,INF = 1e9;
const ll M = 1005;

/*******************************************************************************
 *
 * 按位枚举每一位,让每一位的 1 最少/多
 *
 ******************************************************************************/


int n,m;
int val[N][M],Ansmin[M],Ansmax[M];
int opt[N],a[N],b[N];
// ? - 0

map < string,int > mp;


int Query(int id,int vl) {
    val[0][id] = vl;
    int cnt = 0;
    rep (i,1,n) if (opt[i] != -1) {
        if (opt[i] == 0) val[i][id] = val[a[i]][id] & val[b[i]][id];
        else if (opt[i] == 1) val[i][id] = val[a[i]][id] | val[b[i]][id];
        else if (opt[i] == 2) val[i][id] = val[a[i]][id] ^ val[b[i]][id];
        cnt += val[i][id];
    }
    return cnt;
}

void Solve() {
    rep (i,m) {
        int cnt0 = Query(i,0),cnt1 = Query(i,1);
//         cerr << i << " " << cnt0 << " " << cnt1 << endl;
        if (cnt0 < cnt1) Ansmin[i] = 0,Ansmax[i] = 1;
        else if (cnt0 > cnt1) Ansmin[i] = 1,Ansmax[i] = 0;
        else Ansmin[i] = Ansmax[i] = 0;
    }
}


int main() {
    n = read<int>(),m = read<int>();
    string name,name1,nameopt,name2;
    rep (i,n) {
        cin >> name;
        mp[name] = i;
        cin >> name >> name1;
        if (isdigit(name1[0])) {
            opt[i] = -1;
            rep (j,m) val[i][j] = (name1[j - 1] ^ 48);
            continue;
        }
        cin >> nameopt >> name2;
        if (nameopt == "AND") opt[i] = 0;
        else if (nameopt == "OR") opt[i] = 1;
        else if (nameopt == "XOR") opt[i] = 2;
        if (name1 == "?") a[i] = 0;
        else a[i] = mp[name1];
        if (name2 == "?") b[i] = 0;
        else b[i] = mp[name2];
    }

    Solve();

    rep (i,m) printf("%d",Ansmin[i]);
    puts("");
    rep (i,Ansmax[i]);
    puts("");
    return 0;
}

B

首先括号肯定是加在两个乘号之间才能使答案更大,枚举这个区间,然后就是一遍只有两个符号的模拟了。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,INF = 1e9;

/*******************************************************************************
 *
 * 枚举两个 * 号,把他们中间的括起来
 * 开头和结尾可以加哨兵
 *
 ******************************************************************************/


int n;
char s[N];
int id[N],tot;

ll Stk[N << 1],Top;
ll Solve(int l,int r) {
    int cnt = 0;
    Top = 0;
    rep (i,n) {
        if (i == l + 1) {
            Stk[++Top] = -1;
        }
        if (s[i] == '*') Stk[++Top] = -2;
        else if (s[i] == '+') ++cnt;
        else {
            Stk[++Top] = (s[i] ^ 48);
        }
        if (i == r - 1) {
            for ( ; Stk[Top - 1] != -1 && Top && cnt; --Top,--cnt)
                Stk[Top - 1] = Stk[Top - 1] + Stk[Top];
            Stk[Top - 1] = Stk[Top],--Top;
        }
        if (Stk[Top - 1] == -2 && Stk[Top] >= 0)
            Stk[Top - 2] = Stk[Top - 2] * Stk[Top],Top -= 2;
    }
    for ( ; Top && cnt; --Top,--cnt)
        Stk[Top - 1] = Stk[Top - 1] + Stk[Top];
//     cerr << l << " " << r << " " << Stk[1] << endl;
    return Stk[1];
}


int main() {
    scanf("%s",s + 1);
    n = strlen(s + 1);
    id[tot = 1] = 0;
    rep (i,n) if (s[i] == '*') id[++tot] = i;
    id[++tot] = n + 1;

    ll Ans = 0;
    rep (i,tot) rep (j,i + 1,tot)
        Ans = max(Ans,Solve(id[i],id[j]));

    printf("%lldn",Ans);
    return 0;
}

C

把所有的 summand 提取出来,每个前面肯定有一个系数,一个贪心,系数越小的在前面,与 前置或后置 无关。

注意提取的时候前面的两个 + 必须是没有被使用过得,否则会被 hack

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 10005,INF = 1e9;

/*******************************************************************************
 *
 * 把单独的 a 变成系数为 1 的乘法
 * 所有的乘法按照系数从小到大计算(有负数)
 *
 ******************************************************************************/


#define int ll


int a,n,mark[N];
char s[N];

int tot;
struct NODE {
    int mul,opt;
    inline int operator < (const NODE &__) const {
        return mul < __.mul;
    }
} node[N];


int Solve() {
    sort(node + 1,node + tot + 1);
    int ans = 0;
    rep (i,tot) {
        if (node[i].opt == 0) ++a;
        ans += node[i].mul * a;
        if (node[i].opt == 1) ++a;
    }
    return ans;
}


signed main() {
    a = read<int>();
    scanf("%s",s + 1);
    n = strlen(s + 1);
    rep (i,n) if (s[i] == 'a') {
        ++tot;
        if (s[i - 1] == '+' && s[i - 2] == '+' && !mark[i - 2]) {
            node[tot].opt = 0;
            mark[i] = mark[i - 1] = mark[i - 2] = true;
            if (s[i - 3] != '*') {
                node[tot].mul = (s[i - 3] == '-' ? -1 : 1);
                continue;
            }
            int cur = i - 4,k = 1,init = 0;
            for ( ; cur > 0 && isdigit(s[cur]); --cur) ;
            if (s[cur] == '-') k = -1;
            rep (j,cur + 1,i - 4) init = init * 10 + (s[j] - '0');
            node[tot].mul = init * k;
        } else if (s[i + 1] == '+' && s[i + 2] == '+') {
            node[tot].opt = 1;
            mark[i] = mark[i + 1] = mark[i + 2] = true;
            if (s[i - 1] != '*') {
                node[tot].mul = (s[i - 1] == '-' ? -1 : 1);
                continue;
            }
            int cur = i - 2,i - 2) init = init * 10 + (s[j] - '0');
            node[tot].mul = init * k;
        }
    }

    printf("%lldn",Solve());
    return 0;
}

D

其实题目就是这个意思

Widget [name] ([x],[y])
宽 x,高 y,名字 name

HBox [name]
创建横向打包器

VBox [name]
创建纵向打包器

[name1].pack([name2])
把 name2 丢到 name1 里

[name].set_border([x])
设置 border

[name].set_spacing([x])
设置 spacing

HBox:
2 * border + (cnt - 1) * spacing + Sigma(Width)
2 * border + max(Height)

VBox:
2 * border + max(Width)
2 * border + (cnt - 1) * spacing + Sigma(Height)

最后两组式子可以通过试样例试出来。

然后就是模拟。注意所有的变量都会随时改变,所以要建出一个关系最后更新一遍。

#include <cstdio>
#include <cctype>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 105,INF = 1e9;

/*******************************************************************************
 *
 * 大模拟
 *
 ******************************************************************************/


int n,In[N];
struct EDGE {
    int to,nex;
} edge[N];
int head[N],cntedge;
void Addedge(int u,int v) {
    edge[++cntedge] = (EDGE) { v,head[u] };
    head[u] = cntedge,++In[v];
}

map < string,int > mp;
string name[N];

int tot;
struct Widget {
    char opt;
    int cnt;
    ll border,spacing;
    ll SumWson,SumHson;
    ll MaxWson,MaxHson;
    ll Width,Height;
    void Calc() {
        if (opt == 'W') return ;
        if (!cnt) return (void) (Width = Height = 0);
        if (opt == 'H') {
            Width = 2 * border + (cnt - 1) * spacing + SumWson;
            Height = 2 * border + MaxHson;
        } else if (opt == 'V') {
            Width = 2 * border + MaxWson;
            Height = 2 * border + (cnt - 1) * spacing + SumHson;
        }
    }
    void Pushup(const Widget son) {
        ++cnt;
        SumWson += son.Width;
        SumHson += son.Height;
        MaxWson = max(MaxWson,son.Width);
        MaxHson = max(MaxHson,son.Height);
        Calc();
    }
    void SetBorder(ll x) { border = x; }
    void SetSpacing(ll x) { spacing = x; }
} node[N];

void Widget() {
    string s;
    cin >> s;
    int len = s.length(),id = 0;
    string name = "";
    rep (i,len - 1) {
        if (s[i] == '(') {
            id = i;
            break;
        }
        name += s[i];
    }
    ::name[mp[name] = ++tot] = name;
    int x = 0,y = 0;
    rep (i,id + 1,len - 1) {
        if (s[i] == ',') {
            id = i;
            break;
        }
        x = x * 10 + s[i] - '0';
    }
    rep (i,len - 1) {
        if (s[i] == ')') {
            id = i;
            break;
        }
        y = y * 10 + s[i] - '0';
    }
    node[tot].Width = x,node[tot].Height = y;
    node[tot].opt = 'W';
//     cerr << name << " " << node[tot].Width << " " << node[tot].Height << endl;
}
void HBox() {
    string name;
    cin >> name;
    ::name[mp[name] = ++tot] = name;
    node[tot].opt = 'H';
}
void VBox() {
    string name;
    cin >> name;
    ::name[mp[name] = ++tot] = name;
    node[tot].opt = 'V';
}


void Set(string s) {
    string name = "",ord = "";
    int len = s.length(),id;
    rep (i,len - 1) {
        if (s[i] == '.') {
            id = i;
            break;
        }
        name += s[i];
    }
    int idv = mp[name];
    rep (i,len - 1) {
        if (s[i] == '(') {
            id = i;
            break;
        }
        ord += s[i];
    }
    if (ord == "pack") {
        name = "";
        rep (i,len - 1) {
            if (s[i] == ')') {
                id = i;
                break;
            }
            name += s[i];
        }
        int idu = mp[name];
        Addedge(idu,idv);
    } else {
        int x = 0;
        rep (i,len - 1) {
            if (s[i] == ')') {
                id = i;
                break;
            }
            x = x * 10 + s[i] - '0';
        }
        if (ord == "set_border") node[idv].border = x;
        else if (ord == "set_spacing") node[idv].spacing = x;
    }
}

void Solve() {
    int Q[N],l,r;
    l = r = 0;
    rep (i,tot) if (!In[i]) Q[++r] = i;
    while (l < r) {
        int u = Q[++l];
        for (int i = head[u],v; i; i = edge[i].nex) {
            v = edge[i].to;
            node[v].Pushup(node[u]);
            if (!(--In[v])) Q[++r] = v;
        }
    }
}

int main() {
    n = read<int>();
    rep (i,n) {
        string order;
        cin >> order;
        if (order == "Widget") Widget();
        else if (order == "HBox") HBox();
        else if (order == "VBox") VBox();
        else Set(order);
    }

    Solve();

    sort(name + 1,name + tot + 1);
    rep (i,tot)
        cout << name[i] << " " << node[mp[name[i]]].Width << " "
        << node[mp[name[i]]].Height << endl;
    return 0;
}

E

其实也是模拟,但是有一些性质。

下面定义不安全为 没有被一对括号括起来

  1. 如果一个宏不可行,那么包含他的宏也不可行。
  2. 如果一个 / 后面有不安全的运算符,那么当前宏不可行。
  3. 如果一个 - 后面有不安全的低级运算符,那么当前宏不可行。
  4. 如果一个 * 后面有不安全的低级运算符,那么当前宏不可行。

每个宏有三个变量,分别表示 是否可行是否有不安全的运算符是否有不安全的低级运算符

在输入的时候依次处理出每个宏,最后对输入做一次相同的判断得到是否合法。

一种比较简单粗暴的方法是把整个式子中缀转后缀,然后直接暴力搞,因为只有符号 + 宏会引起歧义。

但是这样的话不安全就只能在最外层判,因为转后缀后就不清楚是否有括号。

这样打代码比较长,但是基本没有思维难度。

#include <cstdio>
#include <cctype>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,INF = 1e9;
const ll M = 1005;

int tot;
struct NODE {
    int save,opr,dop;
} node[N];

string name[N];
map < string,int > mp;
map < int,int > dep;

int OPRTPINT[M],Opr[] = { '+','-','*','/' };
int chkOpr(char ch) {
    rep (i,3) if (Opr[i] == ch) return true;
    return false;
}


int n,debug;

string getName(string &s,int &cur,int len) {
    string name = "";
    rep (i,cur,len - 1) {
        if (!isdigit(s[i]) && !isalpha(s[i])) {
            cur = i - 1;
            break;
        }
        name += s[i];
        if (i == len - 1) cur = len;
    }
    return name;
}


int cntele,cntli,cntnbl,Top;
NODE ele[M],Stk[M];
int li[M],nbl[M],stk[M];
int Change(int l,int r) {
    if (li[l + 1] == -6 && li[l] >= 0) {
        int id = li[l];
        nbl[++cntnbl] = id;
        ele[id].opr = ele[id].dop = false;
        return l + 1;
    }
    int id = l;
    rep (i,r) {
        id = i;
        if (li[i] == -6) break;
        if (li[i] >= 0) {
            nbl[++cntnbl] = li[i];
            continue;
        }
        if (li[i] == -5) {
            i = Change(i + 1,r);
            continue;
        }
        while (Top && stk[Top] >= l && dep[li[stk[Top]]] >= dep[li[i]])
            nbl[++cntnbl] = li[stk[Top]],--Top;
        stk[++Top] = i;
    }
    while (Top && stk[Top] >= l) nbl[++cntnbl] = li[stk[Top]],--Top;
    return id;
}
NODE Get(NODE A,NODE B,int opr) {
    NODE Ans;
    Ans.save = A.save & B.save;
    if (opr == -1 && B.opr) Ans.save = false;
    if (opr == -3 && B.dop) Ans.save = false;
    if (opr == -2 || opr == -1) {
        if (A.dop || B.dop) Ans.save = false;
    }
    Ans.opr = Ans.dop = false;
    return Ans;
}
void CheckLi(int num) {
    Top = 0;
    Change(1,cntli);
    Top = 0;
    rep (i,cntnbl) {
        if (nbl[i] > 0) Stk[++Top] = ele[nbl[i]];
        else Stk[Top - 1] = Get(Stk[Top - 1],Stk[Top],nbl[i]),--Top;
    }
    node[num] = Stk[1];
}
int isch(char ch) { return isdigit(ch) || isalpha(ch); }
void Get(string s,int num) {
    cntli = cntnbl = cntele = 0;
    int len = s.length(),id = -1,flag = false;
    string now = "";
    rep (i,len - 1) if (s[i] != ' ') now += s[i];
    swap(now,s);
    len = s.length();
    if (s[0] == '(') {
        int cnt = 0;
        rep (i,len - 1) {
            if (s[i] == '(') ++cnt;
            else if (s[i] == ')') {
                if (cnt) --cnt;
                else if (i == len - 1) flag = true;
            }
        }
        if (flag) {
            now = "",id = -1;
            rep (i,len - 2) now += s[i];
            swap(now,s);
            len = s.length();
        }
    }
    for (int i = 0; i < len; ++i) {
        if (isch(s[i])) {
            string name = getName(s,i,len);
            if (mp.count(name)) id = mp[name];
            else id = 0;
            li[++cntli] = ++cntele;
            ele[cntele] = node[id];
        } else li[++cntli] = OPRTPINT[(int) s[i]];
    }
    CheckLi(num);
    int cnt = 0;
    rep (i,cntli) {
        if (li[i] == ')') --cnt;
        else if (li[i] == '(') ++cnt;
        if (cnt) continue;
        if (li[i] > -5 && li[i] < 0) node[num].opr = true;
        if (li[i] > -5 && li[i] < -2) node[num].dop = true;
    }
    if (flag) node[num].opr = node[num].dop = false;
}


int main() {

    node[0].save = true;
    rep (i,3) OPRTPINT[Opr[i]] = i - 4;
    OPRTPINT[(int) '('] = -5,OPRTPINT[(int) ')'] = -6;

    dep[-1] = dep[-2] = 2,dep[-3] = dep[-4] = 1;

    n = read<int>();
    rep (i,n) {
        string define;
        cin >> define;
        if (define == "#") cin >> define;
        string name;
        cin >> name;
        ::name[mp[name] = i] = name;
        string txt;
        getline(cin,txt);
        Get(txt,i);
    }

//     rep (i,n)
//         cerr << node[i].save << " " << node[i].opr << " " << node[i].dop << endl;

    string txt;
    getline(cin,txt);
    Get(txt,n + 1);

    string Ans = node[n + 1].save ? "OK" : "Suspicious";
    cout << Ans << endl;
    return 0;
}

F

这其实是一道 DP ,一开始思路挺乱的,有点接近正解,但还是差了些。

假设最后的值是 $ f(s) $ , $ s $ 是每个 $ ? $ 的一组取值,那么只要存在一组 $ s $ 与 $ s‘ $ 满足二者至少有一个 $ ? $ 的取值不一样,而且 $ f(s) neq ?f(s‘) $ 我们就可以确定出这个 $ ? $ 在 $ s $ 时的值。

证明:

对于这部分表达式来说,因为 $ f(s) neq f(s‘) $ ,所以元素值的变化会反应在结果上,具体的操作就是我们尝试改变某个(或几个)值,结果发现函数值改变了,因为我们时可以知道函数值的,从而就可以推断出改变的方向。

反之,如果不存在,那么无论怎么改变,我们都不知道前后的元素的值是否相同,也就不能判断值了。

但是对于异或操作来说,我们可以得知的只有一个表达式的值是否改变,而不是从 $ 0 -> 1 $ 或 $ 1 -> 0 $ ,但如果确定了某一个是 $ 0 / 1 $ ,那么这个值就可以确定了。

所以对于每一组括号,我们 DP 出这组括号的情况:

  1. 是否存在 $ s $ 使 $ f(s) = 0 $ 且 $ f(s‘) = 0 $ .
  2. 是否存在 $ s $ 使 $ f(s) = 1 $ 且 $ f(s‘) = 1 $ .
  3. 是否存在 $ s $ 使 $ f(s) neq f(s‘) $ .

回到题目,因为两种值都至少存在一个,所以我们就把不同的元素不断的放到那个位置上,直到值的改变,然后确定剩下的值。

然后就有了 $ 27 $ 种转移 ( 3 种值 3 种符号) 。这里提供一种比较简洁的做法,借鉴自 Alex_McAvoy 网友的博客.

int Get(int x,int y,int opr) {
    if (opr == '|') return x | y;
    else if (opr == '&') return x & y;
    else if (opr == '^') return x ^ y;
    return 0;
}

int Work() {
    int opr = getchar();
    if (opr == '(') {
        int ls = Work();
        int opr = getchar();
        int rs = Work(),ans = 0;
        getchar();
        rep (i,3) if (ls & (1 << i))
            rep (j,3) if (rs & (1 << j))
                ans |= (1 << Get(i,j,opr));
        return ans;
    } else {
        if (opr == '1') return 8;
        else if (opr == '0') return 1;
        else return 6;
    }
}

int main() {
    read<int>();
    if (Work() & 6) puts("YES");
    else puts("NO");
    return 0;
}

G

一开始题目看错淦了好久。。。

简单的说,给出一棵树,对于每个询问输出有多少根到节点的路径满足条件。

一条路径满足条件当且仅当:

  1. 路径的最后一个节点与给定字符串的最后一个字符相同。
  2. 给定字符串是路径所组成字符串的子序列。

那么把树建出来后直接每个询问去跑就行了, Dfs 的参数中把 从根到当前节点 能匹配到的最大下标 传进去就可以了。

#include <cstdio>
#include <cctype>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 250005,INF = 1e9;
const ll M = 205;

string s;

int tot,node[N];
struct EDGE {
    int to,nex;
} edge[N << 1];
int head[N],head[u] };
    head[u] = cntedge;
}


map < string,int > mp;


int Stk[N],Top;
void Get(int &cur,int r) {
    string tmp = "";
    int flagCloseSelf = false,flagClose = false;
    if (s[cur] == '/') flagClose = true,++cur;
    rep (i,r) {
        cur = i;
        if (s[i] == '>') break;
        if (s[i] == '/') flagCloseSelf = true;
        else tmp += s[i];
    }
//     cerr << tmp << " " ;
    if (flagClose) {
        --Top;
    } else {
        if (mp.count(tmp)) node[++tot] = mp[tmp];
        else node[++tot] = 0;
//         cerr << tot << " " << node[tot] ;
        Addedge(Stk[Top],tot);
        if (!flagCloseSelf) Stk[++Top] = tot;
    }
//     cerr << endl;
}
void Change() {
    int len = s.length();
    for (int i = 0; i < len; ++i) {
        if (s[i] == '<') {
            int cur = i + 1;
            Get(cur,len - 1);
            i = cur;
        }
    }
}


int li[M][M],m,Ans;
void Dfs(int u,int *li,int cur) {
//     cerr << u << " " << node[u] << endl;
    if (node[u] == li[cur + 1]) ++cur;
    if (cur == li[0] && node[u] == li[cur]) ++Ans;
    for (int i = head[u],v; i; i = edge[i].nex) {
        v = edge[i].to;
        Dfs(v,li,cur);
    }
}
void Work() {
    rep (ks,m) {
        Ans = 0;
        for (int i = head[0],v; i; i = edge[i].nex) {
            v = edge[i].to;
            Dfs(v,li[ks],0);
        }
        printf("%dn",Ans);
    }
}


int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    int cnt = 0;
    cin >> s >> m;

    rep (i,m) {
        string now,tmp;
        getline(cin,now);
        while (!now.length()) getline(cin,now);
        now += ' ';
        int len = now.length();
        rep (j,len - 1) {
            if (now[j] == ' ') {
                if (!mp.count(tmp)) mp[tmp] = ++cnt;
                li[i][++li[i][0]] = mp[tmp];
                tmp = "";
                continue;
            }
            tmp += now[j];
        }
    }
    Change();

    Work();

    return 0;
}

H

其实是一个挺简单的 DP ,一开始打 区间 DP T 死我了。

仔细观察题目,可以发现原来多项式的方案数其实就是加括号的方案数。

令 $ f[i][j] $ 表示前 $ i $ 个位置,还有 $ j $ 个左括号没有匹配右括号 的方案数。

考虑两种情况:

  1. 这一位是符号,下一位是数字。

    由于每个符号所影响的两部分是必须用括号包裹的,所以这个符号的左括号只有一个选择,就是在对应的地方。

    而在下一个数字的后面,我们可以加上任意数量的右括号,只要左括号允许。因为可以把后面的数字留给后面的符号用,所以也可以不加右括号。

    所以这一步就是 $ f[i][j] = sum f[lst][k] (k ge j - 1) $ 。

  2. 这一位是符号,下一位是 +-

    首先,对于当前的符号来说,同样只能在也必须在一个确定的地方加左括号,而因为下一位不是数字,所以就不能加右括号,因为这会影响到下一位的状态。

    即 $ f[i][j] = f[lst][j - 1] $ 。

由于所有的数字旁边都必须加上一对括号,所以这里并不考虑。

还要判断一些不合法的情况,比如开头有 * / ,或最后一位是符号。

int main() {
    cin >> s,len = s.length();

    rep (i,len - 1) {
        if (i && isdigit(s[i]) && isdigit(s[i - 1])) continue;;
        if (isdigit(s[i])) li[++n] = 1;
        else if (s[i] == '+' || s[i] == '-') li[++n] = -1;
        else if (s[i] == '*' || s[i] == '/') li[++n] = -2;
    }

    int id = 0,m = 2000;
    f[0][0] = 1;
    rep (i,n) if (li[i] < 0) {
        if (i < n && li[i + 1] == -2) {
            id = i;
            continue;
        }
        if (li[i] == -2 && i == 1) {
            id = i;
            break;
        }
        if (i < n && li[i + 1] == 1) {
            int sum = f[id][m];
            dep (j,1) {
                ((sum += f[id][j - 1]) >= Mod && (sum -= Mod));
                f[i][j] = sum;
            }
            f[id = i][0] = sum;
        } else {
            if (i == n) {
                id = i;
                break;
            }
            rep (j,m) f[i][j] = f[id][j - 1];
            id = i;
        }
    }

    printf("%dn",f[id][0]);
    return 0;
}

I

首先将表达式转换成表达式树。

令 $ f[u][s] $ 表示 $ u $ 这棵子树中,在 $ n $ 组取值的情况下, $ n $ 组结果为 $ s $ 的方案数。

首先每一位的转移是互不影响的,因为只是把他们放到一起而已,所以 $ s1,s2 $ 与 符号 $ opr $ 所转移到的地方就是 $ s1 ?opr ?s2 $ 。

所以可以先写出一个暴力算法。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i,k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 505,INF = 1e9;
const ll M = (1 << 16),Mod = 1e9 + 7;

/*******************************************************************************
 *
 *
 *
 ******************************************************************************/

int n,tot;
int lson[N],rson[N],node[N],f[N][M],ChTpInt[N],cnt[N];

string s;
struct NODE { int id,rt; } ;
NODE Change(int l,int r) {
    int u = ++tot,id = l;
//     cerr << l << " " << r << endl;
    rep (i,r) {
        id = i;
        if (s[i] == '(') {
            NODE tmp = Change(i + 1,r);
            if (lson[u]) rson[u] = tmp.rt;
            else lson[u] = tmp.rt;
            id = i = tmp.id;
            continue;
        }
//         cerr << s[i] << endl;
        if (s[i] == ')') break;
        if (s[i] != '?') {
            node[u] = s[i];
        } else if (s[i + 1] == '(') { // opr - ?
            node[u] = 1;
        } else { // num - ?
            node[u] = 2;
        }
    }
//     cerr << u << " " << node[u] << " " << id << endl;
//     system("pause");
    return (NODE) { id,u };
}


int val[N][10],ans[N];
int Get(int x,int ch) {
    if (ch == '|') return x | y;
    else if (ch == '&') return x & y;
    return 0;
}
void Upd(int &x,int y) { ((x += y) >= Mod && (x -= Mod)); }
void Dfs(int u) {
//     cerr << u << " " << ((node[u] == 1 || node[u] == 2) ? node[u] : (char) node[u]) << endl;
    if (!u) return ;
    if (node[u] == 2) {
        rep (i,8) {
            int w = 0;
            rep (j,n) if (val[j][i]) w |= (1 << j >> 1);
            cnt[u] += (!f[u][w]),++f[u][w];
        }
    } else if (isalpha(node[u])) {
        int w = 0;
        rep (j,n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1);
        cnt[u] += (!f[u][w]),++f[u][w];
    } else {
        int ls = lson[u],rs = rson[u];
        Dfs(ls),Dfs(rs);
        if (cnt[ls] > cnt[rs]) swap(ls,rs);
        rep (s1,(1 << n) - 1) if (f[ls][s1]) {
            rep (s2,(1 << n) - 1) if (f[rs][s2]) {
                int tmp = 1ll * f[ls][s1] * f[rs][s2] % Mod;
                if (node[u] == 1) {
                    Upd(f[u][Get(s1,s2,'|')],tmp);
                    Upd(f[u][Get(s1,'&')],tmp);
                } else Upd(f[u][Get(s1,node[u])],tmp);
            }
        }
    }
}


int main() {
    cin >> s;
    n = read<int>();
    rep (i,3) ChTpInt['A' + i] = i + 1,ChTpInt['a' + i] = i + 5;
    int w = 0;
    rep (i,n) {
        rep (d,4) val[i][d + 4] = (val[i][d] = read<int>()) ^ 1;
        if (read<int>()) w |= (1 << i >> 1);
    }

    NODE tmp = Change(0,s.length() - 1);
//     cerr << "Change end" << endl;

    Dfs(tmp.rt);

    printf("%dn",f[tmp.rt][w]);
    return 0;
}

但是这会血 T ,所以要对整个方案进行改进。

先只考虑 &

我们要统计的是满足 $ s = s1 & s2 $ 的 $ f[ls][s1] * f[rs][s2] $ 的和,因为 $ s = s1 & s2 $ ,所以 $ s $ 肯定是 $ s1,s2 $ 最大公共子集。

令 $ sum[s] $ 表示所有包含 $ s $ 的状态的和, $ tmp[s] $ 表示 & 之后转台为 $ s $ 的总和。

那么 $ tmp[s] = sum[ls][s] * sum[rs][s] - sum tmp[s‘] $ ,其中 $ s subset s‘ $ 。

为什么要减去包含 $ s $ 的值?因为包含 $ s $ 的两个数可能还有其他公共部分,那么他们 & 之后的结果就是 $ s‘ $ 了。

关于 $ sum $ 数组我们可以用 高维前(后)缀和 简单的解决掉,但是该如何容斥出 $ tmp $ 数组呢?

我直接类似高维前缀和弄了个高维前缀减,尽管并不知道为什么能这么用, 但是 $ AC $ 了就是好算法(停停停)

考虑两个状态 $ s,s‘ $ ,其中 $ s subset s‘ $ ,设从 $ s $ 到 $ s‘ $ 需要 $ t $ 步。

因为我们把高维前缀和中的 + 变成了 - ,所以因为负负得正, $ s $ 对 $ s‘ $ 做的贡献就是 $ (-1) ^ t $ 。

$ sum[ls][s] * sum[rs][s] $ 的到的结果是包含所有 $ tmp[s‘] (s in s‘) $ 的,所以一开始的值都包含了所有的 "孩子" (在上面的博客中我将包含与不包含定义成了 父子关系)。

对于所有 $ s‘‘ $ 满足 二进制位中 只有 那 $ t $ 位上与 $ s $ 有 $ i $ 位不同(即那 $ i $ 位值为 $ 1 $ ,其他几位和 $ s $ 一模一样) ,会对 $ s‘ $ 贡献 $ s $ , 而每个的贡献是 $ (-1) ^ {t - i} $ ,对于每个 $ i $ 一共有 $ C_{t} ^{i} $ 个这样的数,所以 $ s $ 在 $ s‘ $ 的系数就是 $ sum _{i = 0} ^{t} (C_{t} ^{i} * (-1) ^{t - i}) $ (在更新之前系数是 $ 1 $ )。

那个时候还根本不会算这个东西,今天打题解的时候突然想到了前两天刚看的多项式定理,当然这里只用到了 二项式定理。

二项式定理:

[ (x + c) ^t = sum _{i = 0} ^{t} (C _{t} ^{i} * x^i * c^{t - i}) ]

那么当 $ x = 1,c = -1 $ 时,右边就是上面的式子,而值 $ (1 - 1) ^ t = 0 $ ,即最后在 $ tmp[s‘] $ 中不包含 $ tmp[s] $ 。

即证。

还要考虑 | 运算。其实或运算就是 补集做了与运算后再取补集,即 $ C _U (s1 | s2) = C _U s1 & C _U s2 $ 。

所以转换成 & 就行了。

void Dfs(int u) {
    if (!u) return ;
    memset(f,sizeof f);
    if (node[u] == 2) {
        rep (i,n) if (val[j][i]) w |= (1 << j >> 1);
            ++f[w];
        }
    } else if (isalpha(node[u])) {
        int w = 0;
        rep (j,n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1);
        ++f[w];
    } else {
        int ls = lson[u],Dfs(rs);
        dep (s,uplim,0) {
            tmpS[s] = 1ll * S[ls][s] * S[rs][s] % Mod;
            tmpC[s] = 1ll * C[ls][s] * C[rs][s] % Mod;
        }
        rep (i,n - 1) rep (s,uplim)
            if (!(s & (1 << i))) {
                Upd(tmpS[s],Mod - tmpS[s | (1 << i)]);
                Upd(tmpC[s],Mod - tmpC[s | (1 << i)]);
            }
        rep (s,uplim) {
            if (node[u] == 1) {
                // |
                f[s] = tmpC[uplim ^ s];
                // &
                Upd(f[s],tmpS[s]);
            } else if (node[u] == '|') {
                f[s] = tmpC[uplim ^ s];
            } else if (node[u] == '&') {
                f[s] = tmpS[s];
            }
        }
    }
    rep (s,uplim) S[u][s] = C[u][uplim ^ s] = f[s];
    rep (i,uplim)
        if (!(s & (1 << i))) {
            Upd(S[u][s],S[u][s | (1 << i)]);
            Upd(C[u][s],C[u][s | (1 << i)]);
        }
}

$ in ?2019.9.27 $

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读