Ranting重新回到蓝的一场比赛
Problem A
题意:月亮的大小是按照这样的顺序排列的0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
然后给定一串数，试判断最后一个是增加还是减少
分析：这题还被hack了，对于最后一个不是0，15，且是一个数的情况，直接输出－1，然后只有一个数是0或15，分别对应增加或减少，然后其他的
情况就分别讨论与前一个数的关系就行
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int maxn=;
int a[maxn];
int n;
int main()
{
while(cin>>n)
{
for(int i=;i<=n;i++)
cin>>a[i];
if(a[n]==){
cout<<"UP"<<endl;
continue;
}
if(a[n]==){
cout<<"DOWN"<<endl;
continue;
}
if(n==){
cout<<"-1"<<endl;
continue;
}
if(a[n-]<a[n]){
cout<<"UP"<<endl;
}else{
cout<<"DOWN"<<endl;
}
}
return ;
}
Problem B
题意：全是由r和b组成的字符串，要改成交错的，问至少要操作多少次
分析：这题可以(1)分别统计如果奇数位全为r，偶数位全为b要修改的次数，取二者当中的最大；(2)统计如果奇数位全为b，偶数位全为r要修改的次数，取二者当中的最大；最后再来求(1)和(2)的最小
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int maxn=;
int a[maxn];
int n;
int main()
{
while(cin>>n)
{
for(int i=;i<=n;i++){
char ch;
cin>>ch;
if(ch=='b'){
a[i]=;
}else{
a[i]=;
}
} int cntb=,cntr=;
int ans=<<;
int tot=;
for(int i=;i<=n;i++){
if(i%==){
if(!a[i]){
cntb++;
}
}
}
for(int i=;i<=n;i++){
if(i%==){
if(a[i]){
cntr++;
}
}
}
while(cntr&&cntb) tot++,cntr--,cntb--;
tot+=cntr+cntb;
ans=min(ans,tot); int cntr1=,cntb1=;
int tot1=;
for(int i=;i<=n;i++){
if(i%==){
if(a[i])
cntb1++;
}
}
for(int i=;i<=n;i++){
if(i%==){
if(!a[i])
cntr1++;
}
}
while(cntb1&&cntr1) tot1++,cntr1--,cntb1--;
tot1+=cntr1+cntb1;
ans=min(ans,tot1);
cout<<ans<<endl;
}
return ;
}
Problem C
暂时没做
Problem E
题意：给定一个数组，1表示对区间[l,r]每个数加上x，2表示统计[l,r]中已元素为下标的斐波拉契的和
分析：矩阵快速幂＋线段树 ，这题是很好的模板题，get一份很好的模板
//
// main.cpp
// E
//
// Created by wanghan on 16/9/26.
// Copyright © 2016年 wanghan. All rights reserved.
// #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cctype>
#include<map>
#include<set>
#include<deque>
using namespace std;
const int N=;
const long long MOD=1e9+;
const int maxn=1e5+;
int n,m; //矩阵快速幂
struct Matrix{
int a[][];
Matrix(){
memset(a,,sizeof(a));
}
void init(){
for(int i=;i<N;i++)
for(int j=;j<N;j++)
a[i][j]=(i==j);
}
Matrix operator + (const Matrix &B)const{
Matrix C;
for(int i=;i<N;i++)
for(int j=;j<N;j++)
C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;
return C;
}
Matrix operator * (const Matrix &B)const{
Matrix C;
for(int i=;i<N;i++)
for(int k=;k<N;k++)
for(int j=;j<N;j++)
C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD;
return C;
}
Matrix operator ^ (const int &t)const{
Matrix A=(*this),res;
res.init();
int p=t;
while(p){
if(p&) res=res*A;
A=A*A;
p>>=;
}
return res;
}
}One,Two; //线段树部分
Matrix sum[maxn<<],add[maxn<<];
void PushUp(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void Build(int l,int r,int rt){
add[rt].init();
if(l==r){
sum[rt]=One;
return;
}
int mid=(l+r)/;
Build(l,mid,rt<<);
Build(mid+,r,rt<<|);
PushUp(rt);
} void PushDown(int rt,int l,int r)
{
if(add[rt].a[][]!=){
int mid=(l+r)/;
add[rt<<]=add[rt<<]*add[rt];
sum[rt<<]=(sum[rt<<]*add[rt]);
add[rt<<|]=(add[rt<<|]*add[rt]);
sum[rt<<|]=(sum[rt<<|]*add[rt]);
add[rt].init();
}
}
void Update(int L,int R,Matrix& v, int l,int r,int rt){
if(l>R||r<L)
return;
if(L<=l&&r<=R){
add[rt]=add[rt]*v;
sum[rt]=sum[rt]*v;
return;
}
PushDown(rt, l, r);
int mid=(l+r)/;
Update(L, R, v, l, mid, rt<<);
Update(L, R, v, mid+, r, rt<<|);
PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt){
if(l>R||r<L)
return ;
if(L<=l&&r<=R)
return sum[rt].a[][];
PushDown(rt, l, r);
int mid=(l+r)/;
return (Query(L, R, l, mid, rt<<)
+Query(L, R, mid+, r, rt<<|))%MOD;
} //初始化斐波拉契数列
void Init(){
One.a[][]=,One.a[][]=;
One.a[][]=,One.a[][]=;
Two.a[][]=,Two.a[][]=;
Two.a[][]=,Two.a[][]=;
} int tt[maxn];
int main()
{
Init();
while(scanf("%d%d",&n,&m)!=EOF)
{
Build(, n, );
for(int i=;i<=n;i++)
scanf("%d",&tt[i]);
Matrix tmp;
for(int i=;i<=n;i++){
tmp=Two^(tt[i]-);
Update(i, i, tmp, , n, );
}
for(int i=;i<=m;i++){
int num,x,y,w;
scanf("%d",&num);
if(num==){
scanf("%d%d%d",&x,&y,&w);
tmp=Two^(w);
Update(x, y, tmp, , n, );
}else{
scanf("%d%d",&x,&y);
cout<<Query(x, y, , n, )<<endl;
}
}
}
return ;
}
