首页 > 其他分享 >abc258 G - Triangle

abc258 G - Triangle

时间:2023-01-11 23:34:21浏览次数:37  
标签:Triangle int cin ++ 64 3000 abc258

题意:

给定图的邻接矩阵,问三元环的数量

\(n\le 3000\)

思路:

\(O(n^3)\) 的最naive的暴力,用 bitset 优化到 \(O(n^3/64)\)

暴力搜 \((i,j)\),则另外两个点 \((i,k),(j,k)\) 在同一列

Since \(\frac{3000^3}{64}=421875000\) \(\simeq\) \(4\) \(\times\) \(10^8\), this solution is fast enough. We may further halve the execution time by only searching \((i,j)\) such that \(i< j\).

// 850ms
void sol() {
    int n; cin >> n;
    vector<bitset<3000> > a(n);
    for(int i = 0; i < n; i++) {
        string s; cin >> s;
        for(int j = 0; j < n; j++)
            a[i][j] = s[j] == '1';
    }
    long long ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            if(a[i][j]) ans += (a[i] & a[j]).count();
    cout << ans / 3;
}

标签:Triangle,int,cin,++,64,3000,abc258
From: https://www.cnblogs.com/wushansinger/p/17045193.html

相关文章

  • Stage3D之Hello Triangle
    ​​http://www.adobe.com/devnet/flashplayer/articles/hello-triangle.html​​RequirementsPrerequisiteknowledgeFamiliarityworkingwiththeStage3DAPIand......
  • hdu5135 Little Zu Chongzhi's Triangles --状压dp
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=5135​​题意:n根木棒,组成若干三角形,求最大面积和。分析:把所有木棒升序排序,可以组成三角形所有的的组合利用位运算......
  • LearnOpenGL "Hello Triangle"
    放图占位#include<glad/glad.h>#include<GLFW/glfw3.h>#include<iostream>voidframebuffer_size_callback(GLFWwindow*window,intwidth,intheight){gl......
  • [ABC251Ex] Fill Triangle 题解
    [ABC251Ex]FillTriangleSolution目录[ABC251Ex]FillTriangleSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面存在序列$a_n$,将......
  • CF1119E Pavel and Triangles 题解
    题面PavelandTriangles题面翻译给定n种木棍,第i+1种有ai​个,长度为2^i,求用这些木棍可以同时拼出多少个三角形(不可重复使用同一根)输入第一行n,第二行n个整数a0,a1,a2.........
  • 动态规划- [USACO1.5][IOI1994]数字三角形 Number Triangles
    [USACO1.5][IOI1994]数字三角形NumberTriangles题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以......
  • 【Kattis - triangle 】Sierpiński Circumference(数学,求位数,取对数或Java)
    题干:PolishmathematicianWacławSierpiński (1882-1969)describedthe2DgeometricfigureknownastheSierpiński triangleaspartofhisworkonsettheory......
  • ABC258Ex
    考虑答案实际就是从\(T=\left\{0,1,\cdots,S\right\}\setminus\left\{A_1,\cdots,A_N\right\}\)中选取若干个数并且满足以下条件:\(0\)和\(S\)一定要选。当选的数......
  • Sept.25 Triangle Game
    portkey考场上因为读不懂题(再加上菜)就弃了所以先给一点翻译non-degenerate不-除掉|生成的不退化的non-degeneratetriangle不退化三角形,就是存在的三角形,满足三边\(......
  • P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
    这是一道动态规划的经典入门题,重点在于递规过程中存储计算结果,避免重复计算.当然直接简单粗暴使用递归也可以拿到部分分数.只是样例太大的话就过不了了.题目描述观......