[模板]杭电多校第一场
据说标题加模板浏览量++
1002 Operation[贪心+线性基]
题目强制在线
一来我就写了一个线段树MLE,仔细一想1.2e8必然MLE
这题求的是\((l,r)\)上的任意数的最大异或和
我们来回忆一下线性基求最大异或和的操作：
将线性基从高位向低位扫，若 xor 上当前扫到的\(pos[j]\)答案变大，就把答案异或上 \(pos[j]\)。
因为从高到低，可以改变当前的第\(j\)位，而以后就没有机会了．改变高的必然比改变低的优．
而本题只需要记录插入最大且最右边改变第\(j\)位的下标．如果这个下标比\(l\)大，那么可以更新\(ans\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 7;
int pos[maxn][32];//每个(1,r)基底
int las[maxn][32];//每个1最右边的位置
void add(int val, int id) {
int k = id;
for (int j = 30; j >= 0; --j) {
pos[id][j] = pos[id - 1][j];
las[id][j] = las[id - 1][j];
}
for (int j = 30; j >= 0; --j) {
if (val >> j) {
if (pos[id][j] == 0) {
pos[id][j] = val;
las[id][j] = k;
break;
}
if (k > las[id][j]) {
swap(las[id][j], k);
swap(val, pos[id][j]);
}
val ^= pos[id][j];
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m, op, u, v;
int l, r;
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
add(x, i);
}
int las_ans = 0;
while (m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d", &u);
u ^= las_ans;
n++;
add(u, n);
} else {
scanf("%d%d", &u, &v);
l = (u ^ las_ans) % n + 1;
r = (v ^ las_ans) % n + 1;
if (l > r) swap(l, r);
las_ans = 0;
for (int j = 30; j >= 0; --j)
if ((las_ans ^ pos[r][j]) > las_ans && las[r][j] >= l)
las_ans ^= pos[r][j];
printf("%d\n", las_ans);
}
}
}
return 0;
}
1004 Vacation[思维]
只看始末状态．
假设车开到不影响杰瑞到达终点的地方就停止．
取一个时间的最大值就是答案．理由：
前面的车比后面快，那影响答案的就是后面的到达时间；如果前面的车比后面慢，那么影响答案的就是前面的车的到达时间，因为他们会接在一起，然后同一时间出发和停止．
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll l[100002], s[100002], v[100002];
int main() {
while (scanf("%lld", &n) != EOF) {
for (ll i = 0; i <= n; ++i) {
scanf("%lld", &l[i]);
}
for (ll i = 0; i <= n; ++i) {
scanf("%lld", &s[i]);
}
for (ll i = 0; i <= n; ++i) {
scanf("%lld", &v[i]);
}
double ans = s[0] * 1.0 / (v[0] * 1.0);
ll tot = 0;
for (ll i = 1; i <= n; ++i) {
tot += l[i];
ans = max(ans, ((tot + s[i]) * 1.0) / (v[i] * 1.0));
}
printf("%.10f\n", ans);
}
return 0;
}
1005 Path[最短路+网络流]
求出所有的最短路径
然后复习一下最小割：https://www.cnblogs.com/smallocean/p/9509817.html
小心爆int
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template<class T>
inline void read(T &res) {
res = 0;
T f = 1;
char c;
c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
const int maxn = 1e4 + 7;
const int maxm = 2e4 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
struct Edge {
int next, to;
ll f;
} e[maxm];
int head[maxn];
ll dep[maxn], tol;
ll ans;
int cur[maxn];
int src, sink, n;
void add(int u, int v, int f) {
tol++;
e[tol].to = v;
e[tol].next = head[u];
e[tol].f = f;
head[u] = tol;
tol++;
e[tol].to = u;
e[tol].next = head[v];
e[tol].f = 0;
head[v] = tol;
}
bool bfs() {
queue<int> q;
for (register int i = 0; i <= n; ++i) dep[i] = -1;
q.push(src);
dep[src] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (register int i = head[now]; i; i = e[i].next) {
if (dep[e[i].to] == -1 && e[i].f) {
dep[e[i].to] = dep[now] + 1;
if (e[i].to == sink)
return true;
q.push(e[i].to);
}
}
}
return false;
}
ll dfs(int x, ll maxx) {
if (x == sink)
return maxx;
for (int &i = cur[x]; i; i = e[i].next) {
if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
ll flow = dfs(e[i].to, min(maxx, e[i].f));
if (flow) {
e[i].f -= flow;
e[i ^ 1].f += flow;
return flow;
}
}
}
return 0;
}
ll dinic(int s, int t) {
ans = 0;
this->src = s;
this->sink = t;
while (bfs()) {
for (register int i = 0; i <= n; ++i)
cur[i] = head[i];
while (ll d = dfs(src, inf))
ans += d;
}
return ans;
}
void init(int n) {
this->n = n;
for (int i = 0; i <= n; ++i)head[i] = 0;
tol = 1;
}
} G;
struct Dijk {
ll dist[maxn];
bool vis[maxn];
struct qnode {
int v;
ll c;
qnode(int _v = 0, ll _c = 0) : v(_v), c(_c) {}
bool operator<(const qnode &r) const {
return c > r.c;
}
};
struct edge {
int v;
ll cost;
edge(int _v = 0, ll _cost = 0) : v(_v), cost(_cost) {}
};
vector<edge> E[maxn];
void add(int u, int v, int w) {
E[u].emplace_back(edge(v, w));
}
void Dijkstra(int n, int start) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; ++i)dist[i] = inf;
priority_queue<qnode> que;
dist[start] = 0;
que.push(qnode(start, 0));
qnode tmp;
while (!que.empty()) {
tmp = que.top();
que.pop();
int u = tmp.v;
if (vis[u])continue;
vis[u] = true;
for (int i = 0; i < E[u].size(); ++i) {
int v = E[tmp.v][i].v;
ll cost = E[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.push(qnode(v, dist[v]));
}
}
}
}
void init(int n) {
for (int i = 0; i <= n; ++i) {
E[i].clear();
}
}
} a;
struct node {
int u, v;
ll w;
} s[maxn];
int main() {
int T;
read(T);
int n, m;
int x, y, z;
while (T--) {
read(n);
read(m);
a.init(n);
for (register int i = 0; i < m; ++i) {
read(x);
read(y);
read(z);
a.add(x, y, z);
s[i].u = x, s[i].v = y, s[i].w = z;
}
a.Dijkstra(n, 1);
G.init(n + 10);
for (register int i = 0; i < m; ++i) {
if (a.dist[s[i].v] - s[i].w == a.dist[s[i].u]) {
G.add(s[i].u, s[i].v, s[i].w);
}
}
printf("%lld\n", G.dinic(1, n));
}
return 0;
}
1009 String[暴力+模拟+合法性判断]
预处理出后缀和
判断某个字符加进来是否合法
非法不加
合法根据上下限以及后缀有多少个字符来判断
#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T &res) {
res = 0;
T f = 1;
char c;
c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
inline void out(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int maxn = 1e5 + 7;
char str[maxn], ans[maxn];
int l[27], r[27];
int sum[maxn][27];
int used[27];
int now;
queue<int> pos[27];
int n, m;
bool check(int id,int p) {
while (!pos[id].empty() && pos[id].front() < now) pos[id].pop();
if (pos[id].empty()) return 0;
int k = pos[id].front();
int cnt = 0;
for (int i = 0; i < 26; ++i) {
if (l[i] > used[i]) {
if (sum[k+1][i] < l[i]-used[i]) return 0;
cnt += l[i] - used[i];
}
}
if (cnt > m-p) return 0;
now = k;
pos[id].pop();
return 1;
}
int main() {
while (scanf("%s%d", str, &m) != EOF) {
n = strlen(str);
for (int i = 0; i < 26; ++i) {
used[i] = 0, sum[n][i] = 0, read(l[i]), read(r[i]);
while (!pos[i].empty())pos[i].pop();
}
for (int i = 0; i < n; ++i) pos[str[i] - 'a'].push(i);
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) sum[i][j] = sum[i + 1][j];
sum[i][str[i] - 'a']++;
}
bool flag = 1;
now = -1;
for (int i = 1, j; i <= m; ++i) {
for (j = 0; j < 26; ++j) {
if (r[j] - used[j] == 0) continue;
used[j]++;
if (check(j,i)) {
ans[i] = 'a' + j;
break;
}
used[j]--;
}
if (j == 26) {
flag = 0;
break;
}
}
if (flag) {
ans[m + 1] = '\0';
printf("%s\n", ans + 1);
} else {
puts("-1");
}
}
return 0;
}
京公网安备 11010502036488号