差别

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

--- 2020-2021:teams:wangzai_milk:20200513比赛记录 [2020/05/20 21:27]
zars19
+++ 2020-2021:teams:wangzai_milk:20200513比赛记录 [2020/06/08 14:23] (当前版本)
wzx27
@@ 行 2: / 行 2: @@
 ===== 比赛情况 =====
+^题号 	^A 	^B 	^C 	^D 	^E 	^F 	^G 	^H 	^I 	^J 	^K 	^L 	^M	|
+^状态 	|Ø 	|O 	|- 	|O 	|O 	|Ø 	|- 	|- 	|Ø	|-	|-	|Ø	|Ø	|
+//O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试//
 **比赛时间**
@@ 行 22: / 行 28: @@
 ===== 题解 =====
+==== A-Blank ====
+补题 by Zars19
+code:[[HDU6578]]
+一个长度为$N$的序列被数字$\{0,1,2,3\}$填充，有$M$个限制条件，限制区间$[l_i,r_i]$中有$x_i$种不同数字。求方案数
+题解：DP，用$f[i][j][k][l](i\geq j\geq k\geq l)$四维分别记录数字最后一次出现的位置，obviously它可以向$f[i+1][j][k][l],f[i+1][i][k][l],f[i+1][i][j][l]$和$f[i+1][i][j][k]$转移。而限制条件在循环到每一个$i$时对$r=i$的条件进行处理（将不满足者清零）。考虑到空间限制使用滚动数组。
 ==== B-Operation ====
 solved by infinity37
@@ 行 496: / 行 511: @@
 </code>
+==== L-Sequence ====
+补题 by _wzx27
+把数列 $a_i$ 写成其生成函数的形式 $f(x)=\sum a_ix^i$，每个操作 $k$ 相当于 $f(x)\cdot \sum x^{ik}$，由交换律知顺序不重要，所以可以统计每种操作的次数 $m_i$，最后有
+$$f(x)\cdot (\sum x^{i})^{m_1} \cdot (\sum x^{2i})^{m_2} \cdot (\sum x^{3i})^{m_3}$$
+其中$(\sum x^{ki})^m = \sum {i+m-1 \choose m-1}x^{ik}$
+另外模数刚好是998244353，做三次NTT即可
+<hidden code>
+<code cpp>
+#include<bits/stdc++.h>
+#define ll 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 = 2e6+5;
+const ll M = 998244353;
+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 n,m,lim,l,r[maxn],cnt[maxn];
+ll A[maxn],B[maxn],fac[maxn],inv[maxn];
+int c[5];
+void NTT(ll a[],int type)
+{
+    rep(i,1,lim-1) if(i<r[i]) swap(a[i],a[r[i]]);
+    for(int mid=1;mid<lim;mid<<=1){
+        ll wn = qpow(3,(M-1)/mid/2);
+        if(type==-1) wn = qpow(wn,M-2);
+        for(int R=mid<<1,j=0;j<lim;j+=R){
+            ll w = 1;
+            for(int k=0;k<mid;k++,w=w*wn%M){
+                ll x=a[j+k],y=w*a[j+mid+k]%M;
+                a[j+k] = (x+y)%M;
+                a[j+mid+k] = (x-y+M)%M;
+            }
+        }
+    }
+    if(type==-1){
+        ll INV = qpow(lim,M-2);
+        rep(i,0,lim) a[i] = a[i]*INV%M;
+    }
+}
+ll Comb(ll a,ll b) {return a<b?0:fac[a]*inv[b]%M*inv[a-b]%M;}
+void init()
+{
+    fac[0] = 1;
+    rep(i,1,2000000) fac[i]=fac[i-1]*i%M;
+    inv[2000000] = qpow(fac[2000000],M-2);
+    per(i,2000000-1,0) inv[i]=inv[i+1]*(i+1)%M;
+}
+int main()
+{
+    fastio();
+    int _;
+    init();
+    for(cin>>_;_;_--){
+        cin>>n>>m;
+        memset(A,0,sizeof(A));
+        memset(B,0,sizeof(B));
+        rep(i,0,n-1) cin>>A[i];
+        lim=1,l=0;
+        while(lim<=2*n) lim<<=1,l++;
+        rep(i,0,lim-1) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));
+        cnt[1]=cnt[2]=cnt[3]=0;
+        while(m--) {int x;cin>>x;cnt[x]++;}
+        rep(i,1,3)if(cnt[i]){
+            memset(B,0,sizeof(B));
+            for(int j=0;j*i<n;j++) B[i*j] = Comb(cnt[i]+j-1,j);
+            NTT(A,1);NTT(B,1);
+            rep(i,0,lim) A[i] = A[i]*B[i]%M;
+            NTT(A,-1);
+            rep(i,n+1,lim) A[i]=0;
+        }
+        ll ans = 0;
+        rep(i,0,n-1) ans ^= ((i+1)*A[i]);
+        cout<<ans<<endl;
+    }
+    return 0;
+}
+</code>
+</hidden>
+==== M-Code ====
+补题 by Zars19
+[[http://acm.hdu.edu.cn/showproblem.php?pid=6590|M-Code]]
+code:
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<cstdlib>
+#include<cmath>
+#include<algorithm>
+#define LL long long
+#define INF 0x3f3f3f3f
+#define eps 1e-10
+using namespace std;
+const int N=105;
+int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+int dcmp(double x){return x<-eps?-1:(x>eps);}
+struct Point
+{
+	double x,y;
+	Point(double x=0,double y=0):x(x),y(y){}
+	Point operator + (Point a){return Point(x+a.x,y+a.y);}
+	Point operator - (Point a){return Point(x-a.x,y-a.y);}
+	Point operator * (double a){return Point(a*x,a*y);}
+	bool operator == (Point a){return dcmp(x-a.x)==0&&dcmp(y-a.y)==0;}
+}d1[N],d2[N],p;
+int top1,top2;
+typedef Point Vector;
+double sqr(double x){return x*x;}
+double Cross(Vector v1,Vector v2){return v1.x*v2.y-v1.y*v2.x;}
+double Dot(Vector v1,Vector v2){return v1.x*v2.x+v1.y*v2.y;}
+double dissqr(Point p1,Point p2){return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);}
+bool cmp(Point p1, Point p2)
+{
+	int u=dcmp(Cross(p1-p,p2-p));
+	return u>0||(u==0&&dcmp(dissqr(p1,p)-dissqr(p2,p))<0);
+}
+int Graham(Point *d,int n)
+{
+	int k=0;
+	for(int i=0;i<n;i++)
+	{
+		int u=dcmp(d[i].x-d[k].x);
+		int v=dcmp(d[i].y-d[k].y);
+		if(v<0||(v==0&&u<0))k=i;
+	}
+	p=d[k];
+	sort(d,d+n,cmp);
+	n=unique(d,d+n)-d;
+	if(n<=1)return n;
+	if(dcmp(Cross(d[n-1]-d[0],d[1]-d[0]))==0){d[1]=d[n-1];return 2;}
+	d[n++]=d[0];
+	int m=1;
+	for(int i=2;i<n;i++)
+	{
+		while(m>0&&dcmp(Cross(d[m]-d[m-1],d[i]-d[m-1]))<=0)m--;
+		d[++m]=d[i];
+	}
+	return m;
+}
+bool SegInter(Point p1,Point p2,Point p3,Point p4)
+{
+	if(max(p1.x,p2.x)<min(p3.x,p4.x))return 0;
+	if(max(p3.x,p4.x)<min(p1.x,p2.x))return 0;
+	if(max(p1.y,p2.y)<min(p3.y,p4.y))return 0;
+	if(max(p3.y,p4.y)<min(p1.y,p2.y))return 0;
+	int u=dcmp(Cross(p2-p1,p3-p1))*dcmp(Cross(p2-p1,p4-p1));
+	int v=dcmp(Cross(p4-p3,p1-p3))*dcmp(Cross(p4-p3,p2-p3));
+	return u<=0&&v<=0;
+}
+double TriS(Point p1,Point p2,Point p3){return fabs(Cross(p2-p1,p3-p1)/2);}
+bool InTri(Point p1,Point p2,Point p3,Point p0)
+{
+	double s1=TriS(p1,p2,p0),s2=TriS(p1,p3,p0),s3=TriS(p2,p3,p0),s=TriS(p1,p2,p3);
+	return dcmp(s-s1-s2-s3)==0;
+}
+int main()
+{
+	int T=read();
+	while(T--)
+	{
+		top1=top2=0;
+		int n=read();
+		for(int i=1;i<=n;i++)
+		{
+			int x1=read(),x2=read(),y=read();
+			if(y<0)d1[top1++]=Point(x1,x2);
+			else d2[top2++]=Point(x1,x2);
+		}
+		top1=Graham(d1,top1);
+		top2=Graham(d2,top2);
+		bool f=1;
+		for(int i=0;i<top1&&f;i++)
+		for(int j=0;j<top2&&f;j++)
+		if(SegInter(d1[i],d1[(i+1)%top1],d2[j],d2[(j+1)%top2]))f=0;
+		for(int i=0;i<top1&&f;i++)
+		for(int j=1;j<top2-1&&f;j++)
+			if(InTri(d2[0],d2[j],d2[j+1],d1[i]))f=0;
+		if(f)puts("Successful!");
+		else puts("Infinite loop!");
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
+给出一个集合，集合中元素是$(\boldsymbol{x_i},y_i)$，其中$\boldsymbol{x_i}$是一个$d$维向量，本题中$d=2$。$f(\boldsymbol{x})=sign(\sum^d_{i=1}w_i⋅x_i+b)=sign(\boldsymbol{w^T}⋅\boldsymbol{x}+b)$。问有没有一个向量$\boldsymbol{w}$可以使得所有$f(\boldsymbol{x_i})=y_i$。
+题解：这题读题好难。。其实是计算几何，判断凸包是否相交。$x_1w_1+x_2w_2+b=0$是二维平面上的一条直线，一侧使得$f(\boldsymbol{x_i})$为$1$，另一侧为$-1$。问题转化成有没有一条直线可以把两个点集分开，于是又等价于对两个点集求凸包判断是否相交。判断凸包相交可以$O(n^2)$做，先判两凸包上的边两两是否线段相交，再看一凸包中的每一个顶点是否在另一凸包内。
 ===== replay =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具