NOIP 模拟赛
Day 1
题目名称LGTB 玩扫雷LGTB 学分块LGTB 打THD
英文代号mine divide thd
时限1 秒1 秒1 秒
输入文件mine.in divide.in thd.in
输出文件mine.out divide.out thd.out
内存限制64Mb 64Mb 64Mb
测试点个数10 10 20
总分100 100 100
时间：2014 年10 月4 日
1
LGTB 玩扫雷
在一个n m 的棋盘上，有位置上有雷(用“*” 表示)，其他位置是空地(用“.” 表示)。
LGTB 想在每个空地上写下它周围8 个方向相邻的格子中有几个雷。
请帮助他输出写了之后的棋盘
输入
输入第一行包含两个整数n, m 代表棋盘大小
接下来n 行，每行m 个字符，代表棋盘
1 n,m 1000
输出
输出包含n 行，每行m 个字符，代表LGTB 写了数字之后的棋盘
样例
样例输入样例输出
3 3
*.*
...
*.*
*2*
242
*2*
2
LGTB 学分块
LGTB 最近在学分块，但是他太菜了，分的块数量太多他就混乱了，所以只能分成3 块
今天他得到了一个数组，他突然也想把它分块，他想知道，把这个数组分成3 块，块可以为空。假设3 块各
自的和中的最大值最小
请输出分完之后3 块中的最大值
输入
输入第一行包含一个整数n 代表数组大小
接下来n 个整数a1, a2, ..., an，代表数组
对于40% 的数据，1 n 10
对于70% 的数据，1 n 103
对于100% 的数据，1 n 105, 1 ai 107
输出
输出包含1 个整数，代表分块完成后3 块中的最大值
样例
样例输入样例输出
10
2 5 1 4 7 3 6 2 5 1
14
3
LGTB 玩THD
LGTB 最近在玩一个类似DOTA 的游戏名叫THD
有一天他在守一座塔，对面的N 个小兵排成一列从近到远站在塔前面
每个小兵有一定的血量hi，杀死后有一定的金钱gi
每一秒，他都可以攻击任意一个活着的小兵，对其造成P 点伤害，如果小兵的血量低于1 点，小兵死亡，他
得到金钱。他也可以不攻击任何小兵。
每一秒LGTB 攻击完毕之后，塔会攻击距离塔最近的一个活着的小兵，对其造成Q 点伤害，如果小兵的血
量低于1 点，小兵死亡，LGTB 不会得到金钱
现在LGTB 想知道，在他选择最优策略时，他能得到多少钱。
输入
输入第一行包含3 个整数P, Q, N
接下来N 行，每行包含2 个整数hi, gi
第i 个小兵和塔之间的距离为i
输入的意义如题面所示
对于20% 的数据，1 N 4
对于50% 的数据，1 N 20
对于100% 的数据，20 P,Q 200, 1 N 100, 1 hi 200, 0 gi 106
输出
输出包含一个整数W，代表LGTB 最多能获得的金钱
样例
样例输入样例输出
20 60 3
80 100
80 200
120 300
500
4
#include<fstream>
using namespace std;
char a[][];
const int d[][]={{-,},{-,},{,},{,},{,},{,-},{,-},{-,-}};
int n;int m;
int main(){
ifstream fin("mine.in");
ofstream fout("mine.out"); fin>>n>>m; for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
fin>>a[i][j]; for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if(a[i][j]=='.'){
a[i][j]='';
for(int k=;k<;k++){
int h=i+d[k][];
int p=j+d[k][];
if(a[h][p]=='*')a[i][j]++;
}
}
} for(int i=;i<=n;i++)
fout<<&a[i][]<<endl;
return ;
}
#include<fstream>
using namespace std;
class divide{
public:
static long long binary_divide(long long * ps,int L,int R){
int lft=L;int rght=R;
long long best=1e12;
while(lft<rght){
int m=(lft+rght)>>;
long long s1=ps[m]-ps[L-];
long long s2=ps[R]-ps[m];
long long t=max(s1,s2);
if(t<best)best=t;
if(s1==s2)break;
if(s1<s2)lft=m+;
else rght=m;
}
return best;
}
};
int n;int a[];
long long ps[];
long long ans=1e12;
int main(){
ifstream fin("divide.in");
ofstream fout("divide.out");
fin>>n; for(int i=;i<=n;i++)
fin>>a[i]; if(n==){
fout<<a[]<<endl;
return ;
} if(n==){
fout<<max(a[],a[])<<endl;
return ;
} if(n==){
fout<<max(a[],max(a[],a[]))<<endl;
return ;
} for(int i=;i<=n;i++)
ps[i]=ps[i-]+a[i]; for(int i=;i<n;i++){
long long s1=ps[i];
long long s2=divide().binary_divide(ps,i+,n);
long long t=max(s1,s2);
if(t<ans)ans=t;
} fout<<ans<<endl;
return ;
}
#include<fstream>
#include<algorithm>
using namespace std;
const int bld=;
const int scr=;
class thd{
public:
static void dynamicProgramming(int (* soldier)[],int (*m)[],int n,int p,int q){
for(int i=;i<=n;i++)
fill(m[i],m[i]+,-1e9);
m[][]=;
for(int i=;i<=n;i++){
int * s=soldier[i];
int t=(s[bld]+q-)/q;
int h=(s[bld]-q*t+q+p-)/p;
for(int j=;j<=;j++){
if(j-t>=)m[i][j]=m[i-][j-t];
if(j+h-t+>=&&(m[i-][j+h-t+]+s[scr])>m[i][j]){
m[i][j]=m[i-][j+h-t+]+s[scr];
}
}
}
}
}; int soldier[][];
int m[][];
int n;int p;int q;int best=-1e9;
int main(){
ifstream fin("thd.in");
ofstream fout("thd.out");
fin>>p>>q>>n;
for(int i=;i<=n;i++)
fin>>soldier[i][bld]>>soldier[i][scr];
thd().dynamicProgramming(soldier,m,n,p,q); for(int i=;i<=;i++)
if(m[n][i]>best)best=m[n][i]; fout<<best<<endl;
return ;
}
explanation
m[i][j]means kill soldier i with j attacktion remain.