InTheBloodHorse

InTheBloodHorse

Hey~

每日一题(49) codeforces 1091B
题目地址 题意给n个坐标以及n个向量,坐标与向量组合可以得到一个目的坐标,要求输出每个坐标与任意一个向量组合都可以得到的目的坐标的坐标。(可能有多个,随意输出哪个) 思路n最大为1000,所以可以暴力求解。暴力将每一个坐标与每一个向量进行组合,并计数,计数为n的坐标就是目标坐标了。 AC代码:123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;int n;map<pair<int,int>,int>m;ve...
数据结构与算法(10) KMP算法
什么是KMP其实在大一下暑假就接触到了KMP,那时候真心看不懂,后续在日常训练中,也几乎遇不到KMP的题目,所以KMP在很长一段时间就被搁置了,只知道KMP里面有一个叫next数组。现在重新捡回来。KMP是解决在字符串A中查找字符串B的下标的问题,即字符串的匹配过程,假如找到字符串B,返回下标,否则返回-1。 为什么选择KMP查找子串里,最容易想到的就是暴力枚举了,假设字符串A长度为n,要查找的字符串B长度为m,这时候的时间复杂度为 n * m,在数据规模很大的情况下就显得不尽人意。其实KMP可以理解为在上述基础上的优化,就是通过已知信息,去省去一些不必要的操作。 PMTKMP算法的核心...
每日一题(48) codeforces1091A
题目地址 题意给三个数字,abc,在不大于abc的数值下,输出abc为等差数列,差值为1的最大值,例如,13,5,6,答案为4+5+6 AC代码:1234567#include<bits/stdc++.h>using namespace std;int main(){ int a,b,c; cin >> a >> b >> c; cout << min(min(b,a+1),c-1) * 3 << endl;}
每日一题(47) codeforces 1097C
题目地址 题意给你n个字符串,由()组成,要求把这些字符串两两拼接起来,使得满足()的规则数量最多。 思路先预处理字符串,先把原字符串内符合条件的删除,最后会得到四种结果: (这是个空字符串) …))))) (n个右括号) …((((( (n个左括号) …))))((((….. 第一种情况的话,只能和第一种情况合并,也就是第一种情况的数量/2第二种情况只能和第三种情况中拥有相同数量的括号合并第三种情况同理第四种不可能拼接成符合规格的,可以忽略 其实这题难点不在实现,想法也不难,就是卡超时,空间换时间。 AC代码:12345678910111213141516171819202122...
数据结构与算法(9) 二进制枚举
什么是二进制枚举二进制枚举是用来枚举子集的。即把问题转化成二进制的思想,根据转化后的二进制每位的数字(0 | 1)来确定状态。例:现在要记录5名学生的期末成绩,1表示通过,0表示不通过,结果会有 2^n 次可能,用二进制表示的话就是从00000 ~ 11111(十进制下为数字 0~31) 复杂度在例子的5名学生中,运算了 32 * 5,所以复杂度为 N * 2^N同样的,DFS也可以解决类似问题,复杂度差不多 位运算在c语言中 << 代表左移 比如 1<> 右移同理 代码 123456789101112131415161718#include<bits/st...
每日一题(46) codeforces 1097B
题目地址 题意给n个数字,问这n个数字之间 或加 或减运算,能够使转盘的指针最终指向0 解法一:好久没写搜索了。很是激动。1void dfs(int index,int op,int sum) index代表操作次数,op代表运算操作(- | +),sum代表当前指针位置 AC代码:12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;int a[1004];int n;string ans;void dfs(int index,int o...
每日一题(45) codeforces 1097A
题目地址 题意给一个目标字符串AB,接下来给五个字符串XY,假如X=A || Y=B输出YES AC代码:12345678910111213141516171819#include<bits/stdc++.h>using namespace std;map<char,int>m1;map<char,int>m2;int main(){ string ans = "NO"; string need; cin >> need; string ff; m1[need[0]] = 1; m2[need[1]] = 1; for(int i...
每日一题(44) hud 1558线段相交
题目地址 题意给N条线段,给一个K,问与第K条线段’相交’的线段有几条(线段之间有联系,即A与B相交,B与C相交,那么A与C也算’相交’) 思路并查集,还是用int数组去记录关系,一个数组存index,一个数组存结果(即index位相交的线段个数)AC代码:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<bits/stdc++.h...
每日一题(43) hud1232
题目地址 题意同样是无方向连通问题,目标是全省任何两个城镇连通,问至少还需要建设几条道路 思路简单的并查集AC代码:1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;int a[1005];int find(int x){ int ans = x; while(a[ans]!=-1){ ans = a[ans]; } return ans;&...
每日一题(42) hud1213
题目地址 题意某人在生日当天邀请了很多朋友,但是他的朋友不愿意和不认识的坐在一起,假如A认识B,B认识C,那么A,B,C就可以坐在一张桌子,问他至少需要准备几张桌子? 思路简单的并查集。AC代码:1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;int a[1005];int find_root(int x){ int root = x; while(a[root]!=-1){...
avatar
InTheBloodHorse
你得抛开过去的事
FRIENDS
阿汤哥