day03:字符串&位運算&快速冪

字符串
什么是字符，什么有又是字符串?

字符一般是指單個字符，用單引號括起來的字符
字符串是指多個字符的集合，用雙引號括起來

一般我們存儲字符串有兩種方式:
一個是字符數組char s[N], char s[N][N];
一個是字符串類型：string s;

字符數組的輸入輸出：

int main(){
    const int N=10; char a[N];
    for(int i=0; i<N; i++){
        a[i] = getchar();//scanf("%c", &a[i]);//'\n'也會讀入
    }
    for(int i=0; i<N; i++){
        putchar(a[i]); //printf("%c", a[i]);
    }
    return 0;
}

或者這樣輸入輸出

gets(a); //scanf("%s", &a);
puts(a); //printf("%s", a);

但是string類型的輸入輸出就方便多了

string s; 
cin>>s;//string類型的輸入
cout<<s;//string類型的輸出
for(int i=0; i<s.length(); i++){
    cout<<s[i];//string類型的輸出
}

C語言中字符串封裝的一些函數方法

//比較兩個字符串的內容是否相等
int strcmp(const char str1,const char str2);

//比較兩個字符串前n個字符是否完全一致
int strncmp(const char str1,const char str2,size_t n);

//查找指定字符在指定字符串中第一次出現的位置
char* strchr(const char* str, char c);

//查找指定字符在指定字符串中最后一次出現的位置
char* strrchr(const char*str, char c);

//在字符串中搜索是否包含一個子字符串
char* strstr(const charhaystack, const char needle);

//將指針src指向的字符串連接到指針dest指向的字符串后面
char* strcat(char* dest, const char* src);

//從src指向的字符串中取不超過n個字符連接到dest指向的字符串后面
char* strncat(char* dest, const char* src,size_t n);

//字符串指針src所指向的字符串將被復制到dest所指向的字符串中。
char* strcpy(char* dest, const char* src);

//取字符串長度函數，不含'\0'
int strlen(char* str);

//大小寫轉換
strupr(char* str);
strlwr(char* str);

string類的一些方法
append() 	– 在字符串的末尾添加字符
find() 		– 在字符串中查找字符串
insert()	– 插入字符
length() 	– 返回字符串的長度
replace() 	– 替換字符串
substr() 	– 返回某個子字符串

#include<iostream>
using namespace std;
int main() {
    string s="12345678901234567890"; 
    cout<<s<<endl;//12345678901234567890

    s.append("a");
    cout<<s<<endl;//12345678901234567890a
    cout<<s.find("0")<<endl;// 9

    s.insert(0, "b");
    cout<<s<<endl;//b12345678901234567890a
    cout<<s.length()<<endl;//22

    s.replace(0, 2, "a");
    cout<<s<<endl;//a2345678901234567890a
    cout<<s.substr(0,10)<<endl;//a234567890
    return 0;
}

位運算
學習位運算前，需要掌握二進制，那么我們這里就將進制轉換在復習一下

二進制：1001B  = 8+1 =9D
八進制：1005O  = 1*8^3+5*8^0=8^3+5
十進制：1289D  = 1289D
十六進制：0x119f = 1*16^3+1*16^2+9*16^1 +15*16^0

計算公式：結果 = sum(基數*位數權重)

&: 按位與，同真為真，其余為假
|: 按位或，同假為假，其余為真
^: 異或運算，相異為真，相同為假
~: 取反，真假顛倒
<<: 左移：按二進制把數字向左移動對應位數，高位移出(舍棄)，低位的空位補0。
>>: 右移：按二進制把數字向右移動對應位數，低位移出(舍棄)，高位的空位補符號位，即正數補0，負數補1
>>左移運算符：num << n; 相當于num乘以2的n次方(低位補0)
>>左移運算符：num >> n; 相當于num除以2的n次方
10D = 8+2 --> 1010B<<2 = 101000B = 32+8=40 = 10*2^2
10D = 8+2 --> 1010B>>2 = 0010B = 2 = 10/(2^2)=2

原碼,反碼,補碼是機器存儲一個具體數字的編碼方式
原碼就是符號位加上真值的絕對值,即用第一位表示符號,其余位表示值

比如如果是8位二進制:
+2的原碼 = 0000 0010
-2的原碼 = 1000 0010
第一位為符號位，所以8位二進制取值范圍為[1111 1111, 0111 1111] 也就是[-127, 127] 

反碼：正數的反碼就是原碼，負數的反碼是在原碼的基礎上，符號位不變，其余位取反

+2的反碼 = 0000 0010
-2的反碼 = 1111 1101

補碼：正數的補碼就是原碼，負數的補碼是在反碼的基礎上+1

+2的反碼 = 0000 0010
-2的反碼 = 1111 1110

總結：
    正數的原碼，反碼，補碼都是原數的二進制； 
    負數的原碼就是符號位為1，其余位按正數計算
    負數的反碼就是符號位為1，其余位按正數取反
    負數的補碼就是符號位為1，其余位按正數取反后+1

原碼：10D=0000 1010B, -10D=1000 1010B
反碼：10D=0000 1010B, -10D=1111 0101B
補碼：10D=0000 1010B, -10D=1111 0110B

快速冪
我們都會使用函數:pow(a, n) = a^n,也就是n個a的成績

于是很容易模擬出來

#include<bits/stdc++.h>
using namespace std;
long long pow(int a, int n){
    long long ans=1;
    for(int i=1; i<=n; i++){
        ans *= a;
    }
    return ans;
}
int main(){
    cout<<pow(2,10);
    return 0;
}

可以看出來，上述求冪運算的時間復雜度為O(n)
我們發現其中對結果求乘積的步驟只有當該位基數為1才進行，所以可以使用位運算來改進這個算法
快速冪實現

#include<bits/stdc++.h>
using namespace std;
long long fastPow(int a, int n){
    long long ans=1;
    while(n){
        if(n&1) ans *= a;
        a *= a;
        n>>=1;//右移1位
    }
    return ans;
}
int main(){
    cout<<fastPow(2,10);
    return 0;
}

注意：快速冪的運算結果是呈幾何倍數的增加，所以很容易爆范圍，故而開long long
經常對于這樣的題目，會說對某個數取模,這里我們可以記住以下幾個公式

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p

如果要求取模mod,可以對fastPow函數進行修改

long long fastPow(int a, int n){
    long long ans=1;
    while(n){
    if(n&1) ans = ans*a%mod;//取模
        a = a*a%mod;//取模
        n>>=1; //右移1位
    }
    return ans;
}

1. P5015 [NOIP2018 普及組] 標題統計

【題目描述】凱凱剛寫了一篇美妙的作文，請問這篇作文的標題中有多少個字符？ 注意：標題中可能包含大、小寫英文字母、數字字符、空格和換行符。統計標題字 符數時，空格和換行符不計算在內。

輸入格式：輸入文件只有一行，一個字符串 s。

輸出格式：輸出文件只有一行，包含一個整數，即作文標題的字符數（不含空格和換行符）。

輸入樣例：234 輸出樣例：3

輸入樣例：Ca 45 輸出樣例：4

題解：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str; getline(cin, str);//讀入一行，賦值給str，結束符為換行
    int ans=0;
    for(int i=0; i<str.size(); i++){
        if(s[i]<='9' && s[i]>='0'){
            ans++;
        } else if(s[i]<='z' && s[i]>='a'){
            ans++;
        }else if(s[i]<='Z' && s[i]>='A'){
            ans++;
        }
    }
    cout<<ans; return 0;
}

2. P1200 [USACO1.1]你的飛碟在這兒Your Ride Is Here

【題目描述】眾所周知，在每一個彗星后都有一只UFO。這些UFO時常來收集地球上的忠誠支持者。不幸的是，他們的飛碟每次出行都只能帶上一組支持者。因此，他們要用一種聰明的方案讓這些小組提前知道誰會被彗星帶走。他們為每個彗星起了一個名字，通過這些名字來決定這個小組是不是被帶走的那個特定的小組（你認為是誰給這些彗星取的名字呢？）。關于如何搭配的細節會在下面告訴你；你的任務是寫一個程序，通過小組名和彗星名來決定這個小組是否能被那顆彗星后面的UFO帶走。

小組名和彗星名都以下列方式轉換成一個數字：最終的數字就是名字中所有字母的積，其中A是1，Z是26。例如，USACO小組就是21×19×1×3×15=17955。如果小組的數字mod47等于彗星的數字mod47，你就得告訴這個小組需要準備好被帶走！（記住“a mod b”是a除以b的余數；34mod10等于4）

寫出一個程序，讀入彗星名和小組名并算出用上面的方案能否將兩個名字搭配起來，如果能搭配，就輸出“GO”，否則輸出“STAY”。小組名和彗星名均是沒有空格或標點的一串大寫字母（不超過6個字母）。

輸入格式：

第1行：一個長度為11到66的大寫字母串，表示彗星的名字。
第2行：一個長度為11到66的大寫字母串，表示隊伍的名字。

輸出格式：無

輸入樣例：

COMETQ
HVNGAT

輸出樣例：

GO

題解：

#include<iostream>
using namespace std;
int main(){
    string s1,s2;    cin>>s1>>s2;
    int ans1=1,ans2=1;
    for(int i=0; i<s1.size(); i++)	ans1 *= (s1[i]-'A')+1;
    for(int i=0; i<s2.size(); i++)	ans2 *= (s2[i]-'A')+1;
    ans1 %= 47;    ans2 %= 47;
    if(ans1==ans2)    cout<<"GO";
    else    cout<<"STAY";
    return 0;
}

3. P1125 [NOIP2008 提高組] 笨小猴

【題目描述】笨小猴的詞匯量很小，所以每次做英語選擇題的時候都很頭疼。但是他找到了一種方法，經試驗證明，用這種方法去選擇選項的時候選對的幾率非常大！

這種方法的具體描述如下：假設maxn是單詞中出現次數最多的字母的出現次數，minn是單詞中出現次數最少的字母的出現次數，如果maxn-minn是一個質數，那么笨小猴就認為這是個Lucky Word，這樣的單詞很可能就是正確的答案。

輸入格式：一個單詞，其中只可能出現小寫字母，并且長度小于100。

輸出格式：共兩行，第一行是一個字符串，假設輸入的的單詞是Lucky Word，那么輸出“Lucky Word”，否則輸出“No Answer”；

第二行是一個整數，如果輸入單詞是Lucky Word，輸出maxn-minn的值，否則輸出00。

輸入樣例：error

輸出樣例：

Lucky Word
2

輸入樣例：olympic

輸出樣例：

No Answer
0

題解：

#include<bits/stdc++.h>
using namespace std;
const int N=27;
int a[N];
bool isPrime(int n){//質數判斷函數 
    if(n<2) return false;
    for(int i=2; i*i<=n; i++){
        if(n%i==0) return false;
    }
    return true;
}

int main(){
    string str;    cin>>str;
    int maxn=0,minn=0;
    for(int i=0; i<str.length(); i++){
         a[str[i]-'a'+1]++; //桶排序的知識
    }
    //a[1]~a[26]  這個對應的就是'a'~'z'出現的次數 
    sort(a+1, a+1+26);//升序排序 
    //a[i] = {0, 0, 0, 1, 2, 3}
    maxn=a[26]; 
    for(int i=1; i<=26; i++){
        if(a[i]!=0){
            minn=a[i];break;//退出當前循環 
        }
    } 
    int num=maxn-minn;
    bool flag = isPrime(num);  //判斷num是不是質數
    if(flag){
        cout<<"Lucky Word"<<endl<<num;
    } else{
        cout<<"No Answer"<<endl<<0; 
    }return 0;
}

4. P1226 【模板】快速冪||取余運算

【題目描述】給你三個整數 a,b,p，求 a^b mod p。

輸入格式：輸入只有一行三個整數，分別代表 a,b,p。

輸出格式：輸出一行一個字符串 a^b mod p=s，其中 a,b,p分別為題目給定的值，s 為運算結果。

輸入樣例：2 10 9

輸出樣例：2^10 mod 9=7

數據范圍：對于100% 的數據，保證 0≤a, b<2^31，a+b>0，2≤p<231

題解：

#include<bits/stdc++.h> 
using namespace std;
long long fastpow(long long a, long long n, long long p){
    long long ans=1;
    while(n){
        if(n&1) ans = ans*a%p; 
        a = a*a%p;
        n>>=1;
    }
    return ans;
}
int main(){
    long long a,b,p; 	cin>>a>>b>>p;
    long long s = fastpow(a,b,p)%p;
    cout<<a<<"^"<<b<<" mod "<<p<<"="<<s;
    return 0;
}