计蒜客 ACM-ICPC 2017 Warmup Contest 12

计蒜客 ACM-ICPC 2017 Warmup Contest 12

因为等了很久计蒜客上都没有更新，所以目前找不到题目，只能凭借记忆写写咯

问题链接：​​rk2 ，一定是高手都没有来参加的缘故。

A. Abandoned Animal

题意

给定一些商品可以在第几家店买的，然后输入购买商品的顺序，问购买序列是否唯一（要求第几家序号不下降）。

若唯一，输出 ​​unique​​​ ，不唯一输出 ​​ambiguous​​​ ，不存在时输出 ​​impossible​​ 。

思路

找一个序号尽可能小的合法序列与一个序号尽可能大的合法序列，若这两个序列相等则结果唯一，否则不唯一。

若无法找到这样的序列则结果不存在。

寻找下一个可行序号的过程可以用二分优化。

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e5+10;const int mod = 1e9+7;unordered_map g[maxn];vector lef,rig;int n,m,k,tot;int solve(){ int now = 0; for(int i=0; i& tmp = g[mp[fi[i]]]; auto s = lower_bound(tmp.begin(),tmp.end(),now) - tmp.begin(); if(s>=(int)tmp.size())return 0; now = tmp[s]; lef.push_back(now); } now = *g[mp[fi[m-1]]].rbegin(); for(int i=m-1; i>=0; i--) { vector &tmp = g[mp[fi[i]]]; auto s = upper_bound(tmp.begin(),tmp.end(),now) - tmp.begin() - 1; if(s<0||s>=(int)tmp.size())return 0; now = tmp[s]; rig.push_back(now); } for(int i=0; i>n>>k; for(int i=0; i>id>>tmp; if(!mp.count(tmp)) mp[tmp] = tot++; g[mp[tmp]].push_back(id); } for(int i=0; i>m; bool flag = false; for(int i=0; i>fi[i]; if(!mp.count(fi[i])) flag = true; } int op = solve(); if(op==0||flag) cout<<"impossible"<

C. Crowd Control

题意

给定一张图，每条边都有它的流量，问从节点 0 到节点 n-1 最大流量的这条路径上需要剪掉哪些边才可以使得流不散失。

思路

乍看可能是最大流的题目，但是没有想到与它有什么关联。

因为节点的数目只有 1000 ，所以我考虑直接 bfs ，寻找一条最大流的路径，然后遍历该条路径判断哪些边可剪。

奇怪的是如果一些边剪掉可以使得流从这里断掉，然后其他一些边可以不剪的情况应该怎么办，两个样例的结果让人费解。

我的代码最后返回的内存超限，一定是数组开太大的缘故，本来以外是 WA ，就没有再提交看看，先存一下代码，等找的题目以后再改。

内存超限 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e6+10;struct node{public: int to; int next; int cap; int id; node() {} node(int t,int n,int c,int i):to(t),next(n),cap(c),id(i) { }} edge[maxn];int head[maxn],tot;int n,m;void init(){ memset(head,-1,sizeof(head)); tot=0;}struct N{ int cap; int last; int now; N() {} N(int c,int l,int n) { cap = c; last = l; now = n; }} tmp[maxn<<2];int top;void addedge(int u,int v,int cap,int id){ edge[tot].to = v; edge[tot].cap = cap; edge[tot].id = id; edge[tot].next = head[u]; head[u] = tot++;}int vis[maxn];void bfs(){ memset(vis,0,sizeof(vis)); queue sk; tmp[top] = N(500000,-1,0); sk.push(top++); int maxflow = 0,ans = 0; while(!sk.empty()) { int p = sk.front(); sk.pop(); if(tmp[p].now==n-1) { if(maxflowvis[u]) vis[u] = tmp[p].cap; else continue; } vis[u] = tmp[p].cap;// cout< path; int now = ans; while(now!=-1) { path.push_back(tmp[now].now); now = tmp[now].last; } reverse(path.begin(),path.end()); vector ak; for(int i=0;i<(int)path.size()-1;i++) { for(int k=head[i];k!=-1;k=edge[k].next) { if(edge[k].to!=path[i+1]) {// cout<>n>>m; init(); for(int i=0; i>u>>v>>cap; addedge(u,v,cap,i); addedge(v,u,cap,i); } bfs(); return 0;}

D. Disastrous Doubling

题意

研究人员需要使用某种细菌进行实验，给定一个序列代表接下来每个小时所用的细菌数目，已知初始时细菌的数目为 1 ，其数目每小时会翻倍增长，并且等到第一个小时以后开始实验，问最后残余的细菌数目。

思路

因为细菌的数目可能会呈指数级上升，所以首先要想到大数。

然后用 java 模拟一下即可，最后别忘了 mod 1e9+7 （所以因为这个 WA 了一次，果然不在状态）。

AC 代码

import java.math.BigInteger;import java.util.Scanner;public class Main static BigInteger b[] = new BigInteger[110000]; static BigInteger mo = new BigInteger("1000000007"); private static Scanner cin; public static void main(String[] args) { cin = new Scanner(System.in); int n; n = cin.nextInt(); BigInteger now = BigInteger.ONE; boolean flag = true; for (int i = 0; i < n; i++) { now = now.add(now); b[i] = cin.nextBigInteger(); if (now.compareTo(b[i]) < 0) { flag = false; } now = now.subtract(b[i]); } if (!flag) { System.out.println("error"); } else

E. Envious Exponents

题意

给定两个数 n 与 k ，问比 n 大的最小的哪个数字其二进制 1 的个数为 k 。

思路

我们设 count 代表 n 二进制中 1

假如 count

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e5+10;const int mod = 1e9+7;LL n,k;bitset<100> ks;int main(){ IO; cin>>n>>k; ks = n; if(ks.count()

H. Horror Film Night

题意

两个人想一起看电影，给出 A 和 B 分别喜欢看的电影所播放的时间，每天只有一场电影，并且每个人都不想连续两次看自己不喜欢的电影，问最多可以挑选多少场电影共同观看。

思路

既然是挑选一个子序列的问题，那当然区间长度越大越好啦~

用数组做桶分别记录 A 和 B 喜欢电影的播放时间，从 0 开始枚举时间到最大，记录上一次看的是谁喜欢的电影。

若喜欢当前电影的人与上一次相同则跳过，否则 ans+1

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 2e6 + 10;const int mod = 1e9+7;int a[maxn],b[maxn];int main(){ IO; int n,m; cin>>n; for(int i=0; i>x; a[x] = 1; } cin>>m; for(int i=0; i>x; b[x] = 1; } int ans = 0,last = 0; for(int i=0; i

K. Knight’s Marathon

题意

给出一个 n×m 的棋盘，问马从 (x1,y1) 到 (x2,y2) 所需要跳的最少步数。 (8<=n,m<=109)

思路

在 HDU 3766 Knight’s Trip 我们做过一个马在无限大的棋盘上两点间跳跃所需要的最少步数，与这道题唯一的不同即地图的范围。

仔细想想可以知道，从 (x1,y1) 到 (x2,y2)

于是我们可以先让给定点向地图中心靠近一步，然后问题就等同于那道原题啦。

AC 代码

#includeusing namespace std;typedef long long LL;LL solve(LL m,LL n){ if(m>n)swap(m,n); if(2LL*m>=n) { if(m==n&&m==1) return 2; else if(m==n&&m==2) return 4; else return (m+n)/3+(m+n)%3; } else { LL ans=m; LL c=(n-2*m)%4; ans+=c; ans+=(n-2*m-c)/2; if(n==1&&m==0) ans=3; return ans; }}LL lx,ly;LL xx1,xx2,yy1,yy2;const int mv[8][2]= {{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};typedef pair P;P a[100],b[100];int tota,totb;void init(){ for(int i=0; i<8; i++) { int xi = xx1+mv[i][0]; int yi = yy1+mv[i][1]; if(xi<0||yi<0||xi>=lx||yi>=ly)continue; a[tota++] = P(xi,yi); } for(int i=0; i<8; i++) { int xi = xx2+mv[i][0]; int yi = yy2+mv[i][1]; if(xi<0||yi<0||xi>=lx||yi>=ly)continue; b[totb++] = P(xi,yi); } if(xx1==xx2&&yy1==yy2) { cout<<0<>lx>>ly; cin>>xx1>>yy1; cin>>xx2>>yy2; init(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。