头像

huwahuwa




离线:1天前


最近来访(11)
用户头像
人生如戏ba
用户头像
余天润
用户头像
yxc
用户头像
Vssun
用户头像
负暄
用户头像
srq_conan
用户头像
Agone
用户头像
黑帮大白菜
用户头像
心升明月
用户头像
重生之我是小雪菜
用户头像
德鲁大叔


高精度阶乘和(C语言版)

#include<stdio.h>
#define MAX_SIZE 3000
#define MAX_POS 2999

int result[MAX_SIZE]={0},res_begin=MAX_POS;

//"+"
void Get_Sum(int all[],int begin){
    int end=MAX_POS;
    int temp=0,sum;
    while(end>=begin){
        result[end]+=all[end];
        temp=end;
        while(result[temp]>=10){
            sum=0;
            while(result[temp]>=10){
                sum++;
                result[temp]-=10;
            }
            temp--;
            result[temp]+=sum;
        }
        if(temp<res_begin){
            res_begin=temp;
        }
        end--;
    }
}

//"!"
void Get_Factorial (const int N){
    int factorial[MAX_SIZE];
    for(int i=0; i<MAX_SIZE; i++)
        factorial[i]=-1;
    factorial[MAX_POS]=1;
    int begin=MAX_POS;
    for(int i=N; i>=2; i--){
        int startIndex=MAX_POS;
        int temp=0;
        while(factorial[startIndex]!=-1){
            int total=i*factorial[startIndex]+temp;
            factorial[startIndex]=total%10;
            startIndex--;
            temp=total/10;
        }
        while(temp!=0){
            if(factorial[startIndex]!=-1){
                temp+=factorial[startIndex];
            }
            factorial[startIndex]=temp%10;
            temp/=10;
            begin=startIndex;
            startIndex--;
        }
    }
    Get_Sum(factorial,begin);
}

int main() {
    int i;
    for(i=1; i<=100; i++){
        Get_Factorial(i);
    }
    while(res_begin<=MAX_POS){
        printf("%d",result[res_begin++]);
    }
    return 0;
}

调整主调函数中i的值即可改变求和范围。



新鲜事 原文

huwahuwa
9个月前
对于01背包一维优化的一点理解: 二维转化为一维: 删掉了第一维:在前i个物品中取。 f[j]表示:拿了总体积不超过j的物品,最大总价值。 为何能转化为一维? 二维时的更新方式:f[i][j]=max(f[i - 1][j] ,f[i - 1][j - v[i]] + w[i]); 1.我们发现,对于每次循环的下一组i,只会用到i-1来更新当前值,不会用到i-2及之前值。于是可以在这次更新的时候,将原来的更新掉,反正以后也用不到。 所以对于i的更新,只需用一个数组,直接覆盖就行了。 2.我们发现,对于每次j的更新,只需用到之前i-1时的j或者j-v[i],不会用到后面的值。 所以为了防止串着改,我们采取从后往前更新的方式,用原来i-1的数组来更新i。 (如果从前往后更新的话,前面的更新过之后,会接着更新后面的值,这样就不能保证是用原来i-1的数组来更新i的了) 如何转化为一维呢? 只用一个数组,每次都覆盖前面的数组。 1.如果当前位置的东西不拿的话,和前一位置的信息(原来i-1数组的这个位置上的值)是相同的,所以不用改变。 2.如果当前位置的东西拿了的话,需要和前一位置的信息(原来i-1数组的这个位置上值)取max。 所以,更新方式就为:f[j]=max(f[j],f[j-v[i]]+w[i]); 整个更新方式就相当于: 每次i++,就从后往前覆盖一遍f数组,看每个位置上的值是否更新。 不知道理解的对不对,有问题的话还请各位大佬指正![抱拳]! 作者:yxc 链接:https://www.acwing.com/video/34/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



huwahuwa
10个月前
__int128的输出函数:

void print(__int128 x)
{
    if (!x) return ;
    if (x < 0) putchar('-'),x = -x;
    print(x / 10);
    putchar(x % 10 + '0');
}

//注意:这个函数没有输出0的能力。
//__int128数值范围:大致在1e36左右



#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
    __int128 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;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int main(void){
    __int128 a = read();
    __int128 b = read();
    print(a + b);
    cout << endl;
    return 0;
}
————————————————



huwahuwa
10个月前

···
__int128的输出函数:

void print(__int128 x)
{
if (!x) return ;
if (x < 0) putchar(‘-‘),x = -x;
print(x / 10);
putchar(x % 10 + ‘0’);
}

//注意:这个函数没有输出0的能力。
//__int128数值范围:大致在1e36左右

include [HTML_REMOVED]

using namespace std;
inline __int128 read(){
__int128 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;
}
inline void print(__int128 x){
if(x < 0){
putchar(‘-‘);
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + ‘0’);
}
int main(void){
__int128 a = read();
__int128 b = read();
print(a + b);
cout << endl;
return 0;
}
————————————————
···




huwahuwa
10个月前

include[HTML_REMOVED]

using namespace std;
const int N=20;
int num[20];
int main()
{
int n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>k&1)
{
cout<<num[k]<<” “;
}
}
cout<<endl;
}
}
突发奇想用费解的开关二进制思想也能ac,貌似在时间复杂度边缘QAQ

作者:yxc
链接:https://www.acwing.com/video/579/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。




huwahuwa
10个月前


新鲜事 原文

huwahuwa
11个月前
#include <iostream> using namespace std; const int N = 100010; int n, sum; int s[N]; int main() { cin >> n; s[0] = 2; s[1] = 0; s[2] = 1; s[3] = 9; for (int i = 4; i < n; i ++ ) s[i] = (s[i - 1] + s[i - 2] + s[i - 3] + s[i - 4]) % 10; for (int i = 0; i < n; i ++ ) cout << s[i] << " ", sum += s[i]; cout << endl << sum; }


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

huwahuwa
2021-09-26 14:35
#pragma GCC optimize(3)
#include <iostream>
using namespace std;
const int N = 1010;
int s[N][N];//he[N][N];
int n, m, q, x1, x2, y1, y2;
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);//he[i][j] = 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 --)
    {
        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;
}


活动打卡代码 AcWing 795. 前缀和

huwahuwa
2021-09-26 14:16
#pragma GCC optimize(3)

#include <iostream>
using namespace std;
const int N = 100010;
int n, m, l, r;
int s[N], a[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    while (m -- )
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}


活动打卡代码 AcWing 826. 单链表

huwahuwa
2021-09-26 13:31
#pragma GCC optimize(3)

#include <iostream>
using namespace std;

int head, idx, k, x;
char op;
const int N = 100010;
int e[N],ne[N];

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}

void add(int k, int x) 
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;
    init();
    while (m -- )
    {
        cin >> op;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {     
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i])  cout << e[i] << ' ';
    cout << endl;
    return 0;
}