Posts

题目描述 在高为 $H$ 的天花板上有 $n$ 个小球，体积不计，位置分别为 $0,1,2,\cdots,n-1$。在地面上有一个小车（长为 $L$，高为 $K$，距原点距离为 $S_1$）。已知小球下落距离计算公式为 $d=0.5 \times g \times (t^2)$，其中 $g=10$，$t$ 为下落时间。地面上的小车以速度 $V$ 前进。 如下图： 小车与所有小球同时开始运动，当小球距小车的距离 $\le 0.0001$ (感谢 Silver_N 修正) 时，即认为小球被小车接受（小球落到地面后不能被接受）。 请你计算出小车能接受到多少个小球。 输入格式 $H,S_1,V,L,K,n$（$1 \le H,S_1,V,L,K,n \le 100000$） 输出格式 小车能接受到的小球个数。 样例 #1 样例输入 #1 5.0 9.0 5.0 2.5 1.8 5 样例输出 #1 1 思路 引用洛谷水友的话，就是希望你永远不要知道我是如何在信息学比赛上推物理公式的 不过不管是物理公式难度或是程序实现难度在提高组中都是签到题 这题的g给的很仁慈，因此可以直接得出车头t_min和车尾t_max时间和h、k之间的关系 通过对二者能够接住的最大值的位置和最小值位置相减，就能轻松得出个数 需要注意，最大距离不能大于总长度s1 代码 #include<stdio.h> #include<cmath> using namespace std; int n; double h,s1,v,l,k; int main() { scanf("%lf %lf %lf %lf %lf %d",&h,&s1,&v,&l,&k,&n); double t_max=sqrt(h/5); double t_min=sqrt((h-k)/5); int i_b=int(s1-t_min*v+l),i_e=int(s1-t_max*v); i_b=min(i_b,n);i_e=max(i_e,0); printf("%d",i_b-i_e); }

第9题 描述 有一个整数数列，第一项是a，以后的每一项都是前一项乘以b再加c的结果，求数列第m项的后两位数字（即十位数和个位数） 输入 一个正整数n，表示有n组测试案例。 每组案例由4个正整数a、b、c、m组成（a、b、c均小于1e+7，m小于1e+9） 输出 针对每组案例，输出一个整数，表示数列第m项的后两位数字。 每组案例输出完都要换行。 样例输入 1 12 3 5 3 样例输出 28 思路 用dzt都会写的“朴实无华”方法可以通过大概40~50%的数据，但暴力方法要拿到AC必定会遇到黄色超时的阻挠 既然一般的方法又不行，那我们就再看看二般的方法 回到计算机底层对数字处理的方式，我们可以知道，当我们输入一个10进制数字，计算机虽然执行指令时还是需要执行2进制指令，具体的次数则由我们对循环的定义进行 举个例子，当我们定义一个for循环时，如果我们让他循环10次，那么计算机也就是按序循环10次，但如果我们通过一些已知的原则或是规律，就能从根源上起到“不用循环到10次”的效果 这里就需要介绍一下一种叫做“快速幂”的算法，众所周知，7的10次方可以表示为10个7相乘。这里如果我们按着这个表述去实现我们的程序，那么这个程序就需要执行10次7的相乘。但如果我们知道，7的10次方可以表示为7的平方和7的5次方相乘，那么我们的循环次数就是2+5=7次，这样我们就可以不用循环10次也能够得到正确的结果.以此类推的，我们可以尽可能想出执行次数少的方法来得到正确结果。而这一思想的宗旨就是去拼凑出“大底数小指数”的组合。 我们将这种方法和位运算结合，就可以得到以超大值m为幂的值的结果。为什么呢？如果你知道2进制与10进制的转换方式，其实很简单，当m每次右移1时，如果该位是1，那么计数器ans就乘上b的该位次序的次方。而根据int的性质，我们可以知道，这样的计算方法将计算次数压缩成小到极致的小于等于32次。 下面我们再来分析一下数学公式。 原始代数式是（…（（（a_b+c）_b+c）b+c）…b+c） 经过展开后可以得到a_b^（m-1）+c（从1到b^（m-1）的等比数列） 首先，我们可以根据上面的方法算出a_b^（m-1）的值，接着再通过等比数列的数学性质来解决后面的值，也就是1+b+b^2+b^3+…b^（m-1）=（1+b^（（m-1）/2））（1+b+b^2+b^3+…b^（（m-1）/2））.【如果m是奇数，那么就会有偶数项，所有前面m-1就要改成m-2，再在最后加个b^（m-1）】 不废话，下面上代码 代码 [Forlogin] #include <bitset> using namespace std; typedef long long ll; int MOD=10000; ll quick(ll a,ll b) { ll ans=1; a%=MOD; while(b) { if(b&1) ans=ans*a%MOD; a=a*a%MOD; b>>=1; } return ans%MOD; } ll sum1(ll a,ll b) { if(b==0) return 1; if(a==0) return 0; if(b&1) return ((1+quick(a,b/2+1)) * sum1(a,b/2))%MOD; else return ((1+quick(a,b/2+1)) * sum1(a,b/2-1) + quick(a,b/2))%MOD; } int main(){ int n; scanf("%d",&n); while (n--){ ll a,b,c,m,num; scanf("%lld%lld%lld%lld",&a,&b,&c,&m); if (m==1)printf("%lld\n",a%100); else { num=((a* quick(b,m-1))+c*(sum1(b,m-2)))%100; printf("%lld\n",num); } } return 0; }[/Forlogin]

先来看看牛客网的入门题 题目描述 Chranos是个数学天才。 一天，有一个可爱的小女孩追求Chranos，他知道Chranos最喜欢当且仅当总质量为K克的时候的番茄炒蛋了。她希望通过美食俘获Chranos的胃，这样就一定可以和他在一起了吧！虽然小女孩有无限数量的食材，但是数学王国的番茄和蛋非常特殊，他们的质量分别为N克和M克。为了表现一颗完整的心、表达充足的爱意，所有的食材必须被用完。N和M都是正整数且互素，制作过程中既不会凭空增加质量，也不会凭空消失质量。 Chranos不希望小女孩打扰他学数学。他发现，并不是所有番茄炒蛋都是可以被制作出来的。他想找出最大的不可以被制作出的总质量K来拒绝小女孩，这样Chranos就可以永远和数学在一起了！ 输入描述: 第一行为正整数N和M(2 \leq N, M \leq 50000)(2≤N,M≤50000)。 输出描述: 输出最大的不可以被制作出的总质量K。 示例 输入 2 3 输出 1 思路 可以通过找规律得到答案，但比较繁琐，所以还是选择找相关的数学知识来解决 这里应用到塞瓦维斯特定律，具体证明则需要用到裴蜀定律 塞瓦维斯特定律：已知a,b为大于1的正整数，gcd（a,b）=1，（a,b的最大公约数=1）则使不定方程ax+by=C不存在非负整数解的最大整数（C是最大的使不定方程 没有 非负整数解 的数。）C=a×b−a−b （需要看证明的移步到最下方） 通过这个定律就可以很容易写出代码。不过需要注意数据范围，所以记得开long long 代码 #include<stdio.h> #include<math.h> int main(){ int n,m; scanf("%d %d",&n,&m); printf("%ld",n*m-n-m); } 接下来我们再看一下NOIP原题 题目描述 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在 小凯无法准确支付的商品。 输入格式 两个正整数 $a$ 和 $b$，它们之间用一个空格隔开，表示小凯中金币的面值。 输出格式 一个正整数 $N$，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。 样例 #1 样例输入 #1 3 7 样例输出 #1 11 提示 【输入输出样例 1 说明】 小凯手中有面值为 $3$ 和 $7$ 的金币无数个，在不找零的前提下无法准确支付价值为 $1,2,4,5,8,11$ 的物品，其中最贵的物品价值为 $11$，比 $11$ 贵的物品都能买到，比如： ...

题目描述 棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。 现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入格式 一行四个正整数，分别表示 $B$ 点坐标和马的坐标。 输出格式 一个整数，表示所有的路径条数。 样例 #1 样例输入 #1 6 6 3 3 样例输出 #1 6 提示 对于 $100 \%$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。 【题目来源】 NOIP 2002 普及组第四题 思路 很简答，结合递归的想法，先把所有格子赋值为0，被马挡的格子标为2，只要碰到就return相应值就行 代码 #include<stdio.h> int bx,by,mx,my; int f(int **pan1,int bx1,int by1,int zx1,int zy1){ if(zy1+1<=by1&&zx1+1<=bx1){ if(pan1[zy1+1][zx1]==0||pan1[zy1][zx1+1]==0) return f(pan1,bx1,by1,zx1+1,zy1)+f(pan1,bx1,by1,zx1,zy1+1); else return 0; }else if(zy1==by1&&zx1+1<=bx1){ return f(pan1,bx1,by1,zx1,zy1+1); }else if(zy1+1<=by1&&zx1==bx1){ return f(pan1,bx1,by1,zx1+1,zy1); }else if(zy1==by1&&zx1==bx1){ return 1; }else return 0; } int main(){ scanf("%d %d %d %d",bx,by,mx,my); int zx=0,zy=0,pan[by+1][bx+1]; for(int i=0;i<=by;i++){ for(int j=0;j<=bx;j++){ pan[i][j]=0; } } pan[my][mx]=1; if(mx+1<=bx&&my+2<=my) pan[my+2][mx+1]=1; if(mx-1<=bx&&my+2<=my) pan[my+2][mx-1]=1; if(mx-2<=bx&&my+1<=my) pan[my+1][mx-2]=1; if(mx+2<=bx&&my+1<=my) pan[my+1][mx+2]=1; if(mx+1<=bx&&my-2<=my) pan[my-2][mx+1]=1; if(mx-1<=bx&&my-2<=my) pan[my-2][mx-1]=1; if(mx-2<=bx&&my-1<=my) pan[my-1][mx-2]=1; if(mx+2<=bx&&my-1<=my) pan[my-1][mx+2]=1; printf("%d",f(pan,bx,by,zx,zy)); } （由于尚未搞清的原因，上述代码还无法运行，具体错误也还没发现） ...

题目背景 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 $11$ 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 $11$ 分制和 $21$ 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。 题目描述 华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 $11$ 分制和 $21$ 分制下，双方的比赛结果（截至记录末尾）。 比如现在有这么一份记录，（其中 $\texttt W$ 表示华华获得一分，$\texttt L$ 表示华华对手获得一分）： $\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}$ 在 $11$ 分制下，此时比赛的结果是华华第一局 $11$ 比 $0$ 获胜，第二局 $11$ 比 $0$ 获胜，正在进行第三局，当前比分 $1$ 比 $1$。而在 $21$ 分制下，此时比赛结果是华华第一局 $21$ 比 $0$ 获胜，正在进行第二局，比分 $2$ 比 $1$。如果一局比赛刚开始，则此时比分为 $0$ 比 $0$。直到分差大于或者等于 $2$，才一局结束。 你的程序就是要对于一系列比赛信息的输入（$\texttt{WL}$ 形式），输出正确的结果。 输入格式 每个输入文件包含若干行字符串，字符串有大写的 $\texttt W$ 、 $\texttt L$ 和 $\texttt E$ 组成。其中 $\texttt E$ 表示比赛信息结束，程序应该忽略 $\texttt E$ 之后的所有内容。 输出格式 输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是 $11$ 分制下的结果，第二部分是 $21$ 分制下的结果，两部分之间由一个空行分隔。 ...