20191108测试总结

又爆零了。。。明天再爆零我女装(flag)

T1:WOJ4803

2019高考原题,推一下式子就可以直接O(n)过了,甚至不需要矩阵快速幂。我考试的时候大概傻了。。。
#include <iostream>
#include <cstdio>
#define mod 1000000007
using namespace std;
int n, aa, bb, a, b, c, x, y, inv, f[20000005];
void exgcd(int p, int q)
{
if (!q)
{
x = 1;
y = 0;
return;
}
exgcd(q, p % q);
int tmp = x;
x = y;
y = tmp - p / q * y;
return;
}
int main()
{
scanf("%d%d%d", &n, &aa, &bb);
a = (long long)(mod + 1 - aa) * bb % mod;
b = ((long long)aa * bb % mod + (long long)(mod + 1 - aa) * (mod + 1 - bb) % mod) % mod;
c = (long long)aa * (mod + 1 - bb) % mod;
exgcd(c, mod);
inv = (x % mod + mod) % mod;
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= 2 * n; ++i)
f[i] = ((long long)(mod + 1 - b) * f[i - 1] + (long long)(mod - a) * f[i - 2]) % mod * inv % mod;
exgcd(f[2 * n], mod);
inv = (x % mod + mod) % mod;
printf("%d", (long long)f[n] * inv % mod);
return 0;
}

T2:WOJ4804

大模拟。考试的时候写链表写炸了,写成了环形链表,调了半天调不出来。晚上重构了一个deque和vector版就过了。
#include <iostream>
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> q;
deque<int> a[105];
int n, m, l, s, t, cnt, ans[105], b[10005], fa[10005];
int main()
{
while (scanf("%d%d%d%d%d", &n, &m, &l, &s, &t))
{
if (n == -1 && m == -1 && l == -1 && s == -1 && t == -1)
break;
q.clear();
cnt = 0;
for (int i = 1; i <= n; ++i)
{
ans[i] = 0;
a[i].clear();
for (int j = 1; j <= l; ++j)
{
int k;
scanf("%d", &k);
a[i].push_back(k);
b[++cnt] = k;
}
}
b[++cnt] = s;
sort(b + 1, b + cnt + 1);
cnt = unique(b + 1, b + cnt + 1) - b - 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < a[i].size(); ++j)
a[i][j] = lower_bound(b + 1, b + cnt + 1, a[i][j]) - b;
s = lower_bound(b + 1, b + 1 + cnt, s) - b;
for (int i = 1; i <= cnt; ++i)
fa[i] = -1;
for (int i = 1; i <= t; ++i)
{
int num = 0;
for (int j = 1; j <= n; ++j)
if (!a[j].empty())
{
int k = a[j].front();
a[j].pop_front();
if (k != s)
{
if (fa[k] >= 0)
{
int tmp = fa[k];
for (int kk = tmp; kk < q.size(); ++kk)
{
a[j].push_back(q[kk]);
fa[q[kk]] = -1;
}
a[j].push_back(k);
while (q.size() > tmp)
q.pop_back();
}
else
{
q.push_back(k);
fa[k] = q.size() - 1;
}
}
else
{
if (q.empty())
q.push_back(k);
else
{
for (int kk = 0; kk < q.size(); ++kk)
{
a[j].push_back(q[kk]);
fa[q[kk]] = -1;
}
a[j].push_back(k);
q.clear();
}
}
if (!a[j].empty())
++num;
else
ans[j] = i;
}
if (num <= 1)
break;
}
for (int i = 1; i <= n; ++i)
if (ans[i])
printf("-%d ", ans[i]);
else
printf("%d ", a[i].size());
putchar('\n');
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < a[i].size(); ++j)
printf("%d ", b[a[i][j]]);
putchar('\n');
}
}
return 0;
}

T3:WOJ4805

被搬到了树上的蒲公英。。。毒瘤数分块,CSP多半不会考这种题(吧?),因此为了节约时间刷没刷完的往届的NOIP题就先咕了(虽然多半永远的咕了)

代码放的std。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fir first
#define sec second

typedef unsigned uint32;
typedef pair<int, int> PII;

namespace io {
void gi(int &ret) {
static char ch;
while (ch = getchar(), !isdigit(ch))
;
ret = ch - '0';
while (ch = getchar(), isdigit(ch)) {
ret = ret * 10 + ch - '0';
}
}

void print(int ret) {
static int qu[15], po;
do {
qu[++po] = ret % 10;
ret /= 10;
} while(ret);
while (po != 0) {
putchar(qu[po--] + '0');
}
}
}
using io::gi;
using io::print;

const int Max_N = 100005;
const int Max_S = 735;

inline void tension(int &c, int &r, int cur_c, int cur_r) {
if (c <= cur_c) {
if (c < cur_c) {
c = cur_c, r = cur_r;
} else {
if (r > cur_r) {
r = cur_r;
}
}
}
}

int N, Q, type, lastans, col[3][Max_N];
int head[Max_N], adj[Max_N * 2 + 1], nxt[Max_N * 2 + 1], total;

inline void addedge(int u, int v) {
++total, adj[total] = v, nxt[total] = head[u], head[u] = total;
}

namespace Tree {
int euler_clock, fir[Max_N], ST[19][(Max_N << 1) + 1], lg[(Max_N << 1) + 1];
int dep[Max_N], fa[Max_N], dfn[Max_N], dfs_clock;

void dfs(int u, int f) {
dfn[u] = ++dfs_clock;
ST[0][++euler_clock] = u, fir[u] = euler_clock;
for (int i = head[u]; i; i = nxt[i]) {
if (adj[i] != f) {
dep[ adj[i] ] = dep[u] + 1;
fa[ adj[i] ] = u;
dfs(adj[i], u);
ST[0][++euler_clock] = u;
}
}
}

inline int get_lca(int u, int v) {
int l = fir[u], r = fir[v], k;
if (l > r) {
swap(l, r);
}
k = lg[r - l + 1];
return dep[ ST[k][l] ] < dep[ ST[k][r - (1 << k) + 1] ] ? ST[k][l] : ST[k][r - (1 << k) + 1];
}

void init() {
lg[0] = -1;
for (int i = 1; i <= N * 2 - 1; i++) {
lg[i] = lg[i >> 1] + 1;
}
dfs(1, 0);
for (int i = 1; i <= 17; i++) {
for (int j = 1; j + (1 << i) - 1 <= euler_clock; j++) {
ST[i][j] = dep[ ST[i - 1][j] ] < dep[ ST[i - 1][j + (1 << (i - 1))] ] ? ST[i - 1][j] : ST[i - 1][j + (1 << (i - 1))];
}
}
}

bool comp_vt(int x, int y) {
return dfn[x] < dfn[y];
}

bool comp_d(int x, int y) {
return dep[x] > dep[y];
}
}
using Tree::get_lca;
using Tree::comp_vt;
using Tree::comp_d;
using Tree::dep;
using Tree::dfn;
using Tree::fa;

void build_vt(vector<int> &que) {
static int stk[Max_N], top;
static vector<int> P;
sort(que.begin(), que.end(), comp_vt);
que.resize(unique(que.begin(), que.end()) - que.begin());
stk[top = 1] = que[0], P.clear(), P.pb(que[0]);
for (size_t i = 1; i < que.size(); i++) {
int lca = get_lca(stk[top], que[i]);
if (lca == stk[top]) {
stk[++top] = que[i];
} else {
while (top > 1 && dep[ stk[top - 1] ] >= dep[lca]) {
--top;
}
if (stk[top] != lca) {
P.pb(lca), stk[top] = lca;
}
stk[++top] = que[i];
}
P.pb(que[i]);
}
que = P;
}

namespace Blocks {
int id[Max_N], up[Max_N], down[Max_N];
int mode[Max_S][Max_S], cnt[Max_S][Max_S], lca[Max_S][Max_S], sum[Max_S][Max_N];
char val[Max_S][Max_N];

vector<int> Key;

int cur[Max_N];
int ext_c[Max_N], visited[Max_N], stk[Max_N], top = 0;

void predfs(int u, int f) {
for (int k = 0; k < 3; k++) {
++cur[ col[k][u] ];
}
if (id[u] != -1) {
for (int i = 1; i <= N; i++) {
sum[ id[u] ][i] = cur[i];
}
}
for (int i = head[u]; i; i = nxt[i]) {
if (adj[i] != f) {
predfs(adj[i], u);
}
}
for (int k = 0; k < 3; k++)
--cur[ col[k][u] ];
}

void dfs(int u, int f, int fr, int cur_c, int cur_m) {
for (int k = 0; k < 3; k++) {
++cur[ col[k][u] ];
tension(cur_c, cur_m, cur[ col[k][u] ], col[k][u]);
}
if (id[u] != -1) {
mode[fr][ id[u] ] = cur_m, cnt[fr][ id[u] ] = cur_c;
}
for (int i = head[u]; i; i = nxt[i]) {
if (adj[i] != f) {
dfs(adj[i], u, fr, cur_c, cur_m);
}
}
for (int k = 0; k < 3; k++) {
--cur[ col[k][u] ];
}
}

void get_up(int u, int f, int ff) {
if (id[u] != -1) {
ff = u;
}
up[u] = ff;
for (int i = head[u]; i; i = nxt[i]) {
if (adj[i] != f) {
get_up(adj[i], u, ff);
}
}
}

void get_down(int u, int f) {
down[u] = id[u] == -1 ? -1 : u;
for (int i = head[u]; i; i = nxt[i])
if (adj[i] != f) {
get_down(adj[i], u);
if (down[u] == -1 && down[ adj[i] ] != -1) {
down[u] = down[ adj[i] ];
}
}
}

inline int query(int x, int y, int c) {
int u = id[x], v = id[y], f = lca[u][v];
return sum[u][c] + sum[v][c] - 2 * sum[f][c] + val[f][c];
}

void query(int u, int v) {
int _lca = get_lca(u, v), cur_r = N + 1, cur_c = 0;
if (up[u] == up[v]) {
while (u != _lca) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][u] ], stk[++top] = col[k][u];
}
u = fa[u];
}
while (v != _lca) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][v] ], stk[++top] = col[k][v];
}
v = fa[v];
}
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][_lca] ], stk[++top] = col[k][_lca];
}
for (int i = 1; i <= top; i++) {
if(!visited[ stk[i] ]) {
tension(cur_c, cur_r, ext_c[ stk[i] ], stk[i]);
visited[ stk[i] ] = true;
}
}
} else {
if ((dep[ up[u] ] < dep[_lca]) || (dep[ up[v] ] < dep[_lca])) {
if (dep[ up[v] ] < dep[_lca]) {
swap(u, v);
}
while (v != up[v]) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][v] ], stk[++top] = col[k][v];
}
v = fa[v];
}
while (u != _lca) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][u] ], stk[++top] = col[k][u];
}
u = fa[u];
}
int p = fa[ down[u] ];
while (p != u) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][p] ], stk[++top] = col[k][p];
}
p = fa[p];
}
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][u] ], stk[++top] = col[k][u];
}
u = down[u];
}
else {
while (v != up[v]) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][v] ], stk[++top] = col[k][v];
}
v = fa[v];
}
while (u != up[u]) {
for (int k = 0; k < 3; k++) {
++ext_c[ col[k][u] ], stk[++top] = col[k][u];
}
u = fa[u];
}
}
cur_c = cnt[ id[u] ][ id[v] ], cur_r = mode[ id[u] ][ id[v] ];
for (int i = 1; i <= top; i++) {
if (!visited[ stk[i] ]) {
tension(cur_c, cur_r, ext_c[ stk[i] ] + query(u, v, stk[i]), stk[i]);
visited[ stk[i] ] = true;
}
}
}
print(cur_c), putchar(' '), print(cur_r), putchar('\n');
lastans ^= cur_c, lastans ^= cur_r;
for (int i = 1; i <= top; i++) {
visited[ stk[i] ] = false;
ext_c[ stk[i] ] = 0;
}
top = 0;
}

void init() {
static int P[Max_N], dist[Max_N];
for (int i = 1; i <= N; i++) {
P[i] = i, dist[i] = 0;
}
sort(P + 1, P + 1 + N, comp_d);
for (int i = 1; i <= N; i++) {
for (int j = head[ P[i] ]; j; j = nxt[j]) {
if (adj[j] != fa[ P[i] ]) {
dist[ P[i] ] = max(dist[ P[i] ], dist[ adj[j] ] + 1);
}
}
if (P[i] == 1 || dist[ P[i] ] >= 225) {
dist[ P[i] ] = 0, Key.pb(P[i]);
}
}
build_vt(Key);
memset(id, -1, sizeof(id));
for (size_t i = 0; i < Key.size(); i++) {
id[ Key[i] ] = i;
for (int k = 0; k < 3; k++)
++val[i][ col[k][ Key[i] ] ];
}
for (size_t i = 0; i < Key.size(); i++) {
for (size_t j = 0; j < Key.size(); j++) {
lca[i][j] = id[ get_lca(Key[i], Key[j]) ];
}
}
predfs(1, 0);
for (size_t i = 0; i < Key.size(); i++) {
dfs(Key[i], 0, i, 0, N + 1);
}
get_up(1, 0, -1);
get_down(1, 0);
}
}

void __main__() {
gi(type);
gi(N);
for (int i = 1; i <= N; i++) {
for (int k = 0; k < 3; k++) {
gi(col[k][i]);
}
}
for (int u, v, i = 1; i <= N - 1; i++) {
gi(u), gi(v);
addedge(u, v), addedge(v, u);
}
Tree::init();
Blocks::init();

gi(Q);
for (int u, v, i = 1; i <= Q; i++) {
gi(u), gi(v);
u ^= lastans * type, v ^= lastans * type;
Blocks::query(u, v);
}
}

int main() {
freopen("mode.in", "r", stdin);
freopen("mode.out", "w", stdout);

__main__();

return 0;
}

 

评论

此博客中的热门博文