- it技术
- [差分前缀和] 菜题の刷
贴码码，刷题题
U53525 前缀和（例题）
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=1e5+5;
int n
,a
[N
];
int main(){
n
=in
;
for(int i
=1;i
<=n
;++i
) a
[i
]=a
[i
-1]+in
;
for(int i
=1;i
<=n
;++i
) cout
<<a
[i
]<<" ";
return 0;
}
前缀和的逆
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=1e5+5;
int n
,a
[N
];
int main(){
n
=in
;
for(int i
=1;i
<=n
;++i
) a
[i
]=in
;
for(int i
=n
;i
>=1;--i
) a
[i
]=a
[i
]-a
[i
-1];
for(int i
=1;i
<=n
;++i
) cout
<<a
[i
]<<" ";
return 0;
}
从上面两道题可以看出，前缀和与差分互为逆运算
最大の和
注意区间
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=1e5+5;
int n
,a
[N
],k
,ans
;
int main(){
n
=in
,k
=in
;
for(int i
=1;i
<=n
;++i
) a
[i
]=a
[i
-1]+in
;
for(int i
=1;i
<=n
-k
;++i
){
ans
=max(ans
,a
[i
+k
]-a
[i
]);
}
cout
<<ans
<<endl
;
return 0;
}
Subsequences Summing to Sev
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=1e5+5;
int n
,a
[N
],ans
;
int main(){
n
=in
;
for(int i
=1;i
<=n
;++i
) a
[i
]=(a
[i
-1]+in
)%7;
for(int k
=0;k
<=6;++k
){
int l
,r
;
for(l
=1;l
<=n
;++l
) if(a
[l
]==k
) break;
for(r
=n
;r
>=1;--r
) if(a
[r
]==k
) break;
ans
=max(ans
,r
-l
);
}
printf("%d\n",ans
>0?ans
:0);
}
这么几分钟刷完这么多题还是一件很有成就感的事情
