A 构造/贪心

B 贪心

C 利用等价类计数

D 贪心

A 构造

考虑”<>”的位置,直接构造即可.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int maxn = 500000+10;
char S[maxn];
int a[maxn];
int main()
{
scanf("%s",S);
int len=strlen(S);
for(int i=0;i<len;i++)
{
if(S[i]=='<')
a[i+1]=a[i]+1;
}
for(int i=len-1;i>=0;i--)
{
if(S[i]=='>')
a[i]=max(a[i],a[i+1]+1);
}
ll sum=0;
for(int i=0;i<=len;i++)
sum+=a[i];
cout<<sum;
}

B 贪心

这类分类找最值的题,一般是转化为min/max的单调性质去做的.

首先考虑最靠右的左端点,记录这个端点为X,同理最靠左的端点记录为Y.

分类讨论:

(1).X,Y 都分在同一个集合内,这个集合的权值就被确定了,那么按照贪心性,我们把除了最长的线段之外的线段都加入到这个集合内,那么答案显然.

(2)X,Y分属两个集合.记X在的集合为$P$,Y在的集合为$Q$,考虑到如下引理:
$$
if ~A属于 B ,\min(B)\leq \min(A)
$$
如果我们将一个线段扔进$P$,那么这个时候将剩下不会更改$P$答案的点扔进这个集合显然是更优的.

按照这样的思想,这个问题就变成了取前缀$\min$和后缀$\min$之和的一个问题,排序后逐个比较即可.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<ll,ll> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
vector<pii> pp;
vector<pii> T;
ll mxL,minR,mxR,minL;


int main()
{
int N;
cin>>N;
mxL=mxR=-1;
minL=minR=10000000000ll;
int P,Q;
for(int i=1;i<=N;i++)
{
ll x,y;
read(x),read(y);
y++;
pp.push_back(make_pair(x,y));
if(x>mxL)
{
mxL=x;
P=i;
}
if(minR>y)
{
minR=y;
Q=i;
}
}
ll ans1=0,ans2=0;
minL=0;
for(int i=1;i<=N;i++)
{
minL=max(minL,pp[i-1].second-pp[i-1].first);
}

ans1=max((minL),0ll)+max((minR-mxL),0ll);

int ca=1;
for(auto p:pp)
{
if(ca!=P&&ca!=Q)
T.push_back(make_pair(max(p.second-mxL,0ll),max(minR-p.first,0ll)));
ca++;
}
sort(T.begin(),T.end());
ll P1=pp[P-1].second-pp[P-1].first;
ll Q1=pp[Q-1].second-pp[Q-1].first;
ll x1=0,x2=Q1;
for(int i=0;i<T.size();i++)
{

x1=min(T[i].first,P1);
ans2=max(ans2,x1+x2);
x2=min(T[i].second,x2);
}
ans2=max(ans2,P1+x2);
cout<<max(ans1,ans2);

}

C 利用等价类计数

方法一:

这个题核心在于构造等价类,利用更容易计数的等价类来计算答案.

考虑删除只能删除相邻字符,那么其实字符的奇偶相对性不会改变,那么我们可以构造一个等价类:

将奇数位置AB互换,统计不能删除”AA,BB”的字符串个数.

这个计数非常简单,考虑”A,B”内部不能自己相消,那么其实这个充要条件是”A的字符数量和B的字符数量都不能超过$\frac{n}{2}$”.

这个证明可以通过构造证明得出.

那么接下来等价类计数非常简单,组合数推一推式子即可.(式子见代码)

(注意不能写$O(nlogn)$的naive计算组合数的方式,TLE好几发~)

方法二:

方法二是用一种比较组合数学的方式,但事实上是和第一种方法等价的.

考虑只有”AB,BA”的字符串,设以下方程:$\sum_{i=1}^{N/2}x_i=S,x_i\in {-1,1}$,字符串可被消空当且仅当$S=0$.

同时,我们注意到”AB,BA”是互斥的,换句话说,也就是如果不能被消空,那么要不然是”AB”没有被消空,要不然是”BA”没有被消空.那么我们得到:
$$
Ans=|I|-|AB|-|BA|=3^n-2*(“AB”没有被消空的序列数量)
$$
这个时候考虑转换成不定方程,$\sum_{i=1}^{N/2}x_i=S,x_i\in {-1,1,0}$,$x$的取值可以由是否能被消除推出.

得出生成函数$F(x)=(4x^{-1}+4+x)^{N/2}$.那么方案数其实就是$F(x)$次数大于0项的系数和.

泰勒展开后得到与之前一样的式子.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*
* @Author: RBQRBQ
* @Date: 2020-04-05 21:40:13
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-05 22:23:03
*/

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn =10000000+10;
const ll mod=998244353;
inline ll qpow(ll a, ll n, ll p)
{
ll ans = 1;
while(n)
{
if(n & 1ll)
ans = ans * a % p;
a = a * a % p;
n >>= 1ll;
}
return ans;
}
ll A[maxn+10];
ll B[maxn+10];

void exPower( int b, int p, int & a, int & k ) {
if( p == 0 ) {
a = 1; k = 0;
return;
}
exPower( p, b % p, k, a );
k -= b / p * a;
return;
}
int inv( int b, int p ) {
int a, k;
exPower( b, p, a, k );
if( a < 0 ) a += p;
return a;
}
void init( int n ) {
A[ 0 ] = 1;
for( int i = 1; i <= n; ++i ) A[ i ] = A[ i - 1 ] * i % mod;
B[ n ] = inv( A[ n ], mod );
for( int i = n - 1; i >= 0; --i ) B[ i ] = B[ i + 1 ] * ( i + 1 ) % mod;
return;
}
inline ll C(ll a, ll b)
{
if(a < b)
return 0;
return (A[a] * B[b] %mod)*B[a-b]%mod;
}
ll mul(ll x,ll y)
{
return (x*y)%mod;
}
ll add(ll x,ll y)
{
return (x+y>=mod)?x+y-mod:x+y;
}
ll pre[maxn];
int main()
{
int N;
cin>>N;
ll ans=qpow(3,N,mod);
init(maxn);
ll pos=0;
pre[0]=1ll;
for(int i=1;i<=N/2-1;i++)
{
pre[i]=mul(pre[i-1],2);
}
for(int i=1;i<=N/2;i++)
{
//pos=(pos%mod+(qpow(2,(N/2-i),mod)*C(N,N/2+i))%mod)%mod;
pos=add(pos,mul(pre[N/2-i],C(N,N/2+i)));
}
pos=pos*2%mod;
cout<<(ans-pos+mod)%mod;
}

D 贪心

(题解咕咕咕了)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef pair<int,int> pii;

namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}

using namespace IO;

typedef pair<ll,ll> frac;

ll N,S=0;
vector<frac> T;
bool mp(frac A,frac B)
{
return (A.first*B.second<A.second*B.first);
}
ll gcd(ll x,ll y) { return (!y)?x:gcd(y,x%y); }
signed main()
{

read(N);
for(int i=1;i<=N;i++)
{
ll x,y;
read(x),read(y);
S+=x;
T.push_back(make_pair(std::max(x,y),y));
}
sort(T.begin(),T.end(),greater<frac>());
ll pos=0;
ll point=-1;
int ca=0;
for(auto it=T.begin();it!=T.end();it++)
{
if((pos+it->first) >S) break;
pos+=it->first;
point=it-T.begin();
ca++;
}
if(ca==N){cout<<"0 1"<<endl;return 0;}
frac ans(0,1);
for(int i=0;i<T.size();++i)
{
if(i>point)
{
if(pos+T[i].second>=S)
{
frac res(pos+T[i].second-S,T[i].second);
ans=(mp(ans,res))?res:ans;
}
}
else
{
if(pos-T[i].first+T[point+1].first+T[i].second>=S)
{
frac res(pos-T[i].first+T[point+1].first+T[i].second-S,T[i].second);
ans=(mp(ans,res))?res:ans;
}
}
}
ans.first+=ans.second*(N-ca-1);ans.second*=N;
ll _f=gcd(ans.first,ans.second);
cout<<ans.first/_f<<" "<<ans.second/_f<<endl;
return 0;
}