zhangas

Pay more attention

0%

Daily Problems

Posted on Edited on

数位排序 前缀和与差分

若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)
设b[]是 a[]的差分 先将a的[l,+∞]加上c 再讲a[r+1,+∞]减去c

1
2
3
4
void insert(int l,int r){
    b[l]+=c;
    b[r+1]-=c; 
}

统计出现的次数cnt[]记录

1
2
3
4
5
6
7
8
9
10
11
12
while(m--){
    int l,r;scanf("%d%d",&l,&r);
    //如果直接嵌套循环会TLE
    //for(int i=l;i<=r;i++)cnt[i]++;
    //转化为差分 在循环外面求差分
    cnt[l]++;cnt[r+1]--;
}
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
sort(a+1,a+n+1);sort(cnt+1,cnt+1+n);
ll sum2=0;
for(int i=1;i<=n;i++)sum2+=cnt[i]*a[i];
printf("%lld",sum2-sum1);

孤独的照片

给一个只含’A’,’B’两种字符的字符串
找出所有字串中 含有单个元素的个数
input：
5
GHGHG
output：
3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
易知'A'和'B'地位相同
情况分为两种
① AAB BAAA B前面或者后面A的个数-1 即为方案数
② ABA ABAA B前后A的个数之积 即为方案数
先预处理打上序号
const int N=5e5+5;
ll g[2][N],h[2][N];
//第0行表示从前往后连续出现的个数
//第1行表示从后往前连续出现的个数
for(int i=1;i<=n;i++){
    if(c[i]=='H') h[0][i]=h[0][i-1]+1;
    else g[0][i]=g[0][i-1]+1;
}
for(int i=n;i>=1;i--){
    if(c[i]=='H') h[1][i]=h[1][i+1]+1;
    else g[1][i]=g[1][i+1]+1;
}
//遍历计算两种方案
ll ans=0;
for(int i=1;i<=n;i++){
    if(c[i]=='H'){
        if(c[i-1]=='G'&&g[0][i-1]>1) ans+=g[0][i-1]-1;
        if(c[i+1]=='G'&&g[1][i+1]>1) ans+=g[1][i+1]-1;
        if(c[i-1]=='G'&&c[i+1]=='G') ans+=g[0][i-1]*g[1][i+1];
    }
    else{
        if(c[i-1]=='H'&&h[0][i-1]>1) ans+=h[0][i-1]-1;
        if(c[i+1]=='H'&&h[1][i+1]>1) ans+=h[1][i+1]-1;
        if(c[i-1]=='H'&&c[i+1]=='H') ans+=h[0][i-1]*h[i+1];
    }
}cout<<ans<<endl;

统计次数 记忆化递归

求从1到n这n个正整数的十进制表示中 k出现的次数。
1≤ n≤ 10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1e6+5;
int f[N],v[N]={1};//v[0]=1 && f[0]=0;
int count(int i,int k){
    if(v[i]) return f[i];
    f[i]=f[i/10]+(i%10)==k;
    v[i]=1;
    return f[i];
}
int main(){
    int n,k;cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=count(i,k);
    }
    cout<<ans<<endl;
}

上课睡觉 数论

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。本题一定有解，因为可以将所有石子堆合并为一堆。
1≤ N ≤10^5

设操作x次成功 合并后有N-x堆
设每组有y个 y*(N-x)=Σai
性质有 sum%y==0 当y最小时 x也取到最小
可以从小到大枚举sum的因数 并检测一下是否符合题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N=1e5+5;
int n;
int a[N];
bool check(int y){
    int t=0;
    for(int i=1;i<=n;i++){
        t+=a[i];
        if(t==y)t=0;
        else if(t>y)return false;
    }
    return true;
}
void volve(){
    int mx=0,sum=0;
    cin>>n;for(int i=1;i<=n;i++){
        cin>>a[i];sum+=a[i];mx=max(a[i],mx);
    }
    if(mx==0){
        cout<<"0"<<endl;
        return;
    }
    //枚举sum的因数并检查是否符合 找出最小的y即可
    for(int i=mx;i<=sum;i++){
        if(sum%i==0&&check(i)){
            cout<<n-sum/i<<endl;
            return;
        }
    }

}
int main(){
    int t;cin>>t;
    while(t--)solve();
    return 0;
}