头像

yunyi


访客:887

离线:5个月前



yunyi
8个月前

对a的b次方取模
取模肯定是一边算一边取模(防止计算过程的溢出)
所以只考虑实现a的b次方
快速幂
就直接说写法和一些理解:
计算a ^ b,如果把 b 写成2 进制,如13 的二进制 1101,于是3 号位 、2号位、0号位就都是1(就不证明了,去了解一些二进制就会了),那么就可以得到13 = 2^3 + 2^2 + 2^1 = 8 + 4 + 1。所以a ^13 = a^8 * a^4 * a^1。
核心1:
把b转换成二进制,然和将b的二进制数从右到左判断,如果判断为1,则ans乘上当前的次方
eg: 3^5-> 3^(101)–>第零位表为1,则ans就要乘 a^( 2^0 ),然后第一位为0,不操作,第二位为1,ans乘上a^( 2^2)–>ans = 1(ans的初始值) * a^( 2^0 ) (==第一次操作==) * a^( 2^2)(==第二次操作==)
核心2:
每次循环的时候不管要不要对ans进行操作,都要对a进行一次操作,即a = a * a,假如到了第n此循环,此时正在判断b的二进制的第n-1位是否为1。又因为a在第一次进入循环时,为a^1 ,即a^( 2^0) ,那么第n次循环就是a^( 2^n-1),正好b正在判断第n-1位,此时如果为1,则直接将ans = ans * a 即可。

最后还有二进制的一些操作

按位与 &(都为1的时候为1)
按位或 |(有1就变1)
异或 ^ (不同为1,相同为0)
运用:
求n的第k位数字: n >> k & 1(k的第n位为1,则为真)
-n的求法:取反码,然后加1(符号位变为1)
2(010)-> -2(101 + 1 -> 110)
只留下n的最后一位1:lowbit(n) = n & -n
n的最后一个1变为0:n&(n - 1)

最后注意取模
代码

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int a, b, p, ans = 1;
    cin >> a >> b >> p;
    ans %= p;
    while (b){
        if (b & 1 == 1)
        {
            ans = 1ll * ans * a % p;(乘了1ll(这里一个是数字1和字母l,这个字体显示不好)可以将其转化为longlong)
        }
        b >>= 1;
        a = 1ll * a * a % p;
    }
    cout << ans << endl;
    return 0;
}




yunyi
8个月前
1. 概念

由一条链状表组成:(待补图)

有两个主要元素:

  • 表头
  • 节点

  • 结点结构
    ┌───┬───┐
    │data │next │
    └───┴───┘
    data域–存放结点值的数据域
    next域–存放结点的直接后继的地址(位置)的指针域(链域)

  • 表头结构
    表头其实就是一个空节点,不放任何元素。
    表头的date域为空,next域指向链表中的第一个元素。

问题1:为什么要表头?
首先这只是个单链表,后续还要学习更高级的数据结构,单个链表的效率以及表示效果肯定不够,多个表头可以联系起多个单链表。

三个基本操作:
1. 从k处插入一个元素
2. 删除k位置后面这个元素
3. 表头插入元素

eg:
从2处插入元素x:a, b, c –> a,b,x,c
删除2位置后面的这个元素x:a,b,x,c –> a,b,c
从表头插入元素x:a,b,c –>x,a, b,c


例题:
描述
实现一个单链表,链表初始为空,支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表

注意:题目中第k个插入的数并==不是指当前链表的第k个数==。例如操作过程中一共插入了n个数,则==按照插入的时间顺序==,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “H x”,表示向链表头插入一个数x。

(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。

(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。

输出格式
共一行,将整个链表从头到尾输出。

数据范围
1≤M≤100000
所有操作保证合法。


C++代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
int head, e[N], nextt[N], t;
void add_head(int a)//在最前面插入一个a
{
    e[++t] = a;//第t个元素为a
    nextt[t] = nextt[head];//第t个元素(a)的在顺序结构中的下一个元素是原来的head的下一个元素
    nextt[head] = t;//现在的head的下一个元素为第t个元素(a)
}
void del(int a)
{
    if (a == 0) head = nextt[head];//如果是删掉第一个,先让表头指向第一个的下一个
    nextt[a] = nextt[nextt[a]];//a的下一个为a的下一个的下一个,这样就相当于架空了a的下一个,相当于删除
}
void insert(int a, int b){
    e[++ t] = b;//第t个元素为b
    nextt[t] = nextt[a];//继承a的下一个,即插在a和a的下一个之间,那么b的下一个就为原来a的下一个
    nextt[a] = t;//a的新的下一个为第t个元素(b)
}
int main(){
    char s;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        int a, b;
        if (s == 'H')
        {
            cin >> a;
            add_head(a);
        }
        else if (s == 'D')
        {
            cin >> a;
            del(a);
        }
        else if (s == 'I')
        {
            cin >> a >> b;
            insert(a, b);
        }
    }

    for (int i = nextt[head]; i; i = nextt[i])
    {
        cout << e[i] << " ";
    }
    return 0;
}


活动打卡代码 AcWing 101. 最高的牛

yunyi
10个月前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 10010;
int f[N], n, p, h, m, check[N];
int main(){
    scanf("%d%d%d%d", &n, &p, &h, &m);

    f[1] = h;
    while (m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b)
        {
            int c = a;
            a = b;
            b = c;
        }
        if(check[a] != b)
        {
            check[a] = b;
            f[a + 1] --;
            f[b] ++;
        }
    }



    for (int i = 1; i <= n; i ++)
    {
        f[i] += f[i - 1];
        printf("%d\n", f[i]);
    }
    return 0;
}


活动打卡代码 AcWing 100. IncDec序列

yunyi
10个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch  <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
const int N = 100010;
long long a[N];
int main(){
    int n;
    n = read();
    for (int i = 1; i <= n; i ++)
    {
        a[i] = read();
    }
    long long p = 0, q = 0;
    for (int i = n; i > 1; i --)
    {
        a[i] = a[i] - a[i - 1];
        if (a[i] > 0) p += a[i];
        else q -= a[i];
    }

    long long ans1, ans2;
    ans1 = max(q, p);
    ans2 = abs(q - p) + 1;
    cout << ans1 << endl << ans2;
    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

yunyi
10个月前
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int r(){
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch -'0'; ch = getchar();}
    return x * f;
}
const int N = 5005;
int boom, f[N][N], ans = -1, n;
int main(){
    n = r();
    boom = r();
    int mx = boom, my = boom;
    for (int i = 1, x, y, w; i <= n; i ++)
    {
        x = r();
        y = r();
        w = r();
        x ++;
        y ++;
        mx = max(mx, x);
        my = max(my, y);
        f[x][y] = w;
    }

    for (int i = 1; i <= mx; i++)
        for (int j = 1; j <= my; j ++)
        {
            f[i][j] += f[i- 1][j]  + f[i][j - 1] - f[i - 1][j - 1];
        }

    for (int i = boom; i <= mx; i ++)
        for (int j = boom; j <= my; j ++)
        {
            ans = max(ans, f[i][j] - f[i - boom][j] - f[i][j - boom] + f[i - boom][j - boom]);
        }
    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 98. 分形之城

yunyi
10个月前
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long LL;
typedef pair<LL, LL > PLL;
PLL found(LL n, LL a){
    if (n == 0) return make_pair(0, 0);
    LL cnt = 1ll << (2 * n - 2), len = 1ll << (n - 1);
    PLL pos = found(n - 1, a % cnt);
    int z = a / cnt;
    if (z == 0) return make_pair(pos.second, pos.first);
    if (z == 1) return make_pair(pos.first, pos.second + len);
    if (z == 2) return make_pair(pos.first + len, pos.second + len);
    return make_pair(2 * len - 1 - pos.second,len - 1 - pos.first);
}


int main(){
    int T;
    cin >> T;
    while (T --)
    {
        LL A, B, n;
        cin >> n >> A >> B;
        PLL a = found(n, A - 1);
        PLL b = found(n, B - 1);
        LL x = a.first - b.first, y = a.second - b.second;
        double ans = sqrt(x * x + y * y) * 10;
        printf("%0.lf\n", ans);
    }
    return 0;
}


活动打卡代码 AcWing 97. 约数之和

yunyi
10个月前
/*
a = p1^k1 * p2^k2 * ... * pn^kn;
约数个数 = (k1 + 1) (k2 + 1) ... (kn + 1);
约数和 = (p1 ^ 0 + p1 ^ 1 + ... + p1 ^ k1) * (p2 ^ 0 + ... p2^k2) ... (pn ^ 0 + pn ^ 1 + ... +pn ^ kn);
       = sum(p1, k1) * sum(p2, k2) ... sum(pn, kn);

sum(p, k) = (p ^ 0 + p ^ 1 + p ^ 2 + ... + p ^ k)
          = (p ^ 0 + ... p ^ (k / 2)) + p ^ (k / 2 + 1) + ... p ^ k
          = (p ^ 0 + ... p ^ (k / 2)) + p ^ (k / 2 + 1) * (p ^ 0 + ... p ^ (k / 2))
          = (1 + p ^ (k / 2 + 1)) * (p ^ 0 + ... p ^ (k / 2))
          = (1 + p ^ (k / 2 + 1)) * sum(p, k / 2);
a ^ b = (p1^k1 * p2^k2 * ... * pn^kn) ^ b
      = (p1 ^ (k1 * b) * p2 ^ (k2 * b)......)

约数和 = (p1 ^ 0 + p1 ^ 1 + ... + p1 ^ (k1 * b)) * (p2 ^ 0 + ... p2^(k2 * b)) ... (pn ^ 0 + pn ^ 1 + ... +pn ^ (kn * b))

*/
#include <iostream>
#include <cstdio>

using namespace std;
const int mod = 9901;

int quick_pow(int p, int k)
{
    int ans = 1;
    p %= mod;
    while (k)
    {
        if (k & 1) ans = ans * p % mod;
        p = p * p % mod;
        k >>= 1;
    }
    return ans;
}

int sum(int p, int k)
{
    if (k == 0) return 1;
    if (k % 2 == 0)
    {
        return (p % mod * sum(p, k - 1) + 1) % mod;
    }
    return (1 + quick_pow(p, k / 2 + 1)) * sum(p, k / 2) % mod;
}

int main(){
    int a, b, ans = 1;
    cin >> a >> b;

    for (int i = 2; i <= a; i ++)
    {
        int res = 0;
        while (a % i == 0)
        {
            res ++;
            a /= i;
        }
        if (res)
        ans = ans * sum(i, res * b) % mod;
    }

    if (!a) ans = 0;
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 96. 奇怪的汉诺塔

yunyi
10个月前
#include <iostream>
#include <cstring>

using namespace std;
int d[15], f[15];
int main(){
    d[1] = 1;
    for (int i = 1; i <= 12; i ++)
    {
        d[i] = d[i - 1] * 2 + 1;
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= 12; i ++)
    {
        for (int j = 0; j < i; j ++)
        {
            f[i] = min(f[i], f[j] * 2 + d[i - j]);
        }
    }

    for (int i = 1; i <= 12; i ++)
    {
        cout << f[i] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

yunyi
10个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char g[6][6];
int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
void turn(int x, int y){
    for (int i = 0; i < 5; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < 5 && b >= 0 && b < 5)
        {
            if (g[a][b] == '1') g[a][b] = '0';
            else g[a][b] = '1';
        }
    }
}

int get_ans(){
    int ans = 0xffffff;
    char backup[6][6];
    memcpy(backup, g, sizeof g);
    for (int k = 0; k < (1 << 5); k ++)
    {
        int res = 0;
        for (int j = 0; j < 5; j ++)
        {
            if ((k >> j) & 1)
            {
                res ++;
                turn(0, j);
            }
        }
        for (int i = 0; i < 4; i ++)
        for (int j = 0; j < 5; j ++)
        {
            if (g[i][j] == '0')
            {
                res ++;
                turn(i + 1, j);
            }
        }
        bool flag = true;
        for (int i = 0; i < 5; i ++)
        {
            if (g[4][i] == '0')
            {
                flag = false;
                break;
            }
        }

        if (flag)
        {
            ans = min(ans, res);
        }
        memcpy(g, backup, sizeof backup);
    }
    if (ans > 6) return -1;
    return ans;
}

int main(){
    int T;
    scanf("%d", &T);
    while (T --)
    {
        for (int i = 0 ; i < 5; i ++)
        {
            cin >> g[i];
        }
        cout << get_ans() << endl;
    }
    return 0;
}



yunyi
10个月前
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> v;
void dfs(int u, int state){
    if (u == n)
    {
        for (int i = 0; i < n; i ++)
            cout << v[i] << ' ';
        cout << endl;
        return ;
    }
    for (int i = 0; i < n; i ++)
    {
        if (!(state >> i & 1)){
            v.push_back(i + 1);
            dfs(u + 1, state | (1 << i));
            v.pop_back();
        }
    }
}
int main(){
    cin >> n;
    dfs(0, 0);
    return 0;
}