牛客竞赛每日俩题 - Day14
创始人
2024-05-11 12:03:45
0

目录

错排算法

三维数组的应用


错排算法

发邮件__牛客网

错排:
假设有n封信要装入到n个信封中,每封信应该要放到对应的信封中,比如:

信:   A B C D...
信封: a b c d. ...
由于疏忽将信放置出错,总共有多少种可能性每封信都放错

假设:D(n)表示n封信总共装错的总数

如果A装入到b的信封中:

  • 将B信装入到A的信封中(a、b互相放错形成独立): A-->b B-->a出错的总数:取决于剩余的n-2封信: D(n-2)
  • 将B信装入到除A以外的其他信封(只有A与b完成独立):剩余n-1封信放错的可能性为D(n-1)


所以A装错到b的信封后有D(n-1) +D(n-2)种出错数
同理,如果将A装入到C、D、E (n-2)*(D(n-1)+D(n-2));

总的出错总数:(n-1)*(D(n-1)+D(n-2));

特殊的:

如果是0封信:D(0)--->0

如果是1封信:D(1)--->0

如果是2封信: D(2)--->1

#include
using namespace std;int main()
{long long d[21]={0,0,1};for(int i=3;i<=20;i++){d[i]=(i-1)*(d[i-1]+d[i-2]);}int n;while(cin>>n)cout<

三维数组的应用

五子棋__牛客网

 核心在于构建三维数组以遍历方向;

int d[横竖斜线][两个小方向][坐标x,y]={ {{x1,y1},{x2,x2}},{...},{},{} }

可以理解为二维数组里面存数组,例如 int a[][]={ {【数组】},{...},{} }

#include 
#include 
#include 
using namespace std;
#define N 20
int count(string table[], char ch, int x, int y)
{int maxc = 0;int dir[4][2][2] = { {{ -1,0 },{ 1,0 }},{{ 0,-1 },{ 0,1 }},{{ -1,-1 },{1,1 }},{{ -1,1 },{ 1,-1 }} };for (int i = 0; i < 4; ++i) // 四种方向{int c = 0;for (int j = 0; j < 2; ++j) // 两个小方向{int nx = x, ny = y;while (nx >= 0 && nx < N && ny >= 0 && ny < N && table[nx][ny] ==ch){nx += dir[i][j][0];ny += dir[i][j][1];++c;}}maxc = max(maxc,c);}return maxc - 1; //统计两个方向(如横向的左右两个方向)的时候,//当前棋子被计算了两次
}
bool solve(string table[])
{// 遍历棋谱,如果某个位置有棋子,再想该位置进行搜索for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){if (table[i][j] == '*' || table[i][j] == '+')// 当某个位置有连在一起的棋子,结束搜索if (count(table, table[i][j], i, j) >= 5)return true;}}return false;
}
int main()
{string table[N];while (cin >> table[0]){for (int i = 1; i < N; ++i)cin >> table[i];cout << (solve(table) ? "Yes" : "No") << endl;}return 0;
}

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...