写在前面
emmmmmm， 这次只过了6道题， 排名19，但是两个队友都比我多，不是很开心。刚开始的时候特别紧张， 签到题先是看错题， 然后选了c语言直接编译错误， 然后才过了，用时17分钟， 然后可能手感来了， 过了这道题后连A4题， 节奏还可以， 用了不到两个小时， 只罚时了一次， 然后我就遇到了K题， 我用我自认为对的做法和自认为对的暴力对拍， 没有任何问题， 然后这个很浪费我的时间， 大概用了80多分钟还没写出来， 打乱的我的节奏，我的排名也下降了好多。这是我开始慌了， 我看了一通过，发现J题通过人数不少，在我的调试和手玩特殊样例之下， 还是过了。 此时还有1个半小时。我的心里还是放不下K题， 又肝了很长时间，最后选择放弃。 最后可能只剩下三四十分钟， 我赶紧去看了看别的题， D题通过人数很多，我看了看，有点思路， 其实就是正解， 但我没有考虑周到 没有严格的证明， 就没有提交。 然后我继续看G题， 发现我会， 我就疯狂的码， 最后也是码完了， 但没有过， 待看题解后一探究竟。 期间也多次看K题。不得不说，这个Ｋ题完全打乱了我的节奏，花费时间大概2个小时，还影响了后面的做题情况，非常不应该，下次如果还是有道题没过，不能盲目自信，可能就是有的点没有考虑周到。
D
这是Ｄ题， 过的人很多， 我当时也没有说很认真的去想， 错失了Ａ这道题的机会。答案非常简单，
ans = min(r - l + 1); 这个上界非常显然， 下界只需构造a[i] = (i - 1) % ans即可， 这个就是在任意一个长度大于ans的区间里， 都存在0~ans-1这些数， 没有写出来真是可惜。
G
这是G题， 非常可惜， 我看一眼就知道是状压，在最后20分钟还是拼命码完了， 但是没有过， 我也不知道为什么 ，打完了才发现是m写成n， 最后改了一下， 直接过了， 我非常崩溃。 可能还是时间安排的不好， 最后没有时间了， 不然这个题还是能写出来。 题解给的是状压dp， 而我写的是基于Dijkstra的堆优化。代码就不给出了， 太简单了。
H
这是H题， 也是我一下就A了的题， 我的想法是， 要是想使d最大， 那尽量不浪费数字， 那么使前n-1个数相同， 那么我前n-1的数就从m/n枚举到1， 最后一个数孤立起来， 然后求gcd， 复杂度是O(m/n)， 题解给了个挺妙的做法
假如最大公约数都是d, 那么每个数肯定都是d的倍数， 最起码一倍， 且m也是d的倍数， 然后我就枚举m的因子， 如果i使得m/i >= n, 那么这个i就成立，复杂度是O((sqrt m)), 跟我的做法也有异曲同工之妙。
I
这是I题， 虽然也是过了， 但是还有点磕磕绊绊， 肯定是枚举每个区间作为包括所有区间的方案数， 我是按左端点排序， 那么在后面的区间直接二分即可， 前面怎么办呢， 我在思考之后可想了出来， 我把前面的出现的右端点都储存起来， 我在枚举第i个点的时候， 只需要统计在l~r之间有多少个右端点即可， 用树状数组实现， 当然需要右端点的离散化。 题解是这样的：
应该给我写的差不多， 右边的还是二分， 左边的用一个堆来解决， 比我的要简单一点
我的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
map < int, int > m, b;
int n, v[N], c[N], ans = 1;
struct edge {
int l, r;
}a[N], d[N];
inline bool cmp1(edge x, edge y) {
if (x.l == y.l) return x.r < y.r;
return x.l < y.l;
}
inline bool cmp2(edge x, edge y) {
if (x.r == y.r) return x.l < y.l;
return x.r < y.r;
}
inline int find1(int x) {
int l = x, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid].l <= a[x].r) l = mid;
else r = mid - 1;
}
return (l - x);
}
inline void add(int x, int y) {
for (; x <= n; x += x & -x) c[x] += y;
return;
}
inline int query(int x) {
if (x <= 0) return 0;
int ans = 0;
for (; x; x -= x & -x) ans += c[x];
return ans;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
int l, r;
read(l), read(r);
a[i].l = l;
a[i].r = r;
d[i] = a[i];
}
sort(a + 1, a + n + 1, cmp1);
sort(d + 1, d + n + 1, cmp2);
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (d[i].r != d[i - 1].r) {
m[d[i].r] = ++cnt;
v[cnt] = d[i].r;
}
v[cnt + 1] = INF;
ans = 1; ++b[1];
add(m[a[1].r], 1);
int u = 0;
for (int i = 2; i <= n; ++i) {
int ans1 = find1(i);
while (v[u + 1] <= a[i].l) ++u;
++b[m[a[i].r]];
add(m[a[i].r], 1);
if (v[u] < a[i].l) ans1 += query(cnt) - query(u);
else ans1 += query(cnt) - query(u - 1);
ans = max(ans, ans1);
}
cout << ans << endl;
}
std
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
template<class T>void Max(T &a,T b){if(b>a)a=b;}
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;
const int inf=0x3f3f3f3f;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int n;cin>>n;
vector<pii>ar(n);
for(auto &i:ar)cin>>i.fi>>i.se;
sort(ar.begin(),ar.end());
multiset<int>r;
int ans=0;
for(int i=0;i<n;i++){
while(!r.empty()&&*r.begin()<ar[i].fi)r.erase(r.begin());
int a=r.size()+upper_bound(ar.begin(),ar.end(),(pii){ar[i].se,inf})-ar.begin()-i;
Max(ans,a);
r.insert(ar[i].se);
}
cout<<ans;
}
k
k题它来了， k题赶紧滚吧， 当看到这个题的时候， 第一反应是0的产生要不是2 * 5， 或者10， 20这种直接带0的， 然后是分奇偶，当x是奇数的时候， 结果肯定是0， 当x是偶数的时候， 5肯定不存在， 只用数0就行了，这是噩梦的开始，然后我就写了个非常优秀的数0代码， 还和一个自以为对的暴力对拍，没问题，但是死活过不去， 赛后， 有人在讨论这个数0问题， 有个学长说， 50的时候会出现5， 我才明白了。啥也不说了， 上题解吧。
首先2特别多， 我们不必在意， 还有关键就是把每个数都除以2， 就变成了一个阶乘， 而不是双阶乘。 然后就变成了数5的个数， 我们可以一直除以5， 第一次就是(5)，(5^2) (5^3)...的个数， 当然每个只加了一次， 第二次的话就是(5^2) (5^3)的个数， 当然还是加了一次， 持续下去就可以统计出5的个数
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, ans = 0;
int main() {
cin >> x;
if (x & 1) puts("0");
else {
x >>= 1;
while (x) {
x /= 5;
ans += x;
}
cout << ans << endl;
}
return 0;
}
B
比赛的时候并没有看到这道题， 好像没有人过， 但是其实不算难， 直接上题解
题解的大意很好理解， 但细节说的不到位， 按着代码说吧， 前两个操作很好理解， 最后那个k我也是琢磨了很长时间。首先我们想要两两配对， 就必须a和b都是偶数， 但如果n，m都是奇数的话， 最后那个九宫格， 可以放两横两竖， 三横一竖， 三竖一横， 所以如果不是这种情况的话， 就必须把a和b加成偶数， 还有最后的a+b+1, 之所以必须要加1， 我们发现，如果在n, m都是奇数的情况下， 且a+b为奇数的情况下， 左边相当于丢失了0.5， 相当于刚好一格， 比如3 3 3 2 这个数据，因为在n, m都为奇数的情况下， 一定会有一个空格的， 那我们在计算的时候丢失一个格子， 就相当于把这个格子利用上了， 会使刚好放下的答案加1
代码
#include <bits/stdc++.h>
using namespace std;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
int n, m, a, b;
int main() {
read(n), read(m), read(a), read(b);
int k = (n & 1) && (m & 1);
if (n & 1) {
a -= m / 2;
--n;
if (a < 0) a = 0;
}
if (m & 1) {
b -= n / 2;
--m;
if (b < 0) b = 0;
}
if (k == 0) {
if (a & 1) ++a;
if (b & 1) ++b;
}
puts((a + b + 1) / 2 <= n * m / 4 ? "YES" : "NO");
return 0;
}
写在后面
emmmmm， 实话实说， 这次并没有发挥好， 没有证明自己的实力， 我应该可以A8题或以上， 也脱了队伍的后腿， 虽然我们已经组队了， 但如果我的成绩不好的话， 依然不会和他们一起。 所以， 好好学习吧， 不要辜负了自己和队友的期望。