头像

阿力


访客:2455

离线:17分钟前



阿力
9天前

题目 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个是插入都是算一个




阿力
23天前

同余方程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

阿力
1个月前

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




阿力
2个月前
#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在算法竞赛中应用的较详细博客




阿力
3个月前

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



问题 求逆

阿力
5个月前

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); 的答案是错的?




阿力
8个月前

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




阿力
8个月前

(另类的扩展欧几里得)

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

#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;
}




阿力
9个月前

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;
}



阿力
10个月前

二分查找用快排的思想最好是o(N),但最坏是o(N*N)————就是假设求最大但每次取最前的都是最小时间复杂的N平方