CSP认证2023-09：坐标变换(其一)、坐标变换（其二）、梯度求解，python满分代码解答
目录
一、坐标变换（其一）
问题描述
输入和输出
思路
代码和结果
c++代码
python代码
二、坐标变换（其二）
问题描述
输入和输出
思路
代码和结果
c++代码
编辑 python代码
改进
c++代码
python代码
三、梯度求解
问题描述
输入和输出
思路
代码和结果
一、坐标变换（其一）
问题描述
输入和输出
输入
3 2
10 10
0 0
10 -20
1 -1
0 0输出
21 -11
20 -10思路
定义一个起始原点坐标(0,0)，将n个操作依次累加，获得移动后的坐标(x_move,y_move)。接着输入m行坐标(x_res,y_res)时，直接加上移动后的坐标(x_move,y_move)输出结果即可。
代码和结果
c++代码
#include<iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int move_x = 0;
int move_y = 0;
for (int i = 0; i < n; i++) {//m行数据
int x,y;
cin >> x>>y;
move_x += x;
move_y += y;
}
for (int j = 0; j < m; j++) {
int input_x, input_y;
cin >> input_x >> input_y;
cout << input_x + move_x << " " << input_y + move_y << endl;
}
}
python代码
n,m=list(map(int,input().split()))
x_move ,y_move= 0,0
for i in range(n):
x_1,y_1 = list(map(int,input().split()))
x_move+=x_1
y_move+=y_1
for j in range(m):
x_res, y_res = list(map(int, input().split()))
x_res += x_move
y_res += y_move
print(x_res,' ',y_res)
二、坐标变换（其二）
问题描述
输入和输出
输入
10 5
2 0.59
2 4.956
1 0.997
1 1.364
1 1.242
1 0.82
2 2.824
1 0.716
2 0.178
2 4.094
1 6 -953188 -946637
1 9 969538 848081
4 7 -114758 522223
1 9 -535079 601597
8 8 159430 -511187输出
-1858706.758 -83259.993
-1261428.46 201113.678
-75099.123 -738950.159
-119179.897 -789457.532
114151.88 -366009.892思路
1、首先将利用两个数组op和value将操作和其对应的值存起来
2、在输入每一个查询时，找到数组op和value的起始位置和终止位置
3、从起始位置和终止位置进行运算即可
代码和结果
这里给出c++代码和python代码
c++代码
#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
int main(){
cout.setf(ios::fixed);
cout.precision(3); // 精度为输出小数点后3位
int n, m;
cin >> n >> m;
static int op[100001];
static double value[100001];
for (int i = 1; i <= n; i++) {
int op1;
double value1;
cin >> op1 >> value1;
op[i] = op1;
value[i] = value1;
}
for (int j = 0; j < m; j++) {
int op_start, op_end;
double value1, value2;
cin >> op_start >> op_end >> value1 >> value2;
for (int op_index = op_start; op_index <= op_end; op_index++) {
//对于第op_index进行以下操作
int operation1 = op[op_index];//进行缩放或旋转
double v1 = value[op_index];//
if (operation1 == 1) {
value1 = value1 * v1;
value2 = value2 * v1;
}
else {
double value1_copy = value1;
value1 = value1 * cos(v1) - value2 * sin(v1);
value2 = value1_copy * sin(v1) + value2 * cos(v1);
}
}
cout <<value1 << " " << value2 << endl;
}
}
python代码
import math
n,m = list(map(int,input().split()))
op = [0]
value = [0.]
for i in range(1,n+1):
operate, v = input().split()
op.append(int(operate))
value.append(float(v))
for i in range(m):
op_start_s,op_end_s,value1_s,value2_s= input().split()
op_start = int(op_start_s)
op_end = int(op_end_s)
value1 = float(value1_s)
value2 = float(value2_s)
for j in range(op_start,op_end+1):
#对于第op_index进行以下操作
operation1 = op[j] # 进行缩放或旋转
v1 = value[j]
if operation1 == 1:
value1 = value1 * v1
value2 = value2 * v1
else:
value1_copy = value1 #这一步很重要
value1 = value1 * math.cos(v1) - value2 * math.sin(v1)
value2 = value1_copy * math.sin(v1) + value2 * math.cos(v1)
print(value1,' ',value2)
改进
然而由于查询过程中存在重复的查询，导致时间复杂度过高而只得到了80分。
通过观察发现，题目让我们求的是给定坐标经过op_start到op_end操作之后的结果，又通过操作内容可知，只包含旋转和坐标缩放这两种操作。从中可以得到以下结论：
首先，这两种操作是不受彼此干扰的；其次，旋转和缩放是可以累积计算的。
因此，我们可以通过两个数组记录从1到n个操作的结果，每一步操作是旋转操作和缩放操作的累积。首先计算从op_start到op_end旋转的角度，只需要用op_end旋转的角度减去op_start的角度；其次计算从op_start到op_end缩放的倍数，只需要用op_end缩放的倍数除以op_start缩放的倍数。
c++代码
//存在的问题：考虑到不能每次去遍历操作，因为这样会导致复杂度很高
//解决办法：将操作数组记录下来，因为缩放和旋转是无关的，所以可以使用两个数组存放；旋转是循环的可以实现累加，缩放也是可以累乘的
#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
#define pai 3.14159265358979323846
int main() {
cout.setf(ios::fixed);
cout.precision(3); // 精度为输出小数点后3位
int n, m;
cin >> n >> m;
//static int op_scale[100001];//分开存放两个操作
//static int op_xuanzhuan[100001];
static double value_scale[100001]={1};
static double value_xuanzhuan[100001]={0};
//累积缩放值
double scale = 1;
//累积旋转值，需要mod 2pai
double xuanzhuan = 0;
for (int i = 1; i <= n; i++) {//现在存放的就不是第i个操作了，而是前i个操作的累积
int op1;
double value1;
cin >> op1 >> value1;
if (op1 == 1) {
//同时记录到上一轮的旋转
value_xuanzhuan[i] = xuanzhuan;
scale = scale * value1;
value_scale[i] = scale;
}
else {
//同时记录到上一轮的缩放
value_scale[i] = scale;
xuanzhuan = xuanzhuan + value1;//先不用取余，最后结果取余就行
value_xuanzhuan[i] = xuanzhuan;
}
}
for (int j = 0; j < m; j++) {
int op_start, op_end;
double value1, value2;
cin >> op_start >> op_end >> value1 >> value2;
//看op_start的缩放是多少，op_end的缩放系数是多少，除一下就是缩放的系数了
double op_scale_start = value_scale[op_start-1];
double op_scale_end = value_scale[op_end];
double op_xuanzhuan_start = value_xuanzhuan[op_start-1];
double op_xuanzhuan_end = value_xuanzhuan[op_end];
//首先计算缩放了多少
double scale_start_end = op_scale_end / op_scale_start;
double xuanzhuan_start_end = fmod((op_xuanzhuan_end - op_xuanzhuan_start), 2 * pai);//op_xuanzhuan_start操作也是进行的
double value1_copy = value1;
value1 = scale_start_end*(value1 * cos(xuanzhuan_start_end) - value2 * sin(xuanzhuan_start_end));
value2 = scale_start_end*(value1_copy * sin(xuanzhuan_start_end) + value2 * cos(xuanzhuan_start_end));
cout << value1 << " " << value2 << endl;
}
return 0;
}
python代码
import math
n,m = list(map(int,input().split()))
#累积缩放值
scale = 1
#累积旋转值，需要mod 2pai
xuanzhuan = 0
value_scale = [1]
value_xuanzhuan = [0]
for i in range(1,n+1):#现在存放的就不是第i个操作了，而是前i个操作的累积
op1_,value1_ = input().split()
op1 = int(op1_)
value1 = float(value1_)
if op1 == 1:
#同时记录到上一轮的旋转
value_xuanzhuan.append(xuanzhuan)
scale = scale * value1
value_scale.append(scale)
else:
#同时记录到上一轮的缩放
value_scale.append(scale)
xuanzhuan = xuanzhuan + value1#先不用取余，最后结果取余就行
value_xuanzhuan.append(xuanzhuan)
for j in range(m):
op_start_s, op_end_s, value1_s, value2_s = input().split()
op_start = int(op_start_s)
op_end = int(op_end_s)
value1 = float(value1_s)
value2 = float(value2_s)
#看op_start的缩放是多少，op_end的缩放系数是多少，除一下就是缩放的系数了
op_scale_start = value_scale[op_start-1]
op_scale_end = value_scale[op_end]
op_xuanzhuan_start = value_xuanzhuan[op_start-1]
op_xuanzhuan_end = value_xuanzhuan[op_end]
#首先计算缩放了多少
scale_start_end = op_scale_end / op_scale_start
xuanzhuan_start_end = (op_xuanzhuan_end - op_xuanzhuan_start)%(2 * math.pi)#op_xuanzhuan_start操作也是进行的
value1_copy = value1
value1 = scale_start_end*(value1 * math.cos(xuanzhuan_start_end) - value2 * math.sin(xuanzhuan_start_end))
value2 = scale_start_end*(value1_copy * math.sin(xuanzhuan_start_end) + value2 * math.cos(xuanzhuan_start_end))
print(value1, ' ', value2)三、梯度求解
问题描述
输入和输出
输入
2 2
x1 x1 x1 * x2 + *
1 2 3
2 3 4输出
15
3思路
本题是一道求偏导的题，计算过程很清晰，但是实现起来还是比较麻烦的。接下来简要介绍一下代码的思路：
1、首先，对于每一次输入，将每一个自变量的值存储起来，注：将逆波兰式的多项式使用copy()进行复制，防止后续操作修改了其中的内容。
for _ in range(m): data = list(map(int,input().split())) bianliang_j = data[0] poly_copy_list = poly_list.copy() value_list = data[1:]#从自变量1到自变量n的值 bianliang_value_dict = {}#变量值字典 for i in range(len(value_list)): if i+1!=int(bianliang_j): x_i = 'x'+str(i+1) bianliang_value_dict[x_i] = str(value_list[i]) else: bianliang_j_value = int(value_list[i])2、将多项式中的不要求偏导的自变量替换成其值，这样就仅包含一个自变量，可以使用字典存储多项式。
#复制多项式，将多项式中的不要求偏导的自变量替换成其值 for i in range(len(poly_copy_list)): if poly_copy_list[i] in bianliang_value_dict.keys(): poly_copy_list[i]=bianliang_value_dict[poly_copy_list[i]]class mul_poly():#对于一个仅包含一个变量的多项式，仅存储其系数和次数即可，但是考虑到稀疏性，得用字典来存储 def __int__(self): self.poly = {}#键表示的是多项式的次数，值表示系数3、开始处理偏导，因为逆波兰式可能只有一项（数值或变量），需要判断一下。如果只有一项，直接用字典形式表示多项式；否则利用栈读取逆波兰式。
- 在处理逆波兰式时，为了简化运算符的判断，将减法用加法、乘法、系数-1进行表示。
- 字典形式的多项式的计算方法为： 在乘法中，两重循环多项式a和多项式b的次数项（键），进行次数（键）相加，系数（值）相乘的操作；多项式加法为，单次循环多项式b的次数（键），如果多项式a中没有，则将多项式b的键值对添加到多项式a中；否则将多项式b的系数（值）和多项式a的系数（值）作和，即可完成加法运算。
if len(poly_copy_list)==1:#只含一个数值或变量 temp = trans_mul_poly(poly_copy_list[0]).poly else: temp = piandao(poly_copy_list)def piandao(poly): ''' :param -poly: 列表形式的多项式 :return: ''' new_poly = [] for ele in poly:#a-b = a+ （-1 *）b 减法运算变成加法和乘法 if ele=='-':#处理减法运算 new_poly.append('-1') new_poly.append('*') new_poly.append('+') else: new_poly.append(ele) poly_stack =[] # #创建一个多项式字典，用以记录多项式加法和乘法的计算结果 #通过逆波兰式读取结果 for ele in new_poly: if ele not in ['+','*']:#如果不是运算符，则加入poly_stack中 poly_stack.append(ele) else: b = poly_stack.pop() a = poly_stack.pop() #a和b初始只可能是 数值（可正可负）、自变量x_1 、之后存在(x_1的多项式) b_mul_poly = trans_mul_poly(b) a_mul_poly = trans_mul_poly(a)#转换成mul_poly对象 res = compute(a_mul_poly,b_mul_poly,ele) poly_stack.append(res) result = poly_stack.pop() return result.polydef compute(a_mul_poly,b_mul_poly,ele): ''' :param a_mul_poly: :param b_mul_poly: :param ele: 运算符，取值为"+"或"*" :return: ''' if ele=='*': res = mul_poly() res.poly = {} #对应位置的系数相乘 for a in a_mul_poly.poly.keys(): for b in b_mul_poly.poly.keys(): # 次数相加，系数相乘 a_b_sum_cishu = a+b a_b_sum_xishu = a_mul_poly.poly[a]*b_mul_poly.poly[b] if a_b_sum_cishu not in res.poly.keys(): res.poly[a_b_sum_cishu] = a_b_sum_xishu else: res.poly[a_b_sum_cishu] += a_b_sum_xishu return res else: # 对应位置的系数相加 for b_cishu in b_mul_poly.poly.keys(): if b_cishu not in a_mul_poly.poly.keys(): a_mul_poly.poly[b_cishu] = b_mul_poly.poly[b_cishu] else: a_mul_poly.poly[b_cishu] += b_mul_poly.poly[b_cishu] return a_mul_poly4、获得结果
res = 0 for key in temp.keys():#键为多项式次数，值为系数 if key == 0:#常数项求偏导为0 continue elif key == 1: #存在0的0次方 res+=temp[key] else: res+=key*temp[key]*bianliang_j_value**(key-1) print(int(res%(10**9+7)))
代码和结果
class mul_poly():#对于一个仅包含一个变量的多项式，仅存储其系数和次数即可，但是考虑到稀疏性，得用字典来存储
def __int__(self):
self.poly = {}#键表示的是多项式的次数，值表示系数
def compute(a_mul_poly,b_mul_poly,ele):
'''
:param a_mul_poly:
:param b_mul_poly:
:param ele: 运算符，取值为"+"或"*"
:return:
'''
if ele=='*':
res = mul_poly()
res.poly = {}
#对应位置的系数相乘
for a in a_mul_poly.poly.keys():
for b in b_mul_poly.poly.keys():
# 次数相加，系数相乘
a_b_sum_cishu = a+b
a_b_sum_xishu = a_mul_poly.poly[a]*b_mul_poly.poly[b]
if a_b_sum_cishu not in res.poly.keys():
res.poly[a_b_sum_cishu] = a_b_sum_xishu
else:
res.poly[a_b_sum_cishu] += a_b_sum_xishu
return res
else:
# 对应位置的系数相加
for b_cishu in b_mul_poly.poly.keys():
if b_cishu not in a_mul_poly.poly.keys():
a_mul_poly.poly[b_cishu] = b_mul_poly.poly[b_cishu]
else:
a_mul_poly.poly[b_cishu] += b_mul_poly.poly[b_cishu]
return a_mul_poly
def trans_mul_poly(data):#将数据转成mul_poly对象
if isinstance(data,mul_poly):
return data
else:
res = mul_poly()
res.poly = {}
if 'x' in data:#是x自变量
res.poly[1] = 1
else:#是数值
res.poly[0]=int(float(data)%(10**9+7))
return res
def piandao(poly):
'''
:param
-poly: 列表形式的多项式
:return:
'''
new_poly = []
for ele in poly:#a-b = a+ （-1 *）b 减法运算变成加法和乘法
if ele=='-':#处理减法运算
new_poly.append('-1')
new_poly.append('*')
new_poly.append('+')
else:
new_poly.append(ele)
poly_stack =[]
# #创建一个多项式字典，用以记录多项式加法和乘法的计算结果
#通过逆波兰式读取结果
for ele in new_poly:
if ele not in ['+','*']:#如果不是运算符，则加入poly_stack中
poly_stack.append(ele)
else:
b = poly_stack.pop()
a = poly_stack.pop()
#a和b初始只可能是 数值（可正可负）、自变量x_1 、之后存在(x_1的多项式)
b_mul_poly = trans_mul_poly(b)
a_mul_poly = trans_mul_poly(a)#转换成mul_poly对象
res = compute(a_mul_poly,b_mul_poly,ele)
poly_stack.append(res)
result = poly_stack.pop()
return result.poly
n,m=list(map(int,input().split()))
poly_list = input().split()
for _ in range(m):
data = list(map(int,input().split()))
bianliang_j = data[0]
poly_copy_list = poly_list.copy()
value_list = data[1:]#从自变量1到自变量n的值
bianliang_value_dict = {}#变量值字典
for i in range(len(value_list)):
if i+1!=int(bianliang_j):
x_i = 'x'+str(i+1)
bianliang_value_dict[x_i] = str(value_list[i])
else:
bianliang_j_value = int(value_list[i])
#复制多项式，将多项式中的不要求偏导的自变量替换成其值
for i in range(len(poly_copy_list)):
if poly_copy_list[i] in bianliang_value_dict.keys():
poly_copy_list[i]=bianliang_value_dict[poly_copy_list[i]]
if len(poly_copy_list)==1:#只含一个数值或变量
temp = trans_mul_poly(poly_copy_list[0]).poly
else:
temp = piandao(poly_copy_list)
res = 0
for key in temp.keys():#键为多项式次数，值为系数
if key == 0:#常数项求偏导为0
continue
elif key == 1: #存在0的0次方
res+=temp[key]
else:
res+=key*temp[key]*bianliang_j_value**(key-1)
print(int(res%(10**9+7)))
