二分

#include <stdio.h>

int a[20] = {1, 4, 9, 13, 21, 34, 55, 89, 144, 233, 377, 570, 671, 703, 812};

int check1(int mid, int x)
{
    // mid是扫描到的数字,x是要查找的数字
    if (mid > x)
        return 1;
    else
        return 0;

    // 或return mid > x;
}

int main()
{
    int x;
    scanf("%d", &x);

    // 二分查找
    int l = -1, r = 15;
    while (l + 1 != r)
    {
        int mid = (l + r) >> 1;
        if (check1(a[mid], x))
            r = mid;
        else
            l = mid;
    }

    // 无法找到,也即找到的是错误的
    if (a[l] != x)
        printf("%d is not inside this array. ", x);
    else
        printf("The position of %d is at (%d).", x, l);

    return 0;
}

DFS深度优先搜索

样题P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷

#include <iostream>
using namespace std;

int c[21]; // c[i]表示第i行皇后放置的列数
int n, ans;

void dfs(int cur)
{
	if (cur > n) // 找完所有的行
	{
		ans++; // 找到一种方案
		return;
	}
	else
		for (int i = 1; i <= n; i++) // 试探将皇后放置第cur行的 1~n 列
		{
			bool flag = false;
			// 放置皇后
			c[cur] = i;
			// 判断皇后与 1 ~ cur-1行的皇后是否有冲突
			for (int j = 1; j <= cur - 1; j++)
			{
				if (c[j] == c[cur] || c[j] - j == c[cur] - cur || c[j] + j == c[cur] + cur) // 有冲突的三种情况
				{
					flag = true; // 标记为有冲突
					break;
				}
			}
			if (flag == false) // 没有冲突可以继续搜索
				dfs(cur + 1);
		}
}

int main()
{
	cin >> n;	 // 输入
	dfs(1);		 // 搜索
	cout << ans; // 输出
	return 0;
}

BFS广度优先搜索

样题P1379 八数码难题 - 洛谷

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
typedef pair<int, int> PII;
// 状态压缩

// 模拟队列,记录当前状态
queue<string> q;
// 前面记录某个状态到初始或结束的最少步数,后面记录是由1初始点还是2终点推算来的
unordered_map<string, PII> m;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};

// 双向广搜，更快
int bfs(string beg)
{
    // 起点,终点入队
    q.push(beg);
    q.push("123804765");
    // 标记起点,终点
    m[beg].second = 1;
    m["123804765"].second = 2;

    while (!q.empty())
    {
        // 记录取出的状态
        string t = q.front();

        // 记录取出的状态是由什么方向推来的
        int ok = m[t].second;

        // 记录取出状态的步数
        int bb = m[t].first;

        q.pop();

        // 找到字符串中'0'在二维图中的坐标
        int hh = t.find('0');
        int x1 = hh / 3, y1 = hh % 3;

        for (int i = 0; i < 4; i++)
        {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];

            if (x2 < 0 || x2 >= 3 || y2 < 0 || y2 >= 3)
                continue;

            int tt = x2 * 3 + y2;

            // 交换完,现在的t是已经交换完的t
            swap(t[hh], t[tt]);
            // 如果没有步数,则没走过,赋值并标记,将交换完的t放入队列
            if (!m[t].first)
            {
                m[t].first = bb + 1;
                m[t].second = ok;
                q.push(t);
            }

            // 当前步和前一步碰头了
            if (m[t].second + ok == 3)
            {
                return m[t].first + bb + 1;
            }

            // 交换回来,为下一个方向做准备s
            swap(t[hh], t[tt]);
        }
    }
    return -1;
}

int main()
{
    string a1;
    cin >> a1;

    // 如果终点等于起点,特判
    if (a1 == "123804765")
    {
        printf("0");
        return 0;
    }

    int ans = bfs(a1);
    printf("%d", ans);
    return 0;
}

埃氏筛法求素数

样题1295. X的因子链 - AcWing题库

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;

const int N = (1 << 20)+10;

int primes[N],cnt=0,minp[N]; bool st[N];

//埃氏筛法求素数
void getPrimes(int n)
{
    st[0]=st[1]=1; //非素数
    for(int i=2;i<=n;i++)
    {
        if(st[i] == 1) continue;
        for(int j=i;j<=n/i;j++) //这里j＝1；卡了好久，因为要赋值minp
        {
            st[i * j]=1;
            minp[i * j]=i;
        }
        if(st[i] == 0)
        {
            minp[i] = i;   //这里也要赋值
            primes[cnt++] = i;
        }
    }
}

//阶乘函数
LL pp(int n)
{
    LL res=1;
    for(int i=2;i<=n;i++)
        res*=i;
    return res;
}

int main()
{
    getPrimes(N); //求1到N的所有素数
    
    
    //将输入的数拆解成素数相乘的形式，记录每一个素数的指数
    int n;
    while(scanf(" %d",&n) != -1)
    {
        //记录每一个素数的系数和指数
        int k=0,coef[30],exp1[N];
        while(n>1)
        {
            int p=minp[n];
            // for(int i=0;i<=n;i++)
            //     cout<<minp[i]<<" ";
            // cout<<endl;
            // break;
            coef[k]=p,exp1[k]=0;
            while(n % p == 0)
            {
                n/=p;
                exp1[k]++;
            }
            k++;
        }
        
        //所有素数的指数相加即为长度
        int len=0;
        for(int i=0;i<k;i++)
            len+=exp1[i];
            
        //对所有系数排列组合即为方案数
        LL res=pp(len);
        for(int i=0;i<k;i++)
            res/=pp(exp1[i]);
            
        printf("%d %lld\n",len,res);
    }
    
    return 0;
}