Clever Space

wood.cpp

dhy0077 — Thu, 06 Nov 2014 02:40:35 GMT

#include #include #include #include #include #include #include #include #include #include #include #include #define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define y1 fuck
using namespace std;
typedef long long LL;
typedef long double LD;
int n,lim;
LL f(int k)
{
if (lim>k-1) return k-1;
return max(k-1-((k-lim-1)<<1),0);
}
int main()
{
int n,i;
scanf("%d",&n);
lim=n/2-1;
if (n%2==1) lim++;
LL ans=0;
FOR(i,2,n-2)
{
ans+=f(i)*f(n-i);
}
printf("%lld\n",ans);
return 0;
}

CG1

dhy0077 — Wed, 24 Sep 2014 08:02:39 GMT

f[i][j]=f[i-1][j-1]+

位置数N
N=7

case 1
sum=

i-1=3
AB..... 3
A.B.... 2
A..B... 1
A...B.. 1
A....B. 2
A.....B 3
ABC.... 2
AB.C... 1
7-3 4
3
4=1+1+2
4=1+3
4=4
f1[i][j]
f2[i][j]
f3[i][j]

【分数规划】[Usaco2014 Mar]Sabotage

dhy0077 — Fri, 15 Aug 2014 11:59:10 GMT

二分答案，判断是否有一组解的F值小于0

Code:b3477.html

一份较详细的单纯形模板

dhy0077 — Sun, 03 Aug 2014 11:28:52 GMT

float a[MAX][MAX], b[MAX], c[MAX], x[MAX], v;
int n, m;

void pivot(bool flag_row[], bool flag_column[], float c[MAX], int l, int e)
{
//计算原等式变形系数
b[e] = b[l] / a[l][e];

for(int j = 0; j <= m+n; ++j)
if(j != e && flag_column[j]) a[e][j] = a[l][j] / a[l][e];

a[e][l] = 1 / a[l][e];

//更新限制等式
for(int i = 0; i <= m+n; ++i)
{
  if(i != l && flag_row[i])
  {
   b[i] -= (a[i][e]*b[e]);

for(int j = 0; j <= m+n; ++j)
if(j != e && flag_column[j]) a[i][j] -= (a[i][e]*a[e][j]);

a[i][l] = -a[i][e]*a[e][l];
}
}

//更新目标等式
v += (c[e]*b[e]);

for(int j = 0; j <= m+n; ++j)
if(j != e && flag_column[j]) c[j] -= (c[e]*a[e][j]);

c[l] = -c[e]*a[e][l];

//更新集合标记
flag_row[l] = false;
flag_row[e] = true;

flag_column[l] = true;
flag_column[e] = false;
}

bool Run(bool flag_row[], bool flag_column[], float c[])
{
int i, j;

while(true)
{
  for(j = 0; j <= m+n; ++j)
  {
   if(flag_column[j] && c[j] > ESP)
   {
    break;
   }
  }

if(j == m+n+1) break;

float data = (float)INF;
int e = j, l;

  for(i = 0; i <= m+n; ++i)
  {
   if(a[i][e] > ESP && flag_row[i])
   {
    float tmp = b[i]/a[i][e];
    if(data > tmp)
    {
     data = tmp;
     l = i;
    }
   }
  }

if(data == INF) return false;
else pivot(flag_row, flag_column, c, l, e);
}

for(j = 0; j <= n+m; ++j)
{
  if(flag_column[j])
   x[j] = 0;
  else
   x[j] = b[j];
}

return true;
}

bool Initialize(bool flag_row[], bool flag_column[])
{
float tmp = (float)INF;
float tmpc[MAX];
int l;

memset(tmpc, 0, sizeof(tmpc));

for(int i = n; i <= m+n; ++i)
{
  if(tmp > b[i])
  {
   l = i;
   tmp = b[i];
  }
}

v = 0.0f;

for(int j = 1; j <= n; ++j) flag_column[j] = true;
for(int i = 1; i <= m; ++i) flag_row[n+i] = true;

if(tmp < 0.0f)
{
tmpc[0] = -1;
flag_column[0] = true;

  for(int i = 1; i <= m; ++i)
   a[n+i][0] = -1;

  pivot(flag_row, flag_column, tmpc, l, 0);

if(!Run(flag_row, flag_column, tmpc)) return false;

if(v < 0.0f) return false;
else v = 0.0f;

flag_row[0] = flag_column[0] = false;

  for(int i = 0; i <= m+n; ++i)
  {
   if(c[i] != 0.0f && flag_row[i])
   {
    v += c[i]*b[i];

    for(int j = 0; j <= m+n; ++j)
    {
     if(flag_column[j]) c[j] -= a[i][j]*c[i];
    }

    c[i] = 0.0f;
   }
  }
}

return true;
}

//样例///////////////////////////////////////////

//m = n = 3;

//c[1] = 3; c[2] = 1; c[3] = 2;
//b[4] = 30; b[5] = 24; b[6] = 36;

//a[4][1] = 1; a[4][2] = 1; a[4][3] = 3;
//a[5][1] = 2; a[5][2] = 2; a[5][3] = 5;
//a[6][1] = 4; a[6][2] = 1; a[6][3] = 2;
////////////////////////////////////////////////

bool Simplex() //n个未知列，m个约束等式
{
bool flag_row[MAX], flag_column[MAX];
v = 0.0f;

memset(flag_row, 0, sizeof(flag_row));
memset(flag_column, 0, sizeof(flag_column));

if(!Initialize(flag_row, flag_column))
return false;

return Run(flag_row, flag_column, c);
}

FFT模板

dhy0077 — Sun, 20 Jul 2014 10:54:48 GMT

复数类：cpx

FFT主过程：FFT_main

一个范例：FFT_sample

最小圆覆盖模板

dhy0077 — Sun, 20 Jul 2014 04:56:06 GMT

double PI=3.1415926535898;
double dis(const Point &a,const Point &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
Point circumcenter(const Point &a,const Point &b,const Point &c)
{ //返回三角形的外心
Point ret;
double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;
double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;
double d=a1*b2-a2*b1;
ret.x=a.x+(c1*b2-c2*b1)/d;
ret.y=a.y+(a1*c2-a2*c1)/d;
return ret;
}
void min_cover_circle(Point *p,int n,Point &c,double &r){ //c为圆心，r为半径
random_shuffle(p,p+n); //
c=p[0]; r=0;
for(int i=1;i {
if(dis(p[i],c)>r+eps) //第一个点
{
c=p[i]; r=0;
for(int j=0;j if(dis(p[j],c)>r+eps) //第二个点
{
c.x=(p[i].x+p[j].x)/2;
c.y=(p[i].y+p[j].y)/2;
r=dis(p[j],c);
for(int k=0;k if(dis(p[k],c)>r+eps) //第三个点
{//求外接圆圆心，三点必不共线
c=circumcenter(p[i],p[j],p[k]);
r=dis(p[i],c);
}
}
}
}
}

bzoj上的两道主席树题

dhy0077 — Mon, 09 Jun 2014 03:03:50 GMT

我发现自己真是个大NC

3295: [Cqoi2011]动态逆序对：这个题的话要把区间修改，单点查询转为区间查询，单点修改否则如果打标记的话复杂度会不对。

3524: [Poi2014]Couriers:区间众数是没法维护的，但是子树大小大于等于(r-l+1)/2的子树一定包括答案，所以就可以搞了

prob list

dhy0077 — Wed, 04 Jun 2014 13:35:59 GMT

2303 2809 1913 2327

又刷了些水题啊啊啊啊啊啊啊啊

dhy0077 — Wed, 04 Jun 2014 13:32:43 GMT

怒A 7题呵呵

dhy0077 — Tue, 03 Jun 2014 13:22:20 GMT

都是水题啦