Newnode

还没完结呢= =先写一点吧= =

有意义的字符串：

这和字符串有毛线关系！

矩阵乘= =

模数巨大加起来就爆long long了

要unsigned long long。。。

#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 unsigned long long LL;

const LL Mod=7528443412579576937ll;

LL Add(LL x,LL y)
{
	x+=y;
	if(x>=Mod)
		x-=Mod;
	return x;
}

LL mult(LL x,LL y)
{
	LL k=0;
	while(y)
	{
		if(y&1)
			k=Add(k,x);
		x=Add(x,x);
		y>>=1;
	}
	return k;
}

LL b,d,n;

struct Mat
{
	LL t11,t12,t22,t21;
}lzz,Ans;

Mat operator*(const Mat& a,const Mat& b)
{
	Mat w;
	w.t11=Add(mult(a.t11,b.t11),mult(a.t12,b.t21));
	w.t12=Add(mult(a.t11,b.t12),mult(a.t12,b.t22));
	w.t21=Add(mult(a.t21,b.t11),mult(a.t22,b.t21));
	w.t22=Add(mult(a.t21,b.t12),mult(a.t22,b.t22));
	return w;
}

Mat operator^(Mat x,LL y)
{
	Mat k;
	k.t11=k.t22=1;k.t12=k.t21=0;
	while(y)
	{
		if(y&1)
			k=k*x;
		x=x*x;
		y>>=1;
	}
	return k;
}

int main()
{
	cin>>b>>d>>n;
	lzz.t21=1;
	lzz.t12=d-b*b>>2;
	lzz.t22=b;
	Ans=lzz^n;
	LL T=Add(Add(Ans.t11,Ans.t11),mult(Ans.t21,b));
	if(d!=b*b&&!(n&1))
		T--;
	cout<<T<<endl;
	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=300005;

LL n,m,dep[N],Ans[N],Ed[N],St[N],fa[N],ai[N],vi[N],hi[N],si[N];

vector<int> V[N],Son[N];

struct node
{
	node *l,*r;
	LL k,d,A,T,id;
}T[N];

#define dis(_) (_?_->d:-1)

void Add(node* p,LL A)
{
	if(p)
		p->k+=A,
		p->A+=A;
}

void Mult(node* p,LL T)
{
	if(p)
		p->k*=T,
		p->T*=T,
		p->A*=T;
}

void pd(node* p)
{
	if(p->T)
		Mult(p->l,p->T),
		Mult(p->r,p->T),
		p->T=1;
	if(p->A)
		Add(p->l,p->A),
		Add(p->r,p->A),
		p->A=0;
}

node* Merge(node* p,node* q)
{
	if(!p||!q)
		return !p?q:p;
	if(p->k>q->k)
		swap(p,q);
	pd(p);
	p->r=Merge(p->r,q);
	if(dis(p->l)<dis(p->r))
		swap(p->l,p->r);
	p->d=dis(p->r)+1;
	return p;
}

node* dfs(int x)
{
	dep[x]=dep[fa[x]]+1;
	node *p=0;
	for(int i=0;i<V[x].size();i++)
		p=Merge(p,T+V[x][i]);
	for(int i=0;i<Son[x].size();i++)
		p=Merge(p,dfs(Son[x][i]));
	while(p&&p->k<hi[x])
		pd(p),
		Ans[x]++,
		Ed[p->id]=x,
		p=Merge(p->l,p->r);
	if(ai[x])
		Mult(p,vi[x]);
	else
		Add(p,vi[x]);
	return p;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&hi[i]);
	hi[0]=1LL<<60;
	Son[0].push_back(1);
	for(int i=2;i<=n;i++)
		scanf("%lld%lld%lld",&fa[i],&ai[i],&vi[i]),
		Son[fa[i]].push_back(i);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&si[i],&St[i]),
		V[St[i]].push_back(i),
		T[i].T=1,T[i].k=si[i],T[i].id=i;
	dfs(0);
	for(int i=1;i<=n;i++)
		printf("%lld\n",Ans[i]);
	for(int i=1;i<=m;i++)
		printf("%lld\n",dep[St[i]]-dep[Ed[i]]);
	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 double DB;

const int N=505;

struct Lzz
{
	DB t[N];
	int c;
}W[N];

bool operator<(const Lzz& a,const Lzz& b)
{
	return a.c<b.c;
}

int n,m,Ans,Sum,Num[N];

bool check(int x)
{
	for(int i=1;i<=m;i++)
		if(fabs(W[x].t[i])>1e-5)
			if(!Num[i])
			{
				Num[i]=x;
				return 1;
			}
			else
			{
				DB tmp=W[x].t[i]/W[Num[i]].t[i];
				for(int j=i;j<=m;j++)
					W[x].t[j]-=tmp*W[Num[i]].t[j];
			}
	return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lf",&W[i].t[j]);
	for(int i=1;i<=n;i++)
		scanf("%d",&W[i].c);
	sort(W+1,W+n+1);
	for(int i=1;i<=n;i++)
		if(check(i))
			Ans++,
			Sum+=W[i].c;
	printf("%d %d",Ans,Sum);
	return 0;
}