1 比赛
1.1 那23个路口
题目解析&题解
题意
给定一个$m $*$n$的权值图，求走23步后最大的可取的权值和。
分析
我们可以通过dp来解决此题。$dp[i][j][k]$表示在第$i$行$j$列走了$k$次最大的权值和。
那么可以轻易地得到$dp[i][j][k] = dp[i -1][j][k-1]+dp[i+1][j][k-1]+dp[i][j+1][k-1]+dp[i][j-1][k-1]$
Code
#include <iostream>
using namespace std;
const int N = 500 + 5;
const int fx[4] = {0, 0, -1, 1};
const int fy[4] = {-1, 1, 0, 0};
typedef long long ll;
int a[N][N];
ll f[N][N][25];
int n, m, sx, sy;
bool check_where(int x, int y)
{
return x < 1 ? false : x > n ? false : y < 1 ? false : y <= m;
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++ )
{
f[i][0][0] = -100000;
f[i][m + 1][0] = -100000;
for (int j = 1; j <= m; j ++ )
{
f[0][j][0] = -100000;
f[n + 1][j][0] = -100000;
cin >> a[i][j];
if (!a[i][j])
{
sx = i, sy = j;
}
f[i][j][0] = -100000;
}
}
f[sx][sy][0] = 0;
for (int k = 1; k <= 23; k ++ )
{
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
long long t = -100000000;
for (int e = 0; e < 4; e ++ )
{
int nx = i + fx[e];
int ny = j + fy[e];
if (!check_where(nx, ny))
{
continue;
}
t = max(t, f[nx][ny][k - 1]);
}
if (t <= -1 || a[i][j] == -1 || a[i][j] == 0)
{
f[i][j][k] = -100000;
continue;
}
f[i][j][k] = t + a[i][j];
}
}
}
ll res = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
res = max(res, f[i][j][23]);
}
}
cout << res;
}总结
认 真 读 题
1.2 我们的可可西里
题面&思路
题面
转眼到了2008年的6月9日，盼望已久的高考结束了。我们踏上了向西的旅程（本来是想写西去之路，可是考虑不太妥当）。可可西里，多么诱人的名词，充满了奇幻的色彩和自然的淳朴。从可可西里徒步走回家的决定是在1年半前定下的，而现在，终于可以实现那个钩过手指的预定。我们的可可西里。。。
在回家的路上，疯子和蚊子看到了许多可爱的藏羚羊，无意之中疯子和蚊子发现藏羚羊的居住地的分布也是有规律的，虽然疯子和蚊子早就听说藏羚羊是一种群体性很强又有超高IQ的动物，但是还是为它们的居住地分布规律感到惊叹。经过细心的观察，疯子和蚊子发现，如果假设一个藏羚羊群体有N只羊，就可以把它们的领地当做一个N*N的方阵，在这个方阵上第I列的第I 行都有一个圣地，它们不会居住在圣地，同时每行每列只能居住一只羚羊。于是他们很快算出一个有N只羊的藏羚羊群体的居住地分布方法数。
这是圣地的一种排列方法
思路
错排+高精。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int N = 2e3 + 5;
string f[N];
char c[10000], t[10000];
long long r[1000000];
string add(string a, string b)
{
strcpy(c, a.c_str());
strcpy(t, b.c_str());
int lena = a.size(), lenb = b.size();
for (int i = 0; i < lena; i ++ )
c[i] -= '0';
for (int i = 0; i < lenb; i ++ )
t[i] -= '0';
reverse(c, c + lena);
reverse(t, t + lenb);
int len = max(lena, lenb), jw = 0;
for (int i = 0; i < len; i ++ )
{
r[i] = c[i] + t[i] + jw;
jw = 0;
if (r[i] >= 10)
{
r[i] -= 10;
jw = 1;
}
}
if (jw)
{
r[len] = 1;
len ++;
}
string res = "";
for (int i = len - 1; i >= 0; i -- )
{
res += char(r[i] + '0');
}
return res;
}
string mul(string a, string b)
{
memset(r, 0, sizeof(r));
strcpy(c, a.c_str());
strcpy(t, b.c_str());
int lena = a.size(), lenb = b.size();
for (int i = 0; i < lena; i ++ )
c[i] -= '0';
for (int i = 0; i < lenb; i ++ )
t[i] -= '0';
reverse(c, c + lena);
reverse(t, t + lenb);
int len = max(lena, lenb), jw = 0;
for (int i = 0; i < lena; i ++ )
{
for (int j = 0; j < lenb; j ++ )
{
r[i + j] += c[i] * t[j];
}
}
for (int i = 0; i < lena + lenb; i ++ )
{
r[i] += jw;
jw = r[i] / 10;
r[i] %= 10;
}
if (jw)
{
r[lena + lenb] = jw;
}
lena ++;
string res = "";
bool flag = false;
for (int i = lena + lenb - 1; i >= 0; i -- )
{
if (r[i] > 0)
flag = true;
if (flag == true)
res += char(r[i] + '0');
}
return res;
}
string tostring(int x)
{
string res = "";
while (x >= 10)
{
res = char(x % 10 + '0') + res;
x /= 10;
}
res = char(x % 10 + '0') + res;
return res;
}
int main()
{
int n;
cin >> n;
f[2] = "1";
for (int i = 3; i <= n; i ++ )
{
f[i] = mul(tostring(i - 1), add(f[i - 1], f[i - 2]));
//cout << tostring(i - 1) << "-" << add(f[i - 1], f[i - 2]) << endl;
//cout << endl;
//cout << f[i] << endl;
//cout << endl;
//cout << endl;
}
cout << f[n];
return 0;
}
//dn=(n-1)*(dn-1 + dn-2)总结
先写错排再写高精是好方法。
[heimu]这题高精太**难写了[/heimu]
[heimu]剩下两题摸了[/heimu]
2.L C A
2.1 P2937 [USACO09JAN]Laserphones S
[heimu]BFS好题[/heimu]
以上。
2.2 P3398 仓鼠找sugar
思路
我们可以假设若存在$a, b$与$c, d$路径相交。[heimu]不妨[/heimu]设$x=lca(a, b)$以及$y=lca(c, d)$。
那么因为$a, b$与$c, d$路径相交，则$x$在$c,d$上或$y$在$a,b$上。
好，我们再来设定$z$在$a,b$上，并且$z$与$c,d$相交。那么可以确认的就是$x,y$为$z$的祖先（不管多上面）
那么$x, y$的那个更深的那个，一定在另一个路径上。
那么问题就改成了给定一个点，确认这个点是否在另一条边上。（在此题中即判断$x是否在c,d边上，y是否在a,b边上。$）
判断方法为：
$$ dis_{x,a} +dis_{x,b}=dis_{a,b} \\dis_{a,b}=deep_a+deep_b-2*deep_{(lca(a,b))} $$
然后就可以解决这道题了awa
// Problem: P3398 仓鼠找sugar
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3398
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, q;
vector<int> g[N];
int d[N], f[N][20];
void dfs(int x, int y)
{
d[x] = d[y] + 1;
f[x][0] = y;
int len = g[x].size();
for (int i = 0; i < len; i ++ )
{
if (g[x][i] != y)
{
dfs(g[x][i], x);
}
}
}
int lca(int x, int y)
{
if (d[x] < d[y])
{
swap(x, y);
}
for (int i = 19; i >= 0; i -- )
{
if (d[f[x][i]] >= d[y])
{
x = f[x][i];
}
}
if (x == y)
{
return x;
}
for (int i = 19; i >= 0; i -- )
{
if (f[x][i] != f[y][i])
{
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int dis(int x, int y)
{
return d[x] + d[y] - 2 * d[lca(x, y)];
}
int main()
{
cin >> n >> q;
for (int i = 1; i < n; i ++ )
{
int l, r;
cin >> l >> r;
g[l].push_back(r);
g[r].push_back(l);
}
dfs(1, 0);
for (int i = 1; i <= 19; i ++ )
for (int j = 1; j <= n; j ++ )
f[j][i] = f[f[j][i - 1]][i - 1];
while (q --)
{
int ca, cb, cc, cd;
cin >> ca >> cb >> cc >> cd;
int x = lca(ca, cb);
int y = lca(cc, cd);
if (d[x] > d[y])
{ // x on c, d
cout << ((dis(x, cc) + dis(x, cd) == dis(cc, cd)) ? 'Y' : 'N') << endl;
}
else
{ // y on a, b
cout << ((dis(y, ca) + dis(y, cb) == dis(ca, cb)) ? 'Y' : 'N') << endl;
}
}
return 0;
}