CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:牛客多校第三场 [2020/07/20 09:40]
great_designer [A]
+++ 2020-2021:teams:namespace:牛客多校第三场 [2020/07/23 21:28] (当前版本)
great_designer [A]
@@ 行 222: / 行 222: @@
 </hidden>
-=====A=====
+=====E=====
-<hidden>
+动态规划。图论那里的思考略微难一些，参见任韩《图论》第四章（？忘了第几章）第一节“对集”部分，有完全相同的例题和细节证明，因此对于数学竞赛生应当是小菜一碟。至于动态规划的部分只是熟练活。
-<code C>
-</code>
+注意不要手误。方程敲错了谁也救不了（……）。
-</hidden>
-=====A=====
+（适合作为算法课动态规划的压轴题之一——思维复杂度麻烦的类型）
+另外，本题改成C代码的qsort貌似就过不了了，会RE，不知为何。
 <hidden>
-<code C>
+<code C++>
+#include<stdio.h>
+#include<stdlib.h>
+#include<algorithm>
+using namespace std;
+int a[200005];
+int b[100005];
+int c[100005];
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		int i;
+		for(i=0;i<n;i++)
+		{
+			scanf("%d",&a[i]);
+		}
+		sort(a,a+n);
+		int tmp=a[n-1]-a[0];
+		int pmt=n/2-4;
+		b[0]=a[4]-a[3];
+		c[0]=0;
+		for(i=1;i<=pmt;i++)
+		{
+			b[i]=(b[i-2]>c[i-1]?b[i-2]:c[i-1])+(a[2*i+4]-a[2*i+3]);
+			c[i]=(b[i-1]>c[i-1]?b[i-1]:c[i-1]);
+		}
+		int mmm=(b[pmt]>c[pmt]?b[pmt]:c[pmt]);
+		tmp-=mmm;
+		printf("%lld\n",2*tmp);
+	}
+}
 </code>
 </hidden>
-=====A=====
+=====F=====
+解一次不定方程题目。注意后面情况讨论以及调整为正数的操作。
 <hidden>
 <code C>
+#include<stdio.h>
+char isprime[2000010];
+int sq[2000010];
+long long exgcd(long long a,long long b,long long *x,long long *y)
+{
+    if(!b)
+	{
+		(*x)=1;
+		(*y)=0;
+		return a;
+	}
+    long long r=exgcd(b,a%b,&(*x),&(*y)),t=(*x);
+    (*x)=(*y);
+	(*y)=t-a/b*(*y);
+    return r;
+}
+long long gcd(long long a,long long b)
+{
+    return (b==0)?a:gcd(b,a%b);
+}
+char cal(long long a,long long b,long long c,long long *x,long long *y)
+{
+    if(c%gcd(a,b)!=0)
+	{
+		return 0;
+	}
+    long long q=exgcd(a,b,&(*x),&(*y));
+    long long v=c/q;
+    (*x)*=v;
+	(*y)*=v;
+	(*y)*=-1;
+    return 1;
+}
+int main()
+{
+	isprime[0]=isprime[1]=1;
+	int i;
+	sq[1]=1;
+	for(i=2;i<=20000;i++)
+	{
+		if(!isprime[i])
+		{
+			int j;
+			for(j=i*i;j<=2000000;j+=i)
+			{
+				isprime[j]=1;
+			}
+		}
+		if(i*i<=2000005)
+		{
+			sq[i*i]=i;
+		}
+	}
+    for(i=1;i<2000005;i++)
+	{
+		if(!sq[i])
+		{
+			sq[i]=sq[i-1];
+		}
+	}
+    int T;
+    scanf("%d",&T);
+    while(T--)
+    {
+    	long long a,b;
+        scanf("%lld%lld",&a,&b);
+        if(b==1)
+		{
+			printf("-1 -1 -1 -1\n");
+		}
+        else if(a%b==0)
+        {
+            int x=a/b;
+            printf("%d 1 %d 1\n",x+1,1);
+        }
+        else if(!isprime[b])
+        {
+            printf("-1 -1 -1 -1\n");
+        }
+        else
+        {
+            int flag=1;
+            long long l,r;
+            for(l=2,r=sq[b]+2;l<=r+1;l++,r--)
+            {
+                if(l>=2&&l<b&&b%l==0)
+                {
+                    long long x=l,y=b/x,c,e;
+                    if(cal(y,x,a,&c,&e))
+                    {
+                        if(c<=0||e<=0)
+                        {
+                            if(c<=0&&e<=0)
+							{
+								printf("%lld %lld %lld %lld\n",-e+y,y,-c+x,x);
+							}
+                            else if(e<=0)
+                            {
+                                long long q=(-e)/y+2;
+                                printf("%lld %lld %lld %lld\n",c+x*q,x,e+y*q,y);
+                            }
+                        }
+                        else
+						{
+							printf("%lld %lld %lld %lld\n",c,x,e,y);
+						}
+                        flag=0;
+                        break;
+                    }
+                }
+                if(r>=2&&r<b&&b%r==0)
+                {
+                    long long x=r,y=b/x,c,e;
+                    if(cal(y,x,a,&c,&e))
+                    {
+                        if(c<=0||e<=0)
+                        {
+                            if(c<=0&&e<=0)
+							{
+								printf("%lld %lld %lld %lld\n",-e+y,y,-c+x,x);
+							}
+                            else if(e<=0)
+                            {
+                                long long q=(-e)/y+2;
+                                printf("%lld %lld %lld %lld\n",c+x*q,x,e+y*q,y);
+                            }
+                        }
+                        else
+						{
+							printf("%lld %lld %lld %lld\n",c,x,e,y);
+						}
+                        flag=0;
+                        break;
+                    }
+                }
+            }
+            if(flag)
+			{
+				printf("-1 -1 -1 -1\n");
+			}
+        }
+    }
+    return 0;
+}
 </code>
 </hidden>
-=====A=====
+=====L=====
+C语言优秀练习题。
 <hidden>
 <code C>
+#include<stdio.h>
+char a[105];
+int main()
+{
+    scanf("%s",a);
+    if((a[0]=='l'||a[0]=='L')&&(a[1]=='o'||a[1]=='O')&&(a[2]=='v'||a[2]=='V')&&(a[3]=='e'||a[3]=='E')&&(a[4]=='l'||a[4]=='L')&&(a[5]=='y'||a[5]=='Y'))
+	{
+        printf("lovely\n");
+    }
+    else
+    {
+        printf("ugly\n");
+    }
+    return 0;
+}
 </code>
 </hidden>
-=====A=====
+=====G=====
+以下是补题。
 <hidden>
-<code C>
+<code C++>
+#include<stdio.h>
+#include<stdlib.h>
+#include<vector>
+using namespace std;
+struct head
+{
+	struct head *r;
+	int val;
+};
+int dsu[1000000];
+int get(int v)
+{
+	if (v == dsu[v]) return v;
+	else return dsu[v] = get(dsu[v]);
+}
+pair<struct head*, struct head*> g[1000000];
+pair<struct head *, struct head *> merge(pair <struct head *, struct head *> a, pair <struct head *, struct head *> b)
+{
+	if (!a.second) return b;
+	else
+	{
+		a.second->r = b.first;
+		return make_pair(a.first, b.second);
+	}
+}
+pair <struct head*, struct head*> lst(int x)
+{
+	struct head *t =(struct head*)malloc(sizeof(struct head));
+	t->r=0;
+	t->val=x;
+	return make_pair(t,t);
+}
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n,m;
+		scanf("%d%d",&n,&m);
+		int i;
+		for(i = 0; i < n; i++)
+		{
+			dsu[i] = i;
+			g[i] =make_pair((struct head*)0,(struct head*)0);
+		}
+		for(i = 0; i < m; i++)
+		{
+			int x, y;
+			scanf("%d%d",&x,&y);
+			g[x] = merge(g[x], lst(y));
+			g[y] = merge(g[y], lst(x));
+		}
+		int q;
+		scanf("%d",&q);
+		for(i = 0; i < q; i++)
+		{
+			int c;
+			scanf("%d",&c);
+			if (get(c) != c)
+			{
+				continue;
+			}
+			else
+			{
+				vector<int> ord;
+				struct head *s;
+				for(s = g[c].first; s != 0; s = s->r)
+				{
+					int z = s->val;
+					if (get(z) != c)
+					{
+						int who = get(z);
+						dsu[who] = c;
+						ord.push_back(who);
+					}
+				}
+				g[c] =make_pair((struct head*)0,(struct head*)0);
+				vector<int>::iterator p;
+				for(p=ord.begin();p!=ord.end();p++)
+				{
+					g[c] = merge(g[c],g[(*p)]);
+				}
+			}
+		}
+		for(i = 0; i < n; i++)
+		{
+			printf("%d ",get(i));
+		}
+		printf("\n");
+	}
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具