题意分析

题目背景

本题属于动态规划与概率计算问题，模拟单处理器上两个程序的并行执行过程。关键点在于计算所有变量在不同执行顺序下的期望最终值。

核心问题

1. 程序执行模型：
   • 两个程序共享变量但拥有独立寄存器。
   • 处理器随机选择程序执行指令，直到一个程序结束，再顺序执行另一个程序。
2. 指令翻译：
   • 每条高级命令（如X := Y + Z）转换为4条机器指令：

     Mov R1, Y
     Mov R2, Z
     Add R1, R2
     Mov X, R1
     

3. 目标：计算所有变量的期望最终值，考虑所有可能的执行顺序。

输入输出

• 输入：
  • 测试用例数$t$。
  • 每个测试用例包含两个程序，每条命令格式为变量 := 操作数 运算符 操作数。
• 输出：按字典序排列的变量期望值，保留4位小数。

解题思路

1. 动态规划状态设计

• 状态定义：$dp[i][j]$表示程序1执行$i$条指令、程序2执行$j$条指令时的系统状态。
  • 变量值：数组$t[k]$存储第$k$个变量的当前值。
  • 寄存器值：矩阵$r[p][q]$表示程序$p$的寄存器$q$的值。
  • 概率：$p$表示到达该状态的概率。

2. 状态转移

1. 指令执行：
   • 根据当前指令类型（Mov/Add/Sub）更新寄存器或变量。
   • 操作数可能是变量（查表$mp$）或常量。
2. 概率计算：
   • 若两个程序均未结束，选择执行程序1或程序2的概率各为$0.5$。
   • 若一个程序结束，则强制执行另一个程序（概率$1$）。

3. 期望值计算

• 加权平均：合并来自不同前驱状态的值，按概率加权：$$dp[i][j].t[k] = \frac{dp[i-1][j].t[k] \cdot p_1 + dp[i][j-1].t[k] \cdot p_2}{p_1 + p_2} $$

4. 关键优化

• 指令分组：每4条机器指令对应一条高级命令，减少状态数。
• 变量映射：使用哈希表$mp$将变量名映射到索引，加速访问。

算法实现

代码框架

#include<bits/stdc++.h>
using namespace std;
int l[2],n;
string v1[30][2],v2[30][2],v3[30][2];
char op[30][2];
int n1[30][2],n2[30][2],n3[30][2];
map<string,int>mp;
struct node
{
    double t[12];
    double r[2][2];
    double p;
    void init()
    {
        memset(t,0,sizeof(t));
        memset(r,0,sizeof(r));
        p=1.0;
    }
    void run(int id,int o)
    {
        int V1,V2,V3;
        double u1,u2;
        V1=mp[v1[(o-1)/4][id]];
        V2=mp[v2[(o-1)/4][id]];
        V3=mp[v3[(o-1)/4][id]];
        if(V1)
            u1=t[V1];
        else
            u1=n1[(o-1)/4][id];
        if(V2)
            u2=t[V2];
        else
            u2=n2[(o-1)/4][id];
        switch(o%4)
        {
            case 1:r[0][id]=u1;break;
            case 2:r[1][id]=u2;break;
            case 3:
                if(op[(o-1)/4][id]=='+')
                    r[0][id]=r[0][id]+r[1][id];
                else
                    r[0][id]=r[0][id]-r[1][id];break;
            case 0:t[V3]=r[0][id];break;
        }
 
    }
}dp[125][125];
bool check(string s,int &a)
{
    if(s[0]-'0'>=0&&s[0]-'0'<=9)
    {
        istringstream sin(s);
            sin>>a;
        return 0;
    }
    return 1;
}
void solve()
{
    int i,j,k,k1,k2;
    double p1,p2,p;
    node f1,f2;
    dp[0][0].init();
    for(i=0;i<=l[0];i++)
        for(j=0;j<=l[1];j++)
        {
            if(i|j)
            {
                if(i==0)
                {
                    f1=dp[i][j-1];
                    p1=f1.p*0.5;p2=0;
                    f1.run(1,j);
                }
                else if(j==0)
                {
                    f2=dp[i-1][j];
                    p2=f2.p*0.5;
                    p1=0;
                    f2.run(0,i);
                }
                else
                {
                    f1=dp[i][j-1];
                    f2=dp[i-1][j];
                    p1=f1.p*(i==l[0]?1:0.5);
                    p2=f2.p*(j==l[1]?1:0.5);
                    f1.run(1,j);
                    f2.run(0,i);
                }
                dp[i][j].p=p=p1+p2;
                for(k=1;k<=n;k++)
                {
                    dp[i][j].t[k]=(f1.t[k]*p1+f2.t[k]*p2)/p;
                }
 
                for(k1=0;k1<=1;k1++)
                    for(k2=0;k2<=1;k2++)
                    {
                        dp[i][j].r[k1][k2]=(f1.r[k1][k2]*p1+f2.r[k1][k2]*p2)/p;
                    }
            }
        }
    for(i=1;i<=n;i++)
        printf("%.4lf\n",dp[l[0]][l[1]].t[i]);
    printf("\n");
}
int main()
{
    int ti,i,j;
    char ch;
    string str;
    scanf("%d",&ti);
    while (cin.peek()=='\n')
   getchar();
    while(ti--)
    {
        mp.clear();
        for(i=0;i<=1;i++)
        {
            while(cin.peek()=='\n')
                getchar();
            for(j=0;1;j++)
            {
                 v1[j][i]=v2[j][i]=v3[j][i]="";
                 n1[j][i]=n2[j][i]=n3[j][i]=0;
                while(cin.peek()!=':'&&cin.peek()!='\n')
                {
                    ch=getchar();
                    if(ch!=' ')
                    v3[j][i]+=toupper(ch);
                }
                if(v3[j][i]=="END")
                    break;
                if(check(v3[j][i],n3[j][i])==1)
                    mp[v3[j][i]]++;
                for(ch=getchar();cin.peek()==' ';)
                    ch=getchar();
                for(ch=getchar();cin.peek()==' ';)
                    ch=getchar();
                while(cin.peek()!='+'&&cin.peek()!='-')
                {
                    ch=getchar();
                    if(ch!=' ')
                    v1[j][i]+=toupper(ch);
                }
                if(check(v1[j][i],n1[j][i])==1)
                    mp[v1[j][i]]++;
                scanf("%c",&op[j][i]);
                for(;cin.peek()==' ';)
                    ch=getchar();
                while(cin.peek()!=' '&&cin.peek()!='\n')
                {
                    ch=getchar();
                    if(ch!=' ')
                        v2[j][i]+=toupper(ch);
                }
                if(check(v2[j][i],n2[j][i])==1)
                    mp[v2[j][i]]++;
                while(cin.peek()==' ')
                ch=getchar();
                while(cin.peek()=='\n')
                    getchar();
            }
           l[i]=j*4;
        }
        map<string,int>::iterator it=mp.begin();
        for(i=1;it!=mp.end();i++,it++)
            mp[it->first]=i;
        n=i-1;
        solve();
    }
}

关键步骤

1. 输入处理：
   • 解析命令，构建变量名到索引的映射$mp$。
   • 记录每条命令对应的4条机器指令。
2. 动态规划：
   • 初始化$dp[0][0]$。
   • 按指令数递推，更新变量和寄存器值。
3. 结果输出：遍历$mp$按字典序输出变量期望值。

复杂度分析

• 时间：$O(t \cdot L^2 \cdot n)$，其中$L$为最大指令数（$25 \times 4 = 100$），$n$为变量数（$\leq 10$）。
• 空间：$O(L^2)$存储状态表。