博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BLUESKY的NOIp模拟赛】解题报告
阅读量:5884 次
发布时间:2019-06-19

本文共 7926 字,大约阅读时间需要 26 分钟。

 昨天晚上熬夜熬得有点严重,今天比赛的时候状态不好,成绩爆炸。。。

 不得不说BLUESKY007 出的题还是相当不错的,也为我提醒了几个需要补的漏洞方向,这里作一下整理。

\(Task 1\):探索

\(1.1\) 题目描述

 古希腊哲学家柏拉图曾经在他的著作中这样描述道:“有这样一群囚徒,他们终生居住在一个黑暗的洞穴中,脖子和脚被锁住,无法环顾四周,只能面向洞穴岩壁。在囚徒身后,”有一堆篝火。在篝火与囚徒之间,有着形形色色的物体,火光将那些物体的影子投射到囚徒面前的岩壁上。这些二维影子就是囚徒们所能看到的全部,他们认为这就是现实世界。但真实情况是,世界要比他们他们所认为的二维世界多一个维度,锁链让他们无法回头看到这个真实的世界。然而这个真实的世界却远远比岩壁上的一切丰富多彩。”那么是不是也有可能我们现在生活的世界也是四维空间的一个投影?是不是宇宙大爆炸之前的纪元里,那时的空间要比我们现在的宇宙空间多出一个维度,而我们的宇宙诞生于高维宇宙中的一次恒星坍塌——这次坍塌在四维宇宙中产生了一个四维黑洞,而黑洞的三维表面,就是我们生活的宇宙?——

 沉浸在对高维时空幻想中的\(BLUESKY007\)想着想着,一不小心就睡着了。在梦里,她竟然来到了四维的神奇世界!这个世界被\(n\)堵三维的墙划分成了很多不同的区域。\(BLUESKY007\)感到很兴奋,于是她想要探索这个神奇的世界,但是每次她只能探索同一个区域。探索一个区域就可以获得一点开心值。

 由于这个四维世界的不确定性,她的开心指数也不会一样,现在她想要知道自己的开心值最大能达到多少。(由于答案一定会很大,所以只需要输出对\(m\)取模后的结果)

\(1.2\) 输入输出格式:

 输入:一行两个整数\(n,m\)

 输出:一行一个整数\(ans\),表示开心指数

\(discover.in\) \(discover.out\)
\(5,5\) \(1\)

\(1.3\) 样例输入输出解释

\(k[1]=2,k[2]=4,k[3]=8,k[4]=16,k[5]=31\)

\(1.4\) 数据范围与约定

  • 对于\(30\%\)的数据,\(n\le10^6,m\le10^5\)
  • 对于\(75\%\)的数据,\(n \le 10^{12},m \le 10^9\)

  • 对于\(100\%\)的数据,\(n,m \le 10^{18}\)

 看到高维的题目,第一想法当然是从低维找规律。但是由于本蒻昨晚修仙,今天早上脑子不清楚,所以直到最后才找到规律,只好匆忙打了一个30分暴力上去。

 先说基础想法,考虑下面一些情况:

拆分空间\维度 一维-零维 二维-一维 三维-二维 四维-三维
\(0\) 1 1 1 1
\(1\) 2 2 2 2
\(2\) 3 4 4 4
\(3\) 4 7 8 8
\(4\) 5 11 15 16

 简单来说就是线被点分,面被线分,体被面分的数量。通过列表会清晰的发现其差分规律,直接大力构造矩阵进行加速线性递推就可以了。

 值得注意的问题是快速乘的用法。实际上快速乘还有一种O(1)的写法,但是因为害怕出锅,所以这里不讨论,反正我也不是高端选手嘛。

 思想上类似快速幂,复杂度O(logn)。相当于把两数相乘,拆成一个数乘另一个数的二进制累加,常用于long long乘法取模爆精度的情况。

inline lint mul(lint x,lint y){    //mod m     lint res=0;    while(y){        if(y&1)res=(res+x)%m;        y>>=1;        x=(x+x)%m;    }    return res;}

 代码如下:

#include
#include
#include
#define lint long long using namespace std;struct Matrix{ lint mp[6][6]; void Init(){ memset(mp,0,sizeof(mp)); } void Unit(){ memset(mp,0,sizeof(mp)); for(int i=0;i<5;++i){ mp[i][i]=1; }//初始化为单位矩阵 }};lint tmp[5][5]={ {1,1,0,0,0}, {0,1,1,0,0}, {0,0,1,1,0}, {0,0,0,1,0}, {1,0,0,0,1}};//构造转移矩阵lint n,m,ans[1][5],bg[1][5]={1,1,1,1,1};//构造初始矩阵inline lint mul(lint x,lint y){ //mod m lint res=0; while(y){ if(y&1)res=(res+x)%m; y>>=1; x=(x+x)%m; } return res;}Matrix __mul(Matrix mat_1,Matrix mat_2){ Matrix res; res.Init(); for(int i=0;i<5;++i){ for(int j=0;j<5;++j){ for(int k=0;k<5;++k){ res.mp[i][k]=(res.mp[i][k]+mul(mat_1.mp[i][j],mat_2.mp[j][k]))%m; } } } return res;}Matrix __pow(Matrix mat,lint p){ Matrix res; res.Unit(); while(p){ if(p&1){ p^=1; res=__mul(res,mat); } p>>=1; mat=__mul(mat,mat); } return res;}int main(){// freopen("discover.in","r",stdin);// freopen("discover.out","w",stdout); cin>>n>>m; Matrix mat,res; for(int i=0;i<5;++i){ for(int j=0;j<5;++j){ mat.mp[i][j]=tmp[i][j]; } } res=__pow(mat,n);//mat^n for(int i=0;i<1;++i){ for(int j=0;j<5;++j){ for(int k=0;k<5;++k){ ans[i][k]=(ans[i][k]+bg[i][j]*res.mp[j][k])%m; } } } cout<
<

 为了保证写法的通用性与鲁棒性,这里我选择构造出来初始矩阵和答案矩阵,这个题不构造也是可以的。


\(Task 2\): 水果蛋糕

\(2.1\) 题目描述

 BLUESKY007要过生日了,为此朋友们准备给她买一个\(nm\)的水果蛋糕,但是在订蛋糕的时候却出现了问题:

 蛋糕是方形的,因为水果颗粒放整齐才好看,所以水果颗粒必须按行按列地摆放(也就是如果建立平面直角坐标系,它们的坐标必须都是整数).

 她的朋友们想要蛋糕店多放点水果,但是由于摆放得太密集也不好看,所以蛋糕店拒绝在和任意的水果颗粒相距 \(\sqrt{13}\)的地方摆放水果颗粒.(距离按照坐标计算)

 她的朋友们想知道蛋糕上最多能摆放多少水果颗粒,但是由于她们没有\(BLUESKY007\)聪(\(rui\))慧(\(zhi\)),所以她们找到了你来帮忙.

\(2.2\) 输入输出格式

 输入:一行两个整数\(n,m\)

 输出:一行一个整数表示答案

\(cake.in\) \(cake.out\)
1 4 4
\(cake.in\) \(cake.out\)
3 4 10

\(2.3\) 样例解释

1479416-20181017000318725-2097276965.png

 如图所示,左图为样例1的实现方案,右图为样例2的实现方案之一

\(2.4\) 数据范围与约定

  • 对于\(20\%\)的数据,\(n,m\le5\)

  • 对于另\(30\%\)的数据,\(n=3,m\le10^4\)

  • 对于另\(30\%\)的数据,\(n=4,m\le10^9\)

  • 对于\(100\%\)的数据,\(n,m\le10^9\)

 这个题目的想法让我很意外,以前很少见到类似这样较多特判的构造。

 首先题目很明确的告诉你了,这个题不能搜索。尽管如此,暴搜打表找规律还是可以的,不过似乎并不需要。

  • 首先考虑对\(n,m\le5\)的情况,可以直接用纸推出来。
  • 其次对于\(n=3\)的情况,可以构造出来一种最优情况,是中间全满,上下6个一循环。
  • 对于\(n=4\)同理,也可以得到循环的最优构造。
  • 对于更大的情况,因为上下也会互相干涉了,所以每两个格子里面最多放一个。考虑区分行列奇偶情况,特判求解即可。

 让人意外的一点是:这个题目的正解就是多个特判,而且部分分之间关联并不大,和往常那种层层递进引向正解的不太相似。虽然正解也好写,但是即使构造出来正确答案也很难不怀疑自己程序的正确性。所以果然,本蒻还是要多练习多见见世面啊QWQ

 为了方便本蒻这里做了一下关于\(n,m\)大小的处理,详见代码。

#include
#include
#include
#include
#define lint long longusing namespace std;lint n,m;lint r_3[6]={0,3,6,9,10,11};lint r_4[6]={0,4,8,10,12,12}; int main(){// freopen("cake.in","r",stdin);// freopen("cake.out","w",stdout); cin>>n>>m; if(n>m)swap(n,m); if(n<=2){ cout<
<
=5){ if(m&1)swap(n,m);//m为奇数就交换 if(~m&1&&~n&1){ cout<

\(Task 3\):好朋友

\(3.1\) 题目描述

\(BLUESKY007\)有很多关系很好的朋友,他们无一例外,名字均由数字组成(首字符不为\(0\))且含有"\(007\)"(例如"\(10007\)","\(10707\)"就是她的好朋友,而"\(97037\)","\(70709\)"不是),即对于字符串\(S\)存在\(i,j,k(i<j<k)\)满足\(\bar{Si}\bar{Sj}\bar{Sk}=“007”\)

 虽然\(BLUESKY007\)眼力极佳,一眼就能看出一个人是不是自己的好朋友,但\(BLUESKY007\)是个蒟蒻,她并不擅长数数,但她又想知道在\([li,ri]\)内有多少人是自己的好朋友,所以就找到了你来帮忙.

 她会向你询问\(T\)次,由于询问次数可能很多,所以你只需要告诉她\(T\)次询问答案的异或和即可.

\(3.2\) 输入输出格式:

 输入:第一行一个整数\(T\),表示询问个数. 接下来\(T\)行,每行两个整数\([li,ri]\)

 输出:一行一个整数表示答案.

\(friend.in\) \(friend.out\)
3 0
1 1000
233 666
999 999

\(3.3\) 样例解释

 在\(0~1000\)范围内不存在与题目要求相符的含有\(“007”\)的数,所以三次询问的答案都是\(0\).

3.8数据范围与约定

  • 对于20%的数据,\(li \le ri \le 10^3\)

  • 对于60%的数据,\(t \le 50,li \le ri \le 5*10^5\)

  • 对于100%的数据,\(t \le 10^5,li \le ri \le 10^{18}\)

 这个题目啊,\(exciting\)\(dreagonm\)说这个题是个送温暖的题目,然而本蒻不会数位DP所以凉凉,60分暴力走人。(幸好我晕乎着还能写出来暴力)学会之后发现数位DP除了处理起来复杂一点,其他和普通DP区别好像不是很大,之后几天,除了练\(NOIp\)题目顺手再多练练数位\(DP\)吧QWQ

 现在我们来考虑一下情况:

  • 对于目前还没有选到的情况,只需要当前这个数选0且没有前导0,就可以转移到选一个有效0的情况
  • 对于当前选择一个有效0的情况,只需要当前这个数选0,就可以转移到选择两个有效0的情况
  • 对于当前选择两个有效0的情况,只需要当前这个数选7,就可以转移到最终的目标情况
  • 对于已经成型的情况只需要保证上下不越界,就可以往后慢慢累加
  • 到达边界就返回值0/1(是否有合法情况),由调用处累计求答案
  • 如果本位置上对于数字大小没有限制就储存(有限制的话答案会不通用),同理不限制的时候进行记忆化调用。

 大概就这样,好像不是很难,明天继续刷类似的题目去。

 代码里注释很清晰。

#include
#include
#include
#define lint long longusing namespace std;lint t,l,s,ch,r,ans,arr[20],res[20][4];inline lint read(){ s=0,ch=getchar(); while(ch==' '||ch=='\n')ch=getchar(); while('0'<=ch && ch<='9') s=s*10+ch-'0', ch=getchar(); return s;}lint dfs(lint pos,lint cmd,lint led,lint lim){ //pos->当前位置 //cmd->控制状态 //led->前导0
//lim->是否受限
if(pos==0)//{// if(cmd==3){// //当前状态->已经达成// return 1; // }else{// //未达成->不累加 // return 0; // } return cmd==3; //} if(!led && !lim && res[pos][cmd])//{ return res[pos][cmd]; //} lint maxn=lim?arr[pos]:9,tmp=0; //可以取的数字上限->根据前面的数是否完全相等确定 for(lint i=0;i<=maxn;++i){ //i表示当前取的数 if(cmd==0)//{ //当前还什么都没有 //如果选的数字是0而且没有前导即可 //前导的状态:原来有的->如果还是0就继续有 //限制的状态:原来限制的->如果等于上限就继续有 tmp+=dfs(pos-1,!i&!led,led&!i,lim&(i==arr[pos])); else if(cmd==1) //已经有一个有效0,一定没有前导 tmp+=dfs(pos-1,(i==0)+1,0,lim&(i==arr[pos])); else if(cmd==2) //有两个有效0,需要一个7,没有前导 tmp+=dfs(pos-1,(i==7)+2,0,lim&(i==arr[pos])); else if(cmd==3) tmp+=dfs(pos-1,3,0,lim&(i==arr[pos])); } if(!led && !lim)res[pos][cmd]=tmp; return tmp; }inline lint sol(lint x){ //get ans in [1,x]; memset(arr,0,sizeof(arr)); memset(res,0,sizeof(res)); lint cnt=0; while(x!=0)//{ arr[++cnt]=x%10, x/=10;//转化进数组记录每一位 // }// for(int i=1;i<=cnt;++i){// for(int j=0;j<=3;++j){// printf("%lld ",res[i][j]);// }// puts("");// } return dfs(cnt,0,1,1); //从高位向低位找 }int main(){// scanf("%lld",&t); t=read(); while(t--){// scanf("%lld%lld",&l,&r); l=read(),r=read(); ans^=(sol(r)-sol(l-1)); //这里一次sol解决的是所有数位的问题,需要减去 // printf("%lld\n",(sol(r)-sol(l-1))); } printf("%lld\n",ans);}

@BLUESKY007

转载于:https://www.cnblogs.com/maomao9173/p/9801575.html

你可能感兴趣的文章
C++四种强制类型转换关键字
查看>>
IIS 7 WAS服务不可用
查看>>
hdu_2191多重背包
查看>>
Sublime console installation instructions install Package Control
查看>>
javaweb各种框架组合案例(三):maven+spring+springMVC+hibernate
查看>>
【HDOJ】2319 Card Trick
查看>>
MySQL在Linux下的安装
查看>>
第二周 登录小界面
查看>>
php函数 array_values()
查看>>
兼容firefox的iframe高度自适应代码
查看>>
Angularjs学习笔记(三)----依赖注入
查看>>
小学期软件工程团队项目进度1
查看>>
MOOC_Java进阶_翁恺讲_第三周题
查看>>
React-router匹配的组件 如何使用?
查看>>
HTML5 JS 实现浏览器全屏(F11的效果)
查看>>
Python进修> What is Python ?
查看>>
Thinkphp 学习笔记
查看>>
[洛谷P1631] 序列合并
查看>>
全局组件父子传参(父传子)
查看>>
Linux vsftpd编译安装和配置允许本地用户登录FTP
查看>>