10.15分治专题解题报告

前言：

向总：每天做两道题就可以了

所以

1. 栅栏涂漆

这道题看起来十分似曾相识。。

非常像NOIP2013提高组复赛Day2第一题

然而那道题我并不是用分治做的

// <block.cpp> – 09/08/15 19:09:18
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int a[100001];
int main()
{
freopen(“block.in”,”r”,stdin);
freopen(“block.out”,”w”,stdout);
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>a[i-1])ans+=a[i]-a[i-1];
}
cout<<ans;
return 0;
}

核心的就两行代码

然而这道题就得用分治做了

首先 如果只有一根栅栏的话 只要高度不是0都只要刷一次

对于一般情况

先求出当前情况下最矮的栅栏

假设先横着刷到这个栅栏

然后再递归求这个栅栏两边的 加起来得到当前状态 底下横着刷的最优result

最后返回result和这排栅栏的根数（全竖着刷）中较小的

就可以了

代码：

// <color.cpp> – 10/15/15 08:14:35
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch=getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
lol getlol(){
lol res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch=getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
lol n,h[5050],ans;
lol brush(lol l, lol r)
{
if(l==r)return(h[l]>0);
lol i,k;
lol result=0;
k=l;
for(i=l+1;i<=r;i++)if(h[i]<h[k])k=i;
result+=h[k];
for(i=l;i<=r;i++)h[i]-=result;
if(k-1>=l)result+=brush(l,k-1);
if(k+1<=r)result+=brush(k+1,r);
if(r-l+1<result)result=r-l+1;
return result;
}
int main()
{
freopen(“color.in”,”r”,stdin);
freopen(“color.out”,”w”,stdout);
lol i;
n=getlol();
for(i=1;i<=n;i++)h[i]=getlol();
ans=brush(1,n);
cout<<ans;
return 0;
}

3.字符加密

不要问我问什么没有2 开头讲了

题目前面一大段话都是扯淡

看到下面就明白了

就是输入一个S

把S视为S中最大数字+1 进制数 然后计算K^S MOD M

K^S MOD M好算 直接边快速幂边mod

然而怎么把S转成十进制还要存得下

最终用了个费马小定理。。还要要求M是质数。。复杂度还是很高。。得了10分

然而机智的YJP居然想到了正解：p进制快速幂

其实也不难 就是没想到

代码：（后来A了 但是删了 就把p进制快速幂写一下）（pow是普通快速幂）

long long qpow(long long a,char* b,int p){
long long res=1;
int l=strlen(*b);
for(int i=0;i<l;i++){
res*=pow(x,(b[l-1-i]转成数字))%m;x=pow(x,p)%m;
}
return res;
}