C

给定一列数,选定若干不相交的区间,对每个区间进行排序,使得最后呈升序。
问选定区间最多为多少

贪心

额,我们扫一遍,然后我们找当前数在排序后的序列的最近位置,然后我们更新一个最大值。
若恰好到达某一位置时候,最大值也为之,则选定这个区间,这样选择的区间长度总是尽量小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
int n,h[maxn],t[maxn];
map<int,int> mp;

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",h+i),t[i] = h[i];
sort(t,t+n);
mp.clear();
int cur = 0,ans = 0;
for(int i=0;i<n;++i)
{
int p = int(lower_bound(t,t+n,h[i])-t) + mp[h[i]];
++mp[h[i]];
if(p > cur)
{
cur = p;
}
if(cur == i) ++ans;
}
printf("%d\n",ans);
return 0;
}

D

暴力+数学
给定x,问有多少m*n的矩形,满足其中包含的正方形个数恰为x

我们发现m*n的矩形(我们不妨设 $m \leq n$)包含的矩形个数为
$\sum_{ 0 < m-i \leq m} (m-i)(n-i) = m*m*n - \frac{m(m-1)}{2}(m+n) + \frac{m(m-1)(2m-1)}{6}$

然后暴力枚举m,求出n再判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<pair<LL,LL> > ans ;

int main()
{
//freopen("test.txt","r",stdin);
LL x;
scanf("%lld",&x);
ans.clear();
LL cnt = 0;
for(LL m=1; ;++m)
{
LL n = (x + m*(m*m-1)/6)/(m*(m+1)/2);
LL res = n*m*(m+1)/2 - m*m*(m-1)/2 + m*(m-1)*(2*m-1)/6;
// printf("%lld %lld %lld\n",m,n,res);
if(m >= n)
{
if(m > n)
{
cnt *= 2;
}
else
{
if(res == x)
{
++cnt;
ans.push_back(make_pair(m,n));
cnt *= 2;
cnt -= 1;
}
else cnt *= 2;
}
break;
}

if(res != x) continue;
++cnt;
ans.push_back(make_pair(m,n));
}
printf("%lld\n",cnt);
for(int i=0;i<ans.size();++i)
{
printf("%lld %lld\n",ans[i].first,ans[i].second);
}
for(int i=ans.size()-1;i>=0;--i)
{
if(cnt&1 && i == ans.size()-1) continue;
printf("%lld %lld\n",ans[i].second,ans[i].first);
}
return 0;
}