19-11-12-Aftern-℘

我饿死了，于是写写博客安慰一下即将退役的自己。

ZJ:

T1。

三种颜色，想到一道神奇的‘天空龙’。

于是觉得此题可做。

那好了。

于是切掉，还拿了一个暴力对拍。疯狂A。

啊dfs慢的要死了

T2一眼拓扑裸题。

但是读入很××。

于是拿出 getline(cin,st); 但是死了。

因为输入太……

后来一番倒饬过了样例。

T3丢了一个大暴力，然后发现根本不是图论题，是序列题=。=

然后就不会了。

最后T2就死了

为什么考输入啊？？？？

Miemeng

100

00:00:03

00:00:04

00:00:05

120

00:00:05

TJ解：

T1：

这题我是贪心思路，但是可以证明是正确的。（但是我不想，所以大家感性理解吧）

首先将三种颜色一个一个一个卡在一起。

非常棒

然后一定会剩两种颜色（或是一种）

那么如果有两种，就用多的少的$2:1$加入锅中组合

好好看

然后就考虑剩下的了。

如果剩下的是比较多的那种，那么就可以每三个多的和一个三元的交换来使答案$++$

如果是比较少的那种，就可以将每三个和前面匹配的两种交换。

有个细节，如果多的那个剩一个，可以和下面的两个少的相结合也挺好的。

//decorate

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int r,b,y;

void getsort(int &x,int &y,int &z){

	if(x<y)swap(x,y);

	if(y<z)swap(y,z);

	if(x<y)swap(x,y);

}

int main(){

#ifndef LOCAL

	freopen("decorate.in" ,"r",stdin);

	freopen("decorate.out","w",stdout);

#endif

//	while(cin>>r>>y>>b,getsort(r,y,b),cout<<r<<" "<<y<<" "<<b<<endl);

	int T;

	cin>>T;

	while(T--){

		scanf("%d%d%d",&r,&b,&y);

		getsort(r,b,y);

//		cout<<"Start:"<<r<<" "<<b<<" "<<y<<endl;

		int n_3=y;

		r-=n_3,b-=n_3,y-=n_3;

//		cout<<"3th_:"<<r<<" "<<b<<" "<<y<<endl;

		int n_2=min(r/2,b);

		r-=n_2*2,b-=n_2;

//		cout<<"2th_:"<<r<<" "<<b<<" "<<y<<endl;

		int swn=0;

		if(b==0){

			swn=min(n_3,r/3);

		}

		else if(r==1){

			if(b>=2){

				b-=2,r--;

				swn++;

				if(b>0){

					swn+=min(n_2+n_3,b/3);

				}

			}

		}

		else{//b!=0 && r==0.

			swn=min(n_2+n_3,b/3);

		}

//		cout<<n_3<<"+"<<n_2<<"+"<<swn<<endl;

		cout<<n_3+n_2+swn<<endl;

	}

}

T2

只考输入的题。

//dependency

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

#define N 333333

#define M 3333333

using namespace std;

const int Mod=5131111,Upbit=2411;//5477777

int id[Mod];

string st;

char dat[20];

struct SR{

	int f,t,next;

}rs[M];

int pcnt,ecnt,fl[N],pn;

struct Myqueue{

	int A[M*5];

	int f,b;

	Myqueue(){f=b=0;}

	void clear(){f=b=0;}

	bool empty(){return f==b;}

	void push(const int k){A[b++]=k;}

	void pop(){f++;}

	int front(){return A[f];}

}q;

int deg[N];

string thes;

int read(){

	getline(cin,thes);

	int d=0,n=0;

	while((thes[d]<'0' || thes[d]>'9') && d<(int)thes.length())d++;

	while(thes[d]>='0' && thes[d]<='9' && d<(int)thes.length()){

		n=n*10+thes[d]-'0';

		d++;

	}

	return n;

}

void add(int f,int t){

//	cout<<f<<"->"<<t<<endl;

	rs[ecnt].f=f;

	rs[ecnt].t=t;

	rs[ecnt].next=fl[f];

	fl[f]=ecnt++;

}

bool topsort(){

	q.clear();

	for(int i=1;i<=pcnt;i++){

		if(deg[i]==0){

			q.push(i);

		}

	}

	while(!q.empty()){

		int f=q.front();q.pop();

		for(int i=fl[f];i!=-1;i=rs[i].next){

			int t=rs[i].t;

			deg[t]--;

			if(deg[t]==0){

				q.push(t);

			}

		}

	}

	for(int i=1;i<=pcnt;i++)

		if(deg[i]!=0)return 1;

	return 0;

}

void prerun(){

	pcnt=0,ecnt=0;

	memset(id , 0,sizeof id );

	memset(deg, 0,sizeof deg);

	memset(fl ,-1,sizeof fl );

}

int main(){

#ifndef LOCAL

	freopen("dependency.in" ,"r",stdin);

	freopen("dependency.out","w",stdout);

#endif

//	freopen("2.in","r",stdin);

	ios_base::sync_with_stdio(false);

	int T;

	T=read();

	while(T--){

		prerun();

		pn=read();

		for(int i=1;i<=pn;i++){

			getline(cin,st);

			st+=" ";

			int f=0,len=st.length();

			long long hsn=0;

			for(int j=0;j<len;j++){

				if(st[j]=='\r')continue;

				if((st[j]>='A'&&st[j]<='Z')||(st[j]>='0' && st[j]<='9'))

					hsn=(hsn*Upbit+st[j])%Mod;

				else{

					if(id[hsn]==0)id[hsn]=++pcnt;

					int sid=id[hsn];

					if(f==0) f=sid;

					else {

						add(f,sid);

						deg[sid]++;

					}

					hsn=0;

				}

			}

		}

		cout<<(topsort()?"Yes":"No")<<endl;

	}

}

T3

可以证明将处理出的数组排序然后切开就是优的。

然后有个决策单调性，即转移点是从$i-\frac{i}{j}$到$i$的

那么就可以了（水题使我快乐）

//assignment

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define N 5555

#define M 55555

#define LL long long

using namespace std;

int pn,cn,pron,edn;

LL vals[N],pre[N];

LL dp[N][N],

   siz[N];

int apppn=0;

typedef pair<LL,int> pli;

struct SR{

	int f,t,next;

	int v;

};

priority_queue<pli,vector<pli>,greater<pli> >q;

struct MAPS{

	SR rs[M];

	int fl[N];

	int cnt;

	LL dis[N];

	bool is_v[N];

	MAPS(){

		memset(fl,-1,sizeof fl);

		cnt=0;

	}

	void add(int f,int t,int v){

		rs[cnt].f=f;

		rs[cnt].t=t;

		rs[cnt].v=v;

		rs[cnt].next=fl[f];

		fl[f]=cnt++;

	}

	void dij(int st){

		memset(dis,0x3f,sizeof dis);

		dis[st]=0;

		q.push(make_pair(0,st));

		while(!q.empty()){

			int f=q.top().second;q.pop();

			if(is_v[f])continue;

			is_v[f]=1;

			for(int i=fl[f];i!=-1;i=rs[i].next){

				int t=rs[i].t;

				if(dis[t]>dis[f]+rs[i].v){

					dis[t]=dis[f]+rs[i].v;

					q.push(make_pair(dis[t],t));

				}

			}

		}

	}

}am,bm;

int main(){

#ifndef LOCAL

	freopen("assignment.in" ,"r",stdin);

	freopen("assignment.out","w",stdout);

#endif

	int a,b,v;

	scanf("%d%d%d%d",&pn,&cn,&pron,&edn);

	for(int i=1;i<=edn;i++){

		scanf("%d%d%d",&a,&b,&v);

		am.add(a,b,v);

		bm.add(b,a,v);

	}

	am.dij(cn+1);

	bm.dij(cn+1);

	for(int i=1;i<=cn;i++){

		vals[i]=am.dis[i]+bm.dis[i];

//		cout<<vals[i]<<" ";

	}

//	cout<<endl;

	sort(vals+1,vals+cn+1);

	for(int i=1;i<=cn;i++)

		pre[i]=pre[i-1]+vals[i];

	memset(dp,0x3f,sizeof dp);

	for(int i=1;i<=cn;i++){

		dp[i][1]=pre[i]*(i-1);

	}

	for(int i=1;i<=cn;i++){

		for(int j=2;j<=pron;j++){

			for(int k=i-i/j;k<i;k++){

				dp[i][j]=min(dp[i][j],dp[k][j-1]+(pre[i]-pre[k])*(i-k-1));

			}

		}

	}

//	cout<<dp[cn-1][pron-1]<<endl;

	cout<<dp[cn][pron]<<endl;

}

巴特西

19-11-12-Aftern-℘

ZJ:

TJ解：

T1：

T2

T3

最新文章

热门文章