Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024
Main » 2013 » October » 08
多米诺难题

状态压缩dp+矩阵加速

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 5
using namespace std;
typedef long long LL;
int m,n,p;
struct matrix
{
  int Matrix[32][32];
  matrix operator*(const matrix b)
  {
    int i,j,k;
    matrix c;
    memset(c.Matrix,0,sizeof(c.Matrix));
    for (i=0;i<(1<<m);i++)
     for (j=0;j<(1<<m);j++)
      for (k=0;k<(1<<m);k++)
       c.Matrix[i][j]=((Matrix[i][k]*b.Matrix[k][j])%p+c.Matrix[i][j])%p;
    return c;
  }
  matrix power(int x)
  {
    if (x<2) return *this;
    matrix mt=power(x/2);
  ... Read more »
Views: 268 | Added by: dhy0077 | Date: 10.08.2013

["扫地"杯III day1]破坏基地

最短路加判断

用数组模拟链表写的，速度很快

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define N 200100
#define L 400100
using namespace std;
typedef long long LL;
typedef long double LD;
int len=0,n,m;
int pre[N],last[N],w[N],e[N],q[L],dis[N],inq[N],path[N];
bool f[N],candel[N];
void add(int x,int y,int z)
{
  pre[++len]=last[x];
  last[x]=len;
  e[len]=y;w[len]=z;
}
void check(in ... Read more »
Views: 425 | Added by: dhy0077 | Date: 10.08.2013

感谢台风

台风万岁

Views: 255 | Added by: dhy0077 | Date: 10.08.2013