【练习】#564 (Div. 2)
C传送门
题意是给定1-n的序列,附加n个0,每次a序列可以任意取出一张加入b序列尾部并且从b序列头部取出一张加入a序列。问最少多少步能完成排序。
分类贪心。第一类情况是b序列的尾部已经是一个完整的上升序列,并且a序列和b序列前部能顺序完成拼出上升序列,这种情况模拟一下,最后判断是否能成立。
另一种情况是必须把b序列取出一定的数。这种情况,对于每个取到的数子a[i] = k.他在第一个数字1加入a序列以后,最迟要在之后k步内取到,所以取如a序列的数字的步数就是tmp = max(tmp, i – a[i] + 1),在最大一个步数的数字取完后,就能保证顺序加入b序列的尾部时能完成排序,此时答案是tmp + n;因为加入n个数字需要n步。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int a[maxn], b[maxn], vis[maxn];
int n;
int go()
{
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(b[i]) ans = max(ans, i - b[i] + 1);
}
return ans + n;
}
int go2()
{
set<int> st;
for(int i = 1; i <= n; i++) if(a[i]) st.insert(a[i]);
int ans = 0;
int p = 1;
while(st.size() && ans < n)
{
b[n + p] = *st.begin();
st.erase(st.begin());
if(b[p]) st.insert(b[p]);
ans++, p++;
}
int t = 1;
while(b[t] != 1) t++;
for(int i = t, j = 1; j < n; i++, j++) if(b[i] + 1 != b[i + 1]) return INT_MAX;
return ans;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
cout << min(go(), go2());
}
D传送门
题意是说给一颗树关系。边不交叉。问节点形成的圆排列有多少种是满足条件的。
需要观察到的是因为在圆上而且边不交叉。所以每个节点的儿子一定是连续的一段区间,儿子之间是可以任意交换的。答案就是n * \prod{!son[p]}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 233;
int n;
ll a[maxn], p[maxn];
ll mod = 998244353;
int main()
{
cin >> n;
for(int i = 1; i < n; i++)
{
int x, y; cin >> x >> y;
a[x]++, a[y]++;
}
p[0] = 1;
for(int i = 1; i <= n; i++) p[i] = (p[i - 1] * i) % mod;
ll ans = 1;
for(int i = 1; i <= n; i++)
{
ans = (ans * p[a[i]]) % mod;
}
cout << ans * n % mod;
}
发表评论