牛客小白月赛47
比赛链接
牛客小白月赛47
D.造桥
题目描述
今天是愉快的周末，牛可乐和牛妹在一起玩游戏。牛妹给了牛可乐 \(n\) 个造桥的零件，每个零件以字符串的形式给出，每个字符串两端的字符是零件的接口，两个零件可以通过连接不同端的接口（一个零件的左端只能连接另一个零件的右端，右端则只能连接左端）得到一个更长的零件，新零件的长度是原零件的长度之和。
牛妹规定，零件不能翻转，且零件左边的接口只能由该零件左边的零件去连接（这意味着，应该按顺序选取零件），右端同理。
牛可乐想得到牛妹的赞许，因此他要想用牛妹给的零件拼接一个尽可能长的桥梁，你能帮帮他吗？
输入描述:
第一行一个整数 \(T\), 代表案例数。
对于每一个样例: 第一行一个数 \(n\), 表示字符串的个数。
接下来有 \(n\) 行, 每行一个字符串, 每个字符串的长度 \(\geqslant 2\) 。
\(0
所有案例的字符串长度的和不超过 \(2 e 5\) 。
保证所有字符均为小写字符。
输出描述:
\(n\) 个字符串能拼接的最大字符串长度。
示例1
输入
1
6
ab
baabc
bb
ba
ba
ad
输出
8
说明
按顺序依次拼接：\(1，3，5，6\)号字符串。
解题思路
思维，dp
相当于将每个字符串的第一个字符向最后一个字符连边，权值为字符串长度，从左到右求最大权值之和
-
状态表示：\(f[i]\) 表示以 \(i\) 结尾的最大权值
-
状态计算：\(f[r]=max(f[r],(int)s.size()+f[l])\)，其中 \(l,r\) 分别为字符串 \(s\) 的前后字符
分析：当前字符串是否对于 \(r\) 结尾的最大权值之和有贡献
代码
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=27;
int f[N],t,n;
int main()
{
for(cin>>t;t;t--)
{
memset(f,0,sizeof f);
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
f[s.back()-'a']=max(f[s.back()-'a'],(int)s.size()+f[s[0]-'a']);
}
int res=0;
for(int i=0;i<26;i++)res=max(res,f[i]);
cout< E.牛牛的方格图
题目描述
牛牛: “你喜欢玩数独吗? 。
牛牛有一个 \(n * m\) 的方格图，每个格子都有自己的颜色，第 \(i\) 行第 \(j\) 列格子上的颜色记为 \(\operatorname{col}(i, j)\) 。
对于任意两个不同位置的颜色相同的点，我们认为其覆盖了一个以它们为对角线上顶点的矩形中的所有点。
严格来说，一个点 \(P\left(i_{p}, j_{p}\right)\) 被覆盖，当且仅当存在两个点 \(A\left(i_{a}, j_{a}\right)\) 和 \(B\left(i_{b}, j_{b}\right)\) 使得以下四个条件都成立:
1: \(\operatorname{col}\left(i_{a}, j_{a}\right)=\operatorname{col}\left(i_{b}, j_{b}\right)\)
2: \(i_{a} \neq i_{b} \| j_{a} \neq j_{b}\)
3: \(\min \left(i_{a}, i_{b}\right) \leqslant i_{p} \leqslant \max \left(i_{a}, i_{b}\right)\)
4: \(\min \left(j_{a}, j_{b}\right) \leqslant j_{p} \leqslant \max \left(j_{a}, j_{b}\right)\)
现在牛牛想知道这张方格图中有多少个顶点尚末被覆盖。
输入描述:
第一行输入两个数 \(n, m\) 代表方格图的行数和列数。
接下来 \(n\) 行每行 \(m\) 个数描述了方格图中每个格子上的颜色。
\(0
输出描述:
输出一行一个整数代表答案。
示例1
输入
3 4
1 3 3 4
2 3 1 4
6 3 3 4
输出
1
说明
6所在方格未被覆盖。
解题思路
思维，二维前缀和
先将同一个颜色的位置提取出来，如果一个颜色出现的位置大于等于 \(2\)，则求出覆盖所有点的最小矩形，即找出最大和最小的横纵坐标，设定一个数组 \(ne[i][j]\)，表示位于 \((i,j)\) 连续覆盖的最左边的纵坐标，每次标记时可利用此数组快速标记未标记的位置，当然，也可以利用二维前缀和做标记
- 时间复杂度：\(O(100000+nm)\)
代码
// Problem: 牛牛的方格图
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11224/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e6+6,M=1005;
int n,m,x,ne[M][M];
vector c[N];
bool v[M][M];
int main()
{
read(n),read(m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)read(x),c[x].pb({i,j});
}
for(int i=0;i<=1e6;i++)
{
if(c[i].size()>1)
{
int x1=M,y1=M,x2=0,y2=0;
for(auto t:c[i])
{
x1=min(x1,t.fi);
y1=min(y1,t.se);
x2=max(x2,t.fi);
y2=max(y2,t.se);
}
for(int j=x1;j<=x2;j++)
for(int k=y1;k<=y2;k++)
{
if(v[j][k])k=ne[j][k];
else
{
ne[j][k]=y2;
v[j][k]=1;
}
}
}
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)res+=!v[i][j];
printf("%d",res);
return 0;
}
- 前缀和
// Problem: 牛牛的方格图
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11224/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e6+6,M=1005;
int n,m,x,s[M][M];
vector c[N];
bool v[M][M];
int main()
{
read(n),read(m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)read(x),c[x].pb({i,j});
}
for(int i=0;i<=1e6;i++)
{
if(c[i].size()>1)
{
int x1=M,y1=M,x2=0,y2=0;
for(auto t:c[i])
{
x1=min(x1,t.fi);
y1=min(y1,t.se);
x2=max(x2,t.fi);
y2=max(y2,t.se);
}
s[x1][y1]++;
s[x1][y2+1]--;
s[x2+1][y1]--;
s[x2+1][y2+1]++;
}
}
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1],res+=!s[i][j];
printf("%d",res);
return 0;
}