前缀和、双指针

时间复杂度O(n^2)

萌新没怎么写过题解 可能逻辑表达混乱

鼓捣了俩小时终于AC了，大致思路是分别统计等边三角形、等腰三角形、其他三角形 对于非退化三角形的判断: 不需要分别判断 x+y<z x+z<y y+z<x 只需要保证 x<=y<=z x+y<z即可

等边三角形只需要判断木棍数量>=3就好了

  for (int i=1;i<=n;i++) {
    if (a[i].val>=3) sum++;
  }

等腰三角形的思路是先找数量多于2的木棍当作三角形的腰，然后用统计是否能组成非退化三角形

用一层循环遍历一遍满足可组成三角形腰的木棍(即数量>=2)，然后开始在合法木棍左右两侧寻找满足第三条的边 如果第三条边在左侧(小)则所有木棍都符合 如果第三条边在右侧(大)则需要判断 因为len数组是先排序后构造的，固然有序，所以直接用了lower_bound，直接寻找第一个大于等于腰长度两倍的木棍(x+y<z)，这个木棍及其后面的木棍均无法符合组成三角形的要求

        for (int i=1;i<=n;i++) {
            if (a[i].val<2) continue;
            sum+=pre[i-1];
            ll it=lower_bound(len.begin()+1,len.begin()+n+1,a[i].len*2)-len.begin();
            sum+=pre[it-1]-pre[i];
        }

其他三角形(三条边均不一样长) 使用双指针从O(n^3)降到了O(n^2) 遍历i从1到n 用滑动窗口在i左侧反复寻找组成三角形最小的j和右侧最大的k 在j层循环遍历时每找到一个k用前缀和加到总和，就是符合组成三角形的数量

        for (int i=1;i<=n;i++) {
            int k=i+1;
            for (int j=1;j<i;j++) {
                while (k<=n&&a[i].len+a[j].len>a[k].len) {
                    k++;
                }
                sum+=pre[k-1]-pre[i];
            }
        }

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
struct node {
    int len;
    int val;
};
bool cmp(node x,node y) {
    if (x.len<y.len) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;cin>>t;
    while (t--) {
        int n;cin>>n;
        node a[N];
        for (int i=1;i<=n;i++) {
            cin>>a[i].len>>a[i].val;
        }
        sort(a+1,a+n+1,cmp);
        ll sum=0;
        vector<int>len(n+1,0);
        vector<int>pre(n+1,0);
        //构造前缀和数组与len数组
        for (int i=1;i<=n;i++) {
            if (a[i].val>=1) pre[i]++;
            pre[i]+=pre[i-1];
            len[i]=a[i].len;
        }
        //寻找等边三角形
        for (int i=1;i<=n;i++) {
            if (a[i].val>=3) sum++;
        }
        //寻找等腰三角形
        for (int i=1;i<=n;i++) {
            if (a[i].val<2) continue;
            sum+=pre[i-1];
            ll it=lower_bound(len.begin()+1,len.begin()+n+1,a[i].len*2)-len.begin();
            sum+=pre[it-1]-pre[i];
        }
        //寻找其他三角形
        for (int i=1;i<=n;i++) {
            int k=i+1;
            for (int j=1;j<i;j++) {
                while (k<=n&&a[i].len+a[j].len>a[k].len) {
                    k++;
                }
                sum+=pre[k-1]-pre[i];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

对于等边和等腰的一起处理，然后普通的三角形就利用双指针来处理

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5010;
struct node
{
    int len, sum;
    friend bool operator<(node x, node y)
    {
        return x.len < y.len;
    }
} a[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i].len >> a[i].sum;
        sort(a + 1, a + 1 + n);
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i].sum >= 2)
            {
                auto it = lower_bound(a + 1, a + 1 + n, (node){2 * a[i].len, 0});
                ll res = distance(a + 1, it); // 这个res是满足条件的最大解
                // 要区分res里面有没有i这个点，再判断能不能形成等边三角形
                if (i<=res && a[i].sum<3)
                --res;
                ans+=res;
            }
        for (int i = 1; i <= n - 2; ++i)
        {
            int k = i + 1;
            for (int j = i + 1; j <= n - 1; ++j)
            {
                while (k + 1 <= n && a[i].len + a[j].len > a[k + 1].len)
                    ++k;
                ans += k - j;
            }
        }
        cout << ans << "\n";
    }
}