Day6去玩了
8.7比赛
e
T1 。。。应该没人质疑我略过吧
T2 同上
T3 不能再不写了，不然YY要找我算账了
不知道为啥WA了2个点
反正补对了 首先：膜拜wbz大佬！！！！！
T4 贪心一下，不想发代码（学习某超重舞者（接受来自南京的膜拜吧）贴代码精神）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 31536000, N = 1e5 + 10;
inline int read() {
int s = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return s * f;
}
int n, ans;
struct node {
int a, b;
bool operator<(const node &o) const { return a + o.b * a < b + o.a * b; }
} a[N];
signed main(void) {
n = read();
for (int i = 1; i <= n; i++) a[i] = { read(), read() };
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
ans += ans * a[i].b + a[i].a;
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
T5
不想开八维（厉害的zgc他们都开出来了，膜拜zgc大佬！！！！！
bfs+哈希一下吧
#include <bits/stdc++.h>
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define Si signed
#define Us unsigned
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f, Ki = 18000000, Kj = 1500005;
struct Node {
int x[5], y[5], ans;
} node[Kj];
int fx[] = { 1, 0, -1, 0 }, fy[] = { 0, 1, 0, -1 };
int n, m;
int tot;
int Hash(Node asks) {
int res = 0;
fup(i, 0, 3) res = res * (1 << 6) + (asks.x[i] - 1) * m + (asks.y[i] - 1);
return res;
}
char s[10][10];
bool mark[Ki];
bool AskNode(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && s[x][y] != '#'; }
int bfs() {
int head = 0, tail = 1;
while (head < tail) {
Node tmp = node[head++];
fup(i, 0, 3) {
Node now = tmp;
now.x[0] += fx[i], now.y[0] += fy[i];
if (not AskNode(now.x[0], now.y[0]))
continue;
bool flag = 0;
fup(j, 1, 3) if (now.x[0] == now.x[j] && now.y[0] == now.y[j]) {
now.x[j] += fx[i], now.y[j] += fy[i];
if (not AskNode(now.x[j], now.y[j])) {
flag = 1;
break;
}
fup(k, 1, 3) if (k != j && now.x[j] == now.x[k] && now.y[j] == now.y[k]) {
flag = 1;
break;
}
}
if (flag)
continue;
++now.ans;
flag = 1;
fup(j, 1, 3) if (s[now.x[j]][now.y[j]] != '@') {
flag = 0;
break;
}
if (flag)
return now.ans;
int hashx = Hash(now);
if (mark[hashx])
continue;
mark[hashx] = 1;
node[tail++] = now;
}
}
return -1;
}
Si main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
scanf("%d%d", &n, &m);
fup(i, 1, n) {
scanf("%s", s[i] + 1);
fup(j, 1, m) {
if (s[i][j] == 'X')
node[0].x[0] = i, node[0].y[0] = j;
if (s[i][j] == '*')
node[0].x[++tot] = i, node[0].y[tot] = j;
}
}
node[0].ans = 0;
printf("%d", bfs());
getchar();
getchar();
return 0;
}T
T6
区间DP吧 e 赛时直接一刀A了 顺便：膜拜cqr大佬！！！！！
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
string s1, s2;
int ls;
int a[N];
int dp[N][N];
signed main(void) {
cin >> s1 >> s2;
s1 = ' ' + s1;
s2 = ' ' + s2;
ls = s1.size() - 1;
memset(dp, 0x3f, sizeof dp);
memset(a, 0x3f, sizeof a);
for (int i = 1; i <= ls; i++) dp[i][i] = 1;
for (int len = 2; len <= ls; len++) {
for (int i = 1; i + len - 1 <= ls; i++) {
int j = i + len - 1;
if (s2[i] == s2[j])
dp[i][j] = dp[i][j - 1];
else
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
for (int i = 1; i <= ls; i++) {
a[i] = dp[1][i];
if (s1[i] == s2[i])
a[i] = a[i - 1];
for (int j = 0; j <= i; j++)
a[i] = min(a[i], a[j] + dp[j + 1][i]);
}
printf("%d\n", a[ls]);
return 0;
}
T7
树形DP？？？
震惊我千年
#include <bits/stdc++.h>
#define fup(i, a, b) for (int(i) = (a); (i) <= (b); ++(i))
#define fdown(i, a, b) for (int(i) = (a); (i) >= (b); --(i))
#define Si signed
#define Us unsigned
using namespace std;
typedef long long ll;
const int inf = 1e9 + 10;
int n, q;
int head[1000010], nxt[2000010], to[2000010], cnt = 0;
int id[1000010], dp[1000010], mn[1000010], mn2[1000010];
int fa[1000010];
int st = 0, ed = 0;
int Q[1000010];
int len = 0;
int a[1000010];
inline int read() {
int p = 0, q = 1;
char ch = getchar();
while (!isdigit(ch)) q = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) p = (p << 3) + (p << 1) + (ch ^ 48), ch = getchar();
return p * q;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 1000010; i++) id[i] = head[i] = -1, dp[i] = mn[i] = mn2[i] = inf;
while (~scanf("%d%d", &n, &q)) {
for (int i = 0; i < n - 1; i++) {
int u = read() - 1, v = read() - 1;
nxt[cnt] = head[u];
to[cnt] = v;
head[u] = cnt++;
nxt[cnt] = head[v];
to[cnt] = u;
head[v] = cnt++;
}
for (int i = head[0]; i != -1; i = nxt[i]) {
st = ed = len = 0;
Q[ed++] = to[i];
fa[to[i]] = 0;
while (st < ed) {
int x = Q[st++];
id[x] = to[i];
a[len++] = x;
for (int j = head[x]; j != -1; j = nxt[j]) {
if (to[j] != fa[x]) {
fa[to[j]] = x;
Q[ed++] = to[j];
}
}
}
for (int j = len - 1; j >= 0; j--) {
mn[a[j]] = min(mn[a[j]], a[j]);
if (fa[a[j]] != 0)
mn[fa[a[j]]] = min(mn[fa[a[j]]], mn[a[j]]);
}
st = ed = 0;
Q[ed++] = to[i];
while (st < ed) {
int x = Q[st++];
int tmp = inf;
len = 0;
dp[x] = mn2[x];
for (int j = head[x]; j != -1; j = nxt[j]) {
if (to[j] != fa[x]) {
mn2[to[j]] = min(mn2[x], tmp);
tmp = min(tmp, mn[to[j]]);
a[len++] = to[j];
}
}
tmp = inf;
for (int j = len - 1; j >= 0; j--) {
dp[x] = min(dp[x], mn[a[j]]);
mn2[a[j]] = min(mn2[a[j]], tmp);
tmp = min(tmp, mn[a[j]]);
}
for (int j = 0; j < len; j++) Q[ed++] = a[j];
}
}
int num[4] = { -1, -1, -1, -1 };
for (int i = head[0]; i != -1; i = nxt[i]) {
num[3] = to[i];
for (int j = 2; j >= 0; j--) {
if (num[j] == -1 || mn[num[j + 1]] < mn[num[j]])
swap(num[j + 1], num[j]);
}
}
int ans = 0;
for (int t = 0; t < q; t++) {
int u = read() ^ ans, v = read() ^ ans;
u--;
v--;
ans = inf;
if (u == 0 || v == 0) {
if (u == v)
ans = 1;
else {
if (u != 0)
swap(u, v);
ans = dp[v];
for (int i = 0; i < 3; i++) {
if (num[i] != id[v] && num[i] != -1) {
ans = min(ans, mn[num[i]]);
}
}
}
} else if (id[u] == id[v])
ans = 0;
else {
ans = min(dp[u], dp[v]);
for (int i = 0; i < 3; i++) {
if (num[i] != id[u] && num[i] != id[v] && num[i] != -1)
ans = min(ans, mn[num[i]]);
}
}
ans++;
printf("%d\n", ans);
}
for (int i = 0; i < n; i++) dp[i] = mn[i] = mn2[i] = inf, id[i] = head[i] = -1;
cnt = 0;
}
return 0;
}
T8
You：太简单了
I：你说得对，但我不会
c
总之
膜拜cye/c and cjx DALAO ！！！！！