杭电多校第一场属实恐怖，我连补题的冲动都莫得了。
本来还想说按去年的经验来说，杭电是要比牛客稍微友好那么一丢丢的吧。结果当场打脸，签到题来了个最短路*2+网络流，这谁顶得住啊。
所以这两天都没在补这场，感觉不太适合我 ······ 今天先更新一下好了，这场就先这样罢，太难了。
以下题解包括：
[1002【HDU-6579】 \ 1004【HDU-6581】 \ 1005【HDU-6582】 \ 1009【HDU-6586】 \ 1013【HDU-6590】
]
【1002】 线性基 HDU-6579 Operation
这场之前我是没学过线性基的（其实是刚了两个小时多的签到题没空看）后面听完题目确定是线性基然后怎么算复杂度都算不对，根本没想到还能先求前缀...好吧太菜了
http://acm.hdu.edu.cn/showproblem.php?pid=6579
给定 n 个数的序列和 m 次询问（(sum n leq 10^6,sum m leq 10^6, 0leq x leq 2^{30})）。有 2 种操作，(0 l r) 表示查询区间 ([l, r]) 里（选择一些数的）最大异或和；(1 x) 表示把数值 (x) 插入到序列末尾。查询过程强制在线。
对于线性基来说，需要将出现在序列靠右的数尽可能地放在高位（在插入新数字的时候，需要记录对应位置上数字出现的位置，在找到可插入的位置时，如果新数字比位置上的原数字更靠右，就将原数字放到低位）。
另外还需要两个数组： (cnt\_d[i][j]) 保存 ([1,i]) 区间第 (j) 位线性基的值；(cnt\_pos[i][j]) 保存 ([1,i]) 区间第 (j) 位线性基的位置）。
对于给定的 ([l,r])，从最高位开始，找出 (cnt\_pos[r][j] geq l && (ans igoplus cnt\_d[r][j]) > ans) 的值异或起来就是答案。
ps：本题和 CF1100F 基本一致，除了 CF1100F 没有插入操作。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 5e5+5;
struct Linear_Basis {
int val[30+5];
int pos[30+5];
inline void init() {
memset(val, 0, sizeof(val));
memset(pos, 0, sizeof(pos));
}
inline bool insert(int x, int id) {
for(int i = 30; i >= 0; i--) {
if(x & (1<<i)) {
if(val[i] == 0) {
val[i] = x;
pos[i] = id;
break;
}
if(pos[i] < id) {
swap(pos[i], id);
swap(val[i], x);
}
x ^= val[i];
}
}
}
}LB;
int a[maxn];
int sum_val[maxn][30+5]; // [1,i] 区间第 j 位线性基的值
int sum_pos[maxn][30+5]; // [1,i] 区间第 j 位线性基的位置
int query(int l, int r) {
int ans = 0;
for(int i = 30; i >= 0; i--) {
if(sum_pos[r][i] >= l) {
ans = max(ans, ans^sum_val[r][i]);
}
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
LB.init();
memset(sum_val, 0, sizeof(sum_val));
memset(sum_pos, 0, sizeof(sum_pos));
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
LB.insert(a[i], i);
for(int j = 30; j >= 0; j--) {
sum_val[i][j] = LB.val[j];
sum_pos[i][j] = LB.pos[j];
}
}
int ans = 0;
while(m--) {
int f;
scanf("%d", &f);
if(f == 0) {
int l, r;
scanf("%d%d", &l, &r);
l = (l ^ ans) % n + 1;
r = (r ^ ans) % n + 1;
if(l > r) {
swap(l, r);
}
ans = query(l, r);
printf("%d
", ans);
}
else {
int x;
scanf("%d", &x);
LB.insert(x^ans, ++n);
for(int i = 30; i >= 0; i--) {
sum_val[n][i] = LB.val[i];
sum_pos[n][i] = LB.pos[i];
}
}
}
}
return 0;
}
【1004】 数学 HDU-6581 Vacation
与其说是数学题，还不如说是思维题... 题目很快就读完了，然后所有人被我一说就全怕了，结果看完题解都傻了，当然包括我...
http://acm.hdu.edu.cn/showproblem.php?pid=6581
给定 n+1 辆车，第 0 辆是主角车。给定每辆车车头距离终点线的距离 (s_i)，车身长度 (l_i)，最高速度 (v_i)。距离终点远的车不能超车，如果后车最高速度大于前车，那么他会跟随前车的速度。问主角车车头需要多久能抵达终点线。
比赛的时候想法实在是太复杂了，复杂到我都没想到自己能想到那些奇奇gaygay的情况。
我们只需要分两种情况考虑：
- 对于主角车 0，如果将它前面的车全部去掉，那么可以得到最短用时（(s_0 /v_0)）
- 对于其他车，它的车尾越过停止线时所跑的距离总是 (sum_i = s_i + sum^{i}_{j=1}l_j)，那么主角车花费的时间最短理论时间可能是 (sum_i / v_i)
对于以上两种情况，我们只需要对每种情况取最大值即可，因为最大值是最坏情况，也是满足条件的唯一可能。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e6+5;
struct node {
double l, s, v;
}p[maxn];
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 0; i <= n; i++) {
scanf("%lf", &p[i].l);
}
for(int i = 0; i <= n; i++) {
scanf("%lf", &p[i].s);
}
for(int i = 0; i <= n; i++) {
scanf("%lf", &p[i].v);
}
double ans = p[0].s / p[0].v;
double len = 0;
for(int i = 1; i <= n; i++) {
len += p[i].l;
ans = max(ans, (p[i].s+len)/p[i].v);
}
printf("%f
", ans);
}
return 0;
}
【1005】 最短路+网络流 HDU-6582 Path
最短路+网络流的签到题，群友们tql，人均网络流。
我收获颇丰，成功发现自己的板子 spfa 和 dinic 全是错的...
http://acm.hdu.edu.cn/showproblem.php?pid=6582
给定 n 个节点和 m 条边，边是单向边，每条边都有权值。问要让图的最短路变大的情况下，最少需要删掉多少权值的边。输出最小权值。
正向建图跑最短路，再反向建图跑最短路，这样可以求出每个点对于 起点 和 终点 的距离，然后可以判断那些边是可能存在最短路上的。然后把这些边再建一张图跑网络流即可。
如果读懂题了，其实就是模板题，主要是代码量大...
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
ll inf = 1e15;
const int mod = 1e9 + 7;
const int maxn = 2e4+5;
int tot, n, m, new_tot, _tot;
int head[maxn];
int new_head[maxn];
int _head[maxn];
int vis[maxn], _vis[maxn];
ll dist[maxn];
ll _dist[maxn];
ll MIN;
struct EDGE {
int to, nxt;
ll w;
}edge[maxn], _edge[maxn], new_edge[maxn << 1];
struct node {
int u, v;
ll w;
}temp[maxn];
void addedge(int u, int v, ll w) {
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void _addedge(int u, int v, ll w) {
_edge[_tot].to = v;
_edge[_tot].w = w;
_edge[_tot].nxt = _head[u];
_head[u] = _tot++;
}
void new_addedge(int u, int v, ll w) {
new_edge[new_tot].to = v;
new_edge[new_tot].w = w;
new_edge[new_tot].nxt = new_head[u];
new_head[u] = new_tot++;
}
void spfa(int x) {
queue <int> q;
dist[x] = 0;
vis[x] = 1;
q.push(x);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
if(dist[v] > dist[u] + edge[i].w) {
dist[v] = dist[u] + edge[i].w;
if(vis[v] == 0) {
vis[v] = 1;
q.push(v);
}
}
}
}
}
void _spfa(int x) {
queue <int> q;
_dist[x] = 0;
_vis[x] = 1;
q.push(x);
while(!q.empty()) {
int u = q.front();
q.pop();
_vis[u] = 0;
for(int i = _head[u]; ~i; i = _edge[i].nxt) {
int v = _edge[i].to;
if(_dist[v] > _dist[u] + _edge[i].w) {
_dist[v] = _dist[u] + _edge[i].w;
if(_vis[v] == 0) {
_vis[v] = 1;
q.push(v);
}
}
}
}
}
bool bfs() {
memset(dist, 0, sizeof(dist));
dist[1] = 1;
queue<int> q;
q.push(1);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = new_head[u]; ~i; i = new_edge[i].nxt) {
int v = new_edge[i].to;
if(dist[v] == 0 && new_edge[i].w > 0) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
if(dist[n] != 0) {
return true;
}
return false;
}
ll dfs(int u, ll w) {
if(u == n) {
return w;
}
for(int i = new_head[u]; ~i; i = new_edge[i].nxt) {
int v = new_edge[i].to;
if(dist[v] == dist[u] + 1 && new_edge[i].w != 0) {
ll Min = dfs(v, min(w, new_edge[i].w));
if(Min > 0) {
new_edge[i].w = new_edge[i].w - Min;
new_edge[i^1].w = new_edge[i^1].w + Min;
return Min;
}
}
}
return 0;
}
ll dinic() {
ll ans = 0, t;
while(bfs()) {
while((t = dfs(1, inf)) > 0) {
ans = ans + t;
}
}
return ans;
}
int main() {
// freopen("02.txt","r",stdin);
int t;
scanf("%d", &t);
while(t--) {
new_tot = tot = _tot = 0;
scanf("%d%d", &n, &m);
for(int i = 0; i <= n; i++) {
dist[i] = inf;
_dist[i] = inf;
vis[i] = 0;
_vis[i] = 0;
head[i] = -1;
_head[i] = -1;
new_head[i] = -1;
}
for(int i = 1; i <= m; i++) {
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
temp[i].u = u;
temp[i].v = v;
temp[i].w = w;
addedge(u, v, w);
_addedge(v, u, w);
}
spfa(1);
_spfa(n);
MIN = dist[n];
if(MIN == inf) {
printf("0
");
continue;
}
for(int i = 1; i <= m; i++) {
int u = temp[i].u;
int v = temp[i].v;
ll w = temp[i].w;
if(dist[u] + _dist[v] + w == MIN) {
// cout << u << " " << v << " " << w << endl;
new_addedge(u, v, w);
new_addedge(v, u, 0);
}
}
ll ans = dinic();
printf("%lld
", ans);
}
return 0;
}
【1009】 模拟+单调栈 HDU-6586 String
我发现今年怎么全是单调队列单调栈，我人傻了，今天会明天不会...
http://acm.hdu.edu.cn/showproblem.php?pid=6586
给定一个由小写字母构成的字符串，从中选择一个长度为 k 的子序列，要求26种字母的出现次数满足下面所给的 ([l, r]) （最少出现次数和最多出现次数），并且字典序最小。
字典序最小用单调栈维护，然后就是模拟模拟大模拟...
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5+5;
struct node {
int l, r;
}a[26+5];
char s[maxn];
int sum[maxn][26+5];
int k;
char ans[maxn];
int main() {
while(~scanf("%s%d", s, &k)) {
stack<char> st;
memset(ans, ' ', sizeof(ans));
memset(sum, 0, sizeof(sum));
for(int i = 0; i < 26; i++) {
scanf("%d%d", &a[i].l, &a[i].r);
}
int n = strlen(s);
for(int i = n-1; i >= 0; i--) {
for(int j = 0; j < 26; j++) {
sum[i][j] = sum[i+1][j];
}
int id = s[i] - 'a';
sum[i][id] ++;
}
for(int i = 0; i < n; i++) {
if(k == 0) {
break;
}
int id = s[i] - 'a';
if(a[id].r == 0) { // 最高数量 == 0
continue;
}
int cnt = 0;
a[id].l --;
a[id].r --;
for(int j = 0; j < 26; j++) {
if(a[j].l < 0) {
continue;
}
cnt += a[j].l;
}
// cout << i << " " << cnt << " " << k << endl;
if(cnt > k-1) { // 如果取了这个连最低数量都不能满足
a[id].l ++; // 补回来
a[id].r ++;
continue;
}
while(!st.empty() && st.top() > s[i]) { // 单调栈满足字典序最小
int _id = st.top() - 'a';
if(a[_id].l >= sum[i+1][_id]) { // 最低要求 >= 后面出现过的次数
break;
}
a[_id].l ++;
a[_id].r ++;
k ++;
st.pop();
}
st.push(s[i]);
k --;
}
if(k) {
printf("-1
");
continue;
}
int flag = 0;
for(int i = 0; i < 26; i++) {
if(a[i].l > 0) {
cout << i << " " << a[i].l << endl;
flag = 1;
break;
}
}
if(flag) {
printf("-1
");
continue;
}
int cnt = 0;
while(!st.empty()) {
ans[cnt++] = st.top();
st.pop();
}
for(int i = cnt-1; i >= 0; i--) {
printf("%c", ans[i]);
}
printf("
");
}
return 0;
}
【1013】 凸包相交判定 HDU-6590 Code
题面极长，题意极简，代码...又臭又长
http://acm.hdu.edu.cn/showproblem.php?pid=6590
其实就是给定两种点，问你能不能画一条直线把这两种点分开。
对于这种题我是莫得办法的...我只能把他当做模板记下来...就这样
以下代码来自：https://blog.csdn.net/jerry99s/article/details/97269795
别问我为什么不自己做..因为太懒了其实是看了一下午假题解心态崩了。
#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int tmax=105;
struct Point{
llong x,y;
Point(llong x=0,llong y=0):x(x),y(y){}
Point operator +(Point p)
{
return Point(x+p.x,y+p.y);
}
Point operator -(Point p)
{
return Point(x-p.x,y-p.y);
}
bool operator<(Point p)
{
return x!=p.x?x<p.x:y<p.y;
}
};
llong dot(Point p1,Point p2)
{
return p1.x*p2.x+p1.y*p2.y;
}
llong cross(Point p1,Point p2)
{
return p1.x*p2.y-p2.x*p1.y;
}
int convexHull(Point *P,int n,Point *aim)
{
int i,m=0;
sort(P+1,P+1+n);
for(i=1;i<=n;i++)
{
while(m>=2&&cross(aim[m]-aim[m-1],P[i]-aim[m-1])<=0) m--;
aim[++m]=P[i];
}
int k=m;
for(i=n;i>=1;i--)
{
while(m>k&&cross(aim[m]-aim[m-1],P[i]-aim[m-1])<=0) m--;
aim[++m]=P[i];
}
return m;
}
bool check(Point A,Point *p,int n)
{
int l=1,r=n-2,mid;
while(l<=r)
{
mid=(l+r)>>1;
double a1=cross(p[mid]-p[0],A-p[0]);
double a2=cross(p[mid+1]-p[0],A-p[0]);
if(a1>=0&&a2<=0)
{
if(cross(p[mid+1]-p[mid],A-p[mid])>=0) return true;
return false;
}
else if(a1<0)
r=mid-1;
else l=mid+1;
}
return false;
}
int main()
{
int T,i,n,kind,num0[2],num1[2];
Point data[2][tmax],aim[2][tmax],tmp;
scanf("%d",&T);
while(T--)
{
num0[0]=num0[1]=num1[0]=num1[1]=0;
memset(data,0,sizeof(data));
memset(aim,0,sizeof(aim));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lld%lld%d",&tmp.x,&tmp.y,&kind);
if(kind==1) data[1][++num1[0]]=tmp;
else data[0][++num0[0]]=tmp;
}
num0[1]=convexHull(data[0],num0[0],aim[0]);
num1[1]=convexHull(data[1],num1[0],aim[1]);
bool ok=false;
for(i=1;i<=num0[1];i++)
ok|=check(aim[0][i],aim[1]+1,num1[1]);
for(i=1;i<=num1[1];i++)
ok|=check(aim[1][i],aim[0]+1,num0[1]);
if(!ok) printf("Successful!
");
else printf("Infinite loop!
");
}
return 0;
}