B.Fire-Fighting Hero 题意： 有个着火点和条联通的路保证整张图联通，现在有一个消防英雄和支消防队伍，消防英雄要一个人从点灭完所有的火，支消防队伍可以合作灭完所有的火，比较消防英雄灭完最短路最大值点的距离除和消防队伍灭完最短路最大值点的距离 题解： 题意比较难读懂，消防英雄的答案只需要以点作为起点跑一遍最短路即可，消防队伍可以合作，因此可以将这个点都作为起点放入优先队列中跑一遍最短路 #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef lon...

Sequence II(主席树) 题意： 给定一个长度为的序列和次询问，每次询问给定一个区间，求出现的不同数中，第个数的位置 题解： 倒序遍历，对每个位置建一棵树，记录每个数字上次出现的位置并更新，那么每次询问就是对第棵树求区间的和，并求第大即可，理解清楚本质就是主席树裸题 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; struct node { int l, r, sum; } T[maxn * 50]; int root[maxn], a[maxn], ans[maxn], cnt...

A.Who is better? 题意： 给定组和，。两个人互相拿这个个数，先手第一次不能拿完，每次后手只能拿到前一次拿的数量之间的数量，不能拿时则输 题解： 可由中国剩余定理求出，算出前几个数可以猜测为斐波那契数列时先手必败 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 105; ll b[maxn], a[maxn], f[maxn]; int n; ll Ex_gcd(ll a, ll b, ll &x, ll &y) { if (b =...

1002 Graph Theory Class 题意： 给定一个个结点的完全无向图，结点间的权值为，求最小生成树的值 题解： 分析可以发现一个合数的贡献就是它本身，而质数和的为两倍的质数，因此最终结果就是中所有合数的和加上两倍的所有质数的和。那么就是加上质数和，的和就是，而质数和可用min25筛求。要注意用long long会爆精度。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000010; ll prime[maxn], id1[maxn], id2[...

A.The beautiful values of the palace 题意： 给定一个阶的螺旋矩阵，其中个点是有价值的，个询问，每次询问求出和组成的矩形内的价值  题解： 通过分析推出公式可以的算出螺旋矩阵每一个点的价值，先求出目标块在哪一圈层，然后判断在所在圈的哪一侧边，分类计算即可。对于求值本质是一个二位前缀和，但是考虑到复杂度求出二位前缀和显然是行不通的。可以对点按x坐标进行升序，这样可以保证这样我们只要求出小于等于的值之和即可。可以用树状数组或者主席树解决。 方法一：主席树 #include<bits/stdc++.h> #define ll long long usi...

Allowed Letters（贪心+霍尔定理） 题意： 给定一个字符串，给出个条件，每个条件要求位置只能填某些指定的字符。要求输出满足条件且字典序最小的，否则输出。保证字符只包含 题解： 首先可以想到可以用最大流解决，从源点向个位置依次连一条流量为的边，在对个条件，每个向对应的几个字符都连一条流量为的边，最终个字符都向汇点连一条的边，最终只需要跑一遍最大流判断最大流是否为即可。这样确实可以判断当前字符串是否满足条件，但是考虑到最坏情况要跑次最大流，肯定会超时，因此想到可能需要优化一下判断字符串满足条件的方法。 霍尔定理：设二分图的两部分为，且。则定理描述为：二分图存在完美匹配，等价于对于的任...

Subset(折半枚举+二分查找) 题意： 给定个数，要求找到一个子集，使得子集内所有数绝对值之和最小，当有不同子集都最小时，输入子集大小最小者。输入最小的和和子集的大小（） 题解： 观察到，如果对这个数都进行枚举，当较大时就会超时，但是考虑到折半枚举，分成和两部分，最高是次，是可以接受的。因此可以对前算出每种情况的绝对值之和，同时记录每种情况的和和数量。在枚举后时，只需要同前一样算出每种情况和的同时，在算出每种情况的和的相反数与前最相近的前后结果，更新最小值即可，这个寻找最接近的数可以通过二分查找来实现。 #include <cstdio> #include <iostre...

A Star not a Tree? (模拟退火或三分套三套) 题意： 给定个点，要求找到一个点到这个点的欧式距离最小，输出最小距离。 题解： 三分套三分：当值固定的时候，随着的值从小到大，距离会先减再增，存在一个最小值；同理值固定，值从小到大变化，距离也会先减再增，存在一个最小值。那么就可以考虑用第一个三分求出最小的值，这个三分的check()函数就是当前和最小的值时的距离，而最小的值同样也可以用三分来求，这个三分的check()函数就是当前x和y时的距离 模拟退火：对于本题，开始随机选一个点（最好是包围盒的中心点）作为出发点，计算评价函数.然后按一定的步长作一次随机位移，到达新点，如果评价...

又见回文(区间dp) 题目：   题解： 可知只有当第一个串的头部和第一个串的尾部、第二个串的头部和第二个串的尾部、第一个串的头部和第二个串的尾部、第一个串的尾部和第二个串的头部四种情况才会使得回文的长度增长。因此，布尔型变量用表示串从到，从到能否组成新串，初始化为,则采取区间动态规划，每次更新最大值即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; const ll mod = 998244353; char a[55], b[55]; ...

A.Permutation 题意： 给定一个质数，要求给出一段的排列，使得或 题解： 暴力枚举或者的情况即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; bool vis[maxn]; int main() { int t; cin >> t; while (t--) { int p; cin >> p; for (int i = 0; i <= p; i++) vis[i] = false; vis[0] ...

A.Groundhog and 2-Power Representation 题意： 要求计算给定的式子的值 题解： 将式子中的"("替换成"**("用python的eval()函数即可 print(eval(input().replace('(','**('))) B.Groundhog and Apple Tree 题意： 现在有一棵树，你要从开始跳一遍所有的点并且每条边只能走两次，再回到，每条边都有一个边权，你走过这条边会先消耗点HP，每个点都有一个果子，吃掉这个果子会上升点HP，你在任何时候的HP不能小于.并且你如果休息一秒钟会恢复点HP。问你最少要休息多少时间才能走完这棵树。 题解：...

A. Omkar and Completion 题意： 给定一个，要求构造一个长度为的序列使得任意一个数不是其他两个数的和 题解： 全即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); ...

A.Magical Sticks 题意： 给个长度为的木棒，木棒可以拼接在一起。问最多可以拼接出多少根长度相等的木棒。 题解： 最终都拼成长度为的，和组合，和组合...最终答案为 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n; sc...

A.Required Remainder 题意： 给定，要求找到最大的，使得 题解： 先算出的值，如果，就减去 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll x, y, n; scanf("%lld%lld%lld", &x, ...