省流：上 \(200pts\) 了
\(7.21\) 晴
模考总结：
\(T1\) （题目链接）
题面简述：
求一段序列中有多少个子序列 (此处为连续的) 的和能被 \(k\) 整除。
考试思路：
想到整除就可以想到取模，想到取模就可以想到它的一个性质，即如果 \(N \equiv M \ (mod \ K)\) ，那么 \(|N - M| \equiv 0 \ (mod \ K)\) （狗都知道）
再观察题面，发现此处的子序列是连续的，我们就可以想到此题正解的一个必要技巧——前缀和。但是只有前缀和是不够的（ 最多 \(50pts\) ），我们还需要一个类似于哈希的桶，来存放每一个前缀和对 \(k\) 取模的余数，然后我们就会发现，有些前缀和对 \(k\) 取模的余数竟然是相同的，那么就可以用上面的公式，求出每一个桶中每一个余数对答案的贡献。
AC code:
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <climits>
#include <random>
#include <bitset>
#include <unordered_map>
#define orz %
#define ll long long
#define juruo Optimist_Skm
#define mid ((l + r) / 2.0)
#define pii std::pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define m_p std::make_pair
#define pq std::priority_queue<int>
#define pq_min std::priority_queue<int, std::vector<int>, std::greater<int> >
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define test(x) cout << "Test: " << x << '\n'
#define close fclose(stdin);fclose(stdout);
#define ull unsigned long long
#define debug(); printf("qwq\n");
namespace Fast_Skm {
template <typename T>
inline void read(T &x) {
register T s = 0, w = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') w = -1;
c = getchar();
}
while(isdigit(c))
s = (s << 1) + (s << 3) + (c & 0xcf), c = getchar();
x = s * w;
return ;
}
template <typename T, typename... Arp>
inline void read(T &x, Arp &...arp) {
read(x), read(arp...);
return ;
}
template <typename T>
inline void write(T x) {
if(x < 0) x = -x, putchar('-');
register int p = 0;
static char s[100];
do {
s[++p] = x orz 10 + '0';
x /= 10;
} while (x);
while(p) putchar(s[p--]);
putchar('\n');
}
template <typename T, typename... Arp>
inline void write(T &x, Arp &...arp) {
write(x), write(arp...);
return ;
}
template <typename S, typename T>
inline void smax(S &x, T y) {
x = (x > y) ? x : y;
}
template <typename S, typename T>
inline void smin(S &x, T y) {
x = (x < y) ? x : y;
}
inline void quit() {
exit(0);
return ;
}
inline ll quick_pow(ll a, ll b, ll P) {
register ll ans = 1;
while(b >= 1) {
if(b & 1) {
ans = ans * a % P;
}
a = a * a % P;
b >>= 1;
}
return ans;
}
template <typename T>
inline T exgcd(T a, T b, T &x, T &y) {
if(b == 0) {
x = 1; y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int tmp = y;
y = x - a / b * y;
x = tmp;
return gcd;
}
} using namespace Fast_Skm;
const int N = 5e4 + 7, M = 1e6 + 7;
ll T, n, k, a[N], t[M];
ll sum[N];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
//freopen("1.out", "r", stdin);
//freopen("2.out", "w", stdout);
read(T);
for (int i = 1; i <= T; ++i) {
read(k, n);
memset(t, 0, sizeof(t));
memset(sum, 0, sizeof(sum));
for (int j = 1; j <= n; ++j) {
read(a[j]);
sum[j] = sum[j - 1] + a[j]; //预处理前缀和
}
for (int j = 1; j <= n; ++j) {
t[sum[j] % k]++; //用桶计数
}
ll ans = t[0];
for (int j = 0; j < k; ++j) {
ans += t[j] * 1ll * (t[j] - 1) / 2; //计算对答案的贡献
}
write(ans);
}
return 0;
}
\(T2\) （题目链接）
题面简述：
我们可以把树想象成若干条链的结合体，然后后我们要求的就是这几条链上严格不下降子序列（连续）的个数（不必最长）。太抽象了吧。
考试思路：
记录最大左边界与最小右边界，进行 \(dfs\) ，遍历整棵树，当发现一个儿子是合法时，在一个新图上将父亲向儿子连边，并将父亲的出度++，最后如果不合法则不连边，这样做可以保证在一个连通块内的点所在的子序列的起点是一样的废话。最后只需要在新图中找有多少个出度为 \(0\) 的点（也就是一个不下降子序列的终点）即可。
ACcode:
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <climits>
#include <random>
#include <bitset>
#include <unordered_map>
#define orz %
#define ll long long
#define juruo Optimist_Skm
#define mid ((l + r) / 2.0)
#define pii std::pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define m_p std::make_pair
#define pq std::priority_queue<int>
#define pq_min std::priority_queue<int, std::vector<int>, std::greater<int> >
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define test(x) cout << "Test: " << x << '\n'
#define close fclose(stdin);fclose(stdout);
#define ull unsigned long long
#define debug(); printf("qwq\n");
namespace Fast_Skm {
template <typename T>
inline void read(T &x) {
register T s = 0, w = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') w = -1;
c = getchar();
}
while(isdigit(c))
s = (s << 1) + (s << 3) + (c & 0xcf), c = getchar();
x = s * w;
return ;
}
template <typename T, typename... Arp>
inline void read(T &x, Arp &...arp) {
read(x), read(arp...);
return ;
}
template <typename T>
inline void write(T x) {
if(x < 0) x = -x, putchar('-');
register int p = 0;
static char s[100];
do {
s[++p] = x orz 10 + '0';
x /= 10;
} while (x);
while(p) putchar(s[p--]);
putchar('\n');
}
template <typename T, typename... Arp>
inline void write(T &x, Arp &...arp) {
write(x), write(arp...);
return ;
}
template <typename S, typename T>
inline void smax(S &x, T y) {
x = (x > y) ? x : y;
}
template <typename S, typename T>
inline void smin(S &x, T y) {
x = (x < y) ? x : y;
}
inline void quit() {
exit(0);
return ;
}
inline ll quick_pow(ll a, ll b, ll P) {
register ll ans = 1;
while(b >= 1) {
if(b & 1) {
ans = ans * a % P;
}
a = a * a % P;
b >>= 1;
}
return ans;
}
template <typename T>
inline T exgcd(T a, T b, T &x, T &y) {
if(b == 0) {
x = 1; y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int tmp = y;
y = x - a / b * y;
x = tmp;
return gcd;
}
} using namespace Fast_Skm;
const int N = 2e5 + 7, M = 1e9 + 7;
int n, l[N], r[N], ans = 0, vis[N], out_deg[N];
std::vector<int> E[N];
inline bool cmp(int a, int b) {
return r[a] < r[b];
}
inline void dfs(int now, int maxl, int minr) { //维护边界
std::sort(E[now].begin(), E[now].end(), cmp);
for (const auto &it : E[now]) {
if(r[it] < maxl) {
dfs(it, l[it], r[it]);
maxl -= r[it];
minr -= r[it];
}
else {
out_deg[now]++; //记录出度
int tmpr = std::min(maxl, minr), tmpl = std::max(l[it], maxl); //更新边界
dfs(it, tmpl, tmpr);
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
read(n);
for (int i = 2; i <= n; ++i) {
int x;
read(x);
E[x].eb(i);
}
for (int i = 1; i <= n; ++i) {
read(l[i], r[i]);
}
dfs(1, l[1], r[1]);
for (int i = 1; i <= n; ++i) {
if(out_deg[i] == 0) {
ans++;
}
}
write(ans);
return 0;
}
\(T3\) （题目链接）
题面简述：
一眼背包，但不会。在 \(N\) 物品中选若干个，其中有两个限制，一个是每类的重量上限，一个是总的重量上限，我们要求出最打价值。
订正思路：
先对每个类进行 \(01\) 背包，然后总体进行分组背包。竟然出奇地简单！！！
ACcode:
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <climits>
#include <random>
#include <bitset>
#include <unordered_map>
#define orz %
#define ll long long
#define juruo Optimist_Skm
#define mid ((l + r) / 2.0)
#define pii std::pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define m_p std::make_pair
#define pq std::priority_queue<int>
#define pq_min std::priority_queue<int, std::vector<int>, std::greater<int> >
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define test(x) cout << "Test: " << x << '\n'
#define close fclose(stdin);fclose(stdout);
#define ull unsigned long long
#define debug(); printf("qwq\n");
namespace Fast_Skm {
template <typename T>
inline void read(T &x) {
T s = 0, w = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') w = -1;
c = getchar();
}
while(isdigit(c))
s = (s << 1) + (s << 3) + (c & 0xcf), c = getchar();
x = s * w;
return ;
}
template <typename T, typename... Arp>
inline void read(T &x, Arp &...arp) {
read(x), read(arp...);
return ;
}
template <typename T>
inline void write(T x) {
if(x < 0) x = -x, putchar('-');
int p = 0;
static char s[100];
do {
s[++p] = x orz 10 + '0';
x /= 10;
} while (x);
while(p) putchar(s[p--]);
putchar('\n');
}
template <typename T, typename... Arp>
inline void write(T &x, Arp &...arp) {
write(x), write(arp...);
return ;
}
template <typename S, typename T>
inline void smax(S &x, T y) {
x = (x > y) ? x : y;
}
template <typename S, typename T>
inline void smin(S &x, T y) {
x = (x < y) ? x : y;
}
inline void quit() {
exit(0);
return ;
}
inline ll quick_pow(ll a, ll b, ll P) {
ll ans = 1;
while(b >= 1) {
if(b & 1) {
ans = ans * a % P;
}
a = a * a % P;
b >>= 1;
}
return ans;
}
template <typename T>
inline T exgcd(T a, T b, T &x, T &y) {
if(b == 0) {
x = 1; y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y);
int tmp = y;
y = x - a / b * y;
x = tmp;
return gcd;
}
} using namespace Fast_Skm;
const int N = 5e3 + 7;
ll n, m, C, v[N], w[N], c[N], dp[N][N], lim[N], f[N][N];
std::vector<pii> l[N];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
read(n, m, C);
for (int i = 1; i <= n; ++i) {
read(v[i], w[i], c[i]);
l[c[i]].eb(m_p(v[i], w[i]));
}
for (int i = 1; i <= C; ++i) {
read(lim[i]);
smin(lim[i], m);
}
for (int i = 1; i <= C; ++i) {
for (int k = 0; k < l[i].size(); ++k) {
for (int j = lim[i]; j >= l[i][k].se; --j) {
smax(f[i][j], f[i][j - l[i][k].se] + l[i][k].fi);
}
}
}
for (int i = 1; i <= C; ++i) {
for (int j = 1; j <= m; ++j) dp[i][j] = dp[i - 1][j];
for (int j = 1; j <= lim[i]; ++j) {
for (int k = j; k <= m; ++k) {
smax(dp[i][k], dp[i - 1][k - j] + f[i][j]);
}
}
}
write(dp[C][m]);
return 0;
}
\(T4\) （题目链接）
题面简述：
求概率。
思路：
目前未AC