Newnode

其实只有day1辣。。。day2还没放出来。。。day2放出来辣

线性代数：

Ci是Ai为1付出的代价，Bij+Bji是AiAj同时为1的价值。。。

真·裸·最小割。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

#define Clear(_,__) memset(_,__,sizeof _)

const int N=555,M=1000005,oo=1e9;

int f[M],e[M],next[M],G[N],Le[N],tot=1,n,B[N][N],C[N],S,T,SB[N],Sum;

void adde(int u,int v,int c,int nc)
{
	e[++tot]=v;next[tot]=G[u];G[u]=tot;f[tot]=c;
	e[++tot]=u;next[tot]=G[v];G[v]=tot;f[tot]=nc;
}

bool bfs()
{
	queue<int> Q;
	Clear(Le,-1);
	Q.push(S);
	Le[S]=1;
	while(!Q.empty()&&Le[T]==-1)
	{
		int u=Q.front();
        Q.pop();
		for(int i=G[u];i;i=next[i])
		{
			int v=e[i];
			if(Le[v]==-1&&f[i]>0)
				Q.push(v),
				Le[v]=Le[u]+1;
		}
	}
	return Le[T]!=-1;
}

int dfs(int u,int delta)
{
	if(u==T)
		return delta;
	int w=0,t,i,v;
	for(i=G[u];i&&w<delta;i=next[i])
	{
		v=e[i];
		if(Le[v]==Le[u]+1&&f[i]>0)
			t=dfs(v,min(delta-w,f[i])),
			w+=t,
			f[i]-=t,
			f[i^1]+=t;
	}
	if(!w)
		Le[u]=-1;
	return w;
}
 
int Maxflow()
{
	int Maxf=0;
	while(bfs())
		Maxf+=dfs(S,oo);
	return Maxf;
}
 

int main()
{
	scanf("%d",&n);
	S=0;T=n+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&B[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1,t;j<=n;j++)
			SB[i]+=t=B[i][j]+B[j][i],
			SB[j]+=t,
			adde(i,j,t,t);
	for(int i=1;i<=n;i++)
		Sum+=SB[i]+(B[i][i]<<1),
		adde(S,i,SB[i]+(B[i][i]<<1),0),
		scanf("%d",&C[i]),
		adde(i,T,C[i]<<1,0);
	printf("%d\n",Sum-Maxflow()>>1);
	return 0;
}

组合数学：

Dilworth定理：DAG的最小链覆盖=最大点独立集

没了。。最大点独立集显然就是一条斜线。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=1005;

int f[N][N],t,n,m,a[N][N],Ans;

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(f,0,sizeof f);
		Ans=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=m;i++)
		{
			for(int j=n;j;j--)
				f[j][i]=max(f[j][i-1],f[j+1][i-1]+a[j][i]);
			for(int j=n;j;j--)
				f[j][i]=max(f[j][i],f[j+1][i]);
			Ans=max(Ans,f[1][i]);
		}
		cout<<Ans<<endl;
	}
	return 0;
}

弦论：

裸·真·sam= =spoj即视感= =没了。。。

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=500500;

struct Node
{
	Node *Son[26],*pre;
	int l,w,s;
}T[N*2],*root=T+1,*last=T+1,*Now=T+1;

char s[N];

int type,k,Num[N],Q[N*2];

void Extend(int x)
{
	Node *p=last,*np=++Now;
	np->l=p->l+1;
	np->w=1;
	last=np;
	for(;p&&!p->Son[x];p=p->pre)
		p->Son[x]=np;
	if(!p)
		np->pre=root;
	else
	{
		Node *q=p->Son[x];
		if(q->l==p->l+1)
			np->pre=q;
		else
		{
			Node *nq=++Now;
			memcpy(nq->Son,q->Son,sizeof q->Son);
			nq->l=p->l+1;
			nq->pre=q->pre;
			np->pre=q->pre=nq;
			for(;p&&p->Son[x]==q;p=p->pre)
				p->Son[x]=nq;
		}
	}
}

void work()
{
	int L=Now-T;
	for(int i=1;i<=L;i++)
		Num[T[i].l]++;
	for(int i=1;s[i];i++)
		Num[i]+=Num[i-1];
	for(int i=L;i;i--)
		Q[Num[T[i].l]--]=i;
	for(int i=L;i>1;i--)
		if(type)
			T[Q[i]].pre->w+=T[Q[i]].w;
		else
			T[Q[i]].w=1;
	T[1].w=0;
	for(int i=L;i;i--)
	{
		Node &p=T[Q[i]];
		p.s=p.w;
		for(int j=0;j<26;j++)
			if(p.Son[j])
				p.s+=p.Son[j]->s;
	}
}

void out()
{
	Node *p=root;
	while(k)
	{
		if(k<=p->w)
			return;
		k-=p->w;
		for(int i=0;i<26;i++)
			if(p->Son[i])
			{
				if(k<=p->Son[i]->s)
				{
					putchar(i+'a');
					p=p->Son[i];
					break;
				}
				k-=p->Son[i]->s;
			}
	}
}

int main()
{
	gets(s+1);
	scanf("%d%d",&type,&k);
	for(int i=1;s[i];i++)
		Extend(s[i]-'a');
	work();
	if(root->s<k)
		puts("-1");
	else
		out();
	return 0;
}

旅游：

树剖裸题。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
const int N=200005;
 
struct Sta
{
    LL Max,Min,Ans1,Ans2;
     
    Sta():Max(-(1LL<<60)),Min(1LL<<60),Ans1(0),Ans2(0){}
}T[N];
 
Sta operator+(const Sta& a,const Sta& b)
{
    Sta c;
    c.Max=max(a.Max,b.Max);
    c.Min=min(a.Min,b.Min);
    c.Ans1=max(max(a.Ans1,b.Ans1),a.Max-b.Min);
    c.Ans2=max(max(a.Ans2,b.Ans2),b.Max-a.Min);
    return c;
}
 
int n,q,tot,G[N],e[N],next[N],top[N],son[N],sz[N],pre[N],pos[N],Index,fp[N],dep[N],w[N];
 
LL tag[N];
 
void adde(int u,int v)
{
    e[++tot]=v;next[tot]=G[u];G[u]=tot;
    e[++tot]=u;next[tot]=G[v];G[v]=tot;
}
 
void dfs1(int u,int p)
{
    pre[u]=p;
    dep[u]=dep[p]+1;
    sz[u]=1;
    for(int i=G[u];i;i=next[i])
        if(e[i]!=p)
        {
            dfs1(e[i],u);
            sz[u]+=sz[e[i]];
            if(sz[e[i]]>sz[son[u]])
                son[u]=e[i];
        }
}
 
void dfs2(int u,int p)
{
    top[u]=p;
    pos[u]=++Index;
    fp[Index]=u;
    if(son[u])
        dfs2(son[u],p);
    for(int i=G[u];i;i=next[i])
        if(e[i]!=pre[u]&&e[i]!=son[u])
            dfs2(e[i],e[i]);
}
 
#define Lc (x<<1)
#define Rc (x<<1|1)
#define Mid (l+r>>1)
 
void Add(int x,LL v)
{
    if(x)
        T[x].Max+=v,
        T[x].Min+=v,
        tag[x]+=v;
}
 
void pd(int x)
{
    if(tag[x])
        Add(Lc,tag[x]),
        Add(Rc,tag[x]),
        tag[x]=0;
}
 
void pu(int x)
{
    T[x]=T[Lc]+T[Rc];
}
 
void build(int x,int l,int r)
{
    if(l==r)
        T[x].Max=T[x].Min=w[fp[l]];
    else
        build(Lc,l,Mid),
        build(Rc,Mid+1,r),
        pu(x);
}
 
Sta Ask(int x,int l,int r,int L,int R,LL v)
{
    Sta w;
    if(L<=l&&r<=R)
        w=T[x],
        Add(x,v);
    else
    {
        pd(x);
        if(R<=Mid)
            w=Ask(Lc,l,Mid,L,R,v);
        else if(L>Mid)
            w=Ask(Rc,Mid+1,r,L,R,v);
        else
            w=Ask(Lc,l,Mid,L,R,v)+Ask(Rc,Mid+1,r,L,R,v);
        pu(x);
    }
    return w;
}
 
 
LL Ask(int u,int v,LL val)
{
    int fu=top[u],fv=top[v],flagu=1,flagv=0;
    Sta Ans1,Ans2,Ans;
    while(fu!=fv)
    {
        if(dep[fu]<dep[fv])
            swap(fu,fv),
            swap(u,v),
            swap(flagu,flagv);
        Sta Lzz=Ask(1,1,n,pos[fu],pos[u],val);
        if(flagu)
            swap(Lzz.Ans1,Lzz.Ans2),
            Ans1=Ans1+Lzz;
        else
            Ans2=Lzz+Ans2;
        u=pre[fu];
        fu=top[u];
    }
    if(dep[u]>dep[v])
        swap(u,v),swap(flagu,flagv);
    Sta Lzz=Ask(1,1,n,pos[u],pos[v],val);
    if(flagu)
        Ans1=Ans1+Lzz;
    else
        swap(Lzz.Ans1,Lzz.Ans2),
        Ans2=Lzz+Ans2;
    Ans=Ans1+Ans2;
    return Ans.Ans2;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),
        adde(u,v);
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    scanf("%d",&q);
    while(q--)
    {
        int u,v;
        LL l;
        scanf("%d%d%lld",&u,&v,&l);
        printf("%lld\n",Ask(u,v,l));
    }
    return 0;
}

棋盘：

也蛮简单的了。。按行装压dp，没了。。。矩阵乘。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <bitset>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef unsigned Ud;
 
int n,m,w,k,p,ok[20][20];
 
struct MAT
{
    Ud t[64][64];
     
    MAT(){memset(t,0,sizeof(t));}
}D,I;
 
MAT operator*(const MAT& A,const MAT& B)
{
    MAT C;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                C.t[i][j]+=A.t[i][k]*B.t[k][j];
    return C;
}
 
MAT operator^(MAT A,int B)
{
    MAT C=I;
    while(B)
    {
        if(B&1)
            C=C*A;
        A=A*A;
        B>>=1;
    }
    return C;
}
 
int check(int i,int j)
{
    bool vis[2][20]={};
    for(int k=0;k<w;k++)
        vis[0][k]=i&(1<<k);
    for(int k=0;k<w;k++)
        vis[1][k]=j&(1<<k);
    for(int l=0;l<2;l++)
        for(int r=0;r<w;r++)
            if(vis[l][r])
                for(int i=0;i<3;i++)
                    for(int j=0;j<p;j++)
                        if(ok[i][j]&&(i!=1||j!=k))
                        {
                            int x=l+i-1,y=r+j-k;
                            if(x>=0&&x<2&&y>=0&&y<w&&vis[x][y])
                                return 0;
                        }
    return 1;
}
 
int main()
{
    scanf("%d%d%d%d",&n,&w,&p,&k);
    for(int i=0;i<3;i++)
        for(int j=0;j<p;j++)
            scanf("%d",&ok[i][j]);
    m=1<<w;
    for(int i=0;i<m;i++)
        I.t[i][i]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            D.t[i][j]=check(i,j);
    cout<<(D^n+1).t[0][0];
    return 0;
}

概率论：

推下公式(打表找规律)就会发现是$\frac{n(n+1)}{4n-2}$，没了。。。

标程你挂精度你知道么
这个程序的精度是挂的。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <iomanip>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
int main()
{
    long long n;
    cin>>n;
    printf("%.9lf",1.0*n*(n+1)/(4*n-2));
    return 0;
}