Codeforces Round #249 (Div. 2) (ABCD题解) - c++编程基础

t samples for better understanding of how to print a cardiogram.

Note that in this problem the checker checks your answer taking spaces into consideration. Do not print any extra characters. Remember that the wrong answer to the first pretest doesn't give you a penalty.

Sample test(s) Input

5
3 1 2 5 1

Output

     ?/?     
  ?/??/?      
 ?/?         
?/?          
          ?/?

Input

3
1 5 1

Output

Note

Due to the technical reasons the answers for the samples cannot be copied from the statement. We've attached two text documents with the answers below.

http://assets.codeforces.com/rounds/435/1.txt

http://assets.codeforces.com/rounds/435/2.txt

题目大意：这题意着实醒神。。。给一个数列，按其顺序一上一下打印图形

题目分析：因为还好ai最大是1000，可以用一个2000*2000的矩阵存起来，然后就模拟吧，注意动态取竖直方向的最大最小值，没想到cf还有这样的题

#include 
  
   
#include 
   
     #include 
    
      using namespace std; char g[2005][2005]; int main() { int n; scanf(%d, &n); int sign = 1; int maxy = 1000, miny = 1000; int x = -1, y = 1000; memset(g, 0, sizeof(g)); while(n--) { int a; scanf(%d, &a); if(sign == 1) y --; else y ++; for(int i = 1; i <= a; i++) { if(sign == 1) { y ++; x ++; g[x][y] = '/'; } else { y --; x ++; g[x][y] = '\'; } }www.2cto.com maxy = max(maxy, y); miny = min(miny, y); sign *= -1; } for(int i = 0; i <= x; i++) for(int j = miny; j <= maxy; j++) if(!g[i][j]) g[i][j] = ' '; int cnt =0 ; for(int j = maxy; j >= miny; j--) { for(int i = 0; i <= x; i++) printf(%c, g[i][j]); printf( ); } }

D. Special Grid time limit per test：4 seconds memory limit per test：256 megabytes

You are given an n?×?m grid, some of its nodes are black, the others are white. Moreover, it's not an ordinary grid — each unit square of the grid has painted diagonals.

The figure below is an example of such grid of size 3?×?5. Four nodes of this grid are black, the other 11 nodes are white.

$\$

Your task is to count the number of such triangles on the given grid that:

the corners match the white nodes, and the area is positive; all sides go along the grid lines (horizontal, vertical or diagonal); no side contains black nodes. Input

The first line contains two integers n and m (2?≤?n,?m?≤?400). Each of the following n lines contain m characters (zeros and ones) — the description of the grid. If the j-th character in the i-th line equals zero, then the node on the i-th horizontal line and on the j-th vertical line is painted white. Otherwise, the node is painted black.

The horizontal lines are numbered starting from one from top to bottom, the vertical lines are numbered starting from one from left to right.

Output

Print a single integer — the number of required triangles.

Sample test(s) Input

Output

Input

2 2
00
00

Output

Input

2 2
11
11

Output

Note

The figure below shows red and blue triangles. They are the examples of the required triangles in the first sample. One of the invalid triangles is painted green. It is invalid because not all sides go along the grid lines.

$\$

题目大意：给个0/1矩阵，0的地方可以相互连接，问矩阵中共有多少个三角形，注意三角形的边必须是垂直水平或者斜45度的

题目分析：做的特别纠结的一题，根据题意显然所有三角形都是直角三角形，所以可以直接枚举直角来做，我说下我的做法吧。。。

我是枚举边做的，首先预处理出每个点往其周围的8个方向可以延伸的最远距离（距离及点数），用dp[i][j][0-7]表示，然后分成两种情况，第一种是只有一个边是斜45度方向的，枚举全部情况，注意这种情况我是按45度角枚举的，所以最后要除2，然后是有两条斜45度方向边的情况，这种情况是按90度枚举的，所以不会重复，其实直接全部枚举直角就可以了，我做的时候调来调去给调乱了，就搞成了这样

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int const MAX = 405; int dp[MAX][MAX][8], g[MAX][MAX]; char s[MAX][MAX]; int main() { int n, m; scanf(%d %d, &n, &m); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { scanf(%s, s[i] + 1); for(int j = 1; j <= m; j++) { g[i][j] = s[i][j] - '0'; if(!g[i][j]) for(int k = 0; k < 8; k++) dp[i][j][k] = 1; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(dp[i - 1][j][0] && dp[i][j][0]) dp[i][j][0] += dp[i - 1][j][0]; if(dp[i - 1][j - 1][7] && dp[i][j][7]) dp[i][j][7] += dp[i - 1][j - 1][7]; if(dp[i][j - 1][6] && dp[i][j][6]) dp[i][j][6] += dp[i][j - 1][6]; } for(int j = m; j >= 1; j--) { if(dp[i - 1][j + 1][1] && dp[i][j][1]) dp[i][j][1] += dp[i - 1][j + 1][1]; if(dp[i][j + 1][2] && dp[i][j][2]) dp[i][j][2] += dp[i][j + 1][2]; } } for(int i = n; i >= 1; i--) { for(int j = 1; j <= m; j++) { if(dp[i + 1][j][4] && dp[i][j][4]) dp[i][j][4] += dp[i + 1][j][4]; if(dp[i + 1][j - 1][5] && dp[i][j][5]) dp[i][j][5] += dp[i + 1][j - 1][5]; } for(int j = m; j >= 1; j--) { if(dp[i + 1][j + 1][3] && dp[i][j][3]) dp[i][j][3] += dp[i + 1][j + 1][3]; } } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) for(int k = 0; k < 8; k++) dp[i][j][k] -= 1; int ans1 = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { for(int k = 1; k <= max(n, m); k++) { if(dp[i][j][0] >= k && dp[i][j][7] >= k && i - k >= 1 &

Codeforces Round #249 (Div. 2) (ABCD题解)(二)