Junior
A - apple
算是简单题，不需要什么脑子，用函数可以直接更简单。
#include <bits/stdc++.h>
using namespace std;
int n;
int F (int x){
if (x == 1)
return 1;
if (x < 1)
return 0;
return F (x - (x + 2) / 3) + 1;
}
int G (int x){
if ((x - 1) % 3 == 0)
return 1;
return G (x - (x + 2) / 3) + 1;
}
int main (){
scanf ("%d", &n);
printf ("%d %d\n", F (n), G (n));
return 0;
}
B - road
简单题，直接贪心即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, d;
int v[N], a[N], Ans, sd, nc;
signed main (){
scanf ("%lld%lld", &n, &d);
for (int i = 2;i <= n;++ i)
scanf ("%lld", &v[i]);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &a[i]);
nc = a[1];
a[n] = - 0x3f3f3f3f3f3fll;
for (int i = 2;i <= n;++ i){
sd += v[i];
if (a[i] < nc){
Ans += max ((sd + d - 1) / d, 0ll) * nc;
sd = sd - max ((sd + d - 1) / d, 0ll) * d;
nc = a[i];
}
}
printf ("%lld", Ans);
return 0;
}
C - uqe
有点麻烦，分类讨论比较多，但好在大样例较强。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, M, a, b, c, delta;
int pu, pd, qu, qd, r;
int gcd (int i, int j){
if (j == 0)
return i;
return gcd (j, i % j);
}
void Write (){
if (pd < 0){
pu = - pu;
pd = - pd;
}
if (pu * pd == 0){
if (qu * qd == 0)
printf ("0");
else {
if (qu != 1)
printf ("%lld", qu);
if (r != 1){
if (qu != 1)
putchar ('*');
printf ("sqrt(%lld)", r);
}
if (qd != 1){
if (qu == 1 && r == 1)
putchar ('1');
printf ("/%lld", qd);
}
}
return ;
}
printf ("%lld", pu);
if (pd != 1)
printf ("/%lld", pd);
if (qu * qd == 0)
return ;
else {
putchar ('+');
if (qu != 1)
printf ("%lld", qu);
if (r != 1){
if (qu != 1)
putchar ('*');
printf ("sqrt(%lld)", r);
}
if (qd != 1){
if (qu == 1 && r == 1)
putchar ('1');
printf ("/%lld", qd);
}
}
return ;
}
signed main (){
scanf ("%lld%lld", &T, &M);
while (T --){
scanf ("%lld%lld%lld", &a, &b, &c);
delta = b * b - 4 * a * c;
r = delta;
pu = - b;
pd = 2 * a;
qu = 1;
qd = 2 * a;
qu = abs (qu);
qd = abs (qd);
if (delta < 0)
puts ("NO");
else {
int u = r;
if (r == 0)
qu = 0;
for (int i = 2;i * i <= u;++ i)
while (r % (i * i) == 0 && r > 0){
r /= i * i;
qu *= i;
}
if (r == 1){
pd = pd * qd;
pu = pu * qd;
pu += qu * (pd / qd);
qu = 0;
}
if (pu != 0){
int gcdp = gcd (abs (pu), abs (pd));
pu /= gcdp;
pd /= gcdp;
}
if (qu != 0){
int gcdq = gcd (abs (qu), abs (qd));
qu /= gcdq;
qd /= gcdq;
}
Write ();
puts ("");
}
}
return 0;
}
D - bus
稍微复杂一些，想了有一会儿。可以分层图，分成 \(k+1\) 层，然后从小到大枚举 \(k\) 倍的时间点，在图中开放新边，然后我们只需要判断第 \(0\) 层的 \(1\) 号点是否能够到达第 \(k+1\) 层的 \(n\) 号点。这样乍一看是 \(O (Vnk)\) 的，但是因为之前时间内染色的点不用撤销，所以考虑枚举每个边的时间除以 \(k\) 的结果，在相邻两个边的时间间隔较大时如果发现无法染出新的点，就可以智能地退出，这样每次进入染色程序都至少会染一个点，而最多染 \(n(k+1)\) 个点，时间复杂度 \(O(nk)\)。
没想到 dij 也可以过。我太菜了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, M = 2e4 + 5, K = 1e2 + 5;
int n, m, k, idx;
bool vis[N * K << 1];
pair < int , pair < int , int > > ed[M];
int firs[N * K << 1], nex[M * K << 1], to[M * K << 1], tot;
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
int id (int i, int j){
return i * n + j;
}
void Coloring (int u){
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (vis[v])
continue;
vis[v] = true;
Coloring (v);
}
}
queue < int > Q;
bool Solve (int q){
for (int i = 1;i <= n;++ i)
if (! vis[id (0, i)] && vis[id (k, i)]){
vis[id (0, i)] = true;
Q.push (id (0, i));
}
int las = idx;
while (idx <= m && ed[idx].first < (q + 1) * k){
for (int i = ed[idx].first % k;i < k;++ i){
Add (id (i, ed[idx].second.first), id (i + 1, ed[idx].second.second));
if (! vis[id (i + 1, ed[idx].second.second)] && vis[id (i, ed[idx].second.first)]){
vis[id (i + 1, ed[idx].second.second)] = true;
Q.push (id (i + 1, ed[idx].second.second));
}
}
++ idx;
}
bool tag = ! Q.empty ();
while (! Q.empty ()){
Coloring (Q.front ());
Q.pop ();
}
for (int p = las;p < idx;++ p){
for (int i = 0;i < ed[p].first % k;++ i){
Add (id (i, ed[p].second.first), id (i + 1, ed[p].second.second));
if (! vis[id (i + 1, ed[p].second.second)] && vis[id (i, ed[p].second.first)]){
vis[id (i + 1, ed[p].second.second)] = true;
Q.push (id (i + 1, ed[p].second.second));
}
}
}
return tag || (! Q.empty ());
}
bool Check (int q){
return idx <= m && ed[idx].first < (q + 1) * k;
}
int main (){
scanf ("%d%d%d", &n, &m, &k);
for (int i = 1;i <= m;++ i)
scanf ("%d%d%d", &ed[i].second.first, &ed[i].second.second, &ed[i].first);
sort (ed + 1, ed + m + 1);
idx = 1;
vis[id (0, 1)] = vis[id (k, 1)] = true;
bool las_Solve = false;
for (int i = 0;i <= 2e6;++ i){
if (Check (i))
las_Solve = Solve (i);
else if (las_Solve)
las_Solve = Solve (i);
if (vis[id (k, n)]){
printf ("%d\n", (i + 1) * k);
return 0;
}
}
puts ("-1");
return 0;
}
Senior
A - lock
纯纯简单题，直接枚举所有情况判断即可。
#include <bits/stdc++.h>
using namespace std;
int n, a[15], b[15], Ans;
bool c[15];
int Upload (){
int x = 0;
for (int i = 0;i < 5;++ i)
x = x * 10 + b[i];
return x;
}
void Download (int x){
for (int i = 4;i >= 0;-- i){
b[i] = x % 10;
x /= 10;
}
}
int main (){
scanf ("%d", &n);
for (int i = 0;i < n;++ i){
for (int j = 0;j < 5;++ j)
scanf ("%d", &b[j]);
a[i] = Upload ();
}
for (int i = 0;i < 100000;++ i){
bool tag = true;
for (int j = 0;j < n;++ j)
if (i == a[j])
tag = false;
if (! tag)
continue;
Download (i);
for (int j = 0, x;j < 5;++ j){
for (int T = 9;T > 0;-- T){
b[j] = (b[j] + 1) % 10;
x = Upload ();
for (int k = 0;k < n;++ k)
if (x == a[k])
c[k] = true;
}
b[j] = (b[j] + 1) % 10;
}
for (int j = 0, x;j < 4;++ j){
for (int T = 9;T > 0;-- T){
b[j] = (b[j] + 1) % 10;
b[j + 1] = (b[j + 1] + 1) % 10;
x = Upload ();
for (int k = 0;k < n;++ k)
if (x == a[k])
c[k] = true;
}
b[j] = (b[j] + 1) % 10;
b[j + 1] = (b[j + 1] + 1) % 10;
}
for (int j = 0;j < n;++ j){
tag = tag && c[j];
c[j] = false;
}
if (tag)
++ Ans;
}
printf ("%d\n", Ans);
return 0;
}
B - game
明明是个简单题，不知道为什么那么多人没想到。
考虑如果出现 \(a(str)aa\) 的情况（\(str\) 指任意字符串），可以无脑删最左边的两个 \(a\)。因为如果删左右端的 \(a\)，就会变成 \((str)a\)，否则变成 \(a(str)\)。如果最终 \(a(str)aa\) 可被删完，则 \(str\) 中还存在 \(a\)，不管是 \(a(str)\) 或 \((str)a\) 都会在某个时刻变成相同的 \(str'\)。
或者说，这结论不是显然？（（
所以扩展一下，定义一个 \(str\) 是不可分割的，当且仅当 \(str\) 可被删完且 \(str\) 左右两端的字符相等且 只能 相互之间匹配，即不存在删除过程使 \((str_1+str_2) \rightarrow str_1\) 或 \((str_1+str_2) \rightarrow str_2\)。这样的话有个非常好的性质，即在原本的串中，要么只能找到一个以 \(i\) 结尾的不可分割子串，否则找不到并且此时 \(i\) 不能作原题统计子串中的右端点。
然后题目中可删除的子串就是多个不可分割子串组成的，这样就很简单了。
然后对于每个 \(i\) 怎么求以 \(i\) 结尾的不可分割子串的左端点？可以直接借由当前位置的前一个位置的对应左端点再往前一位，判断是否与 \(c_i\) 相同，否则重复刚才的操作，直到到 \(0\) ，说明不存在。
然后糊一下时间复杂度：
-
如果求 \(i\) 时 \(i-1\) 不存在合法子串，那么若 \(c_{i-1}=c_i\)，左端点为 \(i-1\)；否则 \(i\) 不存在合法子串。
-
否则 \(i\) 的左端点一定比 \(i-1\) 的左端点小。
发现找不到 hack，但直觉像 \(O(n)-O(n\log_2 n)\) 的。
所以通过了，但我不会证时间复杂度。
#include <bits/stdc++.h>
using namespace std;
int n, nex[2000005], f[2000005], suf[2000005];
long long Ans;
char s[2000005];
int main (){
scanf ("%d\n%s", &n, s + 1);
for (int i = 1;i <= n;++ i){
if (i == 1)
nex[i] = 0;
else {
int u = i - 1;
while (s[u] != s[i] && u > 0)
u = nex[u] - 1;
if (u <= 0)
u = 0;
nex[i] = u;
}
}
suf[n + 1] = n + 1;
for (int i = n;i >= 1;-- i){
if (i == n)
suf[i] = n + 1;
else {
int u = i + 1;
while (s[u] != s[i] && u <= n)
u = suf[u] + 1;
if (u > n)
u = n + 1;
suf[i] = u;
}
}
for (int i = 1;i <= n;++ i)
if (nex[i] > 0)
f[i] = f[nex[i] - 1] + 1;
for (int i = 0;i < n;++ i)
if (suf[i + 1] != n + 1)
Ans += 1ll * (f[i] + 1);
printf ("%lld\n", Ans);
return 0;
}
C - struct
“按照题意模拟即可”，赛时写死我了。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
gp_hash_table < string , int > Type_Name, A_Name;
int n, las_pos;
string ls;
char lc;
int cnt_type = 3;
struct Type {
int k, typ[105], pos[105], len, tb;
string nameT, namem[105];
gp_hash_table < string , int > Mem_Name;
Type (){
k = 0;
len = 0;
tb = 0;
}
} tp[115];
int cnt_A = 0;
struct A {
int typ, pos;
string nameA;
} a[115];
void Write (string &Ans, int u, int ps){
if (ps >= tp[u].len){
Ans = "ERR";
return ;
}
if (u < 4)
return ;
int L = 0, R = tp[u].k, mid;
while (L < R){
mid = (L + R) >> 1;
if (tp[u].pos[mid] <= ps)
L = mid + 1;
else
R = mid;
}
-- L;
Ans += '.';
Ans += tp[u].namem[L];
Write (Ans, tp[u].typ[L], ps - tp[u].pos[L]);
}
signed main (){
tp[0].nameT = "byte";
tp[0].len = tp[0].tb = 1;
tp[1].nameT = "short";
tp[1].len = tp[1].tb = 2;
tp[2].nameT = "int";
tp[2].len = tp[2].tb = 4;
tp[3].nameT = "long";
tp[3].len = tp[3].tb = 8;
Type_Name["byte"] = 0;
Type_Name["short"] = 1;
Type_Name["int"] = 2;
Type_Name["long"] = 3;
cin >> n;
while (n --){
int opt;
cin >> opt;
if (opt == 1){
++ cnt_type;
int u = cnt_type;
cin >> tp[u].nameT >> tp[u].k;
Type_Name[tp[u].nameT] = u;
for (int i = 0;i < tp[u].k;++ i){
cin >> ls >> tp[u].namem[i];
tp[u].typ[i] = Type_Name[ls];
tp[u].Mem_Name[tp[u].namem[i]] = i;
tp[u].tb = max (tp[u].tb, tp[tp[u].typ[i]].tb);
}
tp[u].pos[0] = 0;
tp[u].len = tp[tp[u].typ[0]].len;
for (int i = 1;i < tp[u].k;++ i){
int len = tp[tp[u].typ[i - 1]].len, tb = tp[tp[u].typ[i]].tb;
tp[u].pos[i] = ((tp[u].pos[i - 1] + len - 1) / tb + 1) * tb;
tp[u].len = tp[u].pos[i] + tp[tp[u].typ[i]].len;
}
tp[u].len = tp[u].len + tp[u].tb - 1;
tp[u].len = tp[u].len / tp[u].tb * tp[u].tb;
cout << tp[u].len << " " << tp[u].tb << "\n";
} else
if (opt == 2){
++ cnt_A;
int u = cnt_A;
cin >> ls >> a[u].nameA;
A_Name[a[u].nameA] = u;
a[u].typ = Type_Name[ls];
int Tp = a[u].typ;
a[u].pos = ((las_pos + tp[Tp].tb - 1) / tp[Tp].tb) * tp[Tp].tb;
las_pos = a[u].pos + tp[Tp].len;
cout << a[u].pos << "\n";
} else
if (opt == 3){
ls = "";
lc = getchar ();
lc = '.';
int u = - 1, ps = 0;
while (lc != '\n' && lc != ' '){
lc = getchar ();
if (lc == '.' || lc == '\n' || lc == ' '){
if (u == - 1){
u = a[A_Name[ls]].typ;
ps = a[A_Name[ls]].pos;
}
else {
int v = tp[u].Mem_Name[ls];
ps += tp[u].pos[v];
u = tp[u].typ[v];
}
ls = "";
} else
ls += lc;
}
cout << ps << "\n";
} else
if (opt == 4){
int ps;
string Ans;
cin >> ps;
int L = 1, R = cnt_A + 1, mid;
while (L < R){
mid = (L + R) >> 1;
if (a[mid].pos <= ps)
L = mid + 1;
else
R = mid;
}
-- L;
Ans = a[L].nameA;
if (ps >= a[L].pos + tp[a[L].typ].len || cnt_A == 0)
Ans = "ERR";
else
Write (Ans, a[L].typ, ps - a[L].pos);
cout << Ans << "\n";
}
}
return 0;
}
D - tree
没做，但好像是简单题。就二分时间，再二分求出单个点必须被删掉的最后期限，再逆推取最小就可以把树形结构考虑进去，然后随便判判就行。