题解：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
题解：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; ...
2026-03-09
题解：P10414 [蓝桥杯 2023 国 A] 2023 次方
前言 这个应该小学生都可以看懂吧（本题解没有用到任何较难的知识）。 好像我也是小学生唉。 前置小知识 $a\bmod b=c$ 代表取模，即 $a$ 除 $b$ 的余数是 $c$。 题意 求 $ 2{(3{(4^{(\ldots ^{2023})})})} \bmod2023$。 思路 因为这个式子过于复杂，所以要简化一下。 根据小学的知识，找规律！！！ 但是手算是不行的，写个程序： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2023; sum++;}cout<<sum; 得出每 $408$ 个数为一个周期。 之后我们还需要知道指数在周期外的个数（即$ 3{(4{(\ldots ^{2023})})}\bmod 408$）。 一样，还是找规律： 123456int s=3,sum=0,vis[2025]={};while(!vis[s]){ vis[s]=1; s=(s*3)%2...
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
题解：P10492 Weather Forecast
记忆化搜索+剪枝。 记忆化，记录： 目前到的点 $(x,y)$。 天数 $day$。 四个角的降雨量。 剪枝： 如果活动时下雨，直接剪掉。 如果四个角没有下雨 $\ge 7$ 天，直接剪掉。因为四个角地方被覆盖的情况是最少的。 代码: 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;int n,a[405][5][5],f[5][5][405][8][8][8][8];int dx[]={-1,0,-2,0,2,0,1,0,0},dy[]={0,-1,0,-2,0,2,0,1,0};int dfs(int x,int y,int day,int ex,int sx,int ey,int sy){ if(f[x][y][day][ex][sx][ey][sy]!=-1) return f[x][y][day][ex][sx][ey][sy]; for(int...
2026-03-09
题解：P11601 『Fwb』狼人の杀戮
比较烦的中模拟。 注意事项： 猎人死时必须带走一个人。 女巫只有一份毒药和解药。 在同一晚，同一位女巫只能做一次操作。 如果错误撤回当晚所有操作。 操作： 我们维护十个数组： $die$，所有死亡的记录。 $nw1$，女巫的毒药操作。 $nw2$，女巫的解药操作。 $nd$，当晚死亡人数。 $nnw$，当晚女巫的操作。 $lr$，当晚狼人的操作。 $er$，猎人带走的操作。 $die1$，$die$ 的副本。 $nw1_1$，$nw1$ 的副本。 $nw2_1$，$nw2$ 的副本。 然后，几个 $\texttt {if}$ 判断一下： 判断是否出界。 判断是否死亡。 如果是猎人或女巫，要判断是否当晚死亡。 如果是狼人或女巫，要判断是否当晚用。 接着，记录死亡，是否用技能： 12345678910111213141516if(op==0){ //狼人 if(a[x]==1&&!die[x]&&!die[y]&&!lr[x]&&x<=n&&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)$。 代码楼上楼下都已经写的很明白了，我就不在赘述了。
评论