2019 杭电多校（第一场）

本文主要是介绍2019 杭电多校（第一场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

1002 Operation （线性基）

http://acm.hdu.edu.cn/showproblem.php?pid=6579

题意

给你n个数 两个操作，查询l r区间异或最大值 在数组最后面加一数

思路

维护两个数组：
1、b[i][j]存储a[1]到a[i]之间的第j位线性基。
2、pos[i][j]存储最大的l：a[l]使得b[i][j]有值。
对于每一次询问[l,r]:
如果pos[r][j]>=l就代表b[r][j]这一线性基是在[l,r]之间获得的，从高位到低位对可用的线性基进行贪心。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int Base = 30;
const int N = 500005;
int n,q,b[N][Base+5],pos[N][Base+5];//b a[1] - a[i] 第j位线性基//pos 最小的[i]使b[i][j] 有值void get(int x,int r)
{int id = r;for(int i = Base;i >= 0;i--){if((x>>i)&1){if(!b[r][i]){b[r][i] = x;pos[r][i] = id;return ;}if(pos[r][i] < id){swap(pos[r][i],id);swap(x,b[r][i]);}x ^= b[r][i];}}
}
int query(int l,int r)
{int ans = 0;for(int i = Base;i >= 0;i--){if(pos[r][i] >= l){ans = max(ans,ans^b[r][i]);}}return ans;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&q);for(int i = 1;i <= n;i++){int x;scanf("%d",&x);memcpy(b[i],b[i-1],sizeof(b[i]));memcpy(pos[i],pos[i-1],sizeof(pos[i]));get(x,i);}int lastans = 0;while(q--){int id,l,r;scanf("%d",&id);if(id == 0){scanf("%d%d",&l,&r);l = (l^lastans)%n + 1;r = (r^lastans)%n + 1;if(l > r) swap(l,r);lastans = query(l,r);printf("%d\n",lastans);}else{int x;scanf("%d",&x);x = x ^ lastans;n++;memcpy(b[n],b[n-1],sizeof(b[n]));memcpy(pos[n],pos[n-1],sizeof(pos[n]));get(x,n);}}}return 0;
}

 

1004 Vacation

http://acm.hdu.edu.cn/showproblem.php?pid=6581 （思维）

题意

给你n辆车 告诉你车长 速度 距离终点距离 。 不能超车 问最后一辆到达终点需要时间

思路

思维

可以求出每辆车按原速度到达应该到达的地方所需要的时间，取最大值，最大值前面的都能提前到，后面的可以理解为都撞到了这辆车，以相同速度行驶，该车到达时，所有车都能到达指定位置

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{double l,s,v;int id;
} a[1000006];
bool cmp(node a,node b)
{return a.s < b.s;
}
int main()
{int n;while(scanf("%d",&n) != EOF){ll sum = 0;for(int i = 0; i <= n; i++){scanf("%lf",&a[i].l);sum += a[i].l;}for(int i = 0; i <= n; i++){scanf("%lf",&a[i].s);}for(int i = 0; i <= n; i++){scanf("%lf",&a[i].v);a[i].id = i;}sum -= a[0].l;double  time = 0.0;for(int i = n;i >= 0;i--){double t1 = (a[i].s + sum) / a[i].v;sum -= a[i].l;if(i == n) time = t1;else{if(t1 > time){time = t1;}}}printf("%.10lf\n",time);}return 0;
}

1005 Path （网络流）

http://acm.hdu.edu.cn/showproblem.php?pid=6582

题意

给你n个点 m条边，问去掉那些边后，最短路会变大

思路

最短路变大，即最短路的DAG图不连通，即最小割，即最大流

对于每一条边u->v 如果dist[v] - dist[u] == w 这条边就在最短路的DAG图里
代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
ll head[100006],headp[100006];
struct code
{ll to,v,nx;
} edge[200006],path[200006];
ll top,top1;
void addpath(ll s,ll e,ll v)
{path[top1].to=e;path[top1].v=v;path[top1].nx=headp[s];headp[s]=top1++;
}
ll dist[100005],vis[100005];
void spfa(ll n)
{for(ll i=1; i<=n; i++)dist[i]=1e18+5;memset(vis,0,sizeof(vis));queue<ll>p;p.push(1);dist[1]=0;vis[1]=0;while(!p.empty()){ll u=p.front();p.pop();vis[u]=0;for(ll i=headp[u]; i!=-1; i=path[i].nx){ll v=path[i].to;if(dist[v]>dist[u]+path[i].v){dist[v]=dist[u]+path[i].v;if(!vis[v]){p.push(v);vis[v]=1;}}}}
}
void add(ll s,ll e,ll v)
{edge[top].to=e;edge[top].v=v;edge[top].nx=head[s];head[s]=top++;edge[top].to=s;edge[top].v=0;edge[top].nx=head[e];head[e]=top++;
}
ll dap[100006];
bool bfs(ll s,ll e)
{queue<ll>p;memset(dap,0,sizeof(dap));p.push(s);dap[s]=1;while(!p.empty()){ll u=p.front();p.pop();for(ll i=head[u]; i!=-1; i=edge[i].nx){if(edge[i].v>0&&dap[edge[i].to]==0){dap[edge[i].to]=dap[u]+1;if(edge[i].to==e)return true;p.push(edge[i].to);}}}if(dap[e]!=0)return true;elsereturn false;
}
ll dfs(ll u,ll e,ll f)
{if(u==e||f==0)return f;ll temp=f;for(ll i=head[u]; i!=-1; i=edge[i].nx){if(edge[i].v>0&&dap[edge[i].to]==dap[u]+1){ll di=dfs(edge[i].to,e,min(temp,edge[i].v));temp-=di;edge[i].v-=di;edge[i^1].v+=di;if(temp<=0)break;}}if(temp==f)dap[u]=inf;//就这一个剪枝卡超时return f-temp;
}
ll max_flow(ll s,ll e)
{ll ans=0;while(bfs(s,e))ans+=dfs(s,e,inf);return ans;
}
int main()
{ll n,m,x,y,z,t;cin>>t;while(t--){top1=0,top=0;memset(head,-1,sizeof(head));memset(headp,-1,sizeof(headp));cin>>n>>m;for(ll i=0; i<m; i++){cin>>x>>y>>z;addpath(x,y,z);}spfa(n);for(ll i=1; i<=n; i++){for(ll j=headp[i]; j!=-1; j=path[j].nx){if(dist[path[j].to]-dist[i]==path[j].v){add(i,path[j].to,path[j].v);}}}cout<<max_flow(1,n)<<endl;}return 0;
}

 

1009 String （贪心）

http://acm.hdu.edu.cn/showproblem.php?pid=6586

题意

给你一个字符串，问符合要求的字典序最小的字长是什么

要求 1 长度为k 2 把个字母在某一个范围

思路

求后缀和 贪心枚举每一位，验证

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 100005;
char s[maxn];
int num[maxn][30],pos[30],nxt[maxn][30];
int n,k,l[30],r[30],top;
char b[maxn];
int used[maxn];
void init()
{top = 0;memset(used,0,sizeof(used));for(int i = 0;i < 30;i++){num[n+1][i] = 0;pos[i] = -1;}for(int i = n;i >= 1;i--){for(int j = 0;j < 26;j++){num[i][j] = num[i+1][j];nxt[i][j] = pos[j];}pos[s[i]-'a'] = i;num[i][s[i] - 'a']++;}for(int i = 0;i <26;i++){nxt[0][i] = pos[i];}
}
int ok(int x)
{char ch = s[x];int qw = 0;for(int i = 0;i < 26;i++){if(i == ch - 'a'){if(used[i] + 1 > r[i]) return 0;if(used[i] + num[x][i] < l[i]) return 0;if(used[i] + k - top < l[i]) return 0;qw = qw +max(0,l[i]-used[i]-1);}else{if(used[i] + num[x][i] < l[i]) return 0;if(used[i] + k - top - 1< l[i]) return 0;qw = qw + max(0,l[i]-used[i]);}}if(qw > k - top - 1) return 0;return 1;
}int main()
{while(~scanf("%s",s+1)){n = strlen(s+1);scanf("%d",&k);for(int i = 0;i < 26;i++){scanf("%d %d",&l[i],&r[i]);}init();int flag = 1, p = 0;while(1){int flagg = 0;for(int i =0;i < 26;i++){if(nxt[p][i] == -1) continue;if(ok(nxt[p][i])){b[top++] = i + 'a';used[i]++;flagg = 1;p = nxt[p][i];break;}}if(flagg == 0){flag = 0;break;}if(top == k){b[top] = '\0';break;}}if(flag==0) printf("-1\n");else printf("%s\n",b);}return 0;
}

 

这篇关于2019 杭电多校（第一场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---