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

202309-2

news 2025/8/9 5:39:13

http://118.190.20.162/view.page?gpid=T174

题目分析：

这道题读完题后感觉像是考察前缀和，这里回顾下什么是前缀和：https://blog.csdn.net/weixin_45629285/article/details/111146240
在这里插入图片描述

我们利用前缀和算法，就可以在O(n+m)的时间内完成。

具体分析一下怎么套前缀和模板；
我们只要画个图，就可以发现
在这里插入图片描述
每次旋转的角度和扩大的倍数这两个操作，是彼此独立的，因此我们可以用两个前缀和数组，sum1和sum2，分别记录拉伸k倍和旋转。

代码如下：

#include <iostream>
#include <cmath>using namespace std;const int MAXN = 1e6+5;double k[MAXN] = {1};
double theta[MAXN] = {0.0};
double sumk[MAXN];
double sumTheta[MAXN] = {0};int main() {for (int i = 0;i < MAXN;i++)k[i] = 1,sumk[i] = 1;
//    std::cout << "Hello, World!" << std::endl;int n, m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){int op;scanf("%d",&op);if(op == 1){scanf("%lf", &k[i]);}else{scanf("%lf",&theta[i]);}sumk[i] = sumk[i-1]*k[i];
//        printf("%f",sumk[i]);sumTheta[i] = sumTheta[i - 1] + theta[i];}for(int i = 1; i <= m; ++i){int l, r, x, y;scanf("%d%d%d%d",&l,&r,&x,&y);double tx, ty;double tk = sumk[r] / sumk[l - 1];double ttheta = sumTheta[r] - sumTheta[l - 1];tx = tk * x;ty = tk * y;double ansx, ansy;ansx = tx * cos(ttheta) - ty * sin(ttheta);ansy = tx * sin(ttheta) + ty * cos(ttheta);printf("%f %f\n", ansx, ansy);}return 0;}