头像

Ulyson




离线:2天前


问题 内存超限

Ulyson
5个月前

题目https://www.acwing.com/problem/content/218/
那个错误代码交上去是内存超限
把那两行超长注释符的句子注释掉是finish,不超了
我很好奇c矩阵也就1e7的int不到也能内存超限?
我一开始以为是异或有问题但用c【1】【i】【j】也是内存超限
并且注释掉那两行后,下面的遍历c也没有问题,真是玄学

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
typedef double db;
typedef unsigned long long ull;
#define fi first
#define se second
#define pk push_back
#define mk make_pair

const ll N=1e5+10, M=40, mod=1e9+7, inf=0x3f3f3f3f3f3f3f3f, Max=5e4;
const int iinf=0x3f3f3f3f;
const ll seed=233, hashmod=1e9+7;//哈希
const db esp=1e-7;

int n, a[N], last0[N][M], last1[N][M], c[4][N][M];
bool att[N][M], b[N][M];
// int aaa[200][100005];


void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        for(int j=0;j<31;j++){
            b[i][j]=(a[i]>>j)&1;
        }
    }

    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            last0[i][j]=last0[i-1][j];
            last1[i][j]=last1[i-1][j];
            if(b[i][j])
                last1[i][j]=i;
            else
                last0[i][j]=i;
        }
    }

    for(int j=0;j<31;j++){
        int flag=0;
        for(int i=1;i<=n;i++){
            att[i][j]=flag;
            c[flag][i][j]=c[flag][i-1][j]+1;
            c[1][i][j]=c[1][i-1][j];//////////////////////////////
            // if(b[i][j]) flag=flag?0:1;////////////////////////
        }
    }

    double axor=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            int flag=att[i][j];
            if(b[i][j])
                axor+=1.0*(1<<j)*(c[flag][i][j]-1)*2/n/n,
                        axor+=1.0*(1<<j)/n/n;//ok
            else
                axor+=1.0*(1<<j)*c[flag^1][i][j]*2/n/n;
        }
    }
    printf("%.3f ",axor);

    db aand=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            if(b[i][j]==1)
                aand+=1.0*(1<<j)*(i-last0[i][j]-1)*2/n/n,
                        aand+=1.0*(1<<j)/n/n;
        }
    }
    printf("%.3f ",aand);

    db aor=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            if(b[i][j]==1){
                aor+=1.0*(1<<j)*(i-1)*2/n/n;
                aor+=1.0*(1<<j)/n/n;
            }else{
                aor+=1.0*(1<<j)*(last1[i][j])*2/n/n;
            }
        }
//cout<<j<<" "<<(1<<j)<<"  "<<aand<<endl;
    }
    printf("%.3f",aor);

    return ;
}
int main() {
//     freopen("C:\\Users\\lenovo\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\lenovo\\Desktop\\out.txt","w",stdout);
//    ll t;
//    cin>>t;
//    for(ll i=1;i<=t;i++)
    work();

    return 0;
}






Ulyson
8个月前

题目 ABC 171F (要梯子)
大意就是:给一个len长的小写字母字符串s,然后你可以随意的把26个小写字母插进s,直到s长n,求可以构成多少不同的长度为n的字符串
就只是问两个简单的问题:
这个怎么算?
为什么答案与串s内容无关,只有长度有关?
答案貌似是 : sum(i=len~n) { C(n,i) 25^(n-i) }
需要注意的是:比如说off,可以是of _ f,也可以是off_ ,但直接的c的话又会有 offf,对于f插入会重复计算,第1个是插入和第2个是插入,第3个是插入都是算一个




Ulyson
8个月前

同余方程ax+by=c mod m, 用exgcd(a,b,x,y)求得的x和y的范围怎么求?
https://codeforces.com/problemset/problem/1244/C
这道题目用exgcd求x,y暴ll了



问题 Python和pypy

Ulyson
10个月前

听说Python好慢,运行时间好像是c的20多倍
但pypy好像还不错
两个问题求答:
1.请问pypy的语法和Python是一样的吗?(我看了下代码,貌似一样)
2.打acm的话好像可以用Python,那么这里的Python是Python3还是pypy3呢?




Ulyson
10个月前
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    stringstream s;
    s.precision(0);
    s<<fixed<<pow(2.0L,n+1);  //将pow后存进去
    string a=s.str();    //放到a中,这里个位数只能是2,4,8,6
    a[a.length()-1]--;
    a[a.length()-1]--;   //减去2,不会影响上一行
    cout<<a<<endl;
    return 0;
}

这两句什么意思

s.precision(0);
s<<fixed<<pow(2.0L,n+1);

另外有没有大佬知道关于stringstream在算法竞赛中应用的较详细博客




Ulyson
11个月前

for(auto i:se)的i是什么

set<int> se;
for(auto i:se){
        if(*i!=se.begin()) cout<<" ";
        cout<<i; 
    }

上面报错,主要是刷pta的时候要求末尾不能有多余的空格,
所以用auto的时候就不知道怎么判断当前是不是第一个(即begin())
正常是数组的时候是这样的

for(int i=0;i<n;i++){
    if(i).......
    cout<<.........
}

所以这里问下for(auto i:se)怎么判断现在是第一次遍历或者判i是不是se的begin



问题 求逆

Ulyson
2020-01-13 03:03

https://www.acwing.com/problem/content/225/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e3+10;
int n;
ll a[N],b[N],M,m[N],infm[N],y,ans;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    M=1;
    for(int i=0;i<n;i++) M*=a[i];
    for(int i=0;i<n;i++) m[i]=M/a[i],exgcd(m[i],a[i],infm[i],y);
    for(int i=0;i<n;i++) ans=(ans+b[i]*m[i]*infm[i])%M;
    cout<<(ans%M+M)%M<<endl;
    return 0;
}

这里exgcd(m[i],a[i],infm[i],y)是求m【i】的逆
就是
m*m^-1=1(mod a)
=> m * m^-1=1+ y * a
=> m * m^-1 - a * y=1
为什么exgcd(m[i],-a[i],infm[i],y); 的答案是错的?




Ulyson
2019-10-28 07:26

(a * b * c)/d%MOD
abc%d==0
现在已知ab在longlong范围内,但ab*c/d会爆longlong,怎么把%MOD放到前面,如果可以能不能写下证明




Ulyson
2019-10-26 13:05

(另类的扩展欧几里得)

直接上代码了(纯属学术交流,不建议实战)

#include<bits/stdc++.h>
using namespace std;

int n,a,b,x,y;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int tmp=y;
    y=x-a/b*y;
    x=tmp;
    return d;
}

int main(){
    cin>>n;
    while(n--){
        x=y=0;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}




Ulyson
2019-10-03 12:33

dp相对于暴力优化了什么
就比如:输入一个数n,求n分解成质数相加方法数,如:7=7=2+5=2+2+3,方法数为3
我想的暴力是:
先线性求出1~n的质数
然后递归遍历相加质数直到sum>=n

然而dp是dp【i】=dp【i】+dp【i-质数】

dp优化了什么?为什么dp用的时间少,他们两个不是都考虑了所有情况吗

暴力代码:

#include <iostream>

using namespace std;

int cnt,n,ans;
int prime[1005];
bool st[1005];

void work(int sum,int no){
    if(sum==n) {
        ans++;return;
    }
    else if(sum>n) return;
    for(int i=no;prime[i]+sum<=n&&i<cnt;i++){
        work(prime[i]+sum,i);
//printf("%d\n",prime[i]+sum);      
    }

}
int main(int argc, char** argv) {
    cin>>n;

    for(int i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }

//  puts("this");

    work(0,0);
    cout<<ans;
    return 0;
}