USACO2018DEC GOLD

好简单啊。。

T1裸分层图最短路。

T2裸容斥。

T3更水的DP。

代码

T1

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

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;

}

const int MAXN=50005;

const int MAXM=100005;

int n,m,k,ecnt,head[MAXN<<1];

LL dis[MAXN<<1];

bool book[MAXN<<1];

struct Edge{

	int to,nxt,w;

}e[MAXM*4+MAXN];

inline void add_edge(int bg,int ed,int val){

	++ecnt;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	e[ecnt].w=val;

	head[bg]=ecnt;

}

std::queue<int> q;

void spfa(){

	while(!q.empty()) q.pop();

	memset(dis,0x3f,sizeof dis);

	dis[n]=0;

	q.push(n);

	book[n]=true;

	while(!q.empty()){

		int x=q.front();

		trav(i,x){

			int ver=e[i].to;

			if(dis[ver]>dis[x]+e[i].w){

				dis[ver]=dis[x]+e[i].w;

				if(!book[ver]){

					q.push(ver);

					book[ver]=true;

				}

			}

		}

		q.pop();

		book[x]=false;

	}

}

int main(){

	n=read(),m=read(),k=read();

	rin(i,1,m){

		int u=read(),v=read(),w=read();

		add_edge(u,v,w);

		add_edge(v,u,w);

		add_edge(u+n,v+n,w);

		add_edge(v+n,u+n,w);

	}

	rin(i,1,k){

		int x=read(),y=read();

		add_edge(x,x+n,-y);

	}

	spfa();

	rin(i,1,n-1){

		if(dis[n+i]<=dis[i]) printf("1\n");

		else printf("0\n");

	}

	return 0;

}

T2

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

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;

}

typedef std::pair<int,int> tw;

typedef std::pair<int,tw> tr;

typedef std::pair<tw,tw> fo;

typedef std::pair<tw,tr> fi;

inline tw mktw(int x,int y){

	return (tw){x,y};

}

inline tr mktr(int x,int y,int z){

	return (tr){x,mktw(y,z)};

}

inline fo mkfo(int x,int y,int z,int v){

	return (fo){mktw(x,y),mktw(z,v)};

}

inline fi mkfi(int x,int y,int z,int v,int w){

	return (fi){mktw(x,y),mktr(z,v,w)};

}

int n;

int mp1[1000005];

std::map<tw,int> mp2;

std::map<tr,int> mp3;

std::map<fo,int> mp4;

std::map<fi,int> mp5;

int main(){

	n=read();

	rin(i,1,n){

		int a[6];

		a[1]=read(),a[2]=read(),a[3]=read(),a[4]=read(),a[5]=read();

		std::sort(a+1,a+6);

		int x=a[1],y=a[2],z=a[3],v=a[4],w=a[5];

		++mp1[x];

		++mp1[y];

		++mp1[z];

		++mp1[v];

		++mp1[w];

		++mp2[mktw(x,y)];

		++mp2[mktw(x,z)];

		++mp2[mktw(x,v)];

		++mp2[mktw(x,w)];

		++mp2[mktw(y,z)];

		++mp2[mktw(y,v)];

		++mp2[mktw(y,w)];

		++mp2[mktw(z,v)];

		++mp2[mktw(z,w)];

		++mp2[mktw(v,w)];

		++mp3[mktr(x,y,z)];

		++mp3[mktr(x,y,v)];

		++mp3[mktr(x,y,w)];

		++mp3[mktr(x,z,v)];

		++mp3[mktr(x,z,w)];

		++mp3[mktr(x,v,w)];

		++mp3[mktr(y,z,v)];

		++mp3[mktr(y,z,w)];

		++mp3[mktr(y,v,w)];

		++mp3[mktr(z,v,w)];

		++mp4[mkfo(x,y,z,v)];

		++mp4[mkfo(x,y,z,w)];

		++mp4[mkfo(x,y,v,w)];

		++mp4[mkfo(x,z,v,w)];

		++mp4[mkfo(y,z,v,w)];

		++mp5[mkfi(x,y,z,v,w)];

	}

	LL ans=0;

	rin(i,1,1000000) ans+=1ll*mp1[i]*(mp1[i]-1)/2;

	for(register std::map<tw,int>::iterator it=mp2.begin();it!=mp2.end();++it) ans-=1ll*it->second*(it->second-1)/2;

	for(register std::map<tr,int>::iterator it=mp3.begin();it!=mp3.end();++it) ans+=1ll*it->second*(it->second-1)/2;

	for(register std::map<fo,int>::iterator it=mp4.begin();it!=mp4.end();++it) ans-=1ll*it->second*(it->second-1)/2;

	for(register std::map<fi,int>::iterator it=mp5.begin();it!=mp5.end();++it) ans+=1ll*it->second*(it->second-1)/2;

	printf("%lld\n",1ll*n*(n-1)/2-ans);

	return 0;

}

T3

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

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;

}

const int MAXN=10005;

const int MAXK=1005;

int n,k,a[MAXN],f[MAXN];

int main(){

	n=read(),k=read();

	rin(i,1,n) a[i]=read();

	f[0]=0;

	rin(i,1,n){

		int temp=0;

		irin(j,i,std::max(i-k+1,1)){

			temp=std::max(temp,a[j]);

			f[i]=std::max(f[i],f[j-1]+temp*(i-j+1));

		}

	}

	printf("%d\n",f[n]);

	return 0;

}

巴特西

USACO2018DEC GOLD

代码

T1

T2

T3

最新文章

热门文章