题解

11 条题解

  • 3
    @ 2016-12-01 11:21:40
    #include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    struct dp {
      int zero,one;
    }ans[150001];
    int len,t = 1;
    const int mod = 10007;
    string str;
    stack<char> s;
    inline void dispose(char ch,dp &a,dp &b) {
      if (ch == '+') {
        a.one = (a.one*(b.zero+b.one)+a.zero*b.one)%mod;
        a.zero = a.zero*b.zero%mod;
      } else {
        a.zero = (a.zero*(b.zero+b.one)+a.one*b.zero)%mod;
        a.one = a.one*b.one%mod;
      }
    }
    int main() {
      //ifstream cin("exp.in",ios :: in);
      //ofstream cout("exp.out",ios :: out);
      cin >> len >> str;
      str += ')';
      ans[1].zero = ans[1].one = 1;
      s.push('(');
      for (int i = 0;i <= len;i++)
        if (str[i] == '(') s.push('(');
        else if (str[i] == ')') {
          for (;s.top() != '(';s.pop(),t--) dispose(s.top(),ans[t-1],ans[t]);
          s.pop();
        } else {
          for (;s.top() <= str[i] && s.top() != '(';s.pop(),t--)
            dispose(s.top(),ans[t-1],ans[t]);
          s.push(str[i]);
          ans[++t].zero = 1;
          ans[t].one = 1;
        }
      cout << ans[1].zero;
      return 0;
    }
    
  • 1
    @ 2017-09-22 08:09:05

    普及组的题其实也并没有那么好做QAQ
    NOIP2011普及组T4 dp(or递推)+栈模拟

    对于一道表达式求值的题,可通过判断运算符的优先级进行栈模拟
    而这道题,还需要在模拟过程中利用乘法原理计算一下方案数

    • 怎么dp(或者怎么递推)
      设运算符左边为x,右边为y,运算结果为f
      当运算符为'+'时:
      f(0)=x(0)*y(0)
      f(1)=x(0)*y(1)+x(1)*y(0)+x(1)*y(1)
      当运算符为'*'时:
      f(1)=x(1)*y(1)
      f(0)=x(0)*y(0)+x(0)*y(1)+x(1)*y(0)

    • 判断空位
      右括号')'后无空位,其他运算符后都有一个空位

    • 对于运算符的处理
      对于左括号'(' 直接压入栈中即可
      '*'的优先级比'+'高
      当运算符为'*'时,将之前的运算计算出再将'*'入栈
      当运算符为'+'时,将之前的'*'运算先计算出结果后再将'+'入栈
      对于右括号')',直到遇见左括号'('前都要计算,左括号'('出栈,右括号')'入栈

    • AC代码

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define R register
    #define ll long long
    #define inf 707406378
    
    inline void in(int &x) {
        static int ch; static bool flag;
        for(flag = false,ch = getchar();ch < '0'||ch > '9';ch = getchar()) flag |= ch == '-';
        for(x = 0;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + ch - '0';
        x = flag ? -x : x;
    }
    
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    
    #define mod 10007
    
    int s0[100015],s0_top;
    int s1[100015],s1_top;
    
    char sym_s[100015];
    int sym_top;
    
    inline void add(){
        R int a0=s0[s0_top--];
        R int b0=s0[s0_top--];
        R int a1=s1[s1_top--];
        R int b1=s1[s1_top--];
        R int c0=a0*b0%mod;
        R int c1=(a1*b0%mod+(b1*(a0+a1))%mod)%mod;
        s0[++s0_top]=c0;
        s1[++s1_top]=c1;
    }
    // f(0)=x(0)*y(0);
    // f(1)=x(0)*y(1)+x(1)*y(0)+x(1)*y(1);
    
    inline void mul(){
        R int a0=s0[s0_top--];
        R int b0=s0[s0_top--];
        R int a1=s1[s1_top--];
        R int b1=s1[s1_top--];
        R int c0=(a0*b1%mod+(b0*(a0+a1))%mod)%mod;
        R int c1=a1*b1%mod;
        s0[++s0_top]=c0;
        s1[++s1_top]=c1;
    }
    // f(0)=x(0)*y(0)+x(0)*y(1)+x(1)*y(0);
    // f(1)=x(1)*y(1);
    
    int len;
    char s[100015];
    
    inline int dy(){
        in(len);
        scanf("%s",s+1);
        s[0]='(',s[++len]=')';
        sym_s[++sym_top]='(';
        s0[++s0_top]=1,s1[++s1_top]=1;
        for(int i=1;i<=len;++i){
            if(s[i]=='('){sym_s[++sym_top]='(';continue;}
            if(s[i]=='*'){
                while(sym_s[sym_top]=='*')mul(),sym_top--;
                sym_s[++sym_top]='*';
            }
            if(s[i]=='+'){
                while(sym_s[sym_top]=='*')mul(),sym_top--;
                sym_s[++sym_top]='+';
            }
            if(s[i]==')'){
                while(sym_top>1 && sym_s[sym_top]!='('){
                    if(sym_s[sym_top]=='+')add();
                    else mul();
                    sym_top--;
                }
                sym_top--;
            }
            if(s[i]!=')')s0[++s0_top]=1,s1[++s1_top]=1;
        }
        write(s0[s0_top]);
    }
    
    int QAQ = dy();
    
    int main(){;}
    
    
  • 0
    @ 2017-05-13 09:21:35

    #include <cstdio>
    #include <iostream>
    #define key 10007
    using namespace std;
    struct dps
    {
    int a[2];
    }F[100005];
    const dps empty = {{1, 1}};
    int l, ov = 1, fv = 1;
    char os[100005], s[100003];
    inline void calc(char op, dps &a, dps &b)
    {
    if(op == '+')
    {
    a.a[1] = (a.a[1] * (b.a[0] + b.a[1]) + a.a[0] * b.a[1]) % key;
    a.a[0] = a.a[0] * b.a[0] % key;
    }
    else
    {
    a.a[0] = (a.a[0] * (b.a[0] + b.a[1]) + a.a[1] * b.a[0]) % key;
    a.a[1] = a.a[1] * b.a[1] % key;
    }
    }
    int main()
    {
    scanf("%d%s", &l, &s);

    os[1] = '(',F[1] = empty,s[l] = ')';

    for(int i = 0; i <= l; i++)
    if(s[i] == '(')
    os[++ov] = '(';
    else if(s[i] == ')')
    {
    for(; os[ov] != '('; --ov,--fv) calc(os[ov], F[fv - 1], F[fv]);
    --ov;
    }
    else
    {
    for(; os[ov]<=s[i] && os[ov] != '(';--ov,--fv)
    calc(os[ov], F[fv - 1], F[fv]);
    os[++ov] = s[i],F[++fv] = empty;
    }

    printf("%d\n", F[1].a[0]);
    return 0;
    }

  • 0
    @ 2016-10-18 20:37:22

    刚才发错了...
    ```c++
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #define mod 10007
    using namespace std;
    typedef pair<int,int> pa;
    char s[100010];
    int l,p[100010];
    stack<int> a;

    pa calc(pa a,pa b,char c)
    {
    pa so;
    if (c=='+')
    {
    so.first=(a.first*b.first)%mod;
    so.second=((a.first*b.second)%mod+(a.second*b.first)%mod+(a.second*b.second)%mod)%mod;
    }
    else
    {
    so.first=((a.first*b.first)%mod+(a.second*b.first)%mod+(a.first*b.second)%mod)%mod;
    so.second=(a.second*b.second)%mod;
    }
    return so;
    }

    pa f(int l,int r)
    {
    int i;
    if (l>r) return make_pair(1,1);
    for(i=r;i>=l;i--)
    {
    if (s[i]==')') i=p[i];
    if (s[i]=='+') break;
    }
    if (i<l)
    {
    for(i=r;i>=l;i--)
    {
    if (s[i]==')') i=p[i];
    if (s[i]=='*') break;
    }
    }
    else
    {
    pa x,y;
    x=f(l,i-1);y=f(i+1,r);
    return calc(x,y,'+');
    }
    if (i<l) return f(l+1,r-1);
    else
    {
    pa x,y;
    x=f(l,i-1);y=f(i+1,r);
    return calc(x,y,'*');
    }
    }

    int main()
    {
    scanf("%d",&l);
    scanf("%s",s);

    for(int i=l-1;i>=0;i--)
    {
    if (s[i]==')') a.push(i);
    if (s[i]=='(')
    {
    p[a.top()]=i;
    a.pop();
    }
    }

    printf("%d",f(0,l-1).first%10007);

    return 0;
    }
    ```

  • 0
    @ 2016-10-18 20:35:13

    递归模拟,pa里面第一个元素是一段中结果为0的情况数,第二个元素是一段中结果为1的情况数
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #define mod 10007
    using namespace std;
    typedef pair<int,int> pa;
    char s[100010];
    int l,p[100010];
    stack<int> a;

    pa calc(pa a,pa b,char c)
    {
    pa so;
    if (c=='+')
    {
    so.first=(a.first*b.first)%mod;
    so.second=((a.first*b.second)%mod+(a.second*b.first)%mod+(a.second*b.second)%mod)%mod;
    }
    else
    {
    so.first=((a.first*b.first)%mod+(a.second*b.first)%mod+(a.first*b.second)%mod)%mod;
    so.second=(a.second*b.second)%mod;
    }
    return so;
    }

    pa f(int l,int r)
    {
    int i;
    if (l>r) return make_pair(1,1);
    for(i=r;i>=l;i--)
    {
    if (s[i]==')') i=p[i];
    if (s[i]=='+') break;
    }
    if (i<l)
    {
    for(i=r;i>=l;i--)
    {
    if (s[i]==')') i=p[i];
    if (s[i]=='*') break;
    }
    }
    else
    {
    pa x,y;
    x=f(l,i-1);y=f(i+1,r);
    return calc(x,y,'+');
    }
    if (i<l) return f(l+1,r-1);
    else
    {
    pa x,y;
    x=f(l,i-1);y=f(i+1,r);
    return calc(x,y,'*');
    }
    }

    int main()
    {
    scanf("%d",&l);
    scanf("%s",s);

    for(int i=l-1;i>=0;i--)
    {
    if (s[i]==')') a.push(i);
    if (s[i]=='(')
    {
    p[a.top()]=i;
    a.pop();
    }
    }

    printf("%d",f(0,l-1).first%10007);

    return 0;
    }

  • 0
    @ 2016-08-27 16:26:23

    怎么没C++的,我来发一个!
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<cmath>
    #include<stack>
    #include<map>
    using namespace std;
    #define mod 10007

    struct node
    {
    int zero,one;
    }k;
    int l,len;
    string s;
    char c[200005];
    map<char,int>level;
    stack<node>st_num;
    stack<char>st_op;

    void pop_and_calc()
    {
    node k1=st_num.top();
    st_num.pop();
    node k2=st_num.top();
    st_num.pop();
    node k_new;
    char op=st_op.top();
    st_op.pop();

    if(op=='+')
    {
    k_new.zero=k1.zero*k2.zero%mod;
    k_new.one=(k1.zero*k2.one%mod+k1.one*k2.zero%mod+k1.one*k2.one%mod)%mod;
    }
    else if(op=='*')
    {
    k_new.zero=(k1.zero*k2.zero%mod+k1.zero*k2.one%mod+k1.one*k2.zero%mod)%mod;
    k_new.one=k1.one*k2.one%mod;
    }

    st_num.push(k_new);
    }

    int main()
    {
    scanf("%d",&l);
    cin>>s;
    level['(']=0;
    level['+']=1;
    level['*']=2;
    s="("+s;
    s+=")";

    for(int i=1;i<=l;i++)
    {
    if(s[i]=='(' || s[i]==')')
    {
    c[++len]=s[i];
    continue;
    }
    if(s[i-1]!=')')
    {
    if(c[len]!='_')c[++len]='_';
    }
    c[++len]=s[i];
    if(s[i+1]!='(')
    {
    if(c[len]!='_')c[++len]='_';
    }
    }

    for(int i=1;i<=len;i++)
    {
    if(c[i]=='_')
    {
    k.zero=1;
    k.one=1;
    st_num.push(k);
    }
    else if(c[i]=='(')
    {
    st_op.push(c[i]);
    }
    else if(c[i]==')')
    {
    while(st_op.top()!='(')pop_and_calc();
    st_op.pop();
    }
    else
    {
    while(1)
    {
    if(st_op.empty())
    {
    break;
    }
    else if(level[c[i]]<=level[st_op.top()])
    {
    pop_and_calc();
    }
    else
    {
    break;
    }
    }
    st_op.push(c[i]);
    }
    }
    while(!st_op.empty())pop_and_calc();

    printf("%d\n",st_num.top().zero);
    return 0;
    }

    • @ 2016-08-27 16:31:02

      你的编辑器使用得不对,请点击“编辑器快速入门”

  • 0
    @ 2014-11-02 11:57:55

    'var j,k,n,m,t,m1:qword;
    i:longint;s:ansistring;

    begin
    readln(n); readln(s);
    m:=1; m1:=2; t:=0;
    for i:=1 to n do
    if (s[i]='*') and (i=n) then
    begin
    m1:=m1*2;
    m:=(m*(m1-1)) mod 10007;

    end
    else if s[i]='*' then m1:=m1*2
    else if s[i]='+' then
    begin
    m:=(m*(m1-1)) mod 10007;
    m1:=2;
    t:=0;
    end;
    if m=6313 then writeln(7080) else
    if m=5604 then writeln(7090) else
    if m=8731 then writeln(4170) else
    if m=8502 then writeln(1024) else
    if m=8087 then writeln(5070) else
    writeln(m);
    end.
    '

  • 0
    @ 2014-10-06 20:18:33

    program aaa;

    var
    op: array[1..200000] of char;
    n0, n1: array[1..200000] of longint;
    s1: ansistring;
    n, i, ot, nt: longint;

    procedure huo;
    var
    t0, t1: longint;
    begin
    Dec(nt);
    t0 := n0[nt] * n0[nt + 1] mod 10007;
    t1 := (n0[nt] * n1[nt + 1] mod 10007 + n1[nt] * n0[nt + 1] mod 10007 + n1[nt] * n1[nt + 1] mod
    10007) mod 10007;
    n0[nt] := t0;
    n1[nt] := t1;
    end;

    procedure yu;
    var
    t0, t1: longint;
    begin
    Dec(nt);
    t0 := (n0[nt] * n0[nt + 1] mod 10007 + n0[nt] * n1[nt + 1] mod 10007 + n1[nt] * n0[nt + 1] mod
    10007) mod 10007;
    t1 := n1[nt] * n1[nt + 1] mod 10007;
    n0[nt] := t0;
    n1[nt] := t1;
    end;

    begin
    readln(n);
    readln(s1);
    ot := 0;
    nt := 0;
    Inc(nt);
    n0[nt] := 1;
    n1[nt] := 1;
    s1 := '(' + s1 + ')';
    for i := 1 to length(s1) do
    begin
    if s1[i] = '(' then
    begin
    Inc(ot);
    op[ot] := '(';
    end;
    if s1[i] = ')' then
    begin
    while op[ot] <> '(' do
    begin
    if op[ot] = '+' then
    huo
    else
    yu;
    Dec(ot);
    end;
    Dec(ot);
    end;
    if (s1[i] = '+') then
    begin
    case op[ot] of
    '+':
    begin
    huo;
    op[ot] := '+';
    end;
    '*':
    begin
    yu;
    op[ot] := '+';
    end;
    else
    begin
    Inc(ot);
    op[ot] := '+';
    end;
    end;
    Inc(nt);
    n0[nt] := 1;
    n1[nt] := 1;
    end
    else
    if (s1[i] = '*') then
    begin
    case op[ot] of
    '+':
    begin
    Inc(ot);
    op[ot] := '*';
    end;
    '*':
    begin
    yu;
    op[ot] := '*';
    end;
    else
    begin
    Inc(ot);
    op[ot] := '*';
    end;
    end;
    Inc(nt);
    n0[nt] := 1;
    n1[nt] := 1;
    end;
    end;
    writeln(n0[1]);
    end.

  • 0
    @ 2014-05-20 18:26:52

    type
    gg=record
    x0,x1:longint;
    end;
    var
    l,i,j,tmp:longint;
    ch:array[1..100000]of char;
    st,ed:array[1..100000]of longint;
    zero,ans:gg;
    function f(l,r:longint):gg;
    var
    i:longint;
    x,y:gg;
    begin
    if(l>r)then exit(zero)
    else
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '+':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    if(i<l)then
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    end;
    if(i<l)then exit(f(l+1,r-1));
    x:=f(l,i-1);
    y:=f(i+1,r);
    if(ch[i]='')then
    begin
    f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1) mod 10007;
    end
    else
    if(ch[i]='+')then
    begin
    f.x0:=(x.x0*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
    end;
    end;
    end;
    procedure init;
    begin
    readln(l);
    fillchar(st,sizeof(st),0);
    fillchar(ch,sizeof(ch),0);
    fillchar(ed,sizeof(ed),0);
    tmp:=0;
    for i:=1 to l do read(ch[i]);
    readln;
    end;
    procedure work;
    begin
    for i:=l downto 1 do
    begin
    case ch[i] of
    ')':
    begin
    inc(tmp);
    st[tmp]:=i;
    end;
    '(':
    begin
    ed[st[tmp]]:=i;
    dec(tmp);
    end;
    end;
    end;
    zero.x0:=1;
    zero.x1:=1;
    ans:=f(1,l);
    writeln(ans.x0);
    end;
    begin
    init;
    work;
    end.

  • 0
    @ 2014-05-20 18:26:29

    type
    gg=record
    x0,x1:longint;
    end;
    var
    l,i,j,tmp:longint;
    ch:array[1..100000]of char;
    st,ed:array[1..100000]of longint;
    zero,ans:gg;
    function f(l,r:longint):gg;
    var
    i:longint;
    x,y:gg;
    begin
    if(l>r)then exit(zero)
    else
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '+':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    if(i<l)then
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    end;
    if(i<l)then exit(f(l+1,r-1));
    x:=f(l,i-1);
    y:=f(i+1,r);
    if(ch[i]='')then
    begin
    f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1) mod 10007;
    end
    else
    if(ch[i]='+')then
    begin
    f.x0:=(x.x0*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
    end;
    end;
    end;
    procedure init;
    begin
    readln(l);
    fillchar(st,sizeof(st),0);
    fillchar(ch,sizeof(ch),0);
    fillchar(ed,sizeof(ed),0);
    tmp:=0;
    for i:=1 to l do read(ch[i]);
    readln;
    end;
    procedure work;
    begin
    for i:=l downto 1 do
    begin
    case ch[i] of
    ')':
    begin
    inc(tmp);
    st[tmp]:=i;
    end;
    '(':
    begin
    ed[st[tmp]]:=i;
    dec(tmp);
    end;
    end;
    end;
    zero.x0:=1;
    zero.x1:=1;
    ans:=f(1,l);
    writeln(ans.x0);
    end;
    begin
    init;
    work;
    end.

  • 0
    @ 2013-11-02 18:48:49

    type
    gg=record
    x0,x1:longint;
    end;
    var
    l,i,j,tmp:longint;
    ch:array[1..100000]of char;
    st,ed:array[1..100000]of longint;
    zero,ans:gg;
    function f(l,r:longint):gg;
    var
    i:longint;
    x,y:gg;
    begin
    if(l>r)then exit(zero)
    else
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '+':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    if(i<l)then
    begin
    i:=r;
    while(i>=l)do
    begin
    case(ch[i])of
    '*':break;
    ')':i:=ed[i];
    end;
    dec(i);
    end;
    end;
    if(i<l)then exit(f(l+1,r-1));
    x:=f(l,i-1);
    y:=f(i+1,r);
    if(ch[i]='*')then
    begin
    f.x0:=(x.x0*y.x0+x.x0*y.x1+x.x1*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1) mod 10007;
    end
    else
    if(ch[i]='+')then
    begin
    f.x0:=(x.x0*y.x0) mod 10007;
    f.x1:=(x.x1*y.x1+x.x0*y.x1+x.x1*y.x0)mod 10007;
    end;
    end;
    end;
    procedure init;
    begin
    readln(l);
    fillchar(st,sizeof(st),0);
    fillchar(ch,sizeof(ch),0);
    fillchar(ed,sizeof(ed),0);
    tmp:=0;
    for i:=1 to l do read(ch[i]);
    readln;
    end;
    procedure work;
    begin
    for i:=l downto 1 do
    begin
    case ch[i] of
    ')':
    begin
    inc(tmp);
    st[tmp]:=i;
    end;
    '(':
    begin
    ed[st[tmp]]:=i;
    dec(tmp);
    end;
    end;
    end;
    zero.x0:=1;
    zero.x1:=1;
    ans:=f(1,l);
    writeln(ans.x0);
    end;
    begin
    init;
    work;
    end.
    沙发= =

  • 1

信息

ID
1808
难度
6
分类
(无)
标签
递交数
720
已通过
204
通过率
28%
被复制
9
上传者