题解: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
题解:CF2086C Disappearing Permutation
题意 给定两个排列 $p$ 和 $d$,第 $1 \le i \le n$ 次将 $p_{d_i}$ 设为 0。 然后进行操作,一次操作定义为指定一个 $i$,将 $a_i = i$,问最少多少次操作能将它复原为一个排列(可能与原排列相同)。 思路 我一看,每次 $p_{i}$ 一定要做一次操作 $p_i=i$,那么 $p_{p_i}$ 也要操作,以此类推,直到 $p_k$ 等于 $k$。 那就好办了,每次讲 $p_i$ 和 $i$ 连在一起,分成几个联通块,每次的答案就是联通块的大小。 code 123456789101112131415161718192021222324#include<bits/stdc++.h>#define int long longusing namespace std;int T,n,p[100005],d[100005],f[100005],sz[100005],fg[100005],ans;int fd(int x){ if(f[x]==x) return x; return f[x]=fd(f[x]);...
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
题解: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
题解: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
题解: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
题解: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...