08-27 17:00 郑州轻工业大学 C++ 发布于河南

关注

2025河南萌新联赛题解：（郑州轻工业大学）

在此由衷感谢验题方: Cedeat HaPpY夢 silence_JY 长途

A：数组的贡献

对任意元素 $a_i$ 考虑它作为区间内部被计数的元素时的贡献，可以将问题转化为：每个 $a_i$ 能作为“区间中不小于端点的元素”出现多少次？

对于任意一个位置，我们可以事先预处理其左右两侧（包括自身）分别有多少可以作为边界的选择，那么它的贡献即为：能选的左端点个数 × 能选的右端点个数。最终答案枚举所有位置求和即可。

预处理需要得到一个数以左（包括自身）小于等于它的数的个数，和一个数以右（包括自身）小于等于它的数的个数。可以通过树状数组解决这一问题。对任意元素 $a_i$ 考虑它作为区间内部被计数的元素时的贡献，可以将问题转化为：每个 $a_i$ 能作为“区间中不小于端点的元素”出现多少次？

预处理需要得到一个数以左（包括自身）小于等于它的数的个数，和一个数以右（包括自身）小于等于它的数的个数。可以通过树状数组解决这一问题。

using namespace std;
#define int long long

const int MAXN = 200000 + 10;
int mod = 1000000000 + 7;
int c[MAXN][2];
int lowbit(int a) {return a & -a;}

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<pair<int, int>> p(n + 1);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        p[i] = {a[i], i};
    }
    memset(c, 0, sizeof(c));
    vector<int> l_mn(n + 1), r_mn(n + 1);
    sort(p.begin() + 1, p.end(), [](pair<int, int> x, pair<int, int> y){
        if(x.first == y.first) return x.second < y.second;
        else return x.first < y.first;
    });
    for(int i = 1; i <= n; ++i) {
        for(int j = p[i].second; j <= n; j += lowbit(j)) c[j][0] += 1;
        int sum = 0;
        for(int j = p[i].second; j; j -= lowbit(j)) sum += c[j][0];
        l_mn[p[i].second] = sum;
    }
    sort(p.begin() + 1, p.end(), [](pair<int, int> x, pair<int, int> y){
        if(x.first == y.first) return x.second > y.second;
        else return x.first < y.first;
    });
    for(int i = 1; i <= n; ++i) {
        for(int j = p[i].second; j; j -= lowbit(j)) c[j][1] += 1;
        int sum = 0;
        for(int j = p[i].second; j <= n; j += lowbit(j)) sum += c[j][1];
        r_mn[p[i].second] = sum;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += l_mn[i] * r_mn[i] % mod;
        ans %= mod;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; cin >> t;
    while(t--) { solve(); }
    return 0;
}

B:Running Up That Hill

首先，我们能想到异或的性质: $xorSum[l, r] = xorSum[r] \oplus xorSum[l - 1]$ ，所以问题转化为统计前缀异或数组 $xorSum$ 中满足 $xorSum[i] \oplus xorSum[j] ≥ k$ 的有序对 $(i, j)$ ，很自然想到我们可以固定住其中一个然后求另一个符合的数量，就可以统计出答案。
考虑到建立一颗 01Trie，每个节点记录经过它的数的数量，遍历每个前缀并设 $x = xorSum[i]$ , 在 01Trie 中查询有多少插入过的前缀 $y$ 使得 $x \oplus y ≥ k$ ，查询时从高位向低位决定走哪条分支或直接把整棵子树计入答案，查询完后再把 $x$ 插入到 01Trie中，最终把每次查询得到的计数累加就是答案。总体复杂度大约为 $O(n * 31)$


using i64 = long long;
constexpr int N = 1 << 25;

int trie[N][2], cnt[N];
int tot = 0;

void insert(int x) {
    int cur = 0;
    for (int i = 30; i >= 0; i--) {
        int v = x >> i & 1;
        if (!trie[cur][v]) {
            trie[cur][v] = ++tot;
        }
        cur = trie[cur][v];
        cnt[cur]++;
    }
}

int query(int cur, int x, int low, int i) {
    int v = x >> i & 1;
    if ((1 << i) >= low) {
        int ans = 0;
        if (trie[cur][1 - v]) {
            ans += cnt[trie[cur][1 - v]];
        }
        if (trie[cur][v]) {
            ans += query(trie[cur][v], x, low, i - 1);
        }
        return ans;
    } else {
        if (trie[cur][1 - v]) {
            return query(trie[cur][1 - v], x, low ^ (1 << i), i - 1);
        } else {
            return 0;
        }
    }
}

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n), pf(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        pf[i + 1] = pf[i] ^ a[i];
    }
    
    i64 ans = 0ll;
    for (int i = 0; i <= n; i++) {
        ans += query(0, pf[i], k, 30);
        insert(pf[i]);
    }
    std::cout << ans << "\n";
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C.灯光是我在异世界的呼喊

$n^2$ 的暴力枚举显然不太可行，于是考虑建立一颗 Trie 树，把所有字符串插入到 Trie 树中，然后枚举一遍所有字符串长度求最大值，总体复杂度为 $O(n \log n + n)$ 。


using i64 = long long;

constexpr int N = 1 << 20;
int trie[N][26], vis[N];
int tot = 0;
std::vector<int> res;
 
void insert(std::string s) {
    int cur = 0;
    for (int i = 0; i < s.size(); i++) {
        int v = s[i] - 'a';
        if (!trie[cur][v]) {
            trie[cur][v] = ++tot;
        }
        cur = trie[cur][v];
        vis[cur]++;
    }
    res.push_back(cur);
}

void solve() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        insert(s);
    }
    int ans = 0;
    for (auto &i : res) {
        ans = std::max(ans, vis[i]);
    }
    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D:灯泡

首先偶数号码的同学按偶数次相当于没按，奇数号码的同学按了奇数次相当于改变了一次状态。

设一间教室的号码为 $a$ ，将 $a$ 进行质因数分解， $a=2^{a_1}*3^{a_2}*5^{a_3}*\dots*k_{n}^{a_n}$ ， $a_i$ 为 $a$ 的第 $k_{i}$ 个质因子的数量，将其分为两堆：

写为 $a=x*y$ 的形式，其中 $x=2^{a_1}*3^{x_2}*5^{x_3}*\dots*k_{n}^{x_n}$ ，

$y=2^{0}*3^{a_2-x_2}*5^{a_3-x_3}*\dots*k_{n}^{a_n-x_n}$ ，

$a_1 \neq 0$ 时， $x$ 一定为偶数。我们只需要统计 $y$ 为奇数的个数。

又因为 $y$ 中不包含 $2$ 的因子，所以只需计算所有不同 $y$ 的个数，即 $\prod\limits_{i=2}^{n}(a_i+1)$ 。
$a_1 = 0$ 时， $x$ 和 $y$ 一定都是奇数，所以只有 $x = y$ 时会提供一次状态改变。即 $\forall a_i\equiv0 \ (mod\ 2)$ 。

当 $\prod\limits_{i=2}^{n}(a_i+1)\equiv1 \ (mod \ 2)$ 时 $\forall a_i\equiv0 \ (mod\ 2)$ 。

综上可得只有号码为 $num=2^{x}*p*p(p\in Z,x\in N)$ 的房间是亮着的。 $num=2^{x\%2}*(p*2^{\lfloor \frac{x}{2} \rfloor})*(p*2^{\lfloor \frac{x}{2} \rfloor})$ 。

综上：只需求满足上述条件的 $num$ 的数量即可。即 $num=p*p(p\in Z)$ 或 $num=2*p*p(p\in Z)$ 。

时间复杂度为 $O(log(n))$ 。

using namespace std;

using i64 = long long;

void solve () {
    i64 n;
    cin >> n;
    i64 l = 0, r = sqrt(n), res = 0;
    while (l < r) {
        i64 mid = l + r + 1 >> 1;
        if (mid <= n / mid) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    res += l;
    n /= 2;
    l = 0, r = sqrt(n);
    while (l < r) {
        i64 mid = l + r + 1 >> 1;
        if (mid <= n / mid) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    res += l;
    cout << res << "\n";
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    i64 T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E:优美子序列

记录子序列每种最后两个字符情况所能取到的最大长度。遍历 $s$ 时将最后两个字符中不存在 $s[i]$ 并且最后两个字符不相同的情况更新，状态转移方程 $f[k][s[i]-'a'] = max(f[j][k]+1,f[k][s[i]-'a'])$ 。

时间复杂度为 $O(26*26*n)$ 。

using namespace std;

using i64 = long long;

void solve () {
    i64 n;
    cin >> n;
    i64 l = 0, r = sqrt(n), res = 0;
    while (l < r) {
        i64 mid = l + r + 1 >> 1;
        if (mid <= n / mid) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    res += l;
    n /= 2;
    l = 0, r = sqrt(n);
    while (l < r) {
        i64 mid = l + r + 1 >> 1;
        if (mid <= n / mid) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    res += l;
    cout << res << "\n";
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    i64 T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F:谁是武器大师

分组背包，对于每种武器预处理在每种吉欧所能取到的最大价值，每种武器最多 $\frac{(m+1)*(m+2)}{2}$ 种消耗吉欧的方式。再按照分组背包遍历 $n$ 种武器即可。

时间复杂度为 $O(\frac{n*(m+1)*(m+2)*k}{2})$ 。

using namespace std;

#define endl '\n'
#define int long long
#define all(a) a.begin(),a.end()
#define gcd(a, b) gcd(a, b)
#define lcm(a, b) a / gcd(a, b) * b
#define IOS ios::sync_with_stdio(0);cin.tie(0);

const int N = 3000000 + 10;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f3f3f;
const long double pi = acosl(-1);
constexpr long double eps = 1e-12;
constexpr int dx[] = {-1, 0, 0, 1}, dy[] = {0, 1, -1, 0};

using ull = unsigned long long;
mt19937_64 rng (chrono::steady_clock::now().time_since_epoch().count());


void solve () {

    int n, m, k;
    cin >> n >> m >> k;
    
    // 整理第i件武器花费cost枚吉欧可获得的最大价值
    vector <map <int, int>> mp(n + 1);
    for (int i=1; i<=n; i++) {
        int v, x, a, y, b;
        cin >> v >> x >> a >> y >> b;
        mp[i][0] = v;
        for (int j=0; j<m;  j++) {
            map <int, int> p;
            for (auto [cost, val] : mp[i]) {
                p[cost + x] = max(p[cost + x], val + a);
                p[cost + y] = max(p[cost + y], val * b);
            }
            for (auto [cost, val] : p) {
                mp[i][cost] = max(mp[i][cost], val);
            }
        }
    }

    // 前i件武器在花费j枚吉欧以内能获得的最大价值
    vector <vector <int>> dp(n + 1, vector <int> (k + 1));
    for (int i=1; i<=n; i++) {
        for (int j=k; j>=0; j--) {
            for (auto [x, y] : mp[i]) {
                if (x > j) break;
                dp[i][j] = max(dp[i][j], dp[i-1][j-x] + y);
            }
        }
    }

    cout << dp[n][k] << endl;
}

signed main () {
//     clock_t start, end;
//     start = clock();
    
    IOS;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }

//     end = clock();
//     cout << end - start << endl;
    return 0;
}

G:好想去界园

本题是一个在有向无环图（DAG）上的动态规划问题。每个节点有三种类型，分别对战力或票券产生不同影响，边需要消耗票券。目标是最大化到达终点节点n时的战力。

我们可以这样设计状态， $ans[i][j]$ 代表到达 $i$ 点时并拥有 $j$ 张票卷时的最大战力。由于图是DAG，使用拓扑排序（通过入度队列）确保按正确顺序处理节点。另外注意票券消耗和增加时的边界检查（非负、不超过100）。无法到达的状态需要标记。

节点数 $n≤100$ ，票券状态 $101$ 种，类型2节点需要内层循环（ $101$ ），总复杂度约为 $O(m×101×101)$ 。

using namespace std;
using ll = long long;
#define endl "\n"
const int mod = 998244353;
void solve()
{
	ll n, m, k;
	cin >> n >> m >> k;
	vector<ll> a(n + 1);
	vector<ll> b(n + 1);
	for (int i = 1; i < n; i++)
	{
		cin >> a[i];
		cin >> b[i];
	}
	a[n] = 1;
	b[n] = 0;
	vector<vector<pair<ll, ll>>> ma(n + 1);
	vector<ll> deg(n + 1);
	deg[1] = 1;
	ma[0].push_back({1ll, 0ll});
	for (int i = 0; i < m; i++)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		deg[v]++;
		ma[u].push_back({v, w});
	}
	vector<vector<ll>> ans(n + 1, vector<ll>(101, -1));
	queue<ll> q;
	q.push(0);
	ans[0][k] = 0;
	while (!q.empty())
	{
		auto u = q.front();
		q.pop();
		for (auto [v, w] : ma[u])
		{
			deg[v]--;
			if (a[v] == 1)
			{
				for (int i = 0; i <= 100; i++)
				{
					if (i - w < 0 || ans[u][i] < 0)
						continue;
					ans[v][i-w] = max(ans[v][i-w], ans[u][i] + b[v]);
				}
			}
			if (a[v] == 2)
			{
				for (int i = 0; i <= 100; i++)
				{
					for (int j = 0; j <= 100; j++)
					{
						if (i - w - j < 0 || ans[u][i] < 0)
							continue;
						ans[v][i - w - j] = max(ans[v][i - w - j], ans[u][i] + b[v] * j);
					}
				}
			}
			if (a[v] == 3)
			{
				for (int i = 0; i <= 100; i++)
				{
					if (i - w < 0 || ans[u][i] < 0)
						continue;
					ll ne = i - w + b[v];
					ne = min(100ll, ne);
					ans[v][ne] = max(ans[v][ne], ans[u][i]);
				}
			}
			if (!deg[v])
			{
				q.push(v);
			}
		}
	}
	ll res = -1;
	for (int i = 0; i <= 100; i++)
	{
		res = max(res, ans[n][i]);
	}
	cout << res << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	// cin>> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

H:小 C 的问题

对于区间 $[L,R]$ 内的所有无序对 ${a_i,a_j}$ （ $i<j$ ），我们需要计算：

Ans = \sum_{L\le i<j \le R} (a_i + a_j)^2

设：

S = \sum\limits_{i=L}^R a_i ,\quad Q = \sum\limits_{i=L}^R a_i^2

对原式进行拆分，可推得：

Ans = (R - L - 1)\cdot Q + S^2

于是我们只需要得到区间和 $S$ 与区间平方和 $Q$ 即可求出答案。可以用线段树分别维护。

using namespace std;
#define int long long

int mod = 1000000000 + 7;
const int MAXN = 200000 + 10;
int n, m;
int a[MAXN];
int s1[MAXN * 4], s2[MAXN * 4];

void update(int pos) {
	s1[pos] = (s1[pos << 1] + s1[pos << 1 | 1]) % mod;
	s2[pos] = (s2[pos << 1] + s2[pos << 1 | 1]) % mod;
    return;
}
void build_tree(int pos, int l, int r) {
	if (l == r) {
		s1[pos] = a[l];
		s2[pos] = a[l] * a[l] % mod;
		return;
	}
	int mid = (l + r) >> 1;
	build_tree(pos << 1, l, mid);
	build_tree(pos << 1 | 1, mid + 1, r);
	update(pos);
	return;
}
void modify(int pos, int l, int r, int x, int k) {
	if (l == x && r == x) {
		s1[pos] = k;
		s2[pos] = k * k % mod;
		return;
	}	
	int mid = (l + r) >> 1;
	if (x <= mid) modify(pos << 1, l, mid, x, k);
	if (x > mid) modify(pos << 1 | 1, mid + 1, r, x, k);
	update(pos);
	return;
}
int query(int pos, int l, int r, int x, int y, int k) {
	if (x <= l && r <= y) {
		if(k == 1) return s1[pos];
		if(k == 2) return s2[pos];
	}
	int val = 0;
	int mid = (l + r) >> 1;
	if (x <= mid) val = (val + query(pos << 1, l, mid, x, y, k)) % mod;
	if (y > mid) val = (val + query(pos << 1 | 1, mid + 1, r, x, y, k)) % mod;
	return val;
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    build_tree(1, 1, n);
    for(int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if(opt == 1) {
            int L, R; cin >> L >> R;
            int ans = (R - L - 1) * query(1, 1, n, L, R, 2) % mod;
            int t = query(1, 1, n, L, R, 1);
            ans = (ans + t * t % mod) % mod;
            cout << ans << "\n";
        }
        else if(opt == 2) {
            int a, b; cin >> a >> b;
            modify(1, 1, n, a, b);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

I:Raidian的游戏

根据数据范围，我们可以采取相当暴力的写法处理此题。

考虑枚举所有可能的答案，并对答案进行合法性检测。如果合法的答案超过一个，那说明根据已有的信息不能得到正确答案。

using namespace std;
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    if(n==1&&m==1&&k==0)
    {
        cout<<1<<endl;
        return;
    }
    else if(k==0)
    {
        cout<<-1<<endl;
        return;
    }
    int num = 0;
    vector<vector<int>> a(k, vector<int>(m));
    vector<int> b(k);
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
        cin >> b[i];
    }
    vector<int> np(n);
    for (int i = 0; i < n; i++)
        np[i] = i + 1;
    vector<int> ans(m);
    int ct=0;
    do
    {
        for (int i = 0; i < n - m+1; i++)
        {
            int num = 0;
            for (int u = 0; u < k; u++)
            {
                int cnt=0;
                for (int j = i; j < i + m; j++)
                {
                    if (np[j] ==a[u][j-i]) cnt++; 
                }
                if(cnt==b[u])
                {
                    num++;
                }
            }
            if(num==k)
            {
                int flag=0;
                for(int u=0;u<m;u++)
                {
                    if(ans[u]!=np[i+u]) flag=1;
                    ans[u]=np[i+u];
                }
                if(flag==1) ct++;
                if(ct>1)
                {
                    cout<<-1<<endl;
                    return;
                }
            }
        }
    } while (next_permutation(np.begin(), np.end()));
    for(int i=0;i<m;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

J:掷骰子

将红色骰子和蓝色骰子的数字排序后，红 $\{2, 7, 12, 17, 22, 27\}$ ，蓝 $\{3, 8, 13, 18, 23, 28\}$ 。

通过观察，我们可以发现：红色骰子和蓝色骰子都是公差为 $5$ 的等差数列。

那我们不妨假设每个骰子初始都是 $a_1$ ，那么对于每个骰子都可以进行 $5$ 次 $+5$ 。

一个红色骰子 $= 2 + 5×i$ $(0 \leq i \leq 5)$ ，一个蓝色骰子 $= 3 + 5×i$ $(0 \leq i \leq 5)$ 。

骰子的总和 $S$ $=$ 红色骰子和 $+$ 蓝色骰子和 $= (18+5×i) + (27+5×j) = 45 + 5×(i+j)$ （ $i$ , $j$ 为整数，且 $0\leq i,j\leq45$ ）。因此， $S$ 必须满足：

在区间 $[45, 495]$ 内（因为最小和 $45$ ，最大和 $495$ ）。
是 $5$ 的倍数（因为 $S=45+5×(i+j)$ ）。

于是对于每个数据我们都可以 $O(1)$ 的判断，总时间复杂度为 $O(n)$ 。

using namespace std;

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
    cin >> n;
    
    int ans = n,t;
    for(int i = 0; i < n; ++i)
    {
        cin >> t;
        if(t % 5 == 0 && t >= 45 && t <= 495)
            ans--;
    }

    cout << ans << "\n";
	return 0;
}

}

K:好奇的小夏

解决此问题的一个关键发现是：答案中的第二个数字（即最小数字）必定与某个 $a_j$ 相同。其原因如下：假设答案的第二个数字是 $a_j+d$ （其中 $d≠0$ ），且 $a_j+d$ 不等于任何 $a_i$ 。这意味着我们将某些小于 $a_j$ 的数字增加至 $a_j$ ，再将其中部分数字（包括原本等于 $a_j$ 的数字）进一步提升至 $a_j+d$ 。但若我们仅将这些数字增至 $a_j$ 就停止，所需操作次数更少，结果也更优。

基于此，我们可以采用如下方法：

将数组按非递减顺序排序。
遍历每个 $a_i$ ，假设 $a_i$ 是可操作的数量最多的最小数字，我们需要将较小数字增至 $a_i$ ，且操作次数不超过 $k$ 。显然，应优先增加与 $a_i$ 差值最小的 $a_j$ 。若采用 $O(n²)$ 解法，可从 $i$ 向前遍历 $j$ 直至无法操作，但我们需要更高效的方案。

优化方案：

使用二分搜索枚举最终等于 $a_i$ 的元素数量 $cnt$
验证使 $cnt$ 个元素变为 $a_i$ 的操作数是否 $≤k$ ： $∑(a_i - a_j) = cnt × a_i - (s_i - s_{i-cnt}) ≤ k$ （其中 $s$ 为前缀和数组）
通过预处理前缀和，可在 $O(1)$ 时间内完成验证

最终时间复杂度为 $O(n log n)$ 。

using namespace std;
#define ll long long
#define endl "\n"

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
    
	int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
        
    sort(a.begin() + 1, a.end());
    vector<ll> as(n + 1);
    for(int i = 1; i <= n; ++i)
        as[i] = as[i - 1] + a[i];

    ll mxnum = 0, mxv;
    for(int i = 1; i <= n; ++i)
    {
        int l = 1, r = i;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[i] * (i - mid + 1) - (as[i] - as[mid - 1]) <= k)
                r = mid;
            else
                l = mid + 1;
        }
        if(i - l + 1 > mxnum)
        {
            mxnum = i - l + 1;
            mxv = a[i];
        }
    }

    cout << mxnum << ' ' << mxv << endl;
	return 0;
}

L:写程序or打游戏

Solution 1：动态规划

对于前 $k + 1$ 个事件，显然每个情况都是 $i + 1$ 种，既 $dp[i] = i + 1$ ,对于后面的每个事件分为两种情况：如果选写程序那么答案累加 $dp[i - 1]$ ，如果选择打游戏显然答案累加 $dp[i - k - 1]$ ,综合起来转移就是 $dp[i] = dp[i - 1] + dp[i - k - 1]$ ,再对 $10^9 + 7$ 取模即可。

using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
#define LL long long
const int N = 2e5 + 10, M = 1e7, inf = 1e18;
const int mod = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> f(n + 5);
    for (int i = 1; i <= k + 1; i ++ ) {
        f[i] = i + 1;
    }
    for (int i = k + 2; i <= n; i ++ ) {
        f[i] = (f[i - 1] + f[i - k - 1]) % mod;
    }
    cout << f[n] << endl;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // intal(1e7);
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

Solution 2：组合计数

直接从 $0-n$ 枚举写程序的个数，那么打游戏的数量就为 $n - i$ ,又因为打游戏之间必须有k个写程序事件，所以用 $(n - i - 1) * k$ 个写程序事件把打游戏隔开，此时写程序事件剩下 $i - (n - i - 1) * k$ 个，由于打游戏有 $n - i$ 个事件，所以有了 $n - i + 1$ 个空格，用隔板法统计方案数为 $C(i - (n - i - 1) * k, n - i)$ ,答案对 $10^9 + 7$ 取模即可。

using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
#define LL long long
const int N = 2e6 + 10, M = 1e7, inf = 1e18;
const int mod = 1e9 + 7;


LL fac[N], infac[N]; // C a b == a! / (*b! * (a - b)!) == a! * (b!)[逆元] * (a - b)![逆元]
// fac[a] = a! % mod;  infac[b] = (b!)[逆元] 

LL qmi(LL a, LL k) {
    LL ans = 1;
    while (k) {
        if (k & 1) ans = ans * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return ans;
}

void intal(int n) {
    fac[0] = infac[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        fac[i] = fac[i - 1] * i % mod;
        infac[i] = infac[i - 1] * qmi(i, mod - 2) % mod;
    }
}

int C(int a, int b) {
    if (a < b || a < 0 || b < 0) return 0;
    return fac[a] * infac[b] % mod * infac[a - b] % mod;
}


void solve() {
    int n, k;
    cin >> n >> k;
    intal(n + k);
    int ans = 0;
    for (int i = 0; i <= n; i ++ ) {
        ans = (ans + C(i - (n - i - 1) * k + n - i, n - i)) % mod;
    }
    cout << ans << endl;

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

M:奥数班

根据题目所给的A，B，分别判断属于题目描述中的哪种情况即可。

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << "=" << '\n';
	} else if (a > b) {
		if (a >= b * 10) cout << ">>" << '\n';
		else cout << ">" << '\n';
	} else {
		if (a * 10 <= b) cout << "<<" << '\n';
		else cout << "<" << "\n";
	}
	return 0;
}

#河南萌新联赛#