ABC383入门组题解

A循环模拟

#include <stdio.h>
int n, m, i, j, k, p, s, a, b;
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &a, &b);
        s -= a-p;//等多久水就少多少
        if(s < 0) s = 0;//最少为0
        s += b, p = a;//增加b的水量
    }
    printf("%d\n", s);
    return 0;
}

B枚举统计

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, x, y, c, d, ans, t[15][15];
char s[15][15];
void tu(int x, int y, int k){
    int i, j;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            if(s[i][j] != '.') continue;
            if(abs(i-x)+abs(j-y) > d) continue;
            if(t[i][j] != k) t[i][j] = k, c++;
        }//第k次统计标记为k，这样可以避免重复计算
    }
    if(c > ans) ans = c;
}
int main(){
    scanf("%d%d%d", &n, &m, &d);
    for(i=1; i<=n; i++){
        scanf("%s", s[i]+1);
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            if(s[i][j] != '.') continue;
            for(x=1; x<=n; x++){
                for(y=1; y<=m; y++){
                    if(s[x][y] != '.') continue;
                    c = 0, k++;//暴力枚举两个地板，重复没影响
                    tu(i, j, k);//统计周围的地板
                    tu(x, y, k);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

C广搜原理

#include <stdio.h>
#define N 1005
int n, m, i, j, k, x, y, xx, yy, d, f[N][N], q[N*N];
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
char s[N][N];
int main(){
    scanf("%d%d%d", &n, &m, &d);
    for(i=1; i<=n; i++){
        scanf("%s", s[i]+1);
        for(j=1; j<=m; j++){
            if(s[i][j] == 'H'){
                f[i][j] = 1, q[++k] = i*N+j;
            }//必须一次广搜，分次广搜会有重复，退化成深搜
        }
    }
    for(i=1, j=k; i<=j; i++){
        x = q[i]/N, y = q[i]%N;
        if(f[x][y] > d) break;
        for(k=0; k<4; k++){
            xx = x+dx[k], yy = y+dy[k];
            if(s[xx][yy]=='.' && !f[xx][yy]){
                f[xx][yy] = f[x][y] + 1;
                q[++j] = xx*N + yy;
            }
        }
    }//广搜模板
    printf("%d\n", j);
    return 0;
}

D数论筛法枚举

整数的唯一分解定理：

n = p_1^x * p_2^y * p_3^z ...

每种质因子留下多少个？0~x个、0~y个、0~z个……
约数个数为： (x+1) * (y+1) * (z+1) * ...
9个约数，要么1个质因子8次方，要么2个质因子都是2次方。

#include <stdio.h>
#define LL long long
const LL N = 2e6+7;
LL n, m, i, j, k, s, ans, a[N], p[N], f[N];
int main(){
    scanf("%lld", &n);
    for(m=2; m*m<=n; m++) ;//暴力算开根1次不超时
    for(i=2; i<=m; i++){
        if(f[i]) continue;
        a[++k] = i, p[k] = i*i;
        for(j=i+i; j<=m; j+=i) f[j] = 1;
    }//筛法预处理质数和平方
    for(i=1; i<=k; i++){
        if(p[i] >= n) break;
        for(j=i+1; j<=k; j++){
            if(p[j] <= n/p[i]) ans++;
            else break;//保证时间复杂度 
        }//嵌套循环，时间复杂度为O(方案) 
        for(s=j=1; j<9; j++){
            s = s * a[i];//逐个乘避免爆LL 
            if(s > n) break;
        }
        if(j >= 9) ans++;//8次方 
    }//约数个数为：(x+1)*(y+1)*...(z+1) 
    printf("%lld\n", ans);
    return 0;
}