CodeForces Round #286 Div.2

时间:2023-03-08 16:04:48

A. Mr. Kitayuta's Gift (枚举)

题意:

给一个长度不超过10的串,问能否通过插入一个字符使得新串成为回文串。

分析:

因为所给的串很多,所以可以枚举 “在哪插入” 和 “插入什么”,写一个二重循环枚举新串,判断是否为回文串。时间复杂度为O(n3)

还可只枚举插入位置(在那个位置用一个特殊字符表示),在判断的时候,如果遇到特殊字符,则所插入的字符一定为镜像的字符。

 #include <cstdio>
#include <cstring> char s[], s1[];
int l; bool judge()
{
for(int i = ; i < (l+)/; ++i)
if(s1[i] == ) s1[i] = s1[l-i];
else if(s1[l-i] == ) s1[l-i] = s[i];
else if(s1[i] != s1[l-i]) return false; return true;
} int main()
{
scanf("%s", s);
l = strlen(s);
bool flag = false;
for(int pos = ; pos <= l; ++pos)
{//枚举所加入字符的位置,s1为得到的新串
int i;
for(i = ; i < pos; ++i) s1[i] = s[i];
s1[i++] = ;
for(; i <= l; ++i)s1[i] = s[i-];
if(judge()) { flag = true; break; }
} if(!flag) puts("NA");
else
{
for(int i = ; i <= l; ++i)
if(s1[i] == ) printf("a");
else printf("%c", s1[i]);
} return ;
}

代码君

B. Mr. Kitayuta's Colorful Graph (并查集)

题意:

有一个多种颜色的无向图,给出每条边的两个顶点以及该边的颜色。

然后有若干次询问,每次询问两点间共有多少种颜色的通路。

分析:

这道题可以理解为二维的并查集。如果没有颜色的区分,可以判断两点是否连通。

现在给边染上颜色,则我们可以分开处理。最后在询问的时候枚举所有颜色,判断两点是否连通。

 #include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ; int G[maxn][maxn];
int n, m;
int p[maxn][maxn];
//找颜色为color的边中,x的父节点
int findp(int color, int x) { return x == p[color][x] ? x : p[color][x] = findp(color, p[color][x]); } struct Edge
{
int u, v;
Edge(int u=, int v=):u(u), v(v) {}
}; vector<Edge> edges[maxn]; int main()
{
//freopen("in.txt", "r", stdin);
int n, m, Mc = ;
scanf("%d%d", &n, &m);
//并查集初始化
for(int i = ; i <= m; ++i)
for(int j = ; j <= n; ++j)
p[i][j] = j; for(int i = ; i < m; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
Mc = max(Mc, c);
int pa = findp(c, a);
int pb = findp(c, b);
if(pa != pb) p[c][pa] = pb;
} int Q;
scanf("%d", &Q);
for(int i = ; i < Q; ++i)
{
int u, v, cnt = ;
scanf("%d%d", &u, &v);
for(int c = ; c <= Mc; ++c) //枚举所有颜色
if(findp(c, u) == findp(c, v))
cnt++;
printf("%d\n", cnt);
} return ;
}

代码君

C. Mr. Kitayuta, the Treasure Hunter (DP)

题意:

参见原文吧,=_=||

Mr. Kitayuta, the Treasure Hunter

分析:

设dp(i, j)表示跳到第i个岛步长为j,wi表示第i个岛的宝石数,最大能取到的宝石数。

状态转移方程为 dp(i, j) = wi + max{dp(i+j-1, j-1), dp(i+j, j), dp(i+j+1, j+1)}

上式是从后往前推的,最终答案是dp(d, d)。

从前往后推也是一样的,不过要维护一个最大值。

还有一个很严重的问题就是:30000×30000的空间太大了!

再深入分析,其实步长的变化范围没有3w那么大。

假设每一步步长为前面步长加一,可以求出最大步长。类似地,求出最小步长。

假设d=1,最大步长不会超过245 + d,因为CodeForces Round #286 Div.2

同样的,如果d≤244,则最小步长为0.

如果d≥245,CodeForces Round #286 Div.2

所以,最小步长不会小于max{0, d - 245}.

 #include <cstdio>
#include <algorithm>
using namespace std; int max3(int a, int b, int c)
{ return max(max(a, b), c); } int w[], dp[][]; int main()
{
//freopen("in.txt", "r", stdin); int n, d;
scanf("%d%d", &n, &d);
for(int i = ; i < n; ++i)
{
int x;
scanf("%d", &x);
w[x]++;
} int maxp, minp = ;
for(int n = ; ; n++) if(d*(n+)+n*(n+)/ >= )
{
maxp = d + n; //最大步长
break;
}
for(int n = ; d >= ; n++) if(d*(n+)-n*(n+)/ >= )
{
minp = d - n; //最小步长
break;
} for(int x = ; x >= d; --x)
for(int l = minp; l <= maxp; ++l)
dp[x][l-minp+] = w[x] + max3(dp[x+l][l-minp+], dp[x+l+][l+-minp], dp[x+l-][l-minp]); printf("%d\n", dp[d][d+-minp]); return ;
}

代码君