关键词：
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目来自hzwer的模拟题
果实计数
（count.pas/.c/.cpp）
时间限制：1s，空间限制32MB
题目描述：
淘淘家有棵奇怪的苹果树，这棵树共有n+1层，标号为0~n。这棵树第0层只有一个节点，为根节点。已知这棵树为b叉树，且保证是一颗满b叉树。
现在，该树第n层的每个节点上都结出了一个苹果，淘淘想知道共结了多少苹果。由于数量可能很大，答案要求输出mod k后的结果。
输入描述：
给出第1层的节点数b和层数n和k.
输出描述：
输出苹果数mod k后的结果。
样例输入：
2 10 9
样例输出：
7
数据范围：
30%的数据保证：b<=100,n<=10, k<=100.
100%的数据保证：b<2^31,n<2^31,k<=2^15.
分析：
快速幂裸题。
AC代码：
1 #include<algorithm> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 7 inline void read(long long &x) 8 { 9 char ch = getchar(),c = ch;x = 0; 10 while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar(); 11 while(ch <= ‘9‘ && ch >= ‘0‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar(); 12 if(c == ‘-‘) x = -x; 13 } 14 15 long long a,n,k; 16 17 int ksm(int n) 18 { 19 long long r = a; 20 for(;n;n>>=1) 21 { 22 if(n&1) 23 r = r*a%k; 24 a = a*a%k; 25 } 26 return r%k; 27 } 28 29 int main() 30 { 31 read(a),read(n),read(k); 32 //最终果实数 = a^(n-1)%k 33 int ans = ksm(n-1)%k; 34 printf("%d ",ans); 35 return 0; 36 }
打地鼠游戏
（mouse.pas/.c/.cpp）
时间限制：1s 空间限制：128MB
题目描述：
伟大的2320学长特别喜欢打地鼠游戏，这个游戏开始后，会在地板上冒出一些地鼠来，你可以用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。可是，所有地鼠只会在地上出现一段时间（而且消失后再也不会出现），每个地鼠都在0时刻冒出，但停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同。
最近2320学长经常玩这个游戏，以至于敲击每个地鼠只要1秒。他在想如何敲击能使总分最大。
输入描述：
输入包含3行，第一行包含一个整数n（1<=n<=100000）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间（Maxt<=50000），第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值v（v<=1000）。每行中第i个数都表示第i个地鼠的信息。
样例输入：
5
5 3 6 1 4
7 9 2 1 5
样例输出：
24
数据范围：
30%的数据保证n<=100, t<=500,v<=50
60%的数据保证 n<=10000,t<=3000,v<=500
100%的数据保证 n<=100000,t<=5000,v<=1000
分析：
这题没有A...而且坚持认为自己的思路是对的，很郁闷。
正解思路：堆维护的贪心。把所有鼹鼠的参数放到一个大根堆里，然后按照时间顺序，依次取出堆中元素，在每秒钟都敲击当前能敲的分数最高的鼹鼠。
我的思路：贪心，按照分数给鼹鼠排序，用vis数组记录某个时间是否已经敲了鼹鼠。然后枚举每一只鼹鼠，并且尝试在它消失的那一秒敲击它。如果它消失的那一秒已经被使用，就往前找，找到最近的一个时间来敲击它并标记。
未能AC代码并求指错（如果是思路错了也请指教...）：
1 #include<algorithm> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 7 inline void read(int &x) 8 { 9 char ch = getchar(),c = ch;x = 0; 10 while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar(); 11 while(ch <= ‘9‘ && ch >= ‘0‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar(); 12 if(c == ‘-‘) x = -x; 13 } 14 15 struct MOLE 16 { 17 int t,v; 18 }a[100005]; 19 20 int vis[100005]; 21 22 int cmp(MOLE a,MOLE b) 23 { 24 if(a.v == b.v) 25 return a.t > b.t; 26 return a.v > b.v; 27 } 28 29 int main() 30 { 31 // freopen("1.txt","r",stdin); 32 int n,ans = 0; 33 read(n); 34 for(register int i = 1;i <= n;++ i) 35 read(a[i].t); 36 for(register int i = 1;i <= n;++ i) 37 read(a[i].v); 38 std::sort(a+1,a+1+n,cmp); 39 for(register int i = 1;i <= n;++ i) 40 { 41 if(!vis[a[i].t]) 42 vis[a[i].t] = 1,ans += a[i].v; 43 else 44 { 45 for(register int t = a[i].t;t > 0;-- t) 46 { 47 if(!vis[t]) 48 vis[t] = 1,ans += a[i].v; 49 } 50 } 51 } 52 printf("%d ",ans); 53 return 0; 54 }
斗牛
（niuniu.pas/.c/.cpp）
时间限制：2s，空间限制：128MB
题目描述：
为了更快的获取欢乐豆（因为本蒟蒻斗地主水平太低233），hzwer准备去玩欢乐斗牛，但是由于rp太差，hzwer在一个小时之内输光了20个QQ号的欢乐豆（每天系统会赠送每个号4000欢乐豆）。第二天他准备继续再战欢乐斗牛的抢庄模式，但是由于缺乏思考能力，hzwer需要编写一个程序来决定是否抢庄。
在玩家决定是否抢庄之前，系统会下发四张牌称为底牌，最后一张牌在决定后发放，每张牌可能为1-10，J，Q，K，hzwer认为最后一张牌为每一种点数的概率是相同的，对于一个由五张牌组成的牌型，分数计算规则如下，请你得出底牌的期望得分。
首先注意：在斗牛中，J，Q，K的点数视为10点，即11，12，13在计算头或点数时均视为10，所有牌无视其花色。
首先考虑特殊牌型
- 四炸——即5张牌中有4张一样的牌(如33334)，分数为40
- 五花牛——五张牌均是J，Q或K（如JQJQK），分数为50
- 五小牛——五张牌点数都小于5且点数和小于或等于10（如11223），分数为60
若有多种特殊牌型，得分取分数最大的特殊牌型（如11112视为五小牛）。
如果没有特殊牌型，首先判断牌型是否有“头”，如果五张牌中任意三张的总和为10的倍数如（1K9）即为有“头”，无“头”的牌型得分为0。
对于有头的牌型得分计算如下：
所有牌的和记为t，如果t%10=0则称为“牛牛”,牛牛得分为30；t%10<7称为“小牛”，得分为t%10，否则得分为（t%10）*2。
输入描述：
第一行一个整数T，表示T组数据
每组数据占一行，为4个整数（11，12，13分别表示J，Q，K）
输出描述：
对于输入的n行，输出每4张牌的期望得分（四舍五入）
样例输入：
2
2 2 2 2
10 4 5 12
样例输出：
43
9
样例解释：
对于2 2 2 2，最后一张为1或2时，构成五小牛，否则为炸弹，期望得分为(2*60+11*40)/13=43.08
对于10 4 5 12，最后一张为1-13的得分分别是30+0+0+0+4+5+0+0+0+18+18+18+18=111/13=8.54
1为牛牛，5为4点，6为5点，10-13为9点，其余无头
数据范围：
30%的数据T<=5
70%的数据T<=100000
100%的数据T<=1000000
蒟蒻感言：
在某次对局中发现期望得分很高，果断抢了庄，但是发现有闲家3个“牛牛”，瞬间消失20W欢乐豆
分析：
可怕的大暴力...
先用一个五维数组预处理出所有可能的得分，然后在求每一组数据的时候直接求和再/13即可。注意四舍五入。
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 6 inline void read(int &x) 7 { 8 x = 0;char ch = getchar(), c = ch; 9 while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar(); 10 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); 11 if(c == ‘-‘)x = -x; 12 } 13 14 inline int min(int a,int b) 15 {return a<b?a:b;} 16 17 int ans[15][15][15][15][15]; 18 int x,y,m,n,z,sum; 19 20 inline void init() 21 { 22 for(int a = 1;a <= 13;++ a) 23 for(int b = 1;b <= 13;++ b) 24 for(int c = 1;c <= 13;++ c) 25 for(int d = 1;d <= 13;++ d) 26 for(int e = 1;e <= 13;++ e) 27 { 28 if(a<5 && b<5 && c<5 && d<5 && e<5 && a+b+c+d+e <= 10) 29 ans[a][b][c][d][e] = 60; 30 else if(a>10 && b>10 && c>10 && d>10 && e>10) 31 ans[a][b][c][d][e] = 50; 32 else if((a==b && b==c && c==d) || (a==b && b==c && c==e) || (a==b && b==d && e==d) || (a==e && e==c && c==d) || (e==b && b==c && c==d)) 33 ans[a][b][c][d][e] = 40; 34 else 35 { 36 x = min(a,10),y = min(b,10),m = min(c,10),n = min(d,10),z = min(e,10); 37 if((x+y+m)%10 == 0 || (y+m+n)%10 == 0 || (m+n+z)%10 == 0 || (x+y+n)%10 == 0 || (x+y+z)%10 == 0 || (y+m+z)%10 == 0 || (y+n+z)%10 == 0 || (x+n+z)%10 == 0 || (x+m+n)%10 == 0 || (x+m+z)%10 == 0) 38 { 39 sum = x+y+m+n+z; 40 if(sum%10 == 0) 41 ans[a][b][c][d][e] = 30; 42 else if(sum%10 < 7) 43 ans[a][b][c][d][e] = sum%10; 44 else 45 ans[a][b][c][d][e] = (sum%10)*2; 46 } 47 } 48 } 49 } 50 51 int main() 52 { 53 init(); 54 int t; 55 read(t); 56 for(;t;--t) 57 { 58 sum = 0; 59 read(x),read(y),read(m),read(n); 60 for(register int i = 1;i <= 13;++ i) 61 sum += ans[x][y][m][n][i]; 62 sum = (sum/13.0)+0.5; 63 printf("%d ",sum); 64 } 65 return 0; 66 }
2017.8.2noip2018模拟测试赛（十八）(代码片段)
日期：八月二日 总分：300分 难度：提高~省选 得分：40分（又炸蛋了！！）题目列表：T1：分手是祝愿T2：残缺的字符串T3：树点涂色赛后心得：哎，T1求期望，放弃。看T2像是KMP打完发现并不可做，有感觉像是FFT... 查看详情
[题解]某模拟题（usaco月赛部分题+noip2005部分题）
题目描述 农场上有N(1<=N<=50,000)堆草，放在不同的地点上。FJ有一辆拖拉机，也在农场上。拖拉机和草堆都表示为二维平面上的整数坐标，坐标值在1..1000的范围内。拖拉机的初始位置与所有草堆不同。 FJ开拖拉机时，... 查看详情
noip欢乐赛10.24分火腿
分火腿题目描述：小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿。为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？输入描... 查看详情
启航组欢乐赛题解(代码片段)
T1买本子这一道题我们可以考虑暴力分解：如果每一个包装所含本子的数量不能总共要买的本子数量整除的话，要买的包装总数要多一，然后求出各包装总共的钱数最后比大小即可。#include<cstdio>#include<cstring>usingnamespacest... 查看详情
暑假爆零欢乐赛srm08题解
这真的是披着CF外衣的OI赛制？我怎么觉得这是披着部分分外衣的CF？果然每逢cf赛制必掉rating，还是得%%%cyc橙名爷++rp。。 A题就是找一找序列里有没有两个连在一起的0或1，并且不能向两端延伸（比如……1001……或110…... 查看详情
题解pta团体程序设计天梯赛l1-035情人节(15分)go语言|golang(代码片段)
L1-035情人节(15分)Go语言|Golang以上是朋友圈中一奇葩贴：“2月14情人节了，我决定造福大家。第2个赞和第14个赞的，我介绍你俩认识…………咱三吃饭…你俩请…”。现给出此贴下点赞的朋友名单，请你找出那两位... 查看详情
天梯赛每日打卡04（26-40题解）(代码片段)
...太胖了(10分)L1-028判断素数(10分)logN判断素数最快判断L1-035情人节(15分)L1-033出生年(15分)L1-030一帮一(15分)L1-027出租(20 查看详情
$noip2016day1$模拟考试题解报告(代码片段)
没有摘要的摘要目录$NOIP\\2016\\Day1$模拟考试题解报告得分情况考试过程题解$T1$玩具谜题$T2$天天爱跑步$T3$换教室\\(NOIP\\2016\\Day1\\)模拟考试题解报告得分情况\\(T1\\)\\(85\\Pts\\)\\(T2\\)\\(15\\Pts\\)\\(T3\\)\\(100\\Pts\\)总分:\\(200\\Pts\\)考试过... 查看详情
2018.8.6noip2018模拟测试赛（十九）(代码片段)
日期：八月六号 总分：300分 难度：提高~省选 得分：10分（MMP）题目目录： T1：Tree T2：异或运算 T3：TreeRestoring赛后反思：Emmmmmmm……一直在打第一题……结果考完才发现dp少了一种... 查看详情
2018.7.31noip2018模拟测试赛（十六）(代码片段)
日期：七月最后一天 总分：300分 难度：提高~省选 得分：30分（少的可怜）我太弱了：（题目目录）T1：Mushroom追妹纸T2：抵制克苏恩T3：美味失分分析：（QAQ）开始全部题目看了一遍，第二题期望dp，果断放弃…... 查看详情
天梯赛赛前热身(代码片段)
...题涉及的算法L2-001紧急救援图论,dijkstra+dfsL2-002链表去重模拟+链表L2-003月饼完全背包L2-004这是二叉搜索树吗？二叉树遍历L2-005集合相似度集合L2-006树的遍历二叉树遍历L2-007家庭房产并查集+排序✔L2-008最长对称子串DPL2-009抢红包排... 查看详情
综合-某假期欢乐赛(apri,2018)(代码片段)
假期欢乐赛，确实挺轻松的，被逼迫写了题解。A.推数按列观察，有的列有多个格子，看起来好复杂啊，先放一放。按行观察，黑色格子在i行j列：当i是奇数，对应数字第i位是j-1当i是偶数，对应数字第i位是9-jB.体重某位同... 查看详情
数列题解（noip模拟t2）
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。 【题目描述】a[1]=a[2]=a[3]=1a[x]=a[x-3]+a[x-1] (x>3)求a数列的第n项对1000000007（10^9+7）取余的值。【输入格式】第一行一个整数T，表示询问个数。... 查看详情
noip模拟6考试总结
T1这道题是一道裸的暴力，考场写挂了\\(5pts\\)原因竟是忘了删注释，难受题解T2这道题是一道启发式合并，没想出来，拿了个暴力分跑了题解T3这道题就是一道数学期望，想出来就水得很，想不出来那就暴力题解T4\\(NOIP\\;\\;2017\\)... 查看详情
noip模拟8-21题解
一份模拟题...水得要命真是没谁了。减法(sub.c/.cpp)题目描述东东在幼儿园刚刚学会了20以内的减法，就迫不及待的跑回家要给爸爸出题了。问“10-1”来考东东爸，东东爸想也没想就说是“1”。东东顿时喜笑颜开，臭... 查看详情
noip模拟b君的数组题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。%%%%%%%%%%%%%毕克dalao Orzzzzzzzzzzzz题目大意：给出一个数组a，大小是2^k，下标从0开始。求：对于每个x（0<=x<2^k），下标满足x&i=i的所有ai的和。... 查看详情
noip模拟problem1任务安排题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目大意：你有N个任务，每个任务有其持续时间和截止日期，你在同一时间只能进行一项任务。问：要完成所有的任务，你最晚要从什么时候开始工... 查看详情
数列（noip17提高模拟训练11）
给你一个长度为N的正整数序列，如果一个连续的子序列，子序列的和能够被K整除，那么就视此子序列合法，求原序列包括多少个合法的连续子序列？对于一个长度为8的序列,K=4的情况：2,1,2,1,1,2,1,2。它的答案为6，子序列是位置1... 查看详情