2020-2021:teams:wangzai_milk:20200727比赛记录
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/28 00:27] wzx27 创建 |
2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/30 23:29] (当前版本) infinity37 [J - Josephus Transform] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ||
| - | ^状态 |- |O |O |- |O |O |Ø |O |- |O |O | | + | ^状态 |- |O |O |- |O |- |Ø |O |- |O |O | |
| //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | ||
| 行 13: | 行 13: | ||
| ===== 题解 ===== | ===== 题解 ===== | ||
| + | |||
| + | ==== B - Binary Vector ==== | ||
| + | |||
| + | 求 $n$ 个 $n$ 维 $01$ 向量线性无关的概率。 | ||
| + | |||
| + | 找到分子的通项 $2^{\frac {n(n-1)}2} \prod_{i=1}^n(2^i-1)$，线性的 $dp$ 一下求出来。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #pragma GCC optimize(2) | ||
| + | #pragma GCC optimize(3,"Ofast","inline") | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define db double | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e7+5; | ||
| + | const int M = 1e9+7; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s;} | ||
| + | |||
| + | int ans[maxn],inv2[maxn],s[maxn],s2[maxn]; | ||
| + | |||
| + | void init() | ||
| + | { | ||
| + | int n = 2e7; | ||
| + | |||
| + | inv2[1] = qpow(2,M-2); | ||
| + | rep(i,2,n){ | ||
| + | inv2[i] = 1LL*inv2[i-1]*inv2[1]%M; | ||
| + | } | ||
| + | rep(i,2,n){ | ||
| + | inv2[i] = 2LL*inv2[i-1]%M*inv2[i]%M*inv2[i]%M; | ||
| + | } | ||
| + | |||
| + | |||
| + | ll pow2 = 1; | ||
| + | s[0] = s2[0] = 1; | ||
| + | rep(i,1,n) { | ||
| + | s[i] = 1LL * s[i-1] * pow2 % M; | ||
| + | pow2 = 2LL * pow2%M; | ||
| + | |||
| + | s2[i] = 1LL * s2[i-1] * (pow2-1)%M; | ||
| + | } | ||
| + | |||
| + | |||
| + | rep(i,1,n){ | ||
| + | ans[i] = 1LL * s[i] * s2[i] % M * inv2[i] % M; | ||
| + | } | ||
| + | rep(i,2,n) ans[i] ^= ans[i-1]; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio();init(); | ||
| + | int _; | ||
| + | for(cin>>_;_;_--){ int n; | ||
| + | cin>>n; | ||
| + | cout<<ans[n]<<endl; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== C - Combination of Physics and Maths ==== | ||
| + | |||
| + | 定义一个矩阵的压强是矩阵和除以最下面一行的和，现在要从一个矩阵中取一个子矩阵使得这个矩阵的压强最大。 | ||
| + | |||
| + | 首先我们可以意识到，如果取了$a_{i,j}$作为底中的一个元素，那么取$a_{1…i-1,j}$一定是更最优的，我们考虑两个单列矩阵，如果一列的压强是$a$,另一列的压强是$b$，且$a>b$,那么把后一列加入第一列一定会使压强变小，所以最优的应该是某个元素到顶的。预处理前缀和然后枚举底就行了。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #pragma GCC optimize(2) | ||
| + | #pragma GCC optimize(3,"Ofast","inline") | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define db double | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e7+5; | ||
| + | const int M = 1e9+7; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s;} | ||
| + | |||
| + | int ans[maxn],inv2[maxn],s[maxn],s2[maxn]; | ||
| + | |||
| + | void init() | ||
| + | { | ||
| + | int n = 2e7; | ||
| + | |||
| + | inv2[1] = qpow(2,M-2); | ||
| + | rep(i,2,n){ | ||
| + | inv2[i] = 1LL*inv2[i-1]*inv2[1]%M; | ||
| + | } | ||
| + | rep(i,2,n){ | ||
| + | inv2[i] = 2LL*inv2[i-1]%M*inv2[i]%M*inv2[i]%M; | ||
| + | } | ||
| + | |||
| + | |||
| + | ll pow2 = 1; | ||
| + | s[0] = s2[0] = 1; | ||
| + | rep(i,1,n) { | ||
| + | s[i] = 1LL * s[i-1] * pow2 % M; | ||
| + | pow2 = 2LL * pow2%M; | ||
| + | |||
| + | s2[i] = 1LL * s2[i-1] * (pow2-1)%M; | ||
| + | } | ||
| + | |||
| + | |||
| + | rep(i,1,n){ | ||
| + | ans[i] = 1LL * s[i] * s2[i] % M * inv2[i] % M; | ||
| + | } | ||
| + | rep(i,2,n) ans[i] ^= ans[i-1]; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio();init(); | ||
| + | int _; | ||
| + | for(cin>>_;_;_--){ int n; | ||
| + | cin>>n; | ||
| + | cout<<ans[n]<<endl; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| + | |||
| + | |||
| + | ==== E - Easy Construction ==== | ||
| + | |||
| + | 给一个数字 $k$，要构造一个 $1-n$ 的排列，满足对于 $i \in [1,n]$ 都存在一个长度为 $i$ 子串，使得这个子串内数字的和模 $n$ 等于 $k$。 | ||
| + | |||
| + | 首先考虑 $i=n$的情况，得出结论 $n$ 为偶数时，$k=\frac n2$才有解，否则 $k=0$ 才有解。然后再考虑如何构造，当 $n$ 为偶数时，把 $n$ 和 $k$ 放最左边，然后依次从右边加入 $i,n-i$。当 $n$ 为奇数时，先在最左边放 $n$ 然后依次放入$i,n-i$。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define db double | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 5e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | int n,k; | ||
| + | cin>>n>>k; | ||
| + | if(n%2==0){ | ||
| + | if(k!=n/2) cout<<-1<<endl; | ||
| + | else{ | ||
| + | cout<<n<<" "<<k<<" "; | ||
| + | rep(i,1,k-1) cout<<i<<" "<<n-i<<" "; | ||
| + | cout<<endl; | ||
| + | } | ||
| + | }else{ | ||
| + | if(k) cout<<-1<<endl; | ||
| + | else{ | ||
| + | cout<<n; | ||
| + | rep(i,1,n/2) cout<<" "<<i<<" "<<n-i; | ||
| + | cout<<endl; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== G - Grid Coloring ==== | ||
| + | |||
| + | $n\times n$ 方格框架涂色， $k$ 种颜色出现次数相等，构造一种方案使得每一行每一列都有至少两种颜色，且同色的边不构成环。 | ||
| + | |||
| + | 从上到下从左到右按 $1$ 到 $k$ 循环填就好了。 | ||
| + | |||
| + | {{:2020-2021:teams:wangzai_milk:2020nowcoder6-1.png?400|}} | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii pair<int,int> | ||
| + | #define mp make_pair | ||
| + | using namespace std; | ||
| + | const int N=205; | ||
| + | int r[N][N],c[N][N]; | ||
| + | int main() | ||
| + | { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | while(t--) | ||
| + | { | ||
| + | |||
| + | int n,k; | ||
| + | scanf("%d%d",&n,&k); | ||
| + | if(k==1||n==1||2*(n+1)*n%k){printf("-1\n");continue;} | ||
| + | int res=0; | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | for(int j=1;j<=n;j++)r[i][j]=res,res=(res+1)%k; | ||
| + | for(int j=1;j<=n+1;j++)c[j][i]=res,res=(res+1)%k; | ||
| + | } | ||
| + | for(int i=1;i<=n;i++)r[n+1][i]=res,res=(res+1)%k; | ||
| + | for(int i=1;i<=n+1;i++) | ||
| + | { | ||
| + | for(int j=1;j<=n;j++)printf("%d ",c[i][j]+1); | ||
| + | puts(""); | ||
| + | } | ||
| + | for(int i=1;i<=n+1;i++) | ||
| + | { | ||
| + | for(int j=1;j<=n;j++)printf("%d ",r[i][j]+1); | ||
| + | puts(""); | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== H - Harmony Pairs ==== | ||
| + | |||
| + | 数位dp。状态记录一下数位和差值、 $A\le B$ 的限制和 $B\le N$ 的限制即可。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #pragma GCC optimize(2) | ||
| + | #pragma GCC optimize(3,"Ofast","inline") | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | const int N=105; | ||
| + | const ll mod=1e9+7; | ||
| + | char s[N]; | ||
| + | ll dp[N][2005][2][2]; | ||
| + | ll dfs(int dep,int d,bool lim1,bool lim2) | ||
| + | { | ||
| + | if(dep>=strlen(s))return (d>0); | ||
| + | if(dp[dep][d+900][lim1][lim2]!=-1) return dp[dep][d+900][lim1][lim2]; | ||
| + | dp[dep][d+900][lim1][lim2] = 0; | ||
| + | for(int i=0;i<10;i++) | ||
| + | for(int j=0;j<10;j++) | ||
| + | { | ||
| + | if(lim2&&j>s[dep]-'0')continue; | ||
| + | if(lim1&&i>j)continue; | ||
| + | dp[dep][d+900][lim1][lim2]+=dfs(dep+1,d+i-j,lim1&&(i==j),lim2&&(j==s[dep]-'0')); | ||
| + | dp[dep][d+900][lim1][lim2]%=mod; | ||
| + | } | ||
| + | return dp[dep][d+900][lim1][lim2]; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | memset(dp,-1,sizeof(dp)); | ||
| + | scanf("%s",s); | ||
| + | printf("%lld\n",dfs(0,0,1,1)); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== J - Josephus Transform ==== | ||
| + | |||
| + | 对排列 $1,2,3,\cdots,n$ 做 $m$ 次操作。每次操作是进行 $x$ 次 $k$ 约瑟夫问题。求最后的排列。 | ||
| + | |||
| + | 把操作看成置换，如果已知一次 $k$ 约瑟夫问题的置换，那么可以用类似快速幂的方法在 $nmlogx$ 得到答案。考虑如何求一次 $k$ 约瑟夫问题的置换，用线段树暴力模拟就行，复杂度为 $nmlogn$。所以总复杂度$nm(logn + logx)$ | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define db double | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 1e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | int a[maxn],n,b[maxn],tmp[maxn]; | ||
| + | int tr[maxn<<2]; | ||
| + | void build(int id,int l,int r) | ||
| + | { | ||
| + | tr[id] = 0; | ||
| + | if(l==r) {tr[id]=1;return ;} | ||
| + | int mid = (l+r)>>1; | ||
| + | build(id<<1,l,mid);build(id<<1|1,mid+1,r); | ||
| + | tr[id] = tr[id<<1] + tr[id<<1|1]; | ||
| + | } | ||
| + | void update(int id,int stl,int str,int pos) | ||
| + | { | ||
| + | if(stl==str){ | ||
| + | tr[id] = 0; | ||
| + | return ; | ||
| + | } | ||
| + | int mid = (stl+str)>>1; | ||
| + | if(pos<=mid) update(id<<1,stl,mid,pos); | ||
| + | else update(id<<1|1,mid+1,str,pos); | ||
| + | tr[id] = tr[id<<1] + tr[id<<1|1]; | ||
| + | } | ||
| + | int query(int id,int stl,int str,int l,int r) | ||
| + | { | ||
| + | if(stl==l && str==r){ | ||
| + | return tr[id]; | ||
| + | } | ||
| + | int mid = (stl+str)>>1; | ||
| + | if(r<=mid) return query(id<<1,stl,mid,l,r); | ||
| + | else if(l>mid) return query(id<<1|1,mid+1,str,l,r); | ||
| + | else return query(id<<1,stl,mid,l,mid) + query(id<<1|1,mid+1,str,mid+1,r); | ||
| + | } | ||
| + | int query2(int id,int l,int r,int k) | ||
| + | { | ||
| + | if(l==r) return l; | ||
| + | int mid = (l+r)>>1; | ||
| + | if(tr[id<<1]>=k) return query2(id<<1,l,mid,k); | ||
| + | else return query2(id<<1|1,mid+1,r,k-tr[id<<1]); | ||
| + | } | ||
| + | void perm(int *a,int *b,int x) | ||
| + | { | ||
| + | while(x){ | ||
| + | if(x&1){ | ||
| + | rep(i,1,n) tmp[i] = a[b[i]]; | ||
| + | rep(i,1,n) a[i] = tmp[i]; | ||
| + | } | ||
| + | rep(i,1,n) tmp[i] = b[b[i]]; | ||
| + | rep(i,1,n) b[i] = tmp[i]; | ||
| + | x>>=1; | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); int m,k,x; | ||
| + | cin>>n>>m; | ||
| + | rep(i,1,n) a[i] = i; | ||
| + | while(m--){ | ||
| + | cin>>k>>x; | ||
| + | build(1,1,n); | ||
| + | int last = 0; | ||
| + | rep(i,1,n){ | ||
| + | int r = last==n?0:query(1,1,n,last+1,n); | ||
| + | if(r>=k){ | ||
| + | int pre = last?query(1,1,n,1,last):0; | ||
| + | b[i] = query2(1,1,n,k+pre); | ||
| + | update(1,1,n,b[i]); | ||
| + | last = b[i]; | ||
| + | }else{ | ||
| + | int tt = k - r; | ||
| + | tt %= (n-i+1); | ||
| + | if(tt == 0) tt = n-i+1; | ||
| + | b[i] = query2(1,1,n,tt); | ||
| + | update(1,1,n,b[i]); | ||
| + | last = b[i]; | ||
| + | } | ||
| + | } | ||
| + | perm(a,b,x); | ||
| + | } | ||
| + | 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; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
2020-2021/teams/wangzai_milk/20200727比赛记录.1595867220.txt.gz · 最后更改: 2020/07/28 00:27 由 wzx27
