2019夏季訓練——杭電多校第6場-Nonsense Time(HDU 6635)(最長上昇サブシーケンス+記録経路O(nlogn))
21674 ワード
杭電多校第6場-nonsense Time(HDU 6635)
リンクhttp://acm.hdu.edu.cn/showproblem.php?pid=6635 2つの配列a[]とk[]はいずれも1~nの配列であり、ここでa[]配列のすべての数が完全に凍結され(凍結と削除は同じ意味)、k[]配列の順序で、a[]配列の1つの要素、すなわちi回目、a[k[i]]に対応する要素が回復するたびに、a[]配列で復元された要素のうち、最長上昇サブシーケンスがどれくらい長いか.データ量:n<=5 e 4で、最大3つのサンプルがあります.さらに,a配列とk配列はランダム数で生成されると題した.Time limit:14000 ms構想試合の時、苦慮してnlognのアルゴリズムが思いつかなかった.a配列とk配列がランダムに生成されていることを無視したからだ.ランダムに生成された1~nの配列の最長上昇サブシーケンスの数学的期待がルートnであると結論すると、後進的に直接暴力を振るい、まず最長上昇サブシーケンスを見つけ、その後kの逆順に1つの数を削除し、現在求められている最長上昇サブシーケンスの要素を削除すると、では、nlognの新しい最長上昇サブシーケンスを再求めればいいのです.乱数生成のため,全時間複雑度はO(n*n^(1/2)*logn)である.T=3なので、総所要時間は3秒程度です.ACコード:
最近まとめてacmを勉强するのはいろいろな原因で前の努力がないと感じて、金メダルのために、きっと自励して、もっと努力します.
リンクhttp://acm.hdu.edu.cn/showproblem.php?pid=6635 2つの配列a[]とk[]はいずれも1~nの配列であり、ここでa[]配列のすべての数が完全に凍結され(凍結と削除は同じ意味)、k[]配列の順序で、a[]配列の1つの要素、すなわちi回目、a[k[i]]に対応する要素が回復するたびに、a[]配列で復元された要素のうち、最長上昇サブシーケンスがどれくらい長いか.データ量:n<=5 e 4で、最大3つのサンプルがあります.さらに,a配列とk配列はランダム数で生成されると題した.Time limit:14000 ms構想試合の時、苦慮してnlognのアルゴリズムが思いつかなかった.a配列とk配列がランダムに生成されていることを無視したからだ.ランダムに生成された1~nの配列の最長上昇サブシーケンスの数学的期待がルートnであると結論すると、後進的に直接暴力を振るい、まず最長上昇サブシーケンスを見つけ、その後kの逆順に1つの数を削除し、現在求められている最長上昇サブシーケンスの要素を削除すると、では、nlognの新しい最長上昇サブシーケンスを再求めればいいのです.乱数生成のため,全時間複雑度はO(n*n^(1/2)*logn)である.T=3なので、総所要時間は3秒程度です.ACコード:
#include
",i)
using namespace std;
// using namespace __gnu_pbds;
typedef double db;
typedef long long ll;
typedef pair<int,int>PII;
const double PI = acos(-1.0);
// const ll MOD=1e9+7;
const ll NEG=1e9+6;
const int MAXN=5e4+10;
const int INF=0x3f3f3f3f;
const ll ll_INF=9223372036854775807;
const double eps=1e-9;
int n;
int a[MAXN];
int d[MAXN],pos[MAXN],fa[MAXN];//
int del[MAXN];//
int k[MAXN];
int vis[MAXN];//
vector<int>v;
int update()
{
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
memset(fa,0,sizeof(fa));
memset(pos,0,sizeof(pos));
int len=1;
for(int i=1;i<=n;i++)
{
if(del[i])continue;
int id=lower_bound(d+1,d+len,a[i])-d;
// printf("id=%d
",id);
d[id]=a[i];
if(id==len)len++;
pos[id]=i;
fa[i]=pos[id-1];
}
for(int i=pos[len-1];i;i=fa[i])
{
vis[i]=1;
// printf("%d ",a[i]);
}
// puts("");
return len-1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
v.clear();
memset(vis,0,sizeof(vis));
memset(del,0,sizeof(del));
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=1;i<=n;i++)scanf("%d",k+i);
int len=update();
// printf("len=%d
",len);
v.pb(len);
for(int i=n;i>1;i--)
{
del[k[i]]=1;
if(vis[k[i]])
{
len=update();
v.pb(len);
}
else
{
v.pb(len);
}
}
for(int i=n-1;i>=0;i--)
{
printf("%d",v[i]);
if(i>0)printf(" ");
}
printf("
");
}
return 0;
}
最近まとめてacmを勉强するのはいろいろな原因で前の努力がないと感じて、金メダルのために、きっと自励して、もっと努力します.