前言：
向总：每天做两道题就可以了
所以
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;
}