2017.7.20

  • 第一题:分数化小数
  • 我没有想到小数循环节会很大,数组要开一百万,但我只开了几百,而且我算循环节是用二维for来寻找,也会炸,最后我得分60。实际上这题是一道高精度除法,就是算循环节有些技巧:“每次将被除数除以除数,当前位的商即为该步操作的商。若余数为0则结束(除得尽);否则,将余数*10,再作为被除数,重复进行上一步操作。对于除不尽的式子(如右上),我们发现出现了相同的被除数40:也就是说,若过程中发现了相同的被除数,则产生了循环。至此,可以设计出具体做法:对于当前在k进行的除法,每次求得余数(记为t时,若为0则已经除尽,输出答案结束即可;若未出现过,用数组记录下它出现的位置;若已经出现过,说明出现了循环。我们已经记录下了它第一次出现的位置(记为b[t]),商的b[t] ~ (k - 1)位为循环节。”
  • 第二题:最长路
  • 我直接用搜索,这几天我打了蛮多深搜,自我感觉基本掌握深搜。正解是与最短路算法相似的“最长路”算法,还是SPFA,主要的不同在于松弛操作:我们用队头点更新其他点的最长路。用dis[]数组表示起点到各点的最长路径,val[i][j]表示从i到j的边权,则最长路算法中松弛操作可以表示为:if(dis[x] + v[x][y] > dis[y]){dis[y] = dis[x] + w[x][y];…}。
  • 第三题:竞赛排名
  • 其实只要耐心读懂题目就可以了,题目不难,但题中出现了一个数学符号西格玛,是求和符号,但题目没有解释。但全部人竟然只有一个100的,其他人都是零分。
  • 第四题:汤姆斯的天堂梦
  • 是一题动规题,类似于数塔问题。我们用f[i][j]表示从初始星球走到第i层j号星球的最小花费,则可以得出状态转移方程:f[i][j] = min(f[i - 1][k] + cost) , 其中k为第i - 1层的星球,且能够到达j星球,cost表示k到j的花费。但我卡在输入上,不知道要怎么用数组来输入,很纠结,还想用三维,后来看了标程,也觉得还可以,没做出来有点可惜。
  • 今天100,这几天都80,90,100。

2017.7.19

  • 第一题:路径统计
  • 我竟然用了搜索,可悲地超时了,只拿了20分。本来还沾沾自喜又打出一个“完美”的搜索。唉,不说了,一排AC的,正解递归。因为它只能向右走或向下走,所以也可以倒过来推出a[i][j]=a[i-1][j]+a[i][j-1],前面先“预处理”一下,很容易可以过。
  • 第二题:01迷宫
  • BFS,记忆化搜索。我竟然不会广搜,只好用深搜来“代替”,结果0分,晚上我打算看一下宽搜,俗话说得好:“不行就暴搜”(虽然我不太确定真的是否有这个“俗话”),搜索的重要性可见一斑。
  • 第三题:两个数差
  • 我看它数据到十万,就想着不能用二维,然后就弄了一大堆,至少样例是过了,最后四十分。没想到它正解是二分:首先将数列排序,再二分枚举两两差距的最小值。每一次二分进行一次check,如果相邻两个数的差小于你所二分的最小值,则不能选择这个数,如果能选出c个数,则在二分的右区间中继续查找,否则在左区间继续。
  • 第四题:估算书的页数
  • 做这题的时候我还剩半个多小时,本来我用数学推了一番,结果发现越推越烦,越推越复杂,最后我直接cout<<"1"(怠惰),竟然还骗到了20分!正解是暴力加搜索,讲题的时候学长说,"嗯,那就是考验代码能力······"我也就233333了。
  • 今天总分才80分,已经是第二次一中倒二了,要加油,来个咸鱼翻身(感觉哪里怪怪的)!

【2017.7.15】Long happy集训Day1题解

备战Noip2017暑假集训(练习赛)

Long happy集训Day1

题库比赛链接:传送门

Task1-瓷砖:

描述

  • 在一个w*h的矩形广场上,每一块1*1的地面都铺设了红色或黑色的瓷砖。小y站在某一块黑色的瓷砖上,他可以从此处出发,移动到上下左右四个相邻的、且是黑色的瓷砖上。
  • 求通过重复上述移动所能经过的黑色瓷砖数。

输入格式

  • 第一行为h、w,2<=w、h<=50,之间有一个空格隔开;
  • 以下为一个w行h列的二维字符矩阵,每个字符为“.”、“#”、“@”,分别表示该位置为黑色瓷砖、红色瓷砖、以及小y的初始位置。

输出格式

  • 输出一行为一个整数,表示小y从初始位置出发可以到达的瓷砖数。

输入

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

输出

59

解题思路

深度优先搜索或广度优先搜索。先找到@(即起点),再从起点向上下左右四个 方向拓展搜索查找是否存在可行路'.'(即黑色瓷砖),如果存在就给计数器tot+1,若该方向是'#'则说明该方向无法行走,直接return结束对该方向的搜索即可.最终输出tot,即可行走的黑色瓷砖的个数.

代码实现


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
char a[51][51];
int tot = 0,n,m;

void pd(int x,int y)
{
    if(a[x][y]=='#') return ;
    if (a[x][y] =='.'){
        a[x][y]='#';
        tot++;
        pd(x-1,y);
        pd(x+1,y);
        pd(x,y-1);
        pd(x,y+1);
    }
}
int main()
{
    freopen("tile.in","r",stdin);
    freopen("tile.out","w",stdout);
   
    cin >> n >> m;
    int x,y;
   
    for (int i = 1;i <= m;i++)
        for (int j = 1;j <= n;j++){
            cin >> a[i][j];
            if (a[i][j] == '@'){
                x = i;
                y = j;
            }
        }
       
    a[x][y] = '.';
    pd(x,y);
   
    cout << tot;
           
}
//搜索

Task2-笔记:

描述

  •         were由于破解skj的情书浪费了太多时间,导致他外语课都没有好好听。为什么是外语课?不是英语课?因为were也不知道这门课学的是什么语言。由于没有好好听课,were的笔记全都记的杂乱无章,出现了好多错误的地方。were的笔记是如此的糟糕,以至于他只记了一句例句,而且自己还不知道是什么意思……然后在老师讲语法的时候,were又零星的记了几个字母对,老师说:这几个字母对是绝对不能相邻的,而且相邻是不关心字母的顺序的,比如老师说,’ab’相邻不能,那么相同的,’ba’也相邻不能。
  •         现在were到家了,打开了上课的笔记,然后他发现笔记有很多自相矛盾的地方:为什么下面的不能相邻的字母对会出现在上面的例句里面呢?纠结再三,were觉得下面的东西相对比较简单,所以记错的概率比较小……他决定在上面的例句里面擦掉几个字母,使得句子变得合法。
  •         但是were还有其他作业要做呢,来不及整理笔记了,就把这个艰巨的任务留给了大家,请问大家,were最少要擦掉几个字母,才能使得上面的例句合法?

输入格式

  • 第一行:一个整数N。
  • 第二行:一个长度为N的字符串,只包含小写字母,代表were记下的例句。
  • 第三行:一个整数M,代表不能相邻的字母对的个数。
  • 接下来M行:每行两个小写字母,代表不能相邻的字母对,因为were太不认真了,所以可能有重复T_T。

输出格式

  • 一个整数:最少要擦除的字母数。

输入

4
noip
2
ip
mo

输出

1

解题思路

由数据点可得:10%的数据中m=0.轻易地,根据题意可得出,当m=0时,不存在任何字母对,即没有需要擦除的字母,那么输出0即可。(再不会也可以输出0坑十分,不坑白不坑,反正正解打死写不出来 (。・`ω´・))

而对于100%的数据,根据题意可得出该问题满足无后效性,可以采用动态规划的写法.在这里我们使用f[i]表示前i个字符所需要擦去的字母的最小个数,通过推导可以得出一个状态转移方程:f[i]=min(f[j]+(i-j)),j是可以与i相邻的字符。但算法复杂度高达O(n^2),显然无法满足100%数据的需求。

这里我们再仔细阅读一下题目,可以知道:与i相邻的j总共只可能是26种字符。所以我们可以维护M(j)表示最后一位保留j字符的最小擦去数,但是我们还要维护对应的j的位置,否则怎么计算(i-j)呢?仍然有两个因素限制结果,如果采取枚举一个计算另一个的做法,效率就没有降低。

如果我们不计算最小擦去数,而反过来计算最大保留数呢?那么f[i]=max(f[j]+1),维护一个M(j),显然就可以解决问题,将复杂度降为O(n)

代码实现


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>  
#include<algorithm>  
using namespace std;  
const int maxn=110000;  
int f[maxn],g[maxn];  
int last[30],forbid[30][30];  
char b[maxn];  
int n,m;  
int main(){  
    freopen("note.in","r",stdin);  
    freopen("note.out","w",stdout);  
    scanf("%d",&n);  
    scanf("%s",b+1);  
    for (int i=1;i<=n;i++)  
        f[i]=b[i]-'a';  
    scanf("%d",&m);  
    while (m--){  
        scanf("%s",b);  
        forbid[b[0]-'a'][b[1]-'a']=forbid[b[1]-'a'][b[0]-'a']=1;  
    }  
    int ans=0;  
    for (int i=1;i<=n;i++){  
        g[i]=1;  
        for (int j=0;j<26;j++)  
            if (!forbid[j][f[i]])  
                g[i]=max(g[i],last[j]+1);  
        last[f[i]]=max(last[f[i]],g[i]);  
        ans=max(ans,g[i]);  
    }  
    printf("%d",n-ans);  
    return 0;  
}  
//来源网上博客,暂时没弄懂这题

Task3-简单题:

描述

  •      有一个n个元素的数组,每个元素初始均为 0。有 m条指令,要么让其中一段连续序列数字反转——0变 1,1变 0(操作 1),要么询问某个元素的值(操作 2)。例如当n=20时,10条指令如下:

输入格式

  • 第一行包含两个整数n,m,表示数组的长度和指令的条数.以下 m行,每行的第一个数 t表示操作的种类。若 t=1,则接下来有两个数 L, R (L ≤ R),表示区间[L, R]的每个数均反转;若 t=2,则接下来只有一个数 I,表示询问的下标。

输出格式

  • 每个操作 2输出一行(非 0即 1),表示每次操作 2的回答。

输入

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

输出

1
0
0
0
1
1

解题思路

对于50%的数据,只需要通过暴力修改,依次对读入的指令进行执行修改即可,算法复杂度为O(NM).

而对于100%的数据,可采用线段树或树状数组(暂时不知道怎么搞)