C# 代码

public class Solution {
    public string MakeSmallestPalindrome(string s) {
        int n = s.Length;
        char[] ch = s.ToCharArray();
        int left = 0, right = n - 1;
        while (left < right){
            if (ch[left] != ch[right]){
                char min = (char)Math.Min(ch[left], ch[right]);
                ch[left] = min;
                ch[right] = min;
            }

            left++;
            right--;
        }

        return new string(ch);
    }
}

C# 代码

public class Solution {
    public int MinLength(string s) {
        int n = s.Length;
        Stack<char> stack = new Stack<char>();
        stack.Push('#');
        foreach (char ch in s){
            if ((ch == 'B' && stack.Peek() == 'A') || (ch == 'D' && stack.Peek() == 'C')){
                stack.Pop();
            }
            else{
                stack.Push(ch);
            }
        }

        return stack.Count - 1;
    }
}

include [HTML_REMOVED]

using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;
}

import java.util.*;

public class Main {
public static List[HTML_REMOVED] get_show(int n) {
List [HTML_REMOVED] list = new ArrayList();
for (int i = 1; i * i <= n; i ++ ) {
if (n % i == 0) {
list.add(i);
if (i != n / i) list.add(n / i);
}
}
Collections.sort(list);
return list;
}

public static void main(String [] args) {
    Scanner sr = new Scanner(System.in);
    int n = sr.nextInt();
    List<Integer> list01 = get_show(n);
    for (int x : list01) {
        System.out.println(x);
    }

}

}

1 分析

• 思路与89. a^b类似，用倍增的思想
• 把 $a * b$ 转换成把a加b次
• 因为输入的数值范围为$10^{18}$，所以需要用到unsigned long long数据类型

2 代码

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL qmi(ULL a, ULL b, ULL p)
{
    ULL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    ULL a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

模板题： 89. a^b

代码

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    // p有可能是1，则res为0
    int res = 1 % p;
    // 从最低位开始看，看b的每一位
    while (b)
    {
        // 最后一位是否是1，如果是1的话，就把当前的a的2的多少次幂乘进来。
        if (b & 1)  res = (LL)res * a % p;
        // 每次把a平方，得到下一个
        a = (LL)a * a % p;
        // b右移一位
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

1 分析

• 这类题一般数值较大，直接求的话，求不出来。

• 需要用“快速幂”求解，本质：反复平方法。步骤：

  • 先将b转化成二进制表示，假设：$b = (1110101)_2$
  • 预处理：
    • $a^{2^0} = a^1$
    • $a^{2^1} = (a^{2^0})^2$
    • $a^{2^2} = (a^{2^1})^2$
    • …
  • 则$a^b = a^{1110101} = a^{2^0} * a^{2^2} * a^{2^4} * a^{2^5} *a^{2^6}$
  • 查表，乘的项数 = b的二进制表示中有多少个1，即最多计算$log_2b$次，则时间复杂度为$O(logb)$

• 代码技巧：从低位往高位算，借助位运算把代码写得很简单。

2 代码

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    // p有可能是1，则res为0
    int res = 1 % p;
    // 从最低位开始看，看b的每一位
    while (b)
    {
        // 最后一位是否是1，如果是1的话，就把当前的a的2的多少次幂乘进来。
        if (b & 1)  res = (LL)res * a % p;
        // 每次把a平方，得到下一个
        a = (LL)a * a % p;
        // b右移一位
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        double res = (double)x / 5;
        System.out.println((int)Math.ceil(res));//向上取整
    }
}

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 3e5+10;//无向图+超级零点 所以要存三倍
typedef pair<int,int> PII;
int e[N],ne[N],h[N],w[N],idx;
int dij[N];
int n,m,k,q;
bool text[N];
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra()
{
    //堆优化
    memset(dij,0x3f,sizeof dij);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dij[0] = 0;
    q.push({dij[0],0});
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int num = t.second;
        if(text[num]) continue;
        text[num] = true;
        for(int i = h[num];i!=-1;i=ne[i])
        {
            int s = e[i];
            if(dij[s]>dij[num]+w[i])
            {
                dij[s] = dij[num]+w[i];
                q.push({dij[s],s});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    scanf("%d",&k);
    while(k--)
    {
        int num;
        cin>>num;
        add(0,num,0);//将零点插入链表
        //就是在原本链表的基础上多加一个零点 让其连上村庄的所有距离都为0
        //这样就相当于从零点找最近的村庄的距离 找到的永远都是最近的商店的距离
        //因为零点和商店的距离为0
    }
    dijkstra();
    scanf("%d",&q);
    while(q--)
    {
        int qu;
        cin>>qu;
        printf("%d\n",dij[qu]);
    }
    return 0;
}