首页 > 其他分享 >10.7 杂题补做

10.7 杂题补做

时间:2023-10-08 19:33:24浏览次数:39  
标签:return 10.7 ll long x% 异或 杂题 复杂度

难度超标 属实逆天
考完全员爆蛋(((

T1 ACM_51nod 1984

简要题意 定义 \(f_i\) 表示 \(\in x|i\) 的异或和
给定 \(n\) 求 \(1\to n\) 所有 \(f_i\) 的异或和

\(n\leq 10^{14}\)

很容易想到枚举每个约数 然后算出现次数异或
时间复杂度 \(O(n)\)
过不去 发现可以用整除分块优化 时间复杂度降成 \(O(\sqrt n)\)

现在的问题转化为怎么快速求出 \(1\to x\) 的异或和
发现有规律 找规律 \(O(1)\) 即可求得

#include<bits/stdc++.h>
#define ll long long
#define reg register 
using namespace std;
ll n,ans;
inline ll get(ll x)
{
	if(x%4==0) return x;
	if(x%4==1) return 1;
	if(x%4==2) return x+1;
	return 0;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%lld",&n);
	for(ll l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		if((n/l)&1) ans^=get(r)^get(l-1);
	}
	printf("%lld",ans);
	return 0;
}

T2 亿只只因的回家路

咕了先(((

T3 西琳的魔法字符串

咕了 非常逆天的一道题目 思维和代码量都不小

标签:return,10.7,ll,long,x%,异或,杂题,复杂度
From: https://www.cnblogs.com/g1ove/p/17749965.html

相关文章

  • 10.7闲话
    摆摆摆,我是姬虫摆摆世。数据结构课终于能听懂了,但是没时间写题了,怎么会是呢......
  • 10.5 杂题补做
    T1雷老师的正偏态分布简要题意:给出一个数组\(a\)要找一段平均数\(<\)中位数的子集的方案其中子集大小是奇数其中\(a_i\leqV\)范围:\(n\leq100\spaceV\leq800\)这里有两个思路1枚举平均数锁定中位数比较难找可以抛弃2枚举中位数锁定平均数我们发现第......
  • linux学习记录 10.7
    苹果电脑的insert=fn+回车acterminal中shift选中复制=ctrl+fn+回车粘贴=shift+fn+回车cp=复制文件+可重命名mv=剪切文件+可重命名 Vim中yy=复制当前行y=复制选中p=粘贴到下一行u=撤销ctrl +r=取消撤销fn+←=在insert模式......
  • 10.7算法
    将有序数组转换为二叉搜索树给你一个整数数组nums,其中元素已经按升序排列,请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。 示例1:输入:nums=[-10,-3,0,5,9]输出:[0,-3,9,-10,null,5]......
  • 2023.10.6 若干杂题
    P1552[APIO2012]派遣每个点作为管理者,只需要计算其子树内,最多有多少个人加起来不大于\(M\),考虑维护前\(k\)小的元素。可以使用左偏树合并。然而其实可以平衡树合并,每次在平衡树上二分。P2685[TJOI2012]桥首先,Boss镇守的桥一定是最短路上的边,使得我们不得不改变线路。......
  • 杂题选记
    杂题选记AStatement给定一个长度为\(n\)的单调不降的整数数列\(A\)。有\(q\)次相互独立的询问,每次询问给定\(l,r\),从时刻\(0\)起,每个时刻对于\(\foralli\in\left[l,r\right)\)且\(A_i\textcolor{red}{\lt}A_{i+1}\),令\(A_i\getsA_i+1\)。问最少经过多少时刻......
  • 动态规划杂题选练
    \(\text{CF908G}\)题目描述给\(n<=10^{700}\),问1到n中每个数在各数位排序后得到的数的和。答案膜\(1e9+7\)。思路点拨不是很难,自己想一会可以想出来。因为\(n\)比较大,所以我们考虑数位dp。因为每一种数组产生的贡献十分复杂,所以我们将每一数字拆开统计贡献。如果我们认......
  • 杂题记录
    CF1771DHossamand(sub-)palindromictree题目链接一个小trick。考虑如果不是在树上,而是在序列上的话,那就设\(f(l,r)\)表示区间\([l,r]\)中的最长的回文串,转移方程为:\[f(l,r)=\max\{f(l+1,r),f(l,r-1),f(l+1,r-1)+2\times[s_l=s_r]\}\]那么转换到树上,就可以设\(p(u,v)......
  • 【杂题乱写】AtCoder-ARC113
    AtCoder-ARC113AA*B*C枚举\(A,B\),那么\(C\in[1,\left\lfloor\frac{K}{AB}\right\rfloor]\),时间复杂度是\(O(K\logK)\)。提交记录:Submission-AtCoderAtCoder-ARC113BA^B^C\(A^k\)的末尾存在循环节,找到循环节长度\(|T|\),答案就是\(A^{B^C\bmod|T|}\bmod10\)。提......
  • 杂题选讲
             ......