2017安徽省青少年信息学奥林匹克(AHOI)初中组
2017AHOI初中-T1- 基站覆盖 [cover] P3717
题目描述
由 N×N 个格子构成的网格区域，在该区域中均匀排列成横平竖直的线条分布着N×N个格点。这些格点之间间隔均为1单位长度。例如，在5×5的示例中可以看出具体的分布情况：
我们通常标注左下角的格点为(1, 1)，接着在左侧边界上依次标出右侧各点为(2, 1)、左侧标出上方各点为(1, 2)，按照这种模式类推。
为了部署移动通信服务设施，在每个网格单元中安装了专门的探测装置。进一步地，在包含M个单元的位置上会布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上布置基站在这些位置上的基础上进行测试
输入格式
第一行三个整数 N、M、R；
以下 M 行，每行两个整数 x、y，表示一个基站的坐标(x, y)。
输出格式
输出一行一个整数，表示能检测到信号的检测器个数。
输入输出样例
输入样例1：
输出样例1：
说明
【样例说明】
在5×5网格区域内位于格点(3,3)和格点(4,2)处有两个基站，在工作半径均为1的情况下
【数据范围】
对于 40%的数据：N, M ≤ 100，R = 0（当 R=0 时，基站所在的格点能检测到信号）；
对于 100%的数据：N, M ≤ 100，0 ≤ R ≤ 100，1 ≤ x, y ≤ N，数据不保证基站不重叠。
耗时限制1000ms 内存限制128MB
解析
考点：枚举
思路：
解析如下：首先需要输入三个参数n、m、r来表示矩阵的行数与列数组织以及节点间的平均连接权重。随后采用三重循环结构进行计算，在第一层循环中读取m个基站的位置坐标，在第二层与第三层循环中遍历全图寻找符合条件的检测点位置。
该算法的时间复杂度可表示为O(n³)，其中n和m的取值范围均为[1, 100]。计算量与m乘以n平方呈正比，在这种情况下算法的时间复杂度达到O(4×1e5)，即约4×十的五次方单位运算（运算次数约为4×十的五次方），远低于单处理器每秒执行十亿次运算的能力水平（即单处理器每秒可完成约十亿次运算）。第一层循环负责读取并存储m个基站的位置信息；第二层和第三层循环则依次遍历整个网络拓扑图；最后筛选出所有位于当前基站覆盖范围内的检测器。
注：这道题需用到初中数学知识勾股定理（a²+b²=c²）
参考代码
#include<iostream>//不推荐使用万能头，会和某些变量名冲突 例如map数组
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//申请命名空间
int n,m,r,ans=0;//对应着n*n大小的方阵，m个探测器，r的扫描半径，最终的答案
int x,y;//输入探测器的坐标
double dis;//点到探测器的距离
bool map[1001][1001]={0};//初始化为0，1表示可以被扫到的点
int main()
{
scanf("%d%d%d",&n,&m,&r);//输入
for(int k=1;k<=m;k++) {
scanf("%d%d",&x,&y);//输入点的坐标
map[x][y]=1;//探测仪肯定可以被扫到
for(int i=1;i<=n;i++) {//开始枚举各个点
for(int j=1;j<=n;j++) {
dis=sqrt((x-i)*(x-i)+(y-j)*(y-j));//两点之间的距离公式！！初中就学到了，应该都会吧。
if(dis<=r)//到这里的距离小于扫射的距离
map[i][j]=1;//那么就标记
}
}
}
for(int i=1;i<=n;i++) {//看每一个点
for(int j=1;j<=n;j++) {
if(map[i][j]==1)//可以被扫到
ans++;//计数器加加
}
}
printf("%d",ans);//完美输出答案
return 0;//完美の结束
}2017AHOI初中-T2- 错落有致 [alter] P3718
题目描述
在一个狭长的空间里布置了N盏吊灯，并将它们整齐地排列在了一起。淘气的小男生小可在一天中发现了每盏灯对应的开关。“为什么这些灯具的状态显得如此单调呢？”他自言自语道。经过一番思考后发现，问题出在这些灯具开关的状态不够多样化，在开启过程中经常会出现一大片同时亮着或者同时熄灭的情况。不过由于时间紧迫性问题，在开启所有灯具时最多只能拨动不超过K次开关（每次拨动后会切换一盏灯具的状态：开变关或关变开）。随后他将灯具中出现的最大连续明亮区域或最大连续黑暗区域的数量定义为该组灯具的整体均匀程度，并希望在最多拨动K次开关的情况下将其均匀程度降到最低水平
输入格式
第一行两个整数 N、K；
下行一个长度为N的、由字符N和F构成的字符串依次用来表示该房间的照明状态
第i个字符以'N'代表第i盏灯亮，并以'F'代表第i盏灯灭。这一规定属于输入格式的信息描述。
输出格式
一行一个整数，表示最小化的不优美度。
输入输出样例
输入样例1：
输出样例1：
说明
对于 30%的数据：1 ≤ K ≤ N ≤ 20；
对于 50%的数据：1 ≤ K ≤ N ≤ 300；
对于额外 15%的数据：1 ≤ N ≤ 100000，字符串为全 N 或全 F；
对于 100%的数据：1 ≤ K ≤ N ≤ 100000。
耗时限制1000ms 内存限制128MB
解析:
考点：二分答案
参考代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,p;
int l,r;
bool a[100005];
//从头到尾循环一下，发现相同字母连续个数超过mid，更改当前位置上的字符，发现更改次数超过K，返回假，否则返回真
bool check(int x){
int sum=0;
for(int l=1,i=1,res=0;i<=n;i++){
if(a[i]==a[l]) res++;
else l=i,res=1;
if(res>x) sum++,res=0,l=i+1;
}
return sum<=k;
}
int main(){
scanf("%d %d\n",&n,&k);
for(int i=1;i<=n;i++) {
char c=getchar();
a[i]=(c=='N');
if(i%2&&a[i]) p++;
else if(!(i%2)&&!a[i]) p++;
}
if(p<=k||n-p<=k){
puts("1");
return 0;
}
l=2,r=n;
while(l<r) {
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
return 0;
}2017AHOI初中-T3- 正则表达 [rexp] P3719
题目描述
该方法对于解决各种字符串匹配问题非常有效。该方法通过建立一套符号体系可以描述所需查找的字符串的基本特征。例如，“a|aa”可以匹配 a 或 aa，“(a|b)c”可以匹配 ac 或 bc。由于完整的正则表达式过于复杂 在本研究中我们仅关注由括号 并集运算符以及字母 a 组成的形式
运算遵循下列法则：
(1) 有括号时，我们总是先算括号内的部分；
在两个字符串（或由括号定义的子串）之间不带符号时
该符号用于表示两个可选配对之间的组合关系；当在同一层级中存在多个|符号时，则相当于从这些被分割后的独立字符串中选择一个。
例如，在正则表达式中](aaa)aa|aa|(a(aa)a)与(aaaaa)|(aa)|aaaa等价的形式都具有相同的匹配能力。这些模式都能识别长度为2、4或5的所有连续a字符序列。请编写程序来计算这种简化正则表达式能够最多匹配多长连续的a字符序列。
输入格式
每行单独的一个有效的简化正则表达式（被确保‘|’两端和括号内运算结果均为非空字符串）
输出格式
一行一个整数，表示能匹配的最长全 a 字符串长度。
输入输出样例
输入样例1：
输出样例1：
输入样例2：
输出样例2：
说明
对于 20%的数据：表达式长度为不超过 100 的正整数，且不存在括号；
对于 40%的数据：表达式长度为不超过 100 的正整数；
对于 70%的数据：表达式长度为不超过 2000 的正整数；
对于 100%的数据：表达式长度为不超过 100000 的正整数。
耗时限制1000ms 内存限制128MB
解析
考点：递归
参考代码
#include<iostream>
using namespace std;
int sum(int num){//递归函数
char get='a';
while(cin>>get){
if(get=='a') num++;//相应的a的个数。
else if(get=='(') num=num+sum(0);//这里是括号。
else if(get==')') return num;//这里是括号的结束。
else if(get=='|') return max(num,sum(0));//max根据题面，是数目。
}
return num;//允许结束！
}
int main(){
cout<<sum(0);
return 0;
}2017AHOI初中-T4- 导航 [guide] P3720
题目描述
过去，在人们驾车探索新地点的过程中
输入格式
第一行两个数值N、M分别代表交叉口数量以及单向道路的数量；随后输入的M行数据中每一行都包括四个数值u、v以及两个权重值w₁、w₂。其中u和v为起点和终点节点编号；w₁和w₂分别代表在小兰使用其App平台以及小红使用其App平台时对这条道路估算的成本权重值。每条单向道路都以这样的方式被记录下来。
输出格式
输出一行一个整数，表示小可可整个行程中，最少听到多少声报错。
输入输出样例
输入样例1：
输出样例1：
说明
小可可如果选择路线 1→2→4，则小红的 APP 分别在 1→2 和 2→4 时各报错一次；
小可可若采用路径1-2-3-4，则其应用程序会在步骤1至2间出现一次错误；随后，在步骤2至3间会出现第二次错误；与此同时，在路径选择上作出相应调整的情况下（即采取路径1至3至4），则会发现其应用程序会在第一步骤即出现问题。
上述三种路线中，小可可最少听到的是一次报错声。
【数据范围】
对于 20%数据：N ≤ 10，M ≤ 50；
对于 40%的数据：N ≤ 100，M ≤ 10000；
对于额外 20%的数据：N ≤ 10000，M ≤ 50000，任意 w 1 = w 2 ；
对于 80%的数据：N ≤ 10000，M ≤ 50000；
给定数据集中参数满足N ≤ 5, V ≤ 1, M ≤ 1, W₁, W₂ ∈ [1, 1]时的情况：其中u、v分别表示节点编号且取值范围为[1, N]；权重w₁、w₂满足[1, W_max]；图中任意两点之间可能有多条边；不存在自环结构；并且从起点到终点必存在通路
耗时限制1000ms 内存限制128MB
解析：
看到此题就能想到使用最短路径算法。考虑到数据量极大，并不建议采用传统的Dijkstra算法。因此我们选择使用SPFA算法来解决这个问题，并采用链式前向星进行存储结构设计。
为使答案达到最低水平的抱怨值, 我们需要明确这两个GPS各自指向的具体路线, 即我们需要确定这两条路线之间的最短路径
我们计算了两个GPS指向的'最短路径'之后，在此基础上重新绘制路线图，并再次计算从这个点到另一个点的错误次数（即抱怨值），以确定是否经过了指定的道路。为了判断这一点，则需要查看由已知路径确定的f[y]与f[x]+z的关系（其中x为此点,y为通过这条边到达的点,z为这条边的权值）。则如果f[y]不等于f[x]加上z，则说明这条路没有被使用。
4.spfa中，dis[i]原本代表从起点1到i点的最短距离。此题以1为起点。然而，在统计到达n点是否经过某个路段时，则需要反向计算路径，并相应地，在存储过程中也需要采取反向策略。
参考代码
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF=1000000;
struct edge{
int to;
int w[2];
};
vector<edge> G[500010];
int d1[500010];
int d2[500010];
int n,m;
bool used[500010];
void spfa(int d[],int mode){
for (int i=1;i<=n;i++){
d[i]=INF;
used[i]=false;
}
queue<int> q;
d[n]=0;
q.push(n);
used[n]=true;
while (!q.empty()){
int u=q.front();q.pop();
used[u]=false;
for (int i=0;i<G[u].size();i++){
edge e=G[u][i];
int v=e.to;
int w=e.w[mode];
if (d[v]>d[u]+w){
d[v]=d[u]+w;
if (!used[v]){
q.push(v);
used[v]=true;
}
}
}
}
}
int main(){
cin>>n>>m;
for (int i=1;i<=m;i++){
int u,v,w1,w2;
cin>>u>>v>>w1>>w2;
edge e;
e.to=u;
e.w[0]=w1;
e.w[1]=w2;
G[v].push_back(e);
}
spfa(d1,0);
spfa(d2,1);
for (int i=1;i<=n;i++){
for (int j=0;j<G[i].size();j++){
edge e=G[i][j];
int u=i,v=e.to,w1=e.w[0],w2=e.w[1];
int cnt=0;
if (d1[v]!=d1[u]+w1) cnt++;
if (d2[v]!=d2[u]+w2) cnt++;
G[i][j].w[0]=cnt;
}
}
spfa(d1,0);
cout<<d1[1];
return 0;
}