小白开始成长了+洛谷1488与CF629A Far Relative’s Birthday Cake题解
终于开始我的博客生活了，希望博客可以让我记住学了什么，错了什么，接下来会有什么将出现。
记录写ACM生涯中的一些经验和网工经验吧，如果有人看我博客的话，希望可以留言给我提提意见，指导指导我啦
~
正题：
先把洛谷写过的题解CV一下
题目来源：洛谷 P1488 肥猫的游戏
题目描述
野猫与胖子，合起来简称肥猫，是一个班的同学，他们也都是数学高手，所以经常在一起讨论数学问题也就不足为奇了。一次，野猫遇到了一道有趣的几何游戏题目，便拿给胖子看。游戏要求在一个有n个顶点凸多边形上进行，这个凸多边形的n-3条对角线将多边形分成n-2个三角形，这n-3条对角线在多边形的顶点相交。三角形中的一个被染成黑色，其余是白色。双方轮流进行游戏，当轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。胖子一看觉得确实很有趣，不如就一起玩玩吧。假设游戏由野猫先开始，那么野猫是否有必胜的策略呢？请写一个程序帮助野猫算一算。
输入格式
第一行为一个整数n(4<=n<=50000)，表示多边形的顶点数，多边形的顶点由0至n－1顺时针标号。接着的n-2行描述组成多边形的三角形。第i+1行(1<=i<=n-2)有三个空格分隔的非负整数a、b、c，它们是第i个三角形的顶点编号。第一个给出的三角形是黑色的。
输出格式
只有一行，倘若野猫有必胜策略，输出JMcat Win；否则，输出PZ Win。（注意大小写和空格）
输入输出样例
输入
6 0 1 2 2 4 3 4 2 0 0 5 4
输出
JMcat Win
说明与提示
4 ≤ n ≤ 5×10^4
如果连接一个多边形中任意两点的线段都完全包含于这个多边形，则称这个多边形为凸多边形。
Solution
非正解:
其实就是判对角线数，如果对角线是奇数就JMcat Win，否则就是PZ Win 那么上代码:
#include<iostream>
using namespace std;
int main(){
int n; 5 cin>>n;
if((n-3)%2==0)
cout<<"PZ Win";
else cout<<"JMcat Win";
return 0;
} 但是会WA！！！因为没考虑一刀切和在多边形内部； 就比如5边形，100,010（1是黑的，0是白的） 所以判断下黑的顶点是否连续就行。
#include<iostream>
using namespace std;
int main(){
int n,a,b,c;
cin>>n;
cin>>a>>b>>c;
if(a+1==b){
if(b+1==c){
cout"JMcat Win";
return 0;
}
}
if((n-3)%2==0) cout<<"PZ Win";
else cout<<"JMcat Win";
return 0;
} 好的AC，这不是正解！！！
CF629A Far Relative’s Birthday Cake
Despription
Door's family is going celebrate Famil Doors's birthday party. They love Famil Door so they are planning to make his birthday cake weird!
The cake is a n×n n×n n×n square consisting of equal squares with side length 1 1 1 . Each square is either empty or consists of a single chocolate. They bought the cake and randomly started to put the chocolates on the cake. The value of Famil Door's happiness will be equal to the number of pairs of cells with chocolates that are in the same row or in the same column of the cake. Famil Doors's family is wondering what is the amount of happiness of Famil going to be?
Please, note that any pair can be counted no more than once, as two different cells can't share both the same row and the same column.
Input
In the first line of the input, you are given a single integer n ( 1 <= n <= 100 )
--- the length of the side of the cake.
Then follow n lines, each containing n characters. Empty cells are denoted with '.
', while cells that contain chocolates are denoted by 'C'.
Output
Print the value of Famil Door's happiness, i.e. the number of pairs of chocolate pieces that share the same row or the same column.
Example
input
3 .CC C.. C.C
output
4
input
4 CC.. C..C .CC. .CC.
output
9
Note
If we number rows from top to bottom and columns from left to right, then, pieces
that share the same row in the first sample are:
1.(1,2) and (1,3)
2.(3,1) and (3,3)
Pieces that share the same column are:
1.(2,1) and (3,1)
2.(1,3) and (3,3)
代码可能因为是小白所以有点长。。。不过比较好写，因为大部分重复，CV就行，稍作改动
这个解法没有我看到的其他解法简洁，快速，但是如果新人看我的可能理解更好点吧。。。
本来准备DFS（刚学想练手），写着写着就发现更简单的写法。。。
解法就是计每行与每列的‘C’个数，然后每行每列的个数（>=2的前提下）利用组合公式求解
#include <iostream>
#include <cstring>
using namespace std;
double jiec(int n){ //阶乘函数
double sum =1; //double防超
for(int i = n;i>0;i--){
sum *= i;
}
return sum;
}
int main() {
int wide;
double sum = 0,count = 0; //double防超
scanf("%d",&wide); //边长
char cake[wide+1][wide+1];
int nu[wide],nu2[wide]; //分别计行与列的个数（有点啰嗦的感觉，
应该有优化的方法，但是我比较lazy。。。）
memset(nu,0,sizeof(nu));
memset(nu2,0,sizeof(nu2)); //初始化为0
for(int i =0;i<wide;i++){
scanf("%s",&cake[i]);
}
for(int i = 0 ;i<wide;i++){ //遍历每行
count = 0;
for(int j = 0;j<wide;j++){
if(cake[i][j]=='C'){
count += 1;
}
}
nu[i]=count; //赋值个数
}
for(int i = 0 ;i<wide;i++){ //遍历每行
count = 0;
for(int j = 0;j<wide;j++){
if(cake[j][i]=='C'){
count += 1;
}
}
nu2[i]=count; //赋值个数
}
for(int i = 0;i<wide;i++){
if(nu[i]>=2){
sum += jiec(nu[i])/(2*jiec(nu[i]-2));
//组合公式求解行
（不会请问度娘）
}
}
for(int i = 0;i<wide;i++){
if(nu2[i]>=2){
sum += jiec(nu2[i])/(2*jiec(nu2[i]-2));
//组合公式求解列
}
}
printf("%.0f",sum);
return 0;
} 
京公网安备 11010502036488号