• 2022“杭电杯” 中国大学生算法设计超级联赛（6）7 9题解

    1007-Shinobu loves trip

    题目大意：
    一共有P个城市，编号为0,1,…P-1。
    如果Shinobu当前位于i城市，那么下一天将会前往(i·a)%P城市。
    现在给定若干个旅行计划，每个计划包含起始城市 si 和旅行天数 di 。
    接下来是q次询问，每次询问有多少个计划会经过 xi 城市。

    思路：
    其实当时就想到了这种做法，但是觉得有点暴力就去想其他做法了。没想到赛后给的题解就是这么做的。当时没写有点可惜。

    对于起始城市s，那么第k天到达的城市就是 (s·ak)%p ，反过来(s·ak)%p = xi，将xi乘上s的逆元，就能得到ak ，所以预处理a的次幂，用map保存查询即可。

    在细节方面有挺多需要注意的，在代码中都注释出来了。

    AC代码：

    #include 
const int N = 1e3 + 5;
using namespace std;
long long ksm(long long base, long long power, long long mod)
{
    long long result = 1;
    base %= mod;
    while (power)
    {
        if (power & 1)
            result = (result * base) % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int s[N], d[N], invs[N];
void solve()
{
    int P, a, n, q;
    long long ap = 1;
    unordered_map<int, int> f;
    cin >> P >> a >> n >> q;
    for (int i = 0; i <= 200000; i++)
    {
        if (f.count(ap)) break; //出现重复的了,退出循环,否则相同的数会被以更大的i替换
        f[ap] = i;
        ap = (ap * a) % P;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i] >> d[i];
        invs[i] = ksm(s[i], P - 2, P);
    }
    while (q--)
    {
        long long x, cnt = 0;
        cin >> x;
        for (int i = 1; i <= n; i++)
        {
            if (s[i] == 0 && x == 0) //特殊情况,s和x都为0
                cnt++;
            else
            {
                int ak = (x * invs[i]) % P;
                if (f.count(ak) && f[ak] <= d[i]) cnt++;
            }
        }
        cout << cnt << "\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    1008-Shinobu Loves Segment Tree

    题目大意：
    定义build函数如下

    void build(int id, int l, int r){
  value[id] += r-l+1;
  if(l == r) return;
  int mid = (r+l)/2;
  build(id*2, l, mid);
  build(id*2+1, mid+1, r);
  return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    value数组初始为0
    在第i天会调用build(1,1,i)函数。
    求出第n天value[x]的值。

    思路：
    build在递归调用的过程可以看作是一棵树，根结点为1。
    如果当前结点的区间长度为1，就停止调用。否则进入左右子树：

    • 进入左子树，区间长度为(len+1)/2
    • 进入右子树，区间长度为len/2

    对于第i层的结点x（结点1的层定义为0），只有当结点1处的区间长度增加 2i 时，对x的贡献才会加1。因此我们可以逆向求出贡献为2时的最小区间长度（和天数等价），然后计算剩余的天数有几个2i ，进行求和，最后加上1和右边剩余的天数即可，贡献为1的计算方式有所不同，所以1要单独计算。

    AC代码：

    #include 
#define frein(f) freopen(f ".in", "r", stdin)
#define freout(f) freopen(f ".out", "w", stdout)
using namespace std;

void solve()
{
    long long n, x, len, ans = 0;
    cin >> n >> x;
    if (x == 1)
        ans = (n + n * n) / 2;
    else
    {
        len = 1;
        while ((len << 1) <= x)
            len <<= 1;
        long long l1 = 2, l2 = 2, r, tx;

        tx = x >> 1; //计算1出现的最小值
        while (tx > 1)
        {
            if (tx & 1)
                l1 = l1 << 1;
            else
                l1 = (l1 << 1) - 1;
            tx >>= 1;
        }
        if (l1 > n) //全都是0的情况
        {
            cout << "0\n";
            return;
        }
        tx = x; //计算2出现的最小值
        while (tx > 1)
        {
            if (tx & 1)
                l2 = l2 << 1;
            else
                l2 = (l2 << 1) - 1;
            tx >>= 1;
        }
        if (l2 > n) //全都是1的情况
        {
            cout << n - l1 + 1 << "\n";
            return;
        }
        ans = l2 - l1;                          //左侧1的区间累加
        r = 1 + (n - l2 + 1) / len;             //计算连续区间右端最大值
        ans += len * (2 + r) * (r - 2 + 1) / 2; //连续区间累加和
        ans += (n - l2 + 1) % len * (r + 1);    //剩余右端值累加
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    1009-Map

    题目大意：
    将一张缩小的地图放到原来的地图上（小地图被大地图完全包含），两个地图会有一个公共点，求出这个公共点。

    思路：
    计算几何是队友负责的，不过我当时想到了这个比较有趣的做法，试着敲了一下居然过了。
    将小地图再次缩小，得到小小地图。
    将小小地图放到小地图上，使得小小地图和小地图的位置关系与小地图和大地图的位置关系相同。
    那么小小地图和小地图的公共点和要求的公共点是重合的。
    不断重复这一过程，最后地图会被缩成一个点，这个点就是公共点。
    缩小地图并放置于小地图上的过程实际上就是将地图的三个角进行移动（因为是矩形，只要确定对角即可，这里计算三个角是为了方便向量的计算），可以用向量来计算。

    tips： HDU的long double有精度问题，这题用double即可 因为这个白白wa了一发

    AC代码：

    #include 
using namespace std;

void solve()
{
    double Ax, Ay, Bx, By, Cx, Cy, Dx, Dy; //大地图的四个角坐标
    double ax, ay, bx, by, cx, cy, dx, dy; //小地图的四个角坐标
    double a2x, a2y, c2x, c2y, d2x, d2y; //小小地图的三个角坐标
    double DAx, DAy, DCx, DCy, Dax, Day, Dcx, Dcy, Ddx, Ddy;//向量的坐标
    double dax, day, dcx, dcy, da2x, da2y, dc2x, dc2y, dd2x, dd2y; //向量的坐标
    double m, n; //向量的关系
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &Ax, &Ay, &Bx, &By, &Cx, &Cy, &Dx, &Dy);
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy);
    int cnt = 100;
    DAx = Ax - Dx, DAy = Ay - Dy;
    DCx = Cx - Dx, DCy = Cy - Dy;
    while (cnt--)
    {
        Dax = ax - Dx, Day = ay - Dy;
        Dcx = cx - Dx, Dcy = cy - Dy;
        Ddx = dx - Dx, Ddy = dy - Dy;
        dax = ax - dx, day = ay - dy;
        dcx = cx - dx, dcy = cy - dy;

        m = (Dax * DCy - Day * DCx) / (DCy * DAx - DCx * DAy);
        n = (Dax * DAy - Day * DAx) / (DAy * DCx - DAx * DCy);
        a2x = m * dax + n * dcx + dx;
        a2y = m * day + n * dcy + dy;

        m = (Dcx * DCy - Dcy * DCx) / (DCy * DAx - DCx * DAy);
        n = (Dcx * DAy - Dcy * DAx) / (DAy * DCx - DAx * DCy);
        c2x = m * dax + n * dcx + dx;
        c2y = m * day + n * dcy + dy;

        m = (Ddx * DCy - Ddy * DCx) / (DCy * DAx - DCx * DAy);
        n = (Ddx * DAy - Ddy * DAx) / (DAy * DCx - DAx * DCy);
        d2x = m * dax + n * dcx + dx;
        d2y = m * day + n * dcy + dy;

        ax = a2x, ay = a2y;
        cx = c2x, cy = c2y;
        dx = d2x, dy = d2y;
    }
    printf("%.8lf %.8lf\n", (ax + cx) / 2.0, (ay + cy) / 2.0);
}

signed main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    1010-Planar graph

    题目大意：
    给定一个平面图，要求在两个封闭的圈之间加隧道，使得所有封闭的圈连通，要求加隧道的边最少且字典序最小。

    思路：
    当时想复杂了，想的是怎么把封闭的圈能找出来，然后跑最小生成树。
    赛后看题解也是看得挺懵的，还要去了解平面图的定理啥的。最后看了别人的博客和官方的std才理解了做法：就是用并查集记录加进来的边是否会构成环，如果构成环了就在这条边上建一个隧道。为了使字典序最小，从后往前加边即可。

    AC代码：

    #include 
#define frein(f) freopen(f ".in", "r", stdin)
#define freout(f) freopen(f ".out", "w", stdout)
const int N = 1e5 + 5;
using namespace std;

int u[N * 2], v[N * 2], ans[N * 2], fa[N];
int Find(int x)
{
    if (fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}

void solve()
{
    int n, m, cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> u[i] >> v[i];
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = m; i >= 1; i--)
    {
        int fu = Find(u[i]);
        int fv = Find(v[i]);
        if (fu == fv)
            ans[++cnt] = i;
        else
            fa[fu] = fa[fv];
    }
    cout << cnt << endl;
    for (int i = cnt; i >= 1; i--)
        cout << ans[i] << ' ';
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
  • 相关阅读:
    【mysql篇】操作数据库的日期、字符串、数值、流程控制函数
    如何能提高虚拟机上下载Hadoop压缩包的下载速度
    如何手动运行一个容器【一】
    NER项目 P2 解析文字和实体标签对应关系
    Android配置变体
    基于Jetty9的Geoserver配置https证书
    C# 集合(三) —— Stack/BitArray类
    Consumer的负载均衡
    【docker】docker的一些常用命令-------从小白到大神之路之学习运维第92天
    【正点原子FPGA连载】 第三章 硬件资源详解 摘自【正点原子】DFZU2EG/4EV MPSoC 之FPGA开发指南V1.0
  • 原文地址：https://blog.csdn.net/Shanhj/article/details/126597449