OJ第七套组队赛

Alphabetic Road Trip

/*
整体步骤: 
1存点    2.将城市名城映射成城市编号(输入顺序)  3.存边 
4. 距离初始化为无穷 
5. 把所有起点为'A'的城市 装入队列中,距离初始化为 0 
(队列中存入的的信息:   (  (到源点的距离,当前节点编号) ,节点城市首字母的下一个字母对应的数字))  并且在处理经过而不访问时 不会改变这个数字,访问时才修改
6.算法处理了... 
7.输出结果
dist[i][j]含义: j节点城市 到 以i字母(映射成数字了)开头的城市 的距离 

*/
#include <bits/stdc++.h> 
using namespace std; 
#define INF 0x3f3f3f3f 
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef pair<ll, int> pi; 
typedef pair<pi, int> pii;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a;//装入所有的城市节点 
    vector<pi> adj[n];// 记录与点 有关的边的信息; 
    map<string, int> getIndex;//得到点的编号 
    rep(i,0,n) {
        string curr;
        cin >> curr;
        a.push_back(curr);
        getIndex.insert(make_pair(curr, i));
    }
    rep(i,0,m) {
        string f, s;
        cin >> f >> s;
        int u = getIndex[f], v = getIndex[s];//节点编号 
        int w;
        cin >> w;//权值 
        adj[u].push_back(make_pair(w, v));//储存 点 的 边的信息 
        adj[v].push_back(make_pair(w, u));//储存 点 的 边的信息 
    }

    priority_queue<pii, vector<pii>, greater<pii> > pq; //pii中的单位元素: ( pi:(距离,节点编号) , int( 节点首字母的下一个字母 ) ) 
    int len = (int) ('J' - 'A') + 2;
    vector<ll> dist[len];//初始化 所有点 两两之间的距离 
    
    rep(i,0,len) rep(j,0,n) dist[i].push_back(INF); 
    
    rep(i,0,n) {  //所有起点为'A'的 
        if(a[i][0] == 'A') {
            pq.push(make_pair(make_pair(0, i), 1));
            dist[1][i] = 0; // 第i个输入的节点  到以B字母开头的城市的距离为0 
        }
    }
    while(!pq.empty()) {
        pii curr = pq.top();
        pq.pop();
        int at = curr.first.second,/* 点的编号 */ have = curr.second;/*当前节点城市首字母的下一个字母编号*/ 
        
        if(have == len - 1) continue;//遍历到 J 就结束
		
		
		///通过而不访问  ↓ ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
        rep(i,0,adj[at].size()) { //遍历与此点 有关的边 
            ll w = adj[at][i].first;//权值 
            int to = adj[at][i].second;//此边到达的点 
            if(dist[have][at] + w < dist[have][to]) {
// 从 at节点城市 到 以have(字母到数字的映射)为开头的城市的距离 + 边权 < 从to节点城市 到 have(字母到数字的映射)为开头的城市的距离
                dist[have][to] = dist[have][at] + w;
        //满足判断条件的话  说明 从to到have   比 从 at到 to 再到have 更短,更新即可↑ 
                pq.push(make_pair(make_pair(dist[have][to], to), have));/*这里装进去的 have 没有改变,说明 只是经过了这座城市,但并不作为访问点 
            而 have 没有改变,说明 最初的出发点(相同字母的)没有变  
			*/
			}
        }
		//通过而并不访问 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 
		
        //******************************************************************
        //******************************************************************
        
		//通过并且访问 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 
        int currLetter = (int) (a[at][0] - 'A');//当前访问的城市的首字母--->对应成数字 
        if(currLetter == have && dist[have][at] < dist[have + 1][at]) {//如果 当前访问的城市首字母 == 这个节点的have() ,并且从当前访问节点到 have 比到(have+1)距离更小,就更新离'J'更近的那个: dist[have + 1][at] 
        /*例如   有A,B,C,从A->C, at是A,at的have 是B, 但先经历里上面的 "通过而不访问" , 路线为"A->B->C", 
		 然后 遍历到 B点时 , B 的have 是B,并且发现,从at到 have(B)的距离小于 从at到have+1(C),就更新 从 at到have+1的距离
		 这样就使得了 到达的目的点 距离 J点更近,而 从A点出发 走发相同的距离 里A点更远了.  
		  */ 
            dist[have + 1][at] = dist[have][at];
            pq.push(make_pair(make_pair(dist[have + 1][at], at), have + 1));
        }//这是访问 并且改变have了 
        //通过并且访问了 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 
    }
    ll ans = INF;
    for(int i = 0; i < n; i++) {
        ans = min(ans, dist[len - 1][i]);/*刚开始所有点的距离 已初始化到正无穷了,
		然后 经过 迪杰斯特拉算法 以后, 从 多个以A点开始的城市中,找出了 到所有以J点开头的城市 的最短的距离 
		然后取其中的一个最小值 */ 
    }
	cout<<ans<<endl;
}
int main() 
{
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0; 
}

Glenn and Glenn’s Pizza

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,j,n) for(int i=j;i<n;i++)
#define MAXN 10
#define MAXK 10
#define MAXMASK 2048
#define MAXUNIQUE 2048
#define MAXM 50000
int countSetBits(int n) { //求  n的2进制中  1的个数
	int ans = 0;
	while (n) {
		n &= (n - 1);
		ans++;
	}
	return ans;
}
int n, m, k;
int numones[MAXMASK+10];

int dp[MAXK+1][MAXMASK+1][MAXUNIQUE+1];
vector<int> usables;

int solve(int topsRem, int mask, int idx) {
//( 还可以添加的调料数,((可能)mask 是当前的一种状态,然后 当拿这种调料的时候,用当前的状态和usables()中的状态 做 或 操作),当前的第几种状态数

	if(idx >= usables.size() || topsRem == 0) return numones[mask]; // usables.size():状态数(n个人对披萨的喜欢与讨厌的状态数)
	//----没有剩余状态了||无法在加调料了
	if(dp[topsRem][mask][idx] != -1) return dp[topsRem][mask][idx];

	int take = solve(topsRem-1, mask | usables[idx], idx+1); //拿这种调料
	int leave = solve(topsRem, mask, idx+1);//不拿这种调料

	return dp[topsRem][mask][idx] = max(take, leave);
}

int cas,t;
int main() {
	rep(i,0,MAXMASK+10)
	numones[i]=countSetBits(i); //得到 1-2^10中 每个数字中的 1的个数

	scanf("%d",&cas);
	while(cas--) {
		scanf("%d%d%d",&n,&m,&k);
		vector<int> toppings(m+1, 0);
		rep(i,0,n) {
			scanf("%d",&t);
			rep(j,0,t) {
				int ti;
				scanf("%d",&ti);
				toppings[ti] |= 1<<i;
			}
		}//得到了 每个调料的 n个人喜欢与否 的 一个序列 (然后 在这每个调料的状态中,可能有相同的序列

		rep(i,0,n+1) {
			rep(j,0,(1<<n)+1) {
				rep(kk,0,(1<<n)+1) {
					dp[i][j][kk] = -1;
				}
			}
		}//初始化

		usables = vector<int>(0);//总共的状态数 
		vector<int> usedMasks(MAXMASK+10, 0);  //10 个人最多有 2^10个序列

		rep(i,0,toppings.size()) { //遍历m种调料
			if(!usedMasks[toppings[i]]) { //如果 某种序列状态没出现过 ,就 装进去(因为可能 几种原料 讨厌他们的人 都一样
				usedMasks[toppings[i]] = 1;
				usables.push_back(toppings[i]);
			}
		}
		if(k >= n) printf("0\n");
		else printf("%d\n",n-solve(k, 0, 0));
	}
	return 0;
}

Molecular Mole

#include <bits/stdc++.h>
#include<vector>
using namespace std;
const double EPSILON = 1e-6;
#define rep(i,j,n) for(int i=j;i<n;i++)
bool eq(double a, double b) {
	return abs(a - b) <= EPSILON;
}
bool neq(double a, double b) {
	return abs(a - b) > EPSILON;
}
bool gt(double a, double b) {
	return neq(a, b) && a > b;
}
bool lt(double a, double b) {
	return neq(a, b) && a < b;
}
bool geq(double a, double b) {
	return eq(a, b) || a >= b;
}
bool leq(double a, double b) {
	return eq(a, b) || a <= b;
}
struct point {
	double x, y;
	point(double x, double y): x(x), y(y) {}
	double dist() const {
		return sqrt(x*x+y*y);
	}									//距离 
	point operator+(point o) const {
		return point(x + o.x, y + o.y);
	}
	point operator-(point o) const {
		return point(x - o.x, y - o.y);
	}
	point operator*(double s) const {
		return point(x * s, y * s);
	}
	point operator/(double s) const {
		return point(x / s, y / s);
	}											//四则运算 
	double cross(point o) const {
		return x * o.y - y * o.x;
	}											 //叉乘
	double cross(point a, point b) const {
		return (a - *this).cross(b - *this);
	}
	double dot(point o) const {
		return x * o.x + y * o.y;
	}                                     		//点乘 
	bool operator==(const point& o) const {
		return x == o.x && y == o.y;
	}											//判断 两点相等 
};
const point INVALID_POINT(-1e18, -1e18);

/*
函数用于计算直线P和Q的交点
直线P经过点a和b
直线Q经过点c和d
*/
point line_intersection(point& a, point& b, point& c, point& d) {
	double t = (b - a).cross(d - c);//两个方向向量作叉乘 
	if(eq(t, 0)) {
		return INVALID_POINT;
	}
	
	double p = c.cross(b, d);
	double q = c.cross(d, a);
	return (a * p + b * q) / t;
	/*point u=c-a;
	double t = (b - a).cross(u)/(d-c).cross(b-a);
	point pp(a.x+t*(d-c).x,a.y+t*(d-c).y);
	return pp;
	///return {a.x,a.y};*/
}
struct molecule {
	point p, v;
	molecule(point p, point v): p(p), v(v) {}
	// 计算两个分子相交时间的函数
	double intersect(molecule& o) {
		point a = p, b = p + v;
		point c = o.p, d = o.p + o.v;
		point inter = line_intersection(a, b, c, d);
		if(inter == INVALID_POINT) {  //两条路径平行
			inter = (a + c) / 2;//设交点为初始位置的中点
			if(neq(a.cross(inter, b), 0) || neq(c.cross(inter, d), 0)) {//确保这个点在两个分子的路径上
				return -1;
			}
		}
		if(lt((inter - a).dot(b - a), 0) || lt((inter - c).dot(d - c), 0)) {//确保这一点在两个分子的方向上
			return -1;
		}
		if(neq((inter - a).dist(), (inter - c).dist())) {//确保两个分子同时到达这个点
			return -1;
		}
		return (a - inter).dist();//时间是一个点到交点的距离
	}
};

//事件结构体,用来保存关于两个分子相交的数据
struct event {
	double t; //交集时间
	int i, j; //相交分子的指数
	event(double t, int i, int j): t(t), i(i), j(j) {}
	bool operator<(const event& o) const {// 按照相交时间排序, (t小的时候,优先级更小) 时间长的在前面
		return t < o.t;
	}
};
int x, y, dx, dy,n,tests;
int main() {
	cin >> tests;
	while(tests--) {
		cin >> n;
		
		vector<molecule> molecules;
		rep(i,0,n) {
			cin >> x >> y >> dx >> dy;
			point p(x, y), v(dx, dy);
			molecules.push_back(molecule(p, v));
		}
		
		vector<event> eq;
		rep(i,0,n) {
			rep(j,i+1,n) {
				double intersect_time = molecules[i].intersect(molecules[j]);//分子相交的时间
				if(intersect_time != -1) {
					eq.push_back(event(intersect_time, i, j));//存入 时间 和相交的 分子索引
				}
			}
		}
		sort(eq.begin(), eq.end());
		vector<int> answer(n);
		vector<int> indexes(n);	
		rep(i,0,indexes.size()) indexes[i]=i;
		//在交叉时,添加两个分子的索引
		//在交叉后,两个分子沿着彼此的路径,所以交换它们的索引
		rep(u,0,eq.size()) {
			answer[indexes[eq[u].i]]++;
			answer[indexes[eq[u].j]]++;
			swap(indexes[eq[u].i], indexes[eq[u].j]);
		}
		rep(i,0,n)
			printf("%d\n",answer[i]);
	}
	return 0;
}
上一篇:DP水题乱作


下一篇:最短路问题