CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200727比赛记录 [2020/07/28 00:40]
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	|
-^状态 	|- 	|O 	|O 	|- 	|O 	|O 	|Ø 	|O 	|-	|O	|O	|
+^状态 	|- 	|O 	|O 	|- 	|O 	|- 	|Ø 	|O 	|-	|O	|O	|
 //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
@@ 行 18: / 行 18: @@
 求 $n$ 个 $n$ 维 $01$ 向量线性无关的概率。
-$\text{OEIS}$ 找到分子的通项 $2^{\frac {n(n-1)}2} \prod_i=1^n(2^i-1)$，线性的 $dp$ 一下求出来。
+找到分子的通项 $2^{\frac {n(n-1)}2} \prod_{i=1}^n(2^i-1)$，线性的 $dp$ 一下求出来。
 <hidden code> <code cpp>
@@ 行 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 ====
@@ 行 140: / 行 216: @@
 }
 </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>
 \\
@@ 行 250: / 行 414: @@
 }
 </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

用户工具

站点工具

页面工具