20180806提高模拟B组

20180806提高模拟B组

T1 最短路(path)

看到$k\leq 10$即可想到状压。

inf值设定过小,明明是long long,却inf=0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct Edge;
struct Node{
	Edge *head;
	long long dis;
	bool vis;
}node[50010], *qwq[15];
struct Edge{
	Node *to;
	Edge *ne;
	int val;
	Edge(int x, int y, int z):to(&node[y]), ne(node[x].head), val(z){}
};
int n, m, k, s, t;
long long d[15][15], f[11][1<<10], ans=0x3f3f3f3f3f;

inline void dji(Node *S){
	priority_queue<pair<long long, Node*> >q;
	for(int i=1; i<=n; i++)
		node[i].dis=0x3f3f3f3f3f, node[i].vis=false;
	S->dis=0;
	q.push(make_pair(0, S));
	while(!q.empty()){
		Node *x=q.top().second;
		q.pop();
		if(x->vis)	continue;
		x->vis=true;
		for(Edge *i=x->head; i; i=i->ne)
			if(i->to->dis>x->dis+1LL*i->val){
				i->to->dis=x->dis+1LL*i->val;
				q.push(make_pair(-i->to->dis, i->to));
			}
	}
}

inline long long dp(const int &S){
	long long now=0x3f3f3f3f3f;
	memset(f, 0x3f3f3f3f3f, sizeof(f));
	f[S][1<<(S-1)]=0;
	for(int i=0; i<(1<<k); i++)
		for(int j=1; j<=k; j++)
			for(int K=1; K<=k; K++)
				if((i&(1<<(j-1))) && (i&(1<<(K-1)))){
					f[j][i]=min(f[j][i], f[K][i&(~(1<<(j-1)))]+d[K][j]);
				}
	for(int i=1; i<=k; i++)
		now=min(f[i][(1<<k)-1]+d[0][S]+d[i][k+1], now);
	return now;
}


int main(){
	int x, y, z;
	scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
	for(int i=1; i<=m; i++){
		scanf("%d%d%d", &x, &y, &z);
		node[x].head=new Edge(x, y, z);
	}
	for(int i=1; i<=k; i++){
		scanf("%d", &x);
		qwq[i]=&node[x];
	}
	for(int i=1; i<=k; i++){
		dji(qwq[i]);
		for(int j=1; j<=k; j++)
			d[i][j]=qwq[j]->dis;
		d[i][k+1]=node[t].dis;
	}
	dji(&node[s]);
	for(int j=1; j<=k; j++)
		d[0][j]=qwq[j]->dis;
	if(k==0){
		dji(&node[s]);
		printf("%lld\n", node[t].dis<0x3f3f3f3f3f ? node[t].dis : -1);
		return 0;
	}
	for(int i=1; i<=k; i++)
		ans=min(ans, dp(i));
	if(ans<0x3f3f3f3f3f)	cout<<ans;
	else				cout<<-1; 
	return 0;
}

 

T2 剑与魔法(dragons)

维护一个pq

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int N, x, ans;
char ch;
priority_queue<int>q;

int main(){
	scanf("%d", &N);
	for(int i=1; i<N; i++){
		ch=getchar();
		while(ch!='c' && ch!='e')
			ch=getchar();
		scanf("%d", &x);
		if(ch=='c'){
			q.push(-x);
			ans+=x;	
		}else
			while(q.size()>=x){
				ans+=q.top();
				q.pop();
			}
	}
	ch=getchar();
	while(ch!='c' && ch!='e')
		ch=getchar();
	scanf("%d", &x);
	if(q.size()>=x)	printf("%d", ans);
	else			printf("-1");
	return 0;
}

 

T3 三角形(triangle)

总数-直线上的

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, x[3010], y[3010];
double xie[3010];

int main(){
	freopen("triangle.in", "r", stdin);
	freopen("triangle.out", "w", stdout);
	scanf("%d", &n);
	long long ans=1LL*n*(n-1)/2*(n-2)/3;
	for(int i=1; i<=n; i++)	scanf("%d%d", &x[i], &y[i]);
	for(int i=1; i<n; i++){
		double last=-0x3f3f3f3f;
		int cnt=0;
		for(int j=i+1; j<=n; j++)
			xie[j-i]=1.0*(x[i]-x[j])/(y[i]-y[j]);
		sort(xie+1, xie+n-i+1);
		for(int j=1; j<=n-i; j++)
			if(last==xie[j]){
				cnt++;
			}else{
				if(cnt>1) ans-=1LL*cnt*(cnt-1)/2;
				cnt=1;
				last=xie[j];
			}if(cnt>1) ans-=1LL*cnt*(cnt-1)/2;
	}
	cout<<ans<<endl;
	return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注