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;
}