C. Seat Arrangements time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Suppose that you are in a campus and have to go for classes day by day. As you may see, when you hurry to a classroom, you surprisingly find that many seats there are already occupied. Today you and your friends went for class, and found out that some of the seats were occupied.
The classroom contains n rows of seats and there are m seats in each row. Then the classroom can be represented as an n × m matrix. The character '.' represents an empty seat, while '*' means that the seat is occupied. You need to find k consecutive empty seats in the same row or column and arrange those seats for you and your friends. Your task is to find the number of ways to arrange the seats. Two ways are considered different if sets of places that students occupy differs.
Input
The first line contains three positive integers n, m, k (1 ≤ n, m, k ≤ 2 000), where n, m represent the sizes of the classroom and k is the number of consecutive seats you need to find.
Each of the next n lines contains m characters '.' or '*'. They form a matrix representing the classroom, '.' denotes an empty seat, and '*' denotes an occupied seat.
Output
A single number, denoting the number of ways to find k empty seats in the same row or column.
Examples input
2 3 2
**.
...
output
3
input
1 2 2
..
output
1
input
3 3 4
.*.
*.*
.*.
output
Note
In the first sample, there are three ways to arrange those seats. You can take the following seats for your arrangement.
- (1, 3), (2, 3)
- (2, 2), (2, 3)
- (2, 1), (2, 2)
思路：
在一個n行m列的矩陣中，有的地方被占了，有的沒有，就是簡單的讓你橫排或豎排找連續的k個未占領的位置。坑點在于：别忘了特殊考慮k==1時的情況。
代碼：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#define inf 0x7f7f7f7f
#define ll long long
#define maxn 2000+10
using namespace std;
int sss;
int main()
{
int n,m,k;
while(cin>>n>>m>>k){
int row[2005][2005],low[2005][2005];
char s[2005][2005];
sss=0;
memset(row,0,sizeof(row));
memset(low,0,sizeof(low));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
if(s[i][j]=='.')
sss++;
}
if(k==1) { cout<<sss<<endl;continue;}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j-1]!='*'&&s[i][j]!='*')
{
row[i][j]=row[i][j-1]+1;
}
else if(s[i][j]!='*')
{
row[i][j]=1;
}
if(s[i-1][j]!='*'&&s[i][j]!='*')
{
low[i][j]=low[i-1][j]+1;
}
else if(s[i][j]!='*')
{
low[i][j]=1;
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(row[i][j]>=k)
ans++;
if(low[i][j]>=k)
ans++;
}
cout<<ans<<endl;
}
return 0;
}
D. Substring time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output
You are given a graph with n nodes and m directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is 3. Your task is find a path whose value is the largest.
Input
The first line contains two positive integers n, m (1 ≤ n, m ≤ 300 000), denoting that the graph has n nodes and m directed edges.
The second line contains a string s with only lowercase English letters. The i-th character is the letter assigned to the i-th node.
Then m lines follow. Each line contains two integers x, y (1 ≤ x, y ≤ n), describing a directed edge from x to y. Note that x can be equal to y and there can be multiple edges between x and y. Also the graph can be not connected.
Output
Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.
Examples input
5 4
abaca
1 2
1 3
3 4
4 5
output
3
input
6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4
output
-1
input
10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7
output
4
Note
In the first sample, the path with largest value is 1 → 3 → 4 → 5. The value is 3 because the letter 'a' appears 3 times.
思路：
比賽時想到了運用dfs+dp，但是确實沒有想到要提前進行一下拓撲排序，倘若存在環，那麼就會無限大，也就是題目中-1的情況，其他的情況就是在拓撲排序之後，在進行DP和深搜。
代碼：
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 10;
int n, m;
char s[MAXN];
struct Link
{
int to, next;
}l[MAXN];
int first[MAXN];
int add = 0;
void add_edge(int u, int v)
{
l[++add].to = v;
l[add].next =first[u];
first[u] = add;
}
int in[MAXN];
queue<int> q;//存儲入度為0以及删除節點後入度為0的點
int dp[MAXN][26]; //dp[i][j]表示i位置開始 j字母的個數
bool vis[MAXN]; //表是否通路過
int ans = 0;
bool p[MAXN][26]; //表示目前的狀态是否出現過
int dfs(int x, int c)
{
if (p[x][c]) return dp[x][c]; //記錄，目前節點，目前字母出現過，記憶化
for (int i = first[x]; ~ i; i = l[i].next)
{
if (!vis[l[i].to])
{
dp[x][c] = max(dp[x][c], dfs(l[i].to, c));
}
}
if (s[x-1]-'a' == c)//回溯更新
dp[x][c] += 1;
p[x][c] = 1;
ans = max(ans, dp[x][c]);
return dp[x][c];
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%s", s);
memset(first, -1, sizeof(first));
int u, v;
for (int i = 1; i <= m; i ++)
{
scanf("%d%d", &u, &v);
add_edge(u, v);
in[v] ++;
}
int cnt = 0;
for (int i = 1; i <= n; i ++)
{
if (!in[i])
{
q.push(i);
vis[i] = 1;
cnt += 1;
}
}
while (!q.empty())//拓撲
{
int x = q.front();
q.pop();
for (int i = first[x]; ~ i; i = l[i].next)
{
in[l[i].to] -= 1;
if (in[l[i].to] == 0)
{
q.push(l[i].to);
cnt += 1;
}
}
}
if (cnt != n)//有環時，無限大情況
{
printf("-1");
return 0;
}
for (int j = 0; j < 26; j ++)
{
for (int i = 1; i <= n; i ++)
{
if (vis[i])
{
dfs(i, j);
}
}
}
printf("%d", ans);
return 0;
}
位址：點選打開連結
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)