第二场:
G:构造
题目:
给你 1 - n 的数字, 问你 max(最长上升子序列的长度, 最长下降子序列的长度) 最小
思路:
证明可得:
分界 为 【根号n】,在块中降序排列。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int d=ceil(sqrt(n));
int i=0;
for( i=1;i+d-1<=n;i+=d)
{
if(i+d-1<=n)
for(int j=d+i-1;j>=i;j--)
{
cout<<j<<" ";
}
}
for( int j=n;j>=i;j--)
cout<<j<<" ";
}
return 0;
}
K: dp
题目:
给你一个长度为 n 的括号序列 a 。
序列 a 是 序列 长度为 m 的 b 的子序列。 问你 序列 b 有多少种情况,
思路:
状态表示:
f[i][j][k]
表示 当前 b 的前 i 个位置的 lcs 长度为 j (在 a 中选了长度为 j ),左括号比右括号多 k 个
属性: 数量
状态计算:
- 第 i 个位置放
(
,
f[i][j + (s[j + 1] == '(')][k + 1] += f[i - 1][j][k];
- 第 i 个位置放
)
f[i][j + s[j + 1] == ')'][k - 1] += f[i - 1][j][k];
代码
void solved()
{
memset(f, 0, sizeof f);
cin >> n >> m;
string s;
cin >> s;
f[0][0][0] = 1;
for(int i = 1; i <= m; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= m; k++)
{
//i 放 (
f[i][j + (s[j + 1] == '(')][k + 1] += f[i - 1][j][k]%MOD;
//放)
if(k != 0)
f[i][j + s[j + 1] == ')'][k - 1] += f[i - 1][j][k]%MOD;
}
cout<< f[m][n][0] << endl;
}
D: 判断负环
题目:
存在 n 种类型的物品,物品之间存在一种关系。
例如可以用 a 个 b物品制作成 c*w 个 d物品。 问你最大的 d 不会出现无限复制物品的情况
思路:
建图: 两个物品之间的 边为 c * w / a ,
二分 w 的值,来判断是否存在图中乘积 > 1的环。
因为乘积导致数字很大。 我们可以取 -log 变为 加法 ,之后就可以判断是否存在负环即可
使用spfa 判断负环。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int ne[N], e[N], h[N];
double w[N];
int idx;
void add(int a, int b, double c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
double dist[N];
bool st[N];
int cnt[N];
bool check(double mid)
{
queue<int> q;
for(int i = 1; i <= n; i++)
q.push(i), dist[i] = -1e9, st[i] = true, cnt[i] = 0;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i] - log(mid))
{
dist[j] = dist[t] + w[i] - log(mid);
cnt[j] = cnt[t] + 1;
if(cnt[j] > n) return false;
if(st[j])continue;
st[j] = true;
q.push(j);
}
}
}
return 1;
}
int main()
{
cin >> n >> m;
memset(h, -1 ,sizeof h);
for(int i = 0;i < m; i++)
{
int b , d;
double c , a;
cin >> a >>b >> c >> d;
add(b, d, -log(c/a));
}
double l = 0, r = 1.0;
while(r - l >= 1e-8)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%0.7lf",l);
return 0;
}
L:DP
题目:
存在 n 个世界,每个世界有 m 个点,每个世界有一些边。
每次可以选择通过边到下个点。但是必须到下个世界的下个点或者还是当前点。
思路:
状态表示:
集合:
dp[i][j]
从 1 号点 到 i 个世界的 j 号点 最晚可以从 哪个世界出发。
属性: max
状态计算:
如果 u - v 存在一条边
并且 走 u - v
dp[i][v] = max(dp[i][v], dp[i-1][u])
如果不走
dp[i][v] = dp[i-1][v])
如果不优化一维
代码
int main()
{
cin >> n >> m;
int res = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
//如果是从上个世界不走
for(int j = 0; j <= m; j++) dp[i][j] = dp[i-1][j];
// 初始化边界。如果 u == 1 , 从1号点到 v ,那么最晚为当前世界
dp[i-1][1] = i;
int k;
cin >> k;
for(int j = 1; j <= k; j++)
{
int u, v;
cin >> u >> v;
// if(u == 1) dp[i][v] = i;
dp[i][v] = max(dp[i][v], dp[i-1][u]);
}
if(dp[i][m] != 0)
res = min(res, i - dp[i][m] + 1);
}
if(res == 0x3f3f3f3f) cout << -1 << endl;
else cout << res << endl;
return 0;
}
优化一维,做等价变形。
如果要更新当前世界的当前点。需要上个世界的对应点来更新。 所以只需要维护 2 个 世界的dp值即可。
dpp表示上个世界维护的值。
代码:
int n, m;
int dp[N];
int dpp[N];
signed main()
{
cin >> n >> m;
int res = 1e18;
for(int i = 1; i <= n; i++)
{
dpp[1] = i;
int k;
cin >> k;
for(int j = 1; j <= k; j++)
{
int u, v;
cin >> u >> v;
dp[v] = max(dp[v], dpp[u]);
}
if(dp[m] != 0)
res = min(res, i - dp[m] + 1);
for(int j = 1; j <=m ; j++)dpp[j] = dp[j];
}
if(res == 1e18) cout << -1 << endl;
else cout << res << endl;
return 0;
}
1