CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/14 13:35]
zars19 [题解]
+++ 2020-2021:teams:wangzai_milk:20200713比赛记录 [2020/07/16 15:16] (当前版本)
wzx27
@@ 行 4: / 行 4: @@
 ^题号 	^A 	^B 	^C 	^D 	^E 	^F 	^G 	^H 	^I 	^J	^K      |
-^状态 	|- 	|Ø 	|O 	|O 	|- 	|O 	|Ø 	|- 	|-	|Ø	|Ø	|
+^状态 	|Ø 	|Ø 	|O 	|O 	|Ø 	|O 	|Ø 	|Ø 	|Ø	|Ø	|Ø	|
 //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
@@ 行 142: / 行 142: @@
 </code></hidden>
 \\
+==== C - Cover the Tree ====
+题意：最少链覆盖树，输出方案。
+首先毫无疑问的是最少链数就是度数为1的节点数目加一除以二，方案的话，对于x的子树中度数为1的节点，如果目前未匹配的有奇数个，那么他们之间可以两两配对，然后留一个伸出去，从而覆盖x到其父亲的边，偶数个则要伸出去两个，这样贪心的输出方案即可。
+<hidden><code cpp>
+#include <stdio.h>
+#include <queue>
+#include <string.h>
+#include <stdlib.h>
+#include <algorithm>
+using namespace std;
+const int N = 2e5+5;
+int head[N],tot;
+int du[N];
+struct E
+{int nxt,to;}e[N<<1];
+void add(int x,int y) {
+	e[++tot].nxt = head[x];head[x] = tot;e[tot].to = y;
+	e[++tot].nxt = head[y];head[y] = tot;e[tot].to = x;
+}
+queue<int>sons[N];
+int anss[N][2],anscnt;
+void dfs(int x,int fa) {
+	bool isson = true;
+	int tomatch = 0;
+	for (int i = head[x];i;i=e[i].nxt)
+		if (e[i].to!=fa) {
+			dfs(e[i].to,x);
+			isson = false;
+			tomatch += sons[e[i].to].size();
+		}
+	if (isson) {
+		sons[x].push(x);
+	}
+	queue<int>son2,son1;
+	for (int i = head[x];i;i=e[i].nxt)
+		if (e[i].to!=fa) {
+			if (sons[e[i].to].size()==2)
+				son2.push(e[i].to);
+			else if (sons[e[i].to].size()==1)
+				son1.push(e[i].to);
+		}
+	if (son2.size()%2==1 && son1.size() == 0 && son2.size()!=1) {
+		int x1 = son2.front();son2.pop();
+		int x2 = son2.front();son2.pop();
+		int x3 = son2.front();son2.pop();
+		anss[anscnt+1][0] = sons[x1].front();sons[x1].pop();
+		anss[anscnt+1][1] = sons[x2].front();sons[x2].pop();
+		anss[anscnt+2][0] = sons[x1].front();sons[x1].pop();
+		anss[anscnt+2][1] = sons[x3].front();sons[x3].pop();
+		son1.push(x2);
+		son1.push(x3);
+		anscnt+=2;
+	}
+	while (son2.size()>=2) {
+		int x1 = son2.front();son2.pop();
+		int x2 = son2.front();son2.pop();
+		anss[anscnt+1][0] = sons[x1].front();sons[x1].pop();
+		anss[anscnt+1][1] = sons[x2].front();sons[x2].pop();
+		//anss[anscnt+2][0] = sons[x1].front();sons[x1].pop();
+		//anss[anscnt+2][1] = sons[x2].front();sons[x2].pop();
+		son1.push(x1);
+		son1.push(x2);
+		anscnt++;
+	}
+	while (son2.size()*2 + son1.size() > 2) {
+		if (son2.size()) {
+			int x1 = son2.front();son2.pop();
+			int x2 = son1.front();son1.pop();
+			anss[anscnt+1][0] = sons[x1].front();sons[x1].pop();
+			anss[anscnt+1][1] = sons[x2].front();sons[x2].pop();
+			son1.push(x1);
+			anscnt++;
+		} else {
+			int x1 = son1.front();son1.pop();
+			int x2 = son1.front();son1.pop();
+			anss[anscnt+1][0] = sons[x1].front();sons[x1].pop();
+			anss[anscnt+1][1] = sons[x2].front();sons[x2].pop();
+			anscnt++;
+		}
+	}
+	for (int i = head[x];i;i=e[i].nxt)
+		if (e[i].to!=fa) {
+			while (sons[e[i].to].size())
+			{
+				int tmp = sons[e[i].to].front();
+				sons[x].push(tmp);
+				sons[e[i].to].pop();
+			}
+		}
+}
+int main()
+{
+	int n;
+	scanf("%d",&n);
+	//printf("%d\n",n);
+	int x,y;
+	for (int i = 1;i< n;i++)
+	{
+		scanf("%d%d",&x,&y);
+		//printf("%d %d\n",x,y);
+		add(x,y);
+		du[x]++;du[y]++;
+	}
+	if (n==1) {
+		printf("1\n1 1\n");
+		return 0;
+	}
+	if (n==2) {
+		printf("1\n1 2\n");
+		return 0;
+	}
+	for (int i = 1;i<= n;i++)
+		if (du[i]!=1)
+		{
+			dfs(i,0);
+			if (sons[i].size()==2)
+			{
+				anscnt++;
+				anss[anscnt][0] = sons[i].front();
+				sons[i].pop();
+				anss[anscnt][1] = sons[i].front();
+			}
+			else {
+				anscnt++;
+				anss[anscnt][0] = sons[i].front();
+				anss[anscnt][1] = i;
+			}
+			break;
+		}
+	printf("%d\n",anscnt);
+	for (int i = 1;i<= anscnt;i++)
+		printf("%d %d\n",anss[i][0],anss[i][1]);
+	return 0;
+}
+</code></hidden>
+\\
 ==== D - Duration ====
@@ 行 180: / 行 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>
@@ 行 296: / 行 505: @@
     }
     cout<<ans<<endl;
+    return 0;
+}
+</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>
+\\
+==== I - Interval ====
+开局你有一个区间$[1,n]$，区间可以收缩和扩张，$[l,r]$和$[l+1,r]$、$[l,r]$和$[l,r-1]$间可以来回转换，但是到$l=r$时就不能再变了，所以不希望看到这种局面。给出$m$个限制，$l~r~dir~c$当$dir=L$时表示花费$c$可以限制$[l,r],[l+1,r]$之间的转换，$dir=R$时表示花费$c$可以限制$[l,r],[l,r-1]$之间的转换。问能够限制区间不可能变为$l=r$的最小花费。
+{{:2020-2021:teams:wangzai_milk:grid_graph.png?300|}}
+我们把区间看作坐标，显然这是一个从$(1,n)$到$y=x$的最小割。和狼抓兔子（BZOJ1001）比较像，网格图转对偶图求最短路即最小割，$O(n^2\log n)$
+<hidden><code cpp>
+#pragma GCC optimize(2)
+#pragma GCC optimize(3,"Ofast","inline")
+#include<bits/stdc++.h>
+#define pb push_back
+using namespace std;
+#define ll long long
+#define INF 0x3f3f3f3f3f3f3f3f
+#define pii pair<int,int>
+#define idx(x,y) ((x-1)*(n-1)+y)
+#define mp make_pair
+const int N=505;
+int n,m,s,t,head[N*N],tot=0,done[N*N];
+ll dis[N*N];
+struct Node
+{
+	int nxt,to;ll w;
+	Node(int nxt=0,int to=0,ll w=0):nxt(nxt),to(to),w(w){}
+}edges[N*N*10];
+struct Node1
+{
+	int u;ll d;
+	Node1(int u=0,ll d=0):u(u),d(d){}
+	bool operator < (const Node1 &a) const {return d>a.d;}
+};
+void addedge(int u,int v,ll w)
+{
+	edges[++tot]=Node(head[u],v,w);
+	head[u]=tot;
+}
+ll dij()
+{
+	priority_queue<Node1>q;
+	memset(dis,0x3f,sizeof(dis));
+	dis[s]=0,q.push(Node1(s,dis[s]));
+	while(!q.empty())
+	{
+		int u=q.top().u;q.pop();
+		if(done[u])continue;
+		done[u]=1;
+		for(int i=head[u];~i;i=edges[i].nxt)
+		{
+			int v=edges[i].to;
+			if(dis[v]>dis[u]+edges[i].w)
+			{
+				dis[v]=dis[u]+edges[i].w;
+				q.push(Node1(v,dis[v]));
+			}
+		}
+	}
+	return dis[t]==INF?-1:dis[t];
+}
+int main()
+{
+	memset(head,-1,sizeof(head));
+	scanf("%d%d",&n,&m);
+	s=0,t=(n-1)*(n-1)+1;
+	for(int i=1;i<=m;i++)
+	{
+		int l,r,c;char dir[2];
+		scanf("%d%d%s%d",&l,&r,dir,&c);
+		int id1,id2;
+		if(dir[0]=='L')
+		{
+			id1=idx(l,r),id2=idx(l,r-1);
+			if(r==n)id1=s;
+		}
+		else
+		{
+			id2=idx(l-1,r-1),id1=idx(l,r-1);
+			if(l==1)id2=t;
+		}
+		addedge(id1,id2,c),addedge(id2,id1,c);
+	}
+	printf("%lld\n",dij());
+    return 0;
+}
+</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;
 }
@@ 行 345: / 行 812: @@
 ===== 比赛总结与反思 =====
+补完了！感觉这场题蛮正常的（m(就是隐约觉得都可做，然而没做对）。这种场的要义是不是不能陷入僵局quq（卡题乃正常场之大忌），好几道没怎么看的题后来发现可能更值得入手？啊下周加油。——Zars19
+C题一开始想错了耽误了一些时间，想到了对的实现还很艰难呜呜呜呜该多写难题代码了。FWT这个有点可惜，感觉要多做一些FWT题了。 ——Infinity37
+和上一场一样都是一个题卡了几个小时？（以后要试着跳出来。 ——_wzx27

CVBB ACM Team

用户工具

站点工具

页面工具