2023研究生复试——机试随笔（CSDN已上传）

备研之旅
Word count: 8.1k   |   Reading time≈ 35 min

查漏补缺

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
1.sqrt 在math库
2.计算年月日，计算时间就是进位问题吧，用算法解决问题也是蛮有趣的的哈
3.数据合法无处不在，有时候会很善意的告诉你
4.题目要求是不是多组输入？
5.位数不等于被10整除数值，【17，两位，一个零（10）表示两位数
6.PE错误 presentation error
7.输出结果是否为正整数？要不要0？被用例卡了一次
8.总感觉我这算法学的不系统，不牢固。
12.结构体用起来真的感觉书写麻烦头大，尽量简化代码量
13.用double做结果小数点后好多位总出精度问题，float就不会，为啥？？？？？？保存整数我们不能使用double这类的浮点型，因为，double在存储数据并不是整的，比如存储0，double实际存储为0.00000001，这就导致了我们使用浮点型计算出来的有误差！
14.蓝桥杯整理的笔记还需要细细打磨，都是考研抄作各家博主《作业》的成果
15.for(int i=n; i<2*m-n; i++) 每次取n，i范围[0,2*m),i的终止条件是？取特值，n=0时，一目了然
16.打印一个菱形？？螺旋矩阵。。。这些图形的，我弱爆了。
17.基础漏洞太多了，很多数学基本常识还有些基本推算都如何实现都不记得了。
18.用注释把一些未实现的功能写在合适的位置，思路清晰了不少，不确定的数据用问号表示，少了不少干扰
19.字符串要想读空格只能整行读取
20. 0经常可以作为一个特殊样例卡住你不让你AC，比如遇到过的进制转换，计算小数点后几位都容易忽略0
21.字符串处理函数，stl容器函数，数值处理函数掌握不好，很多函数的使用都有问题。
22.之所以判定乒乓球是中等题，应该就是需要看懂繁琐的规则，模拟出来相对麻烦一点 
23.给容器vector、string排序和数组首地址加长度是行不通的，需要用begin和end。   
24.reverse函数的头文件是？
25.判断素数容易手误，可疑因数容易写死 %i 写成 %2。
26.《结构体问题》写代码是真的冗长，《字符串问题》处理起来是真的有很多基础思路要积累，很多基本函数要记得非常熟悉。 
27.结构体最常用的用途就是结构体排序（捆绑数据，甚至按指定序列要求输出），有些输出顺序是在离谱，无法循环输出，用结构体捆绑数值后，排序就可以循环输出。
28.简单题，模板题；中等题，题意得多读几遍，代码长点；难题，有特殊情况考虑不全/没思路/代码长。
29.矩阵的0次幂是单位矩阵E   
30.进阶题，就是算法题，特点是会手算，数量规模大了就算漏了，代码实现起来思路不清晰。
31.懂了，dfs 最基础的，是走通一条路，   若要搜索所有情况，就要标记，回溯时解除标记
32.有时候程序会崩溃返回-1内存泄漏？为啥重新执行有时又没问题？数组访问越界，访问m[2007],2007未指定，会导致这种执行的不稳定。
33.写日历题的时候，为啥有的月有错误？相邻的月没错？年循环中，数组下标写死了，一年的二月直接影响了之后的每月周1-周7的分布规律，会导致有的样例对，有的就不对。，所以出现跨过一年12月开始出问题。
34.东华oj存在样例每个数据后面都有空格，比如写日历，还比如根本看不出来的PE错误（41 盾神与条状项链），就是每个元素后面都有空格，就是行末元素我习惯是去掉空格
35.每题要提交3-4才AC？永远猜不到oj不给展示的样例有多变态，多健全，而标程上的有多么理想，搞得我三番五次改bug。
36.dfs题目总是超时。。。暴力不动。
37.没说多组输入，卡我的一个样例文件竟然设计成多组输入。就算是不强调多组输入，改成多组输入，也AC。
38.大数乘法我会用char a b c，但是这样10-99我做乘法，做进位都没法搞啊，所以说我应该用int存 a b c，和处理
39.CodeBlocks红点之间调试，可以反复横跳，爽。
40.我发现,对Σ取余和对Σ每一项取模，最后再整体取模一样，这样过程值规模小。s =a+b+c; s%mod = (a%mod + b%mod + c%mod)%mod
41.找出所有可能年份三部分不知道那个是年月日，可能要去重2029-02-02，2029-02-02
42.当map元素值为int类型或者常量时候，默认值为0

闰年问题

判定思路？

闰年是29 ，（x%4==0 &&x%100）||x%400==0

建议用嘴说说，，写代码时间一长脑子一涨，很容易码错，找了半天错误，和正确结果就差一天，不就是2月的问题吗，不就是闰年判断有问题吗？？？

能被4整除不能被100整除或能被400整除

约瑟夫环

如何实现数组循环？

1
if(i>N) i=1;

这不比我取余还要再将0->1代码简洁的多。

终止条件？

1
while(cnt!=N) //因为要求N个人的出局顺序，因此当cnt（用来统计已经出局的人）未达到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
#include<bits/stdc++.h>
using namespace std;
//用数组实现约瑟夫环问题
int a[110]={0};   //元素值为0表示未出局 
//i既代表数组的下标，也代表每个人的编号
//k是用来计数的，一旦k的值达到m，代表此人需要出局，并且k需要重新计数，这样才能够找出所有需要出局的人
//数组的0代表未出局的人，数组非0代表出局的人，未出局的人需要报数，出局的人不需要报数 
int main()
{
	int N,M;
	int cnt=0,i=0,k=0;  //cnt表示目前出局的人数 
	cin>>N>>M;  //表示总共有n人，数到数字m时出局 
	while(cnt!=N) //因为要求N个人的出局顺序，因此当cnt（用来统计已经出局的人）未达到n时，需要循环不断报数 
	{
		i++;   //i是每个人的编号 
		if(i>N) i=1;  //这里需要特别注意：i的值是不断累加的，一旦发现i的值>N，那么i需要重新从第1个人开始
		              //数组要从第一个元素重新开始一个一个往后判断 
		if(a[i]==0)   //只有元素值为0的人 才需要报数，元素值为非0的代表已经出局了，不用报数 
		{
			k++;
			if(k==M)     //代表已经某个人已经报了M这个数，需要出局 
			{
				a[i]=1;  //编号为i的这个人出局 
				cnt++;   //出局的人数+1 
				cout<<i<<" ";  //输出出局的人的编号 
				k=0;   //清空k，让下一个人重新从1开始报数   
			}
		}
	}
	return 0;
}

回文整数

判定思路？

每次拿到一个余数都用来构造新数，如果是回文数，那么新数应该等于原数

这个新数成为逆序数，123取反321,101取反101

1
2
3
4
5
6
7
8
9
10
11
12
13
int hw(int x)
{
    int temp =x,new_x=0;
    while(temp)
    {
        new_x=new_x*10+temp%10;
        temp/=10;

    }

    if(new_x == x)return 1;
    return 0;
}

阶乘问题

可暴力求解的范围？

用int数据类型计算阶乘，最多可以计算到12！

long long内的最大阶乘20!

求解阶乘末尾非零位思路？

思路一：循环从1到n连续相乘，每次乘完后判断去除后面的0。避免数据过大，要对10000取余。

1
2
3
4
5
6
7
8
9
10
 for(int i=1; i<=n; i++)
    {
//      while(i%10 == 0)i/=10; 加上这一条，算不出结果，反而更费时间？？？
        s*=i;

        //dealing
        while(s%10 == 0)s/=10;
        s%=10000;//没有这一步可能精度不够了
    }
//s

思路二：寻找阶乘里面有多少个5，然后再从阶乘里消去同等数量的2，这样就直接消去了所有的10，再把剩下的相乘即可。

链接

输出格式

避免尾部多空格

第一种（老方法）

1
2
3
4
5
6
7
for(int i = 0;i < n;i++)
{
    if(i == 0)cout<<res[i];
    else cout<<" "<<res[i];
	
}
cout<<endl;

第二种（代码更简洁）

1
2
3
4
5
6
7
8
for(i=0; i<n; i++)
{
    if (i>0)cout<<" ";

   cout<<res;
}

cout<<endl;

输入问题

读完一行整数，紧接着要读一整行字符串 要用到getchar() 吃掉整数后面的回车符，否则geline(cin,s)吃掉回车，未读取到这行字符串。

例如 要求输入T组字符串

1
2
3
4
5
6
7
8
int T;
cin>>T;
getchar();
while(T--)
{
    getline(cin,s);

}

没有解释输入多少行确让输出如何去设计输入输出？

while（）定义输入，循环外定义输出，强制结束输入就出结果了。

回形针输出？

矩阵问题

N*N的矩阵，左半部分，右半部分，上半部分，下半部分表示？

对角线：i=j，i+j=n+1

主对角线，上下移动，i变大变小

副对角线，上下移动，i+j的和变大变小

素数问题

几种判定？

①暴力循环[2,x-1]

②有一条 在2到n/2之间任取一个数,如果n能被整除则不是素数，否则就是素数

③在2到sqrt(n)之间任取一个数,如果n能被整除则不是素数，否则就是素数

素数区间问题经常挖的坑？

坑死我了,再出错我是🐖

若给定一个区间去判定，需要把区间内可能存在的1剔除！

输出问题

如何用C++实现保留X位小数？

1
cout<<fixed<<setprecision(x)<<endl;

头文件是？

1
#include<iomanip>

fixed作用？

消除浮点数的科学计数法表示的结果1.23457e+07，得到12345678.000000

另外，

1
2
cout<<fixed<<x<<endl;
cout<<y<<endl;//之后不用再打一遍fixed了

setw()作用？

占位

1
cout << setw(5) << 255 << endl;

setfill()作用？

占位并填充

1
cout<<setfill('0')<<setw(4)<<res<<endl;

在C下输出，如何实现左对齐？

1
printf("%-10.2f\n",res);//有负号就是左对齐

优先级问题

坑死我了,再出错我是🐖

下面两个式子结果完全不同；取余必须先算！ 

1
2
3
int res = x%1000/100 * x%10;
int res = (x%1000/100 )* (x%10);

总之一句话，取余运算如果参与复杂运算要带括号先算。

循环问题

1.while 带等号 会达到执行次数，额外再执行一次，如下所示：

1
2
3
4
5
while( ct < l2 && j < n)
{
    j++;
    ct++;
}

这种循环，终止条件只能是 ct = l2 || j=n 时，反过来，想实现ct 计数到 l2 结束，不带等号，就应该写while( ct < l2 )

2.还有一种循环：

1
2
3
4
5
while(j<n)
{
    s+=a[j++];
    if(s%11 == 0)ct++;
}

它累加的最后一项是不是 a[n-1] ？ 看终止条件，j=n不满足条件，所以是a[n-1]，符合初衷。

3.结束时候 循环因ct =0结束，所以ct=0吗？

1
2
3
4
while(ct--)
{
    ;
}

执行结束后发现是 ct=-1，我常常用 ct 做的是实现循环执行几次，并不关注ct的具体值，所以才忽视了循环结束仍要执行一次 ct–操作。——2023-07-19

判断分支

有一种不常见的错误：

连锁反应

1
2
3
4
5
if(s == 'U')s='L';
if(s == 'D')s='R';
if(s == 'L')s='D';
if(s == 'R')s='U';
//这就更适合用else if

空语句

比如有四类情况，第四类不要表达，所以表达另外三类，来间接实现对第四类的表达，但并不是都需要有些实际操作的，就用空语句，连作用域的括号都不要了，直接分号结束。——2023.07.18补充

1
2
3
4
5
6
7
8
9
10
if()
{
    
}
else if();
else if();
else
{
    
}

进制转换

10进制转2进制会爆栈？

会，比如判断 2925 在2进制下是否是回文数时， 转 2 进制这一步就爆了。

1
2result is: -1978114003                                                                                     3result is: 11000100                                                                                         4result is: 231231                                                                                         5result is: 43200                                                                                           6result is: 21313                                                                                           7result is: 11346                                                                                           8result is: 5555                                                                                             9result is: 4010

尝试用int处理改为 long long int 有时有效。

螺旋方阵

难以想象，看博客会的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int l=0,r=n-1;
int x =1;
while(l<=r)
{
    int i,j;
    for( j=l; j<=r; j++)
        a[l][j] = x++;
    for( i=l+1; i<=r; i++)
        a[i][r] = x++;
    for( j=r-1; j>=l; j--)
        a[r][j] = x++;
    for( i=r-1; i>=l+1; i--)
        a[i][l] = x++;

    l++;
    r--;
}

数字游戏

思路一：所有情况都考虑到，DFS搜一遍，怕数太大用string做了拼接，反而过程更简洁，但，TLE

思路二：规律，用9补位，比较大小，利用补位结果排序（结构体排序，便保存了原结果且有序了），若相同比较多出来的位置是真9的优先。这里有个情况需要考虑，前缀同的情况 345 345543 也补位？看345999和345543？不对，显然345543+345要更大，所以，前缀同的要看原来字符串相加减的情况更稳妥。

思路二改进：不用补位了，就是字典序，”9”>”83742”，结构体都省下了，再把前缀同的情况单独比较结果。

小数问题

如何判断无限循环小数和无限不循环？

将分数化为最简分数后，分母的全部因数（除去1和其自身）没有为2或5以外的数，则该分数就不是无限循环小数；否则为无限循环小数。

涉及到最简分式，也就是要求分子分母最大公约数，常用辗转相除法。

若无限循环，如何判断循环节？

被除数除以除数的余数，记录余数。(如果余数为0，说明数可以被除尽，即没有循环节)
在余数后面加个0（即余数乘以十），把乘以10 的余数当作新的被除数，除数不变，记录余数并判断余数是否出现过（出现即可停止，说明找到循环节）；不断的循环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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[11][11];
int chessW[11];//1维棋盘，键：值 表示 行：列
int chessB[11];
int ans;
int n;


bool check(int chess[],int row,int col)
{
    if(a[row][col] == 0)return false;//这个位置可不可以？
    for(int i=0; i<row; i++)
    {
        if(chess[i] == col)return false;//col列是否在0~row-1行 已经存在了？
        if(abs(chess[i]-col) == abs(i-row))return false;//是否存在对角线？
    }
    return true;
}



void B(int row)
{
    if(row == n)
    {
        ans++;
        return;
    }
    for(int j=0; j<n; j++)
    {
        if(check(chessB,row,j))
        {
            chessB[row] =j;
            B(row +1);
            chessB[row]=-1;
        }
    }
}

void W(int row)
{
    if(row == n)
    {
        B(0);
        return;
    }
    for(int j=0; j<n; j++)
    {
        if(check(chessW,row,j))
        {
            chessW[row] =j;
            a[row][j]=0;
            W(row +1);
            chessW[row]=-1;
            a[row][j]=1;
        }
    }
}


int main()
{

    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }

    //initial
    ans=0;
    for(int i=0; i<n; i++)
    {
        chessB[i] =-1;
        chessW[i] =-1;
    }

    W(0);
    cout<<ans<<endl;

}

衍生问题：

8皇后·改

2n皇后问题

大数乘法

简简单单，轻轻松松

CSDN入口

提醒：

1.用大数乘法模拟每次×的过程，注意数据类型的运用，是string读入，int a[],b[],c[999]={0}来计算。

衍生问题·大数阶乘思路？

500! 就是1000位了，c[999]不够，那就开c[9999]，AC了。

矩形面积交

这个思路我做梦都想不到，太妙了。

1
细节：给的是实数，不是整数

矩形面积交[蓝桥杯]

最长上升子序列

非常经典的dp问题，简单的很。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[];//list
int dp[];//最长长度

for(int i=1; i<n; i++)
{

    for(int j=0; j<i; j++)
    {

        if(a[i]>a[j] && dp[j]+1>dp[i])
        {
            dp[i]=dp[j]+1;

        }

    }
}

如何找到这个序列？

倒着找。

1
2
3
4
5
6
7
8
9
//最大上升子序列的 最后一个 元素下标为p；
//第一个 a[p]
for(int i=p; i>=0; i--)
{
    if(a[p]>a[i]&&dp[p]-1 == dp[i])
    {
		p=i;//a[p] 即为所求
    }
}

数字字符判断

遇到过一个很坑的情况：

要实现将 1~k的扑克牌转为 1-13 数值

1
2
3
4
5
6
7
8
9
10
11
//condition 1
int f(string x)
{
    if(x[0]>='1'&&x[0]<='9')return x[0]-'0';
    if(x == "10")return 10;
    if(x == "J")return 11;
    if(x == "Q")return 12;
    if(x == "K")return 13;
    

}

问题出现在 10上面，它也是符合 if(x[0]>='1'&&x[0]<='9')return x[0]-'0';的！！

1
2
3
4
5
6
7
8
9
10
//condition 2
int f(string x)
{
    if(x == "10")return 10;
    if(x == "J")return 11;
    if(x == "Q")return 12;
    if(x == "K")return 13;
    if(x[0]>='1'&&x[0]<='9')return x[0]-'0';

}

最大子序列和

1.分治法

分两边找的结果再于从中间向两边找的结果取最大（SDUT OJ上见过）

2.递推法

如果要求他的最大连续子序列的和，假设max_sum[i]表示以第i个元素结尾的连续子序列的最大和，可以推出

1
max_sum[i]=max(max_sum[i-1]+nums[i],nums[i]);

利用此递推法可解决最大子段和衍生问题——-最大子矩阵

蓝桥杯最大子阵问题题解

上面题解有个bug，

1
2
3
4
5
6
for(int k=1; k<m; k++)
{
 dp[k] =max(dp[k-1]+temp[k],temp[k]);
 if(dp[k] > res)res =dp[k];
}
if(dp[0]>res)res =dp[0];//文章思路非常对，代码中漏了对dp[0]的判断。

链表问题

很好的标记p指针的前一个位置，q作为p的延时残影，比p=q->next 之类简单多了，而且循环条件完全可以不受p的影响。

1
2
3
4
5
6
7
8
9
10
list *p=head->next;
list *q=head;
while(p)
{

    //deal p
    //next
    q=p;
    p=p->next;
}

双亲表示法

终于懂了这个含义，第二个结构体就是给第一个地数组形式重新定义了成了类型。

1
2
3
4
5
6
7
8
typedef struct PTNode{    //结点结构
TElemType   data;  //结点数据域
	int parent;              //双亲位置
}PTNode;
typedef struct{              //树结构
	PTNode nodes[MAX_TREE_SIZE];    //结点数组
	int  r,n;                     //根节点的位置和结点数
}

字符串系列

字符串表达式

计算”3+ 4+ 5+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
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    // read  whole row
    string s;
    while(getline(cin,s))
    {
        // delete blank
        while(s.find(" ") !=-1)
        {
            int p = s.find(" ");
            s.erase(p,1);

        }
        int sum =0;

        int x=0;
        string flag ="";//保留数前的符号是运算的关键
        for(int i=0; i<s.size(); i++)
        {
            // get number
            if(s[i]>='0' && s[i]<='9')x = x*10+ s[i]-'0';
            //calculate number by character , totally 3 conditions
            else
            {

                if(flag == "-")
                {
                    sum -=x;//  处理这种  1-2

                }
                else
                {
                    sum +=x;  //  处理这种 1+2  1
                }
                flag =s[i];
                x =0;
            }
        }
        if(x != 0)
        {
            if(flag == "-")sum -=x;  //处理单个符号的 -2  ，同时也是最后一个元素是数字的情况
            else sum +=x;
        }
        cout<<sum<<endl;
    }
}

子串问题

如何找目标子串？

1.暴力找全部，一一判断

2.？

回文串问题

模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int palindrome(string x)
{
  int len = x.size();
  stack<char>s;
  int i;
  for( i=0;i<len/2;i++)//强调一点
  {
      s.push(x[i]);
  }
  if(len%2 == 1) i++;
  for( i;i<len;i++)
  {
    if(s.top() != x[i])return 0;
        s.pop();

  }
  return 1;

}

为什么入栈终止条件是 i<len/2不带等号呢？

我解释一下，int 向下取整，所以 len/2 应该是最理想的左半截，但是从0开始，要左移一位，所以就相应的去掉了等号。

字符分割问题

单词分割问题

测试数据仅占一行，每行包括许多个英语单词和空格，单词和单词之间可能有多个空格，每行的长度不会超过1000个字符。

1
i like apple

简单翻译：

数据巨长，所以数据类型是字符串，由字母空格组成，空格起到间隔开的作用，我们要去处理每一个单词。

常规思路：

遇到空格就处理一下空格前的那个单词

这往往会存在什么问题呢？

最后一个单词它很有可能后面没有空格，也就没有处理，这也就是以单词结尾的情况。

我的解决：

1
2
3
string s ;
geline(cin,s);
s  = s+" ";//给它最后整上一个空格，确保所有数据都处理到，

数字分割问题

空格分隔读取字符串中的每个数，其中空格用5表示。

1
2343251231795

常规思路遇见所谓的‘空格’将前面累计的值保存，执行累计的变量再次初始化。

要考虑到三种特殊情况：

①结尾没有空格：最后一组漏了，末尾人为加上空格【人为补上一个终止符】，但要注意判断有空格结尾的不要加了，会多存一次初始值。

②开头就是空格的，甚至连续多个：会导致多存入几个不存在的初始值0（和真实的数字零区分不开），特点是没碰过数，判断遇到空格前是否遇到过数即可。

③中间连续空格：判断上一个是不是也是空格即可避免多存入0。

1
2
3
4
//normal
1525
//结合三种情况的
55512550

若想不起来思路，从完成一个常规判断慢慢丰富这几种情况的判断即可。

找最长回文串

专门求解最长回文子串的算法：Manacher算法

高质量题

繁殖问题

作者: 孙辞海 时间限制: 1S章节: 一维数组

问题描述 :

有一家生化所，一月份引入一对新生的小白鼠。这对小白鼠生长两个月后，在第三、第四、第五个月各繁殖一对新小白鼠，在第六个月停止繁殖，在第七个月则死亡。新生的小白鼠也如此繁殖。问在第N个月时，活的小白鼠有多少对？

输入说明 :

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组输入数据由一行组成，其中只有一个整数N（0 < N ≤ 50）。两组输入数据间无空行。

输出说明 :

对于每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的文本终端）输出一行，其中只有一个整数，即第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
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
    int x;
    while(cin>>x)
    {
        int s=0;
        int m[8];
        memset(m,0,sizeof(m));

        for(int i=1; i<=x; i++)
        {
            //come to i month
            m[7]=m[6];
            m[6]=m[5];
            m[5]=m[4];
            m[4]=m[3];
            m[3]=m[2];
            m[2]=m[1];
            m[1]=m[0];

            if(i == 1) //initial
            {
                m[1]=1;
            }
            //happen
            if(m[3])m[1]+=m[3];
            if(m[4])m[1]+=m[4];
            if(m[5])m[1]+=m[5];
            if(m[7])m[7]=0;

//            for(int j=1;j<=7;j++)
//                cout<<m[j]<<" ";
//            cout<<endl;

        }
        for(int i=1; i<=7; i++)s+=m[i];
        cout<<s<<endl;
    }


}

黑色星期五

问题描述 :

13号又是星期五是一个不寻常的日子吗? 13号在星期五比在其他日少吗?为了回答这个问题,写一个程序来计算在n年里13 日落在星期一,星期二……星期日的次数.这个测试从1900年1月1日到 1900+n-1年12月31日.n是一个非负数且不大于400.

这里有一些你要知道的: 1900年1月1日是星期一. 4,6,11和9月有30天.其他月份除了2月都有31天.闰年2月有29天,平年2月有28天.

输入说明 :

一个整数n（1<= n <= 400）.

输出说明 :

七个在一行且相分开的整数,它们代表13日是星期六,星期日,星期一…..星期五的次数.

输入范例 :

20

输出范例 :

36 33 34 33 35 35 34

判断本月13号星期几，很细节，从1900.1.1星期一计算，每个月13号判断思路：1900累计到上个月的天啊数加13再%7的结果，mon[13]保留mon[0]好处多多，1月的上个月一共0天合理，且也不会数组溢出，但1901年判断出了问题，1901.1.13要判断需要加上的不是0月天数，二是1900.12的31天，通用加上上个月，额外地，给跨年月加个补丁：

1
if(j == 1 && i >1900)total_days_from_last_month+=mon[12];//fixed
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
int mon[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};


    int n;
    cin>>n;
    int total_days_from_last_month=0;
    int week[7]= {0}; //7(0) 1 2 3 4 5 6


    for(int i=1900; i<=1900+n-1; i++)
    {
        for(int j=1; j<=12; j++)
        {
            if(j == 2 && if_leap_year(i)) mon[2]=29;
            if(j == 2 && !if_leap_year(i)) mon[2]=28;
            //last +..+last month +13
            total_days_from_last_month+=mon[j-1];//last year 12 month dismiss?
            if(j == 1 && i >1900)total_days_from_last_month+=mon[12];//fixed
            int w=(total_days_from_last_month+13)%7;
            week[w]++;


        }


    }

最大与最小

在一个由M个整数构成圆环中，找出N个相邻的数，使其和为最大或最小。

我的做法，感觉挺不错的：

存两遍data模拟成环的所有取值情况。

1
2
3
4
5
for(int i=0; i<m; i++)// data size = m
        {
            cin>>a[i];
            a[i+m]=a[i];//double storage to imitate a circle
        }

误区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=n; i<2*m; i++)
      {

          if(min_s+a[i]-a[i-n]<min_s)//这样子min_s要是一直不更新，突然更新，除了两端，中间部分都还停留在一开始的位置，没有实现整个区间的平移，一旦实现，min将会破坏，所以另起炉灶不能平移min。
          {
              cout<<a[i]<<" "<<a[i-n]<<" "<<min_s+a[i]-a[i-n]<<" "<<min_s<<endl;
              min_s = min_s+a[i]-a[i-n];

          }
          if(max_s+a[i]-a[i-n]>max_s)
          {
              max_s = max_s+a[i]-a[i-n];

          }

      }

正确做法

没有意识到temp_s 应该无条件变化，卡了好久，浪费时间，以此谨记

1
2
3
4
5
6
7
8
9
10
for(int i=n; i<2*m; i++)
  {
      temp_s=temp_s+a[i]-a[i-n];//区间和，temp_s,只要移动就一定要change
      if(temp_s<min_s) min_s = temp_s;
      if(temp_s>max_s) max_s = temp_s;

  }
  cout<<"Max="<<max_s<<endl;
  cout<<"Min="<<min_s<<endl;
  cout<<endl;

龟兔赛跑预测

给我狠狠地上了一课，这样应该全过，但是有wa的，而且总是只差一个，怎么回事呢？

注意循环结束条件，s1，s2，它们在循环中的任何一个位置都在变，完全可能在下一次while判断条件前溢出，参见快排代码的严谨性

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
43
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
    //v1，v2，t，s，l，
    int v1,v2,t,s,l;
    cin>>v1>>v2>>t>>s>>l;

    int T=0;
    int s1=0,s2=0;
    while(s1<l && s2<l)
    {

        T++;
        s1 +=v1;
        s2 +=v2;

        if(s1<l && s2<l &&s1-s2>=t)//s1<l && s2<l ？
        {

            int temp =s;
            while( s1<l && s2<l && temp--)//s1<l && s2<l ？
            {
                T++;
                s2+=v2;
            }
        }


    }
    if(s1 > s2)cout<<"R"<<endl;
    else if(s1 < s2)cout<<"T"<<endl;
    else cout<<"D"<<endl;
    cout<<T<<endl;
}

连号区间数

思路太妙了

如果注意到排列这两个字，本题思路就迎刃而解，排列说明每个数只出现一次，已知区间长度的情况下只要求区间里最值之差就可以判断是不是连号区间。

C++连号区间枚举

数字问题

无数题目，我TLE，麻了

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
int main()
{
    int n,k,t;
    cin>>n>>k>>t;

    int i=0;
    int id=1;
    int tot=0;
    int ct=0;
    int ans =1;
    while(ct!=t)
    {
        ans =ans +i;
        ans%=k;// k=13个一循环

        if(id == 1)
        {
            tot+=ans;
            ct++;
            cout<<ans<<endl;
        }
        //next
        id++;
        if(id >n)id=1;
        i++;
        i%=k;
    }

    cout<<tot<<endl;
}

TLE了，我觉得还能抢救，我这里的思路，找规律

发现规律：东东报的数，每k个一循环。

发现环

关键点：

n比较大，用vector 存邻接表

last_v 表示上一个顶点，防止回头

last_v存在一个问题，第一个点位没有回头，找到回路后，会误判第一个数自身是个回路，需要判断last_v !=-1。

PE问题：其实末尾留了空格，选定样例输出内容就可以发现。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;





vector<int>mp[100010];
int vis[100010];
int ff;



void print(vector<int> ans)
{
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
    {
//        if(i>0)cout<<" ";
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
void dfs(int v,int las_v,vector<int>ans)
{
    if(ff)return;
    vis[v]=1;
    ans.push_back(v);
    for(int i=0;i<mp[v].size();i++)
    {
        if(las_v != -1 &&mp[v][i] !=las_v && vis[mp[v][i]] == 1){print(ans);ff=1;return;}
        if(vis[mp[v][i]] == 0)dfs(mp[v][i],v,ans);
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    //pre
    vector <int>ans;
    memset(vis,0,sizeof(vis));
    ff=0;
    //deal
    dfs(1,-1,ans);

}

拉马车

又给我上了一课，老快排问题了。

总结：只要涉及对q1、q2容量改变操作，就要判定是在while条件下!q1.empty() && !q2.empty()执行的。

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
//错误示范
while(!q1.empty() && !q2.empty())
{
    
        v.push_back(q1.front());//!q1.empty() && !q2.empty()刚判断完，没问题，加上while条件再执行更稳妥。
        q1.pop();
    
    while(check("q1") && !q1.empty() && !q2.empty() )
    {

        v.push_back(q1.front());
        q1.pop();

    }
   
        v.push_back(q2.front());//不能确定q1空了这种情况，导致q2赢了还要出一张牌，结果少了一个数！！！
        q2.pop();
    
    while(check("q2") &&!q1.empty() && !q2.empty())
    {
        v.push_back(q2.front());
        q2.pop();
    }
    //K8XKA2A95A 27K5J5Q6K4
    //

}
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
//正确示范
while(!q1.empty() && !q2.empty())
{
    if(!q1.empty() && !q2.empty())//加上while条件再执行更稳妥
    {
        v.push_back(q1.front());
        q1.pop();
    }
    while(check("q1") && !q1.empty() && !q2.empty() )
    {

        v.push_back(q1.front());
        q1.pop();

    }
    if( !q1.empty() && !q2.empty())//加上while条件再执行更稳妥
    {
        v.push_back(q2.front());
        q2.pop();
    }
    while(check("q2") &&!q1.empty() && !q2.empty())
    {
        v.push_back(q2.front());
        q2.pop();
    }
    //K8XKA2A95A 27K5J5Q6K4
    //

}
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2023 cold
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信