2022牛客多校2

  • 构造排列,使 最小

想不出来怎么构造,那就先暴力看看规律

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
#include<bits/stdc++.h>
using namespace std;
int lis(vector<int>& a){
vector<int> f(a.size(),1);
for(int i=1;i<a.size();i++){
for(int j=0;j<i;j++){
if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
}
}
return *max_element(f.begin(),f.end());
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)a[i]=i+1;
int ans=1e9;
vector<int> ans2;
while(1){
int res=lis(a);
reverse(a.begin(),a.end());
res=max(res,lis(a));
reverse(a.begin(),a.end());
if(ans>res){
ans=res;
ans2=a;
}
if(next_permutation(a.begin(),a.end())==0)break;
}
cout<<ans<<"\n";
for(auto &i:ans2)cout<<i<<" ";
}
input1
1
9
output1
1
2
3
3 2 1 6 5 4 9 8 7
input2
1
10
output2
1
2
4
1 2 6 5 4 3 10 9 8 7

由上述两例不难发现规律

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
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
int ans=sqrt(n);
if(ans*ans!=n)ans++;
vector<int> a(n+1);
int num=n;
for(int i=n-ans+1;i>=1;i-=ans){
for(int j=i,cnt=1;cnt<=ans;j++){
a[j]=num;
num--;
cnt++;
}
}
if(num){
for(int j=1;;j++){
a[j]=num;
num--;
if(num==0)break;
}
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}

不过这道题好像可以由Dilworth定理推出结论

  • 可以换

  • 这样会有 bug 产生,比如 ,这样会导致

  • 现有 ,可以变成 可以换

  • 问在不产生 bug 的前提下, 最大值?

答案显然具有单调性,二分答案即可,现在考虑每次怎么

可以理解为 连了一条 的边,图中路径距离是相乘关系(相乘可能会很大,取个 )。

问题即转化成图中有无距离大于 的环。

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
#include<bits/stdc++.h>
using namespace std;
#define add(x,y,z) edge[++tail]={head[x],y,z};head[x]=tail;
struct Edge{
int ne,to;
long double w;
};
int main(){
int n,m;
scanf("%d%d",&n,&m);
vector<int> a(m),b(m),c(m),d(m);

int tail=0;
vector<int> head(n+1,0);
vector<Edge> edge(m+1,{0,0,0});
for(int i=0;i<m;i++){
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
add(b[i],d[i],0);
}
vector<long double> dis(n+1,0);
vector<int> v(n+1,0),cnt(n+1,0);
auto spfa=[&](){
for(int i=1;i<=n;i++)dis[i]=cnt[i]=0;
for(int i=1;i<=n;i++)v[i]=1;
queue<int> que;
for(int i=1;i<=n;i++)que.push(i);
while(!que.empty()){
int x=que.front();que.pop();
v[x]=0;
for(int i=head[x],to;i;i=edge[i].ne){
to=edge[i].to;
if(dis[to]<dis[x]+edge[i].w){
dis[to]=dis[x]+edge[i].w;
cnt[to]=cnt[x]+1;
if(cnt[to]>=n)return 1;
if(!v[to])que.push(to),v[to]=1;
}
}
}
return 0;
};
vector<long double> temp(m);
for(int i=0;i<m;i++)temp[i]=((long double)1.0)*c[i]/a[i];
auto pd=[&](double w){
for(int i=0;i<m;i++)edge[i+1].w=log(temp[i]*w);
return spfa();
};
long double l=0,r=1;
while(r-l>1e-8){
double mid=(l+r)/2;
if(pd(mid))r=mid;
else l=mid;
}
printf("%.12Lf",l);
}
  • 给定

  • 长度为 的括号序列(不一定合法) 是长度为 的括号序列(合法) 的子序列

  • 问有多少种 符合要求

表示 序列前 个与 序列前 ,且多出 的方案数。

考虑怎么推到,似乎需要许多判断。

那就考虑由 ,怎么推到其他状态。

如果在 位填

  • 刚好可以与之配对,

同理,如果在 位填

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
#include<bits/stdc++.h>
using namespace std;
constexpr int mo=1e9+7;
void solve(){
int n,m;
string s;
cin>>n>>m>>s;
s+='0';
vector<vector<vector<int>>> f(m+5,vector<vector<int>>(n+5,vector<int>(m+5,0)));
f[0][0][0]=1;
for(int i=0;i<m;i++){
for(int k=0;k<=i;k++){
for(int j=0;j<=min(i,n);j++){
if(k)f[i+1][j+(s[j]==')')][k-1]=(0ll+f[i+1][j+(s[j]==')')][k-1]+f[i][j][k])%mo;
f[i+1][j+(s[j]=='(')][k+1]=(0ll+f[i+1][j+(s[j]=='(')][k+1]+f[i][j][k])%mo;
}
}
}
cout<<f[m][n][0]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}
发布于

2022-07-24

更新于

2022-07-24

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...