查漏補缺

1.sqrt 在math庫
2.計算年月日，計算時間就是進位問題吧，用算法解決問題也是蠻有趣的的哈
3.數(shù)據(jù)合法無處不在，有時候會很善意的告訴你
4.題目要求是不是多組輸入？
5.位數(shù)不等于被10整除數(shù)值，【17，兩位，一個零（10）表示兩位數(shù)
6.PE錯誤 presentation error
7.輸出結(jié)果是否為正整數(shù)？要不要0？被用例卡了一次
8.總感覺我這算法學的不系統(tǒng)，不牢固。
12.結(jié)構(gòu)體用起來真的感覺書寫麻煩頭大，盡量簡化代碼量
13.用double做結(jié)果小數(shù)點后好多位總出精度問題，float就不會，為啥？？？？？？保存整數(shù)我們不能使用double這類的浮點型，因為，double在存儲數(shù)據(jù)并不是整的，比如存儲0，double實際存儲為0.00000001，這就導致了我們使用浮點型計算出來的有誤差！
14.藍橋杯整理的筆記還需要細細打磨，都是考研抄作各家博主《作業(yè)》的成果
15.for(int i=n; i<2*m-n; i++) 每次取n，i范圍[0,2*m),i的終止條件是？取特值，n=0時，一目了然
16.打印一個菱形？？螺旋矩陣。。。這些圖形的，我弱爆了。
17.基礎漏洞太多了，很多數(shù)學基本常識還有些基本推算都如何實現(xiàn)都不記得了。
18.用注釋把一些未實現(xiàn)的功能寫在合適的位置，思路清晰了不少，不確定的數(shù)據(jù)用問號表示，少了不少干擾
19.字符串要想讀空格只能整行讀取
20. 0經(jīng)?？梢宰鳛橐粋€特殊樣例卡住你不讓你AC，比如遇到過的進制轉(zhuǎn)換，計算小數(shù)點后幾位都容易忽略0
21.字符串處理函數(shù)，stl容器函數(shù)，數(shù)值處理函數(shù)掌握不好，很多函數(shù)的使用都有問題。
22.之所以判定乒乓球是中等題，應該就是需要看懂繁瑣的規(guī)則，模擬出來相對麻煩一點 
23.給容器vector、string排序和數(shù)組首地址加長度是行不通的，需要用begin和end。   
24.reverse函數(shù)的頭文件是？
25.判斷素數(shù)容易手誤，可疑因數(shù)容易寫死 %i 寫成 %2。
26.《結(jié)構(gòu)體問題》寫代碼是真的冗長，《字符串問題》處理起來是真的有很多基礎思路要積累，很多基本函數(shù)要記得非常熟悉。 
27.結(jié)構(gòu)體最常用的用途就是結(jié)構(gòu)體排序（捆綁數(shù)據(jù)，甚至按指定序列要求輸出），有些輸出順序是在離譜，無法循環(huán)輸出，用結(jié)構(gòu)體捆綁數(shù)值后，排序就可以循環(huán)輸出。
28.簡單題，模板題；中等題，題意得多讀幾遍，代碼長點；難題，有特殊情況考慮不全/沒思路/代碼長。
29.矩陣的0次冪是單位矩陣E   
30.進階題，就是算法題，特點是會手算，數(shù)量規(guī)模大了就算漏了，代碼實現(xiàn)起來思路不清晰。
31.懂了，dfs 最基礎的，是走通一條路，   若要搜索所有情況，就要標記，回溯時解除標記
32.有時候程序會崩潰返回-1內(nèi)存泄漏？為啥重新執(zhí)行有時又沒問題？數(shù)組訪問越界，訪問m[2007],2007未指定，會導致這種執(zhí)行的不穩(wěn)定。
33.寫日歷題的時候，為啥有的月有錯誤？相鄰的月沒錯？年循環(huán)中，數(shù)組下標寫死了，一年的二月直接影響了之后的每月周1-周7的分布規(guī)律，會導致有的樣例對，有的就不對。，所以出現(xiàn)跨過一年12月開始出問題。
34.東華oj存在樣例每個數(shù)據(jù)后面都有空格，比如寫日歷，還比如根本看不出來的PE錯誤（41 盾神與條狀項鏈），就是每個元素后面都有空格，就是行末元素我習慣是去掉空格
35.每題要提交3-4才AC？永遠猜不到oj不給展示的樣例有多變態(tài)，多健全，而標程上的有多么理想，搞得我三番五次改bug。
36.dfs題目總是超時。。。暴力不動。
37.沒說多組輸入，卡我的一個樣例文件竟然設計成多組輸入。就算是不強調(diào)多組輸入，改成多組輸入，也AC。
38.大數(shù)乘法我會用char a b c，但是這樣10-99我做乘法，做進位都沒法搞啊，所以說我應該用int存 a b c，和處理
39.CodeBlocks紅點之間調(diào)試，可以反復橫跳，爽。
40.我發(fā)現(xiàn),對Σ取余和對Σ每一項取模，最后再整體取模一樣，這樣過程值規(guī)模小。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%40 &&x%100）||x%4000

建議用嘴說說，，寫代碼時間一長腦子一漲，很容易碼錯，找了半天錯誤，和正確結(jié)果就差一天，不就是2月的問題嗎，不就是閏年判斷有問題嗎？？？

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

約瑟夫環(huán)

如何實現(xiàn)數(shù)組循環(huán)？

if(i>N) i=1;

這不比我取余還要再將0->1代碼簡潔的多。

終止條件？

while(cnt!=N) //因為要求N個人的出局順序，因此當cnt（用來統(tǒng)計已經(jīng)出局的人）未達到n時，需要循環(huán)不斷報數(shù) 

模板

#include<bits/stdc++.h>
using namespace std;
//用數(shù)組實現(xiàn)約瑟夫環(huán)問題
int a[110]={0};   //元素值為0表示未出局 
//i既代表數(shù)組的下標，也代表每個人的編號
//k是用來計數(shù)的，一旦k的值達到m，代表此人需要出局，并且k需要重新計數(shù)，這樣才能夠找出所有需要出局的人
//數(shù)組的0代表未出局的人，數(shù)組非0代表出局的人，未出局的人需要報數(shù)，出局的人不需要報數(shù) 
int main()
{
	int N,M;
	int cnt=0,i=0,k=0;  //cnt表示目前出局的人數(shù) 
	cin>>N>>M;  //表示總共有n人，數(shù)到數(shù)字m時出局 
	while(cnt!=N) //因為要求N個人的出局順序，因此當cnt（用來統(tǒng)計已經(jīng)出局的人）未達到n時，需要循環(huán)不斷報數(shù) 
	{
		i++;   //i是每個人的編號 
		if(i>N) i=1;  //這里需要特別注意：i的值是不斷累加的，一旦發(fā)現(xiàn)i的值>N，那么i需要重新從第1個人開始
		              //數(shù)組要從第一個元素重新開始一個一個往后判斷 
		if(a[i]==0)   //只有元素值為0的人 才需要報數(shù)，元素值為非0的代表已經(jīng)出局了，不用報數(shù) 
		{
			k++;
			if(k==M)     //代表已經(jīng)某個人已經(jīng)報了M這個數(shù)，需要出局 
			{
				a[i]=1;  //編號為i的這個人出局 
				cnt++;   //出局的人數(shù)+1 
				cout<<i<<" ";  //輸出出局的人的編號 
				k=0;   //清空k，讓下一個人重新從1開始報數(shù)   
			}
		}
	}
	return 0;
} 

回文整數(shù)

判定思路？

每次拿到一個余數(shù)都用來構(gòu)造新數(shù)，如果是回文數(shù)，那么新數(shù)應該等于原數(shù)

這個新數(shù)成為逆序數(shù)，123取反321,101取反101

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數(shù)據(jù)類型計算階乘，最多可以計算到12！

long long內(nèi)的最大階乘20!

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

思路一：循環(huán)從1到n連續(xù)相乘，每次乘完后判斷去除后面的0。避免數(shù)據(jù)過大，要對10000取余。

 for(int i=1; i<=n; i++)
    {
//      while(i%10 == 0)i/=10; 加上這一條，算不出結(jié)果，反而更費時間？？？
        s*=i;

        //dealing
        while(s%10 == 0)s/=10;
        s%=10000;//沒有這一步可能精度不夠了
    }
//s

思路二：尋找階乘里面有多少個5，然后再從階乘里消去同等數(shù)量的2，這樣就直接消去了所有的10，再把剩下的相乘即可。

鏈接

輸出格式

避免尾部多空格

第一種（老方法）

for(int i = 0;i < n;i++)
{
    if(i == 0)cout<<res[i];
    else cout<<" "<<res[i];
	
}
cout<<endl;

第二種（代碼更簡潔）

    for(i=0; i<n; i++)
    {
        if (i>0)cout<<" ";

       cout<<res;
    }

    cout<<endl;

輸入問題

讀完一行整數(shù)，緊接著要讀一整行字符串 要用到getchar() 吃掉整數(shù)后面的回車符，否則geline(cin,s)吃掉回車，未讀取到這行字符串。

例如 要求輸入T組字符串

int T;
cin>>T;
getchar();
while(T--)
{
    getline(cin,s);

}

沒有解釋輸入多少行確讓輸出如何去設計輸入輸出？

while（）定義輸入，循環(huán)外定義輸出，強制結(jié)束輸入就出結(jié)果了。

回形針輸出？

矩陣問題

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

對角線：i=j，i+j=n+1

主對角線，上下移動，i變大變小

副對角線，上下移動，i+j的和變大變小

素數(shù)問題

幾種判定？

①暴力循環(huán)[2,x-1]

②有一條 在2到n/2之間任取一個數(shù),如果n能被整除則不是素數(shù)，否則就是素數(shù)

③在2到sqrt(n)之間任取一個數(shù),如果n能被整除則不是素數(shù)，否則就是素數(shù)

素數(shù)區(qū)間問題經(jīng)常挖的坑？

坑死我了,再出錯我是??

若給定一個區(qū)間去判定，需要把區(qū)間內(nèi)可能存在的1剔除！

輸出問題

如何用C++實現(xiàn)保留X位小數(shù)？

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

頭文件是？

#include<iomanip>

fixed作用？

消除浮點數(shù)的科學計數(shù)法表示的結(jié)果1.23457e+07，得到12345678.000000

另外，

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

setw()作用？

占位

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

setfill()作用？

占位并填充

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

在C下輸出，如何實現(xiàn)左對齊？

printf("%-10.2f\n",res);//有負號就是左對齊

優(yōu)先級問題

坑死我了,再出錯我是??

下面兩個式子結(jié)果完全不同；取余必須先算！

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

總之一句話，取余運算如果參與復雜運算要帶括號先算。

循環(huán)問題

1.while 帶等號 會達到執(zhí)行次數(shù)，額外再執(zhí)行一次，如下所示：

while( ct < l2 && j < n)
{
    j++;
    ct++;
}

這種循環(huán)，終止條件只能是 ct = l2 || j=n 時，反過來，想實現(xiàn)ct 計數(shù)到 l2 結(jié)束，不帶等號，就應該寫while( ct < l2 )

2.還有一種循環(huán)：

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

它累加的最后一項是不是 a[n-1] ？ 看終止條件，j=n不滿足條件，所以是a[n-1]，符合初衷。

判斷分支

有一種不常見的錯誤：

連鎖反應

if(s == 'U')s='L';
if(s == 'D')s='R';
if(s == 'L')s='D';
if(s == 'R')s='U';
//這就更適合用else if

進制轉(zhuǎn)換

10進制轉(zhuǎn)2進制會爆棧？

會，比如判斷 2925 在2進制下是否是回文數(shù)時， 轉(zhuǎn) 2 進制這一步就爆了。

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 有時有效。

螺旋方陣

難以想象，看博客會的。

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--;
}

數(shù)字游戲

思路一：所有情況都考慮到，DFS搜一遍，怕數(shù)太大用string做了拼接，反而過程更簡潔，但，TLE

思路二：規(guī)律，用9補位，比較大小，利用補位結(jié)果排序（結(jié)構(gòu)體排序，便保存了原結(jié)果且有序了），若相同比較多出來的位置是真9的優(yōu)先。這里有個情況需要考慮，前綴同的情況 345 345543 也補位？看345999和345543？不對，顯然345543+345要更大，所以，前綴同的要看原來字符串相加減的情況更穩(wěn)妥。

思路二改進：不用補位了，就是字典序，“9”>“83742”，結(jié)構(gòu)體都省下了，再把前綴同的情況單獨比較結(jié)果。

小數(shù)問題

如何判斷無限循環(huán)小數(shù)和無限不循環(huán)？

將分數(shù)化為最簡分數(shù)后，分母的全部因數(shù)（除去1和其自身）沒有為2或5以外的數(shù)，則該分數(shù)就不是無限循環(huán)小數(shù)；否則為無限循環(huán)小數(shù)。

涉及到最簡分式，也就是要求分子分母最大公約數(shù)，常用輾轉(zhuǎn)相除法。

若無限循環(huán)，如何判斷循環(huán)節(jié)？

被除數(shù)除以除數(shù)的余數(shù)，記錄余數(shù)。(如果余數(shù)為0，說明數(shù)可以被除盡，即沒有循環(huán)節(jié))
在余數(shù)后面加個0（即余數(shù)乘以十），把乘以10 的余數(shù)當作新的被除數(shù)，除數(shù)不變，記錄余數(shù)并判斷余數(shù)是否出現(xiàn)過（出現(xiàn)即可停止，說明找到循環(huán)節(jié)）；不斷的循環(huán)1、2這個過程，直到余數(shù)重復出現(xiàn)；

八皇后問題

回溯算法的典型案例

太經(jīng)典了，后悔才做到

采用一維數(shù)組表示棋盤

忘了看這，講的很詳細

#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行 已經(jīng)存在了？
        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皇后問題

大數(shù)乘法

簡簡單單，輕輕松松

CSDN入口

提醒：

1.用大數(shù)乘法模擬每次×的過程，注意數(shù)據(jù)類型的運用，是string讀入，int a[],b[],c[999]={0}來計算。

衍生問題·大數(shù)階乘思路？

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

矩形面積交

這個思路我做夢都想不到，太妙了。

細節(jié)：給的是實數(shù)，不是整數(shù)

矩形面積交[藍橋杯]

最長上升子序列

非常經(jīng)典的dp問題，簡單的很。

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;

        }

    }
}

如何找到這個序列？

倒著找。

//最大上升子序列的 最后一個 元素下標為p；
//第一個 a[p]
for(int i=p; i>=0; i--)
{
    if(a[p]>a[i]&&dp[p]-1 == dp[i])
    {
		p=i;//a[p] 即為所求
    }
}

數(shù)字字符判斷

遇到過一個很坑的情況：

要實現(xiàn)將 1~k的撲克牌轉(zhuǎn)為 1-13 數(shù)值

//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;
    

}

問題出現(xiàn)在 10上面，它也是符合 if(x[0]>='1'&&x[0]<='9')return x[0]-'0';的！！

//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.分治法

分兩邊找的結(jié)果再于從中間向兩邊找的結(jié)果取最大（SDUT OJ上見過）

2.遞推法

如果要求他的最大連續(xù)子序列的和，假設max_sum[i]表示以第i個元素結(jié)尾的連續(xù)子序列的最大和，可以推出

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

利用此遞推法可解決最大子段和衍生問題-------最大子矩陣

藍橋杯最大子陣問題題解

上面題解有個bug，

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 之類簡單多了，而且循環(huán)條件完全可以不受p的影響。

list *p=head->next;
list *q=head;
while(p)
{

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

雙親表示法

終于懂了這個含義，第二個結(jié)構(gòu)體就是給第一個地數(shù)組形式重新定義了成了類型。

typedef struct PTNode{    //結(jié)點結(jié)構(gòu)
TElemType   data;  //結(jié)點數(shù)據(jù)域
	int parent;              //雙親位置
}PTNode;
typedef struct{              //樹結(jié)構(gòu)
	PTNode nodes[MAX_TREE_SIZE];    //結(jié)點數(shù)組
	int  r,n;                     //根節(jié)點的位置和結(jié)點數(shù)
}

字符串系列

字符串表達式

計算"3+ 4+ 5+6"，沒有括號。

思路不錯，關(guān)鍵兩點：

如何在得到數(shù)字的同時還能查看數(shù)字前的符號，同時還要合并最初無符號這個情況。

處理三種情況

#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 ="";//保留數(shù)前的符號是運算的關(guān)鍵
        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  ，同時也是最后一個元素是數(shù)字的情況
            else sum +=x;
        }
        cout<<sum<<endl;
    }
}

子串問題

如何找目標子串？

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

2.？

回文串問題

模板如下

int palindrome(string x)
{
  int len = x.size();
  stack<char>s;
  int i;
  for( i=0;i<len/2;i++)//強調(diào)一點
  {
      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開始，要左移一位，所以就相應的去掉了等號。

字符分割問題

單詞分割問題

測試數(shù)據(jù)僅占一行，每行包括許多個英語單詞和空格，單詞和單詞之間可能有多個空格，每行的長度不會超過1000個字符。

i like apple

簡單翻譯：

數(shù)據(jù)巨長，所以數(shù)據(jù)類型是字符串，由字母空格組成，空格起到間隔開的作用，我們要去處理每一個單詞。

常規(guī)思路：

遇到空格就處理一下空格前的那個單詞

這往往會存在什么問題呢？

最后一個單詞它很有可能后面沒有空格，也就沒有處理，這也就是以單詞結(jié)尾的情況。

我的解決：

string s ;
geline(cin,s);
s  = s+" ";//給它最后整上一個空格，確保所有數(shù)據(jù)都處理到，

數(shù)字分割問題

空格分隔讀取字符串中的每個數(shù)，其中空格用5表示。

2343251231795

常規(guī)思路遇見所謂的‘空格’將前面累計的值保存，執(zhí)行累計的變量再次初始化。

要考慮到三種特殊情況：

①結(jié)尾沒有空格：最后一組漏了，末尾人為加上空格【人為補上一個終止符】，但要注意判斷有空格結(jié)尾的不要加了，會多存一次初始值。

②開頭就是空格的，甚至連續(xù)多個：會導致多存入幾個不存在的初始值0（和真實的數(shù)字零區(qū)分不開），特點是沒碰過數(shù)，判斷遇到空格前是否遇到過數(shù)即可。

③中間連續(xù)空格：判斷上一個是不是也是空格即可避免多存入0。

//normal
1525
//結(jié)合三種情況的
55512550

若想不起來思路，從完成一個常規(guī)判斷慢慢豐富這幾種情況的判斷即可。

找最長回文串

專門求解最長回文子串的算法：Manacher算法

高質(zhì)量題

繁殖問題

作者: 孫辭海 時間限制: 1S章節(jié): 一維數(shù)組

問題描述 :

有一家生化所，一月份引入一對新生的小白鼠。這對小白鼠生長兩個月后，在第三、第四、第五個月各繁殖一對新小白鼠，在第六個月停止繁殖，在第七個月則死亡。新生的小白鼠也如此繁殖。問在第N個月時，活的小白鼠有多少對？

輸入說明 :

你的程序需要從標準輸入設備（通常為鍵盤）中讀入多組測試數(shù)據(jù)。每組輸入數(shù)據(jù)由一行組成，其中只有一個整數(shù)N（0 < N ≤ 50）。兩組輸入數(shù)據(jù)間無空行。

輸出說明 :

對于每組測試數(shù)據(jù)，你的程序需要向標準輸出設備（通常為啟動該程序的文本終端）輸出一行，其中只有一個整數(shù)，即第N個月時活的小白鼠有幾對，所有數(shù)據(jù)前后沒有多余的空行，兩組數(shù)據(jù)之間也沒有多余的空行。

輸入范例 :

輸出范例 :

思路打磨了很久，很有趣就記下來了。

#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 日落在星期一,星期二…星期日的次數(shù).這個測試從1900年1月1日到 1900+n-1年12月31日.n是一個非負數(shù)且不大于400.

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

輸入說明 :

一個整數(shù)n（1<= n <= 400）.

輸出說明 :

七個在一行且相分開的整數(shù),它們代表13日是星期六,星期日,星期一…星期五的次數(shù).

輸入范例 :

20

輸出范例 :

36 33 34 33 35 35 34

判斷本月13號星期幾，很細節(jié)，從1900.1.1星期一計算，每個月13號判斷思路：1900累計到上個月的天啊數(shù)加13再%7的結(jié)果，mon[13]保留mon[0]好處多多，1月的上個月一共0天合理，且也不會數(shù)組溢出，但1901年判斷出了問題，1901.1.13要判斷需要加上的不是0月天數(shù)，二是1900.12的31天，通用加上上個月，額外地，給跨年月加個補丁：

if(j == 1 && i >1900)total_days_from_last_month+=mon[12];//fixed

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個整數(shù)構(gòu)成圓環(huán)中，找出N個相鄰的數(shù)，使其和為最大或最小。

我的做法，感覺挺不錯的：

存兩遍data模擬成環(huán)的所有取值情況。

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

誤區(qū)

  for(int i=n; i<2*m; i++)
        {

            if(min_s+a[i]-a[i-n]<min_s)//這樣子min_s要是一直不更新，突然更新，除了兩端，中間部分都還停留在一開始的位置，沒有實現(xiàn)整個區(qū)間的平移，一旦實現(xiàn)，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 應該無條件變化，卡了好久，浪費時間，以此謹記

      for(int i=n; i<2*m; i++)
        {
            temp_s=temp_s+a[i]-a[i-n];//區(qū)間和，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的，而且總是只差一個，怎么回事呢？

注意循環(huán)結(jié)束條件，s1，s2，它們在循環(huán)中的任何一個位置都在變，完全可能在下一次while判斷條件前溢出，參見快排代碼的嚴謹性

#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;
}

連號區(qū)間數(shù)

思路太妙了

如果注意到排列這兩個字，本題思路就迎刃而解，排列說明每個數(shù)只出現(xiàn)一次，已知區(qū)間長度的情況下只要求區(qū)間里最值之差就可以判斷是不是連號區(qū)間。

C++連號區(qū)間枚舉

數(shù)字問題

無數(shù)題目，我TLE，麻了

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個一循環(huán)

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

    cout<<tot<<endl;
}

TLE了，我覺得還能搶救，我這里的思路，找規(guī)律

發(fā)現(xiàn)規(guī)律：東東報的數(shù)，每k個一循環(huán)。

發(fā)現(xiàn)環(huán)

關(guān)鍵點：

n比較大，用vector 存鄰接表

last_v 表示上一個頂點，防止回頭

last_v存在一個問題，第一個點位沒有回頭，找到回路后，會誤判第一個數(shù)自身是個回路，需要判斷l(xiāng)ast_v !=-1。

PE問題：其實末尾留了空格，選定樣例輸出內(nèi)容就可以發(fā)現(xiàn)。

#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);

}

拉馬車

又給我上了一課，老快排問題了。

**總結(jié)：**只要涉及對q1、q2容量改變操作，就要判定是在while條件下!q1.empty() && !q2.empty()執(zhí)行的。文章來源地址http://www.zghlxwxcb.cn/news/detail-595089.html

//錯誤示范
while(!q1.empty() && !q2.empty())
{
    
        v.push_back(q1.front());//!q1.empty() && !q2.empty()剛判斷完，沒問題，加上while條件再執(zhí)行更穩(wěn)妥。
        q1.pop();
    
    while(check("q1") && !q1.empty() && !q2.empty() )
    {

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

    }
   
        v.push_back(q2.front());//不能確定q1空了這種情況，導致q2贏了還要出一張牌，結(jié)果少了一個數(shù)?。?！
        q2.pop();
    
    while(check("q2") &&!q1.empty() && !q2.empty())
    {
        v.push_back(q2.front());
        q2.pop();
    }
    //K8XKA2A95A 27K5J5Q6K4
    //

}

//正確示范
while(!q1.empty() && !q2.empty())
{
    if(!q1.empty() && !q2.empty())//加上while條件再執(zhí)行更穩(wěn)妥
    {
        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條件再執(zhí)行更穩(wěn)妥
    {
        v.push_back(q2.front());
        q2.pop();
    }
    while(check("q2") &&!q1.empty() && !q2.empty())
    {
        v.push_back(q2.front());
        q2.pop();
    }
    //K8XKA2A95A 27K5J5Q6K4
    //

}

到了這里，關(guān)于2023復試——機試隨筆【c++】【考研】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！