浙大月赛 ZOJ Monthly, June 2014

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

134 - ZOJ Monthly, June 2014 2014.6.1

Link: http://acm.zju.edu.cn/onlinejudge/contestInfo.do?contestId=356 现在只会做其中的7题，另外3题留个坑，等待总结！ A： ZOJ3788 Another Recurrence Sequence 坑！！！！待补！ I： ZOJ3796 Left 4 Dead 坑！！！！待补！ J： ZOJ3797 Sister’s Noise 坑！！！！待补！ B： ZOJ3789 Gears 题意就不赘述了！ 简单的带权并查集，很常见的题目。 其中有个删除操作，我是直接新建一个点。

/* ***
Author :kuangbin
Created Time :2014/6/1 13:47:17
File Name :E:\2014ACM\比赛\浙大月赛June2014\B.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 600010;
int F[MAXN];
int num[MAXN];
int val[MAXN];
int find(int x)
{
if(F[x] == -1)return x;
int tmp = find(F[x]);
val[x] = (val[x] + val[F[x]])%2;
return F[x] = tmp;
}
void bing(int x,int y)
{
int t1 = find(x);
int t2 = find(y);
if(t1 != t2)
{
F[t1] = t2;
num[t2] += num[t1];
val[t1] = (val[y]-val[x]+1)%2;
}
}
int a[MAXN];
char op[10];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m;
while(scanf(“%d%d”,&n,&m) == 2)
{
for(int i = 1;i <= n+m;i++)
{
F[i] = -1;
num[i] = 1;
val[i] = 0;
a[i] = i;
}
int now = n+1;
int u,v;
while(m–)
{
scanf(“%s”,op);
if(op[0] == ‘L’)
{
scanf(“%d%d”,&u,&v);
bing(a[u],a[v]);
}
else if(op[0] == ‘D’)
{
scanf(“%d”,&u);
num[find(a[u])]–;
a[u] = now++;
}
else if(op[0] == ‘Q’)
{
scanf(“%d%d”,&u,&v);
if(find(a[u]) == find(a[v]))
{
if(val[a[u]] == val[a[v]])
printf(“Same\n”);
else printf(“Different\n”);
}
else printf(“Unknown\n”);
}
else
{
scanf(“%d”,&u);
printf(“%d\n”,num[find(a[u])]);
}
}
}
return 0;
}

C： ZOJ3790 Consecutive Blocks 题意是给了一个长度为N(1<=N<=10^5)的序列，要求在最多删掉K个数的情况下，得到的连续相等序列长度。 大致思路，就是枚举起点，然后找最右可以到哪个终点组成相等序列，当然两端的数相等，中间不等的数就是要删掉的。 可以二分去查找，复杂度就是 nlogn了 做法就是先离散化一下。 然后把这些数存入不同的vector里面，对每个数进行计算即可。

/* ***
Author :kuangbin
Created Time :2014/6/1 12:22:44
File Name :E:\2014ACM\比赛\浙大月赛June2014\C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
int b[MAXN];
vectorvec[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,k;
while(scanf(“%d%d”,&n,&k) == 2)
{
for(int i = 0;i < n;i++)
{
scanf(“%d”,&a[i]);
b[i] = a[i];
}
sort(b,b+n);
int m = unique(b,b+n) - b;
map<int,int>mp;
for(int i = 0;i < m;i++)
mp[b[i]] = i;
for(int i = 0;i < n;i++)
a[i] = mp[a[i]];
for(int i = 0;i < m;i++)
vec[i].clear();
for(int i =0;i < n;i++)
vec[a[i]].push_back(i);
int ans = 0;
for(int i = 0;i < m;i++)
{
int sz = vec[i].size();
for(int j = 0;j < sz;j++)
vec[i][j] -= j;
for(int j = 0;j < sz;j++)
{
int t = upper_bound(vec[i].begin(),vec[i].end(),vec[i][j]+k) - vec[i].begin();
t–;
ans = max(ans,t-j+1);
}
}
printf(“%d\n”,ans);
}
return 0;
}

D： ZOJ3791 An Easy Game 题意就是给了两个长度为n的01串s1,s2 每步操作必须选择其中的m个数进行翻转。 问经过k步从s1变换到s2的方法数。 很明显的DP。 我是使用dp[i][j] 表示经过i步，变换为j个不同的方法数 初始化是dp[0][cnt] = 1 其中cnt是指原来s1,s2 不同的位数。 最终答案是dp[k][0], 因为经过k步完全要不同。 转移也很简单了，比如现在是dp[i][j] 那么有i位是不同的， n-i位是相同的。 枚举要变换的m位里面有多少个相同，多少个不同。 这样就转移过去了。

/* ***
Author :kuangbin
Created Time :2014/6/1 12:57:31
File Name :E:\2014ACM\比赛\浙大月赛June2014\D.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MOD = 1e9+9;
int C[220][220];
void init()
{
C[0][0] = 1;
for(int i = 1;i <= 200;i++)
{
C[i][0] = C[i][i] = 1;
for(int j = 1;j < i;j++)
{
C[i][j] = C[i-1][j] + C[i-1][j-1];
if(C[i][j] >= MOD)C[i][j] -= MOD;
}
}
}
int n,m,k;
int dp[200][200];
char str1[200],str2[200];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
init();
while(scanf(“%d%d%d”,&n,&k,&m) == 3)
{
scanf(“%s%s”,str1,str2);
int cnt = 0;
for(int i = 0;i < n;i++)
if(str1[i] != str2[i])
cnt++;
memset(dp,0,sizeof(dp));
dp[0][cnt] = 1;
for(int i = 0;i < k;i++)
for(int j = 0;j <= n;j++)
if(dp[i][j])
{
for(int x = 0;x <= j && x <= m;x++)
if(m-x <= n-j)
{
long long tmp = (long long)C[j][x]C[n-j][m-x]%MOD;
tmp = tmpdp[i][j]%MOD;
dp[i+1][j-x+m-x] += tmp;
if(dp[i+1][j-x+m-x]>=MOD)dp[i+1][j-x+m-x] -= MOD;
}
}
printf(“%d\n”,dp[k][0]);
}
return 0;
}

E： [ZOJ3792](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3792) Romantic Value 其实就是求最小割。 最小割等于最大流。 求出的最小割，一个是要求出 割最小，此外还要选择的割边尽量少。   我是把边的权值乘以2000， 然后+1 这样%2000就是最小割的边数， /2000就是最小割了。

/* ***
Author :kuangbin
Created Time :2014/6/1 13:23:33
File Name :E:\2014ACM\比赛\浙大月赛June2014\E.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

const int MAXN = 1010;//点数的最大值
const int MAXM = 40010;//边数的最大值
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow;
}edge[MAXM];//注意是MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{
tol = 0;
memset(head,-1,sizeof(head));
}
//加边，单向图三个参数，双向图四个参数
void addedge(int u,int v,int w,int rw=0)
{
edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];
edge[tol].flow = 0;head[u] = tol++;
edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];
edge[tol].flow = 0;head[v]=tol++;
}
//输入参数：起点、终点、点的总数
//点的编号没有影响，只要输入点的总数
long long sap(int start,int end,int N)
{
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u = start;
pre[u] = -1;
gap[0] = N;
long long ans = 0;
while(dep[start] < N)
{
if(u == end)
{
long long Min = INF;
for(int i = pre[u];i != -1; i = pre[edge[i^1].to])
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
for(int i = pre[u];i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
}
u = start;
ans += Min;
continue;
}
bool flag = false;
int v;
for(int i = cur[u]; i != -1;i = edge[i].next)
{
v = edge[i].to;
if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])
{
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if(flag)
{
u = v;
continue;
}
int Min = N;
for(int i = head[u]; i != -1;i = edge[i].next)
if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
{
Min = dep[edge[i].to];
cur[u] = i;
}
gap[dep[u]]–;
if(!gap[dep[u]])return ans;
dep[u] = Min+1;
gap[dep[u]]++;
if(u != start) u = edge[pre[u]^1].to;
}
return ans;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int n,m,p,q;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d%d%d”,&n,&m,&p,&q);
int sum = 0;
int u,v,w;
init();
while(m–)
{
scanf(“%d%d%d”,&u,&v,&w);
addedge(u,v,w*2000+1,w*2000+1);
sum += w;
}
long long ans = sap(p,q,n);
int ans1 = ans/2000;
int ans2 = ans%2000;
if(ans == 0)printf(“Inf\n”);
else printf(“%.2lf\n”,(double)(sum-ans1)/ans2);
}
return 0;
}

F： ZOJ3793 First Digit 水题。 纯签到，我是全部输出1，然后就 抢了个FB了。

/* ***
Author :kuangbin
Created Time :2014/6/1 12:06:17
File Name :E:\2014ACM\比赛\浙大月赛June2014\F.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
int a,b;
while(T–)
{
scanf(“%d%d”,&a,&b);
printf(“1\n”);
}

return 0;

}

G： ZOJ3794 Greedy Driver 题目比较长，意思不讲了。 我是从起点和终点分别bfs一次。 求出从起点出发，可以达到某一个点剩余的最大油量。 求出 在某一个点剩余最少流量可以到达终点。 两个相减就可以了。

/* ***
Author :kuangbin
Created Time :2014/6/1 14:12:57
File Name :E:\2014ACM\比赛\浙大月赛June2014\G.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 1010;
const int MAXM = 100010;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next;
int w;
}edge[MAXM],redge[MAXM];
int head[MAXN],tot;
int rhead[MAXN],rtot;
void init()
{
memset(head,-1,sizeof(head));
tot = 0;
rtot = 0;
memset(rhead,-1,sizeof(rhead));
}
void addedge(int u,int v,int w)
{
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].w = w;
head[u] = tot++;
redge[rtot].to = u;
redge[rtot].next = rhead[v];
redge[rtot].w = w;
rhead[v] = rtot++;
}
int N,M,C;
bool fuel[MAXN];
int Max[1010],Min[1010];
void bfs1()
{
Max[1] = C;
queue<pair<int,int> >q;
q.push(make_pair(1,C));
while(!q.empty())
{
pair<int,int>tmp = q.front();
q.pop();
int u = tmp.first;
int v = tmp.second;
if(fuel[u])
{
if(Max[u] < C)
{
Max[u] = C;
q.push(make_pair(u,C));
}
}
for(int i = head[u];i != -1;i = edge[i].next)
{
int to = edge[i].to;
if(edge[i].w <= v && Max[to] < v - edge[i].w)
{
Max[to] = v-edge[i].w;
q.push(make_pair(to,v-edge[i].w));
}
}

}

}
void bfs2()
{
queue<pair<int,int> >q;
Min[N] = 0;
q.push(make_pair(N,0));
while(!q.empty())
{
pair<int,int> tmp = q.front();
q.pop();
int u = tmp.first;
int v = tmp.second;
// printf(“%d %d\n”,u,v);
if(fuel[u])
{
if(Min[u] > 0)
{
Min[u] = 0;
q.push(make_pair(u,0));
}
}
for(int i = rhead[u];i != -1;i = redge[i].next)
{
int to = redge[i].to;
if(v + redge[i].w <= C && Min[to] > v + redge[i].w)
{
Min[to] = v + redge[i].w;
q.push(make_pair(to,v+redge[i].w));
}
}
}
}

int c[1010];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
while(scanf(“%d%d%d”,&N,&M,&C) == 3)
{
int u,v,w;
init();
while(M–)
{
scanf(“%d%d%d”,&u,&v,&w);
addedge(u,v,w);
}
memset(fuel,false,sizeof(fuel));
scanf(“%d”,&M);
while(M–)
{
scanf(“%d”,&u);
fuel[u] = true;
}
for(int i =1 ;i <= N;i++)
{
Min[i] = INF;
Max[i] = -INF;
}
bfs1();
bfs2();
//for(int i = 1;i <= N;i++)
// printf(“%d %d**\n”,Min[i],Max[i]);
memset(c,-1,sizeof(c));
scanf(“%d”,&M);
while(M–)
{
scanf(“%d%d”,&u,&v);
c[u] = max(c[u],v);
}
int ans = 0;
for(int i = 1;i <= N;i++)
if(c[i] != -1 && Min[i] != INF && Max[i] != -INF)
{
if(Max[i] >= Min[i])
ans = max(ans,c[i](Max[i] - Min[i]));
}
if(Min[1] > C) ans = -1;
printf(“%d\n”,ans);
}
return 0;
}

H： ZOJ3795 Grouping 使用有向图的强连通分量缩点吗， 然后求出一条最长链，就是答案了。

/* ***
Author :kuangbin
Created Time :2014/6/1 12:37:28
File Name :E:\2014ACM\比赛\浙大月赛June2014\H.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
/*
* Tarjan算法
* 复杂度O(N+M)
*/
const int MAXN = 100010;//点数
const int MAXM = 300010;//边数
struct Edge
{
int to,next;
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
int Index,top;
int scc;//强连通分量的个数
bool Instack[MAXN];
int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc
//num数组不一定需要，结合实际情况

void addedge(int u,int v)
{
edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}
void Tarjan(int u)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for(int i = head[u];i != -1;i = edge[i].next)
{
v = edge[i].to;
if( !DFN[v] )
{
Tarjan(v);
if( Low[u] > Low[v] )Low[u] = Low[v];
}
else if(Instack[v] && Low[u] > DFN[v])
Low[u] = DFN[v];
}
if(Low[u] == DFN[u])
{
scc++;
do
{
v = Stack[–top];
Instack[v] = false;
Belong[v] = scc;
num[scc]++;
}
while( v != u);
}
}
void solve(int N)
{
memset(DFN,0,sizeof(DFN));
memset(Instack,false,sizeof(Instack));
memset(num,0,sizeof(num));
Index = scc = top = 0;
for(int i = 1;i <= N;i++)
if(!DFN[i])
Tarjan(i);
}
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
int dp[MAXN];
vectorvec[MAXN];

int dfs(int u)
{
if(dp[u] != -1)return dp[u];
dp[u] = num[u];
for(int i = 0;i < vec[u].size();i++)
{
int v = vec[u][i];
dp[u] = max(dp[u],num[u] + dfs(v));
}
return dp[u];
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m;
while(scanf(“%d%d”,&n,&m) == 2)
{
init();
int u,v;
for(int i = 0;i < m;i++)
{
scanf(“%d%d”,&u,&v);
addedge(u,v);
}
solve(n);
for(int i = 1;i <= scc;i++)vec[i].clear();
for(u = 1;u <= n;u++)
{
for(int i = head[u];i != -1;i = edge[i].next)
{
v = edge[i].to;
if(Belong[u] != Belong[v])
{
vec[Belong[u]].push_back(Belong[v]);
}
}
}
int ans = 0;
memset(dp,-1,sizeof(dp));
for(int i = 1;i <= scc;i++)
ans = max(ans,dfs(i));
printf(“%d\n”,ans);
}
return 0;
}

------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 146.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%