T1

题目描述：有Num组数据，每个数据给N个整数，表示有N个地区（一个地区可以被抽象为一个圆），再给出每个地区的坐标（x,y），以及他的半径r，最后再给出起点和目标点的坐标（x1,y1）和(x2,y2),要求求出最少需要穿过的边界数目（1<=Num<=10,1<=N<=50，-1000<=x,y,x1,y1,x2,y2<=1000,r<=1000）

赛时乍一看以为很难，差点就要偷偷骂上几句，但仔细一想，其实挺简单的，因为每个数都是整数，所以运用“勾股定理”就可以算出起点或终点与每个地区的圆心的距离，在判断一下是否大于半径，就能判断是否在地区中，尤其注意的是，如果起点和终点在同一个圆中则是不需要穿过边界，因此要异或一下

T1 AC代码

#include‹bits/stdc++.›//见谅
#define LL long long
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
const int N = 110;
LL read();//read()函数因bolg的部分问题，再次不放
int t;
struct Node {
    int x, y, r;
} a[N];
int f[1100][1100];
int fun(int x7, int y7, int x8, int y8) {//勾股定理
    return sqrt((x7 - x8) * (x7 - x8) + (y7 - y8) * (y7 - y8));
}
int main() {
    freopen("country.in", "r", stdin);
    freopen("country.out", "w", stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    t = read();
    while (t--) {
        int n;
        n = read();
        for (int i = 1; i <= n; i++) {
            a[i].x = read();
        }
        for (int i = 1; i <= n; i++) {
            a[i].y = read();
        }
        for (int i = 1; i <= n; i++) {
            a[i].r = read();
        }
        int x2, y2, x3, y3, h = 0;
        x2 = read(), y2 = read(), x3 = read(), y3 = read();
        for (int i = 1; i <= n; i++) {
            if ((fun(x2, y2, a[i].x, a[i].y) <= a[i].r) xor (fun(x3, y3, a[i].x, a[i].y) <= a[i].r)) {
                h++;
            }
        }
        cout << h << "\n";
    }
    return 0;
}

T2

题目描述：有Num组数据，每个数据中包含一个数N，表示有N个洞，再给出N*2个整数，表示每个洞的两个端点编号，所有端点都是严格递增顺序给出，最后有一个整数largeJump。正走在一条无限长的直线道路上（道路下标可为负数）。Iris的家是在0点上，而她想要见的朋友在点1000000001。她是兔子当然只能通过移动跳跃前行，她有两个跳跃类型：小跳和大跳。当她在点x，通过一小跳，她可以移动到点（x + 2）或（x – 2）。通过一个大跳跃，她可以移动到点（x + largeJump）或点（x – largeJump）。不幸的是，道路总是那么坑坑洼洼，洞的大小不一，有些还可能包含连续几个点，Iris不能跳到这些洞中。Iris喜欢用小跳，因为这样更加的省力。请问到达1000000001所要使用的最少的大跳跃数量。如果不能达到这一点，输出-1。（1<=Num<=10，1<=N<=25，3<=largeJump<=1000000000）

见到题目就觉得我肯定不会打，于是我决定打暴力，首先发现如果largeJump为偶数的话，一定到不了朋友的家，所以输出-1，然后因为不会了，注意到可以输出-1，所以全部输出-1，因题目有多组数据，因此没能得（骗）到分

正解思路

这一题其实可以构建图论模型！注意到小跳跃是没有代价的，而且小跳跃之后所在节点奇偶性不变。由于每个洞是不能进入的，所以可以把每段可以走的路作为节点，再把这个节点拆成两个点，其中一个表示这段能走的路的奇数点，另一个表示偶数点。然后枚举每对节点，如果可以从i节点大跳跃到j节点，则连边。最后求一次最短路就ok！由于是不加权的图，用bfs就可以了

AC代码

你觉得我像是会吗

T3

题目描述：给定x 轴上n （n<1000）个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交，给定n 个闭区间，编程计算去掉的最少闭区间数

题目其实很简单，我赛时想了一个贪心策略，但其实不对，莫名其妙得了80分，说明数据真的水

AC想法

有两种：
1：zmx提供的dp做法（不知道真对假对，有可能是碰巧对了，在此不做赘述）
2真正的正解：贪心算法，策略是在可选区间中选右端点最小的，右端点越小，之后可选的区间越多。所有区间按ri排序。首先可以去除区间包含的情况(只留小区间)。此时的li同样是有序的。考虑前两个区间，若不选第一个区间，则相当于[l1,l2]这段区间无用。此时也是种包含情况，选第二个不会更优

AC代码

你在期待什么还没打

T4

这里我放原题描述，因为我没读懂原题

题目描述：
在2240年，一场巨大的战争在地球联合力量（EAF）与火星联盟(MF)之间展开。至今，双方势均力敌。因最近的一次经济危机，资源紧缺，EAF将被MF勒要更多领土。为此，EAF决定采取战争以来最重要的行动：发动对分散在MF上各处的基地进行同时攻击。EAF的力量大都是mechs——大型两足跛行车，有飞行功能。
典型的MF基地概况如下：构成基地的房屋地跨一到两块领土。每块领土被保护塔产生的穿不透的能量层所笼罩，以免于外来袭击。这些保护塔围绕在领土周围起保护作用。
每座保护塔通过建造在地面上的水道与至少一座塔相联系。当那些相联系的塔围成一圈，它们产生能量层。否则能量层消失。
MF知道如果能量层消失，基地将很容易被EAF的力量侵占，因此，被水道相连的两座塔保护水道免受军事袭击。每座塔有防御功能，能拆卸指定数量的mechs，每个水道在坍塌之前能解决特定数量敌方mechs的袭击。这个数量由水道连接的两塔能拆卸的总数量决定。两座塔不能被一个以上的水道相连。
但是，袭击塔一边的水道不减少塔在另一边能拆卸的mechs的数量。因为这次行动是突袭，所有的对水道的袭击都必须同时，所有水道同时坍塌瓦解。
所有能量层必须废除才算毁灭了一个MF基地。破坏所有水道能达此目的，但也将需要很多mechs 牺牲。EAF只有很少的力量花费了，必须最有效率地部署mechs。
你被赋予这任务，写程序：使EAF胜利。给定一幅保护塔的曲线图，决定哪些水道要被破坏，来使所有能量层消失，要求战斗中牺牲最少的mechs。
Input Format
第一行为一个整数m，2 < m <= 100，代表塔的数量。
以下2m行，对于每个塔都有两行输入：
◎一行包含三个正整数i(0 <= i <= m-1)，ui(1 <= ui <= 50)，ci(1 <= ci <= m-1)：每个塔的身份标识、可以摧毁的mechs的数量和与它相连的河道的数量。两个整数间用一个空格隔开。
◎一行包含ci个不同的正整数，代表和塔i连接的塔。一个塔不能连接到它自己，两个整数间用一个空格隔开。
该防御体系至少能够生成一个能量层。
不一定所有的塔连通。
Output Format
一行一个整数，代表EAF摧毁所有能量层所需要消耗的最少数量的mechs。

AC思路

最大生成树

AC代码

你在期待什么

T5

题目传送门 洛谷P1327
题目描述：给定一个数列{a}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？（-2^31<ai<2^31，n<=100000）

赛时都没发现这题我一年前打过，我赛时连打（骗）都没打（骗）

AC思路

因为每一个数都有一个属于自己的最终位置，所以我们让每一个数换到它最终的位置之后，他就不用再动了。也就是每个数换一次。每个数分配一次，那么理论的时间复杂度就是，O(n)。具体代码只需要模拟这个思路即可。

AC代码

这个我终于会了

#include‹bits/stdc++.h›
#define LL long long
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
const int N = 110;
LL read();//bolg有问题，自己打吧
struct node {
    int before, after;
} q[1000001];
int s[100001];
bool cmp(node x, node y) {
    return x.before < y.before;
}
int main() {
    freopen("seqsort.in", "r", stdin);
    freopen("seqsort.out", "w", stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    int  n, ans = 0;
    n = read();
    for (int i = 1; i <= n; i++) {
        q[i].before = read();
        q[i].after = i;
    }
    sort(q + 1, q + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        s[q[i].after] = i;
    for (int i = 1; i <= n; i++) {
        while (s[i] != i) {
            swap(s[i], s[s[i]]);
            ans++;
        }
    }
    cout << ans;
    return 0;
}