8/17 小白月赛28
A
正难则反，失败的概率是1nm ，那么成功的概率就是 ： 1−1nm=nm−1nm
快速幂 + 逆元即可
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
const int P = 1e9 + 7 ;
inline int qmi(int a,int b) {
ll res = 1 ;
while (b) {
if (b & 1) res = res * a % P ;
b >>= 1;
a = 1ll * a * a % P ;
}
return res ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
cin >> T ;
rep(test,1,T + 1){
int n,m ;
cin >> n >> m;
ll fz = qmi(n,m) ;
cout << (fz + P - 1) % P * qmi(fz,P - 2) % P << endl ;
}
return 0;
}
B
可以发现，x,y 谁大谁小无所谓，所以假设 x<y 。如果是只有一维的话，每次只能移 1~x 的话，那就是一个典型的巴士博弈模型了，只要是 n%(x+1) 存在就先手必赢。而这里是二维，所以考虑移差值。当差值 (y−x)%3==0 时，如果 y 和 x 都存在，先手移完之后 差值模3 必存在，而后手再移，差值又可以模三为零。此时无论先手怎么移，后手都可以使差值模三为零，后手移的时候总是有有值。因此，abs(x−y)%3==0 先手必败，否则必胜。
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
cin >> T ;
rep(test,1,T + 1){
int x,y ;
cin >> x >> y ;
if (abs(x - y) % 3 == 0)
cout << "awsl" << endl ;
else
cout << "yyds" << endl ;
}
return 0;
}
C
递归模拟即可
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
string s ;
inline ll cal(int L,int R) {
if (L >= R) return 0 ;
ll res = 0,sm = 0;
rep(i,L,R) {
auto &t = s[i] ;
if (isalpha(t))
sm = sm + t - 'A' + 1 ;
else if (t == '(') {
res += sm ;
sm = 0 ;
ll r = ++ i ;
int cnt = 1 ;
while (cnt) {
if (s[r] == ')') -- cnt ;
else if (s[r] == '(') ++ cnt ;
++ r ;
}
ll tmp = cal(i,r - 1) ;
i = r;
if (i < R && isdigit(s[i])){
ll tms = 0 ;
while (i < R && isdigit(s[i])) tms = tms * 10 + s[i ++] - '0' ;
tmp *= tms ;
-- i ;
}
-- i ;
res += tmp ;
}else if (isdigit(t)) {
ll tms = 0 ;
while (i < R && isdigit(s[i])) tms = tms * 10 + s[i ++] - '0' ;
res += sm * tms ;
sm = 0 ;
-- i ;
}
}
return res + sm ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s ;
cout << cal(0,s.size()) << endl ;
return 0;
}
D
可以发现，当 x<2y 时，一定无解(x≥(a&b)∗2)。此外 当 (x−2y)&y 存在时，无解。否则，可以用剩下的二进制随意分配凑出a^b 的值。
// 2y <= x
// 然后用剩下的位凑一个x - 2y
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
cin >> T ;
rep(test,1,T + 1){
ll x,y;
cin >> x >> y ;
if (y * 2 > x) cout << -1 << endl ;
else {
x -= 2 * y ;
if (x & y) cout << -1 << endl ;
else cout << x << endl ;
}
}
return 0;
}
E
赛时没调出来，赛后调了 3h ，调吐了。
线段树上二分。
先将坐标离散化，然后按离散化后的坐标建树，树内维护坐标对应的最低高度和最高高度，离散化的同时维护坐标对应原数组中的位置 id[]。
对于左侧的 ： 把当前山峰左边第一个比这个山峰严格大的山峰变得和当前山峰一样高 ，先二分找到左侧区间。如果当前区间最大值小于当前查询的 x ，直接返回 0 （不用修改退出）。否则，假设当前区间右端点小于等于查询区间端点，如果区间长度为 1 ，直接返回当前的坐标；如果右区间存在比 x 大的，直接返回右区间的 qmax ; 右区间不存在严格大于 x 的，则只能在左区间找。 如果在分裂区间的时候，出现查询区间横跨当前区间 ，左右查询之后，如果右侧有解取右侧，否则左侧。
对于右侧的 ： 如果右边没有山峰比他严格大，牛牛还是很不满足，他要把右边最小的山峰变成和当前山峰一样大（如果有多个最小的，变最左边的一个）。也是同理可以通过二分求解，只不过需要注意的是，在查找最小值之前，先检查是否存在比 x 大的值 qmax 。然后进行查找最小值的时候，找到对应坐标之后，应该返回该坐标对应原数组中的位置 ，接着在遇到分裂区间时，出现查询区间横跨当前区间 ，左右查询之后，采取 左区间答案小于等于右区间答案 取 左区间答案，否则右区间。
其他编码细节见代码 。
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
using vi = vector<int> ;
const int maxn = 2e5 + 10 ;
ai2 a[maxn],b[maxn];
int n ;
int id[maxn] ;
struct node {
int minn,maxx;
node operator+(const node &other) {
node res ;
res.minn = min(minn,other.minn);
res.maxx = max(maxx,other.maxx);
return res ;
}
} tr[maxn << 2] ;
inline void build(int q,int l,int r){
if (l == r) tr[q] = {a[id[l]][1],a[id[l]][1]} ;
else {
int mid = l + r >> 1;
build(q << 1,l,mid) ;
build(q << 1 | 1,mid + 1,r);
tr[q] = tr[q << 1] + tr[q << 1 | 1] ;
}
}
inline void modify(int q,int l,int r,int k){
if (l == r) tr[q].maxx = tr[q].minn = a[id[l]][1] ;
else {
int mid = l + r >> 1;
if (k <= mid) modify(q << 1,l,mid,k) ;
else modify(q << 1 | 1 ,mid + 1,r,k) ;
tr[q] = tr[q << 1] + tr[q << 1 | 1] ;
}
}
inline int qmin(int q,int l,int r,int L,int R) {
int mid = l + r >> 1;
if (L <= l && r <= R) {
if (l == r) return id[l];
if (tr[q << 1].minn == tr[q].minn) return qmin(q << 1,l,mid,L,mid) ;
return qmin(q << 1 | 1,mid + 1,r,mid + 1,R) ;
}
if (L > mid) return qmin(q << 1 | 1,mid + 1,r,L,R) ;
if (R <= mid) return qmin(q << 1,l,mid,L,R) ;
int lans = qmin(q << 1,l,mid,L,mid),rans = qmin(q << 1 | 1,mid + 1,r,mid + 1,R);
if (a[lans][1] <= a[rans][1]) return lans ;
return rans ;
}
inline int qmax(int q,int l,int r,int L,int R,int x) {
if (tr[q].maxx <= x) return 0 ;
int mid = l + r >> 1;
if (L <= l && r <= R) {
if (l == r) return l;
else if (tr[q << 1 | 1].maxx > x) return qmax(q << 1 | 1,mid + 1,r,L,R,x) ;
return qmax(q << 1,l,mid,L,R,x) ;
}
if (L > mid) return qmax(q << 1 | 1,mid + 1,r,L,R,x) ;
if (R <= mid) return qmax(q << 1,l,mid,L,R,x) ;
int lans = qmax(q << 1,l,mid,L,mid,x),rans = qmax(q << 1 | 1,mid + 1,r,mid + 1,R,x);
return rans ? rans : lans ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n ;
rep(i,1,n + 1) cin >> a[i][0] >> a[i][1],b[i] = a[i];
sort(b + 1,b + n + 1) ;
rep(i,1,n + 1) {
a[i][0] = lower_bound(b + 1,b + n + 1,a[i]) - b;
id[a[i][0]] = i ;
}
build(1,1,n) ;
rep(i,1,n + 1) {
auto [pos,x] = a[i] ;
if (pos != 1) {
int ID = qmax(1,1,n,1,pos - 1,x) ;
ID = id[ID] ;
if (ID) {
a[ID][1] = x ;
modify(1,1,n,a[ID][0]) ;
}
}
if (pos != n){
int t = qmax(1,1,n,pos + 1,n,x) ;
if (t) continue ;
int ID = qmin(1,1,n,pos + 1,n) ;
a[ID][1] = x ;
modify(1,1,n,a[ID][0]) ;
}
}
rep(i,1,n + 1) cout << a[i][1] << ' ';
return 0;
}
F
F 看了一下乍一看是一堆直线找最小值，感觉上李超线段树，印象中好像是用来求直线的。官方题解里用的则是三分求凸壳。
~我太弱了，学不明白，这里就贴官方题解了~
G
写得 hash + 二分。官方题解直接跑 kmp ，匹配过程求 max 匹配长度，我哭死 。
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ull = unsigned long long ;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
const int P = 13331 ;
ull mi[maxn] ;
ull a[maxn],b[maxn] ;
char s[maxn] ;
inline ull get(int l,int r) {
return a[r] - a[l - 1] * mi[r - l + 1] ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
cin >> s + 1;
ull sm = 0 ;
mi[0] = 1;
int maxlen = strlen(s + 1) ;
rep(i,1,maxlen + 1) b[i] = b[i - 1] * P + s[i],mi[i] = mi[i - 1] * P;
ull res = 0 ;
cin >> T ;
while (T --) {
cin >> s + 1 ;
int len = strlen(s + 1) ;
rep(i,1,len + 1) a[i] = a[i - 1] * P + s[i] ;
auto check = [&](int Len) {
rep(i,Len,len + 1)
if (get(i - Len + 1,i) == b[Len]) {
return true ;
}
return false ;
} ;
int l = 0,r = min(len,maxlen),mid,ans = 0 ;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid))
ans = mid,l = mid + 1;
else
r = mid - 1;
}
res += ans ;
}
cout << res << endl ;
return 0;
}
H
最短路
公交站单向建边，步行双向建边，跑一遍最短路即可。之前自己出过几乎一模一样的题，泰酷啦。
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
int cost[maxn] ;
vector<int> vec[maxn] ;
vector<ai2> g[maxn] ;
int d[maxn] ;
bool st[maxn] ;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,s,t,T ;
cin >> n >> m >> s >> t >> T ;
if (s >= t) {
cout << (s - t) * T << endl ;
return 0 ;
}
rep(i,1,m + 1) cin >> cost[i];
rep(i,1,n + 1) {
int t ;
cin >> t;
vec[t].push_back(i) ;
}
rep(i,1,m + 1) {
rep(j,1,vec[i].size())
g[vec[i][j - 1]].push_back({vec[i][j],cost[i]}) ;
}
rep(i,1,n) g[i].push_back({i + 1,T}) ;
rep(i,2,n + 1) g[i].push_back({i - 1,T}) ;
priority_queue<ai2,vector<ai2>,greater<ai2>> q ;
q.push({0,s}) ;
memset(d,0x3f,sizeof d) ;
d[s] = 0 ;
while (q.size()) {
auto [_,u] = q.top() ;
q.pop() ;
if (st[u]) continue ;
st[u] = 1 ;
for (auto &[v,w] : g[u]){
if (!st[v] && d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({d[v],v}) ;
}
}
}
cout << d[t] ;
return 0;
}
I
可以发现是个 数字三角形类型的DP ，看了看取模的值，直接一维暴力 O(nmp) 冲了，加了个 bitset 优化，复杂度刚好。
官方题解是按照最小步数来写，先搞完同一步数内的所有情况然后再去解下一步，之前写图这题的时候，题解也是这种思路，可惜我没想出来。感觉他们这真的简单且有效，太优雅。
bitset
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 110,maxm = 10010,P = 1e4 + 7;
int a[maxn][maxn];
bitset<maxm> f[maxn],t,tmp ;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m ;
cin >> n >> m ;
f[1][0] = 1;
rep(i,0,P) t[i] = 1;
rep(i,1,n + 1) rep(j,1,m + 1) cin >> a[i][j],a[i][j] %= P;
rep(i,1,n + 1) rep(j,1,m + 1) {
f[j] = (f[j] << a[i][j]) | (f[j] >> P - a[i][j]) ;
f[j] = f[j] | ((f[j - 1] << a[i][j]) | (f[j - 1] >> P - a[i][j])) ;
f[j] = f[j] & t ;
}
cout << f[m].count() << endl ;
return 0;
}
J
不同颜色，分类建边 + dfs 即可。
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'
using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;
const int maxn = 2e5 + 10 ;
vector<int> g[maxn] ;
int a[maxn] ;
bool st[maxn] ;
int ans ;
vector<int> res,vec ;
inline void dfs(int u) {
st[u] = 1;
vec.push_back(u) ;
for (auto &v : g[u]) if (!st[v]) dfs(v) ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1 ;
int n ;
cin >> n ;
rep(i,1,n + 1) cin >> a[i] ;
rep(i,1,n) {
int u,v ;
cin >> u >> v ;
if (a[u] ^ a[v]) continue ;
g[u].push_back(v) ;
g[v].push_back(u) ;
}
rep(i,1,n + 1) if (!st[i]) {
vec.clear() ;
dfs(i) ;
if (ans < vec.size()) res.swap(vec),ans = res.size() ;
else if (ans == vec.size()) for (auto &t : vec) res.push_back(t) ;
}
cout << res.size() << endl ;
sort(res.begin(),res.end()) ;
for (auto t : res) cout << t << ' ';
return 0;
}
