如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
It Can Be Arranged
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
struct Graph
{
struct Vertex
{
vector<int> o /* , i*/; //相关出边和入边编号
//int siz, dep, top, dfn;
//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int first, second;
ll /* len, */ cap; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.first == ed.second)
return; //如果有需要请拆点
v[ed.first].o.push_back(e.size());
//v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
//int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
//int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
struct ISAP : Graph
{
ll flow;
vector<ll> f;
vector<int> h, cur, gap;
ISAP(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0;
Graph::add(ed);
}
ll dfs(int s, int u, int t, ll r)
{
if (r == 0 || u == t)
return r;
ll _f, _r = 0;
for (int &i = cur[u], k; i < v[u].o.size(); ++i)
if (k = v[u].o[i], h[u] == h[e[k].second] + 1)
{
_f = dfs(s, e[k].second, t, min(r - _r, e[k].cap - f[k]));
f[k] += _f, f[k ^ 1] -= _f, _r += _f;
if (_r == r || h[s] >= v.size())
return _r;
}
if (!--gap[h[u]])
h[s] = v.size();
return ++gap[++h[u]], cur[u] = 0, _r;
}
void ask(int s, int t)
{
h.assign(v.size(), 0);
cur.assign(v.size(), 0);
gap.assign(v.size() + 2, 0);
/*
for(deque<int> q(h[t]=gap[t]=1,t); !q.empty(); q.pop_front())//优化，加了能快一点
for(int i=0,u=q.front(),k,to; i<v[u].o.size(); ++i)
if(to=e[v[u].o[i]].second,!h[to])
++gap[h[to]=h[u]+1],q.push_back(to);
*/
for (f.assign(e.size(), flow = 0); h[s] < v.size();)
flow += dfs(s, s, t, INF);
}
};
int main()
{
int t, n, m, kase = 0;
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
ISAP g(n * 2 + 2);
vector<int> a(n), b(n);
ll sum = 0;
for (int i = 0, t; i < n; ++i)
{
scanf("%d%d%d", &a[i], &b[i], &t);
sum += t = (t + m - 1) / m;
g.add({n << 1, i << 1, t});
g.add({i << 1 | 1, n << 1 | 1, t});
}
for (int i = 0; i < n; ++i)
for (int j = 0, t; j < n; ++j)
{
scanf("%d", &t);
if (b[i] + t < a[j])
g.add({i << 1, j << 1 | 1, INF});
}
g.ask(n << 1, n << 1 | 1);
cout << "Case " << ++kase << ": " << sum - g.flow << "\n";
}
}
Shopping Malls
#include <bits/stdc++.h>
using namespace std;
typedef double lf;
typedef lf ll;
const ll INF = 1e18;
struct Graph
{
struct Vertex
{
vector<int> o /* , i*/; //相关出边和入边编号
//int siz, dep, top, dfn; //树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
struct Coord3
{
lf X, Y, Z;
friend Coord3 operator-(const Coord3 &a, const Coord3 &b) { return {a.X - b.X, a.Y - b.Y, a.Z - b.Z}; }
friend lf abs(const Coord3 &a) { return sqrt(a.X * a.X + a.Y * a.Y + a.Z * a.Z); }
} p;
};
struct Edge
{
int first, second;
ll len /*, cap*/; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.first == ed.second)
return; //如果有需要请拆点
v[ed.first].o.push_back(e.size());
//v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
//int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
//int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
struct Dijkstra : Graph
{
vector<ll> d;
vector<int> p;
Dijkstra(int n) : Graph(n) {}
void ask(int s)
{
d.assign(v.size(), INF);
p.assign(v.size(), e.size());
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (int i = 0, k, to; i != v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len, p[to] = k;
q.push(make_pair(-d[to], to));
}
}
}
void print(int x)
{
if (p[x] != e.size())
print(e[p[x]].first);
printf("%d ", x);
}
};
int main()
{
int n, m;
scanf("%d%d", &n, &m);
Dijkstra g(n);
for (int i = 0; i < n; ++i)
scanf("%lf%lf%lf", &g.v[i].p.Z, &g.v[i].p.X, &g.v[i].p.Y), g.v[i].p.Z *= 5;
for (int i = 0, a, b; i < m; ++i)
{
char s[15];
scanf("%d%d%s", &a, &b, s);
if (s[0] == 'l')
g.add({a, b, 1}), g.add({b, a, 1});
else if (s[0] == 'e')
g.add({a, b, 1}), g.add({b, a, abs(g.v[a].p - g.v[b].p) * 3});
else
g.add({a, b, abs(g.v[a].p - g.v[b].p)}), g.add({b, a, abs(g.v[a].p - g.v[b].p)});
}
scanf("%d", &m);
for (int i = 0, a, b; i < m; ++i)
{
scanf("%d%d", &a, &b);
g.ask(a);
g.print(b);
printf("\n");
}
}
Odd and Even Zeroes
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long LL;
const int maxn=30+10;
LL n;
int a[maxn];
struct data
{
LL x,y;
}f[maxn];
data dfs(int now,int ok)
{
data t;t.x=1ll;t.y=0ll;
if (now==-1) return t;
if (!ok && f[now].x!=-1) return f[now];
data res;
res.x=res.y=0;
if (ok)
{
for (int i=0;i<a[now];i++)
{
data to=dfs(now-1,0);
int x=now*i;
if (x&1) {res.x+=to.y;res.y+=to.x;}else {res.x+=to.x;res.y+=to.y;}
}
data to=dfs(now-1,1);
int x=now*a[now];
if (x&1) {res.x+=to.y;res.y+=to.x;}else {res.x+=to.x;res.y+=to.y;}
return res;
}
else
{
for (int i=0;i<5;i++)
{
data to=dfs(now-1,0);
int x=now*i;
if (x&1) {res.x+=to.y;res.y+=to.x;}else {res.x+=to.x;res.y+=to.y;}
}
f[now]=res;
return res;
}
}
int main()
{
for (int i=0;i<30;i++) f[i].x=-1;
scanf("%I64d",&n);
while (n!=-1ll)
{
int m=0;
while (n>0)
{
a[m++]=n%5ll;
n/=5ll;
}
m--;
data res=dfs(m,1);
LL ans=res.x;
printf("%I64d\n",ans);
scanf("%I64d",&n);
}
return 0;
}
VivoParc
#include <bits/stdc++.h>
using namespace std;
const int N = 127;
int n, x, y, ans[N], g[N][N];
void dfs(int k)
{
if (k > n)
{
for (int i = 1; i < k; ++i)
printf("%d %d\n", i, ans[i]);
exit(0);
}
vector<int> cnt(5, 0);
for (int i = 1; i < k; ++i)
if (g[k][i])
++cnt[ans[i]];
for (int i = 1; i < cnt.size(); ++i)
if (!cnt[i])
ans[k] = i, dfs(k + 1);
}
int main()
{
for (scanf("%d", &n); ~scanf("%d-%d", &x, &y);)
g[x][y] = g[y][x] = 1;
dfs(1);
}
Binary Tree
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxn=100000+10,mod=21092013;
int T,n,k;
int f[maxn];
char ch[maxn];
int main()
{
scanf("%d",&T);
for(int t=1;t<=T;t++)
{
scanf("%s",ch);
int Li=strlen(ch);
int k=0;
for(int i=0;i<Li;i++)
{
if (ch[i]=='U' && k!=0) k--;
if (ch[i]=='L') f[++k]=0;
if (ch[i]=='R') f[++k]=1;
}
scanf("%s",ch);
Li=strlen(ch);
int ans=1,L=1,R=1;
for(int i=0;i<Li;i++)
{
if (ch[i]=='L') {ans=(ans+L)%mod;R=(L+R)%mod;}
if (ch[i]=='R') {ans=(ans+R)%mod;L=(L+R)%mod;}
if (ch[i]=='U'&&k)
{
ans=(ans+1)%mod;
if(f[k]==1) L=(L+1)%mod;
else R=(R+1)%mod;
k--;
}
}
printf("Case %d: %d\n",t,ans);
}
return 0;
}
Trending Topic
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<string, int> q[7], sum;
int day = 0, n;
for (char s[31]; ~scanf("%s", s);)
{
if (!strcmp(s, "<text>"))
{
for (const auto &p : q[day])
sum[p.first] -= p.second;
q[day].clear();
for (; scanf("%s", s), strcmp(s, "</text>");)
if (strlen(s) > 3)
++q[day][s];
for (const auto &p : q[day])
sum[p.first] += p.second;
if (++day > 6)
day = 0;
}
else
{
scanf("%d%s", &n, s);
cout << "<top " << n << ">\n";
vector<pair<int, string>> v;
for (const auto &p : sum)
if (p.second)
v.emplace_back(-p.second, p.first);
sort(v.begin(), v.end());
while (n < v.size() && v[n].first == v[n - 1].first)
++n;
for (int i = 0; i < n && i < v.size(); ++i)
cout << v[i].second << ' ' << -v[i].first << '\n';
cout << "</top>\n";
}
}
}