A Cactus
给一棵树，可以连边（不能连重边），问连出仙人掌的方案数。
把模型转化为，给树染色，要求相同颜色的形成一条长度大于1的链或单点，树形dp
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;
#define IN freopen("cactus.in", "r", stdin)
#define OUT freopen("cactus.out", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
struct BigInteger {
typedef unsigned long long LL;
static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;
BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
BigInteger(LL num = 0) {*this = num;}
BigInteger(string s) {*this = s;}
BigInteger& operator = (long long num) {
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while (num > 0);
return *this;
}
BigInteger& operator = (const string& str) {
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for (int i = 0; i < len; i++) {
int end = str.length() - i*WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start,end-start).c_str(), "%d", &x);
s.push_back(x);
}
return (*this).clean();
}
BigInteger operator + (const BigInteger& b) const {
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
BigInteger operator - (const BigInteger& b) const {
assert(b <= *this); // 减数不能大于被减数
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = s[i] + g;
if (i < b.s.size()) x -= b.s[i];
if (x < 0) {g = -1; x += BASE;} else g = 0;
c.s.push_back(x);
}
return c.clean();
}
BigInteger operator * (const BigInteger& b) const {
int i, j; LL g;
vector<LL> v(s.size()+b.s.size(), 0);
BigInteger c; c.s.clear();
for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
for (i = 0, g = 0; ; i++) {
if (g ==0 && i >= v.size()) break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
BigInteger operator / (const BigInteger& b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
BigInteger m; // 余数:初始化为0
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return c.clean();
}
BigInteger operator / (const ll& b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
ll m=0; // 余数:初始化为0
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = m/b ;
m -= b*c.s[i];
}
return c.clean();
}
BigInteger operator % (const ll& b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
ll m=0;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
m%=b;
}
return BigInteger(m);
}
BigInteger operator % (const BigInteger& b) const { //方法与除法相同
BigInteger c = *this;
BigInteger m;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return m;
}
// 二分法找出满足bx<=m的最大的x
int bsearch(const BigInteger& b, const BigInteger& m) const{
int L = 0, R = BASE-1, x;
while (1) {
x = (L+R)>>1;
if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
else R = x;
}
}
BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}
BigInteger& operator /= (const ll& b) {*this = *this / b; return *this;}
BigInteger& operator %= (const ll& b) {*this = *this % b; return *this;}
bool operator < (const BigInteger& b) const {
if (s.size() != b.s.size()) return s.size() < b.s.size();
for (int i = s.size()-1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator >(const BigInteger& b) const{return b < *this;}
bool operator<=(const BigInteger& b) const{return !(b < *this);}
bool operator>=(const BigInteger& b) const{return !(*this < b);}
bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};
ostream& operator << (ostream& out, const BigInteger& x) {
out << x.s.back();
for (int i = x.s.size()-2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
istream& operator >> (istream& in, BigInteger& x) {
string s;
if (!(in >> s)) return in;
x = s;
return in;
}
const int maxn=205;
BigInteger dp[maxn][4];
vi g[maxn];
int n;
void DFS(int u,int f)
{
if(g[u].size()==1 && g[u][0]==f)
{
dp[u][1]=0;
dp[u][0]=0;
dp[u][2]=1;
dp[u][3]=0;
return;
}
dp[u][2]=1;dp[u][0]=dp[u][1]=dp[u][3]=0;
for(int p : g[u])
if(p!=f)DFS(p,u);
int l=g[u].size();
BigInteger cj=1;
for(int p : g[u])
if(p!=f)
{
dp[u][2]*=(dp[p][0]+dp[p][1]+dp[p][2]-dp[p][3]);
//xj*=(dp[p][0]+dp[p][1]+dp[p][2]-dp[p][3]);
}
cj=dp[u][2];
for(int i=0;i<l;i++)
for(int j=i+1;j<l;j++)
{
int x=g[u][i],y=g[u][j];
if(x==f || y==f)continue;
dp[u][0]+=cj/(dp[x][0]+dp[x][1]+dp[x][2]-dp[x][3])/(dp[y][0]+dp[y][1]+dp[y][2]-dp[y][3])*(dp[x][1]+dp[x][2])*(dp[y][1]+dp[y][2]);
}
for(int x : g[u])
if(x!=f)
{
dp[u][3]+=cj/(dp[x][0]+dp[x][1]+dp[x][2]-dp[x][3])*dp[x][2];
dp[u][1]+=cj/(dp[x][0]+dp[x][1]+dp[x][2]-dp[x][3])*(dp[x][2]+dp[x][1]);
}
}
int main()
{
IN;OUT;
scanf("%d",&n);
if(n==1){printf("1\n");return 0;}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].pb(y);g[y].pb(x);
}
DFS(1,0);
cout<<dp[1][0]+dp[1][1]+dp[1][2]-dp[1][3]<<endl;
return 0;
}
C Domino in Casino
给1个n*m的矩阵（元素均为正数），你可以选k个不重叠的1*2小矩形，问所以小矩形的2个数的乘积的和最大是多少。
就是简单网络流
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
class Cost_Flow
{
public:
int n,s,t;
int q[MAXM];
int edge[MAXM],Next[MAXM],Pre[MAXN],weight[MAXM],size;
int cost[MAXM];
void addedge(int u,int v,int w,int c)
{
edge[++size]=v;
weight[size]=w;
cost[size]=c;
Next[size]=Pre[u];
Pre[u]=size;
}
void addedge2(int u,int v,int w,int c=0){addedge(u,v,w,c),addedge(v,u,0,-c);}
bool b[MAXN];
int d[MAXN];
int pr[MAXN],ed[MAXN];
bool SPFA(int s,int t)
{
For(i,n) d[i]=INF,b[i]=0;
d[q[1]=s]=0;b[s]=1;
int head=1,tail=1;
while (head<=tail)
{
int now=q[head++];
Forp(now)
{
int &v=edge[p];
if (weight[p]&&d[now]+cost[p]<d[v])
{
d[v]=d[now]+cost[p];
if (!b[v]) b[v]=1,q[++tail]=v;
pr[v]=now,ed[v]=p;
}
}
b[now]=0;
}
return d[t]!=INF;
}
int totcost;
int CostFlow(int s,int t)
{
int maxflow=0;
while (SPFA(s,t))
{
int flow=INF;
for(int x=t;x^s;x=pr[x]) flow=min(flow,weight[ed[x]]);
totcost+=flow*d[t];
maxflow+=flow;
for(int x=t;x^s;x=pr[x]) weight[ed[x]]-=flow,weight[ed[x]^1]+=flow;
}
// cout<<maxflow<<endl;
return totcost;
}
void mem(int n,int t)
{
(*this).n=n;
size=1;
totcost=0;
MEM(Pre) MEM(Next)
}
}S;
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
ll id[120][120];
ll a[120][120];
int main()
{
freopen("domino.in","r",stdin);
freopen("domino.out","w",stdout);
int m=read(),n=read(),k=read();
int p1=0,p2=0;
For(i,m) For(j,n) {
a[i][j]=read();
id[i][j]=++p1;
}
int s=++p1,ta=++p1,tb=++p1;
S.mem(p1,p1);
For(i,m) For(j,n) {
if ((i+j)%2==0) {
S.addedge2(s,id[i][j],1);
if (i<m) S.addedge2(id[i][j],id[i+1][j],1,-a[i][j]*a[i+1][j]);
if (j<n) S.addedge2(id[i][j],id[i][j+1],1,-a[i][j]*a[i][j+1]);
if (i>1) S.addedge2(id[i][j],id[i-1][j],1,-a[i][j]*a[i-1][j]);
if (j>1) S.addedge2(id[i][j],id[i][j-1],1,-a[i][j]*a[i][j-1]);
}else {
S.addedge2(id[i][j],ta,1);
}
}
S.addedge2(ta,tb,k);
cout<<-S.CostFlow(s,tb)<<endl;
return 0;
}
E Set Partitions
我们定义一个集合大小的比较方式是，集合中的元素从小到大排序后得到的序列的字典序。定义一个集合的划分的比较是，先比较最小的，再比较次小的……，直到比出为止。现在有1~n个整数拆分到若干非空集合中，已知某个划分方案，问这个划分的下一个划分（next_permutation）是？
#include<cstdio>
#include<set>
using namespace std;
int a[501];
int main()
{
freopen("partitions.in","r",stdin);
freopen("partitions.out","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m)==2&&n){
int cnt=0;
getchar();
for(int i=0;i<m;i++){
do scanf("%d",&a[cnt++]);
while(getchar()!='\n');
a[cnt++]=0;
}
set<int> s;s.insert(a[cnt-2]);
bool flag=false;
for(int i=cnt-3;i>0;i--){
if(!a[i])m--;
else s.insert(a[i]);
if(a[i-1]){
auto it=s.upper_bound(a[i]?a[i]:a[i-1]);
if(it!=s.end()){
a[i]=*it;
s.erase(it);
cnt=i+1;a[cnt]=0;
flag=true;break;
}
}
}
printf("%d ",n);
if(flag){
printf("%d\n",m+s.size());
for(int i=0;i<=cnt;i++){
if(a[i])printf("%d ",a[i]);
else printf("\n");
}
for(int t:s)
printf("%d\n",t);
}
else{
printf("%d\n",n);
for(int i=1;i<=n;i++)
printf("%d\n",i);
}
printf("\n");
}
}
close
F Pipe Layout
r*c的矩阵的哈密尔顿回路个数（r*c<=100）
经典题，打表过。
I HTML Table
大模拟
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
string Filename="table";
int f[3100][3100]={},color=0;
char Map[3100][3100]={};
int last_tag;
int col,row;
bool _is_end;
// last_tag = 0(table) 1(tr) 2(td) 3(col) 4(wol)
int main()
{
freopen((Filename+".in").c_str(), "r", stdin);
freopen((Filename+".out").c_str(), "w", stdout);
MEM(f)
char ch,lch;
int n=0,m=0,cnt=0;
int p=0,l=0,pl[3]={};
int nowi=0,nowj;
lch=0;
bool b=0;
int N=0,M=0;
while(1) {
lch=ch;
ch=getchar();
ch=tolower(ch);
// cout<<lch<<ch;
if (ch=='<') {
b=1;
++p;
if (p==4) {
For(l,2)
if (!pl[l]) pl[l]=1;
++color;
while(f[nowi][nowj]) ++nowj;
Fork(i,nowi,nowi+pl[1]-1) {
Fork(j,nowj,nowj+pl[2]-1) {
if (f[i][j]) {
puts("ERROR");return 0;
}
f[i][j]=color;
// cout<<i<<' '<<j<<endl;
}
}
Map[2*nowi-1][2*nowj-1] ='+';
Map[2*nowi-1][2*nowj+pl[2]*2-1] ='+';
Map[2*nowi+pl[1]*2-1][2*nowj-1] ='+';
Map[2*nowi+pl[1]*2-1][2*nowj+pl[2]*2-1] ='+';
gmax(N,2*nowi+pl[1]*2-1);
gmax(M,2*nowj+pl[2]*2-1);
Fork(i,2*nowi,2*nowi+pl[1]*2-2) {
if (Map[i][2*nowj-1]!='+')
Map[i][2*nowj-1]='|';
if (Map[i][2*nowj+pl[2]*2-1]!='+')
Map[i][2*nowj+pl[2]*2-1]='|';
}
Fork(j,2*nowj,2*nowj+pl[2]*2-2) {
if (Map[2*nowi-1][j]!='+')
Map[2*nowi-1][j]='-';
if (Map[2*nowi+pl[1]*2-1][j]!='+')
Map[2*nowi+pl[1]*2-1][j]='-';
}
// cout<<nowi<<' '<<pl[1]<<' '<<nowj<<' '<<(-1+nowj+pl[2])<<endl;
nowj+=pl[2];
pl[1]=pl[2]=l=0;
}
}
if(b && ch=='>') {
b=0;
}
if (!b) continue;
if (ch=='/') {
p-=2;
if (!p) break;
}
if(lch=='t'&&ch=='r' && p==2) {
++nowi;nowj=1;
}
if (ch=='r') {
l=1;
} else if (ch=='c') {
l=2;
}
if (isdigit(ch)) {
pl[l]=pl[l]*10+ch-'0';
}
if (ch==EOF) break;
}
// For(i,n) {
// For(j,m) {
// cout<<f[i][j]<<' ';
// }
// }
For(i,N){
int tm=0;
For(j,M) if (Map[i][j]) tm=j;
For(j,tm) {
putchar(Map[i][j]?Map[i][j]:' ');
}cout<<endl;
}
return 0;
}