CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/28 16:10]
zars19
+++ 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	|
-^状态 	|- 	|O 	|O 	|- 	|O 	|O 	|Ø 	|O 	|-	|O	|O	|
+^状态 	|- 	|O 	|O 	|- 	|O 	|- 	|Ø 	|O 	|-	|O	|O	|
 //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
@@ 行 88: / 行 88: @@
 </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 ====
@@ 行 208: / 行 284: @@
 {
     if(dep>=strlen(s))return (d>0);
-    if(dp[dep][d][lim1][lim2]!=-1)return dp[dep][d][lim1][lim2];
+    if(dp[dep][d+900][lim1][lim2]!=-1) return dp[dep][d+900][lim1][lim2];
-    dp[dep][d][lim1][lim2]=0;
+    dp[dep][d+900][lim1][lim2] = 0;
     for(int i=0;i<10;i++)
     for(int j=0;j<10;j++)
@@ 行 215: / 行 291: @@
         if(lim2&&j>s[dep]-'0')continue;
         if(lim1&&i>j)continue;
-        dp[dep][d][lim1][lim2]+=dfs(dep+1,d+i-j,lim1&&(i==j),lim2&&(j==s[dep]-'0'));
+        dp[dep][d+900][lim1][lim2]+=dfs(dep+1,d+i-j,lim1&&(i==j),lim2&&(j==s[dep]-'0'));
-        dp[dep][d][lim1][lim2]%=mod;
+        dp[dep][d+900][lim1][lim2]%=mod;
     }
-    return dp[dep][d][lim1][lim2];
+    return dp[dep][d+900][lim1][lim2];
 }
 int main()
@@ 行 335: / 行 411: @@
     }
     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>
 \\

CVBB ACM Team

用户工具

站点工具

页面工具