C.Potions
题目描述
有 (n) 瓶药剂，从左往右编号依次是 (1...n)，每瓶药剂有一个值 ，表示喝下去之后会变化 (a_i) 点生命值。你的初始生命值为 (0)，从左往右依次选择药剂喝掉，询问最多可以喝多少药剂，过程中要保证生命值不低于 (0)
(1leq nleq 2cdot 10^5,-10^9leq a_ileq 10^9)
解法
老子反悔贪心白学了，直接乱喝，喝死了把最毒的一瓶吐出来。
还可以不守交规，先把解药喝了，再从最小的毒药开始喝，能喝就喝。
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
priority_queue<long long, vector<long long>, greater<long long> > pq;
long long S = 0;
for(int i = 1;i <= n;i++){
long long x; cin >> x;
S += x;
pq.push(x);
while(S < 0){
S -= pq.top();
pq.pop();
}
}
cout << (int) pq.size();
}
D. Kill Anton
题目描述
给定一个只含 A,N,O,T 的初始基因序列，你可以任意安排目标基因序列（基因含量相同）的顺序，试确定目标序列，使得初始序列通过交换相邻位置到目标序列的步数最大，输出目标序列。
(nleq 100000)
解法
这种交换到指定顺序消耗步数的题尽量转成逆序对问题吧，要不然真的想不动。
设 (c_i) 表示第 (i) 个初始的位置的终点，可知同一种颜色的 (c_i) 一定是单增的，并且 (c_i) 序列的逆序对个数就是步数
关键的结论是：最优方案一定是相同的颜色挨在一起，证明：
考虑 (i<j) 的颜色相同，如果 ([i,j]) 之间大于 (c_i) 的位置多，那么把 (c_i) 换到 (c_j) 旁边不会减少逆序对。
如果 ([i,j]) 之间小于 (c_i) 的位置多，因为 (c_i<c_j)，那么把 (c_j) 换到 (c_i) 旁边不会减少逆序对。
最后把 (4) 种颜色的全排列搜索一下就行了。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 100005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,a[M],b[200],c[5],v[5],cnt[5],f[5][5];char s[M];
signed main()
{
T=read();
b['A']=0;b['N']=1;b['O']=2;b['T']=3;
c[0]='A';c[1]='N';c[2]='O';c[3]='T';
while(T--)
{
scanf("%s",s+1),n=strlen(s+1);
memset(f,0,sizeof f);
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
{
a[i]=b[s[i]];
cnt[a[i]]++;
}
for(int x=0;x<4;x++)
{
int sz=0;
for(int i=1;i<=n;i++)
{
f[x][a[i]]+=sz;
if(a[i]==x) sz++;
}
}
v[0]=0;v[1]=1;v[2]=2;v[3]=3;
int mx=0,ans[5]={};
do
{
int res=0;
for(int i=0;i<4;i++)
for(int j=i+1;j<4;j++)
res+=f[v[j]][v[i]];
if(res>=mx)
{
mx=res;
memcpy(ans,v,sizeof ans);
}
}while(next_permutation(v,v+4));
for(int i=0;i<4;i++)
for(int j=0;j<cnt[ans[i]];j++)
printf("%c",c[ans[i]]);
puts("");
}
}
E. Oolimry and Suffix Array
题目描述
给定长度为 (n) 的后缀数组，求在字符集为 (k) 的情况下，有多少字符串的后缀数组是它。
(1leq n,kleq 200000)
解法
把数组中相邻两个后缀的大小关系解决了，那么字符串自然就确定了。
一开始以为这个限制很不好搞，但这个题其实把后缀的大小关系全部告诉你了，所以后缀 (i) 在后缀 (j) 正好前一位，讨论去掉第一个字符后两后缀的大小关系，直接在给定的后缀数组里面查询就行了。
那么我们就得到了某个字符严格小于某个字符，或者小于等于某个字符的限制。由于按这样看字符一定是单增的，可以自然地联想到不定方程的整数解问题，设严格小于的限制有 (cnt) 个，那么就是要求这些地方必须取正数，其他地方可以为 (0)
使用插板法不难得到答案是 ({n+k-cnt-1choose n})，减 (1) 的原因是第一个位置也必须取正数。
#include <cstdio>
const int M = 400005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,a[M],p[M],fac[M],inv[M];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[i]*inv[i-1]%MOD;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
if(n<m) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
signed main()
{
init(4e5);
n=read();k=read();
for(int i=1;i<=n;i++)
a[i]=read(),p[a[i]]=i;
p[n+1]=-1;
for(int i=1;i<n;i++)
if(p[a[i]+1]>p[a[i+1]+1])
k--;
printf("%lld
",C(n+k-1,n));
}