当前位置：首页 > news >正文

CF364

news 来源：原创 2024/4/29 22:41:50

链接：http://codeforces.com/contest/364

A:Matrix

关于矩阵。。。

Let's notice that sum in the rectangle (x1, y1, x2, y2) is sum(x1, x2)·sum(y1, y2). Where sum(l, r) = sl + sl + 1 + ... + sr. Then, we have to calc sum(l, r) for every pair (l, r) and count how many segments give us sum x for any possible x (0 ≤ x ≤ 9·|s|). In the end we should enumerate sum on segemnt [x1, x2] and find $\text{[math]}$ . There is corner case a = 0.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 #define LL long long
 6 const int maxn=4010;
 7 LL n;
 8 char s[maxn];
 9 LL a[maxn][maxn],sum[maxn][maxn];
10 int main()
11 {
12     cin>>n>>s+1;
13     int len=strlen(s+1);
14     for(int i=1;i<=len;i++)
15         for(int j=1;j<=len;j++)
16         a[i][j]=(s[i]-'0')*(s[j]-'0');
17     for(int i=1;i<=len;i++)
18         for(int j=1;j<=len;j++)
19             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
20             LL ans=0;
21     for(int i=1;i<=len;i++)
22         for(int j=1;j<=len;j++)
23             for(int k=1;k<=i;k++)
24                 for(int l=1;l<=j;l++)
25         if(sum[i][j]+sum[k-1][l-1]-sum[i][l-1]-sum[k-1][j]==n) ans++;
26            cout<<ans<<endl;
27 }

我的一看就超时的代码

 1 #include <cstdio>
 2 #include <numeric>
 3 #include <iostream>
 4 #include <vector>
 5 #include <set>
 6 #include <cstring>
 7 #include <string>
 8 #include <map>
 9 #include <cmath>
10 #include <ctime>
11 #include <algorithm>
12 #include <bitset>
13 #include <queue>
14 #include <sstream>
15 #include <deque>
16 
17 using namespace std;
18 
19 #define mp make_pair
20 #define pb push_back
21 #define rep(i,n) for(int i = 0; i < (n); i++)
22 #define re return
23 #define fi first
24 #define se second
25 #define sz(x) ((int) (x).size())
26 #define all(x) (x).begin(), (x).end()
27 #define sqr(x) ((x) * (x))
28 #define sqrt(x) sqrt(abs(x))
29 #define y0 y3487465
30 #define y1 y8687969
31 #define fill(x,y) memset(x,y,sizeof(x))
32                          
33 typedef vector<int> vi;
34 typedef long long ll;
35 typedef long double ld;
36 typedef double D;
37 typedef pair<int, int> ii;
38 typedef vector<ii> vii;
39 typedef vector<string> vs;
40 typedef vector<vi> vvi;
41 
42 template<class T> T abs(T x) { re x > 0 ? x : -x; }
43 
44 const int N = 40000;
45 
46 int n;
47 int m;
48 string s;
49 
50 int cnt[N];
51 
52 int main () {
53     cin >> m >> s;
54     n = sz (s);
55     for (int i = 0; i < n; i++) {
56         int cur = 0;
57         for (int j = i; j < n; j++) {
58             cur += s[j] - '0';
59             cnt[cur]++;
60         }
61     }
62     ll ans = 0;
63     if (m == 0) {
64         int all = n * (n + 1) / 2;
65         ans += (ll)all * all - (ll)(all - cnt[0]) * (all - cnt[0]);
66     } else {
67         for (int i = 1; i * i <= m && i < N; i++)
68             if (m % i == 0 && m / i < N) {
69                 int j = m / i;
70                 if (i != j) ans += (ll)2 * cnt[i] * cnt[j]; else ans += (ll)cnt[i] * cnt[i];
71             }
72     }
73     cout << ans << endl;
74     return 0;
75 }

一号

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <list>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <stack>
 9 #include <vector>
10 #include <cmath>
11 #include <cstring>
12 #include <string>
13 #include <iostream>
14 #include <complex>
15 #include <sstream>
16 using namespace std;
17  
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 typedef long double LD;
21 typedef vector<int> VI;
22 typedef pair<int,int> PII;
23  
24 #define REP(i,n) for(int i=0;i<(n);++i)
25 #define SIZE(c) ((int)((c).size()))
26 #define FOR(i,a,b) for (int i=(a); i<(b); ++i)
27 #define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
28 #define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)
29 #define ALL(v) (v).begin(), (v).end()
30  
31 #define pb push_back
32 #define mp make_pair
33 #define st first
34 #define nd second
35 
36 LL gcd(LL a, LL b) {
37     return b ? gcd(b,a%b) : a;
38 }
39 
40 char S[5000];
41 int su[5000];
42 int main() {
43     int A;
44     scanf("%d", &A);
45     scanf("%s", S);
46     int N = strlen(S);
47     REP(i,N) S[i] -= '0';
48     
49     map<int,int> C;
50     su[0] = 0;
51     FOR(i,1,N+1) su[i] = S[i-1] + su[i-1];
52     
53     map<int,int> M;
54     REP(i,N+1)REP(j,i) M[su[i] - su[j]]++;
55 
56     if (A == 0) {
57         LL Y = (N + 1) * N / 2;
58         LL X = M[0];
59         cout << (Y * Y - (Y - X) * (Y - X)) <<  endl;
60         return 0;
61     }
62 
63     LL result = 0;
64     for (int a = 1; a * a <= A; ++a) {
65         if (A % a) continue;
66         LL X = M[a];
67         LL Y = M[A / a];
68     
69         result += X * Y;
70         if (a * a != A) result += X * Y;
71     }
72     
73     cout << result << endl;
74 }