B. Find the Spruce(暴力)

待我称王封你为后i 2021-07-17 01:25 375阅读 0赞

[题目][Link 1]

思路：先预处理一下每个元素之后会有多少个连续的’\*’,时间O(n^3），然后对于每一个元素暴力模拟一下，时间O  
(n^3)，细节见代码。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<bitset>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[505][505];
    int Mod = 1e9 + 7;
    int n, m;ll sum = 0;
    int dp[505][505];
    
    void check(int x,int y)
    { 
    	int g = 0;int f = 0;
    	while (1)
    	{ 
    		if (x + g > n || y + g > m||y-g<1)break;
    		if ( dp[x+g][y-g]<1+2*g)f = 1;
    		g++;
    		if (f)break;
    		sum++;
    	}
    }
    
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		cin >> n >> m;
    		for (int i = 1;i <= n;i++)
    		{ 
    			for (int j = 1;j <= m;j++)
    			{ 
    				char g;cin >> g;
    				if (g == '*')lst[i][j] = 1;
    				else lst[i][j] = 0;
    			}
    		}
    		sum = 0;
    		memset(dp, 0, sizeof(dp));
    		for (int i = 1;i <= n;i++)
    		{ 
    			for (int j = 1;j <= m;j++)
    			{ 
    				int su = 0;
    				for (int k = j;k <= m;k++)
    				{ 
    					if (lst[i][k] == 1)su++;
    					else break;
    				}
    				dp[i][j] = su;
    			}
    		}
    		for (int i = 1;i <= n;i++)
    		{ 
    			for (int j = 1;j <= m;j++)
    			{ 
    				if (lst[i][j])check(i, j);
    			}
    		}
    		cout << sum << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1461/problem/B

发表评论取消回复

表情：

评论列表（有 0 条评论，375人围观）

还没有评论，来说两句吧...

相关阅读

相关 TopCoder 636 B 【暴力】

题意：给出一个排列，其中的一些数字不小心给擦掉了。但是知道这个序列满足 i < j && a\[ i \] < a\[ j \] 的元素对有n个，然后让你求还原这个排列之后有几

我就是我/ 2022年08月13日 06:29/ 0 赞/ 154 阅读

相关 Find The Multiple

Find The Multiple Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d &

亦凉/ 2022年08月07日 09:51/ 0 赞/ 148 阅读

相关 Find The Parity Outlier

You are given an array (which will have a length of at least 3, but could be very large)

亦凉/ 2022年06月16日 07:10/ 0 赞/ 185 阅读

相关 Find the missing letter

Find the missing letter Write a method that takes an array of consecutive (increasing)

爱被打了一巴掌/ 2022年06月16日 07:09/ 0 赞/ 487 阅读

相关 leetcode 564. Find the Closest Palindrome 寻找最近回文数字 + 暴力求解

Given an integer n, find the closest integer (not including itself), which is a palindro

拼搏现实的明天。/ 2022年06月03日 04:17/ 0 赞/ 167 阅读

相关 F - Christmas Spruce

题目描叙： Consider a rooted tree. A rooted tree has one special vertex called the root. A

谁践踏了优雅/ 2022年04月01日 12:12/ 0 赞/ 146 阅读

相关 Find the Missing Number

方法一：数学方法，先找到最大的值，需要比较最大的值和array size，要是比array size小，说明最大值missing。然后用等差数列公式求得如果不缺失值的和

青旅半醒/ 2021年12月16日 07:25/ 0 赞/ 236 阅读

相关 1481B New Colony （暴力）

[题目][Link 1] 看到题目中山的数量最多只有100，那么我们直接暴力模拟O(N^2)，对于每一个石块都从第一座山放下去，如果发现有前面的山高于自己则将自己所在的山

向右看齐/ 2021年07月17日 01:45/ 0 赞/ 365 阅读

相关 B. Find the Spruce(暴力)

[题目][Link 1] 思路：先预处理一下每个元素之后会有多少个连续的’\’,时间O(n^3），然后对于每一个元素暴力模拟一下，时间O (n^3)，细节见代码。

待我称王封你为后i/ 2021年07月17日 01:25/ 0 赞/ 376 阅读

相关 1400B - RPG Protagonist (暴力)

[题目][Link 1] 思路：一开始觉得像个dp,但一看范围太大了。然后发现每种刀剑的质量固定的特点，那么很容易想到贪心肯定先把质量小的搞完，而数量范围最多2e5。所以

àì夳堔傛蜴生んèń/ 2021年07月16日 23:37/ 0 赞/ 329 阅读