题意 巴拉巴拉巴拉模拟题
题解 优先队列模拟即可，没啥意思的题目
代码
#include<bits/stdc++.h> #include<iostream> using namespace std; struct node{ int index; char name[201]; int value; bool enter; bool operator < (const node &b)const { if(value != b.value) return value < b.value; else return index > b.index; } }; struct door{ int rank; int num; }; node a[150011]; door b[150001]; bool cmp(door x,door y) { return x.rank<y.rank; } int main(){ int t; scanf("%d",&t); int k,m,q; while(t--) { priority_queue<node> pq; memset(a, 0, sizeof a); memset(b , 0, sizeof b); int ans[150011]; int start=0; scanf("%d%d%d",&k,&m,&q);//friend,door,querry getchar(); for(int i=0;i<k;i++) { scanf("%s",a[i].name); scanf("%d",&a[i].value); getchar(); a[i].index=i; } int temp=0; for(int j=0;j<m;j++){ scanf("%d",&b[j].rank); scanf("%d",&b[j].num); } sort(b,b+m,cmp); for(int j=0;j<m;j++) { while(temp<b[j].rank) { pq.push(a[temp]); a[temp].enter=true; temp++; } int number = b[j].num; while(number--) { if(!pq.empty()) { node x; x=pq.top(); ans[++start] = x.index; pq.pop(); } else break; } } for(int i=0;i<k;i++) { if(a[i].enter == false) pq.push(a[i]); } while(!pq.empty()) { node x; x=pq.top(); ans[++start]=x.index; pq.pop(); } for(int i=0;i<q;i++) { int qu=0; scanf("%d",&qu); if(i<q-1)printf("%s ",a[ans[qu]].name); else printf("%s",a[ans[qu]].name); } printf("\n"); } return 0; }题意 给定一张n个点m条边的无向图，每个点都一个权值。现在不断删除孤立点和度数小于2的点，计算处于拥有奇数个点的连通块内所有点的权值和。
题解 拓扑排序思想+并查集求连通块。可以不断把度数为1的点放入队列里面，按照拓扑排序的方法进行更新，然后记录一下被删除的点。通过并查集求连通块，同时维护一下连通块的点数目和权值和。累加即可。
代码
#include <bits/stdc++.h> using namespace std; int const M = 2e5 + 10, N = 1e4 + 10; typedef long long LL; typedef pair<int, int> PII; unordered_set<int> s; int n, T, m; int e[M], ne[M], h[N], v[N], idx, d[N]; int sz[N]; // sz维护数目 LL cnt[N]; // cnt权值和 int fa[N]; vector<PII> edge; int get(int x) { if (x == fa[x]) return x; int root = get(fa[x]); return fa[x] = root; } void add(int a, int b ) { e[idx] = b, ne[idx] = h[a] , h[a] = idx++; } int main() { // freopen("in.txt", "r", stdin); cin >> T; while (T--) { scanf("%d%d", &n, &m); s.clear(); memset(h, -1, sizeof h); memset(d, 0, sizeof d); edge.clear(); idx = 0; for (int i = 1; i <= n; ++i) { scanf("%d", &v[i]); fa[i] = i; sz[i] = 1; cnt[i] = v[i]; } for (int i = 1; i <=m; ++i) { int a, b; scanf("%d%d", &a, &b); add(b, a), add(a, b); edge.push_back({a, b}); d[a] ++ ,d[b]++; } queue<int> q; for (int i = 1; i <= n; ++i) { if (!d[i]) s.insert(i); if (d[i] == 1) { q.push(i); s.insert(i); } } while(q.size()) { int t = q.front(); // cout << t << endl; q.pop(); for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; d[j]--; if (d[j] == 1) { q.push(j); s.insert(j); } } } for (int i = 0; i < edge.size(); ++i) { int a = edge[i].first, b = edge[i].second; int pa = get(a), pb = get(b); if (s.count(a) || s.count(b) || pa == pb) continue; // printf("%d-%d a:%d pa:%d b:%d pb:%d\n", a, b, a, pa, b, pb); fa[pa] = pb; sz[pb] += sz[pa]; cnt[pb] += cnt[pa]; } LL res = 0; for (int i = 1; i <= n; ++i) { if (s.count(i)) continue; if (fa[i] == i && (sz[i] & 1)) res += cnt[i]; } printf("%lld\n", res); } return 0; }题意 给定一张n个点m条边的带权无向图，每次询问给定一个x，计算所有点对(a,b)的数目，使得a->b的路径上最长边小于等于x。
题解 每次询问都相当于删边，删去图中大于x的边，然后找到连通块，计算每个连通块内的点数n，答案累加 c [ n ] [ 2 ] c[n][2] c[n][2]。但是询问有5000个，如果每次都dfs，那么会超时。删边的过程可以等价为建边的过程，因此我们只需要在建图的过程中不断记录当前的连通块数目及其内部的点数，那么就可以等价找出删边的过程。
代码
// 以下代码segment error,有空再调吧，最近忙 #include <bits/stdc++.h> using namespace std; int const N = 40010, M = 400010; // 20000, m≤100000 typedef long long LL; typedef pair<int, int> PII; int n, T, m, Q; int e[M], ne[M], w[M], h[N], idx; int fa[N], cnt[N]; LL sum[N]; struct Edge{ int a, b, c; bool operator < (const Edge &w) const { return c < w.c; } }edge[M]; int get(int x) { if (fa[x] == x) return x; int root = get(fa[x]); return fa[x] = root; } int add(int a, int b , int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } LL C(int n) { return (LL)n * (n - 1) / 2; } int main() { // freopen("in.txt", "r", stdin); cin >> T; while (T--) { scanf("%d%d%d", &n, &m, &Q); memset(h, -1, sizeof h); idx= 0; for (int i = 1; i <= n; ++i) { fa[i] = i; cnt[i] = 1; } for (int i = 1; i <= m; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edge[i] = {a, b, c}; } sort(edge + 1, edge + 1 + m); for (int i = 1; i <= m; ++i) { sum[i] = sum[i - 1]; int a = edge[i].a, b = edge[i].b, c = edge[i].c; int pa = get(a), pb = get(b); if (pa != pb) { sum[i] = sum[i] - C(cnt[pa]) - C(cnt[pb]); sum[i] += C(cnt[pa] + cnt[pb]); fa[pa] = pb; cnt[pb] += cnt[pa]; } } while(Q--) { int x; scanf("%d", &x); Edge tmp; tmp.a = 0, tmp.b = 0, tmp.c = x; if (x > edge[m].c) { printf("%lld\n", 2 * sum[m]); continue; } int i = lower_bound(edge + 1, edge + 1 + m, tmp) - edge; printf("%lld\n", 2 * sum[i - 1] ); } } return 0; }题意 给定一个字符串，求出顺时针的最大表示法和逆时针的最大表示法。如果顺时针的最大表示法更大，那么打印这个结果；如果顺时针和逆时针一样大，那么再比较哪个下标比较小，打印下标小的那个；如果下标一样，那么打印顺时针的
题解 原字符串做一遍最大表示法，然后原字符串逆置一遍后再做一次最大表示法。由于逆置后的最大表示法的求得的下标是逆置后的最小下标，因此需要kmp匹配求得逆置后的最大下标，这样对应原串的最小下标。
代码
// 以下代码runtime error,有空再调吧，最近忙 #include <bits/stdc++.h> using namespace std; int const N = 2e4 + 10; typedef long long LL; int n, T; char s1[N], s2[N], s3[N * 2], s4[N]; int ne[N]; char res1[N], res2[N]; int Get_max(char s[]) { int i = 0, j = 1, k = 0, t; int len = n; while(i < len && j < len && k < len) { t = s[(i + k) % len] - s[(j + k) % len]; if(!t) k++; else { if (t > 0) j += k + 1;//与最小模板比，只有这里和下方变了 else i += k + 1;// if(i == j) j++; k = 0; } } return min(i, j); } void get_nex(char p[]) { for (int i = 2, j = 0; i <= n; ++i) { while (j && p[j + 1] != p[i]) j = ne[j]; // 对模式串进行匹配，如果没有匹配成功，j变成ne[j]的位置 if (p[j + 1] == p[i]) j++; // 匹配成功，j到后一位 ne[i] = j; // 记录匹配成功的i位和j位的对应关系 } } int kmp(char p[], char s[]) { int maxv = -1; int m = n * 2; for (int i = 1, j = 0; i <= m; ++i) { while (j && p[j + 1] != s[i]) j = ne[j]; // 没匹配成功， j变成ne[j]的位置 if (p[j + 1] == s[i]) j++; // 匹配成功，j往后一位 if (j == n) {// 如果完全匹配完毕 // cout << i - n << " "; if (i - n < n) maxv = max(maxv, i - n); j = ne[j]; // 寻找p在s中的下一次出现的位置，利用ne数组优化时间复杂度 } } return maxv; } int main() { // freopen("in.txt", "r", stdin); cin >> T; while(T--) { memset(ne, 0, sizeof ne); scanf("%d", &n); scanf("%s", s1); strcpy(s2, s1); reverse(s2, s2 + n); // s1: abab s2: baba s3: 0babababa s4:0baba int idx1 = Get_max(s1); memcpy(s3 + 1, s2, sizeof s2); memcpy(s4 + 1, s2, sizeof s2); for (int i = 1; i <= n; ++i) s3[i + n] = s3[i]; get_nex(s4); int idx2 = kmp(s4, s3); // cout << idx2 << endl; idx2 = n - idx2; idx1 ++ ; int cnt = 0; for (int i = idx1 - 1; i < n; ++i) res1[cnt++] = s1[i]; for (int i = 0; i < idx1 - 1; ++i) res1[cnt++] = s1[i]; cnt = 0; for (int i = idx2 - 1; i >= 0; --i) res2[cnt++] = s1[i]; for (int i = n - 1; i >= idx2; --i) res2[cnt++] = s1[i]; int t = strcmp(res1, res2); if (t > 0) { cout << idx1 << " " << 0 << endl; } else if (t < 0) { cout << idx2 << " " << 1 << endl; } else { if (idx1 <= idx2) cout << idx1 << " " << 0 << endl; else cout << idx2 << " " << 1 << endl;; } } return 0; }**题意 **签到，求区间最大值
题解 签到，范围小，直接暴力
代码
#include <bits/stdc++.h> using namespace std; int const N = 1e6 + 10; typedef long long LL; int n, T, m, a[N], Q; int main() { // freopen("in.txt", "r", stdin); cin >> T; while(T--) { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; cin >> Q; while(Q--) { int l, r; cin >> l >> r; int maxv = -1; for (int i = l; i <= r; ++i) maxv = max(maxv, a[i]); cout << maxv << endl; } } return 0; }题意 给一颗二叉搜索树，在树上找到x
题解 直接利用二叉搜索树的性质，左子树小，右子树大，然后暴力dfs即可。一开始去找左右子树的边界在做dfs，然后疯狂爆栈，最后发现只需要找到第一个不满足条件的位置即可
代码
#include <bits/stdc++.h> using namespace std; int const N = 2e5 + 10; typedef long long LL; int n, T, m, a[N], Q, x; void dfs(int cur) { if (a[cur] == x) { return; } if (x > a[cur]) { printf("W"); for (int i = cur + 1; i <= n; ++i) { if (a[i] > a[cur]) { cur = i; break; } } } if (x < a[cur]) { printf("E"); for (int i = cur + 1; i <= n; ++i) { if (a[i] < a[cur]){ cur = i; break; } } } dfs(cur); } int main() { // freopen("in.txt", "r", stdin); cin >> T; while(T--) { scanf("%d", &n); for (int i = 1 ; i <= n; ++i) scanf("%d", a+ i); scanf("%d", &Q); while (Q--) { scanf("%d", &x); dfs(1); printf("\n"); } } return 0; }题意 首先有n种点心，每种点心的t,u,v代表该点心每个所提供的能量，体积，数量。然后有m中车，每种车的x,y,z代表这种车的容量，费用，数量。又有一个p，问你所选的点心达到p的能量值的时候所需要的最少费用。（点心可以切割，即可以分开到每辆车里面，但是只要你选了一个，就整个点心都要放进车里）
题解 分两次dp，第一次先求出要达到p能量的时候需要的最小体积minspace，第二次dp求就是要达到minspace的的最小费用f2[minspcae]，是个两次多重背包。这里的多重背包只需要二进制优化即可。
代码
// 以下代码segment error,有空再调吧，最近忙 #include <bits/stdc++.h> using namespace std; int const N = 300010; typedef long long LL; int f1[N], f2[N], n, m, p, T; struct Good { // 存储新的生成的物品 int v, w; }; vector <Good> goods; int main() { freopen("in.txt", "r", stdin); cin >> T; while(T--) { goods.clear(); scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; ++i) { int v, w, s; scanf("%d%d%d", &v, &w, &s); for (int k = 1; k <= s; k *= 2) { // 即1份为一个新的物品，2份为一个新的物品，4份为一个新的物品，8份为一个新的物品 s -= k; goods.push_back({v * k, w * k}); } if (s > 0) goods.push_back({v * s, w * s}); // 剩下的一份为一个新的物品 } memset(f1, 0x3f, sizeof f1); f1[0] = 0; for (auto good: goods) // 从小到大枚举物品 for (int j = p * 4; j >= 0; --j) // 从大到小枚举体积 f1[j] = min(f1[j], f1[max(0, j - good.v)] + good.w); // 状态转移 int minspace = f1[p]; goods.clear(); for (int i = 1; i <= m; ++i) { int v, w, s; scanf("%d%d%d", &v, &w, &s); for (int k = 1; k <= s; k *= 2) { // 即1份为一个新的物品，2份为一个新的物品，4份为一个新的物品，8份为一个新的物品 s -= k; goods.push_back({v * k, w * k}); } if (s > 0) goods.push_back({v * s, w * s}); // 剩下的一份为一个新的物品 } memset(f2, 0x3f, sizeof f2); f2[0] = 0; for (auto good: goods) // 从小到大枚举物品 for (int j = minspace; j >= 0; --j) // 从大到小枚举体积 f2[j] = min(f2[j], f2[max(0, j - good.v)] + good.w); if (f2[minspace] > 50000) printf("TAT\n"); else printf("%d\n", f2[minspace]); } return 0; }题意 求$c[n][m] $% ( p 1 ∗ p 2 ∗ . . . ∗ p k ) (p1*p2*...*pk) (p1∗p2∗...∗pk)
题解 lucus+CRT裸题，可以拆分为$c[n][m] % p1, c[n][m] % p2, c[n][m] $% pk,然后crt求解即可。
代码
自己写的代码没有调通…就粘了网上大佬的代码…
#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; #define ll long long #define CL(a) memset(a,0,sizeof(a)) const int maxn = 1e5 + 5; ll fac[maxn]={0,1},inv[maxn]={0,1}; ll pow_mod(ll a, ll n, ll mod)//快速幂取模 { ll ret = 1; while (n) { if (n&1) ret = ret*a%mod; a = a*a%mod; n >>= 1; } return ret; } ll Lucas(ll n, ll m, ll mod)//Lucas定理 { ll ret=1; ll mm=m,nn=n; while (mm && nn) { ll mod_m=mm%mod, mod_n=nn%mod; if (mod_n>=mod_m) ret = ret*fac[mod_n]%mod*inv[mod_m]%mod*inv[mod_n-mod_m]%mod; else { ret = 0; break; } mm/=mod; nn/=mod; } return ret; } void exgcd(ll a, ll b, ll &d, ll &x, ll &y)//扩展欧几里德求逆元 { if (b == 0) d = a, x = 1, y = 0; else { exgcd(b, a%b, d, y, x); y -= x * (a / b); } } ll china(ll n, ll m[], ll a[])//中国剩余定理求解 { ll aa = a[0]; ll mm = m[0]; for (int i=0; i<n; i++) { ll sub = (a[i] - aa); ll d, x, y; exgcd(mm, m[i], d, x, y); if (sub % d) return -1; ll new_m = m[i]/d; new_m = (sub/d*x%new_m+new_m)%new_m; aa = mm*new_m+aa; mm = mm*m[i]/d; } aa = (aa+mm)%mm; return aa; } int main () { int cas; ll n, m, k, a[15], p[15]; scanf("%d", &cas); while (cas--) { scanf("%lld%lld%lld",&n,&m,&k); for (int i=0; i<k; i++) { scanf("%lld",&p[i]); //init(p[i]); for (int j=2; j<p[i]; j++) fac[j] = fac[j-1]*j%p[i]; inv[p[i]-1] = pow_mod(fac[p[i]-1], p[i]-2, p[i]); for (int j=p[i]-1; j>0; j--) inv[j-1] = inv[j]*j%p[i]; a[i] = Lucas(n, m, p[i]); } printf("%lld\n",china(k, p, a)); } return 0; }