今晚看了一下低年级组的几道题写了个题解。
D-我裂开来读题，首先肯定是想的暴力做法一个一个求，然后发现 1 e 5 ∗ 1 e 6 1e5*1e6 1e5∗1e6的复杂度显然不可能，那么怎么解决呢？
我们稍微想一下可以知道我们可以开一个 1 e 6 1e6 1e6的 l o n g l o n g long long longlong 数组来存储 1 → 1 e 6 1to1e6 1→1e6的每个数的立方，在查找答案直接用 b b b去数组中比较答案，当然如果直接找也会花费很高时间，但是可以通过二分这个算法(这个算法想知道的同学可以自己去学习一下)来查找答案，复杂度 O ( t ∗ l o g n ) O(t*logn) O(t∗logn)，代码如下:
const int MAX_N = 1e6+10;
ll t,n,m,a[MAX_N],b[MAX_N];
int find(int l,int r,ll ans){
int mid = (l + r) >> 1;
if(b[l]==ans){
return l;
}else if(b[r] == ans){
return r;
}else if(b[mid]==ans){
return mid;
}else if(b[mid] > ans){
return find(l,mid,ans);//说明答案在区间左半边直接找这半边
}else{
return find(mid+1,r,ans);//说明答案在区间右半边直接找这半边
}
}
int main(){
ios::sync_with_stdio(0);
for(ll i=1;i<=1e6+5;i++){b[i] = i * i * i;}
cin>>t;
while(t--){
cin>>m;
int index = find(1,1e6+5,m);//二分函数查找答案
cout<
F-Ginger与区间和
这道题看题是一个简单的单点修改区间求和的线段树题目，但是一看数据量，只有
1
e
5
1e5
1e5我们可以用一种很优雅的暴力去解决这道题,那就区间分块算法，算法的思想就是整个数组分成
n
sqrt{n}
n
连续区域，然后对每个区域进行求和操作，这一步的复杂度为
O
(
n
)
O(n)
O(n),接着在每次询问的时候我们只需把所求区间包括的所有完整区间直接算进去，然后将不包含的零散的区块单独逐个计算，这一步的复杂度为
3
∗
n
sqrt{3*n}
3∗n
，所以总的复杂度为
O
(
q
∗
s
q
r
t
n
)
O(q*sqrt{n})
O(q∗sqrtn),可以知道这个数字是低于要求的。
代码如下:
const int MAX_N = 1e5+10;
const int MAX_T = 1e3;
ll n,m,a[MAX_N],x,l,r,sq;
ll st[MAX_T],ed[MAX_T],bl[MAX_N],k;
ll sum[MAX_T];
void build(){
for(int i=1;i<=sq;i++){
st[i] = n/sq*(i-1)+1;
ed[i] = n/sq*i;
sum[i] = 0;
}//建立分块区间
ed[sq] = n;
for(int i=1;i<=sq;i++){
ll temp = 0;
for(int j=st[i];j<=ed[i];j++){
bl[j] = i;
temp = (temp + a[j]) % 2;//计算每个区间的和，这里因为只需要问奇偶，所以直接每次加的时候取余即可
}
sum[i] = temp;
}
}
ll cal(int l,int r){
ll ans = 0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++){ans += a[i];}//答案中不包含任何一个区块
}else{
for(int i=l;i<=ed[bl[l]];i++){ans += a[i];}//计算答案左边不是完整区块的地方
for(int i=st[bl[r]];i<=r;i++){ans += a[i];}//计算答案右边不是完整区块的地方
for(int i=bl[l]+1;i<=bl[r]-1;i++){ans += sum[i];}//计算完整区块
}
return ans;
}
void update(int l,int k){
a[l] += k;
sum[bl[l]] += k;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i] = a[i] % 2;
}
sq = sqrt(n);
build();
cin>>m;
for(int i=1;i<=m;i++){
cin>>x>>l>>r;
if(x==1){
update(l,r%2);
}else{
cout<<((cal(l,r)%2)==1?"0":"1145141919810")<<"n";
}
}
return 0;
}
K-错误计算
这道题的难点在于理解题目，题目给出目标加法的性质，然后让我们根据规则产生两个数字使其按照目标加法规则可以获得与要检验的值相同的答案。题目给了很清晰的提示那就
0
+
x
0+x
0+x这个
x
x
x无论是任何数，都不会产生目标加法的效果。所以我们这道题的目标就是构造两个数字
0
0
0尽量多的相加，用来规避加法效果带来的影响。
不难分析得出
∗
b
∗
∗
∗
∗
=
∗
0
∗
∗
∗
∗
+
b
0000
(
b
≠
0
)
*b**** = *0**** + b0000(bneq0)
∗b∗∗∗∗=∗0∗∗∗∗+b0000(b=0)
10
∗
∗
∗
∗
∗
=
5
∗
∗
∗
∗
∗
+
400000
10***** = 5***** + 400000
10∗∗∗∗∗=5∗∗∗∗∗+400000
20
x
∗
∗
∗
∗
=
9
a
∗
∗
∗
∗
+
8
b
0000
(
a
+
b
+
1
=
x
+
10
∗
n
)
20x**** = 9a**** + 8b0000(a+b+1=x+10*n)
20x∗∗∗∗=9a∗∗∗∗+8b0000(a+b+1=x+10∗n)
x
0
∗
∗
∗
∗
∗
=
(
x
−
2
)
0
∗
∗
∗
∗
∗
+
1000000
x0*****=(x-2)0*****+1000000
x0∗∗∗∗∗=(x−2)0∗∗∗∗∗+1000000
同时由第一个公式可以得出当
t
t
t小于
100
100
100时我们可以直接输出
a
=
t
,
b
=
0
a = t,b = 0
a=t,b=0。
代码如下：
if(c<100){
cout<=100){
len ++;
temp /= 10;
}
int a = c,b = 1;
for(int i=1;i<=len - 2;i++){b *= 10;}
if(temp % 10 == 0){
if(temp>20){
b *= 10;
cout< 
