引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简要题意:
给定两个 vector,v1=(x1,x2,⋯ ,xn)v_1 = (x_1, x_2, \cdots, x_n)v1=(x1,x2,⋯,xn) 和 v2=(y1,y2,⋯ ,yn)v_2 = (y_1, y_2,\cdots, y_n)v2=(y1,y2,⋯,yn),要求最小化标量积 x1×y1+x2×y2+⋯+xn×ynx_1 \times y_1 + x_2 \times y_2+ \cdots + x_n \times y_nx1×y1+x2×y2+⋯+xn×yn,两个 vector 中的元素可以任意更改位置。
思路:
将 v1v_1v1 和 v2v_2v2 分别按升序和降序进行排序,然后计算即可。
证明在最后。
代码:
#include<bits/stdc++.h>using name ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
对于用斐波那契数列将距离从英里转换为公里,我们可以发现一个性质,误差最小的公里数必然是距离真实值 1.6×n1.6 \times n1.6×n 最近的两个整数之一。
通过拆分英里数,我们可以用斐波那契数列中小的数组合出任何大于等于 222 的整数公里数。所以我们也可以组合出与真实值最近的两个整数,我们只需要在两个整数与真实值的差中取最小值就好了。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint n;int main(){ //ios::sync_with_stdio(0); //cin.tie(0);cout.tie(0); ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
前言:
没学过数位 DP 的可以参考 CSP Wiki。
思路:
考虑数位 DP。
本题只需要在填数时判断一下当前相邻数位差的绝对值之和有没有大于 mmm 就行了。
具体地,对于每次填数,我们需要考虑,当前相邻数位差的绝对值之和有没有大于 mmm。
如果大于,返回本次 000 表示没有答案;否则,我们考虑当前数位是否有限制,接着填数,如果最后一位也填了,并且相邻数位差的绝对值之和没有大于 mmm 就代表本次填的答案是可行的。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longLL n,m;LL dp[20][300][11];int a[20];int cf(LL x ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简要题意:
多组数据。
每组数据给定 nnn(0≤n≤10000 \le n \le 10000≤n≤1000)个区间 [si,ei][s_i,e_i][si,ei](0≤si≤ei≤315360000 \le s_i \le e_i \le 315360000≤si≤ei≤31536000),求所有时刻中同时存在的区间数量的最大值。
思路:
考虑扫描线算法。
对于扫描线的基本步骤,可以参考此博文。
将每个区间的开始点和结束点存下来,然后按照时间顺序排序,如果是起点让计数器加一,否则是终点让计数器减一,我们只需要在计算器里取最大值就好了。
因为终点也算在区间里,所以我们在处理时要优先处理起点。
对于每组数据,时间复杂度为 O(nlogn)O(n \log n)O(nlogn)。
代码:
#include<bits/stdc++.h&g ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
通过观察可以发现有一些字母在所有数字中只出现过一次,我们可以先处理这些字母对应的单词。
比如字母 Z 只出现在 ZERO 中。
在处理完这些后,我们可以发现有一些字母在这些单词中只出现过两次,而其中一个单词已经处理过了,这时我们就可以直接处理另外一个单词。
例如 SIX 和 SEVEN,SIX 中的 X 只在它自己里面出现,已经被处理了,而 S 只在这两个单词中出现,所以剩下的 S 都是 777 的了。
以此类推,我们便可以完成此题。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint T;string s;int main(){ cin> ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意简述:
多组数据。
每组数据给出两个字符串(源字符串和目标字符串),输出所有通过栈操作将源单词转为目标单词的操作字符串(i 表示入栈,o 表示出栈)。
操作字符串按字典序输出。
思路:
使用 DFS 算法,暴力模拟出栈入栈操作,为了保证按字典序从小到大输出,应该优先模拟入栈操作。因为入栈用字母 i 表示,出栈用字母 o 表示,很明显 i 的字典序比 o 小。
特别注意:本题不允许行末多余空格。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longstring st,en;stack<char>sta;int lenen;void dfs(int s, ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
前言:
本题数据范围不大,使用 Floyd 也可通过,但本人练习迪杰斯特拉,所以写的是迪杰斯特拉建反图的题解。
题意:
有 nnn 个点,求有多少个点到 eee 点的最小花费小于等于 ttt。
有多组数据。
思路:
可以发现起点有很多个,但是终点只有一个,我们可以考虑建反图,把终点看做反图起点,然后跑迪杰斯特拉得出终点到每个点的最小花费,然后把花费小于等于 ttt 的点的个数加起来就好了。
输出格式注意。
UVA 的输出格式是谜,本题输出要求每次输出答案后换行,如果这不是最后一组数据,则需要再换一次行;但是如果是最后一组数据则只需要换一次行。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsi ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
题意:
输入 nnn 行,每行一个分数,格式为 p/qp / qp/q(数字与字符中间有空格),你需要将分数简化到最简形式并按格式输出。
其中 1≤p,q≤10301\le p,q \le 10^{30}1≤p,q≤1030。
思路:
我们知道,一个分数的最简形式可以通过将分子和分母同时除以它们的最大公因数来获得。
那么先不考虑数据范围,我们可以得到一个简单的代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint n;LL p,q;int main(){ cin>>n; char k; while(n--){ cin>>p ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
发现题解区的线段树题解都是建 262626 棵线段树的方法,来一个不建 262626 棵线段树的线段树题解。本题思路其实来源于上课老师讲了这题,并且用的是本题解的方法。
思路:
线段树。
本题除了操作三以外是模版,本题解主要讲操作三,没学过线段树出门右转线段树模版。
我们知道线段树把区间全部修改成同一个值是很简单的,但是本题操作三是要求排序,很可能是修改成不同的值,怎么办呢?我们可以想到既然是要求排序,那么排序后的值是不是连续的,既然是连续的,那是不是可以把它转换为一个普通的区间修改。
考虑把要排序的范围里的所有字母的数量求出来,然后按顺序枚举每个字母,确定排序后被排到了哪个范围,然后正常区间修改就好了。
如何确定被排序后在哪个范围内?首先设现在的起点为 ststst,有 numnumnum 个这个字母,那么修改的这个区间大小也是 numnumnum,但 ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
通过分析,可以发现:
当 nnn 和 mmm 中有一个为 111 时,只用一条线就可以,答案为 111。
当 nnn 和 mmm 中没有一个为 111 时,当 n<mn<mn<m 时,最优方案是是用 nnn 条线把每一行的所有车站连起来,再用一条线把一列连起来,就可以实现,答案为 n+1n+1n+1;同理当 n<mn<mn<m 时,答案为 m+1m+1m+1,综上 ans=min(n,m)+1ans=\min(n,m)+1ans=min(n,m)+1。
如果还是无法理解,可以看看图片。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigne ...