首页 > Symmetric Matrix
开通博客写题解
头像 ThinkofBlank
发表于 2020-04-28 12:00:22
太菜了，直接上OEIS 然后发现递推式: 于是。。。完了/x #include<bits/stdc++.h> using namespace std; const int N=1e5+1; int n,m; int a[N]; int main(){ while(~scanf( 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 一衍一
发表于 2020-04-28 14:19:39
(小声bb)(这题不会,看了好多题解看明白的)参考博客链接: https://blog.csdn.net/qq_37632935/article/details/81122408 https://ac.nowcoder.com/discuss/87364?type=101&am 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 精神病科黄主任
发表于 2020-05-04 20:35:28
题意：给出n和m，要你构造出满足如下条件的n*n的矩阵， 1、矩阵内的元素A[i][j] = {0,1,2} 2、矩阵内的元素A[i][j] = A[j][i] 3、矩阵内的元素A[i][1]+A[i][2]+A[i][3]+...+A[i][n]=2 对于所有的 i 都成立 4、矩阵内的元素A[i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 回归梦想
发表于 2020-05-02 11:24:53
链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 输入描述: The input consists of several test cases and is terminated b 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-02 23:54:35
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld 题目描述 Count the number of n x n matrices A satisfying the following c 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-05-06 02:01:59
题意：求满足以下条件的n*n矩阵的个数：1.所有元素的值属于{0，1，2}；2.为对称矩阵；3.每一行的值的和为2；4对角线的值为0；结果对m取模。 思路：我们知道无向图的邻接矩阵是对称的，所以将四个条件可以转化为找满足没有自环的n个节点且每个节点有且仅有二条边的无向图有多少个？我们可以知道这样的无 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 _LRJ_
发表于 2020-05-06 11:47:37
这个题目构思十分巧妙，我们考虑把这样的矩阵作为一个图的邻接矩阵，恰好满足题目中的所有条件，并且关键的一点是每一个点都有且仅有2条边。针对这类问题可以使用dp来解决。dp[i]表示i个点满足条件的图的种类数目。分情况讨论可以得到状态转移方程： dp[i]=((i-1)*dp[i-2]+(i-1)*dp 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 与人无语
发表于 2020-04-30 23:01:45
看题不会 疯狂自闭看完雨巨和其他大佬的题解后 写出了这道题写些自己的理解1、将矩阵的构造转化成图的构造（图的邻接矩阵表示法） 边权值即表示点与点有几条边于是由条件可知 每个点有且只有两条边（后面的关键） 这个图由几个简单环组成 每个环至少2个点2、如何由dp[n-1]推出dp[n] 相当于n-1个的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 呱呱咕
发表于 2020-05-01 21:00:55
一天终于搞懂了，还是手动推了一边公式。题意，就是题目要求让你构建合法的矩阵，然后问你种类数。题解：这道题我们可以把这个图看成邻接矩阵，是个无向图，首先，我们看来数据范围，不超过1e7，那么肯定是个递推，或者动态规划，或者就是规律，然后我们分析，我们给点赋值，不就是在图里面加边权吗，当我们需要加第N个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 人丑心更黑
发表于 2021-03-10 14:50:51
数学也太难了QWQ 题目大意：给一个n*n的矩阵，对于矩阵的每个元素a[i]∈{0,1,2}其中每行的a[i]的和为2，a[i][i]=0a[i][j]=a[j][i]问满足条件的矩阵有多少个。n<=10^5 思路：看题目感觉是个递推，但是完全不知道怎么做。参考了题解：本题给出的矩阵我们可以联 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”