思路：一开始写麻烦了，其实这题很简单，因为这个一个33的矩阵，只需要O(n)遍历一个给你的数组，然后离线处理，分别判断5个点的坐标即 只需要判断这5个坐标是否对应的方向是否有3个相同的数字就行了，具体看一下代码，不太好用语言描述，我这个题代码写复杂了，一开始没看到是33的矩阵 class Solution { public: int maze[100][100]={0}; bool check(int x,int y){ return maze[x][y]==maze[x-1][y]&&maze[x-1][y]==maze[x+1][y]|| maze[x][y]==maze[...

#include<iostream> using namespace std; const int maxn=1e3+10; struct priority_queue{ int data[maxn]; int size; priority_queue(){ size=0; } void heap_up(int id) { if (id == 1)return; if (heap[id] > heap[id / 2]) { swap(heap[id], heap[id / 2]); heap_up(id / 2); } } void add(int v) { heap[++h...

#include<iostream> #include<stdlib.h> #include<time.h> #define n 10000 using namespace std; const int maxn=1e6+10; int a[maxn],b[maxn]; void display(){ for(int i=0;i<n;i++){ printf("%4d",a[i]); } puts(""); } void insertsort(){ for(int i=1;i<n;i++){ if(a[i]...

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 344507 Accepted Submission(s): 81909 Problem Description Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the m...

A 做游戏 牛牛和 牛可乐在玩石头剪刀布。 众所周知，石头剪刀布的规则是这样的：  在一局游戏中，双方各自出石头、剪刀、布其一。 胜负关系如下：  牛牛和 牛可乐进行了多轮游戏， 牛牛总共出了 A 次石头，B 次剪刀，C 次布；牛可乐总共出了 X 次石头，Y 次剪刀，Z 次布。 你需要求出 牛牛最多获胜多少局。 输入描述: 第一行，三个非负整数 A,B,C 。 第二行，三个非负整数 X,Y,Z 。 保证 A+B+C=X+Y+Z, 0<= A,B,C,X,Y,Z<= 10^9A+B+C=X+Y+Z,0≤A,B,C,X,Y,Z≤10 9 。 输出描述: 输出一行，一个整数表示答案。 示...

A 牛牛的DRB迷宫I   思路：暴力dfs，时间复杂度O(2^n)超时，改dp。 定义状态：dp[i][j]表示起点(1,1)到坐标(i,j)的路径条数。 边界：因为只能向右或者向下走，所以dp[1][i]和dp[i][1]都可以计算出来，dp[1][1]=1。 状态转移方程：dp[i][j]=dp[i][j-1]+dp[i-1][j]; （不带约束，具体看代码） 代码： #include<iostream> using namespace std; const int mod = 1e9 +7; int n,m; char maze[100][100]; int dp[100]...

B 括号序列  思路：用栈去模拟，左括号进栈右括号出栈(对应括号),最后判断一下是否栈空，空说明没问题，否则不行。 代码： #include<bits/stdc++.h> using namespace std; int main(){ string s;cin>>s; stack<char>st; bool flag=true; for(int i=0;i<s.size();i++){ if(s[i]=='['||s[i]=='{'||s[i]=='(')st.push(s[i]); if(s[i]==']'){ if(st.top()!='['){...

C. Painting the Fence time limit per test2 seconds memory limit per test256 megabytes You have a long fence which consists of n sections. Unfortunately, it is not painted, so you decided to hire q painters to paint it. i-th painter will paint all sections x such that li≤x≤ri. Unfortunately, you are ...

题意：给你一个长度为n的序列，要你求他们的连乘，最后mod m。 思路： 如果O(n^2)暴力的话很好求，但是因为n = 2e5 所以肯定会超时。 先给出结论，如果 n > m ，连乘直接为0。（等下给出证明） 如果n <= m ，直接O(n^2)暴力即可，因为m最大取值 = 1e3。 证明： 假设存在 j ,使得 an - aj = 0 mod m,那么整个式子就直接等于0了，结论成立。 假设存在j1，使得 an - aj != 0 mod m,那么一定存在 0<j1<j2<n，因为mod m的取值只有[0,m-1]，如果取值为0 ，结论显然成立，如果不为0，那...

循环赛日问题： 设有n=2^k个选手参加循环赛，要求设计一个满足以下要求比赛日程表： 1）每个选手必须与其它n-1个选手各赛一次； 2）每个选手一天只能赛一次。 分析，按照上面的要求，可以将比赛表设计成一个n行n-1列的二维表，其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号。 思路： 一开始我以为枚举全排列然后满足每行每列不出现同样的数字就行了，然后发现还要满足一个人一天只能赛一次，然后就不行了，(构造了一个矩阵满足每行每列不出现相同数字，可惜 了)。 solved是我构造的矩阵。（可以省略） 然后这个题用分治的方法去做就行了，思路不是很难，就是左上角复制到右下角，右上角复制到左下...

Problem Description “Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says. “The second problem is, given an positive integer N, we define an equation like this: N=a[1]+a[2]+a[3]+…+a[m]; a[i]>0,1<=m<=N; My question is how many different ...

第k小的数 Description 现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。 Input 多组输入。 首先输入一个数据组数T（1<=T<=100） 接下来是T组数据。 每组数据有两行。 第一行先输入两个整数，n和k。 接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。 Output 对于每组数据，输出该组数据中第k小的数num。 Sample Input 1 6 4 3 2 5 1 4 ...

最大间隙问题 Description 最大间隙问题：给定n个实数x1,x2,……,xn，求这n 个数在实轴上相邻2 个数之间的最大差值。 假设对任何实数的下取整方法耗时O(1)，设计解最大间隙问题的线性时间算法。 对于给定的n 个实数x1,x2,……,xn，计算它们的最大间隙。 Input 输入数据的第1行有1个正整数n，n≤200000。 接下来的1行中有n个实数x1,x2,……,xn。 Output 将找到的最大间隙输出，保留1位小数。 Sample Input 5 2.3 3.1 7.5 1.5 6.3 Output 3.2 Hint 注意：要 求 线 性 时 间 算 法 思路：很容易想...

思路：为了完整的用完（4^k - 1）/3 个L型骨牌，不妨采用四等分划分，对于没有特殊方格的区域构造一个L型骨牌，这样使得所有区域再放一下L型骨牌刚刚好把整个棋盘放满，然后再进行四等分递归划分，直到只有一个方格时才结束划分，应该算是一个经典的分治法吧。 代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; int chess[maxn][maxn]; int cnt = 1; void dfs(int sr,int sc,int len,int dx,int dy){ if(len ...