2020-2021:teams:wangzai_milk:20200727比赛记录
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/30 23:23] infinity37 [B - Binary Vector] |
2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/30 23:29] (当前版本) infinity37 [J - Josephus Transform] |
||
|---|---|---|---|
| 行 411: | 行 411: | ||
| } | } | ||
| rep(i,1,n) cout<<a[i]<<" \n"[i==n]; | rep(i,1,n) cout<<a[i]<<" \n"[i==n]; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| + | ==== K - K-Bag ==== | ||
| + | |||
| + | 问给出的序列是否是若干个$1-k$序列组成序列的子序列（好绕） | ||
| + | |||
| + | 首先特判序列里有大于k的情况。 | ||
| + | |||
| + | 其余的上权值线段树，对于前k个位置，只要没有次数大于1就行，后面的dp转移，权值线段树查长度为k的区间是否次数都为1，如果是就转移，然后最后k个位置和前k个位置类似处理。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | #define il inline | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const int N=5e5+5; | ||
| + | const int inf = 1e9+5; | ||
| + | int mx[N<<2],a[N],id[N],cnt; | ||
| + | bool f[N]; | ||
| + | void build(int p,int l,int r) { | ||
| + | mx[p] = 0; | ||
| + | if (l==r) return ; | ||
| + | int mid = (l+r)>>1; | ||
| + | build(p<<1,l,mid); | ||
| + | build(p<<1|1,mid+1,r); | ||
| + | } | ||
| + | void Update(int p,int l,int r,int a,int b) { | ||
| + | if (l==r) { | ||
| + | mx[p]+=b; | ||
| + | return ; | ||
| + | } | ||
| + | int mid = (l+r)>>1; | ||
| + | if (a<=mid)Update(p<<1,l,mid,a,b); | ||
| + | else Update(p<<1|1,mid+1,r,a,b); | ||
| + | mx[p] = max(mx[p<<1],mx[p<<1|1]); | ||
| + | } | ||
| + | int Getans(int p,int l,int r,int a,int b) { | ||
| + | if (l>=a&&r<=b) | ||
| + | return mx[p]; | ||
| + | int mid = (l+r)>>1; | ||
| + | int ans = 0; | ||
| + | if (a<=mid)ans = max(ans,Getans(p<<1,l,mid,a,b)); | ||
| + | if (b >mid)ans = max(ans,Getans(p<<1|1,mid+1,r,a,b)); | ||
| + | return ans; | ||
| + | } | ||
| + | int getid(int x) { | ||
| + | int l = 1,r = cnt+1; | ||
| + | while (l<r) { | ||
| + | int mid = (l+r)>>1; | ||
| + | if (id[mid]<x)l = mid+1; | ||
| + | else r = mid; | ||
| + | } | ||
| + | return l; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int cas; | ||
| + | scanf("%d",&cas); | ||
| + | while (cas--) { | ||
| + | int n,k; | ||
| + | scanf("%d%d",&n,&k); | ||
| + | bool flag = false; | ||
| + | for (int i = 1;i<= n;i++) { | ||
| + | scanf("%d",&a[i]); | ||
| + | if (a[i] > k || a[i] <= 0) flag = true; | ||
| + | id[i] = a[i]; | ||
| + | } | ||
| + | if (flag) {printf("NO\n");continue;} | ||
| + | cnt = 0; | ||
| + | id[0] = -1; | ||
| + | sort(id+1,id+n+1); | ||
| + | for (int i = 1;i<= n;i++) | ||
| + | if (id[cnt]!=id[i]) | ||
| + | id[++cnt] = id[i]; | ||
| + | build(1,1,cnt); | ||
| + | for (int i = 1;i<= n;i++)f[i] = false; | ||
| + | f[0] = true; | ||
| + | for (int i = 1;i<= n && i <= k;i++) { | ||
| + | Update(1,1,cnt,getid(a[i]),1); | ||
| + | if (Getans(1,1,cnt,1,cnt)==1) | ||
| + | f[i] = true; | ||
| + | } | ||
| + | for (int i = k+1;i<= n;i++) { | ||
| + | int tp = i-k; | ||
| + | Update(1,1,cnt,getid(a[i]),1); | ||
| + | Update(1,1,cnt,getid(a[tp]),-1); | ||
| + | if (Getans(1,1,cnt,1,cnt)==1) | ||
| + | f[i] |= f[i-k]; | ||
| + | } | ||
| + | int bg = max(1,n-k+1); | ||
| + | bool ans = f[n]; | ||
| + | for (int i = bg;i<= n && !ans;i++) | ||
| + | { | ||
| + | if (f[i-1] && Getans(1,1,cnt,1,cnt)==1) | ||
| + | ans = true; | ||
| + | Update(1,1,cnt,getid(a[i]),-1); | ||
| + | } | ||
| + | if (ans) printf("YES\n"); | ||
| + | else printf("NO\n"); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> </hidden> | </code> </hidden> | ||
| \\ | \\ | ||
2020-2021/teams/wangzai_milk/20200727比赛记录.1596122595.txt.gz · 最后更改: 2020/07/30 23:23 由 infinity37
