過去問

• 2023年第十四回蓝桥杯C++B組の振り返り
• 2022年
• 2021年
• 蓝桥杯公式サイトの問題演習

⭐試験テクニック⭐

1. まず暴力解法（時間計算量の高い解法）を考えます → 部分点を獲得
2. データ範囲から正しい時間計算量を判断し、その計算量に基づいてアルゴリズムの範囲を特定します。

• 暴力解法：問題文のプロセスをシミュレーションします。
• 時間計算量：https://www.acwing.com/blog/content/32/
• 基礎アルゴリズム：
• 累積和、二分探索、差分（入門アルゴリズム）
• DP（蓝桥杯で頻繁に出題されます）
• 探索（BFS、DFS）→ 通常は暴力解法として使用
• グラフ理論（最短経路、最小全域木）
• データ構造

アルゴリズムと問題解決テクニック

暴力列挙

データサイズが数十程度の場合、ほぼ確実に暴力列挙です。暴力列挙が正解であることが多いです。暴力列挙の方法は通常DFSです。

日付に関する処理

カレンダーのシミュレーション

20D.ランニングエクササイズ

#include <iostream>
#include <cstring>
using namespace std;
int ans;
int d[2][13] = { {0,31,28,31,30,31,30,31,31,30,31,30,31},
                {0,31,29,31,30,31,30,31,31,30,31,30,31} //閏年 
              };
//閏年判定
bool isLeap(int y)
{
    if((y%100!=0 && y%4==0) || y%400==0) return true;
    else return false;
}
int main()
{
    //初期状態
    int y = 2000, m = 1, day = 1;
    int t = 6; //tは曜日
    
    while(1)
    {
        if(t==1 || day==1) ans += 2;
        else ans ++;
        
        //出口条件
        if(y==2020 && m==10 && day==1)
        {
            cout << ans << endl;
            break;    
        } 
        
        //日付をインクリメント
        day ++;
        
        int flag = 0;
        if(isLeap(y)) flag = 1;
        
        //桁上がり処理
        if(day >= d[flag][m]+1)
        {
            day = 1;  //日付を1にリセット
            m += 1;   //月をインクリメント
            if(m >= 13)
            {
                m = 1; //月を1にリセット
                y += 1;
            }
        } 
        t = (t + 1) % 7;  //曜日の更新
    }
    return 0;
}

閏年判定

• 年が4で割り切れ、かつ100で割り切れない場合、その年は閏年です。例えば、2004年は閏年ですが、1900年はそうではありません。
• 世紀年の場合、400で割り切れる年のみが閏年です。例えば、2000年は閏年ですが、1900年はそうではありません。

さらに、2月の日数を確認することでも判断できます。閏年では2月は29日あります。

//閏年判定
bool isLeap(int y)
{
    if((y%100!=0 && y%4==0) || y%400==0) return true;
    else return false;
}

日付の妥当性判定

//日付の妥当性判定
//前提：数字形式で日付を列挙する
bool isValidDate(int x)
{
    int month = x/100%100;
    int day = x%100;
    if(month>=1 && month<=12)
    {
        if(day>=1 && day<=days[month])
            return true;
        else return false;    
    }    
    else return false;
}

23A.日付統計

/*
問題データ：
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 
8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 
8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

答え：235
*/ 

//直接解くのが難しい場合、配列内で条件を満たす部分列を見つけるのは面倒で、重複排除の問題もあります。
//考え方を変えて、2023年の各日付を列挙し、100個の数の中に対応する数字があるか確認してみましょう。 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int a[N];
int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; 
int ans;
//日付の妥当性判定
bool isValidDate(int x)
{
    int month = x/100%100;
    int day = x%100;
    if(month>=1 && month<=12)
    {
        if(day>=1 && day<=days[month])
            return true;
        else return false;    
    }    
    else return false;
}
int main()
{
    for(int i=0;i<100;i++)
        cin >> a[i];
    
    //iの下4桁が月と日
    for(int i=20230101;i<=20231231;i++)
    {
        if(isValidDate(i)==1)
        {
            string s = to_string(i);
            int k=0;
            for(int j=0;j<100;j++)
            {
                //注意：a[j]はint型、s[k]はchar型
                if(a[j] == s[k]-'0') k++;
            }
            if(k==8) ans ++;
        }    
    }
    cout << ans << endl; 
    return 0;
}

無限大の設定

ブログ

INF = 0x3f3f3f3f; //正の無限大

memset初期化関数

const int INF = 0x3f3f3f3f, N = 510;
int f[N][N];

//memset関数の使い方
//第一引数：初期化する配列f
//第二引数：初期化する値-INF（-INFは負の無限大）
//第三引数：配列のバイト数、sizeofでf配列のバイト数を計算
memset(f, -INF, sizeof f);

切り捨てと切り上げ

切り捨て

1. 整数除算演算子 / は切り捨てを意味し、計算によく使われます（正数に適用、負数の場合は正数の結果に負符号を付けたもの）

例：5 / 2 = 2、-5 / 2 = -2 2. C++のfloor()関数、floor(x)はx以下の最大整数を返します

例：floor(2.5) = 2、floor(-2.5) = -3 3. 小数部分を直接切り捨て、整数変数に代入（正数に適用）

例：int a = 2.5、b = int(2.5)、aとbの値はどちらも2

切り上げ

1. C++のceil()関数、ceil(x)はxより大きい最小の正数を返します

例：ceil(2.5) = 3、ceil(-2.5) = -2 2. 公式 x = (a-1) / b + 1、変形すると x = (a + b - 1) / b 3. 小数部分を直接切り捨て、整数変数に代入（負数に適用）

例：int a = -2.5、b = int(-2.5)、aとbの値はどちらも-2

四捨五入

round()関数は四捨五入に使用されます

元のリンク

整数の上下限の特定

• 2023 C.金属精錬
• 下限切り捨て記号**"⌊ ⌋"**

アルゴリズム基礎

累積和

数列の前n項和を求めるようなものです。

数列：a1,a2,a3,…,an

累積和 Si = a1 + a2 + … + ai

• 注意：インデックスは1から始まるようにします（S0 = 0）

部分行列の和

//acwing
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N][N];//行列データを格納
int s[N][N];//累積和を初期化
int n,m,q;
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    
    //データを格納
    //注意：i,jは1から始まる（0を引く操作があるため）
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
            
    //累積和を初期化
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        
        //部分行列の和を求める
        int sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        
        printf("%d\n",sum);
    }
    return 0;
}

繰り返し二乗法

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll; //数論の問題は通常long longを開く必要があり、intがオーバーフローする可能性があります

//a^k % pを求める
int qmi(int a,int k,int p)
{
    int res = 1;
    while(k) //kを二進数化し、下位から上位へ
    {
    	//kの二進数表現の最下位ビット（最右ビット）が1の場合、現在のaを掛けます
        if(k&1) res = (ll)res*a%p;
        
        //kの二進数表現を右シフト
        k >>= 1;
        
        //aを更新
        a = (ll)a*a%p; //剰余を取った結果
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a,k,p;
        scanf("%d%d%d", &a,&k,&p);
        printf("%d\n", qmi(a,k,p));
    }
    return 0;
}

高精度除算

高精度除算

• 高精度数値は文字列で保存します
• vectorは動的配列で、要素に対して頻繁な操作が可能です
• vector要素操作（挿入、削除）は主に最後の要素に対して行われるため、コード中に多くの逆順操作があります

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
// A / b、rは余り、Cは商
vector<int> divide(vector<int> &A, int b, int &r) //Aとrは参照渡し
{
    vector<int> C;
    
    r = 0;
    for(int i=A.size()-1; i>=0; i--)
    {
        //以下3行が核心
        r = r*10 + A[i];  //右辺のrはi-1に対応、左辺のrはiに対応
        C.push_back(r / b); //Cに各桁の商を保存
        r %= b; //i桁目の余りに対応
    }
    
    //上のforループで保存されたCの商は正順なので、先頭の0を削除する操作のために逆順にします
    reverse(C.begin(), C.end());
    
    while(C.size()>1 && C.back()==0)
        C.pop_back();
        
    return C;
}
int main()
{
    string a;  // 高精度数値は文字列で保存
    int b;  //低精度はint
    cin >> a >> b;
    
    vector<int> A;
    //高精度数値を逆順でベクタAに保存
    for(int i=a.size()-1; i>=0; i--)
        A.push_back(a[i] - '0');  //注意：a[i]はchar型、'0'を引くとint型になる
    
    int r; //余り
    auto C = divide(A, b, r);
    
    //商を出力
    for(int i=C.size()-1; i>=0; i--)
        printf("%d", C[i]);
    
    puts(""); //改行
    
    //余りを出力
    cout << r << endl;
    
    return 0;
}

グラフ理論

木とグラフの保存

木の重心

/*
ACwing 846.木の重心 
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
*/

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N*2;
//h[i]はヘッダポインタを保存、iは値
//ne[i]はnextポインタを保存、iはポインタ
//e[i]はインデックスiの値
//idxはインデックス、つまりポインタ
int h[N],ne[M],e[M],idx;

//先頭挿入法：ヘッドノードの後ろにノードbを挿入（a-->b）
void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
    int n;
    cin >> n;
    
    //ヘッドポインタを-1で初期化、空ノードを指す
    memset(h, -1, sizeof h);
    
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin >> a >> b;
        
        add(a,b); //有向グラフ
        
//        add(a,b), add(b,a); //無向グラフ
    } 
    
    //ヘッドノードが2のすべての隣接ノードを走査
    for(int i=h[2]; i!=-1; i=ne[i])
    {
        cout << e[i] << ' ';
    }
    
    return 0;
}

木とグラフの深さ優先探索と幅優先探索（オーバーロードの知識を含む）

P5318文献検索

/*
入力： 
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

出力：
1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8  
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int h[N],ne[N],e[N],idx;
bool st[N];
int path[N]; //経路記録用
int k = 1, k1 = 0;
//構造体を定義 辺の起点a、終点bを保存
struct edge{
    int a,b;
}edges[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//並べ替え順序をオーバーロード、aの昇順、bの降順、aが同じ場合はbも降順
bool cmp(edge e1, edge e2)
{
    if(e1.a == e2.a) return e1.b > e2.b;
    return e1.a < e2.a;
}
//深さ優先探索
//u：ノードu
void dfs(int u)
{
    cout << u << ' ';
    
    st[u] = 1; //ノードuが走査済み、マーク
    
    //ノードuをヘッドノードとして、uの隣接点を走査
    for(int i=h[u]; i!=-1; i=ne[i])
    {
        //jは値（ノード番号）、uの隣接点
        int j = e[i];
        {
            //ノードが走査されていない場合
            if(!st[j])    
            {
                st[j] = 1; //走査して、マーク
                dfs(j); //j番ノードをヘッドノードとして深さ優先探索を続ける
            }
        } 
    } 
}

//幅優先探索
void bfs()
{
    queue<int> q;
    
    st[1] = true;
    path[0] = 1;
    q.push(1);
    
    while(q.size())
    {
        int t = q.front(); q.pop();
        
        cout << t << ' '; //探索しながら出力
        
        for(int i=h[t]; i!=-1; i=ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
                st[j] = true;
                path[k++] = j;
                q.push(j);
            }
        }
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;
        edges[i] = {a,b}; //辺の起点a、終点bを保存
    }
    
    //cmpを追加することに注意
    sort(edges, edges+m, cmp);
    
    //グラフを保存
    for(int i=0;i<m;i++)
    {
        add(edges[i].a,edges[i].b);
    }
    
    dfs(1);
//    for(int i=0;i<k1;i++)
//        cout << path[i] << ' ';
        
    puts(""); //改行 
    
    //st状態配列をリセット
    memset(st, false, sizeof st);
    
    bfs();
//    for(int i=0;i<k;i++)
//        cout << path[i] << ' ';
    return 0;
}

spfaによる最短経路

spfaによる最短経路

st[i]配列はノードiがキュー内にあるかを示します

• st[i] = true はi番ノードがキュー内にあることを示します
• st[i] = false はi番ノードがキュー内にないことを示します

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int h[N],e[N],w[N],ne[N],idx;

//st[i]配列はノードiがキュー内にあるかを示します
bool st[N]; // st[i] = true はi番ノードがキュー内にあることを示し、st[i] = false はi番ノードがキュー内にないことを示します

int dist[N]; //dist[i]はi番ノードから1番ノードまでの距離を保存
int n,m;
void add(int a,int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa()
{
    //distを初期化、最初はすべてのノードから1番ノードまでの距離が無限大
    memset(dist, 0x3f, sizeof dist);
    //特例、1番ノードから自身への距離は0
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while(q.size())
    {
        int t = q.front(); q.pop();

        st[t] = false; //t番ノードが削除され、キュー内にないため、st[t]をfalseに設定

        for(int i=h[t]; i!=-1; i=ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true; //j番ノードがキューに入り、キュー内にあるため、st[j]をtrueに設定
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        add(x,y,z);
    }

    spfa();

    if(dist[n] == 0x3f3f3f3f) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}

秦九韶のアルゴリズム

2022年蓝桥杯c++B組E題X進法減算から出題

オーバーロード 浮動小数点数の等価判定

21年C題 直線

//傾き、切片で唯一の直線を決定

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e6;
int n;
//小なり演算子をオーバーロード
struct Line{
    double k,b; //k傾き b切片
/*
    bool operator< (const Line& t) const
    {
        if(k != t.k) return k > t.k;
        return b > t.b;
    }
*/
};
//別のオーバーロード方法
bool cmp(Line l1, Line l2)
{
    if(l1.k == l2.k) return l1.b > l2.b;
    return l1.k > l2.k;
}

int main()
{
    //2点を列挙
    for(int x1=0;x1<20;x1++)
        for(int y1=0;y1<21;y1++)
            for(int x2=0;x2<20;x2++)
                for(int y2=0;y2<21;y2++)
                    //傾きが存在する場合
                    if(x1 != x2)
                    {
                        double k = (double)(y2-y1) / (double)(x2-x1);
                        double b = y1 - k*x1;
                        l[n++] = {k,b};    
                    } 
    //cmpパラメータを追加することに注意
    sort(l,l+n, cmp);
    
    int res = 1;
    
    //インデックスは1から始まる（i-1操作があるため）
    for(int i=1;i<n;i++)
    {
        //fabsは浮動小数点数の絶対値関数、cmathライブラリをインクルードする必要あり
        //浮動小数点数の等価判定：fabs(l[i].k-l[i-1].k) < 1e-8 に小なり演算子を使用
        //浮動小数点数の非等価判定
        if(fabs(l[i].k-l[i-1].k)>1e-8 || fabs(l[i].b-l[i-1].b)>1e-8)
            res ++ ;
    }
    
    //傾きが存在しない場合20を忘れずに追加
    cout << res + 20 << endl;
    return 0;
}

C/C++知識点

一般的な数学関数

• 絶対値関数
• fabs()
• abs()関数

#include<cmath>

float x = -2.2342;

// fabs()とabs()は同じ効果ですが、これらの関数の戻り値は6桁の有効数字しか保持できず、数字の長さが6桁を超えると四捨五入されます
cout << fabs(x) << endl;
cout << abs(x) << endl;
>>>>2.2342
    2.2342 

• 数学関数

	関数	関数プロトタイプ	機能
指数関数	exp(x)	double exp(double x)	e^xの値を計算し、計算結果を返します
対数関数	log(x)	double log(double x)	lnxの値を計算し、計算結果を返します
	log10(x)		底を10（任意の正の定数にすることができます）、xを指数とする対数を計算し、計算結果を返します。注意：x>0
べき関数	pow(x,y)	double pow(double x,double y)	xを底、yを指数とするべき乗、つまりx^yを返します。注意：この関数はパラメータx,yと関数の戻り値がすべてdouble型である必要があり、そうでないと数値オーバーフローの問題が発生する可能性があります。
平方根	sqrt(x)	double sqrt(double x)	√xの値を計算し、計算結果を返します。注意：x>=0
正弦関数	sin(x)	double sin(double x)	sinxの値を返します。注意：xの単位はラジアン
余弦関数	cos(x)	double cos(double x)	cosxの値を返します。注意：xの単位はラジアン
正接関数	tan(x)	double tan(double x)	tanxの値を返します。注意：xの単位はラジアン

データ型

C++データ型（整数型、浮動小数点型、文字型、文字列型、ブール型）

データ型		占有スペース	値の範囲
short	短整数型	2バイト	(-2^15 ~ 2^15-1)
**int**	整数型	**4バイト**	**(-2^31 ~ 2^31-1)** **約=2e9**
long	長整数型	**Windowsでは4バイト**；Linuxでは4バイト（32ビット）または8バイト（64ビット）	(-2^31~ 2^31-1)
long long	長長整数型	8バイト	(-2^63 ~ 2^63-1) **約=9e18**
float	単精度浮動小数点型	4バイト	6~7桁の有効数字
double	倍精度浮動小数点型	8バイト	15~16桁の有効数字
long double	高倍精度浮動小数点型	8バイト	16桁の有効数字
char	文字型	1バイト	ASCIIコード範囲(0~127)
bool	ブール型	1バイト	0または1 (true or false)
string	文字列型

注：C++のbool型では、true または 任意の非0値 は「真」を表し、false または 0値 は「偽」を表します。

sizeofキーワード

作用：データ型が占有するメモリサイズを統計し、戻り値はデータ型が占有するバイト数です

構文：sizeof(データ型) または sizeof(変数名)

b,B,KB,MB,GB,TBの変換

基本概念

1. bit（ビット、別名「ビット」）：bitの略称はbで、コンピュータの最小データ単位です（二進法の範囲、つまり0または1）
2. Byte（バイト）：Byteの略称はBで、コンピュータファイルサイズの基本計算単位です。例えば、1文字は1Byte、漢字の場合は2Byteです。

さらに、キロバイト（KB）、メガバイト（MB）、ギガバイト（GB）、テラバイト（TB）も使用されます。

換算 容量における b、B、KB、MB、GB 、TBの換算関係の対応

1B（バイト）= 8b（ビット）
1 KB = 1024 B
1 MB = 1024 KB
1 GB = 1024 MB
1TB = 1024GB
1B = 1つの英字または1つの数字または1つの文字
2B = 1つの中国語の漢字

それらの間の換算関係はすべて1024倍です

元のリンク：https://blog.csdn.net/joshua317/article/details/120186858

剰余演算式（%）

1. 加法分配則 (a + b) % p = (a % p + b % p) % p
2. 減法分配則 (a - b) % p = (a % p - b % p) % p
3. 乗法分配則 (a * b) % p = (a % p * b % p) % p
4. 指数 a ^ b % p = ((a % p)^b) % p

演算子

ビットごとのAND（&）

c++でk&1とは何ですか

C++では、式 k & 1 は整数 k に対するビットごとのAND（&）演算を意味します。ここで 1 は二進数の 0000000000000001 です（k の型に依存します）。ビットごとのAND演算は、2つのオペランドの各ビットに対して論理AND操作を実行します：

• 2つの対応する2進数ビットが両方とも1の場合、結果ビットは1です；
• それ以外の場合、結果ビットは0です。

二進数表現では、数字1の最後のビットは1で、他のすべてのビットは0です。したがって、任意の整数 k に対する k & 1 の演算は、k の二進数表現の最下位ビット（最右ビット）が1かどうかを検出するものです。

k が奇数の場合、その二進数表現の最下位ビットは必ず1なので、k & 1 の結果は1になります。 k が偶数の場合、その二進数表現の最下位ビットは必ず0なので、k & 1 の結果は0になります。

したがって、k & 1 は整数 k が奇数かどうかを判断するために頻繁に使用され、結果が1の場合は k が奇数、0の場合は k が偶数を意味します。

二進数右シフト演算子（>>）

C++でk>>=1とは何ですか

C++では、式 k >>= 1; は複合代入演算子で、整数変数 k を右に1ビットシフトし、その結果を k 自身に戻します。

ここでの >> は二進数右シフト演算子で、k の二進数表現を指定されたビット数（ここでは1ビット）だけ右にシフトします。右シフトの過程では、最上位ビット（最左ビット）は通常破棄され、最下位ビット（最右ビット）は0で埋められます（符号なし整数の場合）、または符号ビットに基づいて拡張されます（符号付き整数の場合、つまり元の符号ビットを保持）。

したがって、k >>= 1; を実行すると、以下の2つのステップが実行されます：

1. k = k >> 1; —— k の値を1ビット右シフトします。
2. 結果を自動的に k に代入します。

この操作は整数を2で割る操作（切り捨て）を高速に実現するために頻繁に使用されます。なぜなら、二進数では1ビット右シフトするごとに2で割ることになるからです。例えば、k の値が10進数の8（二進数 1000）の場合、k >>= 1; を実行すると、k の値は4（二進数 0100）になります。

XOR演算子（^）

XOR演算子（XOR演算子）は二進数ビット演算子の一種で、通常2つの二進数の対応ビットを比較するために使用されます。XOR演算のルールは：2つの対応する2進数ビットが同じ場合、そのビットの結果は0です；2つの対応する2進数ビットが異なる場合、そのビットの結果は1です。

多くのプログラミング言語では、XOR演算子は ^ 記号で表されます。例えば、C++、Java、Pythonなどの言語では、^ を使用してXOR演算を実行できます。

XOR演算にはいくつかの重要な特性があります：

1. 交換法則：A ^ B は B ^ A と等しい。
2. 結合法則：(A ^ B) ^ C は A ^ (B ^ C) と等しい。
3. 任意の数と0のXOR演算、結果は元の数のまま：A ^ 0 は A と等しい。
4. 任意の数と自身のXOR演算、結果は0：A ^ A は 0 と等しい。
5. XOR演算は一時変数を使用せずに2つの変数の値を交換するために使用できます：A = A ^ B; B = A ^ B; A = A ^ B; を実行すると、AとBの値が交換されます。

#include <iostream>  
using namespace std;
int main() {  
    int a = 5;    // 二進数表現は 0101  
    int b = 3;    // 二進数表現は 0011  
    int result = a ^ b; // XOR演算
  
    cout << "XOR結果は: " << result << endl; // 出力は 0110、つまり10進数の6
  
    return 0;  
}

データ構造

キューqueue

【C++】キュー（queue）の基本使い方

//ヘッダファイル
#include<queue>
typedef pair<int,int> PII;

queue<PII> q; //キューqを構築し、その内部要素の型はpair

//メソッドには括弧が必要 例：q.pop()
//属性には括弧が不要 例：t.first   t.second

q.push({1,2}); //要素{1,2}をキューの末尾に挿入、単一要素ではない場合は{}を使用
q.pop(); //キューの先頭要素をポップ（つまり先頭要素を削除）
PII t = q.front(); //キューの先頭要素をクエリ、tはpair型

t.first;  //tの最初のint値をクエリ
t.second; //tの2番目のint値をクエリ

q.back(); //キューの末尾要素をクエリ
q.size(); //qの要素数をクエリ
q.empty(); //qが空かどうかをクエリ、空の場合は1を返し、キューが空でない場合は0を返す

キューの定義

• キュー（queue）は、一端でのみ挿入操作を許可し、もう一端でのみ削除操作を許可する線形表であり、「先入れ先出し/FIFO」という原則に従うデータ構造です。
• 注意：キューの先頭と末尾のみが外部からアクセス可能であり、したがって走査操作は許可されていません。

• キューの先頭（front）：削除を許可する端、別名キューの先頭
• キューの末尾（rear）：挿入を許可する端
• 空のキュー：要素を含まない空の表

vector

C++_vector操作

C++ vectorコンテナの詳細

#include<vector>
vector<int> a,b;

//aの最後の要素を返す
a.back();

//aの最初の要素を返す
a.front();

//aベクタの最後の要素を削除
a.pop_back();

//aベクタの最後の要素の後に値5の要素を挿入
a.push_back(5);

//aの最初の要素から2番目の要素までを削除、つまり削除される要素はa.begin()+1から（含む）a.begin()+3まで（含まない）です
a.erase(a.begin()+1,a.begin()+3);

//a中の要素数を返す
a.size();

//bはベクタ、aの要素とbの要素を全体で交換
a.swap(b);

//aの要素をクリア
a.clear();

//aが空かどうかを判断、空の場合trueを返し、空でない場合はfalseを返す
a.empty();

pair

C++ pairの基本使い方まとめ（整理）

⭐文字列操作

C++ Stringの一般的な関数の使い方まとめ

string s="abcd";
//文字列の長さnを求め、s.length()とs.size()は同じ効果
n = s.size(); 

to_string関数

• 数値定数を文字列に変換し、戻り値は変換された文字列です

• 文字列は添字インデックス操作をサポートし、Pythonのリストのようなものです

• c++では文字と文字列は区別されます：

• 文字：char 単一引用符

• 文字列：string 二重引用符

string str = "abc"; //二重引用符は文字列
// char = 'a'; //単一引用符は文字
int num = 20230101; 
cout << str[0] << endl;
cout << str + to_string(num) << endl;
>>>> 'a'
>>>> 'abc20230101'

string関連関数

unique関数

C++のStringの一般的な関数の使い方まとめ

sort

unique

erase

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <typeinfo>
using namespace std;
int main()
{
    string s;
    cin >> s;
    
    //文字列をソート
    sort(s.begin(),s.end());
    cout << s << endl;
    
    //unique関数はイテレータを返します（イテレータはアドレス、インデックスとみなせます）
    //unique関数は実質的に「擬似重複排除」関数です。
    //重複要素をコンテナの末尾に追加するだけで、戻り値は重複排除後の末尾アドレス（アドレスです！！）
    auto it = unique(s.begin(),s.end());
    
    cout << typeid(it).name() << endl; //uniqueの戻り値の型を出力
    
    int t = it - s.begin(); //s中の重複しない文字数
    cout << t << endl;
    
    s.erase(it,s.end()); //重複した文字を削除
    
    cout << s << endl;

    return 0;
}

変数のデータ型を判断

C / C++：変数のデータ型をクエリ

関数を使用

#include<typeinfo>
typeid(a).name()  // aは変数名

コードの実際の測定

#include <iostream>
#include <string>
#include <typeinfo> //必須のヘッダファイル
using namespace std;
int main(){
    int num = 0;
    char cha = 'a';
    float flo = 1.0;
    double dbe = 2.3;
    bool boo = false;
    string str = "haihong"; 
    
    cout<< "numの型は " << typeid(num).name() <<endl;
    cout<< "chaの型は " << typeid(cha).name() <<endl;
    cout<< "floの型は " << typeid(flo).name() <<endl;
    cout<< "dbeの型は " << typeid(dbe).name() <<endl;
    cout<< "booの型は " << typeid(boo).name() <<endl;
    cout<< "strの型は " << typeid(str).name() <<endl;
}

文字'0'を減算し、単一文字の減算の説明

ブログ

c++で単一文字を減算すると、対応するASCIIコードが減算されます

• char型の数字をchar型の'0'で減算すると、int型のその数字が得られます
• 例：'9' - '0' = 9

'0'を減算することは、0のASCIIコード値48を減算することと同じです。数字文字から'0'を減算すると、その数字が得られます。

文字列中の英字を小文字から大文字に変換するのも、文字のASCIIコード値を使用します

関数を使用

#include<typeinfo>
typeid(a).name()  // aは変数名

コードの実際の測定

#include <iostream>
#include <string>
#include <typeinfo> //必須のヘッダファイル
using namespace std;
int main(){
    int num = 0;
    char cha = 'a';
    float flo = 1.0;
    double dbe = 2.3;
    bool boo = false;
    string str = "haihong"; 
    
    cout<< "numの型は " << typeid(num).name() <<endl;
    cout<< "chaの型は " << typeid(cha).name() <<endl;
    cout<< "floの型は " << typeid(flo).name() <<endl;
    cout<< "dbeの型は " << typeid(dbe).name() <<endl;
    cout<< "booの型は " << typeid(boo).name() <<endl;
    cout<< "strの型は " << typeid(str).name() <<endl;
}