蓝桥杯（杂题1）

取模运算的使用 AcWing

1230. K倍区间

https://www.acwing.com/problem/content/description/1232/

思路： 取模转化 + 前缀和

观察到有k倍 or 倍数关系的题目，尽量可以往取模分析来想。
先维护一段前缀和，转化为前缀和%k为0的组合, 两个取模相等的前缀和就能组成一个k倍区间。注意：取模为零的前缀和即可以单独满足条件（从0起）
由 (sum[r] - sum[|-1])%k = 0
推出 sum[r]%k = sum[|-1]%k

#include
using namespace std;
long long a[100010];
long long s[100010];
long long res[100010];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
        s[i] = s[i-1] + a[i];
    }
    long long num=0;
    long long ans;
    for(int i=1;i<=n;i++){
        ans = s[i] % m;
        res[ans]++;
        num += res[ans]-1;          //两个相等的前缀和就能组成一个k倍区间
    }
    num += res[0];                  //模为零 本身就可
    cout << num << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1214. 波动数列

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

思路：动态规划

先进行dp的状态方程推导
后利用模n的余数相同来进行转化
分析可知 系数和下标之和为n，所以第i项的的系数为n-i

#include

using namespace std;

int get_mod(int a,int b){       // 为了让负数取模变为正数
    return (a%b+b)%b;
}
const int N = 1010, MOD = 100000007;
int f[N][N];

int main(){
    int n,s,a,b;
    cin >> n >> s >> a >> b;
    f[0][0]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<n;j++){
            f[i][j] = (f[i-1][get_mod(j-(n-i)*a,n)] + f[i-1][get_mod(j+(n-i)*b,n)])%MOD;
        }
    
    printf("%d", f[n - 1][get_mod(s, n)]);
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22