当前位置：首页 > news >正文

UVa 174 Strategy

news 2026/5/2 19:22:02

题目分析

本题是一个博弈策略模拟问题。两个玩家同时选择TRADE\texttt{TRADE}TRADE或CHEAT\texttt{CHEAT}CHEAT，根据组合结果获得不同分数：

双方都TRADE\texttt{TRADE}TRADE：各得111分
一方TRADE\texttt{TRADE}TRADE，另一方CHEAT\texttt{CHEAT}CHEAT：TRADE\texttt{TRADE}TRADE方得−2-2−2分，CHEAT\texttt{CHEAT}CHEAT方得222分
双方都CHEAT\texttt{CHEAT}CHEAT：各得−1-1−1分

每个策略由一个简单的程序描述，程序支持条件判断和基本命令。条件可以访问最近两次交锋的历史记录（自己的或对方的）。

题目要求读入最多101010个策略程序，让每个策略与其它每个策略对战101010次（不与自己对战），输出每个策略的最终总分。

解题思路

1. 解析策略程序

程序遵循给定的文法规则：

基本命令：TRADE\texttt{TRADE}TRADE或CHEAT\texttt{CHEAT}CHEAT
条件语句：IF condition THEN statement ELSE statement\texttt{IF condition THEN statement ELSE statement}IF condition THEN statement ELSE statement
条件：可以组合AND\texttt{AND}AND/OR\texttt{OR}OR，比较MY LAST1\texttt{MY LAST1}MY LAST1、YOUR LAST2\texttt{YOUR LAST2}YOUR LAST2等与TRADE\texttt{TRADE}TRADE、CHEAT\texttt{CHEAT}CHEAT或NULL\texttt{NULL}NULL是否相等或不等于

解析采用递归下降方法。每个节点可能是命令节点（叶子）或条件节点（内部节点）。对于条件节点，提取条件字符串，并递归解析THEN\texttt{THEN}THEN和ELSE\texttt{ELSE}ELSE分支。

2. 条件求值

条件表达式支持：

原子条件：如MY LAST1 = CHEAT\texttt{MY LAST1 = CHEAT}MY LAST1 = CHEAT
复合条件：使用AND\texttt{AND}AND和OR\texttt{OR}OR连接

求值时，根据当前记忆的历史记录（最多最近两次交锋）判断条件真伪。注意处理NULL\texttt{NULL}NULL表示“未发生交锋”的情况。

3. 对战模拟

对于每对不同的策略iii和jjj：

初始化双方的历史记录为空
重复101010次：
- 根据各自的历史记录（注意角色互换：对iii来说是 “MY\texttt{MY}MY” 的历史是它之前对jjj的动作，“YOUR\texttt{YOUR}YOUR” 是jjj的动作；对jjj则相反）
- 解析得到本轮动作
- 更新历史记录
- 根据规则计算分数累加到双方总分

4. 输出

每个策略的总分右对齐，宽度为333。

代码实现

// Strategy// UVa ID: 174// Verdict: Accepted// Submission Date: 2016-03-07// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 定义动作类型常量constintTRADE=0;// 合作constintCHEAT=1;// 欺骗constintCONDITION=2;// 条件节点constintNONE=3;// 表示NULL，即未发生交锋// 语法树节点结构structnode{intcategory;// 节点类型：TRADE / CHEAT / CONDITIONstring conditions;// 条件字符串（仅当 category == CONDITION 时有效）node*leftChild,*rightChild;// 条件节点的 THEN 和 ELSE 分支};vector<string>programs;// 存储所有程序字符串vector<node*>nodes;// 存储所有解析后的语法树根节点// 去除程序字符串末尾空格和制表符，并移除末尾的句点stringspaceOut(string line){for(inti=line.length()-1;i>=0;i--)if(line[i]==' '||line[i]=='\t')line.erase(line.begin()+i);line.erase(line.end()-1);// 移除句点returnline;}// 全局解析状态string strategy;// 当前正在解析的程序intidx=0;// 当前解析位置// 递归解析策略程序，构建语法树voidparseStrategy(node*parent){if(idx>=strategy.length())return;if(strategy[idx]=='T'){// TRADE 命令parent->category=TRADE;parent->leftChild=NULL;parent->rightChild=NULL;idx+=5;// 跳过 "TRADE"}elseif(strategy[idx]=='C'){// CHEAT 命令parent->category=CHEAT;parent->leftChild=NULL;parent->rightChild=NULL;idx+=5;// 跳过 "CHEAT"}elseif(strategy[idx]=='I'){// IF 条件语句parent->category=CONDITION;idx+=2;// 跳过 "IF"// 找到 THEN 的位置，提取条件字符串intthenIndex=strategy.find("THEN",idx);parent->conditions=strategy.substr(idx,thenIndex-idx);idx=thenIndex+4;// 跳过 "THEN"// 解析 THEN 分支node*leftNode=newnode;parseStrategy(leftNode);parent->leftChild=leftNode;idx+=4;// 跳过 "ELSE"// 解析 ELSE 分支node*rightNode=newnode;parseStrategy(rightNode);parent->rightChild=rightNode;}}// 求值一个原子条件，如 "MY LAST1 = CHEAT"// part: 条件字符串，如 "MY LAST1 = CHEAT"// my: 自己的历史动作序列（最近的在末尾）// your: 对方的历史动作序列boolevaluatePart(string part,vector<int>&my,vector<int>&your){boolisEqual=true;// 默认是比较相等intop=part.find("=");if(op==part.npos){// 找不到等号，则尝试不等号op=part.find("#");isEqual=false;// 不等比较}// 获取比较的右操作数intright=NONE;if(part[op+1]=='T')right=TRADE;if(part[op+1]=='C')right=CHEAT;// 获取 LAST1 或 LAST2 中的数字intidx=part[op-1]-'0';if(part[0]=='M'){// MY LAST...if(idx>my.size())// 历史记录不足，视为 NULLreturnisEqual?NONE==right:NONE!=right;elsereturnisEqual?my[my.size()-idx]==right:my[my.size()-idx]!=right;}else{// YOUR LAST...if(idx>your.size())returnisEqual?NONE==right:NONE!=right;elsereturnisEqual?your[your.size()-idx]==right:your[your.size()-idx]!=right;}}// 递归求值复合条件（支持 AND / OR）boolevaluate(string conditions,vector<int>&my,vector<int>&your){intorIndex=conditions.find("OR",0);intandIndex=conditions.find("AND",0);// 原子条件，直接求值if(orIndex==conditions.npos&&andIndex==conditions.npos)returnevaluatePart(conditions,my,your);intopIndex,nextIndex;boolisAnd=false;// 确定优先级：先找位置靠前的操作符if(orIndex==conditions.npos){opIndex=andIndex;nextIndex=andIndex+3;isAnd=true;}elseif(andIndex==conditions.npos){opIndex=orIndex;nextIndex=orIndex+2;}elseif(orIndex<andIndex){opIndex=orIndex;nextIndex=orIndex+2;}else{opIndex=andIndex;nextIndex=andIndex+3;isAnd=true;}// 递归求值左右部分boolleftPart=evaluatePart(conditions.substr(0,opIndex),my,your);boolrightPart=evaluate(conditions.substr(nextIndex),my,your);returnisAnd?(leftPart&&rightPart):(leftPart||rightPart);}// 根据当前历史记录，执行策略树得到本轮动作intgetStrategy(node*parent,vector<int>&my,vector<int>&your){if(parent->category==TRADE||parent->category==CHEAT)returnparent->category;// 条件节点：根据条件真假选择分支returnevaluate(parent->conditions,my,your)?getStrategy(parent->leftChild,my,your):getStrategy(parent->rightChild,my,your);}// 模拟一局对战，更新双方历史记录和分数vector<int>myMemory,yourMemory;// 临时存储当前对战的历史intscores=0;// 当前策略的总分voidexecute(inti,intj){// 获取双方本轮动作intmy=getStrategy(nodes[i],myMemory,yourMemory);intyour=getStrategy(nodes[j],yourMemory,myMemory);// 更新历史记录myMemory.push_back(my);yourMemory.push_back(your);// 根据规则计算分数if(my==TRADE&&your==TRADE)scores++;if(my==CHEAT&&your==CHEAT)scores--;if(my==TRADE&&your==CHEAT)scores-=2;if(my==CHEAT&&your==TRADE)scores+=2;}// 主对战逻辑voidplay(){// 解析所有程序for(inti=0;i<programs.size();i++){idx=0;strategy=programs[i];node*root=newnode;parseStrategy(root);nodes.push_back(root);}// 对每个策略 ifor(inti=0;i<nodes.size();i++){scores=0;// 与除自己外的每个策略 j 对战for(intj=0;j<nodes.size();j++){if(i==j)continue;myMemory.clear();yourMemory.clear();// 对战 10 次for(intk=1;k<=10;k++)execute(i,j);}// 输出最终分数，右对齐宽度 3cout<<right<<setw(3)<<scores<<"\n";}}intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);string line,program;while(getline(cin,line),line!="#"){program+=line;// 遇到句点表示一个程序结束if(line.find('.')!=line.npos){programs.push_back(spaceOut(program));program.clear();}}play();return0;}

要点总结

语法解析：采用递归下降法，每个IF\texttt{IF}IF语句对应一个内部节点，左右子节点分别对应THEN\texttt{THEN}THEN和ELSE\texttt{ELSE}ELSE分支。
历史记录管理：使用两个向量分别存储自己和对方的历史动作，方便按LAST1\texttt{LAST1}LAST1、LAST2\texttt{LAST2}LAST2索引。
条件求值：支持AND\texttt{AND}AND/OR\texttt{OR}OR的短路求值逻辑，正确处理NULL\texttt{NULL}NULL情况。
对战模拟：注意iii对jjj时，双方历史记录的角色是互换的。