PAT-B] 1007. 素数对猜想 [数论]

链接:1007. 素数对猜想 (20)

题意

任意给一个小于$10^5$的正整数N,并要求在$( 0, N )$这个范围内,
找出满足以下条件的数对的总数:

  1. 两个数均是素数
  2. 两个数之间相差2

样例中的N20
满足条件的数对为:
3, 55, 711, 1317, 19
总计4对, 则输出4

分析

题意中要求判断的数均为素数,而且给的N也并不大。所以直接暴力打表,把所有的素数存到数组中再处理也挺简单的。

题目要求的条件是相差为2,对于素数来说除了2之外就没有其他偶数了,所以这里我们可以直接对相邻的素数进行判断,如果相邻的还不行其他的也不用考虑了。

PS:如果是其他的OJ说明输入多组样例的话,把每次的结果存下来给下面的样例使用会快很多哦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
typedef long long LL;
int prime[100015]; // 增序存放素数
int flag[100015]; // 标记这个下标对应的数是否是素数
int idx = 0; // 素数数组的下标
void init( int n ){
// 初始化两个数组为 0
memset( prime, 0, sizeof( prime ) );
memset( flag, 0, sizeof( flag ) );
for( LL i = 2; i < n + 10; i++ ){
if( flag[i] ) continue; // 非素数则不处理
prime[ idx++ ] = i; // 素数存入素数数组
for( LL j = i * i; j < 100002; j += i ) // 将其倍数均标记为合数
flag[j] = 1;
}
}
int main()
{
int N;
while( ~scanf( "%d", &N ) ){
init( N );
int num = 0;
for(int i = 2; prime[i] <= N; i++ ){
// 依次遍历相邻的素数 看是否满足条件
if( prime[i] - prime[i - 1] == 2 )
num++;
}
printf( "%d\n", num );
}
return 0;
}

小结

处理出素数的方法有很多,可以多尝试尝试。

PAT-B] 1006. 换个格式输出整数 [模拟]

链接:1006. 换个格式输出整数 (15)

题意

给一个小于1000的正整数,按照以下格式输出:

  1. 个位数:从1开始按顺序输出直到等于个位数为止
    (如个位数为7,则输出1234567
  2. 十位数:按十位数的大小输出相应数量的 S
  3. 百位数:按百位数的大小输出相应数量的 B

则,如果给一个两位数43,我们就要输出SSSS123

分析

题意比较简单,按照思路写下来就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
int main()
{
int n;
while( ~scanf( "%d", &n ) ){
int b, s, g; // 百, 十, 个
g = n % 10; // 存放个位数
n /= 10;
s = n % 10; // 存放十位数
n /= 10;
b = n % 10; // 存放百位数
for( int i = 0; i < b; i++ )
putchar( 'B' );
for( int i = 0; i < s; i++ )
putchar( 'S' );
for( int i = 0; i < g; i++ )
printf( "%d", i + 1 );
puts( "" );
}
return 0;
}

小结

大水题。

codeforces] ECR19 A. k-Factorization [数论]

链接:Codeforces Educational Codeforces Round 19 A. k-Factorization

题意

给你两个正整数 n, k

判断是否存在k个数相乘,使其乘积等于n
如果不存在,输出-1
如果存在,再以任何你喜欢的顺序输出这k个数。
(当然他们之间应以空格分隔)

分析

题目不难,应该有很多种方法解答这个问题。

我直接说一下我的思路:

既然要得到k个数相乘,那么这k个数肯定是尽量越小越好
(比如n能被6整除,那尽量把6拆成23。)
这里面有点贪心的感觉。因为如果剩下的n越大,那满足k个数的概率也就越大。

所以这道题我直接从2开始循环判断是否能够做n的因子。
如果可以就直接存下来,n除去当前因子,然后继续判断这个因子。
如果不行,那再判断他的后一个(新因子 = 因子+1

依次这样判断,直到找不到因子了或者已经够个数了为止。

(当已经找到k-1个因子时,就可以直接把剩下的n当做最后一个数,而不用继续做下去了。)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <vector>
using namespace std;
int n, k;
int main()
{
while( ~scanf( "%d %d", &n, &k ) ){
vector< int > ans; //用来存这k个数
int j = 0; //保存当前因子个数
for( int i = 2; i <= n; i++ ){
if( n % i == 0 ){ //若能整除则存下来
if( ++j == k ){ //已经存够k-1个数,则直接存入剩下的n
ans.push_back( n );
break;
}
n /= i;
ans.push_back( i );
i--;
}
}
if( j != k ) puts( "-1" );
else{
int sz = ans.size();
printf( "%d", ans[ 0 ] );
for( int i = 1; i < sz; i++ ){
printf( " %d", ans[ i ] );
}
puts( "" );
}
}
return 0;
}

小结

毕竟签到题,比较得简单,如果大家有更简单的方法可以留言或者Q我。

PAT-B] 1005. 继续(3n+1)猜想 [查找]

链接:1005. 继续(3n+1)猜想 (25)

题意

(3n+1)猜想的衍生题目。
给你一串数字,对每个数字进行猜想的验证,如果其中的某些数字并没有在验证其他数字的时候被验证过,那这些数字就是关键数字。并以从大到小的顺序输出他们。

分析

这道题目的话不需要想太多,就依次验证每一个数字就可以了。在验证数字的过程中,把每一个中间数字都保存下来就可以了。
所以我们需要一个保存数字的数组f[],然后对中间数字进行标记(比如验证5的时候,就能得到中间数字8, 4, 2, 1,分别将f[8], f[4], f[2], f[1]都置为1就可以了)
值得一提的是,在递归验证思想的时候如果发现某个中间数字已经被置为1了,那么就不需要再递归下去了,因为下面的数字都已经被算过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[ 100000 ]; //标记这个数字是否已经查找过了
int in[ 105 ]; //输入
void solve( int n, int i ){ //n为由猜想递归计算得到的数 i为输入的当前数字
if( f[ n ] || n == 1 ) return; //得到的n已经查找过了或者已经查找到1满足猜想了就结束程序
if( n != i ) f[ n ] = 1; //将递归计算到的数都置为 1 表明这些数字都已经在验证猜想时被覆盖了
if( n % 2 ) solve( ( 3 * n + 1 ) / 2, i );
else solve( n / 2, i );
}
int main()
{
int k;
while( ~scanf( "%d", &k ) ){
memset( f, 0, sizeof f );
memset( in, 0, sizeof in );
f[ 1 ] = 1;
for( int i = 0; i < k; i++ ){
scanf( "%d", in + i );
}
for( int i = 0; i < k; i++ ){
solve( in[ i ], in[ i ] );
}
sort( in, in + k ); //排序方便降序输出
int flag = 1;
for( int i = k - 1; i >= 0; i-- ){
if( f[ in[ i ] ] == 0 ){ //f为0表示该数没在递归中被查找到,则输出
if( flag ) flag = 0;
else printf( " " ); //空格规范
printf( "%d", in[ i ] );
}
}
puts( "" );
}
return 0;
}

小结

就慢慢做就好了..

PAT-B] 1004. 成绩排名 [查找]

链接:1004. 成绩排名 (20)

题意

给你很多学生的成绩,然后找出拿最高分的学生和拿最低分的学生。

分析

解决这类问题有很多种方法,我的想法就是能不存下来就不存下来,尽量采用在线处理的方式,$O(n)$ 的复杂度,很快。
在线处理就是说在边存入数据的时候就直接处理。
这道问题中,每次输入一个学生的三个信息,就把他的成绩跟我们已经存好的最高和最低分进行比较,如果更大或者更小,就直接用这个学生的信息替换到已经存好的信息。
这样,当我们录入完信息之后,答案也就出来了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
struct stu{
char name[ 12 ], no[ 12 ];
int score;
};
int main()
{
int n;
while( ~scanf( "%d", &n ) ){
stu ma, mi, t; //成绩最高,最低 和 当前学生
scanf( "%s%s%d", t.name, t.no, &t.score );
ma = t; mi = t;
for( int i = 1; i < n; i++ ){
scanf( "%s%s%d", t.name, t.no, &t.score );
if( t.score > ma.score ) ma = t;
if( t.score < mi.score ) mi = t;
}
printf( "%s %s\n", ma.name, ma.no );
printf( "%s %s\n", mi.name, mi.no );
}
return 0;
}

小结

一道简单的查找题..

PAT-B] 1003. 我要通过! [字符串处理]

链接:1003. 我要通过!(20)

题意

一道字符串处理问题。
输入一行字符串 :

  1. 字符串中必须仅有P, A, T这三种字符,不可以包含其它字符;
  2. 任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;
  3. 如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 a, b, c 均或者是空字符串,或者是仅由字母 A 组成的字符串。

满足这三个条件就输出“YES”, 否则输出“NO”

分析

条件1 只是针对字符串有限制,作前提

再看 2 和 3 :
条件2 是“YES”的直接要求,而条件3 是 间接要求

整理思路 :

  1. 首先满足前提,字符串中分别只能依次出现一个 P一个 T,其余若干项只能填充 A
  2. 条件2 中提出 P 和 T 之间由一个 A 分隔,且 a == c (小写表示长度,下同)。 条件3 中提出 aPbTc 正确,则 aPbATca 也正确,这就给了我们一个关系式 : c == b * a。只要满足该关系式,字符串就能通过。

有一点注意 :
这道题有题意不清楚的地方。就是并不是 aPbTc 这种形式出现过了,aPbATca 才正确。只要递推到最后的式子满足条件2 就是“YES”

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
int N;
char c;
int f, P, T, i;
int main()
{
while( ~scanf( "%d", &N ) ){
getchar();
for( int t = 0; t < N; t++ ){
f = 1, i = -1, P = -1, T = -1;
while( scanf( "%c", &c ) && c != '\n' ){
i++;
if( c == 'P' ){
if( P == -1 ) P = i; //第一次遇到 P, 记录位置
else f = 0; //第二次遇到 P, 改结果 f 为不通过
}
else if( c == 'T'){ //同 P 的处理
if( T == -1 ) T = i;
else f = 0;
}
else if( c != 'A' ) f = 0; //遇 PAT 以外的字母, 改结果 f 为不通过
}
if( f ){
if( P == -1 || T == -1 ) f = 0; //判断是否有 P 和 T
else if( P >= T - 1 ) f = 0; //判断 P 和 T 的 位置是否满足要求
else if( i - T != ( T - P - 1 ) * P ) f = 0; //关键递推式
}
if( f ) puts( "YES" );
else puts( "NO" );
}
}
return 0;
}

小结

分析出结论就不难..
一开始会掉到我提到的注意的地方。(应该不是我脑回路不正常吧!)

PAT-B] 1002. 写出这个数 [字符串处理]

链接:1002. 写出这个数(20)

题意

输入一个整数 n 。
计算 n 的每一位的相加的和 sum
以拼音的方式顺位输出

分析

首先,这个 n 范围很大.. 小于 $10^{100}$
也就是说这个 n 最大可以取到 $10^{100} - 1$ 。
所以先定位到字符串处理问题。(虽然可以不用字符串,用轻松的方法来写。详见代码)

如果用字符来存储某一位数字的话,在计算 sum 的时候就要注意 - ‘0’。不减的话可以要犯大错误的。

算完 sum 之后 输出每一位数字的拼音的时候。要注意两点 :

  1. 拼音要高位先输出,之间有空格最后没空格
  2. 拼音要学好 (・-・*)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <stack>
using namespace std;
char* py[10]={ "ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };
int main()
{
char n;
int sum = 0;
while( ~scanf( "%c", &n ) && n != '\n' ){
sum += n - '0';
}
stack< int > stk;
while( sum ){
stk.push( sum % 10 );
sum /= 10;
}
printf( "%s", py[ stk.top() ] );
stk.pop();
while( stk.size() ){
printf( " %s", py[ stk.top() ] );
stk.pop();
}
puts( "" );
return 0;
}

小结

用上stack写起来比较简单..

//

PAT-B] 1001. 害死人不偿命的(3n+1)猜想 [模拟]

链接:1001. 害死人不偿命的(3n+1)猜想 (15)

题意

非常简单的数论模拟。

输入一个 n :

  1. 判断这个数 n 的奇偶性
  2. 奇数 -: n = ( 3 * n + 1 ) / 2
  3. 偶数 -: n = n / 2
  4. 不断地重复,直到 n = 1 停止。输出重复了几次

分析

其实都不用分析了…
只要按照题意去循环就好了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
long long solve( long long n ){
if( n == 1 ) return 0;
if( n % 2 ) return 1 + solve( ( 3 * n + 1 ) / 2 );
else return 1 + solve( n / 2 );
}
int main()
{
long long n;
while( ~scanf( "%lld", &n ) ){
printf( "%lld\n", solve( n ) );
}
return 0;
}

小结

很水的一道题..
dalao签到用

codeforces] #398(Div.2) B. The Queue [模拟]

链接:Codeforces Round #398 (Div. 2) B. The Queue

题意

Vasya 这个人终于成年了。有一天,他想去办个护照(年龄到了就想出去浪)。说做咱就做,他决定明天就去办事处搞点事情。

但是问题就出现了,办证这种事情一看就会有很多人,哪个时候去可以少排一会儿队呢?

Vasya决定将偷懒进行到底,先是弄来了办事处的开门时间 $t_s$ ,关门时间 $t_f$ 和为每个客户服务需要消耗的时间 $e_t$(这里假设每个客户需要的时间相同)。然后他又通过特殊渠道得知了明天会有 $n$ 个客户,以及每个客户来的具体时间 $n_t$

补充:

  1. Vasya和其他客户到达办事处的时间点均为整点。
  2. 当Vasya和其他人同时到达时,Vasya会表现出他的绅士风度,让其他人排在他前面
  3. 工作人员反应很快,一旦有人来就会马上开始工作
  4. 如果给的数据有多个答案,只需给出其中任意一个答案
  5. Vasya在明天必须拿到护照

分析

题意描述应该非常清晰了,但这个题目里面所包含的各种特殊情况在比赛的时候不是那么容易考虑得到。
所有的情况大概有以下几点:

  1. 来的人不是很多或者工作效率很高,在整个工作时间内有那么一个时刻工作人员在玩手机
  2. 办事处还没开门,但早就有围观群众到场了
  3. 虽然来了很多人,但是大家都睡过了头,在关门之后才到
  4. 人满为患,这一天都有很多人没能办成功的

1 和 3 应该是比较简单的,直接找一个空闲的时间作为答案就可以了。相比较而言比较麻烦的是 2 和 4 。
2 和 4 需要在各个客户之间的时间进行比较判断,才能寻得最优解。
当然这四个都不是难的,结合起来更麻烦。

下面就说一下我的思路:

最优解就在 空闲时间某个客户来之前一分钟的那个时间($n_t-1$) 其中一个。

空闲时间就不解释了。根本不用等啊。
(但是一定要保证到关门之前有充足的时间来办护照哦,即$t+e_t<t_f$)

后面那个的话就是

  1. 把本来可以排最少时间的客户挤掉,代替他的位置。(这样你就必须比他早来)
  2. 尽可能地不在前面的人身上浪费时间。(只要早一分钟来)

然后这个问题就变成了求哪个客户等的时间最短的问题
(分别求出他们离开的时间就行了)
(总共就$10^6$的客户,都遍历一遍也没问题)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
typedef __int64 LL;
LL nt[100005];
int main()
{
LL ts,tf,et;
while(~scanf("%I64d%I64d%I64d",&ts,&tf,&et)){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%I64d",&nt[i]);
}
LL t=ts,ans=nt[1]-1;
LL low=t-nt[1]+1; //最少消耗的时间
if(ans+et>tf){
ans=ts;
t=tf+1;
}
int f=0; //判断是否有空闲时间
for(int i=1;i<=n&&t<=tf;i++){
if(nt[i]>t){
ans=t;
f=1;
break;
}
if(i>1){
LL l=t-nt[i]+1; //当前客户消耗的时间
if(l<low){
ans=nt[i]-1;
low=l;
}
}
t+=et;
}
if(f) printf("%I64d\n",ans);
else if((t<tf)&&((t+et)<=tf)) printf("%I64d\n",t);
else printf("%I64d\n",ans);
}
return 0;
}

小结

由于这个题目考虑的点比较多且繁琐(在比赛的时候我真的这样觉得!)所以就收录下来了(其实是个水题)
针对模拟类的题目自己不是特别敏感,写一下也加深印象。

如果有更好的方法或者我有什么不足或者有什么值得探讨的东西的话,可以评论或者联系我。

hexo] Light主题的修改使用

(更新ing..)
(文中出现各类链接均来自搜索引擎。侵删

使用hexo搭建博客

博客搭建在Github上,地址是 Nezar’s Nest . 搭建的过程参考零基础免费搭建个人博客-hexo+github

这里要注意几点:

  • 上面链接中的node.js的版本最好在官网上下载 4.0.0(好像)以上的版本,不然淘宝NPM镜像步骤会失败
  • 记得如果是用的上面文章中的淘宝镜像。 npm 以后都要改成 cnpm 来使用 (非常重要!)
  • Github的账号跟你要申请的博客的域名(xxx.github.io)黑体部分必须一致。否则博客会打不开,显示404

更改主题

当然这里你也可以用原来默认的官方主题Landscape.
这里给想换的朋友一个知乎上的问题链接 有哪些好看的 Hexo 主题?
我个人用的是其中很老的一个主题 Light . 很简约,我个人比较喜欢。

选完了主题,接下来就要对主题发挥自己的修改了。毕竟别人的东西自己用起来多多少少会有些不习惯,更何况在大天朝,有些功能使用起来可能不好用甚至没办法用。
这里需要再给一个链接,以便修改掉一些必须去掉的功能,增加一些必须有的功能 Hexo-基于hexo-theme-light的主题修改
(这个链接里的内容我暂时只做了第一个)

然后接下来就是自由发挥了。

修改字体

路径:\themes\hexo-theme-light-master\source\css\_base\variable.styl
修改 font-default = "Times New Roman", "Microsoft YaHei", Arial, sans-serif
效果是以“Times New Roman”,”微软雅黑”,”Arial”,”sans-serif” 的优先级设置默认字体,由于“Times New Roman”无法作用中文字体,所以中文字体是“微软雅黑”
(大多数浏览器都支持微软雅黑,也比较好看)

在同一个文件中继续修改标题的字体。
font-title = "Lato",修改为font-title = "Times New Roman",。因为Lato这个字体有很多弊端。顺便将下面的@import url("//fonts.googleapis.com/css?family=Lato:400,400italic")删除。

添加友情链接的标签

编写一个widget

由于Light主题中没有自带这个widget. 所以我们需要自己写一个。
路径:\themes\hexo-theme-light-master\layout\_widget
在这个文件夹中创建一个文本文件,改成blogroll.ejs
打开文件,将一下代码复制进去:

1
2
3
4
5
6
<div class="widget tag">
<h3 class="title">友情链接</h3>
<ul class="entry">
<li><a href="http://blog.csdn.net/nezar" title="Nezar" target="_blank">CSDN</a></li>
</ul>
</div>

当然这里的链接部分可以自己修改(href后带链接 title表示鼠标悬停时显示文字 target="_blank"表示在新窗口打开链接 a标签中间则是链接显示的文字)

把标签添加到博客里去

路径:\themes\hexo-theme-light-master\_config.yml
找到 widgets: 在下面添加 - blogroll-后要加一个空格)
各类widget的顺序与博客上的显示上下位置有关

删除一二级标题下的横线

Light这个主题有一点我超级不喜欢,就是一二级标题下面的横线。于是我就把它删掉了。当然你们觉得无所谓的话可以留着。
路径:\themes\hexo-theme-light-master\source\css\_partial\article.styl
使用ctrl+f找到h1 然后把border-bottom 1px solid color-border这一行删掉。线就消失了。
我的话还把下一行的10px改成了0px. 因为感觉空得太多不太美观。

主标题下方加分割线

加上线以便区分标题正文
路径跟上一步一致:\themes\hexo-theme-light-master\source\css\_partial\article.styl
使用ctrl+f找到header 然后稍微往下拉一点,找到.titlefont-weight normal下加两行代码

1
2
padding-bottom 15px
border-bottom: 4px solid color-border

其中border-bottom:后的像素数据可以控制线的粗细

设置多层分类

如果要想博客写的有条理。博客中的每篇文章都应该有它的分类。一个大类里面还应该有多个小类。即为多层分类。
Light主题中自带的分类只有单层的。无法表示出层次感。这里我也给一个链接 Hexo主题中实现多级分类
大家可以按照这篇文章,设计自己的分类效果。

添加Latex公式效果

技术类的博客肯定少不了公式的,所以安装上Latex还是很有必要的。
搭建一个支持LaTEX的hexo博客
(记得如果是用的上面文章中的淘宝镜像。npm 记得改成 cnpm

暂时先这样,接下来的部分下次更新..