题目描述
L实现了一个大整数模板（十进制） 。他的大整数有一个十分厉害的功能：它可以像提取子串那样提取出整数中的一段。
当然，这提取出的一段也是大整数。不过，L发现他的模板中这种操作的效率很低，于是想请你帮他实现这样一个功能。也就是说，在给出一 个长度为 NN 的大整数后，你的程序要能够快速求出大整数某一段的值。由于大整数在加减 中经常会有进位等状况发生，你的程序还需要支持区间修改操作，即将某一段中的数字全部 变成一个给定的数字。
注意：我们从大整数的最低位（最右边）开始标号，依次为第 0, 1, 2,…, N – 10,1,2,…,N−1位。
输入格式
第一行两个整数 N，MN，M，分别为大整数长度和操作数量。
第二行为长度为 NN 的串表示初始的大整数。
接下来 MM 行，每行描述一次操作。格式如下（第一个整数为操作类型） ：
1 l r表示询问[l, r][l,r]这一段的值
2 l r v 表示将[l, r][l,r]这一段中所有数字变为 vv
输出格式
对每个询问操作输出一行一个整数表示对应的答案。由于大整数的值可以很大，输出答案对 10^9 + 7109+7 取模后的结果即可。
样例
数据规模与约定
对于 40%的数据，N, M <= 5000N,M<=5000。
对于另外 30%的数据，所有修改操作中l = rl=r。
对于 100%的数据，1 <= N, M <= 100000，0 <= l <= r <= N – 1, 0 <= v <= 91<=N,M<=100000，0<=l<=r<=N−1,0<=v<=9，大整数中每位数 字均在 0-90−9的范围中。
这道题我打了一个线段树但是爆了RE（segmentation fault）
我终于找道为啥RE了
mid = (t[p].l+t[p].r)>>1;
被我写成了
正解也是线段树（应该没人不会想到线段树吧）这题特征太明显了
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
struct Node{
long long l,r,mul,len,lazy;
}t[400010];
long long n,m,a[100010],mo[100010],ten[100010];
void pushup(long long p){
t[p].mul = (t[p*2].mul*ten[t[p*2+1].len]%mod+t[p*2+1].mul)%mod;
}
void pushnow(long long p,long long v){
t[p].mul = mo[t[p].len]*v%mod;
t[p].lazy = v;
t[p].lazy%=mod;
}
void pushdown(long long p){
if(t[p].lazy!=-1){
pushnow(p*2,t[p].lazy);
pushnow(p*2+1,t[p].lazy);
t[p].lazy = -1;
}
}
void build(long long p,long long l,long long r){
t[p].lazy = -1;
t[p].l = l;
t[p].r = r;
t[p].len = t[p].r-t[p].l+1;
if(l==r){
t[p].mul = a[l];
return;
}
long long mid = (t[p].l+t[p].r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void update(long long p,long long l,long long r,long long v){
if(l<=t[p].l&&t[p].r<=r){
pushnow(p,v);
return;
}
pushdown(p);
long long mid = (t[p].l+t[p].r)>>1;
if(r<=mid){
update(p*2,l,r,v);
}else if(l>mid){
update(p*2+1,l,r,v);
}else{
update(p*2,l,mid,v);
update(p*2+1,mid+1,r,v);
}
pushup(p);
}
long long query(long long p,long long l,long long r){
if(l<=t[p].l&&t[p].r<=r)
return t[p].mul%mod;
pushdown(p);
long long mid = (t[p].l+t[p].r)>>1;
if(r<=mid)return query(p*2,l,r);
if(l>mid)return query(p*2+1,l,r);
int ans1 = query(p*2,l,mid),ans2 = query(p*2+1,mid+1,r);
return (ans1*ten[min(t[p].r,r)-mid]%mod+ans2%mod)%mod;
}
int main(){
freopen("bigint.in","r",stdin);
freopen("bigint.out","w",stdout);
scanf("%lld%lld",&n,&m);
mo[0] = 0;
ten[0] = 1;
for(int i = 1;i<=n;++i){
mo[i] = (mo[i-1]<<3)%mod+(mo[i-1]<<1)%mod+1;
mo[i]%=mod;
ten[i] = (ten[i-1]<<3)%mod+(ten[i-1]<<1)%mod;
ten[i]%=mod;
char ch = getchar();
while(ch<'0'||ch>'9') ch = getchar();
a[i] = ch-'0';
}
build(1,1,n);
while(m--){
long long b,x,y,l,r;
scanf("%lld%lld%lld",&b,&x,&y);
l = n-y,r = n-x;
if(b==1) printf("%lld\n",query(1,l,r));
else{
long long z;
scanf("%lld",&z);
update(1,l,r,z);
}
}
return 0;
}
题目描述
小 C 有一个数组 A，其中第ii个数为 A_iAi，不过小 C 不太喜欢他的数组。 小 C 定义了可以估计一个数组的美丽度的函数 T：
T(A)=\text {max}_{i=2}^n|A_i-A_{i-1}|T(A)=maxi=2n∣Ai−Ai−1∣
小 C 认为 T(A)T(A)的值如果越小，那么 A 数组的美丽度就越大。小 C 认为他现在的数组不太美丽，所以他想要修改一些位置，使得 A 数组的美丽度尽量大。
小 C 会告诉你，他想要修改 k 个位置，每次修改可以把原来位置上的 A_iAi 修改为任意值。他想要你告诉他，当 A 数组的美丽度最大的时候，T(A)T(A) 的值等于多少。
输入格式
第一行两个数 n, k。
接下来一行 n 个数，第 i 个数表示A_iAi。
输出格式
输出一个数，当 A 数组的美丽度最大时 T(A) 的值。
样例
更多样例：
array2.in, array2.out
array3.in, array3.out
数据规模与约定
对于 30 % 的数据，n ≤ 100，|Ai| ≤ 10n≤100，∣Ai∣≤10。
对于 70 % 的数据，n ≤ 300，|Ai| ≤ 100n≤300，∣Ai∣≤100。
对于 100 % 的数据，n ≤ 2000，|Ai| ≤ 10^9n≤2000，∣Ai∣≤109。
woc，遇到了我做过的题。现在不会了
不过因为害怕老师抽我讲尊严，我没有抄我的源代码
光明正大的爆零
思路还是二分答案，只不过加了个DP，二分T(A)的值，f数组为第i个元素之后的最小修改次数，n-i-1为i后的部分最大修改次数（减一的原因是第一个端点可视为基准，后面的值依据它来改动），初始化f之后的for循环就是计算i+1及以后的元素的最少修改次数，abs那一句是用来与最大差值m*(j-i)作比较，若小于最大差值，则可以更新当前状态，若大于最大差值，需要修改，所以不能更新当前状态，f[j]+j-i-1是算的当前位置的状态加上后面所需的最大次数的值，f[i]+i则代表i元素之前所需的最大次数与元素之后所需的最小次数的和，若这个小于k则i元素之前所需最小次数与i元素之后所需最小次数的和，即整个数列所需最小次数一定小于k
#include<bits/stdc++.h>
using namespace std;
int n,k,a[2010],f[2010];
bool check(long long m){
for(int i = n;i>=1;i--){
f[i] = n-i-1;
for(int j = i+1;j<=n;j++)
if(abs(a[j]-a[i])<=m*(long long)(j-i))
f[i] = min(f[i],f[j]+j-i-1);
if(f[i]+i<=k) return true;
}
return false;
}
int main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
long long l = 0,r = 2e9,ans = r;
while(l<=r){
long long mid = (l+r)>>1;
if(check(mid)) r = mid-1,ans = mid;
else l = mid+1;
}
printf("%lld",ans);
return 0;
}
综上所述，我是蒟蒻
还望大佬指点
恳请大佬顺带指点一下博客如何个性化
2022-10-26 16:28:45
