CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_1 [2020/07/24 15:55]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_1 [2020/08/01 10:17] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:jxm2001:错题集_1被移动至2020-2021:teams:legal_string:jxm2001:other:错题集_1
@@ 行 21: / 行 21: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=5005;
 int a[MAXN][MAXN],b[MAXN][MAXN],que[MAXN];
@@ 行 141: / 行 94: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2e5+5;
 struct Edge{
@@ 行 290: / 行 196: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2e5+5;
 int a[MAXN],dp[MAXN];
@@ 行 377: / 行 236: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
 int a[MAXN],vis[MAXN],pos[MAXN],cyc_cnt;
@@ 行 497: / 行 309: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXP=2e5+20;
 bool vis[MAXP],vis2[MAXP];
@@ 行 647: / 行 412: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2e5+5,Inf=1e9;
 set<int> low[MAXN<<2];
@@ 行 777: / 行 495: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2e6+5;
 char buf[MAXN];
@@ 行 837: / 行 508: @@
 		else
 		pos=(pos+len+x)%len;
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 8、Fraction Constructive Problem =====
+[[https://ac.nowcoder.com/acm/contest/5668/F|链接]]
+==== 题意 ====
+若干询问，每次询问给定 $a,b(1\le a,b\le 2\times 10^6)$，要求构造 $1\le c,d,e,f\le 4\times 10^{12}$。
+构造需要满足 $d,f\lt b$ 或 $\frac cd-\frac ef=\frac ab$。
+==== 题解 ====
+情况 $1$:$(a,b)\gt 1$
+记 $a'=\frac a{(a,b)},b'=\frac b{(a,b)}$，令 $c=a'+1,d=b',e=1,f=b'$ 即可。
+情况 $2$:$(a,b)== 1$ 且 $b\neq p^\alpha$
+令 $b=df$ 且 $(d,f)=1$，根据裴蜀定理和拓展欧几里得算法，可以找到 $fx+dy=1$。
+于是有 $\frac xd+\frac yf=\frac 1b$，令 $c=ax,e=ay$ 即可，需要注意调整负号。
+关于 $b=df$ 中合适的 $d,f$ 的寻找，可以提前线性筛记录每个数最小素因子，令 $d$ 为 $b$ 最小素因子的幂次。
+情况 $3$:$(a,b)== 1$ 且 $b= p^\alpha$(包括 $b=1$)
+该情况无解，因为 $\frac cd-\frac ef$ 的分母为 $\text{lcm}(d,f)$ 的因子，而由于 $d,f\lt b$ 且 $b= p^\alpha$，必有 $\text{lcm}(d,f)$ 中 $p$ 因子幂次小于 $b$。
+<hidden 查看代码>
+<code cpp>
+const int MAXP=2e6+5;
+int vis[MAXP],prime[MAXP],cnt;
+void Prime(){
+	vis[1]=1;
+	_for(i,2,MAXP){
+		if(!vis[i])prime[cnt++]=i,vis[i]=i;
+		for(int j=0;j<cnt&&i*prime[j]<MAXP;j++){
+			vis[i*prime[j]]=prime[j];
+			if(i%prime[j]==0) break;
+		}
+	}
+}
+LL gcd(LL a,LL b){
+	while(b){
+		LL t=b;
+		b=a%b;
+		a=t;
+	}
+	return  a;
+}
+LL exgcd(LL a,LL b,LL &tx,LL &ty){
+	if(b==0){
+		tx=1,ty=0;
+		return a;
+	}
+	LL re=exgcd(b,a%b,ty,tx);
+	ty-=a/b*tx;
+	return re;
+}
+int main()
+{
+	int t=read_int();
+	Prime();
+	while(t--){
+		int a=read_int(),b=read_int();LL c,d,e,f,temp;
+		if((temp=gcd(a,b))>1){
+			d=f=b/temp;
+			e=1;
+			c=a/temp+1;
+		}
+		else{
+			d=1,f=b;
+			while(f!=1&&f%vis[b]==0)
+			d*=vis[b],f/=vis[b];
+			if(f==1){
+				puts("-1 -1 -1 -1");
+				continue;
+			}
+			exgcd(f,d,c,e);
+			if(c<0)
+			swap(c,e),swap(d,f);
+			e=-e;
+			c*=a,e*=a;
+		}
+		printf("%lld %lld %lld %lld\n",c,d,e,f);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 9、Operation on a Graph =====
+[[https://ac.nowcoder.com/acm/contest/5668/G|链接]]
+==== 题意 ====
+给定一个图，图中点 $i$ 初始颜色为 $i$。
+每次选择一种颜色的点进行操作，每次操作将与该颜色相邻的点所属颜色的所有点染成该颜色。(如果所选颜色不存在则忽略操作)
+问经过若干次操作后所有点最终的颜色。
+==== 题解 ====
+并查集维护颜色，链表维护与每种颜色节点相连的节点，每个节点最多向外合并一次，于是每个链表节点最多遍历一次，线性复杂度。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=8e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],tail[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	if(!head[u])tail[u]=edge_cnt;
+	head[u]=edge_cnt;
+}
+int p[MAXN];
+int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+int main()
+{
+	int t=read_int();
+	while(t--){
+		int n=read_int(),m=read_int(),u,v;
+		_for(i,0,n)
+		p[i]=i,head[i]=tail[i]=0;
+		while(m--){
+			u=read_int(),v=read_int();
+			Insert(u,v);Insert(v,u);
+		}
+		int q=read_int();
+		while(q--){
+			u=read_int();
+			if(Find(u)!=u)
+			continue;
+			int temp_head=0,temp_tail=0;
+			for(int i=head[u];i;i=edge[i].next){
+				v=Find(edge[i].to);
+				if(v==u)continue;
+				edge[tail[v]].next=temp_head;
+				if(!temp_head)temp_tail=tail[v];
+				temp_head=head[v];
+				p[v]=u;
+			}
+			head[u]=temp_head;tail[u]=temp_tail;
+		}
+		_for(i,0,n)
+		space(Find(i));
+		puts("");
 	}
 	return 0;

CVBB ACM Team

用户工具

站点工具

页面工具