C/C++教程

codeforces365C(数学)

本文主要是介绍codeforces365C(数学),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

365C

题意:

给定一个长度为n的字符串s,组成一个数组b,其中b[i,j]=s[i]xs[j],问有多少个矩阵的和等于给定的数字a

思路:

考虑一般情况:假设子矩阵是左上角是(x,y),右下角是(xn,yn);
则这个矩阵的和可以表示为
第一行是:

\[s[x]*s[y]+s[x]*s[y+1]+s[x]*s[y+2]+...+s[x]*s[y_{n}] \]

化简得:

\[s[x]*(s[y]+s[y+1]+s[y+2]+...+s[y_{n}]) \]

一共有n行,所以总矩阵大小就是:

\[(s[x]+s[x+1]+s[x+2]+...+s[x_{n}])*(s[y]+s[y+1]+s[y+2]+...+s[y_{n}]) \]

所以可以预处理出来所有区间的前缀和,然后枚举,求a/s[len]的个数即可

题解:

#include <bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define lowbit(x) x&(-x)
#define INF 0x7fffffff
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);};
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
char s[4010];
int ss[4010];
void solve() {
    int a;
    cin >> a;
    cin >> (s + 1);
    int n = strlen(s + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++) ss[i] = ss[i - 1] + s[i] - '0';
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            int x = ss[r] - ss[l - 1];
            mp[x]++;
        }
    }
    int cnt = 0;
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            int x = ss[r] - ss[l - 1];
            if(a==0) cnt+=mp[0];//a为0的情况特判;
            if(x==0) continue;//x为0避免对0取模,
            if (a % x == 0) {
                cnt += mp[a / x];
            }
        }
    }
    cout << cnt << endl;
}
signed main() {
    IOS;
    solve();
    return 0;
}
这篇关于codeforces365C(数学)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!