头像

Nicoppa




离线:1天前


最近来访(185)
用户头像
想想y总怎么做
用户头像
keke1
用户头像
-_21
用户头像
rd0
用户头像
牛牛的跟屁虫
用户头像
bxcXCX
用户头像
acmdyh
用户头像
要挥剑了
用户头像
成舅感
用户头像
ytcccf
用户头像
今夕
用户头像
Eden_
用户头像
自律
用户头像
invisible-pat.
用户头像
rickwang
用户头像
sd6f5
用户头像
UFFFO
用户头像
JmZeroQAQ
用户头像
BieHuiTou
用户头像
Xueranran


Nicoppa
8天前

Nicoppa的个人博客

货仓选址

在一条数轴上有 $N$ 家商店,它们的坐标分别为 $A_1…A_N$。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数$N$。

第二行$N$个整数$A_1…A_N$。

输出格式

输出一个整数,表示距离之和的最小值。

数据范围

$1≤N≤100000$

输入样例

4
6 2 9 1

输出样例

12

解析

无代码,只放证明

假设仓库建在最优位置(必需有这个前提)时,左边有 $a$ 个商店,那么右边就有 $n - a$ 个商店,左边商店距离仓库的位置之和为 $p$ ,右边的商店距离仓库的位置之和为 $q$ 可得 $p + q$ 为所有商店到仓库的最小距离之和

现在将仓库向左移 $x$,可得
$p - ax + q + (n-a)x$
$ = p - ax + q + nx - ax$
$ = p + q + (n - 2a)x $

因为仓库之前是设在最优位置,所以 $n - 2a ≥ 0$ ,如果不满足这个条件,那么就和我们仓库建在最优位置的条件产生冲突,即 $p + q$ 就不是我们的所有商店到仓库的距离之和最小了。

此时,当 $a = \frac{n}{2}$ 时,得到最优答案。




Nicoppa
9天前

Nicoppaの个人博客

电影

莫斯科正在举办一个大型国际会议,有 $n$ 个来自不同国家的科学家参会。

每个科学家都只懂得一种语言。

为了方便起见,我们把世界上的所有语言用 $1$ 到 $10^9$ 之间的整数编号。

在会议结束后,所有的科学家决定一起去看场电影放松一下。

他们去的电影院里一共有 $m$ 部电影正在上映,每部电影的语音和字幕都采用不同的语言。

对于观影的科学家来说,如果能听懂电影的语音,他就会很开心;如果能看懂字幕,他就会比较开心;如果全都不懂,他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影,可以让观影很开心的人最多。

如果有多部电影满足条件,则在这些电影中挑选观影比较开心的人最多的那一部。

输入格式

第一行输入一个整数 $n$,代表科学家的数量。

第二行输入 $n$ 个整数 $a_1,a_2…a_n$,其中 $a_i$表示 第 $i$ 个科学家懂得的语言的编号。

第三行输入一个整数 $m$,代表电影的数量。

第四行输入 $m$ 个整数 $b_1,b_2…b_m$,其中 $b_i$ 表示第 $i$ 部电影的语音采用的语言的编号。

第五行输入 $m$ 个整数 $c_1,c_2…c_m$,其中 $c_i$表示第 $i$ 部电影的字幕采用的语言的编号。

请注意对于同一部电影来说,$b_i≠c_i$。

同一行内数字用空格隔开。

输出格式

输出一个整数,代表最终选择的电影的编号。电影编号 $1∼m$。

如果答案不唯一,输出任意一个均可。

数据范围

$1≤n,m≤200000$,
$1≤a_i,b_i,c_i≤10^9$

输入样例

3
2 3 2
2
3 2
2 3

输出样例

2

解析

只考虑电影的语言和字幕是否和科学家会的语言一样,看到询问的数据范围 $2 \times 10^5$,而每个数的大小却是 $1 \times 10^9$ 那么久考虑使用离散化。

离散化是指,将一段稀疏的数据变成一段稠密的数据

对应题意,有一个最简单的实现方法,假设会的语言编号为 2 8 1000 100000,那么就可以得到 $f_2 = …,f_8 = …,f_{1000} = …,f_{100000}=…$ 这里的 $f_i$ 为每种语言有多少科学家会,于是我们询问时直接提取就好,但是有个问题 这里编号大小的数据范围为 $[1,10^9]$,直接开这么大的数组就会 MLE。于是考虑离散化

例如,假设我的原数组是 2 8 1000 100000,那么我的新数组就是 1 2 3 4,为了在询问原数组的数时能快速得到新数组的对应值,我们用另外一个数组来储存原数组 即 $a_i$,那么可得 $a_1 = 2,a_2 = 8, a_3 = 1000, a_4 = 100000$ ,该数组满足单调性,那么用二分在这个数组里查询就可以很快得到新数组的值(即查询的下标)。

我们的原问题也可以得到解决,此时我们的 $f_i$ 就变成了 $f_1 = …,f_2 = …,f_3 = …,f_4 = …$ ,离散化后的下标数据范围为 $[1, 2\times 10^5]$ ,很显然 这样开就不会MLE了。

既然不会 MLE 了,我们再来算下时间复杂度。假设总共有 $K$ 种语言,那么每次询问用二分来查询就是 $O(logK)$ 的复杂度,单独查询电影语言的总复杂度就是 $O(mlogK)$,而二分查询需要满足一定的二分性,且科学家的顺序并不影响我们之后的操作,所以我们统计科学家语言的时候只需要将其排序再统计,那么可得总复杂度就是 $O(nlogn +2mlogK )$

这个时间复杂度是可以过的,即使写的杂糅点时间也绰绰有余。

看代码

#include <cstdio>
#include <iostream>
#include <algorithm>
//不想用map和set 也不想记二分函数 那样就不会计算时间复杂度了
//代码写的有点复杂了,懒得优化 看个思路就好 自己写
const int N = 200005;
int arr[N], Sign[N], Newarr[N], RSign[N], answ[N];
bool Vis[N];

int tnt = 1, tot = 0;
int cheak(int x) { //二分寻找离散化之前的原值
    int l = 1, r = tot;
    while(r >= l) {
        int mid = (l + r) >> 1;
        if(x == Sign[mid]) return mid;
        else if(x > Sign[mid]) l = mid + 1;
        else r = mid - 1;
    } return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    std::sort(arr + 1, arr + 1 + n);

    for (int i = 1; i <= n; i++) { //统计每种语言有多少科学家会,离散化原数组
        if(arr[i] == arr[i + 1]) Newarr[tnt]++;
        else Newarr[tnt]++, tnt++;

        if(arr[i] != arr[i + 1]) Sign[++tot] = arr[i];
    }

    int m, ans = 0, ansx, maxx = 0, twt = 0; bool flag = false;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) { //询问电影语言
        int x;
        scanf("%d", &x); RSign[i] = x;

        ansx = cheak(x); if(ansx == 0) continue;
        if(maxx < Newarr[ansx]) { 
        //因为可能存在多个听得懂语言的科学家数量相同的电影 所以需要记录
            maxx = Newarr[ansx];
            ans = i;
            twt = 1;
            answ[twt] = i;
        } else if(maxx == Newarr[ansx]) {
            twt++;
            answ[twt] = i;
        }
    } if(ans == 0) flag = true;
    //如果所有科学家都听不懂,那么我们就标记 等会儿就只考虑看得懂

    for (int i = 1; i <= twt; i++) Vis[answ[i]] = true; //方便调用

    int ansy, maxy = 0;
    for (int i = 1; i <= m; i++) { //询问电影字幕
        int y;
        scanf("%d", &y);

        ansy = cheak(y); if(ansy == 0) continue;
        if(flag && maxy <= Newarr[ansy]) maxy = Newarr[ansy], ans = i; 
        if(!flag && Vis[i] && maxy <= Newarr[ansy]) {
            maxy = Newarr[ansy];
            ans = i;
        }
    } if(ans == 0) printf("%d\n", m); else printf("%d\n", ans);
    //如果没有一部电影是科学家们看得懂和听得懂的 我们就随便输出一个(也满足题意)
    return 0;
}



Nicoppa
13天前

个人博客: Nicoppa的个人博客

最高的牛

有 $N$ 头牛站成一行,被编队为 $1、2、3…N$,每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。

现在,我们只知道其中最高的牛是第 $P$ 头,它的身高是 $H$ ,剩余牛的身高未知。

但是,我们还知道这群牛之中存在着 $M$ 对关系,每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数 $N,P,H,M$,数据用空格隔开。

接下来 $M$ 行,每行输出两个整数 $A$ 和 $B$,代表牛 $A$ 和牛 $B$ 可以相互看见,数据用空格隔开。

输出格式

一共输出 $N$ 行数据,每行输出一个整数。

第 $i$ 行输出的整数代表第 $i$ 头牛可能的最大身高。

数据范围

$1≤N≤10000$,
$1≤H≤1000000$,
$1≤A,B≤10000$,
$0≤M≤10000$

输入样例

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例

5
4
5
3
4
4
5
5
5

注意:

  • 此题中给出的关系对可能存在重复

解析

需要用到知识点 差分数组 (复习)

有数组 A[1] A[2] A[3] A[4]
差分数组 B[i] = A[i] - A[i - 1]
可得 A[i] = B[1] + B[2] + B[3] + .... + B[i]

由问题可得,我们需要始终让数组 $a_n$ 的某区间 $[l,r]$ 中,$a_l$ 与 $a_r$ 的值在这个区间最大。

那很简单,让每次的询问中使 $[l+1,r-1]$ 的区间内所有数 $-1$ 就好,这样就能保证 $a_l$ 与 $a_r$ 在 $[l,r]$ 中最大,且满足我们尽可能让每头牛的身高最高的条件。

这里的区间数作加减,用差分数组完成即可。

最后就是 此题中给出的关系对可能存在重复 的条件,我们只需要排序一下,看看当前的区间是否和上一个区间不同就好。(因为 $1≤N≤10000$,所以没有考虑用二维数组标记 64MB会MLE,但题解里似乎有用 bool 数组进行标记的)

剩下的看代码

#include <cstdio>
#include <iostream>
#include <algorithm>
//前排提醒 更简单的看yxc的代码
int n, p, h, m;

const int N = 10005;
std::pair<int, int> arr[N];
int B[N];

int cmp(std::pair<int, int>a, std::pair<int, int>b) { //用pair排序得构造
    if(a.first != b.first) return a.first < b.first;
    else return a.second < b.second;
}

int main() {
    scanf("%d %d %d %d", &n, &p, &h, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
        if(arr[i].first > arr[i].second) std::swap(arr[i].first, arr[i].second);
    } //保证一定是左区间小于右区间

    std::sort(arr + 1, arr + 1 + m, cmp);

    for (int i = 1; i <= m; i++) { //如果相同就跳过,不同就进行区间操作
        if(arr[i].first == arr[i - 1].first && arr[i].second == arr[i - 1].second) continue;
        B[arr[i].first + 1] -= 1;
        B[arr[i].second] += 1;  
    }

    int ans = h;
    for (int i = 1; i <= n; i++) {
        ans = ans + B[i];
        printf("%d\n", ans);
    } return 0;
}

注意注意

我只说明了 $[l + 1,r - 1]$ 上 $-1$ 的方法的最优性,没有证明其正确性

若存在数据
6 6 5 3
1 4
2 4
3 6
则由方法可得
5 4 3 4 4 5
并不满足 3 6 的询问,但这并不能说明方法的错误,只是因为这种数据不可能得到一个正确解
所以为了保证数据的正确性 若出现询问区间交叉的情况,设不合理的区间为 [l, r]
那么[l, r]一定会再次进行询问,直到原来的两次询问都为合法询问(满足题意要求的正确答案)为止
所以可以得到我们方法一定是正确的



Nicoppa
13天前

博客地址 Nicoppa的个人博客

增减序列

给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$,每次可以选择一个区间 $[l,r]$,使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式

第一行输入正整数 $n$。

接下来 $n$ 行,每行输入一个整数,第 $i+1$ 行的整数代表 $ai$。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

$1≤n≤10^5$,
$0≤a_i<2147483648$

输入样例

4
1
1
2
2

输出样例

1
2

解析

需要用到知识点 差分数组

有数组 A[1] A[2] A[3] A[4]
差分数组 B[i] = A[i] - A[i - 1]
可得 A[i] = B[1] + B[2] + B[3] + .... + B[i]

含义:原数组 $A_i$ 是差分数组 $B_i$ 的前 $i$ 项和

知道知识点我们来看题

首先需要实现,快速在 $[l,r]$ 区间内进行加减,根据差分数组的定义,在原数组 $A_i$ 的 $[l,r]$ 上作加减 就相当于在差分数组 $B_i$ 的 $B_l$ 与 $B_{r+1}$ 上作加减

比如样例

A_i 1 1 2 2
B_i 1 0 1 0
在[1,2]上 +1,则
A_i 2 2 2 2
B_i 2 0 0 0 (B_1 + 1, B_3 - 1)

好了,已经快速解决 $[l,r]$ 上作加减的问题,就可以来看题目的要求了

① 求最少的操作次数

② 输出最终能得到多少种结果

首先来解决①,我们的目的是 让差分数组除 $B_1$ 外的所有数都变成0,那么我们只需要让差分数组 负的加,正的减 就可以保证每次的选择都是最优选择,这个问题很好解决 一个循环即可。

但每次肯定不会正好减到 0,那我们只需要把多出来全部加到 $B_1$ 就好,这样也满足我们的目的。

然后来解决②,考虑①的最后一步,我们除了将多出来的移到 $B_1$,当然还可以移到 $B_{n+1}$,即将多出来的数再 加一减一 变成0(这里可以理解成在自己[l == r]上操作,也可以理解为在整个差分数组外还有一个规则外的区域),那么只需要多出来几就加上几就好(每个数都有两种选择,加到 $B_1$ 上 或者 不加到 $B_1$ 上)

看代码

#include <cstdio>
#include <iostream>

const int N = 100005;
long long arr[N], g[N];

//更简单的看yxc大佬的代码

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &arr[i]);
        g[i] = arr[i] - arr[i - 1]; //差分数组
    }

    long long tnt = 0, ans = 0;
    for (int i = 2; i <= n; i++) {
        if(tnt > 0 && g[i] < 0) ans = ans + std::min(tnt, std::abs(g[i])), tnt = tnt + g[i]; 
        else if(tnt < 0 && g[i] > 0) ans = ans + std::min(std::abs(tnt), g[i]), tnt = tnt + g[i]; 
        //异号的情况 说明有正负出现 正的加,负的减就好
        else tnt += g[i]; //同号的情况 那么记录起来就好
    }

    printf("%lld\n", ans + std::abs(tnt));
    //最优情况(负的加,正的减   +    多出来的数(可能是负数,记得取绝对值))
    printf("%lld\n", std::abs(tnt) + 1);
    //讨论多少种情况 详细看上面解析
    return 0;
}



Nicoppa
16天前

博客地址:Nicoppa的个人博客

激光炸弹

地图上有 $N$ 个目标,用整数 $X_i,Y_i$ 表示目标在地图上的位置,每个目标都有一个价值 $W_i$。

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 $R×R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 $x,y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

接下来 $N$ 行,每行输入一组数据,每组数据包括三个整数 $X_i,Y_i,W_i$,分别代表目标的 $x$ 坐标,$y$ 坐标和价值,数据用空格隔开。

输出格式

输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0≤R≤10^9$
$0<N≤10000$
$0≤X_i,Y_i≤5000$
$0≤W_i≤1000$

输入样例

2 1
0 0 1
1 1 1

输出样例

1

解析

一个前缀和的小运用,因为本题只有一个炸弹,所以我们只需要 贪心 选择一个 $R\times R$ 大小区域内的价值总数最高的即可

那么就有一个疑问,如何快速求得一个 $R\times R$ 大小区域的价值总数?小技巧 前缀和,因为你想快速询问某个区域内的价值总数 最快的方式就是先将里面的所有数加起来放到一个点上,这样无论是询问和扩展都只用询问这个点即可。

知道这个方法,接下来的事情就非常简单了,如果当前询问的点并没有超过R,那么直接与答案求最大值,如果当前询问的点长或宽超过了R,那么就将超过的部分在前面截掉,因为我们用的前缀和,所以在截掉这里的计算也十分的便捷。

但这里注意,如果长和宽都超过了R,同时截掉长和宽多出的一部分就会使这两者重叠的一部分被减掉两次,所以在这里处理的时候需要再加上。

详细看代码

#include <cstdio>
#include <cstring>
#include <iostream>

int N, R;

const int Maxn = 5005;
int Map[Maxn][Maxn];

int main() {
    memset(Map, 0, sizeof(Map));
    scanf("%d %d", &N, &R); int mx = 0, my =0;
    for (int i = 1; i <= N; i++) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        Map[x + 1][y + 1] += w;
        mx = std::max(mx, x + 1);
        my = std::max(my, y + 1); //因为防止 -1 会变成负数,我这里 +1
    }

    for (int i = 1; i <= mx; i++) {
        for (int j = 1; j <= my; j++) {
            Map[i][j] = Map[i - 1][j] + Map[i][j - 1] - Map[i - 1][j - 1] + Map[i][j];
        }
    } //前缀和计算

    int ans = 0;
    for (int i = 1; i <= mx; i++) { //四种情况分别讨论
        for (int j = 1; j <= my; j++) {
            if(i <= R && j <= R) ans = std::max(ans, Map[i][j]);
            if(i > R && j <= R) ans = std::max(ans, Map[i][j] - Map[i - R][j]);
            if(i <= R && j > R) ans = std::max(ans, Map[i][j] - Map[i][j - R]);
            if(i > R && j > R) ans = std::max(ans, Map[i][j] - Map[i - R][j] - Map[i][j - R] + Map[i - R][j - R]); //这里要加上重叠的部分 因为减了两次
        }
    } printf("%d\n", ans);
    return 0;
}



Nicoppa
16天前

博客地址:LoveHshan.top

分形之城

城市的规划在城市建设中是个大问题。

不幸的是,很多城市在开始建设的时候并没有很好的规划,城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案,如下图所示:

city.png

当城区规模扩大之后,Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围,提升城市的等级。

对于任意等级的城市,我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂,Fractal 规划部门的人员还是想知道,如果城市发展到了等级 $N$,编号为 $A$ 和 $B$ 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离,每个街区都是边长为 $10$ 米的正方形。

输入格式

第一行输入正整数 $n$,表示测试数据的数目。

以下 $n$ 行,输入 $n$ 组测试数据,每组一行。

每组数据包括三个整数 $N,A,B$,表示城市等级以及两个街区的编号,整数之间用空格隔开。

输出格式

一共输出 $n$ 行数据,每行对应一组测试数据的输出结果,结果四舍五入到整数。

数据范围

$1≤N≤31$,
$1≤A,B≤2^{2N}$,
$1≤n≤1000$

输入样例

3 
1 1 2 
2 16 1 
3 4 33 

输出样例

10 
30 
50 

解析

大模拟题,思路简单

首先解决三个问题

①:如何从 [等级一] 的图像变化成 [等级二] 的图像

②:给你 [等级二] 图像中的某个点,如何找出该点在 [等级一] 图像中的对应点

③: 如何将上面的思路运用到更高等级的图像中

先解决 ①

懒,不想画图,给一张写题的草稿图,请自行找张纸根据我说的一边画一边看

我简单的令 等级一的图像 为 1图,等级二的图像 为 2图。将 2图 以四个房子为一个象限,图像的中点为原点,右为正x,上位正y 作一个坐标轴。取出 2图 中的四个象限图像,以 1图 样式摆放。

此时我们可以得到 4个4方格图像,分别代表的是 2图 的 “第一象限” “第二象限” “第三象限” 第四象限“

此时再以图像的中点为原点,右为正x,上为正y 作一个坐标轴,可以得到四个点分别在四个象限的图像。

此时 我们将四个图像的各编号以从小到大的顺序重新编号为 1、2、3、4,再将这四个图像与 1图 作比较。

这里挑一个最难的说

第二象限图像:是 1图 以坐标原点顺时针旋转90°,再以 y轴 作左右对称得到的图形,观察坐标变化

1:(-1,1) -> (-1,1)

2:(1,1) -> (-1,-1)

3:(1,-1) -> (1, -1)

4:(-1,-1) -> (1,1)

即可得,变化式为

(x,y) -> (y,x) ->(-y,-x)

这样就可以从 1图 变成第二象限图像,再将此图像移动至 2图 的第二象限处 即(令一个方格的长度为len)

(-y + len / 2,-x - len / 2)

剩下的象限图像同理

第一象限图像:(x + len / 2, y + len / 2)

第三象限图像:(y - len / 2, x - len / 2)

第四象限图像:(x + len / 2, y - len / 2)

于是此时我们就解决了 ①

考虑 ②,我们发现 2图 的每个象限图的点上的数去减一 Mod 一图的点总数 再加一,就可以得到 2图 每个象限的个点 在 1图上的对应点。于是②解决

考虑③,对照题中给的 3图 与 2图 的图像,我们发现与 2图 和 1图 的对应关系是相同的,那么我们继续套用 1图 到 2图 的公式 进 2图 到 3图即可,毕竟我们只需要做到点的对应,一个递归解决。

那么根据上面的 ①②③,我们就可以写出代码

    #include <cmath>
    #include <cstdio>
    #include <iostream>
    //前排提醒 我的递归写的较差,更简单的可以看yxc的代码
    long long n;

    struct Coordinates{
        long long x, y;
    };

    Coordinates Tem;
    void init() {
        Tem.x = 0;
        Tem.y = 0;
    }

    Coordinates Calculate(long long x, long long k) {
        long long len = (1ll << (x - 1)) * 10; //每个象限的总长度
        long long cnt = (k - 1) / (1ll << (x * 2 - 2)); //该点在第几象限
        long long tnt = ((k - 1) % (1ll << (x * 2 - 2))) + 1; //该点对应上一级的哪个点

        if(x == 1) { //如果到等级一了 就给坐标值
            if(k == 1) Tem.x = -5, Tem.y = 5;
            if(k == 2) Tem.x = 5, Tem.y = 5;
            if(k == 3) Tem.x = 5, Tem.y = -5;
            if(k == 4) Tem.x = -5, Tem.y = -5;
            return Tem;
        }

        Calculate(x - 1, tnt); //返回到前一级
        Tem.x = Tem.x + len / 2; //我这里的意思是 先统一移动到第一象限
        Tem.y = Tem.y + len / 2; //因为我下面的公式都是以第一象限来推的
        if(cnt == 0) { //如果在第二象限
            long long x1, y1;
            x1 = Tem.x, y1 = Tem.y;
            Tem.x = -y1, Tem.y = -x1 + len;
        }
        //第一象限我已经移动过了 所以不用写
        if(cnt == 2) { //如果在第四象限
            Tem.y = Tem.y - len;
        }

        if(cnt == 3) { //如果在第三象限
            long long x1, y1;
            x1 = Tem.x, y1 = Tem.y;
            Tem.x = y1 - len, Tem.y = x1 - len;
        } return Tem;
    }

    int main() {
        long long N, a, b;
        scanf("%ld", &N);
        init();
        while(N--) {
            scanf("%ld %ld %ld", &n, &a, &b);
            Coordinates k = Calculate(n, a); init(); //重置一下
            Coordinates m = Calculate(n, b); init();
            double x = k.x - m.x, y = k.y - m.y; //两点距离公式
            printf("%.0lf\n", sqrt(x * x + y * y));
        } return 0;
    }


活动打卡代码 AcWing 532. 货币系统

Nicoppa
2019-10-14 15:47
//#define fre yes

#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 105;
bool Vis[N];
int arr[N];
int ans = 0;

int main() {
    static int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
        } std::sort(arr + 1, arr + 1 + n);

        ans = 1; bool flag = false;
        if(arr[2] % arr[1] != 0) {
            ans = 2;
        } else Vis[2] = true;
        for (int i = 3; i <= n; i++) {
            flag = false;
            for (int j = 1; j < i; j++) {
                if(Vis[j]) continue;
                int t = 0;
                if(arr[i] % arr[j] == 0) {
                    Vis[j] = 1;
                    flag = true; 
                    break;
                } else t = arr[i] % arr[j];
                for (int k = 1; k < j; k++) {
                    if(Vis[k]) continue;
                    if(k == j) break;
                    if(t % arr[k] == 0) {
                        flag = true;
                        Vis[i] = true;
                        break;
                    }
                } if(flag) break;
            } if(!flag) ans++;
        } printf("%d\n", ans);
    } return 0;
}


活动打卡代码 AcWing 531. 铺设道路

Nicoppa
2019-10-14 14:23
//#define fre yes

#include <cstdio>
#include <iostream>

const int N = 100005;
int arr[N];

int main() {
    static int n;
    scanf("%d", &n);

    int minn = 1e9, ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        minn = std::min(arr[i], minn);
    }

    ans = minn;
    for (int i = 1; i <= n; i++) {
        arr[i] -= minn;
    }

    int maxx = 0; minn = 0; bool flag = false;
    for (int i = 1; i <= n; i++) {
        maxx = std::max(maxx, arr[i]);
        if(arr[i] < arr[i + 1]) {
            ans += maxx - minn;
            minn = arr[i];
            flag = true;
            maxx = 0;
        } else flag = false;
    } if(!flag) ans += maxx - minn;
    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

Nicoppa
2019-09-19 15:16

可达性统计

原题链接:可达性统计

题目大意

给你一张$n$个点$m$条边的有向无环图,分别统计从每个点出发能够到达的点的数量

题目题解

看到题意就知道要用到拓扑排序,但是拓扑排序的理论复杂度在30000的极限条件下会超时,这个时候我们考虑使用 $bitset$,一个很好用的代替bool的防卡常技巧,详细的说明这里不说,可以去百度上查看相关运用

//#define fre yes

#include <queue>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 30005;
int head[N << 1], to[N << 1], ver[N << 1];
int in[N], ans[N];

std::bitset<N> f[N];

int tot, k;
void addedge(int x, int y) {
    ver[tot] = y;
    to[tot] = head[x];
    head[x] = tot++;
}

int n, m;

void toposort() {
    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        if(!in[i]) q.push(i);   
    }

    while(!q.empty()) {
        int t = q.front(); q.pop();
        ans[++k] = t;
        for (int i = head[t]; ~i; i = to[i]) {
            int v = ver[i];
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addedge(u, v);
        in[v] ++;
    } toposort();
    // for (int i = 1; i <= n; i++) {
    //     printf("%d ", ans[i]);
    // }

    for (int  i = n; i >= 1; i--) {
        int j = ans[i];
        f[j][j] = 1;
        for (int x = head[j]; ~x; x = to[x]) {
            f[j] |= f[ver[x]];
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("%d\n", f[i].count());
    } return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

Nicoppa
2019-09-18 20:57
//#define fre yes

#include <cstdio>

int n, m;

const int N = 1000005;
struct Node {
    int idx, x;
} q[N];
int arr[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }

    int front = 1, back = 0;
    for (int i = 1; i <= n; i++) {
        if(q[front].idx + m < i) front++;
        while(front <= back && q[back].x >= arr[i]) back--;
        back++; q[back].idx = i - 1, q[back].x = arr[i];
        if(i >= m) printf("%d ", q[front].x);
    } puts("");

    front = 1, back = 0;
    for (int i = 1; i <= n; i++) {
        if(q[front].idx + m < i) front++;
        while(front <= back && q[back].x <= arr[i]) back--;
        back++; q[back].idx = i - 1, q[back].x = arr[i];
        if(i >= m) printf("%d ", q[front].x);
    } return 0;
}