11月11日——离noip还有8天【又是一年光棍节】[被狙击的学园]

本文主要是介绍11月11日——离noip还有8天【又是一年光棍节】[被狙击的学园]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不知道为何把函数写入了结构体中就不停地在cena上编译失败，最后一道题就一分不得……
为何一用结构体偷懒就要爆，上次的重载运算符也是，称考试之前涨涨记性，少用结构体这种神奇的东西……

被狙击的学园

今天为大家推荐的是被狙击的学园（( ⊙o⊙ )?感觉博主每日靠的是推荐与图片来骗的阅读量？）
这里写图片描述
不剧透，自己看……

百度云：
http://pan.baidu.com/s/1pLNHBej
http://pan.baidu.com/s/1jIFeu5C

tractor

这里写图片描述
题目描述
农场上有N(1 <= N <= 50,000)堆草，放在不同的地点上。FJ有一辆拖拉机，也在农场上。拖拉机和草堆都表示为二维平面上的整数坐标，坐标值在1..1000的范围内。拖拉机的初始位置与所有草堆不同。
FJ开拖拉机时，只能平行于坐标轴（即东、南、西、北四个方向），而且每次开动的一段必须是整数长度。
例如，他可以向北开2个单位长度，然后向东开3个单位长度。拖拉机不能开到草堆的位置。
请帮助FJ计算出最少要移动多少个草堆，他才能将拖拉机开回坐标原点。
拖拉机可以开到1..1000之外的地方去。
输入
第1行: 3个整数，即N 和拖拉机的初始位置 (x,y)
第2..1+N行: 每行2个整数，表示一堆草的位置 (x,y)
输出
第1行: FJ必须移动的最少的草堆的数量

样例输入
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
样例输出
1
提示
样例说明：拖拉机初始在(6,3)，7堆草分别在 (6,2), (5,2), (4,3), (2,1), (7,3), (5,4), (6,4).
FJ必须移动一堆草

思考

用搜索*8的方法的话看看行不行（上下左右顺逆乱搜）

萎靡不正的AC

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define ll long long
#define clr(x)  memset(x,0,sizeof(x))
#define N 100005
#define NAME "tractor"
#define minn(x,y,z) x=min(x,min(y,z))
using namespace std;
inline void readin(int &res) {static char ch;while ((ch = getchar()) < '0' || ch > '9');res = ch - 48;while ((ch = getchar()) >= '0' && ch <= '9')res = res * 10 + ch - 48;
}
int a[1005][1005];
int dp[1005][1005];
int n,r,c,op;
int ans=INF;
int main(){freopen(NAME".in","r",stdin);freopen(NAME".out","w",stdout);readin(n);readin(r);readin(c);for(int x,y,i=1;i<=n;i++){readin(x);readin(y);a[x][y]=1;}for(int i=0;i<=1001;i++){for(int j=0;j<=1001;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1]);dp[i][j]+=a[i][j];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=1001;i>=0;i--){for(int j=0;j<=1001;j++){dp[i][j]=min(dp[i+1][j],dp[i][j-1]);dp[i][j]+=a[i][j];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=0;i<=1001;i++){for(int j=1001;j>=0;j--){dp[i][j]=min(dp[i-1][j],dp[i][j+1]);dp[i][j]+=a[i][j];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=1001;i>=0;i--){for(int j=1001;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1]);dp[i][j]+=a[i][j];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=0;i<=1001;i++){for(int j=1001;j>=0;j--){dp[j][i]=min(dp[j+1][i],dp[j][i-1]);dp[j][i]+=a[j][i];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=0;i<=1001;i++){for(int j=0;j<=1001;j++){dp[j][i]=min(dp[j-1][i],dp[j][i-1]);dp[j][i]+=a[j][i];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=1001;i>=0;i--){for(int j=1001;j>=0;j--){dp[j][i]=min(dp[j+1][i],dp[j][i+1]);dp[j][i]+=a[j][i];}}ans=min(ans,dp[r][c]);clr(dp);for(int i=1001;i>=0;i--){for(int j=0;j<=1001;j++){dp[j][i]=min(dp[j-1][i],dp[j][i+1]);dp[j][i]+=a[j][i];}}cout<<ans;return 0;
}

时间超级稳定……
AC了……，但是只是数据水，如果出现螺旋结构，就GG（那就加一次dfs，就可以完美AC）

  <testcase status="7" exitcode="0" detail="" time="0.14" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.17" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.15" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.15" memory="8140" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.15" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.14" memory="8140" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.15" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.15" memory="8140" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.17" memory="8416" score="10" /> <testcase status="7" exitcode="0" detail="" time="0.17" memory="8140" score="10" />

怎么说呢……这方法有毒……

sol

Solution Notes: This is a fairly standard shortest path problem, where we wish to find the shortest path from the initial location of the tractor to the outer boundary of the square with coordinates in the range 1..1000. Squares containing haybales cost 1 unit to cross, and all other squares cost 0 units. We could solve this problem using Dijkstra’s algorithm, although the fact that costs are either zero or one allows us to use a slightly different (perhaps slightly simpler) approach using a pair of queues, one containing all the squares we intend to visit that are at distance zero away from our current location, and the other containing a list of all squares we intend to visit that are at distance one away from our current location. We always visit squares from the “zero away” quque, and when this empties out, we refill it with the contents of the “one away” queue. The total running time is therefore linear in the area of the square we are searching.
(小编懒，自行翻译……)

所以真正的方法

#include <cstdio>
#include <queue>using namespace std;struct Point {int x, y;Point (int _x, int _y) { x = _x; y = _y; }Point (void) { x=y=0; }
};queue<Point> zero_away, one_away;
int A[1002][1002], D[1002][1002];int relax(int curx, int cury, int x, int y)
{if (x>=0 && x<=1001 && y>=0 && y<=1001 && (D[x][y]==0 || D[curx][cury]+A[x][y]<D[x][y])) {D[x][y] = D[curx][cury]+A[x][y];if (A[x][y]==0) zero_away.push(Point(x,y));else            one_away.push(Point(x,y));}
}int main(void)
{Point p;int i, n;freopen ("tractor.in", "r", stdin);freopen ("tractor.out", "w", stdout);scanf ("%d %d %d", &n, &p.x, &p.y);D[p.x][p.y] = 1;zero_away.push(p);for (i=0; i<n; i++) {scanf ("%d %d", &p.x, &p.y);A[p.x][p.y] = 1;}while (!zero_away.empty() || !one_away.empty()) {if (zero_away.empty()) while (!one_away.empty()) {zero_away.push(one_away.front()); one_away.pop();}p = zero_away.front(); zero_away.pop();relax(p.x,p.y,p.x-1,p.y);relax(p.x,p.y,p.x+1,p.y);relax(p.x,p.y,p.x,p.y-1);relax(p.x,p.y,p.x,p.y+1);}printf ("%d\n", D[0][0]-1);return 0;
}

这就高级多了，各种松弛与结构体（除非必要，我再也不想用结构体写函数了……）

Landscaping

这里写图片描述
要资源的到这儿
题目描述
N(1 <= N <= 100)个数排成一行，值分别为A_i，现在希望把每个数对应地改成B_i。(A_i,B_i的值均在0..10之间)。改变的方式有3种：
(1)把A_i增加到B_i，每增加1，花费 $X (2)把A_i减少到B_i，每减少1，花费$ Y
(3)把第i个数的值转移到第j个数，每转移1，花费为$Z*|i-j|
问：最小的花费是多少。
输入
第1行：4个整数 N, X, Y, Z (0 <= X, Y, Z <= 1000).
第2..1+N行: 每行2个整数 A_i 和 B_i.
输出
第1行：1个整数，表示最小的花费。

样例输入
4 100 200 1
1 4
2 3
3 2
4 0
样例输出
210
提示
INPUT DETAILS: There are 4 flowerbeds in a row, initially with 1, 2, 3, and 4 units of dirt. Farmer John wishes to transform them so they have 4, 3, 2, and 0 units of dirt, respectively. The costs for adding, removing, and transporting dirt are 100, 200, and 1.
OUTPUT DETAILS: One unit of dirt must be removed (from flowerbed #4), at a cost of 200. The remaining dirt can be moved at a cost of 10 (3 units from flowerbed #4 to flowerbed #1, 1 unit from flowerbed #3 to flowerbed #2).

thought

不想再写dp了，贪心……直接爆……
理应用dp，判断新旧大小用两种状态，关键是转移不好写

题解

Solution Notes: We transform each landscape pattern into an array of length at most 1000 by listing out the locations of the individual units of dirt in the landscape in order. For example, if we have a landscape with heights 3,1,4,1, we would transform this into the sequence 0,0,0,1,2,2,2,2,3 (e.g., there are 4 units of dirt at position 2). Our problem now reduces to something very close to the computation of the “edit distance” between two sequences, which is a classical dynamic programming problem. Our goal is to transform one landscape sequence into another at minimum cost given three possible operations: insertion of a new character (at cost X), deletion of a character (at cost Y), or modification of a character (at cost Z times the magnitude of the change). This can be accomplished in O(N^2) time (where N=1000) using dynamic programming, as shown below. Each subproblem C[i][j] we solve along the way represents the minimum cost of transforming just the first i characters of the source sequence into just the first j characters of the target sequence.
（小编自己都忍不住了，好没有诚意的题解……）

正解

无耻地拷贝何神的代码（比anantheparty的好看多了）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
#define smax(x,tmp) x=max((x),(tmp))
#define smin(x,tmp) x=min((x),(tmp))
#define maxx(x1,x2,x3) max(max(x1,x2),x3)
#define minn(x1,x2,x3) min(min(x1,x2),x3)
typedef long long LL;
template <class T> inline void read(T &x)
{x = 0;T flag = 1;char ch = (char)getchar();while(ch<'0' || ch>'9'){if(ch == '-') flag = -1;ch = (char)getchar();}while(ch>='0' && ch<='9'){x = (x<<1) + (x<<3) + ch - '0';ch = (char)getchar();}x *= flag;
}
template <class T> T gcd(T a,T b) { return !b?a:gcd(b,a%b); }
const int INF=0x3f3f3f3f;
const int maxn = 105;
const int maxd = 2005;
const int base = 1000;
int V;
int a[maxn],b[maxn],delta[maxn];
int n,X,Y,Z;
inline void init()
{read(n);read(X),read(Y),read(Z);for(int i=1;i<=n;i++) read(a[i]),read(b[i]),V+=abs(a[i]-b[i]),delta[i]=b[i]-a[i];
}
int dp[maxn][maxd];
int dynamic()
{memset(dp,0x3f,sizeof(dp));dp[0][base] = 0;for(int i=0;i<n;i++){for(int j=-V;j<=V;j++) smin(dp[i+1][base+j+delta[i+1]],dp[i][base+j]+Z*abs(j));for(int j=V;j>=1;j--){smin(dp[i+1][base+(j-1)],dp[i+1][base+j]+X);smin(dp[i+1][base-(j-1)],dp[i+1][base-j]+Y);}}return dp[n][base];
}
int main()
{freopen("landscaping.in","r",stdin);freopen("landscaping.out","w",stdout);init();int ans = dynamic();printf("%d",ans);return 0;
}

所以迎来了今天的无语编译错误（老*花了一个半小时调的呀！！）

equal

这里写图片描述
（上图为chaos；head【游戏比动漫好】）

【问题描述】
明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
1．表达式只可能包含一个变量‘a’。
2．表达式中出现的数都是正整数，而且都小于10000。
3．表达式中可以包括四种运算‘+’（加），‘-’（减），‘’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）
4．幂指数只可能是1到10之间的正整数（包括1和10）。
5．表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：
((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9……
【输入文件】
输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2 <= n <= 26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……
输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。
【输出文件】
输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

【样例输入】
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
【样例输出】
AC
【数据规模】
对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；
对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。
对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。

opinion

比上两道题都简单的表达式求值，把a值取为绝对值为质数的负数即可。
但是不知为何在cena上编译错误
……不说这些……

题解

算法分析：
用栈的方法求表达式的值是经典的算法。考虑到多项式的处理比较麻烦，不妨对变量a进行多次赋值以判断表达式是否等价。
值得注意，由于进行数值运算，采用哪种数据类型成为程序是否正确的关键。下面的程序，采取mod m的方法，其中m为任意正整数。当对a多次赋值，且m取不同的较大的正整数时，可以保证算法的正确性。
（。。。。没有我的方法优）

骚皮（交份java）

//package noip2005.equal;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;public class Main {public static void main(String[] args) throws Exception{BufferedReader stdin =new BufferedReader(new InputStreamReader(System.in));Polynomial poly = new Evaluator(stdin.readLine()).count();int n = Integer.parseInt(stdin.readLine());for (int i = 0; i < n; i++) {if (poly.equals(new Evaluator(stdin.readLine()).count())){System.out.print((char)('A' + i));}}System.out.println();}
}interface Invariant {int POLY_LEN = 200;int EVA_LEN = 1000;
}class Polynomial {private BigInteger[] v = new BigInteger[Invariant.POLY_LEN];private int length = 0;private void initial() {for (int i = 0; i < Invariant.POLY_LEN; i++) {v[i] = BigInteger.ZERO;}}private void clear() {while(length >= 0 && v[length].equals(BigInteger.ZERO))length--;}Polynomial() {initial();length = -1;}Polynomial(int a) {initial();if (a == 0) {length = 1;v[1] = BigInteger.ONE;}else if (a > 0) {length = 0;v[0] = BigInteger.valueOf(a);}else assert false;}Polynomial add(Polynomial other) {Polynomial ans = new Polynomial();ans.length = Math.max(length, other.length);for (int i = 0; i <= ans.length; i++) {ans.v[i] = v[i].add(other.v[i]);}ans.clear();return ans;}Polynomial subtract(Polynomial other) {Polynomial ans = new Polynomial();ans.length = Math.max(length, other.length);for (int i = 0; i <= ans.length; i++) {ans.v[i] = v[i].subtract(other.v[i]);}ans.clear();return ans;}Polynomial multiply(Polynomial other) {Polynomial ans = new Polynomial();if (length == -1 || other.length == -1) return ans;ans.length = length + other.length;for (int i = 0; i <= length; i++) {for (int j = 0; j <= other.length; j++)ans.v[i + j] = ans.v[i + j].add(v[i].multiply(other.v[j]));}//ans.clear();return ans;}Polynomial pow(int a) {if (length == -1) return new Polynomial();return pow_1(a);}private Polynomial pow_1(int a) {if (a == 0) return new Polynomial(1);if (a == 1) return this;Polynomial ans = pow_1(a / 2);ans = ans.multiply(ans);if (a % 2 == 1) ans = ans.multiply(this);return ans;}boolean equals(Polynomial other) {if (length != other.length) return false;for (int i = 0; i <= length; i++) {if (v[i].equals(other.v[i]) == false) return false;}return true;}int intValue() {assert length == 0;return v[0].intValue();}
}class Evaluator {private String str = null;Polynomial []num = new Polynomial[Invariant.EVA_LEN];int lnum = 0;char []sign = new char[Invariant.EVA_LEN];int lsign = 0;static boolean [][]pos = new boolean[256][256];static{pos['^']['^']=pos['^']['*']=pos['^']['+']=pos['^']['-']=pos['*']['*']=pos['*']['+']=pos['*']['-']=pos['+']['+']=pos['+']['-']=pos['-']['+']=pos['-']['-']=true;}Evaluator(String s) {str = s;}Polynomial count(){lnum=lsign=0;int i;int t;for(i=0; i < str.length(); i++){if (str.charAt(i) == ' ') continue;if (Character.isDigit(str.charAt(i))){t=0;while(i < str.length() && Character.isDigit(str.charAt(i))){t=10*t+str.charAt(i)-'0';i++;}num[lnum++]= new Polynomial(t);i--;}else if(str.charAt(i) == 'a') {num[lnum++]= new Polynomial(0);}else if(str.charAt(i)=='(') {sign[lsign++]='(';}else if(str.charAt(i)=='+'||str.charAt(i)=='-'||str.charAt(i)=='^'||str.charAt(i)=='*'){while(lsign>0&&sign[lsign-1]!='('&&pos[sign[lsign-1]][str.charAt(i)]){if(sign[lsign-1]=='+')num[lnum-2] = num[lnum-2].add(num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = num[lnum-2].subtract(num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = num[lnum-2].multiply(num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = num[lnum-2].pow(num[lnum-1].intValue());lnum--;lsign--;}sign[lsign++]=str.charAt(i);}else if(str.charAt(i)==')'){count_1();}else assert false;}count_1();return num[0];}private void count_1(){while(lsign>0&&sign[lsign-1]!='('){if(sign[lsign-1]=='+')num[lnum-2] = num[lnum-2].add(num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = num[lnum-2].subtract(num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = num[lnum-2].multiply(num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = num[lnum-2].pow(num[lnum-1].intValue());lnum--;lsign--;}if(lsign>0&&sign[lsign-1]=='(')lsign--;}
}

太长了吧…………还是c++友善（虽然跑得慢……）

sol——1

#include <string.h>
#include <iostream.h>
#include <assert.h>
#include <stdio.h>
#include <ctype.h>
#include <string>using  std::string;//using namespace std;inline int MAX(int a,int b) {return a>b?a:b;}const int DIV = 10000;struct bigint1{enum{LEN = 10};int num[LEN];bigint1(){//num = new int[LEN];int i;for(i=0;i<LEN;i++)num[i]=0;}bigint1(const bigint1& a){//num = new int[LEN];int i;for(i=0;i<LEN;i++)num[i]=a.num[i];}bigint1(int a) {//num = new int[LEN];//memset(num, 0, sizeof(num));//assert(a > 0);int i = 0;while(i < LEN) {num[i] = a % DIV;i++;a = a / DIV;}}//~bigint1() { delete[] num;}bigint1& operator=(const bigint1& a){int i;for(i=0;i<LEN;i++)num[i]=a.num[i];return *this;}bigint1 operator+(const bigint1& b) const{bigint1 result;int tot;int i;int add = 0;for(i=0;i<LEN;i++){tot = num[i] + b.num[i] + add;result.num[i] = tot % DIV;add = tot / DIV;}return result;}bigint1 operator*(const bigint1& b) const{bigint1 result;int i, j, tot, add;for(i=0;i<LEN;i++){if(b.num[i]==0)continue;add=0;for(j=0;i + j < LEN;j++){tot=result.num[i+j]+num[j]*b.num[i]+add;result.num[i+j]=tot%DIV;add=tot/DIV;}}return result;}bigint1 operator-(const bigint1& b) const{bigint1 result;int i, sub = 0;for (i = 0; i < LEN; i++) {if (num[i] - sub >= b.num[i]) {result.num[i] = num[i] - sub - b.num[i];sub = 0;}else {result.num[i] = num[i] - sub + DIV - b.num[i];sub = 1;}}return result;}int compare(const bigint1& b) const {int i;for(i = LEN - 1; i >= 0; i--) {if (num[i] != b.num[i]) return num[i] - b.num[i];}return 0;}void print() {bool isp = false;for (int i = LEN - 1; i >=0 ;i--) {if (num[i] != 0) isp = true;if (isp) cout << num[i];}if (!isp) cout << 0;}
};struct bigint {int sign;bigint1 value;bigint(int a):value(a) {sign = 1;}bigint():value() {sign = 1;}void clear() {int i;for (i = 0; i < bigint1::LEN; i++) {if (value.num[i] != 0) break;}if (i == bigint1::LEN) sign = 1;}bigint& operator=(const bigint& b){sign = b.sign;value = b.value;return *this;}bigint operator+(const bigint& b) const{bigint result;if (sign * b.sign == 1) {result.sign = sign;result.value = value + b.value;}else {if (value.compare(b.value) >= 0) {result.sign = sign;result.value = value - b.value;}else {result.sign = b.sign;result.value = b.value - value;}}result.clear();return result;}bigint operator-(const bigint& b) const{bigint temp(b);temp.sign = -b.sign;bigint result = *this + temp;result.clear();return result;}bigint operator*(const bigint& b) const{bigint result;result.value = value * b.value;result.sign = sign * b.sign;result.clear();return result;}bool operator==(const bigint& b) const{if (sign == b.sign) {for (int i = 0; i < bigint1::LEN; i++)if (value.num[i] != b.value.num[i]) return false;return true;}else {return false;}}void print() {if (sign == -1) cout << '-';value.print();}};bool pos[256][256];
bigint ZERO;
bigint ONE(1);const int POLY_LEN = 150;
const int EVA_LEN = 1000;struct Polynomial {bigint* v;int length;void clear() {while(length >= 0 && v[length] == ZERO)length--;}Polynomial() {v = new bigint[POLY_LEN];length = -1;}Polynomial(int a) {v = new bigint[POLY_LEN];if (a == 0) {length = 1;v[1] = ONE;}else if (a > 0) {length = 0;v[0] = bigint(a);}else assert(0);}Polynomial(const Polynomial& other) {v = new bigint[POLY_LEN];length = other.length;int i;for (i = 0; i <= length; i++) v[i] = other.v[i];}Polynomial& operator=(const Polynomial& other) {length = other.length;int i;for (i = 0; i < POLY_LEN; i++) v[i] = other.v[i];return *this;}~Polynomial(){delete[] v;}Polynomial add(Polynomial other) {Polynomial ans;ans.length = MAX(length, other.length);for (int i = 0; i <= ans.length; i++) {ans.v[i] = v[i] + other.v[i];}ans.clear();return ans;}Polynomial subtract(Polynomial other) {Polynomial ans;ans.length = MAX(length, other.length);for (int i = 0; i <= ans.length; i++) {ans.v[i] = v[i] - other.v[i];}ans.clear();return ans;}Polynomial multiply(Polynomial other) {Polynomial ans;if (length == -1 || other.length == -1) return ans;ans.length = length + other.length;assert(ans.length < POLY_LEN);for (int i = 0; i <= length; i++) {for (int j = 0; j <= other.length; j++)ans.v[i + j] = ans.v[i + j] + (v[i] * other.v[j]);}//ans.clear();return ans;}Polynomial pow_1(int a) {if (a == 0) return Polynomial(1);if (a == 1) return *this;Polynomial ans = pow_1(a / 2);ans = ans.multiply(ans);if (a % 2 == 1) ans = ans.multiply(*this);return ans;}Polynomial pow(int a) {if (length == -1) return Polynomial();return pow_1(a);}bool equals(Polynomial other) {if (length != other.length) return false;for (int i = 0; i <= length; i++) {if (!(v[i] == other.v[i])) return false;}return true;}int intValue() {assert(length == 0);return 10 * v[0].value.num[1] + v[0].value.num[0];}void print() {if (length == -1) cout << 0;int i;for (i = length; i >= 0; i--) {v[i].print(); cout << ' ';}}
};struct Evaluator {string str;Polynomial* num;int lnum;char* sign;int lsign;Evaluator(const string s) {str = s;lnum = lsign = 0;num = new Polynomial[EVA_LEN];sign = new char[EVA_LEN];}~Evaluator() {delete[] num; delete[] sign;}Polynomial count(){lnum=lsign=0;int i;int t;for(i=0; i < str.length(); i++){if (str[i] == ' ') continue;if (isdigit(str[i])){t=0;while(i < str.length() && isdigit(str[i])){t=10*t+str[i]-'0';i++;}num[lnum++]= Polynomial(t);i--;}else if(str[i] == 'a') {num[lnum++]= Polynomial(0);}else if(str[i]=='(') {sign[lsign++]='(';}else if(str[i]=='+'||str[i]=='-'||str[i]=='^'||str[i]=='*'){while(lsign>0&&sign[lsign-1]!='('&&pos[sign[lsign-1]][str[i]]){if(sign[lsign-1]=='+')num[lnum-2] = num[lnum-2].add(num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = num[lnum-2].subtract(num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = num[lnum-2].multiply(num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = num[lnum-2].pow(num[lnum-1].intValue());//num[lnum-2].print(); cout << endl;lnum--;lsign--;}sign[lsign++]=str[i];}else if(str[i]==')'){count_1();}else assert(0);}count_1();return num[0];}void count_1(){while(lsign>0&&sign[lsign-1]!='('){if(sign[lsign-1]=='+')num[lnum-2] = num[lnum-2].add(num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = num[lnum-2].subtract(num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = num[lnum-2].multiply(num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = num[lnum-2].pow(num[lnum-1].intValue());//num[lnum-2].print(); cout << endl;lnum--;lsign--;}if(lsign>0&&sign[lsign-1]=='(')lsign--;}
};int main() {pos['^']['^']=pos['^']['*']=pos['^']['+']=pos['^']['-']=pos['*']['*']=pos['*']['+']=pos['*']['-']=pos['+']['+']=pos['+']['-']=pos['-']['+']=pos['-']['-']=true;char buffer[1024];cin.getline(buffer, 1024);Polynomial poly = Evaluator(buffer).count();//poly.print(); cout<< endl;cin.getline(buffer, 1024);int n;sscanf(buffer, "%d", &n);for (int i = 0; i < n; i++) {cin.getline(buffer, 1024);Polynomial temp = Evaluator(buffer).count();//temp.print();cout<< endl;if (poly.equals(temp)) cout << char('A' + i);}cout << endl;return 0;
}

打脸，怎么比java长这么多……
420行……这标答也是够了……
重新来一次……

sol——2

#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>char obj[200];
char data[30][200];void change(char *a) {int i, j;for (i = 0; a[i] != 0; i++) {if (isalpha(a[i])) assert(a[i] == 'a');if (isdigit(a[i]) && a[i + 1] == ' ') {for (j = i + 2; a[j] != 0; j++) {if (a[j] != ' ') break;}assert(!isdigit(a[j]));}}for (i = j = 0; a[i] != 0; i++) {if (!isspace(a[i])) {a[j] = a[i];j++;}}a[j] = 0;
}int pp[30];bool pos[130][130];int num[1000];
int lnum;
char sign[1000];
int lsign;int divide;inline int add(int a, int b) {return (a + b) % divide;
}inline int sub(int a, int b) {return (a - b + divide) % divide;
}inline int mul(int a, int b) {return a * b % divide;
}inline int sqr(int a, int b) {assert(1 <= b && b <= 10);if (b == 0) return 1;if (b == 1) return a;int c = b / 2;int d = sqr(a, c);d = (d * d) % divide;if (2 * c != b) d = d * a % divide;return d;
}void count(){while(lsign>0&&sign[lsign-1]!='('){if(sign[lsign-1]=='+')num[lnum-2] = add(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = sub(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = mul(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = sqr(num[lnum-2], num[lnum-1]);lnum--;lsign--;}if(lsign>0&&sign[lsign-1]=='(')lsign--;
}int count(char* a){lnum=lsign=0;int i;int t;for(i=0;a[i]!=0;i++){if(isdigit(a[i])){t=0;assert(a[i] != 0);while(isdigit(a[i])){t=10*t+a[i]-'0';assert(0 < t && t < 10000);i++;}t = t % divide;num[lnum++]=t;i--;assert(a[i + 1] == 0 || a[i + 1] == '+' || a[i + 1] == '*' ||a[i + 1] == '-' || a[i + 1] == '^' || a[i + 1] == ')');}else if(isalpha(a[i])) {assert(islower(a[i]));assert(a[i + 1] == 0 || a[i + 1] == '+' || a[i + 1] == '*' ||a[i + 1] == '-' || a[i + 1] == '^' || a[i + 1] == ')');num[lnum++]=pp[a[i]-'a'];}else if(a[i]=='(') {assert(isdigit(a[i + 1]) || isalpha(a[i + 1]) || a[i + 1] == '(');sign[lsign++]='(';}else if(a[i]=='+'||a[i]=='-'||a[i]=='^'||a[i]=='*'){assert(isdigit(a[i + 1]) || isalpha(a[i + 1]) || a[i + 1] == '(');if (a[i] == '^') assert(isdigit(a[i + 1]));while(lsign>0&&sign[lsign-1]!='('&&pos[sign[lsign-1]][a[i]]){if(sign[lsign-1]=='+')num[lnum-2] = add(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='-')num[lnum-2] = sub(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='*')num[lnum-2] = mul(num[lnum-2], num[lnum-1]);else if(sign[lsign-1]=='^')num[lnum-2] = sqr(num[lnum-2], num[lnum-1]);lnum--;lsign--;}sign[lsign++]=a[i];}else if(a[i]==')'){assert(a[i + 1] == 0 || a[i + 1] == '+' || a[i + 1] == '*' ||a[i + 1] == '-' || a[i + 1] == '^' || a[i + 1] == ')');count();}else assert(0);}count();assert(lsign==0 && lnum==1);return num[0];
}int equal[30];int n;void issame(){int t=100,i,j;int a,b;for(i=0;i<t;i++){divide = rand() % 10000 + 100;for(j=0;j<26;j++)pp[j] = rand() % divide;a=count(obj);for (j = 0; j < n; j++) {if (equal[j]) {if (count(data[j]) != a) equal[j] = 0;}}}
}void solve(){cin.getline(obj,200);assert(1 <= strlen(obj) && strlen(obj) <= 50);change(obj);int i;cin >> n;assert(2 <= n && n <= 26);cin.ignore(200, '\n');for (i = 0; i < n; i++) {cin.getline(data[i], 200);//cerr << data[i] << endl;assert(1 <= strlen(data[i]));assert(strlen(data[i]) <= 50);change(data[i]);}{char c; assert(!(cin >> c));}memset(equal, -1, sizeof(equal));issame();for (i = 0; i < n; i++) {if (equal[i]) cout << char('A' + i);}cout << endl;
}int main(){//frist >= secondpos['^']['^']=pos['^']['*']=pos['^']['+']=pos['^']['-']=pos['*']['*']=pos['*']['+']=pos['*']['-']=pos['+']['+']=pos['+']['-']=pos['-']['+']=pos['-']['-']=true;solve();return 0;
}

壮哉我c++，这才对嘛……

sol——3

自己改进的代码，虽然还是莫名报错……

#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<iostream>
#define NAME "equal4"
#define ll long long
#define N 10005
using namespace std;
char s[N];
ll number[N],i,p=1;
char symbol[N];
void push(){symbol[++p]=s[i];
}
ll mf(int x,int y){if(y==1)return x;return x*mf(x,y-1);
}
void pop(){       switch (symbol[p--]){case '+':number[p]+=number[p+1];break;case '-':number[p]-=number[p+1];break;case '*':number[p]*=number[p+1];break;case '^':number[p]=mf(number[p],number[p+1]);break;}
}
bool can(){if((s[i]=='+'||s[i]=='-')&&symbol[p]!='(')return 1;if((s[i]=='*')&&(symbol[p]=='*'||symbol[p]=='^'))return 1;return 0;
}
int str(char t[]){int len=strlen(t);return len;
}
ll work(){s[str(s)]=')';symbol[p]='(';while (i<str(s)){while (s[i]=='('){push();i++;}int x=0;if(s[i]=='a'){x=-23;i++;}elsewhile (s[i]>='0'&&s[i]<='9')x=x*10+s[i++]-'0';number[p]=x;do{if (s[i]==')'){while (symbol[p]!='(')pop();--p;number[p]=number[p+1];}else{while(can())pop();push();}i++;}while (i<str(s)&&s[i-1]==')');}return number[0];
}
int main(){freopen(NAME".in","r",stdin);freopen("equal.out","w",stdout);int n;for(int q=0;q<=1000;q++){s[q]=symbol[q]=number[q]=0;}scanf("%s",s);int bd=work();cin>>n;for(int j=0;j<n;j++){for(int q=0;q<=1000;q++){s[q]=symbol[q]=number[q]=0;}scanf("%s",s);i=0,p=1;char ch='A';ll ans=work();if(ans==bd){ch+=j;cout<<ch;}}return 0;
}