标签：P2119 NOIP2016 const int 魔法阵 long mp ans define

P2119 [NOIP2016 普及组] 魔法阵

传送门

1

我们可以先写出\(O(m^4)\)的暴力

#include <bits/stdc++.h>  
#define int long long  
#define PII pair<int, int>  
using namespace std;  
const int inf = 0x3f3f3f3f;  
const int MOD = 1e9 + 7, N = 4e4 + 5;  
int n, m, ans[N][4];  
  
struct Node  
{  
    int x, id;  
    friend bool operator< (Node x, Node y)  
    { return x.x < y.x; }  
}x[N];  
  
signed main()  
{  
    scanf("%lld%lld", &m, &n);  
    for (int i = 1; i <= n; ++i)  
        scanf("%lld", &x[i].x), x[i].id = i;  
    sort(x + 1, x + 1 + n);  
    for (int a = 1; a <= n; ++a)  
    {  
        for (int b = a + 1; b <= n; ++b)  
        {  
            if (x[a].x == x[b].x) continue;  
            for (int c = n; c > b; --c)  
            {  
                if (4 * x[b].x >= 3 * x[a].x + x[c].x) break;  
                if (x[b].x == x[c].x) continue;  
                for (int d = c + 1; d <= n; ++d)  
                {  
                    if (x[c].x == x[d].x) continue;  
                    if (x[b].x - x[a].x != 2 * (x[d].x - x[c].x)) continue;  
                    ++ans[x[a].id][0], ++ans[x[b].id][1], ++ans[x[c].id][2], ++ans[x[d].id][3];  
                }  
            }  
        }  
    }  
    for (int i = 1; i <= n; ++i)  
        printf("%lld %lld %lld %lld\n", ans[i][0], ans[i][1], ans[i][2], ans[i][3]);  
    return 0;  
}

其实这份代码是优化过一点的
比如

for (int c = n; c > b; --c)  
    if (4 * x[b].x >= 3 * x[a].x + x[c].x) break;  

把\(c\)反着循环，\(c\)会越来越小，如果这条式子现在满足不了，以后也满足不了
分数\(65pts\)

2

接着我们可以看到\(n\)的数据范围比\(m\)小
就会想到计数数组
可写出\(O(n^4)\)的暴力

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 4e4 + 5;
int n, m, ans[N][4], mp[N], x[N];

signed main()
{
    // freopen("magic.in", "r", stdin);
    // freopen("magic.out", "w", stdout);
    scanf("%lld%lld", &m, &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &x[i]), ++mp[x[i]];
    for (int a = 1; a <= m; ++a)
    {
        if (!mp[a]) continue;
        for (int b = a + 1; b <= m; ++b)
        {
            if (!mp[b]) continue;
            for (int c = m; c > b; --c)
            {
                if (!mp[c]) continue;
                if (4 * b >= 3 * a + c) break;
                for (int d = c + 1; d <= m; ++d)
                {
                    if (!mp[d]) continue;
                    if (b - a != 2 * (d - c)) continue;
                    int tmp = mp[a] * mp[b] * mp[c] * mp[d];
                    ans[a][0] += tmp / mp[a], ans[b][1] += tmp / mp[b];
                    ans[c][2] += tmp / mp[c], ans[d][3] += tmp / mp[d];
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%lld %lld %lld %lld\n", ans[x[i]][0], ans[x[i]][1], ans[x[i]][2], ans[x[i]][3]);
    return 0;
}

分数: \(75pts\)

3

因为题目中说了 \(X_b-X_a=2(X_d-X_c)\)
所以，我们可以只枚举\(X_a, X_b, X_c\)

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7, N = 4e4 + 5;
int n, m, ans[N][4], mp[N], x[N];

signed main()
{
    // freopen("magic.in", "r", stdin);
    // freopen("magic.out", "w", stdout);
    scanf("%lld%lld", &m, &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &x[i]), ++mp[x[i]];
    for (int a = 1; a <= m; ++a)
    {
        if (!mp[a]) continue;
        for (int b = a + 1; b <= m; ++b)
        {
            if (!mp[b]) continue;
            if ((b - a) % 2) continue; // 因为式子是(b - a + 2 * c) / 2，c * 2一定是偶数，那么 b - a 也得是偶数
            for (int c = m; c > b; --c)
            {
                if (!mp[c]) continue;
                if (4 * b >= 3 * a + c) break;
                int d = (b - a + 2 * c) / 2;
                if (!mp[d]) continue;
                int tmp = mp[a] * mp[b] * mp[c] * mp[d];
                ans[a][0] += tmp / mp[a], ans[b][1] += tmp / mp[b];
                ans[c][2] += tmp / mp[c], ans[d][3] += tmp / mp[d];
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%lld %lld %lld %lld\n", ans[x[i]][0], ans[x[i]][1], ans[x[i]][2], ans[x[i]][3]);
    return 0;
}

分数: \(85pts\)

4

我们可以知道

这样， 中间的\(>6x\)的数量可以用后缀和处理

\[\displaystyle C[i]+=\sum_{j=1}^{j+8x<i}mp[j]\times mp[j+2t]\times mp[i+t] \\ C[i] += mp[i+t]*\sum^{j+8t<i}_{j=1}cnt[j]\times cnt[j+2t] \\ \]

#include <bits/stdc++.h>  
#define int long long  
#define PII pair<int, int>  
using namespace std;  
const int inf = 0x3f3f3f3f;  
const int MOD = 1e9 + 7, N = 4e4 + 5;  
int n, m, ans[N][4], mp[N], val[N];  
  
signed main()  
{  
    // freopen("magic.in", "r", stdin);  
    // freopen("magic.out", "w", stdout);  
    scanf("%lld%lld", &m, &n);  
    for (int i = 1; i <= n; ++i)  
        scanf("%lld", &val[i]), ++mp[val[i]];  
    for (int x = 1; 9 * x + 1 <= n; ++x)  
    {  
        int sum = 0;  
        int x7 = x * 7, x8 = x * 8, x9 = x * 9, x2 = x * 2;  
        for (int i = x9 + 2; i <= n; ++i)  
        {  
            sum += mp[i - x7 - 1] * mp[i - x9 - 1];  
            ans[i - x][2] += mp[i] * sum;  
            ans[i][3] += mp[i - x] * sum;  
        }  
        sum = 0;  
        for (int i = n - x9 - 1; i >= 1; --i)  
        {  
            sum += mp[i + x8 + 1] * mp[i + x9 + 1];  
            ans[i][0] += mp[i + x2] * sum;  
            ans[i + x2][1] += mp[i] * sum;  
        }  
    }  
    for (int i = 1; i <= n; ++i)  
        printf("%lld %lld %lld %lld\n", ans[val[i]][0], ans[val[i]][1], ans[val[i]][2], ans[val[i]][3]);  
    return 0;  
}

标签：P2119,NOIP2016,const,int,魔法阵,long,mp,ans,define
From： https://www.cnblogs.com/wanghaoze121126/p/18335659