T1 [HAOI2016]放棋子
https://daniu.luogu.org/problem/show?pid=3182
障碍交换行不影响
所以第i列有障碍的行换到第i行
然后错排公式
本校自测要写压位高精，不写了。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int len;
int num[];
void clear()
{
len=;
memset(num,,sizeof(num));
}
void operator = (int a)
{
len=;
while(a) len++,num[len]=a%,a/=;
}
void operator = (node a)
{
len=a.len;
for(int i=;i<=len;i++) num[i]=a.num[i];
}
node operator + (node a)
{
node c; c.clear();
memset(c.num,,sizeof(c.num));
int L=max(a.len,len);
c.len=L;
for(int i=;i<=L;i++) c.num[i]=num[i]+a.num[i];
for(int i=;i<=L;i++)
if(c.num[i]>) c.num[i+]+=c.num[i]/,c.num[i]%=;
if(c.num[L+]) c.len++;
while(c.num[c.len]>) c.num[c.len+]=c.num[c.len]/,c.num[c.len]%=,len++;
if(c.num[c.len+]) c.len++;
return c;
}
node operator * (int a)
{
node c; c.clear();
int L;
c.len=L=len;
for(int i=;i<=L;i++) c.num[i]=num[i]*a;
for(int i=;i<=L;i++)
if(c.num[i]>) c.num[i+]+=c.num[i]/,c.num[i]%=;
if(c.num[L+]) c.len++;
while(c.num[c.len]>) c.num[c.len+]=c.num[c.len]/,c.num[c.len]%=,len++;
if(c.num[c.len+]) c.len++;
return c;
}
void print()
{
for(int i=len;i;i--) printf("%d",num[i]);
}
};
node f[];
int main()
{
// freopen("firstmeet.in","r",stdin);
// freopen("firstmeet.out","w",stdout);
int n;
scanf("%d",&n);
f[]=,f[]=,f[]=;
for(int i=;i<=n;i++)
{
f[i].clear();
f[i]=(f[i-]+f[i-])*(i-);
}
f[n].print();
}
T2 [Usaco2010 Dec]Exercise 奶牛健美操
http://www.lydsy.com/JudgeOnline/problem.php?id=2097
树形DP
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100001
using namespace std;
int front[N],to[N<<],nxt[N<<],tot;
int dp[N],tmp[N];
int cnt,p;
void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}
bool dfs(int x,int y,int z)
{
int sum=;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=y) { if(!dfs(to[i],x,z)) return false; }
for(int i=front[x];i;i=nxt[i])
if(to[i]!=y) tmp[++sum]=dp[to[i]]+;
sort(tmp+,tmp+sum+);
for(sum;tmp[sum]+tmp[sum-]>z;sum--,cnt++);
dp[x]=tmp[sum];
if(cnt>p) return false;
return true;
}
bool check(int mid)
{
memset(dp,,sizeof(dp));
cnt=;
return dfs(,,mid);
}
int main()
{
/* int size = 256 << 15;
char *pp = (char*) malloc(size) + size;
__asm__ ("movl %0, %%esp\n" :: "r"(pp));
freopen("longnosee.in","r",stdin);
freopen("longnosee.out","w",stdout); */
int n;
read(n), read(p);
int u,v;
for(int i=;i<n;i++)
{
read(u),read(v);
add(u,v);
}
int l=,r=n,mid,ans;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
T3
大爆搜，粘std啦
#include <cstdio>
#include <iostream>
#define rg register
#define Max 22
inline void read (int &now)
{
rg char c = getchar ();
for (now = ; !isdigit (c); c = getchar ());
for (; isdigit (c); now = now * + c - '', c = getchar ());
}
int _x[] = { , -, , , , }, _y[] = { , , , -, , }, _z[] = { , , , , , - };
int N, M, Z, P, Sx, Sy, Sz, St, Tt,Tx, Ty, Tz, Answer; bool is[Max][Max][Max], dot[Max][Max][Max];
inline bool Can (int x, int y, int z) { return x > && x <= N && y > && y <= M && z > && z <= Z && !is[x][y][z] && !dot[x][y][z]; }
inline int abs (int a) { return a < ? -a : a; }
void Dfs (int x, int y, int z, int t, int s)
{
int r = abs (x - Tx) + abs (y - Ty) + abs (z - Tz);
if (s + (r >> ) >= Answer) return ;
if (x == Tx && y == Ty && z == Tz) { if (t == Tt) Answer = s; return ; }
rg int i, a, b, c;
if (Can (x + _x[t], y + _y[t], z + _z[t]) && Can (x + _x[t] * , y + _y[t] * , z + _z[t] * ))
{
is[x + _x[t]][y + _y[t]][z + _z[t]] = true;
is[a = (x + _x[t] * )][b = (y + _y[t] * )][c = (z + _z[t] * )] = true;
for (i = ; i < ; ++ i)
if ((i >> ) != (t >> ) && Can (a + _x[i], b + _y[i], c + _z[i]) && Can (a + _x[i] * , b + _y[i] * , c + _z[i] * ))
{
is[a + _x[i]][b + _y[i]][c + _z[i]] = true;
is[a + _x[i] * ][b + _y[i] * ][c + _z[i] * ] = true;
Dfs (a + _x[i] * , b + _y[i] * , c + _z[i] * , i, s + );
is[a + _x[i]][b + _y[i]][c + _z[i]] = false;
is[a + _x[i] * ][b + _y[i] * ][c + _z[i] * ] = false;
}
if (Can (x + _x[t] * , y + _y[t] * , z + _z[t] * ))
{
is[a = (x + _x[t] * )][b = (y + _y[t] * )][c = (z + _z[t] * )] = true;
for (i = ; i < ; ++ i)
if ((i >> ) != (t >> ) && Can (a + _x[i], b + _y[i], c + _z[i]))
{
is[a + _x[i]][b + _y[i]][c + _z[i]] = true;
Dfs (a + _x[i], b + _y[i], c + _z[i], i, s + );
is[a + _x[i]][b + _y[i]][c + _z[i]] = false;
}
is[a = (x + _x[t] * )][b = (y + _y[t] * )][c = (z + _z[t] * )] = false;
}
is[x + _x[t]][y + _y[t]][z + _z[t]] = false;
is[x + _x[t] * ][y + _y[t] * ][z + _z[t] * ] = false;
}
}
int Main ()
{
freopen ("blessyou.in", "r", stdin); freopen ("blessyou.out", "w", stdout);
read (N), read (M), read (Z), read (P); rg int i, j; int x, y, z; rg char c;
if (N <= && M <= && Z <= ) return printf ("Dream Battle"), ;
read (Sx), read (Sy), read (Sz);
for (c = getchar (); c != 'x' && c != 'y' && c != 'z'; c = getchar ());
St = (c - 'x') << ;
if (c == 'x') St += (Sx == N); else if (c == 'y') St += (Sy == M);
else if (c == 'z') St += (Sz == Z);
Sx -= _x[St], Sy -= _y[St], Sz -= _z[St];
read (Tx), read (Ty), read (Tz);
for (c = getchar (); c != 'x' && c != 'y' && c != 'z'; c = getchar ());
Tt = (c - 'x') << ;
if (c == 'x') Tt += (Tx == ); else if (c == 'y') Tt += (Ty == );
else if (c == 'z') Tt += (Tz == );
for (i = ; i <= P; ++ i) read (x), read (y), read (z), dot[x][y][z] = true;
Answer = ; Dfs (Sx, Sy, Sz, St, );
if (Answer == ) printf ("Dream Battle"); else printf ("%d", Answer);
return ;
}
int ZlycerQan = Main (); int main (int argc, char *argv[]) { return ; }