第一次不用翻譯來打CF，中國人的英文有共鳴啊^_^
不過沒做出C題，很可惜啊.D題看了不敢碰，我對mod10^9+7的題目有陰影...
A題，題意是一堆蘋果，能不能分成兩堆一樣重的，我一開始沒讀清楚題目，拍了個背包（以總和一般作背包容量是否能剛好裝滿），後來看真一點，才發現只有兩種重量的，一種是100，一種是200。之後我就YY了，是不是sum%200==0就輸出YES,否則就是NO。。我還無恥地交了，獲得了一個WA，馬上想明白了，200,200,200明顯即不對啦。之後繼續YY…思路就是計算200的有多少個，記做cnt1,100的有多少個,記做cnt2。
如果cnt1%2==0,判斷cnt1%2==0,能YES，否NO
否則 判斷cnt<2,是，輸出NO，
否則 判斷(cnt-2)%2==0,是輸出YES(就是用兩個100的蘋果充當一個200的)
否則 輸出NO
代碼:
/*************************************************************************
> OS : Linux 3.2.0-60-generic #91-Ubuntu
> Author : yaolong
> Mail : [email protected]
> Created Time: 2014年05月24日 星期六 14:52:20
************************************************************************/
#include
#include
#include
using namespace std;
int main(){
int tmp, n,i,sum=0;
cin>>n;
int cnt1=0,cnt2=0;
for( i=0;i>tmp;
if(tmp==100){
cnt1++;
}else{
cnt2++;
}
}
if(cnt2%2==0){
if(cnt1%2==0){
puts("YES");
}else{
puts("NO");
}
}else{
if(cnt1>=2){
cnt1-=2;
if(cnt1%2==0){
puts("YES");
}else{
puts("NO");
}
}else{
puts("NO");
}
}
return 0;
}
B題，一種強烈的線段樹的味道……不過是兩"棵"線段樹。一棵是沒排序的，一棵是排序的！之前看胡浩大神的線段樹，
官方做法好想是做了預處理，計算a[k]=sum(1~k)，之後計算sum[l,r]時候就是a[r]-a[l-1],顯然我是弄麻煩了～不過算了。。 done is better than perfect.貼我的代碼吧..
/*************************************************************************
> OS : Linux 3.2.0-60-generic #91-Ubuntu
> Author : yaolong
> Mail : [email protected]
> Created Time: 2014年05月24日 星期六 14:52:45
************************************************************************/
#include
#include
#include
#include
using namespace std;
#define N 123456
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
long long sum[2][N<<4],stmp[N];
void PushUP(int type,int rt){
sum[type][rt]=sum[type][rt<<1]+sum[type][rt<<1|1];
}
int cnt=0;
void Build(int rt,int l,int r){
if(l==r){
int tmp;
scanf("%d",&tmp);
sum[0][rt]=stmp[cnt]=tmp;
cnt++;
return ;
}
int m=(l+r)>>1;
Build(lson);
Build(rson);
PushUP(0,rt);
}
long long Query(int type,int L,int R,int rt,int l,int r){
if(L<=l&&r<=R){
return sum[type-1][rt];
}
int m=(l+r)>>1;
long long ans=0;
if(L<=m) ans+=Query(type,L,R,lson);
if(R>m) ans+=Query(type,L,R,rson);
return ans;
}
void Build2(int rt,int l,int r){ //sort了之後的
if(l==r){
sum[1][rt]=stmp[cnt];
cnt++;
return ;
}
int m=(l+r)>>1;
Build2(lson);
Build2(rson);
PushUP(1,rt);
}
int main(){
int n;
scanf("%d",&n);
Build(1,1,n);
sort(stmp,stmp+cnt);
cnt=0;
Build2(1,1,n);
int M,t,lt,rt;
scanf("%d",&M);
while(M--){
scanf("%d%d%d",&t,<,&rt);
cout<
