A | Mezo Playing Zoma |
A:LR中选择任意步,求最后到达的点的数量
题解:简单题,统计LR数量加上原点即可
B | Just Eat It! |
B:简单题,问是否有连续子段比全部元素之和大、
题解:求最长连续子段[l+1,r]与[l,r-1]两次即可
C | Fadi and LCM |
C:给定n=lcm(a,b),要使max(a,b)尽 可 能 小
题解:注意到最大的最小,也就是两个数是n的因子,那么直接枚举sqrt(n)个较小的因子,判断是否lcm是n,然后取最小即可
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair PII;
ll n,m,k,t;
int main(void){
cin>>n;
ll maxx = n;
if(n == 1){
cout<<"1 1\n";
return 0;
}
ll x,y;
for(ll i = 1;i <= n/i;i++){
if(n%i == 0){
y = n/i;
x = i;
if(x*y == n*__gcd(x,y)){
maxx = min(max(y,i),maxx);
}
}
}
cout<
D | Dr. Evil Underscores |
D:有一个长度为 n 的整数序列,要找到一个非负整数 X 使得 max(ai⊕X) 最小,输出最小值
题解:输入的数据有1e5,每个元素又有ai <= 2^30-1,对每一个数进行亦或运算,考虑位运算,从最高位开始考虑,一开始考虑直接最高位,但是要是有111,110,011,010这类,明显是要大于100的,所以考虑建树,在Trie字典树上DP,每一位要是只有1或者0就是0,要是有1或者0就DP
这里介绍Trie树:本质上是一棵多叉树,例如对于英文,son[N][26]是节点,有26个分支,前面是idx编号,比如son[2][26] = 10表示2的字母z的子节点是10,只要节点是0表示结束
这里建子节点是01的类似二叉树的字典树:注意到位数总共30,当前二进制位置都是1的话,就选择1,都是0就选择0,两种都有就取1< 当然,也可以在跑的过程中建字典树,但是不如预先处理树之后快 Delete a Segment E:给定n个线段覆盖在数轴上,问随便删除一个,剩下的不连续段数最多是多少 题解:先考虑区间修改,然后每次在n个区间中选择一个,该线段在数轴上删除,统计剩余的覆盖片段数量,时间复杂度是o(n^2*数据结构时间)这里的数据结构可以是并查集,也可以是线段树,明显超时,考虑其他方法,这里考虑类似贪心的做法,排序之后从左往右,ans记录总共线段数量,add_union记录删除时候会增加或者减少的区间数量,取最大值再加上原来ans得到答案 ans的做法是遍历序列,只要没有括号嵌套,说明是一段结束了,ans++ add_union考虑三种情况 情况1: (1)-1 -2 2 -3 这样嵌套,那么id2的那一段在id1段中,而且id2与id3的那一段分离,所以删除1在这里可以+1区间数 (2)-1 -2 1 -3 这样嵌套,那么id1段与id3段分离,删除id2段可以增加1 注意到括号匹配之后剩下的首元素恰好是最开始入栈的元素,这里用multiset模拟可以查看首元素,修改里面的元素的栈,首元素与后面的比较判断情况1 情况2: -1 1 这样id1的一段删除之后贡献是-1,直接记录 情况3: -1 -2 1 2,这里2或者1对总线段数的贡献都是0,没有必要记录,删除id2段剩下id1段,反之亦然 欢迎分享,转载请注明来源:内存溢出#include
#include
E #include
评论列表(0条)