题解:P7900 [COCI 2006/2007 #2] SJECIŠTA
发表于|更新于|题解
|浏览量:
题意:
给定一个没有任何三个及以上的对角线交于一点的凸多边形。
问对角线交点个数。
思路:
我们注意到任意两个对角线一定可以确定一个点。
那么只要求出对角线数量就行了!
解法:
确定两个对角线就是找到四个点。
即在 $n$ 个点中选 $4$ 个点。
所以答案就是 $C^4_n$。
文章作者: heyZzz
文章链接: https://heyzzz629.github.io/2026/03/09/%E9%A2%98%E8%A7%A3%EF%BC%9AP7900-COCI-2006-2007-2-SJECISTA/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 heyZzz's OI Blog!
相关推荐
2026-03-09
题解:CF1598D Training Session
题目翻译: 给定 $n$ 个互不相同二元组,现在要从其中选出三个二元组,使得这三个二元组的的前一项互不相同或后一项互不相同。求有几种方案。 思路: 正难则反,先算总数:有 $\Large\frac{n \times (n-1) \times (n-2)}{6}$ 种情况。 不满足的情况是没有一个二元组与另一个二元组元素两两不相同(同一个元素)。 也就是就是一个二元组与另一个二元组元素至少一个相同(也是同一个元素)。 考虑用桶记录,$x_i$ 代表 $a_i$ 的出现个数,$y_i$ 代表 $b_i$ 的出现个数。 第一组固定,第二组有 $x_{a_i}-1$ 种,第三组有 $y_{b_i}-1$ 种。 一共有 $(x_{a_i}-1) \times (y_{b_i}-1)$。 代码楼上楼下都已经写的很明白了,我就不在赘述了。
2026-03-09
题解:P10928 走廊泼水节
回顾 kruskal: 取边权最小的一条边,若两个点在不同连通块(并查集),则连边合并。 我们把以上规则改一下: 如果点 $A$ 的老大的小弟数<点 $B$ 的老大的小弟数,$A$ 成为 $B$ 小弟。 反之,$B$ 成为 $A$ 小弟。 我们定义 $s_i$ 是点 $i$ 的老大的小弟数,$w$ 是 $a$ 到 $b$ 的边权。 贡献和为:$(s_A×s_B−1) \times (w+1)$。 代码楼上楼下都已经写的很明白了,我就不在赘述了。
2026-03-09
题解:P10578 [蓝桥杯 2024 国 A] 旋转九宫格
用 BFS。 思路 我们可以使用一个长度为 $3\times3$ 的 string 来表示状态,每一种状态可以进行旋转(左上,右上,左下,右下)。 我们可以用 map 来记录状态。 预处理一下即可。 代码: 12345678910111213141516171819202122#include<bits/stdc++.h>#define int long longusing namespace std;map<string,int> mp; int T,n; char c;signed main(){ cin>>T; queue<string> q; //bfs q.push("123456789"),mp["123456789"]=1; while(q.size()){ string u=q.front(),v[4]={u,u,u,u}; q.pop(); v[3][4]=u[5],v[3][5]=u[8],v[3][7]=u[4],v[3][...
2026-03-09
题解:CF333B Chips
原题传送门 题目大意: 有一个 $n \times n$ 的棋盘,$m$ 个格子是障碍物,然后移动芯片使它们返回到初始对边位置,不能经过障碍物、重叠或交换位置。问最多可以放置多少个芯片完成游戏。 思路: 本题直接按题意模拟即可: 使用桶记录障碍,$a_i$ 代表第 $i$ 行的芯片个数,同理 $b_i$ 代表第 $i$ 列的芯片个数。 如果第 $i$ 行或第 $j$ 没有芯片,$cnt+1$。 如果相遇,就是 $n$ 为奇数且中间行且列有值,$cnt-1$。 下面是样例 $3$ 的解释: 列1 列2 列3 列4 行1 无芯片 可放芯片 可放芯片 无芯片 行2 放芯片 ______ ______ 放芯片 行3 障碍物 障碍物 障碍物 可放芯片 行4 无芯片 可放芯片 可放芯片 无芯片 行2的两个芯片可以连通,$cnt=1$。 没有相遇情况,输出 $1$。 上代码: 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int n,m,x,y...
2026-03-09
题解:P12131 [蓝桥杯 2025 省 B] 客流量上限
思路 因为对于任意分店 $i$ 和 $j(1\le i,j\le2025)$,它们的客流量上限 $A_i$ 和 $A_j$ 的乘积不得超过 $ij+2025$。 所以,对于任意分店 $i$,$A_i\le\sqrt{i^2+2025}$。 我们直接打表: 1for(int i=1;i<=2025;i++) cout<<(int)sqrt(i*i+2025)<<' '; 发现在 $i\ge1013$ 时 $A_i \le i$。 那么当 $1\le i<1013\le j\le2025$ 时,$A_iA_j=A_ij,A_iA_j\le ij+2025$。 两边同除 $j$:$A_i\le i+\frac{2025}{j}$。 发现:$A_i\le i+\lfloor\frac{2025}{j}\rfloor$。 由于 $1013\le j\le2025$,所以,$A_i\in[1,i+1]$。 所以我们可以得出: $A_1$ 有 $2$ 种选择; $A_k$ 为了不与 $A_1$~$A_{k-1}$ 选的重复,总是有 $i+...
2026-03-09
题解:P10161 [DTCPC 2024] 小方的疑惑 10
思路 我们注意到答案串一定是若干个可以变成一个可以做出 $k$ 个合法的括号序列的长度 $\le n$ 的序列再补上若干个 )。 显然,设答案串 $s$ 有 $k$ 对括号在最外层,那么合法子串个数为 $\frac{k(k+1)}{2}$。我们就可以构造了! 这样就可以在不浪费括号的情况下将答案串分成多个括号串。 设 $dp_i$ 为构造出 $i$ 个合法子串(即 $k$)所需的最小括号对数。 状态转移就是:$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$。 我们先把这部分预处理出来。 如果 $2dp_k>n$ 则说明无解,否则在 dp 数组上递归构造(如果$dp_i=dp_{i-\frac{j(j+1)}{2}}+j$,那么就转移)。 代码: 1234567891011121314151617#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,k,dp[100005];void print(int x){ if(!x) return; ...