250:
首先先特判答案不存在的情况.
再设答案为k,则B[k+1,n]是A的一个子序列,所以,
做法1,枚举k检查子序列是否成立;
做法2,反过来想,从后往前看,最长的一个子序列对应了最小答案.
600:
问题可转化为,找一个凸多边形中是否存在三角形,且三角形与多边形不共顶点.
1暴力:
找出所有凸包中的点再找一个三角形,
找凸包中的所有点:枚举横坐标,再枚举每条边找到上端点和下端点. (O(size*N))
找三角形: 任取2个点,枚举下一个点,过程中必须保证每个点都不是凸包顶点.(O(size*N))
2特判:
如果凸包上点的个数size>=最大坐标差,可以确定其中必定有3不共线的点.
int N;
#define INF 200000
#define EPS 1e-10
int findcross(node a,node b,int x,bool flg)
{
if (a.x==b.x) return flg?max(a.y,b.y):min(a.y,b.y);
double k = (double)(a.y-b.y)/(double)(a.x-b.x);
double c = (double)a.y-k*(double)a.x;
double yy = k*(double)x+c;
int res;
if (flg) res = floor(yy+EPS);
else res = ceil(yy-EPS);
if (x==||x==-)
{
// printf("seg:(%d,%d) (%d,%d) cross at (%d ,%.2lf) , flg=%d res=%d\n",a.x,a.y,b.x,b.y,x,yy,flg,res);
}
return res;
}
int count(vector<int>X,vector<int>Y,vector<node> &q)
{
int cnt = ;
int l,r;
l = INF, r = -INF;
for (int i= ; i<N ; i++ ) l=min(l,X[i]),r=max(r,X[i]);
printf("l=%d r=%d\n",l,r);
for (int i=l ; i<=r ; i++ )
{
int yu,yl;
yu = -INF, yl = INF;
for (int j= ; j<N ; j++ )
{
node a = (node){X[j],Y[j]};
node b = (node){X[(j+)%N],Y[(j+)%N]};
if (min(a.x,b.x)<=i && i<=max(a.x,b.x))
{
yu = max(yu,findcross(a,b,i,));
yl = min(yl,findcross(a,b,i,));
}
}
// if (yu-yl>=0) printf("x=%d yl=%d yr=%d\n",i,yl,yu);
cnt += yu-yl+;
if (cnt>INF+N) return cnt;
for (int j=yl ; j<=yu ; j++ ) q.push_back((node){i,j});
}
return cnt;
}
double xmult(node p1,node p2 ,node p3)
{
// printf("area: (%d,%d) , (%d,%d) , (%d,%d) = ",p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);
node a;
a.x = p1.x-p2.x;
a.y = p1.y-p2.y;
node b;
b.x = p3.x-p2.x;
b.y = p3.y-p2.y;
double res = (double)(a.x*b.y-b.x*a.y)/2.0;
// printf("%lf\n",res);
return fabs(res);
}
bool ok(node a,vector<int> X,vector<int> Y)
{
for (int i= ; i<N ; i++ ) if (a.x==X[i] && a.y==Y[i]) return false;
return true;
}
bool check(vector<int>X,vector<int>Y)
{
vector<node>q;
int cnt = count(X,Y,q);
printf("count=%d\n",cnt);
if (cnt>INF+N) return true;
// for (int i=0 ; i<q.size() ; i++ ) if (ok(q[i],X,Y))printf("(%d,%d)\n",q[i].x,q[i].y);
for (int i= ; i<q.size() ; i++ )
if (ok(q[i],X,Y))
{
for (int j=i+ ; j<q.size(); j++ )
if (ok(q[j],X,Y))
{
for (int k = j+ ; k<q.size() ; k++ )
if (ok(q[k],X,Y) && xmult(q[i],q[j],q[k])>EPS) return true;
return false;
}
}
return false;
}
string ConvexPolygonGame::winner(vector <int> X, vector <int> Y)
{
N = X.size();
if (check(X,Y)) return "Masha";
else return "Petya";
}
trick:
计算上端点和下端点需要用取整函数,由于精度误差要加EPS:
上端点 = floor(y+EPS);
下端点 = ceil(y-EPS);
900：
通过分析知道确定第一列和"接下来每列新出现的颜色序列"后,可以确定一种方案,同时颠倒第一列可以得到一种对称方案.
再推导出"新颜色序列"的性质:
长度为N的序列可以确定长度为N的方案;
相邻项不相邻;
问题转化为对于给定的R,G,B,求组成序列的方案数;
然后计算一系列组合数就可以统计答案(按最后一位的颜色分别计算).
一个技巧:
计算 0~n 的 阶乘的逆元,根据模数是prim的性质,利用费马小定理得到n!的逆元f[n],然后由于
f[n]*n! = f[n]*n*(n-1)! = 1 % MOD
所以f[n-1] = f[n]*n,递推即可.
#define MOD 1000000007
#define MAXN 1500001
typedef long long llong;
llong a[MAXN],inv[MAXN],p[MAXN];
llong Pow(llong num,llong times)
{
llong res=;
while (times)
{
if (times%2ll) res = res*num%MOD;
num = num*num%MOD;
times/=2ll;
}
return res;
}
llong c(int m,int n)
{
if (n>m||m<) return ;
return a[m]*inv[m-n]%MOD*inv[n]%MOD;
}
llong getans(int x,int y,int z)
{
llong res=;
for (int g=x- ; g<=x ; g++ )
{
for (int e= ; e<=g ; e++ )
{
if ((y-z+g-e)%) continue;
int oy = (y-z+g-e)/;
int oz = g-e-oy;
int ry = y-oy-e;
int rz = z-oz-e;
if (oy<||oz<||ry<||rz<||ry!=rz) continue;
res += c(g,e)*c(g-e,oy)%MOD*c(g+ry-,ry)%MOD*p[e]%MOD;
while(res>=MOD) res-=MOD;
}
}
// printf("res=%lld\n",res);
return res;
}
int LittleElephantAndBoard::getNumber(int M, int R, int G, int B)
{
for (int i= ; i<MAXN ; i++ ) a[i] = i==?:a[i-]*(llong)i%MOD;
for (int i= ; i<MAXN ; i++ ) p[i] = i==?:p[i-]*2ll%MOD;
inv[MAXN-] = Pow(a[MAXN-],MOD-);
for (int i=MAXN- ; i>= ; i-- ) inv[i] = inv[i+]*((llong)i+)%MOD;
llong res=;
res += getans(M-R,M-G,M-B)*2LL%MOD; res %= MOD;
res += getans(M-G,M-R,M-B)*2LL%MOD; res %= MOD;
res += getans(M-B,M-G,M-R)*2LL%MOD; res %= MOD;
return (int)res;
}