Xzt's Blog

XZT的个人博客

【SCOI2005】扫雷

Question 题目传送门 Solution 做完之后看题解，发现各位大仙递归就完事了 然而我还在挨个判断每种状态 首先我们看一看题目有四种情况 然后我们开一个三维数组f[i][j][k] f[i][j][k]表示当前位置i是否是雷（也就是j） 下一位置要不要是雷的方案数k 我们有了它就可以为所欲为了 判断下一位置的状态，看上一状态就好了 最后我们累加方案数就行了 Code #include<bits/stdc++.h> using namespace std; const int N = 11000; int n,g[N]; int f[N][2][2]; inline int read(){ int num=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') ...

Posted by xzt on May 2, 2019

Wpgwhpg

Inscription 长久以来， 我也想过换一种方式去爱这个世界。 以热烈，以冷漠，或以让别人满意为准。 但总觉得不妥， 那不是真正的我。 Background “身体是革命的本钱”,gryz每天都会进行游行般的跑操，当然跑操是小事儿，最 重要的还是每周两节61级一班一节都不能少的体育课。 上体育课每次都要跑一大圈进行热身，在某一天老师看不惯了一个人，那个人竟 然是上题中为lyk收拾残局的wpgwhpg，老师可能见他长得太可爱 所以奖励他以后每节体育课他都要跑圈，直到下课 所以，他只能认栽，自我安慰道：唉这是培养我运动细胞啊! Description 假如，有一天只有体育老师来上课，那么必然要一直上体育，所以上课N分钟, 就 要跑N分钟。但是他的体力有限，他有时候跑，有时候偷懒。他选择在第i分钟 跑，那么在这一分钟内他可以跑S米。假设他有疲劳度，且他...

Posted by xzt on April 29, 2019

Lyk

Inscription 行来春色三分雨 睡去巫山一片云 Background As we all know，gryz是一个永远都不会让你休息的地方，每天他都有你意想不 到的任务而你只能按照祂所吩咐的去做，否则你的德育积分就。。。 某一天， 的魔爪伸向61级，你要知道lyk是一个被周武王看重的学生 所以周武王会布置许多任务给他，那么lyk想他怎样忙里偷闲 去争取尽可能多的时间去休息，可他由于周武王繁重的任务没时间去想这些问题 所以他找到了你希望你可以帮助他 Description 每天起来，lyk都会积极地去周武王那里领取任务，每个任务由一个开始时刻与一个持续时间构成 他每天的待电时间为N分钟，当他拿到任务时就开始工作。但有时候周武王会 在同一时刻给他很多任务使他完全没有办法完全承受，所以周武王可怜他告诉 他：他可以选择其中一个来做，剩下的交给wpgwhpg来...

Posted by xzt on April 29, 2019

Diary

2019.04.29 今天是在Github上面第一篇日记 之前在我Cnblogs写的感觉总有一点不妥当的地方 所以另辟蹊径来到了这里 第一篇当然没有什么好写的所以就扯一下创建Github的原因吧 首先是因为发现周围的小伙伴都有了，便动心了 其次是这个网站不同于Cnblogs的地方在于他面对的范围更广 是一个不错的交流或者学习的地方 最后也是最直接的原因就是感觉做得挺高大上的 我的一天从Github开始然后就结束了 2019.05.01 五一快乐 虽然惨兮兮的只有一天

Posted by xzt on April 29, 2019

【国家集训队】特技飞行

题目背景 1.wqs爱好模拟飞行。 2.clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。 注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符 题目描述 神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间，每个单位时间可以进行一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。安排一种方案，使得总价值最大。 输入输出格式 输入格式： 第一行，两个数，N和K，如上所述； 第二行，K个正整数，表示K种动作的Ci值。 输出格式： 仅一行，一个整数，表示最大总价值。 输入输出样例 输入样例#1： 5 2 2 2 输出样例#1： 12 说明 对于10%的测试数据，N<=20，K<=3...

Posted by xzt on April 28, 2019

容斥原理

定义 在计数时，必须注意没有重复，没有遗漏 为了使重叠部分不被重复计算，人们研究出一种新的计数方法 这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复 这种计数的方法称为容斥原理 想必大家都不想读这么多字，而且读了还不一定懂 所以我们用维恩图来看一下： 简单明了，其实容斥原理就是小学学的重叠问题 公式 在百度百科中所展现的式子是这样的 而对于像我这样的初学者来看无疑是“天书” 所以我总结了一个式子 公式含义 如图，当我们减去两两相交的部分时，三个部分都重合的那个被减去了三次 因此需要加上一次 其实容斥也就这么多了 作为Oier，我们还要会敲代码 模板题 HDU Eddy’s爱好 AC代码： #include<bits/stdc...

Posted by xzt on April 28, 2019

匈牙利算法

概念叙述 看原理之前我们先来了解——匈牙利概念 在我们理解概念之后，我们知道这是一个优化时间的算法 至于原理是什么我们现在来讲 首先我们先来放一张男女找伴侣的图 是不是有种~鲜花插在牛粪上的感脚~ 我们看他们相互的连线，所连的线表示男生对某个女生有好感 那么我们男生按编号从小到大来找对象 很显然1——>1 2——>2，但是到3号的时候发现跟一号是情敌 那怎么办呢？我们假设三号抢的过一号那么一号女生让给了三号 还好一号还喜欢二号女生，那么我们把二号女生给一号 但是之前二号男生喜欢二号女生，那么只能受委屈 喜欢另一个目标——三号女生 这样前三位男生就不再冲突了 就是这种情况（蓝线表示两两相对关系） 那么，我们只能恭喜四号男生找到了~最漂亮~的女生 其实这种找对象方法是一个递归的过程 那么匈牙利算法就是这种原理——有条件就上，没条...

Posted by xzt on April 28, 2019

测试

测试模板

正文内容

Posted by xzt on April 28, 2019

【国家集训队】拉拉队排练

题面 题面 Solution 首先做这道题要掌握一个算法——Manacher算法 简要说他就是用来解决回文串相关问题的算法，并不高深 由题意可知，显然每一个和谐群体就是一个长度为奇数的回文串 用Manacher可以求每个位置的回文半径 因为我们只要求奇数个的回文串，那么显然我们不需要在字符串里添加一些无关字符 那么我们用Manacher求出以当前位置为中心的最长回文子串长度 所以我们就会在求的同时搞出最长的len 然后根据对称性可知也有长为len*2-1的回文子串，接着我们只需要统计一下就可以了 注意我们只要奇数个，去掉偶数个 因为数据范围过大，所以我们要Fast_Pow使得不会爆掉 AC代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int ...

Posted by xzt on April 28, 2019

FEATURED TAGS
Answer test Algorithm Diary Personal Problem
ABOUT ME

太想摘取星星的人，往往忽视了脚下的鲜花

✉️ 2864609873@qq.com