个人题解（A M F L C E G）
之前单发的G好像不太够字数，于是水一下个人解法，为了照顾萌新我会尽量讲明白一点。
// 之后补题会顺便更新
A
一个比较显然的结论：1与任何数互质
考虑石头个数为偶数的情况，此时你只能拿走奇数个石头，那么轮到对方时一定是奇数个石头；
石头个数为奇数的话，此时我拿一个，轮到对方就是偶数个石头；
这意味着如果我先手且开局为奇数的话，轮到我的时候永远是奇数，偶数同理。
显然1是奇数，于是结论很显然了。
代码如下：
#define ll long long
void solve(){
ll n;cin>>n;
if(n%2==1){
cout<<"Yes\n";
}
else if(n%2==0){
cout<<"No\n";
}
}
M
简单统计，略
F
小学解方程，略
L
神秘模拟，好奇为什么一开始没人做，一开始C过的都比这个多
上手画一下会发现无论多少层都有解，这里分享一下我自己的画法
注意到沿着红色箭头走下来之后，按照以下方式操作若干次即可：向左走到头，然后上下横跳走到头。
然后观察一下数字规律，一个循环走下来即可。
注意层数的定义！
代码如下：
void solve(){
int n;cin>>n;
n++;//层数定义看错导致的
cout<<"Yes\n";
int pre=1;
cout<<pre<<' ';
for(int i=1;i<n;i++){
pre=i+pre;
cout<<pre<<' ';
}
int t=n;
while(t--){
for(int i=1;i<=t;i++){
pre=pre+1;
cout<<pre<<' ';
}
for(int i=1;i<=2*t-1;i++){
if(i%2==1){
pre=pre-t-1;
cout<<pre<<' ';
}
else{
pre=pre+t;
cout<<pre<<' ';
}
}
}
}
C
前置知识：字典树的定义，只需要了解一棵字典树长什么样子就可以了。
本题可以直接套字典树板子，当然排序也可以，简单说一下为什么字典树做法是对的：
首先注意到只有退格，那么我们只需要关注前缀就可以了。
朴素的贪心思想：所有前缀都应该利用完价值再删除，即：一个公共前缀删除前，应使带有该前缀的字符串全部出现过。这个很显然，无需证明。
那么什么顺序最优呢？其实不重要，我们只需要使得最长的字符串最后出现即可：因为除了最后一个字符串，其他的字符串我们都会删除掉。
再看字典树，我们会发现：敲键盘打字的次数实际上就是字典树中所有字符的数量——我们定义这个数量为。
删除次数=打字次数
最长字符串长度
那么
代码如下（随便抄了个板子）：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct TrieNode {
TrieNode* children[26];
TrieNode() {
for (int i = 0; i < 26; ++i) children[i] = nullptr;
}
~TrieNode() {
for (int i = 0; i < 26; ++i)
if (children[i]) delete children[i];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> words(n);
for (int i = 0; i < n; ++i)
cin >> words[i];
while (m--) {
int l, r;
cin >> l >> r;
l--; r--;
vector<string> q;
for (int i = l; i <= r; ++i)
q.push_back(words[i]);
TrieNode* root = new TrieNode();
int sum = 0;
int max_len = 0;
for (const auto& word : q) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (!current->children[index]) {
current->children[index] = new TrieNode();
sum++;
}
current = current->children[index];
}
if (word.size() > max_len) max_len = word.size();
}
int result = sum * 2 - max_len;
cout << result << '\n';
delete root;
}
return 0;
}
顺带提一下排序的方法：
本质上其实是一样的，因为按照字典序排了之后相同前缀的会挨在一起，不赘述了
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> words(n);
for (int i = 0; i < n; ++i)
cin >> words[i];
while (m--) {
int l, r;
cin >> l >> r;
l--; r--;
vector<string> q;
for (int i = l; i <= r; ++i)
q.push_back(words[i]);
sort(q.begin(), q.end());
if (q.empty()) {
cout << "0\n";
continue;
}
int sum_len = 0;
int max_len = 0;
for (auto& s : q) {
sum_len += s.size();
if (s.size() > max_len) max_len = s.size();
}
int total_lcp = 0;
for (int i = 1; i < q.size(); ++i) {
const string& a = q[i-1];
const string& b = q[i];
int lcp = 0;
while (lcp < a.size() && lcp < b.size() && a[lcp] == b[lcp])
++lcp;
total_lcp += lcp;
}
int ans = (sum_len - total_lcp) * 2 - max_len;
cout << ans << '\n';
}
return 0;
}
E
神秘二分，竟然一遍过了。
简单说一下思路：
如何统计碰撞次数呢？对于每个向右移动的小球，统计所有在其右侧向左移动的小球数量
，
即是总碰撞次数。道理很简单：因为碰撞交换速度且两球速率相同，我们可以认为两个球穿透了彼此继续按照原速度移动（高中物理好像讲过，等效替代）；
注意到小球速度都是一样的，那么给定时间 t，对于两个小球而言，当且仅当一个小球向右移动，另一个小球向左移动，并且它们之间的距离在 t 时间内可以被缩短到 0，它们才会发生碰撞。同样使用我们上述的等效替代考虑，任意两个球的移动区间有交集则认为这两个球发生了一次碰撞。
要球经过多长时间发生k次碰撞的话就很简单了，二分时间后check次数即可。
看了一眼精度感觉跑个几十次check就行了，保险起见跑了150次
#define ll long long
ll cal(double t, const vector<int>& sr, const vector<int>& sl) {
int nr=sr.size(), nl=sl.size();
ll res=0;
double two_t=2*t;
int l=0, r=0;
for(int x:sr){
double limit=x+two_t;
while(l<nl&&sl[l]<=x)l++;
while(r<nl&&sl[r]<=limit)r++;
res+=r-l;
}
return res;
}
void solve(){
int n,k;
cin>>n>>k;
vector<int> sr,sl;
for(int i=0;i<n;++i){
int p,v;
cin>>p>>v;
if(v==1)sr.push_back(p);
else sl.push_back(p);
}
sort(sr.begin(),sr.end());
sort(sl.begin(),sl.end());
ll total=0;
int l=0,nl=sl.size();
for(int x:sr){
while(l<nl&&sl[l]<=x)l++;
total+=nl-l;
}
if(total<k){
cout<<"No\n";
return;
}
double low=0.0,high=0.0;
if(!sr.empty()&&!sl.empty()&&sr[0]<sl.back()){
high=(sl.back()-sr[0])/2.0;
}
for(int _=0;_<150;++_){
double mid=(low+high)*0.5;
ll cnt=cal(mid,sr,sl);
if(cnt>=k)high=mid;
else low=mid;
}
cout<<"Yes\n"<<fixed<<setprecision(7)<<high<<'\n';
}
G：
第一眼看过去就知道肯定是整除分块，对于每个块对应的余数，我们可以将其看作一段长为等差数列。
我们定义一个分块为Block：
struct Block { int a, b, q; }; // [a,b]除数区间，对应商为q
其中为除数区间，对于任意
属于[a,b]，有
；
此时我们知道，对于任意属于
，
的值构成一个等差数列，我们知道此时区间内的最大余数为
，即
。
不妨暴力的考虑：将所有的分块放入一个优先队列中，按照最大余数的大小进行排序，每次从区间中取出一个最大余数，更新区间，再将其放回队列中，直到取满k个元素。
显然对于k=1e9的数据规模这是必定超时的。
如何优化呢？
这里有一个很巧妙的方法：我们可以二分计算出一个阈值T，T表示大于等于T的余数至少有k个。
那么问题就迎刃而解了：我们只需要遍历所有区间，每个区间取出所有大于等于T的余数，再把多余的等于T的余数减去即可。
代码：
#define ll long long
struct Block { int a, b, q; }; // [a,b]除数区间，对应商为q
vector<Block> blocks;
void build(int n) {
blocks.clear();
for(int q=1, r; q<=n; q=r+1) {
r = n/(n/q); // 计算当前商对应的除数区间右边界
blocks.push_back({q, r, n/q}); // 存储除数区间[q,r]和商
if(r == n) break; // 终止条件
}
}
ll count(int T, int n) {
ll cnt = 0;
for(auto &blk : blocks) {
int q_val = blk.q;
int max_i = (n - T)/q_val; // 最大满足条件的除数
int low = max(blk.a, 1); // 除数区间下限
int high = min(blk.b, max_i);
if(high >= low) cnt += high - low + 1;
}
return cnt;
}
ll sum(int T, int n) {
ll s = 0;
for(auto &blk : blocks) {
int q_val = blk.q;
int max_i = (n - T)/q_val;
int low = max(blk.a, 1);
int high = min(blk.b, max_i);
if(high >= low) {
int cnt = high - low + 1;
int first = n - q_val*low; // 首项余数
int last = n - q_val*high; // 末项余数
s += (ll)(first + last)*cnt/2;
}
}
return s;
}
void solve() {
int n, k;
cin >> n >> k;
build(n); // 构建分块
// 二分求临界值T
int l=0, r=n, T=0;
while(l <= r) {
int mid = (l+r)/2;
count(mid, n) >= k ? (T=mid,l=mid+1) : (r=mid-1);
}
ll total = sum(T, n);
ll cnt = count(T, n);
cout << total - (cnt - k)*T << endl;
}
正浩创新EcoFlow公司福利 199人发布