题解牛客练习赛 88
活着的证据
https://ac.nowcoder.com/acm/contest/11178/A
A 题
简单的贪心，不妨令 和
分别表示
V 和数量和 I 的数量。
的时候就直接先输出所有的
V然后再输出所有的I即可。否则就尝试先用
V填满前面的尽可能多的数字位，然后考虑将I先用来占没有填满的位，如果还有富余的I就尽量往前面的数字位就完事了。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
int T;
int main() {
T = read();
while(T --) {
int V = read(), I = read(), Num = read();
if(V + I <= Num) {
for(int i = 1 ; i <= V + I ; i ++) {
if(i <= V) putchar('5');
else putchar('1');
}
}
else {
int L = I - max(0, Num - V);
for(int i = 1 ; i <= Num ; i ++) {
if(i <= V) {
putchar(5 + min(L, 3) + '0');
L = max(L - 3, 0);
}
else {
putchar(1 + min(L, 2) + '0');
L = max(L - 2, 0);
}
}
}
putchar('\n');
}
return 0;
} B 题
就简单的字符串 hash 就完事了。
设字符串长度是 。
先把 C 串的末尾 个字符去掉，然后我们枚举
M 串的位置 ，然后如果
能够匹配上
C 串末尾的 个字符就判断
以及
能否与
C 串匹配就行了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 50;
const int Mod1 = 998244353, B1 = 31;
const int Mod2 = 1e9 + 7, B2 = 137;
int P1[MAXN], P2[MAXN];
inline int read() {
int x = 0, flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
int T, K;
char M[MAXN], C[MAXN], Suffix[10];
struct Hash {
int x, y;
bool operator == (const Hash a) const {
return (a.x == x) & (a.y == y);
}
} Ha[MAXN], Hb[MAXN];
void Prepare(Hash *H, char *s) {
int len = strlen(s + 1);
for(int i = 1 ; i <= len ; i ++) {
H[i].x = (1ll * H[i - 1].x * B1 % Mod1 + s[i] - 'A' + 1) % Mod1;
H[i].y = (1ll * H[i - 1].y * B2 % Mod2 + s[i] - 'A' + 1) % Mod2;
}
return ;
}
Hash Get(Hash *H, int l, int r) {
Hash ans;
ans.x = (H[r].x - (1ll * H[l - 1].x * P1[r - l + 1]) % Mod1 + Mod1) % Mod1;
ans.y = (H[r].y - (1ll * H[l - 1].y * P2[r - l + 1]) % Mod2 + Mod2) % Mod2;
return ans;
}
int main() {
T = read(); P1[0] = P2[0] = 1;
for(int i = 1 ; i <= 3e5 ; i ++) {
P1[i] = 1ll * P1[i - 1] * B1 % Mod1;
P2[i] = 1ll * P2[i - 1] * B2 % Mod2;
}
while(T --) {
scanf("%s%s%d", M + 1, C + 1, &K);
int lm = strlen(M + 1), lc = strlen(C + 1);
Prepare(Ha, M), Prepare(Hb, C);
for(int j = lc - K + 1 ; j <= lc ; j ++)
Suffix[j - lc + K] = C[j];
int Ans = 0;
for(int i = 1 ; i <= lm - K + 1 ; i ++) {
int flag = 1;
for(int j = 0 ; j < K ; j ++)
if(M[i + j] != Suffix[j + 1]) { flag = 0; break; }
if(flag == 0) continue;
if(i == lm - K + 1) {
if(Get(Ha, 1, lm - K) == Get(Hb, 1, lm - K)) Ans = 1;
}
else if(i == 1) {
if(Get(Ha, K + 1, lm) == Get(Hb, 1, lm - K)) Ans = 1;
}
else {
int Len1 = i - 1;
if(Get(Ha, 1, Len1) == Get(Hb, 1, Len1)) {
Hash a = Get(Ha, i + K, lm), b = Get(Hb, Len1 + 1, lm - K);
if(a == b) Ans = 1;
}
}
}
Ans == 0 ? printf("NO\n") : printf("YES\n");
}
return 0;
} C题
可以发现我们并不关心是哪一位数字上运用了 同或 运算，而是只关心用了还是没用 同或运算。
可以发现，对于 同或上
，就是相当于
异或上
再异或上
。
于是就考虑我们能不能通过异或上 使得得到的答案变大即可。但是需要注意
的时候是不能运用同或运算的。
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int MAXN = 1e6 + 50;
inline int read() {
int x = 0;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) ;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x;
}
int n, A[MAXN], K;
int Ans;
signed main() {
n = read(), K = read();
for(int i = 1 ; i <= n ; i ++)
A[i] = read(), Ans ^= A[i];
int Max = 18446744073709551615ULL;
if(n != 1) {
if(K == 64) Ans = max(Ans, Ans ^ Max);
else Ans = max(Ans, Ans ^ (((1ULL << K) - 1ULL)));
}
cout << Ans;
return 0;
} D题
可以发现一个很显然的性质，我们对于原图建最小生成树后，再次按照题意重建边权是没有意义的，因为得到的最小生成树还是不会变。
于是就是对于原图跑 Kruscal 最小生成树并且建一个 Kruscal 重构树，求 Kruscal 重构树上两个叶子节点的 LCA 即是询问的答案。
我们发现无聊到极致的出题人还顺手无意义地卡了 LCA 并且觉得很有意义。
采用 的
LCA 算法即可。或者是用 tarjan 算法离线后算就可以了。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
typedef unsigned long long ull;
ull a1, a2;
ull myRand(ull &k1, ull &k2){
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 <<23);
k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
return k2 + k4;
}
pair<int,int>myRanq(ull&k1,ull&k2,int N){
int x=myRand(k1,k2)%N+1, y=myRand(k1,k2)%N+1;
if(x > y)return make_pair(y,x);
else return make_pair(x,y);
}
const int MAXN = 2e6 + 50;
int n, m, f[MAXN << 1], tot, rt, start[MAXN], q, V[MAXN << 1];
int dep[MAXN], now = 0;
int LOG[MAXN << 2], Euler[MAXN << 2], Cnt, ST[MAXN << 2][24];
int ID[MAXN << 2];
vector <int> Son[MAXN];
struct Edge {
int from, to, w;
} e[MAXN];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int MIN(int a, int b) { return dep[a] < dep[b] ? a : b; }
void DFS(int x, int from) {
dep[x] = dep[from] + 1, Euler[++ Cnt] = x, ID[x] = Cnt;
for(int i = 0 ; i < Son[x].size(); i ++) {
int to = Son[x][i];
DFS(to, x), Euler[++ Cnt] = x;
}
return ;
}
void Prepare() {
for(int i = 2 ; i <= Cnt ; i ++) LOG[i] = LOG[i >> 1] + 1;
for(int i = 1 ; i <= Cnt ; i ++) ST[i][0] = Euler[i];
for(int i = 1 ; i <= LOG[Cnt] ; i ++) {
for(int j = 1 ; j + (1 << i) - 1 <= Cnt ; j ++)
ST[j][i] = MIN(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
}
return ;
}
int LCA(int l, int r) {
if(l > r) swap(l, r);
int k = LOG[r - l + 1];
return MIN(ST[l][k], ST[r - (1 << k) + 1][k]);
}
signed main() {
n = read(), m = read(), rt = n;
for(int i = 1 ; i <= m ; i ++) {
int u = read(), v = read(), w = read();
e[i] = (Edge) { u, v, w };
}
for(int i = 1 ; i <= n + m ; i ++) f[i] = i;
sort(e + 1, e + 1 + m, cmp);
for(int i = 1 ; i <= m ; i ++) {
int u = find(e[i].from), v = find(e[i].to);
if(u != v) {
rt ++, f[u] = f[v] = f[rt] = rt;
V[rt] = e[i].w;
Son[rt].push_back(u), Son[rt].push_back(v);
}
}
DFS(rt, 0), Prepare(), q = read(), cin >> a1 >> a2;
int Ans = 0;
for(int i = 1 ; i <= q ; i ++) {
pair <int, int> ques = myRanq(a1, a2, n);
Ans ^= V[LCA(ID[ques.first], ID[ques.second])];
}
cout << Ans;
return 0;
} E 题
强行二合一的恶心板子题，很无聊，大概就是线段树分治 + exLucas，出题人差不多得了。
考虑对于边的出现时刻进行线段树分治。可以发现一条边要是在 时刻出现并且在
时刻消失，那么它存在的时间区间就是
。
将这个区间放到线段树上，最后 DFS 遍历整个线段树，这样子我们只会有 次加边操作，于是就没有删边操作了。
假设我们合并两个联通块，那么就用可撤销的并查集维护一下，同时统计 size 和权值总和即可，因为是可撤销，所以得使用按重量启发式合并的并查集。
然后算 就直接用
exLucas 即可，为了方便统计答案开一个 set + map 或者是 mulity set 就可以了。
强行考板子很有意思吗？不理解
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define DEF template<typename Type, typename... Types>
#define V(x) solve(Sum[x], Siz[x])
#define Rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(int i=(a);i>=(b);--i)
inline void read() {}
DEF inline void read(Type& x, Types&... args) {
int flag = 1; x = 0;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
x = x * flag, read(args...);
}
typedef long long LL;
const int MAXN = 2e5 + 50;
int n, m, tot, Mod, q;
int st[MAXN], w[MAXN], Ans[MAXN];
unordered_map <int, int> mp;
struct cmp {
bool operator ()( int a, int b ) { return a > b; }
} ;
set <int, cmp> S;
vector <int> G[MAXN << 2];
struct Edge {
int u, v;
} E[MAXN << 1];
namespace DSU {
LL Sum[MAXN];
int top, tack[MAXN][2], f[MAXN], Siz[MAXN];
int find(int x) { return x == f[x] ? x : find(f[x]); }
int P;
int fac[3][MAXN * 20];
int ans = -1;
int pri[MAXN], pw[MAXN], tt;
inline int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1; y = 0;
return a;
}
int t = exgcd(b, a % b, y, x);
y -= a / b * x;
return t;
}
inline int power(int u, int v, int md) {
int sm;
for (sm = 1; v; v >>= 1, u = (LL)u * u % md)
if (v & 1) sm = (LL)sm * u % md;
return sm;
}
inline int getfac(LL u, int p, int pw, int id) {
if (u <= p) return fac[id][u];
//cout <<
//"ctr mml" << fac[id][pw] << endl;
return (LL)fac[id][u % pw] * power(fac[id][pw], u / pw % (pw / p * (p - 1)), pw) % pw * getfac(u / p, p, pw, id) % pw;
}
inline int getans(LL n, LL m, int p, int pw, int id) {
int up = getfac(n, p, pw, id), dow = (LL)getfac(m, p, pw, id) * getfac(n - m, p, pw, id) % pw;
//cout << "\n" << n << " " << m << " ";
//cout << up << endl;
LL lefp = 0ll, x = n;
while (x) lefp += x / p, x /= p;
x = m;
while (x) lefp -= x / p, x /= p;
x = n - m;
while (x) lefp -= x / p, x /= p;
Rep(i, 1, lefp) {
up = (LL)up * p % pw;
if (!up) return 0;
}
return (LL)up * power(dow, pw / p * (p - 1) - 1, pw) % pw;
}
LL CRT(LL a1, LL a2, LL md1, LL md2) {
LL M = Mod, ret = 0;
LL x, y;
LL tm = M / md1;
exgcd(tm, md1, x, y);
ret = (ret + tm * x * a1) % M;
tm = M / md2;
exgcd(tm, md2, x, y);
ret = (ret + tm * x * a2) % M;
return (ret + M) % M;
}
inline int solve(LL n, LL m) {
ans = getans(n, m, pri[1], pw[1], 1);
//cout << "f:" << n <<" " << m << " " << ans << endl;
int ans2;
if(Mod != 1145141) ans2 = getans(n, m, pri[2], pw[2], 2), ans = CRT(ans, ans2, pw[1], pw[2]);
return ans;
}
void init() {
P = Mod;
int lm = sqrt(P) + 1, x = P;
Rep(i, 2, lm)
if (x % i == 0) {
pri[++ tt] = i, pw[tt] = 1;
while (x % i == 0) pw[tt] *= i, x /= i;
}
if (x > 1) ++ tt, pri[tt] = pw[tt] = x;
for(int j = 1 ; j <= tt; j ++) {
int PW = pw[j];
fac[j][0] = 1;
for(int i = 1 ; i <= PW ; i ++) {
fac[j][i] = fac[j][i - 1];
if(i % pri[j] != 0) fac[j][i] = (LL)fac[j][i] * i % PW;
}
}
}
void Del() {
int x = tack[top][0], y = tack[top][1]; top --;
int Y = V(y);
if( !(-- mp[Y]) ) S.erase(Y);
f[x] = x, Siz[y] -= Siz[x], Sum[y] -= Sum[x];
int Vx = V(x), Vy = V(y);
if( (++ mp[Vx]) == 1) S.insert(Vx);
if( (++ mp[Vy]) == 1) S.insert(Vy);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return ;
if(Siz[x] > Siz[y]) swap(x, y);
int Vx = V(x), Vy = V(y);
if( (-- mp[Vx]) == 0) S.erase(Vx);
if( (-- mp[Vy]) == 0) S.erase(Vy);
f[x] = y, Siz[y] += Siz[x], Sum[y] += Sum[x];
++ top, tack[top][0] = x, tack[top][1] = y;
int Y = V(y);
if( (++ mp[Y]) == 1 ) S.insert(Y);
}
void reset() { top = 0; for(int i = 1 ; i <= n ; i ++) f[i] = i, Siz[i] = 1, Sum[i] = w[i]; }
} ;
void Clean(int x) { while(DSU::top != x) DSU::Del(); }
void puton(int x, int L, int R, int l, int r, int id) {
if(L >= l && R <= r) { G[x].push_back(id); return ; }
int mid = (L + R) >> 1;
if(L == R) return ;
if(l <= mid) puton(x << 1, L, mid, l, r, id);
if(r > mid) puton(x << 1 | 1, mid + 1, R, l, r, id);
return ;
}
void DFS(int x, int L, int R) {
int mid = (L + R) >> 1, top = DSU::top;
for(int i = 0 ; i < G[x].size() ; i ++)
DSU::merge(E[G[x][i]].u, E[G[x][i]].v);
if(L == R) { Ans[L] = *S.begin(), Clean(top); return ; }
DFS(x << 1, L, mid);
DFS(x << 1 | 1, mid + 1, R);
Clean(top); return ;
}
signed main() {
int u, v, op;
read(n, q, Mod), DSU::init();
for(int i = 1 ; i <= n ; i ++) read(w[i]), S.insert(w[i] % Mod), mp[w[i] % Mod] ++;
for(int i = 1 ; i <= q ; i ++) {
read(op);
if(op == 0) read(u, v), E[++ tot] = (Edge) { u, v }, st[tot] = i;
else read(u), (puton(1, 1, q, st[u], i - 1, u), st[u] = 0);
}
for(int i = 1 ; i <= q ; i ++) if(st[i]) puton(1, 1, q, st[i], q, i);
DSU::reset(), DFS(1, 1, q);
for(int i = 1 ; i <= q ; i ++) printf("%d\n", Ans[i]);
return 0;
} F 题
写了 E 之后就呕吐去了，没有做了。
做了前 5 题的体验
给出题人的建议就是 E 题还可以多套一个线性基，就要求输出所有答案的最大异或和，这样就更加恶心了，出题人你说是不是？
或者再来套一个，让你以这个答案序列做某个 dp 什么的。(doge)
闲人碎语 文章被收录于专栏
刊载算法学习笔记以及一些题解
拼多多集团-PDD公司福利 470人发布
