补题
小蓝有 𝑡 组询问,每次给定两个数字 𝑙, 𝑟 你需要计算出区间 [l,r] 中所有整数在二进制下1的个数之和。由于结果特别大,你只需要计算出结果模998244353之后的值即可。
#include<bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define ll long long
long long solve(long long l,long long r)
{
ll dn=0;
ll res=0;
for(ll i=0 ,j=2;i<62;i++,j*=2)
{
if(l>>i&1)
{
ll st=l+dn+1;
if(st>r)
{
res=(res+r-l+1)%MOD;
continue;
}
res=(res+dn+1)%MOD;
ll len=r-st+1;
res=(res+(len/j)*(j/2))%MOD;
res=(res+max(0ll,len%j-j/2))%MOD;
}
else
{
ll st=l+dn+1;
if(st>r)
{
continue;
}
ll len=r-st+1;
res=(res+(len/j)*(j/2))%MOD;
res=(res+min(j/2,len%j))%MOD;
dn+=(1ll<<i);
}
}
return res;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
long long l, r;
cin>>l>>r;
cout<<solve(l, r)<<endl;
}
}
方法的核心思想是计算在二进制中每一位1出现的次数之和,如最低位中每2个数就会出现1个1,如{0,1},次低位中每4个数会出现2个1,{00,01,10,11};对st的处理则是保证第i位之前的数均为0,就是在周期的开头或者中旬,并且如果l的第i位是0/1,st则会是1/0,然后对未满一个周期的长度进行处理,如果st>r并且l与r的位数一致(二进制下),则l到r的每个数都会提供一个最高位的1,计入答案
爱探险的朵拉(dfs)
某天朵拉穿越到了一个冒险世界中,该世界共有 n 个冒险关卡,朵拉可以选择任意一个关卡作为起始关卡,若朵拉选择了 𝑖 i 号关卡,则完成该关卡的冒险后,朵拉可以选择回到原来的世界即冒险结束,或选择传送到第 𝑎 𝑖 a i 号关卡,(其中对于任意一个 𝑖 i 号关卡,其 𝑎 𝑖 a i 号关卡是固定的。)由于朵拉喜欢探险,因此她想向你请教她最多可以探险多少个不同的关卡。
#include <iostream>
#include <cstring>
using namespace std;
/*
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
*/
const int N = 1e6 + 10;
int e[N], dis[N], ne[N], h[N], idx;
bool vis[N];
int res;
void add(int a, int b) {
e[a] = b;
}
void dfs(int i) {
if(dis[i]==-1)
{
vis[i]=true;
dis[i]=0;
res++;
dfs(e[i]);
}
if(e[i]==i)
{
vis[i]=true;
return ;
}
return ;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
memset(h, -1, sizeof(h));
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
add(i, x);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if(!vis[i])
{
res=0;
memset(dis, -1, sizeof(dis));
dfs(i);
ans = max(ans, res);
}
}
cout << ans << endl;
return 0;
}
没啥好说的,凑合看一下,优化完ac不了就这样简陋了