首页 > 其他分享 >2023.8.6 练习

2023.8.6 练习

时间:2023-08-06 21:55:27浏览次数:35  
标签:表示 方案 sum 练习 矩阵 考虑 2023.8

ARC058D

首先有一个 \(n\times m\) 的矩阵,从左上走到右下的方案数是 \(C_{n+m-2}^{n-1}\).
考虑把原图切分成两个矩阵。(左上和右整边)
计算出走到左上角的矩阵边上每个点的方案数,再乘上这个点走到右下的方案数,求和即可。

ARC058E

发现题目条件中有“存在”字眼,非常容易重复计数,所以我们考虑反面。
总方案数是 \(10^n\),再减去完全不满足条件的即为答案。

看见 \(x+y+z\le 17\) 考虑状压。
设 \(f(n,S)\) 表示已经考虑到 \(n\) 位,状态为 \(S\) 的方案数、
我们如何表示这个 \(S\) 呢?
我们首先想到可以把每个位置的数都在 \(s\) 中表示出来,但可惜数字可以重复,就不能表示。
所以我们可以把 \(S\) 表示为以 \(i\) 结束每个区间的和,可以用二进制表示。
这样如何这个和中同时出现了 \(z,y+z,x+y+z\),就要排除掉。

那么如何转移呢?假设现在加入第 \(i\) 位的数为 \(d\),\(i-1\) 的状态为 \(s\).
新的状态是把 \(s\) 二进制下左移 \(d\) 位,再把第 \(d\) 位设成 \(1\) 即可。

ARC059E

看到很多求和被震慑住了。

考虑 dp,设 \(f_{i,j}\) 表示前 \(i\) 位总共发了 \(j\) 颗糖果。
\(f_{i,j}=\sum f_{i-1,k}\cdot \sum_{t=A_i}^{B_i}(t^{k-j}\).

标签:表示,方案,sum,练习,矩阵,考虑,2023.8
From: https://www.cnblogs.com/Simon-Gao/p/17610134.html

相关文章

  • 2023.8.3
    A01矩阵,每次可以对一个子矩阵取反,问最少多少次操作后,存在一条只向下或右走,只经过0,从左上角到右下角的路径。\(n,m\le1000\).这个dp还是非常trival的。#include<bits/stdc++.h>#defineN1010#defineinf(1<<25)usingnamespacestd;intread(){ intx=0,w=1;char......
  • 2023.8.6 周日:数据类型
     1#对于int数据类型2ageint;34#对于double数据类型,并且保留n位小数5scoredouble(总长度=整数位数+小数位数,小数点后要保留的位数);67#对于生日等日期类8birthdaydata;910#对于字符类型11namevarchar(字符最大长度); ......
  • 2023.8.6
    日常做题1.P4198楼房重建非常离谱的线段树题,反正我当时看了标签是想不出来怎么线段树的。题意就是求斜率单调上升的序列长度(以下简称该序列为答案序列)。好,我们尽力地去想一下线段树怎么做。同样记左区间、右区间节点为\(p1,p2\),我们考虑维护区间的答案长度,记为\(len\)。......
  • 练习回—绑定网卡
    BOND将多块网卡绑定同一IP地址对外提供服务。bond聚合链路模式共7种模式:0-6Mode实现“bond”两种方式:手写,改配置文件;命令.手动配置 ​BONDINGOPTS="mode=1miimon=100failover_mac=1"#miimon指定链路监测时间间隔。如果miimon=100,那么系统每100ms监测一次链路连接......
  • 练习用markdown编写文档
    流水记录之20230806早在十多年前,我就曾用HTML编写我的日记,坚持一段时间后,因其复杂而放弃了。多年后,通过wordpress认识了markdown,但因日常基本上用不到,所以也就一直搁置。如今,重拾markdown,希望能够在不断的练习中快速上手。......
  • 前端学习笔记202305学习笔记第三十三天-js-练习题1
     ......
  • 前端学习笔记202305学习笔记第三十三天-js-执行上下文练习题2
      ......
  • 前端学习笔记202305学习笔记第三十三天-js-执行上下文练习题4
     ......
  • 【ACM专项练习#03】打印图形、栈的合法性、链表操作、dp实例
    运营商活动题目描述小明每天的话费是1元,运营商做活动,手机每充值K元就可以获赠1元,一开始小明充值M元,问最多可以用多少天?注意赠送的话费也可以参与到奖励规则中输入输入包括多个测试实例。每个测试实例包括2个整数M,K(2<=k<=M<=1000)。M=0,K=0代表输入结束。输出对于每个测试实......
  • 【ACM专项练习#02】输入整行字符串、输入值到vector、取输入整数的每一位
    输入整行字符串平均绩点题目描述每门课的成绩分为A、B、C、D、F五个等级,为了计算平均绩点,规定A、B、C、D、F分别代表4分、3分、2分、1分、0分。输入有多组测试样例。每组输入数据占一行,由一个或多个大写字母组成,字母之间由空格分隔。输出每组输出结果占一行。如果输入的大......