题解 CF1080B
莫名就卡到了最优解第一,但是代码又长又臭,很明显我代码实现能力太弱了。。。
直接开始讲,我都不知道怎么讲
分情况讨论
-
如果 \(l=r\):
我们只需要考虑这个位置的奇偶即可,奇数是 \(-l\) ,偶数是 \(l\),如图
-
如果不是的话,我们就判断两端点的奇偶性
如果我们想用简便的方法去计算这段区间的和,我们就会发现,相邻的一奇一偶(奇数在偶数的左边)会相互抵消为
1
所以我们可以考虑去让这段区间变为这样的一个形式,如果右端点是奇数就先把右端点的贡献算上,然后再 \(r-1\) ,如果左端点是偶数,我们就需要吧 \(l-1\) ,然后把当前
l
的贡献从最终结果中去除掉,这样才能保证最终结果正确,中间区间内相邻两个正好抵消为1
,直接统计
如图一个过程
// #Tyrue#
#include<map>
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=1e8;
int T,n;
int main(){
T=read();
while(T--){
int ans=0;
int x=read(),y=read();
if(x==y){
if(x&1){
ans=-x;
}else{
ans=x;
}
printf("%d\n",ans);
continue ;
}
if(y%2){
ans-=y;
y--;
}
if(!(x%2)){
x--;
ans+=x;
}
ans+=(y-x+1)>>1;
printf("%d\n",ans);
}
return 0;
}
标签:CF1080B,ch,题解,偶数,端点,include
From: https://www.cnblogs.com/Tyrue-blog/p/16937373.html