头像

yysh




离线:8小时前


最近来访(6)
用户头像
yxc的小迷妹
用户头像
yxᴄ
用户头像
励志关注所有人
用户头像
YaphetStar
用户头像
一生雾梦
用户头像
封清扬

新鲜事 原文

yysh
16小时前
高精度除法 高精度 / 高精度 #include<iostream> #include<algorithm> #include<vector> using namespace std; int compare(vector<int> &a1, vector<int> &t) { //a1和t位数不一样 if(a1.size() > t.size()) { return 1;//说明被除数大于减数 } else if(a1.size() < t.size()){ return -1;//说明被除数小于减数 } //a1和t1位数一样的时候 for(int i = a1.size() - 1; i >= 0; i--) { if(a1[i] < t[i]) { return -1; //如果某位上的a1[i]小于t[i],说明a1小于t } if(a1[i] > t[i]) { return 1; //如果某位上的a1[i]大于t[i], 说明a1大于t } } return 0; //反之,说明a1 == t } void sub(vector<int> &a1, vector<int> &t) { //如果可以进行减法,被减数a1肯定是大于t的 for(int i = 0; i < a1.size(); i++) { if(i < t.size()) { if(a1[i] < t[i]) { a1[i] += 10; a1[i + 1]--; } a1[i] -= t[i]; } } //弹出前导的0 while(a1.size() > 1 && a1.back() == 0) { a1.pop_back(); } } void addNum(vector<int> &b1, vector<int> &t, int n) { //将b1数组整体移动n位到t数组中 for(int i = 0; i < b1.size(); i++) { //把原来在b1数组中靠前位置的数,移动到t数组中靠后位置的数 t[i + n] = b1[i]; } } int main(){ string a, b; //输入被除数a和除数b cin >> a >> b; //特判被除数为0的情况 if(a == "0") { cout << 0; return 0; } //声明数组a1, b1存储被除数和除数,c1作为答案数组 vector<int> a1(a.size(), 0), b1(b.size(), 0), t1(b.size(), 0), c1; //初始化答案数组 if(a.size() >= b.size()) { for(int i = 0; i < a.size() - b.size() + 1; i++) { c1.push_back(0); } } else { c1.push_back(0); } //倒序读入被除数和除数(因为使用减法模拟除法,所以需要倒序存储) for(int i = a.size() - 1; i >= 0; i--) { a1[a.size() - i - 1] = a[i] - '0'; } for(int i = b.size() - 1; i >= 0; i--) { b1[b.size() - i - 1] = b[i] - '0'; } //获得商 for(int i = c1.size() - 1; i >= 0; i--) { //声明且初始化存储临时减数的数组t,全部初始化为0,有利于接下来的扩大除数操作 vector<int> t(b1.size() + i, 0); //获取新的除数 addNum(b1, t, i); //原除数,新的除数,扩大的位数 //模拟竖式减法 //如果被除数 >= t,继续执行减法 while(compare(a1, t) >= 0) { //累加当前位置上的次数,计算当前位置上的商 c1[i]++; //计算被除数a1 - t sub(a1, t); } } //处理答案数组中前导的0 while(c1.size() > 1 && c1.back() == 0) { c1.pop_back(); } //输出商 for(int i = c1.size() - 1; i >= 0; i--) { printf("%d", c1[i]); } cout << "\n"; //输出余数 for(int i = a1.size() - 1; i >= 0; i--) { printf("%d", a1[i]); } return 0; }



yysh
21小时前

高精度除法

高精度 / 低精度

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> div(vector<int> & a1, int b, int &t) {
    vector<int> c;

    //由于我们是倒序存入的数,但是除法需要从高位开始计算,所以,我们倒序循环
    for(int i = a1.size() - 1; i >= 0; i--) {
        //余数 = 上一次计算的余数 * 10 + 当前位置上的数
        t = t * 10 + a1[i];

        //存入商
        c.push_back(t / b);

        //取余除数,更新当前的余数
        //如果t >= b,说明t可以除以b,那么我们进行更新,反之,说明t除以不了,那么t不变
        t %= b;
    }

    //除法可能存在前导的0,所以我们需要处理前导的0
    //由于我们存入答案数组的结果是顺序存入的,但是vector没办法弹出前面的元素,只能尾部弹出
    //所以,我们先反转数组,让高位移动到尾部,然后弹出前导的0
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0) {
        c.pop_back();
    }

    return c;
}


int main() {
    string a;
    int b;

    cin >> a >> b;

    vector<int> a1(a.size(), 0);

    //除法本来可以不用倒序存储,但是我们为了保持一致性,选择倒序存入
    for(int i = a.size() - 1; i >= 0; i--) {
        a1[a.size() - 1 - i] = a[i] - '0';
    }

    //声明t表示余数
    int t = 0;
    auto c1 = div(a1, b, t);

    //由于我们处理前导的0,所以在答案数组中的数又变成了倒序存储,所以,我们需要倒序输出
    for(int i = c1.size() - 1; i >= 0; i--) {
        printf("%d", c1[i]);
    }

    //换行,输出最终的余数
    cout << "\n" << t;

    return 0;
}


新鲜事 原文

yysh
1天前
高精度乘法 高精度 * 高精度 #include<iostream> #include<vector> using namespace std; int main() { string a, b; cin >> a >> b; //特判0 if(a == "0" || b == "0") { cout << 0; return 0; } vector<int> a1(a.size(), 0), b1(b.size(), 0); for(int i = a.size() - 1; i >= 0; i--) { a1[a.size() - 1 - i] = a[i] - '0'; } for(int i = b.size() - 1; i >= 0; i--) { b1[b.size() - 1 - i] = b[i] - '0'; } vector<int> c1(a1.size() + b1.size(), 0); for(int i = 0; i < a1.size(); i++) { for(int j = 0; j < b1.size(); j++) { //累加当前位置上的数 c1[i + j] += a1[i] * b1[j]; //获取进位 c1[i + j + 1] += c1[i + j] / 10; //处理当前位置,确保存入的数在[0,9] c1[i + j] %= 10; } } //处理高位的0,因为我们是倒序存储的,所以高位的0在后面 while(c1.size() > 1 && c1.back() == 0) { c1.pop_back(); } //倒序输出 for(int i = c1.size() - 1; i >= 0; i--) { printf("%d", c1[i]); } return 0; }



yysh
1天前

简单高精度

#include<iostream>
#include<vector>

using namespace std;

vector<int> mul(vector<int> & a1, int b) {
    vector<int> c;
    int t = 0;

    for(int i = 0; i < a1.size(); i++) {
        //t表示大数的每一位乘以小数整体的值
        t += a1[i] * b;

        //确保我们存入答案数组的都是个位数
        c.push_back(t % 10);

        //获取进位的数
        t /= 10;
    }

    //处理进位
    if(t > 0) {
        c.push_back(t);
    }

    return c;
}

int main() {

    string a;
    int b;

    cin >> a >> b;

    //提前特判0
    if(a == "0" || b == 0) {
        cout << 0;
        return 0;
    }

    vector<int> a1(a.size(), 0);
    for(int i = a.size() - 1; i >= 0; i--) {
        a1[a.size() - 1 - i] = a[i] - '0';
    }

    auto c1 = mul(a1, b);

    for(int i = c1.size() - 1; i >= 0; i--) {
        printf("%d", c1[i]);
    }

    return 0;
}




yysh
25天前

高精度减法(代码量进一步减少)

思路

模拟人为的竖式减法,且要确保被减数大于等于减数,避免负数情况,导致难度增加

#include <iostream>
#include <vector>

using namespace std;

vector<int> sub(vector<int> v1, vector<int> v2) {
    vector<int> v3;

    int temp = 0;

    //不管是a >= b 还是 a < b,我们都保证了a > b,即v1.size > v2.size
    //所以,循环的结束条件是遍历完v1
    for(int i = 0; i < v1.size(); i++) {
        //整个循环跑的就是v1的大小,所以不担心会越界
        temp += v1[i];

        //由于v2小于v1所以我们要避免越界
        //此外,由于我们默认的是大减去小
        //所以temp += v1[i]     temp -= v2[i]
        if(i < v2.size()) temp -= v2[i];

        //(temp + 10) % 10的写法,把temp >= 0的情况和temp < 0的情况合二为一了
        //temp >= 0的情况返回的就是temp本身 那么(temp + 10) % 10 = temp + 0 
        //因为0 <= temp <= 9,所以(temp + 10) % 10还是temp本身
        //如果temp < 0的情况,返回的应该就是temp + 10,那么(temp + 10) % 10 = temp + 10
        //因为temp < 0的情况下,0 <= temp + 10 <= 9, 所以(temp + 10) % 10还是temp + 10本身
        v3.push_back((temp + 10) % 10);

        //判断temp的大小
        if(temp >= 0) temp = 0;//大于等于0说明不需要像高位借位,把temp赋值为0避免影响下一次运算
        else temp = -1;//小于0说明需要像高位借位,把temp赋值为-1,确保下一次计算的时候高位的值-1
    }

    //由于是减法,所以不存在最后一位发生进位的事情,但是,减法有另外一个问题
    //比如123 - 120 = 3,但是我们保证了答案数组v3的位数和被减数数组v1的位数是一样的
    //所以,v3数组中实际装的值就是 0 0 3,所以,为了答案的准确性,我们输出的时候需要去掉前导的0
    //但是,由于我们存储的时候是先存的低位部分,所以v3中实际的存储情况是 3 0 0
    //所以,我们需要从v3的末尾去掉前导的0(输出答案是从高位输出到低位,0都保存在了高位,所以是前导0)
    //如果v3的末尾元素是0,且v3中的元素不止一个,我们不断的弹出尾部元素,以达到去除前导0的效果
    //最坏的情况是全0,所以我们至少要保留一个0。
    while(v3.size() > 1 && v3.back() == 0) v3.pop_back();

    return v3;
}

int main() {
    string a, b;
    cin >> a >> b;

    //如果a < b,我们需要提前进行处理,交换a和b的位置,然后输出一个负号
    //这样一来,我们可以在不影响结果的情况下,保证了被减数 >= 减数
    //此外,我们还要明白a < b的两种情况。
    //第一种就是a的位数小于b的位数 a = 1, b = 213   a < b
    //第二种情况就是a的位数等于b的位数,但是a某些位上的值小于b     
    //a = 111, b = 199    a < b
    if(a.size() < b.size() || (a.size() == b.size() && a < b)) {
        swap(a, b);
        cout << "-";
    }

    vector<int> v1, v2;

    for(int i = a.size() - 1; i >= 0; i--) v1.push_back(a[i] - '0'); 

    for(int i = b.size() - 1; i >= 0; i--) v2.push_back(b[i] - '0'); 

    auto v3 = sub(v1, v2);

    for(int i = v3.size() - 1; i >= 0; i-- ) printf("%d", v3[i]);

    return 0;
}

没有注释

#include <iostream>
#include <vector>

using namespace std;

vector<int> sub(vector<int> v1, vector<int> v2) {
    vector<int> v3;

    int temp = 0;

    for(int i = 0; i < v1.size(); i++) {
        temp += v1[i];

        if(i < v2.size()) temp -= v2[i];

        v3.push_back((temp + 10) % 10);

        if(temp >= 0) temp = 0;
        else temp = -1;
    }

    while(v3.size() > 1 && v3.back() == 0) v3.pop_back();

    return v3;
}

int main() {
    string a, b;
    cin >> a >> b;

    if(a.size() < b.size() || (a.size() == b.size() && a < b)) {
        swap(a, b);
        cout << "-";
    }

    vector<int> v1, v2;

    for(int i = a.size() - 1; i >= 0; i--) v1.push_back(a[i] - '0'); 

    for(int i = b.size() - 1; i >= 0; i--) v2.push_back(b[i] - '0'); 

    auto v3 = sub(v1, v2);

    for(int i = v3.size() - 1; i >= 0; i-- ) printf("%d", v3[i]);

    return 0;
}



yysh
25天前

正整数高精度加法

思路

模拟人为的竖式加法

#include <iostream>
#include <vector>

using namespace std;

//获取地址是为了提高效率,如果不添加&的话
//系统会把整个vector拷贝一遍,然后赋值给add中的形参
//如果添加了,就是直接作用到地址,不需要拷贝
//和普通的数组不一样,普通的数组是引用传递,而向量数组是拷贝传递
//所以,为了提高效率,建议加上&
vector<int> add(vector<int> &v1, vector<int> &v2) {
    int temp = 0;

    vector<int> v3;
    //循环要确保遍历完v1和v2两个数组,避免遗漏
    for(int i = 0; i < v1.size() || i < v2.size(); i++) {
        if(i < v1.size()) {
            temp += v1[i];
        }

        if(i < v2.size()) {
            temp += v2[i];
        }

        //从低位开始存储
        //取余10是为了确保每一位上的数字在0 - 9这个范围内
        v3.push_back(temp % 10);

        //除以10是为了检查是否有进位,如果有,下一次循环计算的时候temp = 1;
        //反正,如果没有,temp = 0,会避免该次计算影响下一次计算
        temp /= 10;
    }

    //因为循环的最后一次操作是检查temp是否可以进位
    //如果最后一次的temp可以进位(数组的最高位可以进位),我们需要在循环外面处理,避免遗漏
    if(temp) v3.push_back(temp);

    return v3;
}

int main() {
    string a, b;

    cin >> a >> b;

    vector<int> v1, v2;
    //字符串开头的是最高位,我们要保证低位在数组中是开头,所以要倒序存入
    for(int i = a.size() - 1; i >= 0; i--) v1.push_back(a[i] - '0');

    for(int i = b.size() - 1; i >= 0; i--) v2.push_back(b[i] - '0');

    auto v3 = add(v1, v2);

    //由于我们存入数组的时候,开头是低位,所以我们运算的时候,是从数组的前面走向后面的
    //所以,对于一个数组来说,下标小的位置是低位,下标大的位置是高位
    //当我们要对答案进行输出的时候必须考虑到这一点,即,高位在数组后面,低位在数组前面
    //所以,为了输出符合题目要求的答案,我们需要倒序输出
    for(int i = v3.size() - 1; i >= 0; i--) {
        printf("%d", v3[i]);
    }

    return 0;
}




yysh
1个月前

思路

这个题目看上去比较难处理。但是实际上是比较简单的。
题目给我们一个01字符串,要求我们对0字符进行删除操作,让所有的1字符串变成连续的字符串,并且返回0字符的最小的删除次数。
我们通常情况下,想的是从头到尾遍历,找到某种规律,然后进行贪心。
我刚开始看的时候,也觉得好像是一个贪心问题。但后面想了想,这个题其实是一道思维题。
首先我们假设一个01字符串:
00011110101100110011101000110000

在进行删除操作之前,我们可以发现,有一部分的0是不需要我们进行处理的,它们的存在对1字符组成连续的字符串没有任何影响。
那么,哪些0字符是不需要我们进行处理的呢?
很明显,最左边的1之前的0,以及最右边的1之后的0,这两个地方的0是不需要我们进行处理的。
因为这两个位置不存在1字符串。
那么,我们需要处理的0的范围就确定了——[最左边1的位置, 最右边1的位置]
这个区间,就是我们需要删除0的范围。
确定这个范围之后,我们对这个区间进行遍历,找出0的个数即可。
步骤:
1、确定处理区间的左端点
2、确定处理区间的右端点
3、遍历区间,统计0的个数

值得注意的是,我们需要设置一个条件来判断字符串中一个1都没有的特别情况。

代码实现

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;

    while(t--) {
        int cnt = 0;
        string s;
        //检查是否是全0的特殊情况
        bool ps = false;
        cin >> s;

        int l = 0, r = s.size() - 1;

        //处理左边的0
        for(int i = 0; i < s.size(); i++) {
            if(s[i] != '0') {
                l = i;
                ps = true;
                break;
            } 
        }

        //处理右边的0
        for(int i = s.size() - 1; i >= 0; i--) {
            if(s[i] != '0') {
                r = i;
                ps = true;
                break;
            }
        }

        //统计最左边的1和最右边的1之间0的个数
        for(; l <= r; l++) {
            if(s[l] == '0') cnt++;
        }

        if(ps) {
          printf("%d\n", cnt); 
        } else {
          printf("0\n");
        }

    }

    return 0;
}



yysh
1个月前

思路

位权展开转换为10进制,然后判断个位的数

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt = 0;

    long long ans = 0;

    for(int i = s.size() - 1; i >= 0; i--) {
        if(s[i] >= '0' && s[i] <= '9') {
            long long num = pow(16, cnt);
            ans += (s[i] - '0') * num;
            cnt++;
        } else {
            long long num = pow(16, cnt);
            ans += (s[i] - 'A') * num;
            cnt++;
        }
    }

    ans %= 10;
    if(ans % 2 == 0) {
        cout << 0;
    } else {
        cout << 1;
    }

    return 0;
}



yysh
1个月前

思路

从2开始进行质因数分解,当n % i == 0的时候,说明我们遇见了一个质因数,cnt++。然后进入循环,以当前的约数为除数
让n不断的除以当前的约数,直到不能整除。这一步的作用是为了保障之后n % i等于0的时候,i是质数
由于n可能很大,且本身是一个质数,那么,我们设置i的时候,应该把i也设置为较大的数据类型,避免报错
最后退出整个循环的时候,我们需要检查当前的n。
由于我们不可能使用完全的暴力进行判断,这样肯定会超时,所以,我们的判断范围是化简过的。
其次,由于我们进行了化简,那么数n的约数判断范围会缩小,众所周知,约数都是成对出现的,如果在小约数的时候结束了循环,那么,n的大约数我们就肯可能会遗漏。所以,当结束所有循环的时候,我们需要判断当前的n是否是质因数

#include<iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    int cnt = 0;

    for(long long i = 2; i <= n / i; i++) {
        if(n % i == 0) {
            cnt++;
            while(n % i == 0) {
                n /= i;
            }
        }
    }

    if(n > 1) cnt++;

    cout << cnt;

    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

yysh
1个月前

scanf(“%d%d%d”, &n, &m, &q);
//n是行数 m是列数 q是询问次数
for (int i = 1; i <= n; i )
for (int j = 1; j <= m; j
) //这是把数 录入进二维数组
scanf(“%d”, &s[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];//二维数组的每一位前缀和 都用这个公式表示

while (q -- )
{
    int x1, y1, x2, y2;                         //接下来就是输出  矩阵的前缀和了  x1 y1  x2  y2  给的是矩阵范围的坐标
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

return 0;