node.js 做网站,淘宝上网站开发,公众号页面设计,玉溪建设网站传送门
题意#xff1a;给定n个点#xff0c;m个操作#xff0c;n和m都是1e5级别的。让后每个操作是将这个点绕原点顺时针、逆时针转90#xff0c;将这个点按照 x p 或着 y p 做对称。再有q个询问#xff0c;q也是1e5级别的。让后每个询问是问B这个点在第A次操作之后在…传送门
题意给定n个点m个操作n和m都是1e5级别的。让后每个操作是将这个点绕原点顺时针、逆时针转90°将这个点按照 x p 或着 y p 做对称。再有q个询问q也是1e5级别的。让后每个询问是问B这个点在第A次操作之后在哪里。
显然我们不能直接暴力因为都达到了1e5级别。 一开始像找一下规律看看是否这几个操作是相互独立的一开始发现了点但是随着越来越多的例子很快否定了我找规律的想法。 现在问题就是我们能否将点的变换转变成类似乘法除法之类可以累计的变量呢显然就会发现矩阵是满足这个性质的我们只需要对每个操作递推维护一个右乘矩阵当需要进行前A次操作的时候只需要乘一下A这个操作之前的矩阵乘积即可。 下面依次给出这几个操作的矩阵。 当然为了方便我们可以把初始矩阵写成 (xy1)\begin{pmatrix} x y 1\\ \end{pmatrix} (xy1) (0−10100001)\begin{pmatrix} 0 -1 0 \\ 1 0 0 \\ 0 0 1 \end{pmatrix} ⎝⎛010−100001⎠⎞ (010−100001)\begin{pmatrix} 0 1 0 \\ -1 0 0 \\ 0 0 1 \end{pmatrix} ⎝⎛0−10100001⎠⎞ (−1000102p01)\begin{pmatrix} -1 0 0 \\ 0 1 0 \\ 2p 0 1 \end{pmatrix} ⎝⎛−102p010001⎠⎞ (1000−1002p1)\begin{pmatrix} 1 0 0 \\ 0 -1 0 \\ 0 2p 1 \end{pmatrix} ⎝⎛1000−12p001⎠⎞ 为什么多加了一维呢想必看到上面矩阵的时候大家也知道了因为对称的时候会多一个常数所以加一维比较方便处理常数。 下面代码仅供参考写的比较乱
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
struct Point
{int x,y;
}q[N];
struct Query
{LL mp[3][3];
}node[N],t;
vectorQueryv;void mult(int id,Query v,int op)
{int x;if(op3||op4) scanf(%d,x);if(op3) v.mp[2][0]2*x;else if(op4) v.mp[2][1]2*x;for(int i0;i3;i)for(int j0;j3;j)for(int k0;k3;k)node[id1].mp[i][j]node[id].mp[i][k]*v.mp[k][j];
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);t.mp[0][0]0; t.mp[0][1]-1; t.mp[0][2]0;t.mp[1][0]1; t.mp[1][1]0; t.mp[1][2]0;t.mp[2][0]0; t.mp[2][1]0; t.mp[2][2]1;v.push_back(t);t.mp[0][0]0; t.mp[0][1]1; t.mp[0][2]0;t.mp[1][0]-1; t.mp[1][1]0; t.mp[1][2]0;t.mp[2][0]0; t.mp[2][1]0; t.mp[2][2]1;v.push_back(t);t.mp[0][0]-1; t.mp[0][1]0; t.mp[0][2]0;t.mp[1][0]0; t.mp[1][1]1; t.mp[1][2]0;t.mp[2][0]0; t.mp[2][1]0; t.mp[2][2]1;v.push_back(t);t.mp[0][0]1; t.mp[0][1]0; t.mp[0][2]0;t.mp[1][0]0; t.mp[1][1]-1; t.mp[1][2]0;t.mp[2][0]0; t.mp[2][1]0; t.mp[2][2]1;v.push_back(t);scanf(%d,n);for(int i1;in;i) scanf(%d%d,q[i].x,q[i].y);scanf(%d,m);node[0].mp[0][0]node[0].mp[1][1]node[0].mp[2][2]1;for(int i1;im;i){int op; scanf(%d,op);mult(i-1,v[op-1],op);}int _; scanf(%d,_);while(_--){int a,b; scanf(%d%d,a,b);Query t,ans;memset(t.mp,0,sizeof(t.mp));memset(ans.mp,0,sizeof(ans.mp));t.mp[0][0]q[b].x,t.mp[0][1]q[b].y,t.mp[0][2]1;for(int i0;i3;i)for(int j0;j3;j)for(int k0;k3;k)ans.mp[i][j]t.mp[i][k]*node[a].mp[k][j];printf(%lld %lld\n,ans.mp[0][0],ans.mp[0][1]);}return 0;
}
/**/
