9.17 2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)

BCJ貌似签到题（不是我做的不补了）
FG直接咕了（以前学长都没补）
H自闭，写错变量WA了n次。~~（我其实还没太懂）~~不管。
I注意条件就很简单，就是要高精。

A.Altruistic Amphibians(01背包)

(Description)
有(n)只青蛙要过宽度为(d)的河，每只青蛙有重量(w)、高度(h)、跳跃距离(l)。
若干只青蛙可以叠罗汉，但要保证每只青蛙(i)上面的所有青蛙重量和小于(w_i)。此时若青蛙(i)下面青蛙高度和(sum h+l_i>d)则(i)可以跳过河。
只要满足条件每只青蛙可以任意次堆叠。求最多有多少只青蛙能过河。

(Solution)
英语题面读漏条件就很难受...要注意重量和是严格小于(w_i)，且青蛙总重要(leq 1e8)。
因为青蛙可以任意次叠罗汉，所以单独的一只青蛙(i)可以为总重(< w_i)的青蛙提供(h_i)的贡献，且只会重的去贡献轻的，
每只青蛙可以选择贡献或不贡献，所以就是一个01背包了。。。
青蛙从重到轻排序，(f[i])表示可承重为(i)时的最大高度，青蛙(k)的影响为：(f[i]=max(f[i], f[i+w_k]+h_k))。
注意(k)能更新的(i)范围只有(1sim w_i-1)，所以总复杂度只有(O(n+sum w_i))。
至于统计答案，只要(f[w_k]+l_k>d)青蛙(k)就一定有办法过了。。

//218ms	392400KB
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5,M=1e8+3;

int f[M];
struct Frog
{
	int l,w,h;
	bool operator <(const Frog &x)const
	{
		return w>x.w;
	}
}A[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now;
}

int main()
{
	int n=read(),D=read(),s=0;
	for(int i=1; i<=n; ++i) A[i]=(Frog){read(),read(),read()}, s+=A[i].w;
	std::sort(A+1,A+1+n);
	int ans=0;
	for(int i=1; i<=n; ++i)
	{
		int w=A[i].w, h=A[i].h;
		if(A[i].l+f[w]>D) ++ans;
		for(int j=1; j<w && j+w<=s; ++j) f[j]=std::max(f[j],f[j+w]+h);
	}
	printf("%d
",ans);

	return 0;
}

D.Delivery Delays(二分 DP)

(Description)
给定一张图，走1距离花费1时间。H在1号点有一家披萨店。有(k)个订单，每个订单有收到订单时间(s_i)，需送到的位置(u_i)，披萨被做好的时间(t_i)。
披萨(i)在(t_i)时间在1号店做好后，H才能在1号店拿起任意多披萨去送。每一时刻H可以带任意多的披萨，但必须严格按照订单顺序送披萨。
最小化每个订单得到披萨所需的等待时间的最大值。

(Solution)
因为严格按照顺序送披萨，所以可以(f[i])表示送完前(i)个披萨并还留在(u_i)位置所需的最短时间。
但怎么使最大值最小化呢。。二分答案(x)，设送到时间为(p_i)，满足(x-s_igeq p_i)，即(x-p_igeq s_i)则可以转移。
设(d_{i,j})为(i)到(j)距离。然后考虑一次拿起(i+1sim j)的披萨去送，花的时间是(d_{1,i}+max_{k=i+1sim j}t_k+d_{i+1,i+1}+...+d_{j-1,j})，对每个(l∈[i+1,j])要有(x-(f[i]+d_{1,i}+max_{k=i+1sim l}t_k+d_{i+1,i+1}+...+d_{l-1,l})-s_igeq 0)。
发现只要拿(f[i])去依次更新(f[j](j>i))时可以维护几个量，保证满足条件。所以转移就好了。。（具体不想写了。。）

//576ms	9300KB 比赛时写的有点乱
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define pc putchar
#define pr std::pair<LL,LL>
using namespace std;
typedef long long LL;
const int N=1005,M=1e5+6;
const LL INF=1e16;

int Enum,H[N],nxt[M],to[M],val[M],u[N],s[N],t[N];
LL d[N][N],dis[N],f[N];
bool vis[N];
std::priority_queue<pr> q;

inline int read()
{
	int now=0; char c=gc();
	for(; !isdigit(c); c=gc());
	for(; isdigit(c); now=now*10+c-48,c=gc());
	return now;
}
inline void AE(int u,int v,int w)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, val[Enum]=w;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, val[Enum]=w;
}
void Dijkstra(int s)
{
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	dis[s]=0, q.push(pr{0,s});
	while(!q.empty())
	{
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=H[x],v; i; i=nxt[i])
			if(dis[v=to[i]]>dis[x]+val[i])
				dis[v]=dis[x]+val[i], q.push(pr{-dis[v],v});
	}
}
bool Check(LL x,int n)
{
	if(x+s[1]-(t[1]+d[1][u[1]])<0) return 0;
	f[0]=0;
	for(int i=1; i<=n; ++i) f[i]=INF;
	for(int i=0; i<n; ++i)
	{
		if(f[i]==INF) continue;
		int maxt=0,pi=u[i];
		LL sum=0,now=INF,nowmax=0,tmp=f[i]+d[1][pi];
		for(int j=i+1; j<=n; ++j)
		{
			int pj=u[j];
			if(j!=i+1) sum+=d[u[j-1]][pj];
			else sum+=d[1][pj];
			maxt=std::max(maxt,t[j]);
			now=std::min(now,x+s[j]-tmp-sum);
			nowmax=std::max(nowmax,std::max(maxt-tmp,0ll));
			if(now<nowmax) break;
			if((x+s[j])-(tmp+sum+std::max(maxt-tmp,0ll))>=0)
				f[j]=std::min(f[j],f[i]+d[1][pi]+sum+std::max(maxt-(f[i]+d[1][pi]),0ll));
		}
		
	}
	return f[n]<INF;
}

int main()
{
	int n=read(),m=read();
	for(int i=1,u,v; i<=m; ++i) u=read(),v=read(),AE(u,v,read());
	for(int i=1; i<=n; ++i)
	{
		Dijkstra(i);
		for(int j=1; j<=n; ++j) d[i][j]=dis[j];
	}
	for(int i=1; i<=n; ++i) d[0][i]=d[i][0]=0;
	int k=read();
	for(int i=1; i<=k; ++i) s[i]=read(), u[i]=read(), t[i]=read();
	LL l=0,r=INF,mid;
	while(l<r)
	{
		if(Check(mid=l+r>>1,k)) r=mid;
		else l=mid+1; 
	}
	printf("%lld
",l);

	return 0;
}

E.Explosion Exploit(记忆化搜索)

(Description)
你有(n)个小兵，对方有(m)个小兵，血量给定。随机对场上所有还存活的小兵造成(1)伤害，重复(d)次。求(d)次伤害后对方所有小兵死亡的概率（你的小兵是否存活随意）。

(Solution)
这题不会..我怕不是个傻子...（以为排序后状态数依旧很多）
直接DP，最简单的就是开个10维数组了，复杂度(O(7^{10}))。
容易发现具体哪个小兵的血量是多少是无所谓的，只需要记血量为(i)的小兵有多少个，也就是将某时刻的血量排序作为一种状态就可以了。
写个程序算下排序后的状态数，只有462*462=213444个。直接记忆化就ok了。
血量可以七进制来存，也可以用10位longlong+map，或者存每个血量的有多少个（转移方便）。注意剪下枝。
第三种存状态的话s<1e6时敌方就都挂了。（0血量不用存啊。。）
（打ACM就随便用STL了）

//124ms	8000KB
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <unordered_map>
#define gc() getchar()
typedef long long LL;
const int N=250005;

namespace TEST
{
	const int N=1e5+5;
	int ans;
	bool v[N];
	int Trans(int x)
	{
		static int a[6];
		for(int i=1; i<=5; ++i,x/=10) a[i]=x%10;
		std::sort(a+1,a+6);
		if(a[5]>6) return 0;
		x=0;
		for(int i=1; i<=5; ++i) x*=10, x+=a[i];
		return x;
	}
	void Main()
	{
		for(int i=0,t; i<100000; ++i)
			if(!v[t=Trans(i)]) v[t]=1, ++ans;
		printf("%d
",ans);
	}
}

int A[8],B[8];
std::unordered_map<LL,double> f;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now;
}
LL Trans()
{
	LL x=0;
	for(int i=1; i<=6; ++i) x=x*10+B[i];
	for(int i=1; i<=6; ++i) x=x*10+A[i];
	return x;
}
double DFS(LL s,int d)
{
	if(s<1000000) return 1;
	if(f.count(s)) return f[s];
	if(!d) return 0;
	double res=0;
	for(int i=1; i<=6; ++i)
		if(A[i]) --A[i], ++A[i-1], res+=(A[i]+1)*DFS(Trans(),d-1), ++A[i], --A[i-1];
	for(int i=1; i<=6; ++i)
		if(B[i]) --B[i], ++B[i-1], res+=(B[i]+1)*DFS(Trans(),d-1), ++B[i], --B[i-1];
	int sum=0;
	for(int i=1; i<=6; ++i) sum+=A[i]+B[i];
	return f[s]=res/sum;
}

int main()
{
	const int n=read(),m=read(),d=read();
	for(int i=1; i<=n; ++i) ++A[read()];
	for(int i=1; i<=m; ++i) ++B[read()];
	printf("%.9lf
",DFS(Trans(),d));

	return 0;
}

K.King's Colors(容斥/二项式反演)

(Description)
给定一棵(n)个节点的树和(k)，求用恰好(k)种颜色将每个点染色，且相邻点不同色的方案数。

(Solution)
设(f(k))表示最多用(k)种颜色染色的方案数。树的形态是无所谓的，只需要每个点颜色不同与父节点，即对于(f(k))根节点有(k)种选择，非根节点都是(k-1)种选择，即(f(k)=k*(k-1)^{n-1})。
令(g(k))表示恰好用(k)种颜色染色的方案数。

由容斥有：(g(k)=f(k)-C_k^{k-1}f(k-1)+C_k^{k-2}f(k-2)-...)即(g(k)=sum_{i=1}^k(-1)^{k-i}f(i))。

或二项式反演：由(f(k)=sum_{i=0}^kC_k^ig(i))，二项式反演得(g(k)=sum_{i=0}^k(-1)^{k-i}f(i))。

即答案(g(k)=sum_{i=1}^k(-1)^{k-i}i*(i-1)^{n-1})。

//31ms	0KB
#include <cstdio>
#include <cctype>
#include <algorithm>
#define mod 1000000007
#define gc() getchar()
typedef long long LL;
const int N=2505;

int inv[N],C[N];

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}
inline int FP(LL x,int k)
{
	LL res=1;
	for(; k; k>>=1,x=x*x%mod)
		if(k&1) res=res*x%mod;
	return res;
}

int main()
{
	const int n=read(),K=read();
	C[0]=inv[1]=1;
	for(int i=2; i<=K; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1; i<=K; ++i) C[i]=1ll*(K-i+1)*inv[i]%mod*C[i-1]%mod;

	LL res=0;
	for(int i=K,sgn=1; i; --i,sgn*=-1)
		res+=1ll*sgn*C[i]*i%mod*FP(i-1,n-1)%mod;
	printf("%lld
",(res%mod+mod)%mod);

	return 0;
}