头像

木棉觉




离线:2小时前


最近来访(194)
用户头像
九凤白
用户头像
Peter_5
用户头像
ac波比
用户头像
Ysensei
用户头像
灰原乐
用户头像
YF1994
用户头像
好孩子都会写代码
用户头像
Eureka_7
用户头像
tamsles
用户头像
println8888
用户头像
skydegree
用户头像
DPH
用户头像
Pr
用户头像
盼旧η
用户头像
胡圣
用户头像
Z_char
用户头像
jasonho
用户头像
踏碎宴席
用户头像
凌乱之风
用户头像
evecome


木棉觉
7小时前

状态机分析

结点表示状态,边代表转移条件

起始状态在条件C转移得到状态0状态0在条件O转移得到状态1状态1在条件W转移得到状态2,也就是字符串COW

过程如图所示

1884.png


核心观点:当前状态由上个转态转移而来。

从左往右,递推记录,信息要传递
i-1个字母要将起状态信息传递个第i个字母;


状态定义f[i,j]:走到第i个字母,第j个状态的方案数;

  1. f[i,0]代表第i个字母,状态0的方案数
  2. f[i,1]代表第i个字母,状态1的方案数
  3. f[i,2]代表第i个字母,状态2的方案数

转移方程如下:

如果当前第i个字母是C,由之前的分析可知:满足由状态起始状态转移到状态1的条件,状态1的数量可以加1,其余皆不满足转移条件,状态数量不变
1. f[i,0] = f[i-1,0]+1
2. f[i,1] = f[i-1,1]
3. f[i,2] = f[i-1,2]

同理,如果当前第i个字母是C,
1. f[i,0] = f[i-1,0]
2. f[i,1] = f[i-1,1]+f[i-1,0]
3. f[i,2] = f[i-1,2]

同理,如果当前第i个字母是W,
1. f[i,0] = f[i-1,0]
2. f[i,1] = f[i-1,1]
3. f[i,2] = f[i-1,2]+f[i-1,1]


优化

因为从左往右,第i字母状态的更新,只会用到第i-1字母的信息,所以我们可以用3个变量优化数组。


代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
char s[N];

int main()
{

    scanf("%d", &n);
    scanf("%s", s);

    LL a = 0, b = 0, c = 0;

    for(int i = 0; i<n; i++){
        if(s[i] == 'C') a++;
        else if(s[i]=='O') b+=a;
        else c += b;
    }

    printf("%lld\n",c);
    return 0;
}


活动打卡代码 AcWing 1884. COW

木棉觉
8小时前

状态机模型

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
char s[N];

int main()
{

    scanf("%d", &n);
    scanf("%s", s);

    LL a = 0, b = 0, c = 0;

    for(int i = 0; i<n; i++){
        if(s[i] == 'C') a++;
        else if(s[i]=='O') b+=a;
        else c += b;
    }

    printf("%lld\n",c);
    return 0;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

从后往前

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second


const int INF = 1e9+10;
const int N = 1e5+10;
PII a[N];
int main()
{

    int n;
    scanf("%d",&n);
    for(int i = 0 ;i < n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
    }

    //位置已经有序
    int res = 0;
    //单指针
    int last_v = INF;
    for(int i = n-1 ;i >= 0; i--)
    {

        if(last_v >= a[i].y)
        {   res ++;
            last_v = a[i].y;
        }

    }
    cout<<res;
    return 0;
}



题目描述

  • 从上下左右四个面射入光,最多可以反射几次

样例

输入样例:
3 3
/\\
\\\
/\/
输出样例:
3

图的遍历

题目分析

A.png

  1. 可以用8个if-else判断来表示规则
  2. 如果我们将这4个方向编号之后,因为只偏折90度,因此,编号也只相差1,因此可以借助异或操作
  3. 图的遍历我们要考虑边界,边界条件 是 非递归写法中循环结束的条件,也是递归写法中递归结束的条件
  4. 在普通遍历的条件下加入方向

当一个图中点的度小于等于2时,图中的路径由链和环组成

时间复杂度 $O(n*m)$

迭代非递归写法

## 普通遍历

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//定义规则,模拟
const int N =  1010;
char g[N][N];
int n,m;
int d1[4] = {-1,0,1,0}, d2[4] = {0,1,0,-1};
//d1 代表数组的第一维 d2 代表数组的第二维


int dfs(int i,int j,int d){
    //遍历函数
    //按照规则一条道走到出去,没有递归和回溯
    //x,y代表坐标,d代表方向,0 1 2 3 代表上下左右 
    int step = 0;
    while(i>=0&&i<n&&j>=0&&j<m)
    {
        //小坑 \ 代表转移字符 需要两个\\
        if(g[i][j]== '\\') d^=3;
        else d=d^1;
        i += d1[d];
        j += d2[d];
        step ++ ;
    }
    return step;
}
int main()
{
    //定义长宽
    cin>>n>>m;
    for(int i = 0;i < n;i++)
        scanf("%s",g[i]);
    int res = 0;
    for(int i = 0; i < m; i++)
    {
        //从上到下
        //从下到上
        res = max(res,dfs(0,i,2));
        res = max(res,dfs(n-1,i,0));

    }
    for(int i = 0; i < n; i++)
    {
        //从左到右
        //从右到左
        res = max(res,dfs(i,0,1));
        res = max(res,dfs(i,m-1,3));
    }
    cout<<res;
    return 0;
}


递归写法,不需要判断和回溯的DFS

int n, m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y, int d)
{
    if (x < 0 || x >= n || y < 0 || y >= m) return 0;

    if (g[x][y] == '/') d ^= 1;
    else d ^= 3;

    return dfs(x + dx[d], y + dy[d], d) + 1;
}




活动打卡代码 AcWing 1913. 公平摄影

来个10月

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N =100010;


int n;
PII q[N];


int main()
{

    //奶牛的种类有两种,荷斯坦牛和根西岛牛
    //我们发现只要,只要两种奶牛相邻,那么最小距离就是2
    //所以距离为0的情况是只有一种奶牛,只有荷斯坦牛 或 根西岛牛


    //区间的查询
    //前缀和统计数量
    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        int x;
        char str[2];
        scanf("%d%s", &x, str);
        if(*str == 'G' ) q[i] = {x,1};
        else q[i] = {x,-1};

    }


    sort(q+1,q+n+1);

    unordered_map<int, int> hash;

    int res = 0, sum = 0, last;


    //我们最终关心的是是否相等,可以转换为两种数量的差

    for(int i = 1; i <= n; i++){

        //sum 
        //因为是求最大,所以越靠左越好,只记录最左边的位置
        if(!hash.count(sum)) hash[sum] = q[i].x; //坐标


        sum += q[i].y; //代表目前的差值

        if(hash.count(sum)) res = max(res,q[i].x - hash[sum]);
        //如果前面有,那么求差

        if(i==1||q[i].y!=q[i-1].y) last = q[i].x;//只要当前和前一个不一样
        res = max(res,q[i].x-last);
        //全0或者全1的情况



    }

    printf("%d\n",res);
    return 0;


}


活动打卡代码 AcWing 1929. 镜子田地

普通遍历

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//定义规则,模拟
const int N =  1010;
char g[N][N];
int n,m;
int d1[4] = {-1,0,1,0}, d2[4] = {0,1,0,-1};
//d1 代表数组的第一维 d2 代表数组的第二维


int dfs(int i,int j,int d){
    //遍历函数

    //按照规则一条道走到出去,没有递归和回溯

    //x,y代表坐标,d代表方向,0 1 2 3 代表上下左右 
    int step = 0;
    while(i>=0&&i<n&&j>=0&&j<m)
    {
        //规则可以用8个if-else判断
        //因为可逆原则 进行判断
        //相差1的可逆变换



        //小坑 \ 代表转移字符 需要两个\\

        if(g[i][j]== '\\') d^=3;
        else d=d^1;

        i += d1[d];
        j += d2[d];

        step ++ ;

    }


    return step;
}



int main()
{


    //定义长宽
    cin>>n>>m;

    for(int i = 0;i < n;i++)
        scanf("%s",g[i]);


    int res = 0;



    for(int i = 0; i < m; i++)
    {
        //从上到下
        //从下到上
        res = max(res,dfs(0,i,2));
        res = max(res,dfs(n-1,i,0));

    }

    for(int i = 0; i < n; i++)
    {
        //从左到右
        //从右到左
        res = max(res,dfs(i,0,1));
        res = max(res,dfs(i,m-1,3));
    }

    cout<<res;


    return 0;
}


新鲜事 原文

今天没写好就发出去的题解,告诉我用了1h+,而我浑然不觉,甚至感觉只是很短的时间。QAQ。但是我感觉很有意义。写的过程让我思路比写之前更清晰了,倒逼我去思考一些,直觉上正确的事情,而“理所应当”。在表达上,如何让抱着问题的人,更快的找到他想要的东西,自己这么一步一步的说清楚,而尽量避免思路上的跳跃,中途尝试了配了一张图。ps:感谢AcWing上那么多认真的小伙伴,一个很Nice的社区。以极大的热情和友好表达自己和鼓励他人



题目描述

  • 总距离是一千米
  • 初始速度是$V_0=1$
  • 在某些时间,或者每个位置会减速
  • 第$i$次减速,速度变为

    $$V_i=\frac{1}{V_{i-1} + 1}$$

样例

输入样例:

2
T 30
D 10

输出样例:

2970

写法和归并排序很像

$O(n)$

思路分析

首先虽然车子在减速,但是速度是正值,
$\Leftrightarrow$
也就是说,时间越久,距离原点的距离越远
$\Leftrightarrow$
按时间给出的减速信息天然有序,按距离给出的减速信息天然有序
$\Leftrightarrow$
但是,以这两种不同方式方式给出的减速信息实际上是相互间隔的,因此我们要得到这两种方式减速信息的先后关系。
1. $t_i$代表以时间给出的减速信息
2. $d_i$代表以距离起点的距离的减速信息
3. $$V_i=\frac{1}{V_{i-1} + 1}$$
IMG_125A0EDE5220-1.jpeg

也就是说当我们知道先后顺序也就是知道了每段路程其对应的速度
$\Leftrightarrow$

只时候,我们需要从左到右,去不断的确立下一个减速信息。而这个比较的过程,和归并排序非常类似。
按照归并排序的思路,模拟即可
我们需要转换,统一用距离来比较。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;


vector<int> t;
//存储时间
vector<int> d;
//存储距离


//模拟


int main()
{

    int n;
    cin>>n;
    char op[2];
    //减速信息个数
    while (n -- )
    {
        int x;
        scanf("%s%d",op,&x);

        if(*op=='T') t.push_back(x);
        else d.push_back(x);
    }
    d.push_back(1000);
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());

    double current_dis = 0;

    double current_time = 0; //要记录时间
    int v = 1; //代表v的倒数


    //归并排序的两个起点
    int i = 0, j = 0;
    while(i<t.size()||j<d.size())
    {
        //只要有一个没循环结束,就要执行


        if ( j==d.size() || (i<t.size()&&current_dis + (t[i]-current_time)/v < d[j]) ) {
            //时间标准的距离 比 距离的更近
            //边界

            //对当前坐标进行更新
            current_dis += ( t[i]- current_time)/v;
            //对当前时间进行更新
            current_time = t[i];


            //速度减少
            v++;
            i++;
        }
        else{



            //对当前时间进行更新
            current_time+= v*(d[j]-current_dis);
            current_dis = d[j];

            v++;
            j++;
        }

    }

    //cout<<current_time;
    printf("%.0lf\n", current_time);
    return 0;
}




活动打卡代码 AcWing 1934. 贝茜放慢脚步

会,但是不熟练了,写了好久

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;


vector<int> t;
//存储时间
vector<int> d;
//存储距离


//模拟


int main()
{

    int n;
    cin>>n;
    char op[2];
    //减速信息个数
    while (n -- )
    {
        int x;
        scanf("%s%d",op,&x);

        if(*op=='T') t.push_back(x);
        else d.push_back(x);
    }
    d.push_back(1000);
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());

    double current_dis = 0;

    double current_time = 0; //要记录时间
    int v = 1; //代表v的倒数


    //归并排序的两个起点
    int i = 0, j = 0;
    while(i<t.size()||j<d.size())
    {
        //只要有一个没循环结束,就要执行


        if ( j==d.size() || (i<t.size()&&current_dis + (t[i]-current_time)/v < d[j]) ) {
            //时间标准的距离 比 距离的更近
            //边界

            //对当前坐标进行更新
            current_dis += ( t[i]- current_time)/v;
            //对当前时间进行更新
            current_time = t[i];


            //速度减少
            v++;
            i++;
        }
        else{



            //对当前时间进行更新
            current_time+= v*(d[j]-current_dis);
            current_dis = d[j];

            v++;
            j++;
        }

    }

    //cout<<current_time;
    printf("%.0lf\n", current_time);
    return 0;
}



差分与离散化

离散化的使用场景:数的范围很大,但实际上用的较少,数之间的间隔比较大。

Map写法

  • 代码短,容易实现
  • 效率低

Map的使用,简洁直接的实现了映射关系

1 定义map

map<int,int> b;

2 map通过key找value

b[l] += value;
b[r+1] -= value;

3 前缀和恢复具体某一点的值

3.1 朴素版本

  b[i] +=b[i-1];

3.2 离散化版本

  int res = 0, sum =0
  for(auto& [key,value]:b)
  {
      sum += value;
      res = max(res,sum);
  }

手写离散化

  • 代码长,出错概率变大
  • 效率高

思路:

  1. vector存储
  2. 排序
  3. 去重
  4. 映射的部分,由Map变成对有序vector的二分

1 vector存储

vector<int> xs;

2 把区间端点放入

xs.push_back(); 

3 排序

sort(xs.begin(),xs.end());

4 去重

xs.erase(unique(xs.begin(),xs.end()),xs.end());

5 find 实现 映射

映射之后的范围即是vector的大小

int find(int v)
{
    int l = 0, r = xs.size()-1;

    while(l<r)
    {
        int mid = l+r>>1;
        if(xs[mid]>=v) r = mid;
        else l = mid+1;
    }
    return r;
}