期望:100 + 0 + 0 + 50
实际:0 + 0 + 0 + 35
能冲: 100 + 100 + 100 + 0

输光了

主要输在 T2 想复杂了以及 T1FST 了

T2 胡了个线段树优化建图但点数爆炸就没写,实际上简单地上前缀优化建图即可。

T1FST 的奇奇怪怪的,还是要自己好好想想。

T4 看错题了,但还有 35 (?) ,但它自动姬一点的做法是真的玄妙,但好像作为原题出现过两次(我都没考)


# Solutions

# A

你在 ss 要去 tt ,有个杀手要干你,初始在 kk ,求你和他速度最小比使得你不会被干。

n5e5n\le 5e5

值得注意的是,你只知道杀手初始在哪里,但不能动态知道它每一步在哪里,所以你不是博弈类似的它走一步你走一步,也不能直接硬上最短路。

那我们把杀手到每个点的最短路求出来,然后你二分答案 xx ,再跑 dijdij ,当你到某个点时 dis2v>x×dis1vdis2_v > x\times dis1_v 那你走就会被鲨,于是不能走,这样就能 checkcheck

# B

nn 个怪,mm 种魔法 (a,b,c)(a,b,c) 表示把一个 aa 血量的怪变成 bb 血量花费 cc 法力,你也可以直接打花 11 法力扣 11 血量,求把每个怪打成 11 血所花费的最少法力

n1e6n\le 1e6

线段树优化建图?

直接排序离散化建图!

我是什么石锤了

# C

nn 个路口,两两距离为 did_i ,每 G+RG+R 时间中 GG 时间绿灯,RR 时间红灯,你只有在绿灯才能通过路口,qq 次询问从时刻 tt 出发啥时候能到 nn 号路口。

n2×105n\le 2\times 10^5

考虑你在时刻 kRk\ge R 时间到了一个路口,你必然会等到下一个绿灯区间才会往后走。

这启发我们预处理每个路口从绿灯区间出发到 nn 号路口的答案。

你考虑,从后往前,类似 dpdp 的,ii 号路口的答案一定会由后面第一个红灯的 jj 号路口答案转移过来。

我们可以列出不等式 :$$G\le sum_j-sum_i < G+R$$.
在你做 ii 时, sumisum_i 是个定值,于是你可以直接在值域线段树上查 jj

查询时,只需类似的判断后面第一个红灯在哪里,就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* ==============================
* Author : Odalys
*
* Blog : Odalys.xyz
*
* Mail : minyuenu@gmail.com
* =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 2e5 + 10;
#define LL long long
struct SGT {
struct Node { int val, l, r; };
int tot, rt;
vector < Node > tr;
SGT (int siz) : tot(0), rt(0), tr(siz, Node{-1, 0, 0}) {}
#define ls tr[x].l
#define rs tr[x].r

inline void put (int &x, int v) {
if (!x) x = ++tot;
tr[x].val = v;
}
void pushdown (int x) {
if (~tr[x].val) put(ls, tr[x].val), put(rs, tr[x].val), tr[x].val = -1;
}
void update (int &x, int l, int r, int ll, int rr, int v) {
if (ll <= l && r <= rr) return put(x, v), void();
pushdown(x);
int mid = (l + r) / 2;
if (ll < mid) update (ls, l, mid, ll, rr, v);
if (rr > mid) update (rs, mid, r, ll, rr, v);
}
int query (int x, int l, int r, int p) {
if (~tr[x].val) return tr[x].val;
pushdown(x);
int mid = (l + r) / 2;
if (p < mid) return query (ls, l, mid, p);
return query (rs, mid, r, p);
}
} ;
int n, G, R;
LL a[N], pre[N];
LL Ans[N];
int main() {
read(n); read(G); read(R);
For (i, 0, n) read(a[i]), pre[i] = pre[i - 1] + a[i];
SGT tr (n * 100); R += G;
tr.update(tr.rt, 0, R, 0, R, n);
foR (i, n - 1, 0) {
int j = tr.query (tr.rt, 0, R, (R - pre[i] % R) % R);
Ans[i] = Ans[j] + pre[j] - pre[i];
if (j < n) Ans[i] += (R - (pre[j] - pre[i]) % R);
int l = (R + G - pre[i] % R) % R;
int r = (R - pre[i] % R) % R;
if (l < r)
tr.update (tr.rt, 0, R, l, r, i);
else {
tr.update (tr.rt, 0, R, l, R, i);
if (r)
tr.update (tr.rt, 0, R, 0, r, i);
}
}
int q; read(q);
LL tmp = 0;
while (q--) {
int t; read(t); t = t xor (tmp % 2147483647);
int i = tr.query (tr.rt, 0, R, t % R);
tmp = Ans[i] + pre[i] + t;
if (i < n) tmp += R - (pre[i] + t) % R;
printf ("%lld\n", tmp);
}
return 0;
}

# d

this

考虑设计一个 DFA ,每个状态为一个等价类,即满足 f(x)=f(y)f(x) = f(y)f(x+S)=f(y+S)f(x+S) = f(y+S) 其中 SS 为任意 01 串

可以证明,这样的等价类不超过 200 个 草!

然后考虑判断两个串是否在同一等价类中,可以证明,只要在这两个串后面随意加长度不超过 77 的函数值还 TM 相等,就在同一等价类中。 草!

然后暴力建出自动姬在上面 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e5 + 10;
const int Mod = 1e9 + 7;
struct Node {
int siz, a[20];
} dot[222];

int f[10];

int get ( vi a ) {
while (a.size() > 1) {
int xx = 0;
For (i, 0, 2) xx = xx * 2 + a.back(), a.pop_back();
xx = f[xx]; a.pb(xx);
}
return a[0];
}

int to[N][2], tot;
bool tag[30][2];
pii sol ( Node x ) {
memset (tag, 0, sizeof tag);
tag[1][x.a[1]] = 1;
for (int i = 3; i <= x.siz; i += 2)
for (int j = 1; j < i; j += 2)
For (k, 0, 1)
if (tag[j][k]) {
vi tmp; tmp.pb(k);
For (o, j + 1, i) tmp.pb(x.a[o]);
tag[i][get(tmp)] = 1;
}
return mp (tag[x.siz][0], tag[x.siz][1]);
}

bool ck ( Node x, Node y ) {
if ( (x.siz & 1) != (y.siz & 1) ) return false;
For (len, 0, 7)
if ( (x.siz + len) & 1 ) {
For (s, 0, (1 << len) - 1) {
Node c = x, d = y;
For (i, 1, len) {
c.a[++c.siz] = (s >> i - 1) & 1;
d.a[++d.siz] = (s >> i - 1) & 1;
}
if (sol(c) != sol(d)) return false;
}
}
return true;
}

void build () {
static queue <int> q; while (!q.empty()) q.pop();
q.push(1);
tot = 1;
while (!q.empty()) {
int id = q.front(); q.pop();
Node u = dot[id];
For (i, 0, 1) {
Node v = u; v.a[++v.siz] = i;
bool flag = false;
For (j, 1, tot) if (ck(dot[j], v)) { to[id][i] = j; flag = 1; break; }
if (!flag) {
dot[to[id][i] = ++tot] = v;
q.push(tot);
}
}
}
}
int dp[N][333];
char ch[N];
int main() {
int cases; read(cases);
while (cases--) {
memset (to, 0, sizeof to);
For (i, 0, 7) scanf ("%1d", &f[i]);
build ();
memset (dp, 0, sizeof dp);
scanf ("%s", ch + 1);
int n = strlen(ch + 1);
dp[0][1] = 1;
For (i, 1, n) For (j, 1, tot) {
if (dp[i - 1][j]) {
if (ch[i] == '?')
For (o, 0, 1) (dp[i][to[j][o]] += dp[i - 1][j]) %= Mod;
else
(dp[i][to[j][ch[i] - '0']] += dp[i - 1][j]) %= Mod;
}
}
int Ans = 0;
For (i, 1, tot) if (sol(dot[i]).se == 1) (Ans += dp[n][i]) %= Mod;
printf ("%d\n", Ans);
}
}

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝