一周时间过的这么快，马上第二场的萌新联赛就结束了，对比上一场，这次罚坐的时间更长了，感觉平时学的知识在比赛中根本开不到算法题，这次的A题是一个数论中的整除分块的问题，卡了我好久好久，后来才知道是自己见识短浅了（其实就是一个模板题），卡的我没心态去开其他题了。
打瓦
能想出来这种题目的也是很时髦了，废话不多说，题目来源于：K-打瓦
这是一道签到题，读完题之后就会发现不管输入的是啥，最后都让你输出同一个字符串，那就直接输出即可。
// Problem: 打瓦
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/K
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
void pre_handle()
{
string s;cin>>s;
cout<<"gugugaga"<<endl;
}
void solve()
{
}
signed main()
{
IOS
int T=1;
pre_handle();
// cin>>T;
while(T--) solve();
return 0;
}
猜数游戏（esay）
题目链接：I-猜数游戏
这道题很明显最优解就是不断的用二分来取中间值，所以直接用函数log2计算即可，不过要注意如果log之后有剩余的话就还需要加一（向上取整）。因为x是随机的，要想让他采取的次数最多，就要让x等于2（不唯一，相对于1来说2他需要多猜一次）的时候可以让他多猜一次（因为交互机只会告诉他当前猜的数是否大于x，而不会告诉他等于x，当x=2的时候他只知道交互机给出的结果为false，所以他会猜1，结果还是false，那么这时候他才就知道x等于2了）。
// Problem: 猜数游戏(easy)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/I
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
void pre_handle()
{
}
void solve()
{
int n;cin>>n;
int ans = log2(n);
if(pow(2,ans) != n) ans++;
cout<<ans<<endl;
}
signed main()
{
IOS
int T=1;
pre_handle();
// cin>>T;
while(T--) solve();
return 0;
}
米娅逃离断头台
题目链接：米娅逃离断头台
这道题感觉出的挺好的，完全就是数学逻辑，只不过题目中给出的示意图会迷惑你，其实你只要把小半圆移到中间就能发现规律。
要想求阴影部分的面积，就要求出大的半圆的面积减去小的半圆的面积即可，实际上就是只需要知道两个半径就行了，但其实半径具体是多少求不出来，但是可以根据公式来整体替换
ans = 0.5 * π * (R² - r²) 这个就是阴影部分面积的计算公式，那么我们如果将小半圆移到中间再连接OA的时候，就可以发现构成了直角三角形，那么此时就可以根据勾股定理得到如下半径的关系：r² + (x / 2)² = R² 移过来就是 R² - r² = (x / 2)²，而(x / 2)²我们是知道的，因为题目中给出了x的值，所以这道题也就引刃而解了！
// Problem: 米娅逃离断头台
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/M
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
double pi = 3.1415926535;
void pre_handle()
{
}
void solve()
{
int x;cin>>x;
double r ,R;
double xx = x/2.0;//用double精度即可通过 用long doble的话就需要输出llf了
xx *= xx;
printf("%.2lf\n",0.5 * xx * pi);
}
signed main()
{
IOS
int T=1;
pre_handle();
// cin>>T;
while(T--) solve();
return 0;
}
约数个数和
题目链接：约数个数和
这道题要着重讲一下了，因为这道题涉及到了我不会的数论中的整除分块的解法
整除分块算法（又称数论分块、除法分块）是一种通过分组优化整除计算的技巧，主要用于快速求解包含除法或取整运算的和式。其核心思想是将相同的整除结果分组计算。
在遍历因子的过程中，n/i 代表了从1到n中有多少个i的倍数，然后再通过n/k[n/i]就能算出全为k的区间的右端点，然后由左端点就是上一个右端点+1计算出区间的长度，最后通过求乘积一下子将这个区间内的所有的数都给计算出来，达到跳着遍历的优化实现。详解代码如下：
// Problem: 约数个数和
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/A
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
int n;
void pre_handle()
{
//找因子 ——》 找倍数
}
void solve()
{
cin>>n;
int ans=0;
int l=1,r=1,k;
for(int i=1;i<=n;i++)//枚举所有的因子
{
k = n/i;//从1到n里面有几个i的倍数
r = n/k;//通过整除分块来确定右边界
ans += k*(r-l+1);//这个区间内的所有因子在1到n中都有k个该因子的倍数（即他们都作为k个数的因子）
l = r+1;//更新完答案之后更新左边界
i = r;//直接跳过这段区间 省去大量时间！
}
cout<<ans<<endl;
}
signed main()
{
IOS
int T=1;
pre_handle();
// cin>>T;
while(T--) solve();
return 0;
}
异或期望的秘密
题目链接：异或期望的秘密
这道题最后的输出是以乘法逆元的方式输出，所以要用到快速幂和费马小定理计算乘法逆元，我们可以根据二进制的规律来计算从l到r区间内每一位上1的个数之和，然后以位为单位计算分子（1的个数）最后因为是等概率所以每一位的概率都相等，所以最后累加完之后成区间长度分之一即可。
不过需要注意的是在枚举二进制的每一位的时候需要去判断枚举当前位不能超过r和y的最高位，否则在计算的时候y的第i位一直是0，而x的第i位一直是0所以最后计算当前位的贡献的时候就会多加好几个区间长度！具体的判断方法见代码：
// Problem: 异或期望的秘密
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/B
// Memory Limit: 512 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int f(int n,int k)//从0到n 第k位上的1的个数
{
if(n==0) return 0;
int ans=0,t = 1 << (k + 1);//二进制中1的周期性规律 第k位上以pow(2,k+1)的区间长度为规律
n++;//因为周期区间窗口是以0开始的，所以要在前面多补一个0 整体退一位 可以拿1来举例
//1有1个1，但是区间长度从0开始且开始时长度为2 让n++才能正常计算（保证左闭右开区间）
//此时的n表示的是从0开始的第n个数 是不是好理解多了！
ans += n / t * (t / 2);
ans %= mod;
if(n % t > t / 2) ans += n % t - t / 2;
ans %= mod;
return ans;
}
void solve()
{
int l,r,y;cin>>l>>r>>y;
int fz = 0,fm = r - l + 1;//计算期望时的分子和分母
for(int i=0;i<=30;i++)
{
//条件(1LL<<i)<=max(r,y)一定要加上 确保i不超过r和y的最高有效位。
if((1LL << i) <= max(r,y))
{
int sum = f(r,i) - f(l-1,i);//如果y的第i位上是0 则贡献为1的个数
if((y >> i) & 1) sum = fm - sum;//如果y的第i位上是1 则贡献为0的个数
fz += sum;
fz %= mod;
}
}
int ans = fz * ksm(fm,mod-2) % mod;
cout<<ans<<endl;
}
signed main()// Don't forget pre_handle!
{
IOS
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
这时候就有有小伙伴问了，为啥要加这个判断条件？就不能不加吗？当然可以！
但是在计算2的幂的时候千万要注意数据溢出以及数据类型不匹配的问题！只需要在f函数中将数据类型开为long long类型即可通过！上次犯的错这次怎么还犯了呢
// Problem: 异或期望的秘密
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/B
// Memory Limit: 512 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int f(int n,int k)//从0到n 第k位上的1的个数
{
if(n==0) return 0;
int ans=0,t = 1LL << (k + 1);//二进制中1的周期性规律 第k位上以pow(2,k+1)的区间长度为规律
n++;//因为周期区间窗口是以0开始的，所以要在前面多补一个0 整体退一位 可以拿1来举例
//1有1个1，但是区间长度从0开始且开始时长度为2 让n++才能正常计算（保证左闭右开区间）
//此时的n表示的是从0开始的第n个数 是不是好理解多了！
ans += n / t * (t / 2);
ans %= mod;
if(n % t > t / 2) ans += n % t - t / 2;
ans %= mod;
return ans;
}
void solve()
{
int l,r,y;cin>>l>>r>>y;
int fz = 0,fm = r - l + 1;//计算期望时的分子和分母
bitset<35> b(y);
for(int i=0;i<=30;i++)
{
int sum = f(r,i) - f(l-1,i);//如果y的第i位上是0 则贡献为1的个数
if((b[i]) == 1) sum = fm - sum;//如果y的第i位上是1 则贡献为0的个数
fz += sum;
fz %= mod;
}
int ans = fz * ksm(fm,mod-2) % mod;
cout<<ans<<endl;
}
signed main()// Don't forget pre_handle!
{
IOS
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
开罗尔网络的备用连接方案
题目链接：开罗尔网络的备用连接方案
这道题就是一个简单的树的应用，用双向无向边将两个点连接起来建树最后遍历将每个点的答案更新即可。
// Problem: 开罗尔网络的备用连接方案
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/114408/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+10;
vector<int> e[N];
vector<int> res(N,0),a(N,0);
int n,q;
void dfs(int x,int w,int f)//因为是无向边 所以用一个参数用来表示这个点的父节点 防止倒着遍历上去了 用以保证正常的树的搜索方式
{
int k = a[x]&w;
bitset<40> b(k);//位运算之后用bitset来转为二进制 便于统计1的个数
res[b.count()]++;//这个点的类型（二进制和点权进行按位与后的1的个数）++
for(auto i : e[x])//遍历这个节点的所有子节点（因为是无向边 所以要加一个if防止往上递归）
{
if(i==f) continue;
dfs(i,k,x);//进行正常的数的遍历 i就是子节点 k就是当前的按位与w的状态 x表示在递归这几个子节点的过程中的父节点 因为e[x]中会存他的父节点
}
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];//每个点的点权
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,-1,0);//因为要进行与操作所以用-1（二进制全为1）作为dfs的初值
while(q--)
{
int x;cin>>x;
cout<<res[x]<<endl;
}
}
signed main()
{
IOS
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
回顾一下往年的萌新联赛的二进制问题：
累加器
题目链接：累加器
我一开始想到的是遍历利用异或操作中的相异就为1的特性然后用bitset来直接统计1的个数，可是数据范围确实有点大了，每次都遍历的话会导致时间超限的，所以就只能看看有没有什么规律所在，枚举1-15的二进制位就可以发现，第0位上每加1就会变一次，第1位上每加2就会变一次，第二位上每加4就会变一次....所以就能根据这个规律，从第0位开始不断的累加每一位即可。
// Problem: 累加器
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/87865/F
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+10;
int res[N];
void pre_handle()//利用异或的性质和bitset并预处理 但还是不够 因为x+y会很大 根本不够跑一遍
{
int xx=1,ans=0;
for(int i=1;i<N-1;i++)
{
int k = xx;
xx++;
int t = xx ^ k;
bitset<40> b(t);
ans += b.count();
res[i+1] = ans;
}
}
int an(int x)
{
int ans=0,f=1;//从第0位上开始枚举每一位
while(x>=f)
{
ans += x/f;//统计1的个数
f*=2;
}
return ans;
}
void solve()
{
int x,y;cin>>x>>y;
// cout<<res[y+x] - res[x]<<endl;
cout<<an(x+y) - an(x)<<endl;
}
signed main()
{
IOS
int T=1;
// pre_handle();
cin>>T;
while(T--) solve();
return 0;
}
小蓝的二进制询问
这道题数据范围更大，肯定也是要找规律，将1-15的二进制位枚举出来就能发现，从0开始（在所有的数的前面加一个0），在第0位上每2个数就有1个1，第1位上每4个数就有2个1，第二位上每8个数就有4个1....以此类推就能写出代码，详解见代码：
// Problem: 小蓝的二进制询问
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/86639/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int mod = 998244353;
int res(int x)
{
x++;//因为要从0开始计算 所以多加一个0
int ans=0,k=2;//因为一开始是两个数为一个循环 所以一开始就2个2个的看
while(x>=k/2)//x的最高位如果在第n位上，那么此时的k就为2*(2^n)（因为二进制位上有一个第0位）
{
//更直观的来讲 第0位的时候x为2^0但是k为2^1，第一位的时候x为2^1、k为2^2 所以每一位上k都为x的两倍
ans = (ans + (k/2)%mod * (x/k))%mod;//循环集里面的1的数量
if(x%k) ans = (ans + max(0LL,(x%k) - (k/2)))%mod;//如果有剩余(循环集外面还有数 计算剩余的1的个数)
k*=2;//循环集的大小每次都是乘2 同时也可以通过循环集的大小来计算当前的循环集所代表的数与x进行比较
}
return ans%mod;
}
void solve()
{
int x,y;cin>>x>>y;
//输出的时候要多加一个mod因为两个结果都是取模的结果 可能会出现负数 这时候实际上两者之间差距还是很大的所以要加上一个mod
//比如 res(l) = mod+2,res(r) = 2mod+1,实际上相差mod-1,取模后还是mod-1,但是都取模再相减的话就是-1，所以要加上mod变为mod-1再进行对mod取模运算
cout<<(res(y)-res(x-1) + mod)%mod<<endl;
}
signed main()
{
IOS
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
也可以用k=1作为初始值：
// Problem: 小蓝的二进制询问
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/86639/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int mod = 998244353;
int res(int x)
{
x++;
int ans=0,k=1;
while(x>=k)
{
ans = (ans + k*(x/(k*2)))%mod;
if(x%(k*2)) ans = (ans + max(0LL,x%(k*2) - k))%mod;
k*=2;
}
// if(x%2) ans++;
return ans%mod;
}
void solve()
{
int x,y;cin>>x>>y;
cout<<(res(y)-res(x-1) + mod)%mod<<endl;
}
signed main()
{
IOS
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
至于为什么要让x++，因为只有算上0的时候才满足这样的规律，所以在前面补充一个0，这是原本所有的数都要往后移一位，原本1的位置就变成了0，所以函数传进来的是x实际上是计算的从0 到x-1时候的答案，所以直接x++，或者像下面一样直接传入x+1的值即可。
int x,y;cin>>x>>y;
cout<<(res(y+1)-res(x) + mod)%mod<<endl;取模
题目链接：取模
这道题是整除分块的进阶版本，其实也不难，只是需要用“/”和“%”的关系公式推导一下即可：
第一次用__int128还不是很熟练，一直报错和溢出...
// Problem: 取模
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/30532/K
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
const int mod = 998244353;
void solve()
{
int x;cin>>x;
__int128 n = x;
__int128 res = n*n;//类型转换
__int128 l=1,r=1;
for(l=1;l<=n;l=r+1)
{
int k = n/l;
r = n/k;
res -= ((l+r)*(r-l+1)/2*k)%mod;//注意这里不是区间长度*k，而是系数的和*k
res += mod;
res %= mod;//因为rs也要取模所以防止负数出现
}
int ans = res%mod;
cout<<ans<<endl;;
}
signed main()
{
IOS
int T=1;
// cin>>T;
while(T--) solve();
return 0;
}
沉淀沉淀！！！之后的题目还会在本文更新！