题解: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
题解:CF1766C Hamiltonian Wall
题目就是求 $s$ 是否可以一笔画。 像这样(样例): 12BWBBWBBBBBBB 走法: 123B W B--B W B| | | |B--B--B B--B--B 我们发现如果上面或下面没有走过且可以走,是一定要走。 如果上面或下面都走过了,就向后走。 另外形如: 12BBBW 就要特判是开始是第一行还是第二行,我的做法是都枚举一遍。 最后放上超长代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,fg,as,x,y,vis[200005][2]; char s[200005][2];signed main(){ cin>>T; while(T--){ cin>>n,fg=as=0; for(int...
2026-03-09
题解:P3535 [POI 2012] TOU-Tour de Byteotia
并查集板子。 思路 一条边如果没有我们所关注的点,可以直接不管,因为这些边不会影响我们需要的点。直接丢到并查集里维护即可。 剩下的边贪心,能加的都要加。 代码解释 首先,$u_i>k$ 且 $v_i>k$ 的边一定要选,用并查集维护即可。 12345for(int i=1;i<=m;i++){ cin>>u[i]>>v[i]; if(u[i]>v[i]) swap(u[i],v[i]); if(u[i]>k&&v[i]>k) f[fd(u[i])]=fd(v[i]);} 然后,剩下 $u_i \le k$ 或 $v_i \le k$ 的边看情况选: 如果他们不在一个集合里(不会出现简单环),选并合并。 如果他们在一个集合里,不选并计入答案。 123456for(int i=1;i<=m;i++){ if(u[i]<=k||v[i]<=k){ if(fd(u[i])!=fd(v[i])) f[fd(u[i])...
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
题解: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
题解: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
题解: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; ...
评论