wweiyiのblog

【清北学堂国庆刷题班】Day6 T1 math 题目描述 请求出 gcd(qa−1,qb−1) gcd(q^a-1,q^b-1) gcd(qa−1,qb−1) 模p的结果。 输入格式 第一行一个整数T，表示数据组数。 接下来T行，每行四个整数q,a,b,p。 输出格式 T行，每行一个整数表示答案。 样例输入 1213 1 2 11 样例输出 12 数据范围 对于30%的数据，a,b≤500,T≤100 对于另外30%的数据，p为素数 对于所有数据，满足1<=q,a,b,p<=109,T<=104,q>11<=q,a,b,p<=10^9,T<=10^4,q>11<=q,a,b,p<=109,T<=104,q>1 思路 式子变形 gcd(qa−1,qb−1)=gcd(qb−1,qa−1−qb+1)=gcd(qb−1,qa−qb) gcd(q^a-1,q^b-1) =gcd(q^b-1,q^a-1-q^b+1) =gcd(q^b-1,q^a-q^b) gcd(qa−1,qb−1)=gcd(qb−1,qa−1−qb+...

还有9天我就要走上中考的考场，加油！

祖国生日快乐

【解题报告】 [YNOI2019]排队 题目描述 小明所在的班级要举办一场课外活动，在活动开始之前老师告诉小明：“需要把男女生分成两队，并且每一队都要按照身高从矮到高进行排序”。但是由于小明的马虎，没有把老师的安排转达给同学，导致全班同学已经排成了一列。活动马上要开始了，小明的老师对此很困扰，你能帮帮她吗？ 输入格式 输入文件名为queue.in。 每个输入文件包含多组数据。 输入文件的第一行，包含一个正整数T，代表该输入文件中所含的数据组数。 接下来是T组数据，每组数据的格式如下： 每组数据包含3 行； 第一行包含一个整数n，代表班级的总人数，其中(0 < h ≤ 10410^{4}104)； 第二行包含n个整数，它们之间用一个空格隔开，代表已经排成的一列中每一位同学的性别。每一位整数只取0 或1（0 表示女生，1 表示男生）； 第三行包含n个浮点数，它们之间用一个空格隔开，与第二行中的数据一一对应，代表已经排成的一列中每一位同学的身高h(100 ≤ h ≤ 200)。 输出格式 输出文件名为queue.out。 输出文件包含2T行，分别对应T组数据的答案，每组答案的格式...

【解题报告】[AHOI2001]彩票摇奖 题目描述 为了丰富人民群众的生活、支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是： (1) 每张彩票上印有 7 个各不相同的号码，且这些号码的取指范围为 1~33。 (2) 每次在兑奖前都会公布一个由七个各不相同的号码构成的中奖号码。 (3) 共设置 7 个奖项，特等奖和一等奖至六等奖。兑奖规则如下： 特等奖：要求彩票上 7 个号码都出现在中奖号码中。 一等奖：要求彩票上有 6 个号码出现在中奖号码中。 二等奖：要求彩票上有 5 个号码出现在中奖号码中。 三等奖：要求彩票上有 4 个号码出现在中奖号码中。 四等奖：要求彩票上有 3 个号码出现在中奖号码中。 五等奖：要求彩票上有 2 个号码出现在中奖号码中。 六等奖：要求彩票上有 1 个号码出现在中奖号码中。 注：兑奖时并不考虑彩票上的号码和中奖号码中的各个号码出现的位置。例如，中奖号码为 23 31 1 14 19 17 18，则彩票 12 8 9 23 1 16 7 由于其中有两个号码(23 和 1)出现在中奖号码中，所以该彩票中了五等奖。 现已知中奖号码和小明买的若干张彩...

【解题报告】 [NOIP2006]能量项链 题目描述 在Mars星球上，每个Mars人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。 能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。 并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。 因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。 如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 mrn（Mars单位），新产生的珠子的头标记为 m，尾标记为 n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。 显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。 我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第 j，k 两颗珠子聚合后所释放的能量。则 第4、1两颗珠子聚合后释...

【解题报告】 启示录 题目描述 探险队员终于进入了金字塔。通过对古文字的解读， 他们发现，和《圣经》的作者想的一样，古代人认为 666 是属于魔鬼的数。不但如此，只要某数字的十进制表示中 有三个连续的 6，古代人也认为这个是魔鬼的数，比如 666, 1 666, 2 666, 3 666, 6 663, 16 666, 6 660 666 等等，统统是魔 鬼的数。 古代典籍经常用“第 X 大的魔鬼的数”来指代这些数。 这给研究人员带来了极大的不便。为了帮助他们，你需要写一个程序来求出这些魔鬼的数字。 输入格式 输入文件包含多组测试数据。第一行有一个整数 T 表示测试数据的组数。 每组测试数据包含一个整数 X，表示需要求第 X 大的魔鬼的数。 输出格式 对于每组测试数据，在一行内输出结果。 输入输出样例 输入 #1 1234323187 输出 #1 1231666266666666 说明/提示 对于 20% 的数据，保证 X≤10e6。 对于 100% 的数据，保证 T≤1 000，X≤50 000 000。 解题思路 这是一个标准的数位Dp，我们只需要简单地找出他的动态转移方程，...

【NOIP2018】 摆渡车 题目：摆渡车 解题思路： NOIP2018 PJ T3 时隔一年还是会感到有一些难度，让我措手不及，所以我这次做出来了，虽然不是自己做的，但是明白了意思，在基础上又进步了一大步 AC代码 123456789101112131415161718192021222324252627282930313233#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int n,m,t[505],mem[505][505];int solve(int i,int st){ if(i==n+1) return 0; if(st<t[i]) return solve(i,t[i]); if(mem[i][st-t[i]]) return mem[i][st-t[i]]; int sum=0,j=i; while(j<=n&&t[j]<=st) sum+=t[j++]; int best=st*...

【NOIP2017】 奶酪 题目：奶酪 解题思路： 同样的，可以用dfs做，但是有没有发现，用并查集做会更加地，简单？ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>using namespace std;struct node{ long long high,low; long long x,y,z;};long double dist(node p,node q){ return (lo...

【NOIP2017】 棋盘 题目：棋盘 解题思路： 从左上向右下搜索，然后来一点剪枝就可以了，比较简单，毫无体验感 AC代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <iostream>#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int inf=0x7fffffff;int m,n;int map[105][105];//如果是1，代表黄色；如果是2，代表红色；int s[105][105];int sx[4]={-1,0,1,0};int sy[4]={0,-1,0,1};int ans=inf;void dfs(int x,int y,int cost,bool use){...