20191114测试总结

CSP-S模拟总算有点CSP的样子了正解仍然十分不CSP-S

T1:WOJ4819

用dij跑一下宝藏之间两两的最小消费,然后10!枚举一下走到宝藏的顺序即可
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, k, t, lx, rx, r, g, b, sum, cnt, xt[15], yt[15], use[15], aa[505][505], head[505][505], vis[505][505];
long long ans = -0x7f7f7f7f7f7f7f7f, num, dis[505][505], w[15][15];
char s[505];
struct node
{
int x;
int y;
long long dis;
node(int aa, int bb, long long cc)
{
x = aa;
y = bb;
dis = cc;
}
bool operator<(const node &bb) const
{
return dis > bb.dis;
}
};
priority_queue<node> q;
struct point
{
int x;
int y;
int w;
int nxt;
} a[2000005];
void ins(int x, int y, int xx, int yy, int w)
{
++sum;
a[sum].x = xx;
a[sum].y = yy;
a[sum].w = w;
a[sum].nxt = head[x][y];
head[x][y] = sum;
return;
}
void dijkstra(int x, int y)
{
memset(vis, 0, sizeof(vis));
memset(dis, 0x7f, sizeof(dis));
dis[x][y] = 0;
q.push(node(x, y, 0));
while (!q.empty())
{
node id = q.top();
q.pop();
int kx = id.x, ky = id.y;
if (vis[kx][ky])
continue;
vis[kx][ky] = 1;
int d = head[kx][ky];
while (d)
{
int xx = a[d].x, yy = a[d].y;
if (dis[a[d].x][a[d].y] > dis[kx][ky] + a[d].w)
{
dis[a[d].x][a[d].y] = dis[kx][ky] + a[d].w;
q.push(node(a[d].x, a[d].y, dis[a[d].x][a[d].y]));
}
d = a[d].nxt;
}
}
return;
}
void dfs(int id)
{
if (cnt >= lx && cnt <= rx)
ans = max(ans, num);
if (cnt == rx)
return;
++cnt;
num += t;
for (int i = 1; i <= k; ++i)
if (!use[i])
{
use[i] = 1;
num -= w[id][i];
dfs(i);
num += w[id][i];
use[i] = 0;
}
num -= t;
--cnt;
return;
}
int main()
{
scanf("%d%d%d%d%d%d%d%d", &n, &k, &t, &lx, &rx, &r, &g, &b);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1);
for (int j = 1; j <= n; ++j)
if (s[j] == 'S')
{
xt[0] = i;
yt[0] = j;
}
else if (s[j] == 'T')
{
++cnt;
xt[cnt] = i;
yt[cnt] = j;
}
else if (s[j] == 'R')
aa[i][j] = r;
else if (s[j] == 'G')
aa[i][j] = g;
else if (s[j] == 'B')
aa[i][j] = b;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
if (i != 1)
ins(i, j, i - 1, j, aa[i - 1][j]);
if (i != n)
ins(i, j, i + 1, j, aa[i + 1][j]);
if (j != 1)
ins(i, j, i, j - 1, aa[i][j - 1]);
if (j != n)
ins(i, j, i, j + 1, aa[i][j + 1]);
}
for (int i = 0; i <= k; ++i)
{
dijkstra(xt[i], yt[i]);
for (int j = 1; j <= k; ++j)
w[i][j] = dis[xt[j]][yt[j]];
}
cnt = 0;
dfs(0);
printf("%lld", ans);
}

T2:WOJ4821

发现T2和T3数据放反了,然后刷新之后发现直接交换了T2、T3的题目名称???这是个什么神奇的操作。

对于一条链上,只要前缀gcd一刷新至少要小一半,因此总共只有log个不同的gcd的值,那么一个点到根节点的链上显然只有在gcd交接的log个位置可能产生最优解。我们对于每个叶节点dfs一次就可以找到所有的链,然后刷新答案即可。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;
int n, sum, w[200005], num[200005], head[200005], dep[200005];
long long ans;
struct node
{
int v;
int nxt;
} a[400005];
struct point
{
int id;
int val;
point(int aa, int bb)
{
id = aa;
val = bb;
}
};
vector<point> v[200005];
void ins(int u, int v)
{
++sum;
a[sum].v = v;
a[sum].nxt = head[u];
head[u] = sum;
return;
}
int gcd(int a, int b)
{
if (!b)
return a;
return gcd(b, a % b);
}
void dfs(int k, int fa)
{
v[k] = v[fa];
v[k].push_back(point(k, w[k]));
for (int i = 0; i < v[k].size(); ++i)
{
v[k][i] = point(v[k][i].id, gcd(v[k][i].val, w[k]));
ans = max(ans, (long long)(dep[k] - dep[v[k][i].id] + 1) * v[k][i].val);
}
int j = 0;
for (int i = 0; i < v[k].size(); ++i)
if (v[k][i].val != v[k][i - 1].val)
v[k][j++] = v[k][i];
while (v[k].size() > j)
v[k].pop_back();
int d = head[k];
while (d)
{
if (a[d].v != fa)
{
dep[a[d].v] = dep[k] + 1;
dfs(a[d].v, k);
}
d = a[d].nxt;
}
}
int main()
{
int size=40<<20;//40M
//__asm__ ("movl %0, %%esp\n"::"r"((char*)malloc(size)+size));//调试用这个
__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//提交用这个
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
for (int i = 1; i < n; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
ins(u, v);
ins(v, u);
++num[u];
++num[v];
}
for (int i = 1; i <= n; ++i)
if (num[i] == 1)
{
dep[i] = 0;
dfs(i, 0);
}
printf("%lld", ans);
exit(0);
}

T3:WOJ4820

又是毒瘤计数题。。。反正慢慢推总能推出来的

dp[i][j]表示从左往右选到第i个数,这i个数在形成安排的序列中形成了j个连通块

然后推导就如代码所示了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 1000000007
using namespace std;
int n, s, e, ans, dp[2005][2005];
char S[2005];
int main()
{
char ch = getchar();
while (ch < 'A' || ch > 'Z')
ch = getchar();
while (ch >= 'A' && ch <= 'Z')
{
S[++n] = ch;
ch = getchar();
}
scanf("%d%d", &s, &e);
dp[0][0] = 1;
for (int i = 0; i <= n - 2; ++i)
for (int j = (i > 0); j <= i; ++j)
{
if (dp[i][j] == 0)
continue;
char k = S[i + 1];
long long val = dp[i][j];
int free = j;
if (i >= s)
free--;
if (i >= e)
free--;
if (free < 0)
continue;
if (i + 1 == s)
{
if (k == 'R' || k == 'B')
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
if (k == 'L' || k == 'B')
dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
}
else if (i + 1 == e)
{
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
}
else
{
if (k == 'R' || k == 'B')
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + val) % mod;
if (i + 1 > s && (k == 'R' || k == 'B'))
dp[i + 1][j] = (dp[i + 1][j] + val) % mod;
if (i + 1 > s && (k == 'L' || k == 'B') && j)
dp[i + 1][j - 1] = (dp[i + 1][j - 1] + val * free) % mod;
if (i + 1 > e && (k == 'L' || k == 'B'))
dp[i + 1][j] = (dp[i + 1][j] + val) % mod;
if (i + 1 > e && (k == 'L' || k == 'B') && j)
dp[i + 1][j - 1] = (dp[i + 1][j - 1] + val * free) % mod;
if (k == 'L' || k == 'B')
dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
if (k == 'R' || k == 'B')
dp[i + 1][j] = (dp[i + 1][j] + val * free) % mod;
if (free >= 2 && (k == 'L' || k == 'B'))
dp[i + 1][j - 1] = (dp[i + 1][j - 1] + free * (free - 1) % mod * val) % mod;
}
}
if (n == s)
{
if (S[n] == 'L' || S[n] == 'B')
ans = dp[n - 1][1];
}
else if (n == e)
ans = dp[n - 1][1];
else if (S[n] == 'L' || S[n] == 'B')
ans = dp[n - 1][2];
printf("%d", ans);
return 0;
}

评论

此博客中的热门博文

min-max反演