差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/14 20:31]
zars19 [比赛总结与反思]
+++ 2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/16 15:16] (当前版本)
wzx27
@@ 行 319: / 行 319: @@
     printf("%lld\n",ans);
     return 0;
+}
+</code> </hidden>
+\\
+==== E - Exclusive OR ====
+如果可以猜到结论/想到结论/打表观察可以发现对于$20\leq i$的$ans_i=ans_{i-2}$
+那么就可以对于$i\leq 20$的时候fwt计算结果，其余的递推即可。
+<hidden code> <code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+const int N = 1<<18;
+const int M = 2e5+5;
+typedef long long ll;
+int n,nans[N],one[N],ans[M];
+void FWT(int *src) {
+    for (int sz = 2;sz <= N;sz<<=1) {
+        int step = sz >> 1;
+        for (int i = 0;i< N;i+=sz) {
+            for (int j = i;j < i+step;j++) {
+                int a = src[j],b = src[j+step];
+                src[j] = a+b;
+                src[j+step] = a-b;
+            }
+        }
+    }
+}
+void IFWT(int *src) {
+    for (int sz = 2;sz <= N;sz<<=1) {
+        int step = sz >> 1;
+        for (int i = 0;i < N;i+=sz) {
+            for (int j = i;j<i+step;j++) {
+                int a = src[j],b = src[j+step];
+                src[j] = (a+b) >> 1;
+                src[j+step] = (a-b)>>1;
+            }
+        }
+    }
+}
+int main()
+{
+    scanf("%d",&n);
+    int x;
+    for (int i = 1;i<= n;i++) {
+        scanf("%d",&x);
+        one[x]=1;
+        nans[x]=1;
+        if (x > ans[1]) ans[1] = x;
+    }
+    FWT(one);
+    for (int i = 2;i<= 20;i++) {
+        FWT(nans);
+        for (int j = 0;j < N;j++)
+            nans[j] = nans[j]*one[j];
+        IFWT(nans);
+        for (int j = 0;j < N;j++)
+            if (nans[j])
+                nans[j] = 1;
+        for (int j = N-1;j>=0;j--)
+            if (nans[j]) {
+                ans[i] = j;
+                break;
+            }
+    }
+    for (int i = 21;i<= n;i++)
+        ans[i] = ans[i-2];
+    for (int i = 1;i<= n;i++)
+        printf("%d ",ans[i]);
 }
 </code> </hidden>
@@ 行 438: / 行 508: @@
 }
 </code> </hidden>
+\\
+==== H - Happy Triangle ====
+题意：维护一个multiset，三种操作：添加删除查询。查询是查询对于x，multiset中是否存在两条边可以和其组成三角形。
+分两种情况讨论，第一种情况是询问的边是最大的边，第二种情况是非最大边。对于最大边的情况可以发现找小于x的最大的两条边即可，这一部分直接用multiset就能维护。对于非最大边时，假设能组成三角形的另外两条边是a和b，那么一定有$x < b$且$b-a < x$，可以发现对于一个b，肯定是选择前驱作为a时$b-a$最小，所以我们需要做的就是写一个数据结构，使得可以维护当前点减去前驱点的后缀最小值。仝multiset+离散化+线段树可以做到这一操作。
+<hidden><code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+const int N = 2e5+5;
+const int INF = 2e9+5;
+int tr[N<<2],id[N];
+struct Node {
+	int op,val;
+}qur[N];
+void Build(int p,int l,int r) {
+	if (l==r) {
+		tr[p] = INF;
+		return ;
+	}
+	int mid = (l+r)>>1;
+	Build(p<<1,l,mid);
+	Build(p<<1|1,mid+1,r);
+	tr[p] = min(tr[p<<1],tr[p<<1|1]);
+}
+void Update(int p,int l,int r,int a,int b) {
+	if (l==r) {
+		tr[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);
+	tr[p] = min(tr[p<<1],tr[p<<1|1]);
+}
+int Getans(int p,int l,int r,int a,int b) {
+	if (l>=a&&r<=b) {
+		return tr[p];
+	}
+	int mid = (l+r)>>1;
+	int ans = INF;
+	if (a<=mid) ans = min(ans,Getans(p<<1,l,mid,a,b));
+	if (b>mid) ans = min(ans,Getans(p<<1|1,mid+1,r,a,b));
+	return ans;
+}
+multiset<int> MS;
+int c[N];
+int main()
+{
+	MS.insert(-1);MS.insert(-1);MS.insert(INF);
+	int q;
+	scanf("%d",&q);
+	for (int i = 1;i<= q;i++) {
+		scanf("%d%d",&qur[i].op,&qur[i].val);
+		id[i] = qur[i].val;
+	}
+	sort(id+1,id+q+1);
+	int cnt = unique(id+1,id+q+1)-id-1;
+	Build(1,1,cnt);
+	for (int i = 1;i<= q;i++) {
+		int x = qur[i].val;
+		int pos = lower_bound(id+1,id+cnt+1,x)-id;
+		if (qur[i].op == 1) {
+			MS.insert(x);
+			c[pos]++;
+			if (c[pos] == 2) {
+				Update(1,1,cnt,pos,0);
+			} else if (c[pos] == 1) {
+				Update(1,1,cnt,pos,(*MS.upper_bound(x))-x);
+				auto it = MS.lower_bound(x);
+				it--;
+				int pre = *it;
+				int prepos = lower_bound(id+1,id+cnt+1,pre)-id;
+				if (c[prepos] == 1)Update(1,1,cnt,prepos,x-pre);
+			}
+		} else if(qur[i].op == 2) {
+			MS.erase(MS.find(x));
+			c[pos]--;
+			if (c[pos] == 1) Update(1,1,cnt,pos,(*MS.upper_bound(x))-x);
+			else if (c[pos] == 0) {
+				Update(1,1,cnt,pos,INF);
+				auto it = MS.lower_bound(x);
+				it--;
+				int pre = *it;
+				int prepos = lower_bound(id+1,id+cnt+1,pre)-id;
+				if (c[prepos] == 1)Update(1,1,cnt,prepos,(*MS.lower_bound(x))-pre);
+			}
+		} else {
+			bool flag = false;
+			auto it = MS.lower_bound(x);
+			int t1 = *it;
+			int t2 = *(--it);
+			int t3 = *(--it);
+			if (t2+t3>x || t2+x>t1)flag = true;
+			if (Getans(1,1,cnt,pos,cnt) < x) flag = true;
+			if (flag)printf("Yes\n");
+			else printf("No\n");
+		}
+	}
+	return 0;
+}
+</code></hidden>
 \\
@@ 行 526: / 行 698: @@
 }
 </code></hidden>
+\\
+==== J - Just Shuffle ====
+给一个置换 $A$ 和大质数 $k$，求置换 $P$ 使得 $P^k = A$。
+求出 $A$ 的每个循环节，因为 $k$ 是个大质数，所以 $P$ 每个循环节作 $k$ 次方都不会分裂，于是 $P$ 的循环节和 $A$ 的循环节是一样的，只是向右平移了 $k$ 对循环节长度的逆元个长度。
+<hidden code> <code cpp>
+#include<bits/stdc++.h>
+#define ALL(x) (x).begin(),(x).end()
+#define ll long long
+#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 pg PermutationGroup
+#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);}
+inline ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
+inline ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
+ll extgcd(ll a,ll b,ll& u,ll& v)
+{
+    ll d;
+    if(b==0){
+        d = a;
+        u=1,v=0;
+    }else {
+        d = extgcd(b,a%b,v,u);
+        v -= a/b*u;
+    }return d;
+}
+int n,k,vis[maxn];
+int P[maxn],ans[maxn],a[maxn],tmp[maxn],ttt[maxn];
+int main()
+{
+    //fastio();
+    scanf("%d%d",&n,&k);
+    rep(i,1,n) scanf("%d",&a[i]);
+    rep(i,1,n)if(!vis[i]){
+        vis[i] = 1;
+        vector<int> pos;
+        int u = a[i],len = 1;pos.pb(i);
+        while(u!=i){
+            len++;
+            vis[u] = 1;pos.pb(u);
+            u = a[u];
+        }
+        ll x,y;
+        extgcd(k,len,x,y);
+        x = (x%len+len)%len;
+        rep(i,1,len){
+            ans[pos[i-1]] = pos[(i-1+x)%len];
+        }
+    }
+    rep(i,1,n) printf("%d ",ans[i]);
+    return 0;
+}
+</code> </hidden>
 \\
 ==== K - Keyboard Free ====
@@ 行 572: / 行 812: @@
 ===== 比赛总结与反思 =====
-感觉这场题蛮正常的（m(就是隐约觉得都可做，然而没做对）。这种场的要义是不是不能陷入僵局quq（卡题乃正常场之大忌），好几道没怎么看的题后来发现可能更值得入手？——Zars19
+补完了！感觉这场题蛮正常的（m(就是隐约觉得都可做，然而没做对）。这种场的要义是不是不能陷入僵局quq（卡题乃正常场之大忌），好几道没怎么看的题后来发现可能更值得入手？啊下周加油。——Zars19
+C题一开始想错了耽误了一些时间，想到了对的实现还很艰难呜呜呜呜该多写难题代码了。FWT这个有点可惜，感觉要多做一些FWT题了。 ——Infinity37
+和上一场一样都是一个题卡了几个小时？（以后要试着跳出来。 ——_wzx27

CVBB ACM Team

用户工具

站点工具

差别

页面工具