2020-1-18學習總結

今天是放假在家打卡學習的第一天，
早上8:30簽到打卡，
8:50——12:00學習演算法（大數相加，快速冪，部分背包貪心策略，博弈基礎之巴什博弈）
14:00——18:00刷題，
晚上歸納總結，

大數相加的思路是以模擬算術的加法進位程序，在這里我們運用了陣列來依次存放每一位字符，首先將字符每一位翻轉，因為我們是從低位算起，所以需要將低位放在陣列頭部，在計算程序中也需要用一個臨時變數來控制每一位的進位，再回圈結束過后還需要對進位的變數判斷，如果進位不是1的話還要在后面進位，

  len1=strlen(str1);
    len2=strlen(str2);
    for(i=0; i<len1; i++)
        ans1[i]=str1[len1-i-1]-'0';//對字串進行翻轉
    for(i=0; i<len2; i++)
        ans2[i]=str2[len2-i-1]-'0';

 for(i=0; i<len1||i<len2; i++)
    {
        sum[i]=(ans1[i]+ans2[i]+t)%10;//每位剩下的數
        t=(ans1[i]+ans2[i]+t)/10;//取進位
    }
    if(t)//判斷是否還有進位
        sum[i++]=t;//有進位的話還需進位
        sum[i]='\0';

快速冪是應用在我們平時求取高次方冪的精簡版
一般的是對冪進行回圈遍歷，這樣時間復雜度相對而言會高一點為0(N)，
而快速冪的話是以二進制的位權來簡化時間復雜度，（將底數放大，將指數縮小）

void main()
{   int a,b;
scanf("%d%d",&a,&b);
    int ans=1;
    while(b)
    {
        if(b&1)//按位運算相當于b%2!=0
            {ans*=a;}
           a*=a;
           b>>=1;//位運算右移相當于除以2
    }
    printf("%d",ans);
}

部分背包策略我就結合今天刷題組的一道題來理解，主要是運用貪心策略，看題：
問題 H: Home Work
描述
臨近開學了，大家都忙著收拾行李準備返校，但I_Love_C卻不為此擔心! 因為他的心思全在暑假作業上：目前為止還未開動(-_-!!還以為他有多冷靜呢)，
暑假作業是很多張試卷，我們這些從試卷里爬出來的人都知道，卷子上的題目有選擇題、填空題、簡答題、證明題等， 而做選擇題的好處就在于作業量很少，但又因為選擇題題目都普遍很長， 如果有5張試卷，其中4張是選擇題，最后一張是填空題，很明顯做最后一張所花的時間要比前4張長很多， 但如果你只做了選擇題，雖然作業量很少，但表面上看起來也已經做了4/5的作業了， I_Love_C決定就用這樣的方法來蒙混過關，
他統計出了做完每一張試卷所需的時間以及它做完后能得到的價值（按上面的原理，選擇題越多價值當然就越高咯）， 現在就請你幫他安排一下，用他僅剩的一點時間來做最有價值的作業，

格式
輸入格式
測驗資料包括多組， 每組測驗資料以兩個整數M，N(1≤M≤20, 1≤N≤10000)開頭，分別表示試卷的數目和I_Love_C剩下的時間， 接下來有M行，每行包括兩個整數T，V(1≤T≤N,0<V<10000)，分別表示做完這張試卷所需的時間以及做完后能得到的價值！ 輸入以0 0結束，寫試卷的時間可能為0!!!

輸出格式
對應每組測驗資料輸出I_Love_C能獲得的最大價值，
保留小數點2位

樣例
樣例輸入 Copy
4 20
4 10
5 22
10 3
1 2
0 0
樣例輸出 Copy
37.00
提示
float的精度可能不夠， 你應該使用double型別，
對平均價值進行降序排序，先取價值高的，代碼如下

#include <stdio.h>
#include <string.h>
struct node
{
    double a[3];

};
int main()
{
    int i,j,n,k;
    double s,m;
    struct node arr[1000],t;
    while(~scanf("%d%lf",&n,&s))
    {
        if(n==0&&s==0)
            break;
        memset(arr,0,sizeof(arr));//對記憶體進行重置
        m=0;
        for(i=0; i<n; i++)
        {
            scanf("%lf%lf",&arr[i].a[0],&arr[i].a[1]);
            if(arr[i].a[0]==0)//題目說過寫題可能為0，但因為除數不能為0
            所以我進行了單獨處理
                arr[i].a[2]=arr[i].a[1];
            else
                arr[i].a[2]=arr[i].a[1]/arr[i].a[0];
        }
        for(i=0; i<n-1; i++)//冒泡降序排序，關鍵字為平均價值
            for(j=0; j<n-1-i; j++)
                if(arr[j].a[2]<arr[j+1].a[2])
                {
                    t=arr[j],arr[j]=arr[j+1],arr[j+1]=t;
                }
        i=0;
        while(s)//對價值進行累加，因為是可以進行部分取的
        {
            if(s>=arr[i].a[0])
            {
                s-=arr[i].a[0];
                m+=arr[i].a[1];
            }
            else
            {
                m+=arr[i].a[2]*s;
                s=0;
                break;

            }
            i++;
        }

        printf("%.2lf\n",m);//保留兩位小數

    }

}

在刷題題組中運用了博弈基礎——巴什博弈
看題
問題 E: 刷題的兄弟倆
描述
眾所周知，lbg和gbl是一對兄弟，他們時常位居刷題榜前列，為了贏得學妹的芳心
他們決定進行一場刷題比賽，他們找來了1000000000000000道題，比賽的規則是
1、一道題只能歸一個人所有（這題被gbl過了，lbg就接著往后刷）；
2、從第一題開始往后刷；
3、誰先刷完最后一題誰就贏了；
4、只有一臺機子，每次只能有一個人上機；
5、一次上機刷超過 m (1<=m<=100) 道題會被系統判定為舞弊；
因為lbg和gbl都很聰明，所以每次上機都不會舞弊，而且所有的題他們都會做，
這時比賽已經進行到了晚上就要斷網了，還剩 n （0<n<1000000）道題，
假設lbg先上機，請問誰能獲得小學妹的芳心？

格式
輸入格式
輸入資料首先包含一個正整數T，表示包含T組測驗用例，然后是T行資料，每行包含兩個正整數n，m，n和m的含義參見上面提到的規則，

輸出格式
對于每組測驗資料，如果lbg能獲得小學妹的芳心，請輸出字串"lbg"， 如果gbl能獲得小學妹的芳心，請輸出字串"gbl"，每個實體的輸出占一行，

樣例
樣例輸入 Copy
2
8 10
11 10
樣例輸出 Copy
lbg
gbl
這道題算是巴什博弈的模板題把，
因為每次做題的數不超過m道，也就是說每個人每次做題數目都在1至m,所以如果題目數2*m>n>=m+1，也就說明先手必輸，因為先手只能拿1~m,后手就可以拿剩下的n-(m)，必定是在1—m內的，所以后手必贏，同樣如果n是m+1的倍數拿必定可以變成m+1.所以我們只需判斷如果是m+1的倍數那必定是后手贏，代碼如下：

#include <stdio.h>
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n%(m+1)==0)
            printf("gbl\n");
        else
            printf("lbg\n");
    }

}

愿每天都能過的充實，加油大氣層！！！！！