最近有点小摆，总结一下吧。
邻接表存图中节点
单源最短路径（标准版） - 洛谷 P4779 - Virtual Judge (vjudge.net)
迪杰斯特拉，最短路板子
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e6 + 10;
int e[N], w[N], ne[N], idx, st[N],ds[N],h[N];
int n, m,s;
void add(int a, int b, int c)
{
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
void djs(int xd)
{
memset(ds, 0x3f, sizeof ds); ds[xd] = 0;
memset(st, 0, sizeof st);
//小顶堆
priority_queue<pii, vector<pii>, greater<pii>>pq;//
pq.push({ 0,xd });
while (pq.size())
{
auto [y, x] = pq.top(); pq.pop();
if (st[x]) continue;
st[x] = 1;
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (ds[j] > ds[x] + w[i])
{
ds[j] = ds[x] + w[i];
pq.push({ ds[j],j });
}
}
}
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m>>s;
while (m--)
{
int x, y, z; cin >> x >> y >> z;
add(x, y, z);
}
djs(s);
for (int i = 1; i <= n; i++) cout << ds[i] << " \n"[i == n];
return 0;
}I-马拉松_河南萌新联赛2024第（四）场：河南理工大学 (nowcoder.com)
这个用于找到x,y的为父亲的子树节点，
走一个dfs
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, x, y;
int ne[N * 2], h[N * 2], e[N * 2], idx, st[N];
map<pair<int, int>, int>mp;
void add(int a, int b)
{
ne[idx] = h[a]; e[idx] = b; h[a] = idx++;
}
void dfs(int op, int res, int& ans)//
{
if (res == 2) ans++;
for (int i = h[op]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
st[j] = 1;
if (j == x || j == y) dfs(j, res + 1, ans);
else dfs(j, res, ans);
st[j] = 0;
}
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> x >> y;
int nn = n - 1;
while (nn--)
{
int a, b; cin >> a >> b;
add(a, b); add(b, a);//双向的
}
memset(st, 0, sizeof st);
st[x] = 1;
int anx = 0, any = 0;
dfs(x, 1, anx);
memset(st, 0, sizeof st);
st[y] = 1;
dfs(y, 1, any);
//当到达点为
// cout << anx << " " << any << '\n';
cout << anx * any;
return 0;
}
B-小雷的神奇电脑_河南萌新联赛2024第（四）场：河南理工大学 (nowcoder.com)
这个题，首先相同为1，铜为0
比如
1011 0111 --> 0011;
这个可以通过
1011^0111^1111==0011
我们快排一下找到数组中两个数的使之异或最小即可，当有两个数相同的话就，异或是0，就是数组的最小的，可以去重一下，代码如下
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int mina = 1e18;
int ksm(int a, int n)
{
int ans = 1;
while (n)
{
if (n & 1) ans = ans * a;
a = a * a;
n = n >> 1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector<int>a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int ks = ksm(2, m) - 1;
if (a.size() != n)
{
cout << ks << "\n";
return 0;
}
for (int i = 1; i < n; i++)
{
mina = min(mina, a[i] ^ a[i - 1]);
}
mina = mina ^ ks;
cout << mina << '\n';
return 0;
}
前几天的cf,div4的f题，一个组合数
直接统计01数组中0，1的个数，c0,c1;
然后从(k+1)/2【k/2的向上取整】开始遍历到k
令 op=(k+1)/2,od=k-(k+1)/2; 之后C(c1,op)*C(c0,od)即可
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int M = 1e9 + 7;
const int N = 2e6 + 10;
int a[N];
int n, k;
int fa[N], inv[N];//阶乘//逆元
int ksm(int a, int n)
{
int ans = 1;
while (n)
{
if (n & 1) ans = ans * a % M;
a = a * a % M; n = n >> 1;
}
return ans;
}
void get_zhuhe()
{
fa[0] = inv[0] = 1;
for (int i = 1; i < N; i++)
{
fa[i] = fa[i - 1] * i % M;
inv[i] = inv[i - 1] * ksm(i, M - 2) % M;
}
}
int C(int n, int m)
{
return fa[n] * inv[m] % M * inv[n - m] % M;
}
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int c0 = count(a + 1, a + 1 + n, 0);
int c1 = count(a + 1, a + 1 + n, 1);
if (c1 < (k + 1) / 2)
{
cout << 0 << "\n";
return;
}
int op = (k + 1) / 2;
int ans = 0;
for (int i = op; i <= c1 && i <= k; i++)
{
int j = k - i;
if(c0>=j) ans = (ans + C(c1, i) * C(c0, j)%M) % M;
}
cout << ans%M << '\n';
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
get_zhuhe();
int T; cin >> T; while (T--) solve();
return 0;
}P10837 『FLA - I』云音泛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前几天洛谷上的一道黄题，（被前缀和卡死）
先给数据分号l,r进行差分，然后对每一个位置进行特判，当要移走的是这个位置这个位置的贡献变化，之后对贡献变化前缀和，然后遍历每一个木板，把这个木板移走后的总贡献最大化输出
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int N = 1e7 + 10;
int a[N], b[N];
int c[N], d[N],ansl[N],ansr[N];
int ck,dk,kk,maxa,sum;
map<int, int>mp;
map<pair<int, int>, int>mmp;
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i] + m;
mp[a[i]]++;
mp[b[i]]--;
}
for(auto i:mp)
{
c[ck++]=i.first;
d[dk++]=i.second;
}
for (int i = 0; i < ck-1; i++)
{//ck-1
if (d[i] == 1) sum += c[i + 1] - c[i];
d[i + 1] += d[i];
}
for (int j = 0; j+1 <ck; j++)
{
if (d[j] == 1) ansl[j] -= (c[j + 1] - c[j]);
else if (d[j] == 2) ansr[j] += (c[j + 1] - c[j]);
}
for(int i=1;i<ck;i++)
{
ansl[i]+=ansl[i-1];
ansr[i]+=ansr[i-1];
}
// for(int i=0;i<ck;i++) cout<<ansl[i]<<" \n"[i==ck-1] ;
// for(int i=0;i<ck;i++) cout<<ansr[i]<<" \n"[i==ck-1] ;
//
for (int i = 1; i <= n; i++)
{
int l = a[i], r = b[i];
if (mmp[{l, r}]) continue;
mmp[{l, r}]++;
l = lower_bound(c, c + ck, l) - c;
r = lower_bound(c, c + ck, r) - c;
int ans = 0;
ans+=ansl[r-1]-ansl[l-1]+ansr[r-1]-ansr[l-1];
maxa = max(maxa, sum+m+ans);
if (ans == m) break;
}
cout << maxa << '\n';
return 0;
}E-区间_河南萌新联赛2024第（三）场：河南大学 (nowcoder.com)
这是一个维护一串相同的最大长度。
用线段树，维护当前串的左端最大，右端最大，总体最大，总体0，1总和（这里把0看成了负无穷）。
#include<bits/stdc++.h>
#define int long long
#define kl (k<<1)
#define kr (k<<1|1)
using namespace std;
const int N = 1e6 + 10;
const int INF = 1e12;
struct tree { int l, r, sum, ansl, ansr, tsum; };
tree tr[N * 4];
int n, q;
void push_up(int k)
{
//左
tr[k].sum=tr[kl].sum+tr[kr].sum;
tr[k].ansl = max(tr[kl].ansl, tr[kl].sum + tr[kr].ansl);
tr[k].ansr = max(tr[kr].ansr, tr[kr].sum + tr[kl].ansr);
tr[k].tsum = max(max(tr[kl].tsum, tr[kr].tsum), tr[kl].ansr + tr[kr].ansl);
}
void push_up_op(tree& tr, tree kll, tree krr)
{
//左
tr.sum = kll.sum + krr.sum;
tr.ansl = max(kll.ansl, kll.sum + krr.ansl);
tr.ansr = max(krr.ansr, krr.sum + kll.ansr);
tr.tsum = max(max(kll.tsum,krr.tsum), kll.ansr + krr.ansl);
}
void build(int k, int l, int r)
{
tr[k] = { l,r,0,0,0,0 };
if (l == r)
{
tr[k] = { l,r,1,1,1,1 };
return;
}
int mid = (l + r) >> 1;
build(kl, l, mid);
build(kr, mid + 1, r);
push_up(k);
}
void change(int k, int l, int r, int op)
{
if (tr[k].l == l && tr[k].r == r)
{
if (tr[k].sum == 1) tr[k] = { l,r,-INF,-INF,-INF,-INF };
else tr[k] = { l,r,1,1,1,1 };
return;
}
int mid = (tr[k].l + tr[k].r) >> 1;
if (l <= mid) change(kl, l, r, op);
else change(kr, l, r, op);//mid>l
push_up(k);
}
tree query(int k, int l, int r)
{
if (l <= tr[k].l && tr[k].r <= r)
{
return tr[k];
}
int mid = (tr[k].l + tr[k].r) >> 1;
tree tre={0,0,0,0,0,0}, kll = {0,0,0,0,0,0}, krr = {0,0,0,0,0,0};
if (l <= mid) kll = query(kl, l, r);
if (mid < r) krr = query(kr, l, r);
push_up_op(tre, kll, krr);
return tre;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
build(1, 1, n);
while (q--)
{
int x; cin >> x;
if (x == 1)
{
int op; cin >> op;
change(1, op, op, -INF);//查询这个位置
}
else
{
int l, r; cin >> l >> r;
cout << max(0ll,query(1, l, r).tsum) << endl;
}
}
return 0;
}