她认为,满足以下三个条件的三角形是"好三角形".
1.三角形的三个顶点均为格点,即横坐标和纵坐标均为整数.
3.三角形至少有一条边和 轴或 轴平行.
honoka想知道,在平面中选取一个大小为 的矩形格点阵,可以找到多少个不同的"好三角形"?由于答案可能过大,请对取模.
面积为1的格点三角形的数量,对取模的结果.
这道题的意思就是给你一个n*m的矩形,让你在里面找面积为1并且三角形顶点都处于端点的三角形的个数.
底边与x轴平行时,每一条与x轴平行的边有种情况满足底边为2,并且它对应的满足条件的三角形的顶点会有或种如果这条边在中间,那么它可以组成的三角形个数就是,如果是上下底边就是种.这个挺好理解的,因为中间的边顶点可以在上面也可以在下面.所以总数是
底边与x轴平行时,每一条与x轴平行的边有种情况满足底边为1,并且它对应的满足条件的三角形的顶点会有或种,如果这两边是上下底边或者紧挨上下底边的四条边之一,顶点数是,否则就是.所以总数就是
有一天,kotori发现了一个和lovelive相似的游戏:bangdream.令她惊讶的是,这个游戏和lovelive居然是同一个公司出的!
kotori经过一段时间的练习后已经变得非常触,每个音符 的概率perfect,获得分, 概率great,获得分.
已知一首歌有个音符.kotori想知道,不考虑连击加成的话,一首歌得分的期望是多少?
一行个整数,用空格隔开.分别是.
一首歌得分的期望,保留两位小数.
如果全perfect是50000分,全great是40000分.由于它们的概率都是50%,即perfect和great五五开,所以期望是45000分.
umi准备在轴或轴上放置一块挡板来挡住弓箭的轨迹,使得她可以射中的靶子数量不超过个.
她想知道挡板的最短长度是多少?
注:假定弓箭的轨迹是起点为umi坐标,长度无穷大的射线.umi和靶子的体积可以无视.挡板的边缘碰到弓箭轨迹也可视为挡住弓箭.
注2:挡板不能弯折,起始和终点必须在同一坐标轴上.
第一行两个整数代表umi的坐标.
第二行两个正整数和,分别代表靶子的总数量,放置挡板后可射中靶子的最大值.
接下来的行,每行两个整数和 .代表每个靶子的坐标.
保证没有任何一个点在坐标轴上(无论umi还是靶子),保证没有任何两点重合.
若无论如何无法保证可以射中的靶子数量不超过个,则输出.
否则输出挡板的最小长度.如果你和正确答案的误差不超过,则视为答案正确.
umi要保证能射中的靶子不超过0个,即全部挡住.在y轴上选区间[11.5]放置一个长度为0.5的挡板即可.
这道题比赛的时候没看.发现还是挺简单的一道题.
这道题的就是给你一个坐标作为起点,然后会有n个点的坐标.问你能否通过挡住x轴或者y轴上的某一部分使得,从起点的射线所能到达的点的个数不超过个.首先如果在一个象限内是肯定挡不住的,然后我们把每个点(除了与起点同象限的点)和起点的连线与x轴,y轴的交点记录下来.记录完之后排序,然后每隔k个做差统计最小值即可.
有一天,她拿出了个碗,第一个碗装了粒米饭,第二个碗装了粒米饭,以此类推,第个碗装了粒米饭.
然而,爱搞恶作剧的rin把所有的碗的顺序打乱,并拿走了一个碗.hanayo想知道,rin拿走的碗里有多少粒米饭?
输出一个正整数,代表rin拿走的碗里米饭数量.
开始共有5个碗,每个碗内分别有1,2,3,4,5粒米饭.rin拿走的是第四碗.这么简单的样例连tairitsu都看得懂好伐~
然而数论实在太复杂了,她只能研究一些简单的问题.
这天,她在研究正整数因子个数的时候,想到了一个"快速迭代"算法.设为的因子个数,将迭代下去,rin猜想任意正整数最终都会变成.
她希望你帮她验证一下.她会给你一个正整数,让你输出它在迭代过程中,第一次迭代成的迭代次数.
3的因子:1,3.共2个.
这道题直接跟着题目的描述模拟暴力写即可.
有一天,maki拿到了一颗树.所谓树,即没有自环,重边和回路的无向连通图.
这个树有个顶点,条边.每个顶点被染成了白色或者黑色.
maki想知道,取两个不同的点,它们的简单路径上有且仅有一个黑色点的取法有多少?
树上两点简单路径指连接两点的最短路.
第二行是一个仅由字符'B'和'W'组成的字符串.第个字符是B代表第个点是黑色,W代表第个点是白色.
一个正整数,表示只经过一个黑色点的路径数量.
这道题就是给了你一棵树,每个节点都有颜色,黑色或者白色.问你有多少条路径经过黑色节点.
我们可以把白点当成连通块处理,并且把这一块百点中的任意一个百点的值赋为连通块中节点的数量.
然后每遇到一个黑点计算一次.对与黑点相连的点,如果是白色,答案加上这个白色的所处连通块的节点数量.但是有可能存在一个黑点连接好几个白点的情况,这个时候同时也得计算两个端点都是白色节点的路径数,统计一下之前相连的所有白色节点的个数相乘即可.
注意会爆int
这道题也可以用带权并查集,bfs写,但是dfs会简洁一点.
eli拿到了一个仅由小写字母组成的字符串.
她想截取一段连续子串,这个子串包含至少个相同的某个字母.
她想知道,子串的长度最小值是多少?
注:所谓连续子串,指字符串删除头部和尾部的部分字符(也可以不删除)剩下的字符串.例如:对于字符串"arcaea"而言,"arc","rcae"都是其子串.而"car","aa"则不是它的子串.
输入仅有一行,为一个长度为的,仅由小写字母组成的字符串.
如果无论怎么取都无法满足条件,输出.
否则输出一个正整数,为满足条件的子串长度最小值.
选择"beb"子串,长度为3,其中包含相同的两个'b'
这道题的意思是给你一个字符串,让你找一个最短的子串里面包含k个相同字母.
因为保证只有小写字母,所以我们统计每个字母出现的位置,然后每次计算k个相邻字母的距离,直接位置相减即可.并且每次更新最小值.
nozomi看到eli在字符串的"花园"里迷路了,决定也去研究字符串问题.
她想到了这样一个问题:
nozomi有最多次操作的机会.她想在操作之后找出一个尽可能长的连续子串,这个子串上的所有字符都相同.
nozomi想问问聪明的你,这个子串的长度最大值是多少?
注:次操作机会可以不全部用完.
如果想知道连续子串的说明,可以去问问eli,nozomi不想再讲一遍.
输入仅有一行,为一个长度为 的,仅由字符 和 组成的字符串.
如果修改第三个或者第四个位置的字符也可以选出长度为的子串.
这道题跟上一道题很像,这道题的意思是给你一个只有01组成的字符串,你有k次机会可以把0变成1,或者把1变成0.问你可以找到的最大的子串长度,要求子串中的每一个元素都相等,即都是1或者都是0
我们仍然统计0和1的出现位置,现在假如我们考虑把1换成0,那我们只需要看1的位置中,中间有k个1的两个1之间的距离就是此时可以达到的最大子串长度.
注意有一些细节需要处理,具体可以看代码去理解.
I nico和niconiconi
nico平时最喜欢说的口头禅是niconiconi~.
有一天nico在逛著名弹幕网站"niconico"的时候惊异的发现,n站上居然有很多她的鬼畜视频.其中有一个名为"让nico为你洗脑"的视频吸引了她的注意.
她点进去一看,就被洗脑了:"niconicoh0niconico*^vvniconicoG(vniconiconiconiconiconicoG(vniconico......"
弹幕中刚开始有很多"nico1 nico2"等计数菌,但到后面基本上都是"计数菌阵亡"的弹幕了.
她拿到了一个长度为 的字符串,请帮她算出最大计数分数.
这道题的意思就是给你一个字符串,不同的子串可以有不同的分数,问你最多可以得多少分.
就是一个dp,找到状态转移方程就可以了.
μ's在九人齐心协力下,影响力越来越大了!
已知第一天影响力为 ,第二天影响力为 ,从第三天开始,每一天的影响力为前两天影响力的乘积再乘以 的 次方.她们想知道第天影响力是多少?
由于这个数可能非常大,只需要输出其对取模的值就可以了.
1000000007是素数.
题意挺明确的,就是一个递推式,让你求第n项,但是这第n项求起来就很难.