目录
- G Link with Monotonic Subsequence
- J Link with Arithmetic Progression
- K Link with Bracket Sequence I
- D Link with Game Glitch
G Link with Monotonic Subsequence
题目
对于[1-n]的一种排列，求其最长上升子序列和最长下降子序列的最大值的最小值
分析
排列权值的最小值为 ⌈ ⌉
只需要构造形如 3, 2, 1, 6, 5, 4, 9, 8, 7 的排列即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e5+10,M=5e5+5;
int n;
int main(){
//freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--) {
cin>>n;
int m=0;
while(m*m<n) m++;
int i=1;
for(i=1;i<=n;i+=m) {
for(int j=min(n,i+m-1);j>=i;j--) {
cout<<j<<' ';
}
}
cout<<'\n';
}
return 0;
}
J Link with Arithmetic Progression
题目
将一个数组变为一个等差数列，花费代价为 ，求其最小代价
分析
通过列式子可以发现代价与公差与公比有关，且最高次数为2次，可以利用三分模拟，可以先模拟公差，公比可以直接根据二次函数在对称轴取得最小值直接计算。
也可以利用线性回归直接计算最小代价
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e5+10,M=5e5+5;
int n;
int a[N];
ld check(ld t) {
ld sum=0,ans=0;
for(int i=1;i<=n;i++) {
sum += a[i]-(i-1)*t;
}
sum /= n; // 此时最小值即取平均值
for(int i=1;i<=n;i++) {
ld x=a[i]-(i-1)*t;
ans+=(sum-x)*(sum-x);
}
return ans;
}
int main(){
//freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout.setf(ios::fixed);
cout.precision(10);
int T;
cin>>T;
while(T--) {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
ld l=-1e9,r=1e9,ans=1e30; // 三分模拟公差
while(r-l>1e-9) {
ld midl=(l+l+r)/3.0;
ld midr=(l+r+r)/3.0;
ld ansl=check(midl);
ld ansr=check(midr);
ans = min(ans,min(ansl,ansr));
if(ansl<ansr) r=midr;
else l=midl;
}
cout<<ans<<'\n';
}
return 0;
}
K Link with Bracket Sequence I
题目
知括号序列 a 是一个长度为 m 的合法括号序列 b 的子序列，求可能 的序列 b 的数量。
分析
记表示序列b的前i位中，匹配a的前j个，前左括号比右括号多k个的方案数
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e2+10,M=5e5+5;
int n,m;
int f[N][N][N];
char str[N];
int main(){
//freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
scanf("%s",str+1);
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=0;i<m;i++) {
for(int j=0;j<=n;j++) {
for(int k=0;k<=i;k++) {
if(!f[i][j][k]) continue;
// 第i个位置分别为（ 和 ）
int t=j+(str[j+1]=='('); // 避免重复计算
f[i+1][t][k+1]=(f[i][j][k]+f[i+1][t][k+1])%mod;
t=j+(str[j+1]==')');
if(k) f[i+1][t][k-1]=(f[i+1][t][k-1]+f[i][j][k])%mod;
}
}
}
printf("%d\n",f[m][n][0]);
}
return 0;
}
D Link with Game Glitch
题目
给定 m 个物品合成的方式，求一个最大的合成损耗参数 w ，使得所有 物品都无法通过无限合成的方式无限获得。
分析
考虑建图 对于每个物品建点，每个合成方式由 bi 向 di 建有向边，边权为 ci/ai 。
原问题实际上是要求一个最大的 w ，使得在每条边的边权乘上 w 之后， 不存在一个乘积大于 1 的环。
将值取对数，转为加法，判断是否存在负权换。
w具有单调性 ，二分w，check 的问题类似于求负环。由于边权乘积较大，需要对其取对数。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e3+10,M=5e5+5;
int n,m,cnt[N];
bool st[N];
char str[N];
double d[N];
vector<pair<int,double> > e[N];
bool check(double x) {
queue<int> q;
memset(cnt,0,sizeof(cnt));
memset(d,0,sizeof(d));
memset(st,0,sizeof(st));
for(int i=1;i<=n;i++) {
st[i]=1; q.push(i);
}
while(q.size()) {
int t=q.front(); q.pop();
st[t]=0;
for(int i=0;i<e[t].size();i++) {
int k=e[t][i].first;
double w=e[t][i].second;
if(d[k]<d[t]+x+w) {
d[k]=d[t]+x+w;
cnt[k]=cnt[t]+1;
if(cnt[k]>=n+3) return false; // 存现负权换
if(!st[k]) { // 不在队列，加入队列
st[k]=1;
q.push(k);
}
}
}
}
return true;
}
int main(){
//freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin>>n>>m;
int a,b,c,d;
for(int i=1;i<=m;i++) {
cin>>a>>b>>c>>d;
e[b].push_back({d,log(1.0*c/a)});
}
int ca=60;
double l=0,r=1;
while(ca--&&r-l>1e-9) {
double mid=(l+r)/2;
if(check(log(mid))) l=mid;
else r=mid;
}
cout<<fixed<<setprecision(9)<<l<<'\n';
return 0;
}
京公网安备 11010502036488号