首页 > 其他分享 >2023省选武汉联测7

2023省选武汉联测7

时间：2023-04-20 21:14:53浏览次数：40  
标签：include Matrix 省选 mid int 联测 2023 now ql

T1 动点 (point)

首先考虑两种操作，根据高中计算几何知识很容易得到这两种变换后点的坐标，首先考虑 \(1\) 操作，假设旋转中心 \(P\) 为原点，考虑将点 \(A(x_0,y_0)\) 绕点旋转 \(\alpha\) 到 \(B\) ，设 \(\overrightarrow{OA}\) 与 \(x\) 轴的夹角为 \(\beta\) ，如下图：

设 \(\mid\overrightarrow{OA}\mid=\mid\overrightarrow{OB}\mid=L\) ，比较显然 \(\overrightarrow{OA}=(\cos\beta L, \sin\beta L),\overrightarrow{OB}=(\cos(\alpha+\beta)L,\sin(\alpha+\beta)L)\) ，简单化简一下发现 \(\overrightarrow{OA}=(\cos\alpha x_0-\sin\alpha y_0,\sin\alpha x_0+\cos\alpha y_0)\) ，旋转中心不为原点的情况简单平移一下即可。

其次考虑操作二，设直线为 \(Ax+By+C=0\) ，直线的方向向量为 \(\vec{\alpha}\) ，设操作的点 \(P=(x_0,y_0)\) ，设操作后点移动到了 \(Q(x,y)\) ，容易发现其满足一下关系：

\[\begin{cases} Ax+By+C=0\\ \overrightarrow{PQ}\cdot\vec{\alpha}=0 \end{cases} \]

简单解方程可以得到：

\[\begin{cases} x=\tfrac{B^2x_0-ABy_0-AC}{A^2+B^2}\\ y=\tfrac{A^2y_0-ABx_0-BC}{A^2+B^2} \end{cases} \]

发现这两种操作都是线性变换，对于没有修改的操作可以直接用线段树维护矩阵乘，考虑加入修改，对于第一种操作，容易发现我们将操作点 \(P\) 向 \((-u,-v)\) 平移后进行操作，之后在平移回来，很容易用线段树维护，对于第二种操作，同样将操作点关于 \(Ax+By+C=0\) 对称，操作后在对称回去，需要注意的是，对称后原先的逆时针旋转变成了顺时针旋转，在线段树维护两个旋转方向的矩阵即可。

code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int max1 = 1e5;
const long double pi = acos(-1);
int n, m;
struct Option
    { int opt, A, B, C; } g[max1 + 5];
struct Matrix
{
    long double matrix[3][3];
    void Identity ()
    {
        for ( int i = 0; i < 3; i ++ )
            for ( int j = 0; j < 3; j ++ )
                matrix[i][j] = i == j;
        return;
    }
    Matrix operator * ( const Matrix &A ) const
    {
        Matrix res;
        for ( int i = 0; i < 3; i ++ )
        {
            for ( int j = 0; j < 3; j ++ )
            {
                res.matrix[i][j] = 0;
                for ( int k = 0; k < 3; k ++ )
                    res.matrix[i][j] += matrix[i][k] * A.matrix[k][j];
            }
        }
        return res;
    }
};
struct Segment_Tree
{
    #define lson(now) ( now << 1 )
    #define rson(now) ( now << 1 | 1 )
    struct Struct_Segment_Tree
        { Matrix sum1, sum2, lazyl, lazyr; bool rev; } tree[max1 * 4 + 5];
    void Push_Up ( int now )
    {
        tree[now].sum1 = tree[rson(now)].sum1 * tree[lson(now)].sum1;
        tree[now].sum2 = tree[rson(now)].sum2 * tree[lson(now)].sum2;
        return;
    }
    void Update1 ( int now, const Matrix &A, const Matrix &B )
    {
        tree[now].sum1 = B * tree[now].sum1 * A;
        tree[now].sum2 = B * tree[now].sum2 * A;
        tree[now].lazyl = tree[now].lazyl * A;
        tree[now].lazyr = B * tree[now].lazyr;
        return;
    }
    void Update2 ( int now )
    {
        swap(tree[now].sum1, tree[now].sum2);
        tree[now].rev ^= 1;
        return;
    }
    void Push_Down ( int now )
    {
        Update1(lson(now), tree[now].lazyl, tree[now].lazyr);
        Update1(rson(now), tree[now].lazyl, tree[now].lazyr);
        tree[now].lazyl.Identity();
        tree[now].lazyr.Identity();
        if ( tree[now].rev )
        {
            Update2(lson(now));
            Update2(rson(now));
            tree[now].rev = false;
        }
        return;
    }
    void Build ( int now, int l, int r )
    {
        tree[now].lazyl.Identity();
        tree[now].lazyr.Identity();
        tree[now].rev = false;
        if ( l == r )
        {
            if ( g[l].opt == 1 )
            {
                long double alpha = pi * g[l].C / 1800;
                long double c = cos(alpha), s = sin(alpha), x0 = g[l].A, y0 = g[l].B;
                tree[now].sum1.matrix[0][0] = c, tree[now].sum1.matrix[0][1] = -s, tree[now].sum1.matrix[0][2] = -c * x0 + s * y0 + x0;
                tree[now].sum1.matrix[1][0] = s, tree[now].sum1.matrix[1][1] = c, tree[now].sum1.matrix[1][2] = -s * x0 - c * y0 + y0;
                tree[now].sum1.matrix[2][0] = 0, tree[now].sum1.matrix[2][1] = 0, tree[now].sum1.matrix[2][2] = 1;
                alpha = -alpha;
                c = cos(alpha), s = sin(alpha), x0 = g[l].A, y0 = g[l].B;
                tree[now].sum2.matrix[0][0] = c, tree[now].sum2.matrix[0][1] = -s, tree[now].sum2.matrix[0][2] = -c * x0 + s * y0 + x0;
                tree[now].sum2.matrix[1][0] = s, tree[now].sum2.matrix[1][1] = c, tree[now].sum2.matrix[1][2] = -s * x0 - c * y0 + y0;
                tree[now].sum2.matrix[2][0] = 0, tree[now].sum2.matrix[2][1] = 0, tree[now].sum2.matrix[2][2] = 1;
            }
            else
            {
                long double A = g[l].A, B = g[l].B, C = g[l].C;
                tree[now].sum1.matrix[0][0] = B * B / ( A * A + B * B ), tree[now].sum1.matrix[0][1] = -A * B / ( A * A + B * B ), tree[now].sum1.matrix[0][2] = -A * C / ( A * A + B * B );
                tree[now].sum1.matrix[1][0] = -A * B / ( A * A + B * B ), tree[now].sum1.matrix[1][1] = A * A / ( A * A + B * B ), tree[now].sum1.matrix[1][2] = -B * C / ( A * A + B * B );
                tree[now].sum1.matrix[2][0] = 0, tree[now].sum1.matrix[2][1] = 0, tree[now].sum1.matrix[2][2] = 1;
                tree[now].sum2.matrix[0][0] = B * B / ( A * A + B * B ), tree[now].sum2.matrix[0][1] = -A * B / ( A * A + B * B ), tree[now].sum2.matrix[0][2] = -A * C / ( A * A + B * B );
                tree[now].sum2.matrix[1][0] = -A * B / ( A * A + B * B ), tree[now].sum2.matrix[1][1] = A * A / ( A * A + B * B ), tree[now].sum2.matrix[1][2] = -B * C / ( A * A + B * B );
                tree[now].sum2.matrix[2][0] = 0, tree[now].sum2.matrix[2][1] = 0, tree[now].sum2.matrix[2][2] = 1;
            }
            return;
        }
        int mid = l + r >> 1;
        Build(lson(now), l, mid);
        Build(rson(now), mid + 1, r);
        Push_Up(now);
        return;
    }
    void Insert_Matrix ( int now, int l, int r, int ql, int qr, const Matrix &A, const Matrix &B )
    {
        if ( l >= ql && r <= qr )
            { Update1(now, A, B); return; }
        Push_Down(now);
        int mid = l + r >> 1;
        if ( ql <= mid )
            Insert_Matrix(lson(now), l, mid, ql, qr, A, B);
        if ( qr > mid )
            Insert_Matrix(rson(now), mid + 1, r, ql, qr, A, B);
        Push_Up(now);
        return;
    }
    void Insert_Reverse ( int now, int l, int r, int ql, int qr )
    {
        if ( l >= ql && r <= qr )
            { Update2(now); return; }
        Push_Down(now);
        int mid = l + r >> 1;
        if ( ql <= mid )
            Insert_Reverse(lson(now), l, mid, ql, qr);
        if ( qr > mid )
            Insert_Reverse(rson(now), mid + 1, r, ql, qr);
        Push_Up(now);
        return;
    }
    Matrix Query ( int now, int l, int r, int ql, int qr )
    {
        if ( l >= ql && r <= qr )
            return tree[now].sum1;
        Push_Down(now);
        Matrix res;
        res.Identity();
        int mid = l + r >> 1;
        if ( qr > mid )
            res = res * Query(rson(now), mid + 1, r, ql, qr);
        if ( ql <= mid )
            res = res * Query(lson(now), l, mid, ql, qr);
        return res;
    }
}Tree;
int main ()
{
    freopen("point.in", "r", stdin);
    freopen("point.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d%d%d%d", &g[i].opt, &g[i].A, &g[i].B, &g[i].C);
    Tree.Build(1, 1, n);
    int opt, l, r;
    long double u, v, w;
    Matrix upl, upr;
    while ( m -- )
    {
        scanf("%d", &opt);
        if ( opt == 1 )
        {
            scanf("%d%d%Lf%Lf", &l, &r, &u, &v);
            upl.matrix[0][0] = 1, upl.matrix[0][1] = 0, upl.matrix[0][2] = -u;
            upl.matrix[1][0] = 0, upl.matrix[1][1] = 1, upl.matrix[1][2] = -v;
            upl.matrix[2][0] = 0, upl.matrix[2][1] = 0, upl.matrix[2][2] = 1;
            upr = upl;
            upr.matrix[0][2] = u;
            upr.matrix[1][2] = v;
            Tree.Insert_Matrix(1, 1, n, l, r, upl, upr);
        }
        else if ( opt == 2 )
        {
            scanf("%d%d%Lf%Lf%Lf", &l, &r, &u, &v, &w);
            upl.matrix[0][0] = ( v * v - u * u ) / ( u * u + v * v ), upl.matrix[0][1] = -2 * u * v / ( u * u + v * v ), upl.matrix[0][2] = -2 * u * w / ( u * u + v * v );
            upl.matrix[1][0] = -2 * u * v / ( u * u + v * v ), upl.matrix[1][1] = ( u * u - v * v ) / ( u * u + v * v ), upl.matrix[1][2] = -2 * v * w / ( u * u + v * v );
            upl.matrix[2][0] = 0, upl.matrix[2][1] = 0, upl.matrix[2][2] = 1;
            upr = upl;
            Tree.Insert_Matrix(1, 1, n, l, r, upl, upr);
            Tree.Insert_Reverse(1, 1, n, l, r);
        }
        else
        {
            scanf("%d%d%Lf%Lf", &l, &r, &u, &v);
            upl.matrix[0][0] = u, upl.matrix[0][1] = upl.matrix[0][2] = 0;
            upl.matrix[1][0] = v, upl.matrix[1][1] = upl.matrix[1][2] = 0;
            upl.matrix[2][0] = 1, upl.matrix[2][1] = upl.matrix[2][2] = 0;
            upl = Tree.Query(1, 1, n, l, r) * upl;
            printf("%.8Lf %.8Lf\n", upl.matrix[0][0], upl.matrix[1][0]);
        }
    }
    return 0;
}

T2 有限域方阵期望对数转置相关度 (transpose)

神奇的线性代数，不会_。

T3 灭国 (destroy)

首先明确题意，将普通队列换成优先队列求解 Bfs 序，可以加入 \(k\) 条边，需要最后的序列的字典序最大。

考虑模拟 Bfs 序的求解过程，由于当前队列 \(S_1\) 中最小的数可以通过加边暂时不被加入到 Bfs 序后，因此我们用集合 \(S_2\) 维护当前可以通过加边乱序加入到 Bfs 序的点，考虑下一次插入到 Bfs 序后的数，如果 \(S_1\) 中的最小的数小于 \(S_2\) 中最大的数并且 \(S_1\) 大小为 \(1\) ，那么将 \(S_1\) 中最小的数插入到 \(S_2\) 中，将 \(S_2\) 中最大的数插入到 \(S_1\) 中，如果大小不为 \(1\) ，直接将 \(S_1\) 中最小的数插入到 \(S_2\) 中即可，否则直接将 \(S_1\) 中最小的数加入到 Bfs 序中即可。

code

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <utility>
using namespace std;
const int max1 = 1e5;
int n, m, lim, degree[max1 + 5];
vector <int> edge[max1 + 5];
set <int> s1, s2;
vector < pair <int, int> > add_edge;
int last;
int main ()
{
    freopen("destroy.in", "r", stdin);
    freopen("destroy.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &lim);
    for ( int i = 1, u, v; i <= m; i ++ )
    {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        ++degree[v];
    }
    for ( int i = 1; i <= n; i ++ )
        if ( !degree[i] )
            s1.insert(i);
    while ( true )
    {
        while ( s1.empty() && !s2.empty() )
        {
            int x = *--s2.end();
            s2.erase(--s2.end());
            add_edge.push_back(make_pair(last, x));
            printf("%d ", last = x);
            for ( auto v : edge[x] )
            {
                --degree[v];
                if ( !degree[v] )
                    s1.insert(v);
            }
        }
        if ( s1.empty() )
            break;
        int x = *s1.begin();
        s1.erase(s1.begin());
        if ( !s1.empty() && lim )
            s2.insert(x), --lim;
        else if ( !s2.empty() && x < *--s2.end() && lim )
        {
            int tmp = *--s2.end();
            s2.erase(--s2.end());
            s1.insert(tmp);
            add_edge.push_back(make_pair(last, tmp));
            s2.insert(x);
            --lim;
        }
        else
        {
            printf("%d ", last = x);
            for ( auto v : edge[x] )
            {
                --degree[v];
                if ( !degree[v] )
                    s1.insert(v);
            }
        }
    }
    printf("\n");
    printf("%lu\n", add_edge.size());
    for ( auto v : add_edge )
        printf("%d %d\n", v.first, v.second);
    return 0;
}

标签：include,Matrix,省选,mid,int,联测,2023,now,ql
From： https://www.cnblogs.com/KafuuChinocpp/p/17338339.html

相关文章

  • 2023省选武汉联测6
    T1线性代数实际上我们需要求解值域\(\len\)的线性空间的个数，考虑将线性空间与线性基一一对应，为了使得一个线性基唯一对应一个线性空间，我们将主元列上的非主元全部消成\(0\)，发现此时将线性基全部异或得到的值为原集合的最大值，并且可以做到一一对应。（化简为最简阶梯形矩阵）于......
  • 2023省选武汉联测10
    T1矩阵随机一个向量\(V\)，判断\(V\timesA\timesB\)是否等于\(V\timesC\)即可，实质上我们在判断对于每个\(i\in[1,n]\)\(\sum_{k=1}^nV_k\sum_{p=1}^{n}A_{k,p}B_{p,i}\)是否等于\(\sum_{k=1}^{n}V_kC_{k,i}\)。code#include<cstdio>#include<vector>#incl......
  • 2023省选武汉联测9
    T1背包问题模板比较套路的，我们考虑进行二进制拆分，对于数量\(A\)，我们首先从小到大拆分为\(1,2,4...2^k\)，对于剩余的\(w\)，我们直接按照它的二进制位拆分即可，这样问题转化为比较简单的\(0/1\)背包。由于\(b_i\)的范围很小，如果将物体体积用二进制数表示，发现二进制上为\(......
  • 2023省选武汉联测13
    T1构树直接\(O(n^2)\)暴力枚举连边即可。code#include<cstdio>#include<vector>#include<set>#include<utility>usingnamespacestd;constintmax1=1000;intn,Min[max1+5],Max[max1+5];vector<int>part[max1+5];intcolo......
  • # 2023省选武汉联测12
    T1图案首先是题解做法：考虑对于每个\(r\)，判断\(s[1,r]\)是否为一个图案，设\(r=ik+j\)，其中\(0\lej\lei\)，如果存在一组这样的\((i,j)\)满足\(s[1,r-i]=s[i+1,r]\)，那么\(s[1,r]\)是一个图案，考虑这样做的正确性，如果\(s[1,r-i]=s[i+1,r]\)，那么一定有\(s[i+1,r-2i]=s......
  • 2023省选武汉联测11
    T1游戏对于树上三点\((u,v,w)\)，一定存在一个点\(p\)满足\(p\tou\)与\(p\tov\)与\(p\tow\)的路径两两不重合，考虑枚举\(p\)计算答案，由于题目给定\(\operatorname{dis}(u,v),\operatorname{dis}(u,w),\operatorname{dis}(v,w)\)，因此我们首先用解方程的方法求解\(......
  • 2023-04-20：有一堆石头，用整数数组 stones 表示 其中 stones[i] 表示第 i 块石头的重量
    2023-04-20：有一堆石头，用整数数组stones表示其中stones[i]表示第i块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎假设石头的重量分别为x和y，且x<=y那么粉碎的可能结果如下：如果x==y，那么两块石头都会被完全粉碎；如果x!=y，那么重量为x的石头将......
  • 西南民族大学 2023 天梯自主训练 4
    西南民族大学2023天梯自主训练4 多项式A除以B思路：a表示被除多项式，b表示除数多项式，一次运算的商的项p为a的最高项-b的最高项，商的系数q为a的最高项的系数除以b的最高项的系数，将所有a中项数和b的项数乘p后相同的系数减去b项的系数乘q（...haoluan...看图吧） #include<bits/s......
  • 2023/4/20 SCRUM个人博客
    1、我昨天的成就:1111111111111昨天完成了识别视频画面中的人脸并且绘制人脸的边框到视频画面上面2、遇到了什么困难困难在于opencv、dlib等的使用，查阅了相关资料以及视频后得以解决3、今天的任务今天的任务主要是完成人脸课堂集中度检测画面的绘制，以从暗到亮表......
  • 每日总结2023-04-20
    今天完成了对于界面的初步优化，但对于基于通过dialog对话框的跳转的传值不理解，无法将主界面的信息通过dialog传递到另一个页面。 初步完成的页面： 剩余任务还有Android的网络获取定位输出详细地址。 ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99