本文主要是介绍2014多校联合十（HDU 4972 HDU 4973 HDU 4974 HDU 4975），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 4972 A simple dynamic programming problem
题意：篮球比赛有1、2、3分球 现给出两队的分差序列（5：3 分差2 3：5分差也是2） 问有多少种可能的比分
思路：
比较简单的想法题 可以类一张表“从分差x到分差y一共有几种情况” 很容易发现只有1->2和2->1的时候会多一种情况 其他均是一种 所以只需要统计这种特殊分差即可 注意一下最后结果要不要乘2 如果最后分差是0就不用因为x:x只有一种 但是最后分差不是0就要乘 因为x:y和y:x算两种 还有本题有坑！！ 那个SB记分员会把分数记错 所以一旦记错种类数就为0了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;int a[100010];int main()
{int t,n,i,l,flag,cas=1;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&a[i]);a[0]=0;l=1;flag=1;for(i=1;i<=n;i++){if(abs(a[i]-a[i-1])>3||(a[i]!=1&&a[i]==a[i-1])){flag=0;break;}if(a[i-1]==1&&a[i]==2||a[i-1]==2&&a[i]==1) l++;}printf("Case #%d: ",cas++);if(!flag){printf("0\n");}else{if(a[n]==0)printf("%d\n",l);else printf("%d\n",l*2);}}return 0;
}HDU 4973 A simple simulation problem
题意：一段区间一开始是1、2、3…n 有m个操作 D操作为区间复制 Q为查询区间最多的相同元素个数
思路：
一看就是线段树… 由于区间会复制 所以自然会想到节点记得是元素个数 比较有意思的是寻找区间方式和以往不同 不过既然已经记录了元素个数 我们就可以按个数来寻找了 我是用(head,num)表示该区间从第head个元素开始操作num个元素 这样就可以实现在线段树上找区间了 注意的是叶子节点特殊处理一下就好
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define N 50010
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)struct node
{LL sum,max,lazy;bool leaf;
}f[N*4];
int t,n,m;void up(int i)
{f[i].sum=f[L(i)].sum+f[R(i)].sum;f[i].max=max(f[L(i)].max,f[R(i)].max);
}void down(int i)
{if(f[i].lazy!=1){f[L(i)].sum*=f[i].lazy;f[L(i)].max*=f[i].lazy;f[L(i)].lazy*=f[i].lazy;f[R(i)].sum*=f[i].lazy;f[R(i)].max*=f[i].lazy;f[R(i)].lazy*=f[i].lazy;f[i].lazy=1;}
}void init(int l,int r,int i)
{f[i].leaf=false;f[i].lazy=1;if(l==r){f[i].leaf=true;f[i].sum=f[i].max=1;return ;}int mid=(l+r)>>1;init(l,mid,L(i));init(mid+1,r,R(i));up(i);
}void update(LL head,LL num,int i)
{if(head==1&&num==f[i].sum){f[i].sum*=2;f[i].max*=2;f[i].lazy*=2;return ;}if(f[i].leaf){f[i].sum+=num;f[i].max+=num;return ;}down(i);if(f[L(i)].sum>=head+num-1) update(head,num,L(i));else if(head>f[L(i)].sum) update(head-f[L(i)].sum,num,R(i));else{LL fzc=f[L(i)].sum-head+1;update(head,fzc,L(i));update(1,num-fzc,R(i));}up(i);
}LL query(LL head,LL num,int i)
{if(head==1&&num==f[i].sum) return f[i].max;if(f[i].leaf) return num;down(i);LL res;if(f[L(i)].sum>=head+num-1) res=query(head,num,L(i));else if(head>f[L(i)].sum) res=query(head-f[L(i)].sum,num,R(i));else{LL fzc=f[L(i)].sum-head+1;res=query(head,fzc,L(i));res=max(res,query(1,num-fzc,R(i)));}up(i);return res;
}int main()
{int i,cas=1;LL l,r;char op[3];scanf("%d",&t);while(t--){printf("Case #%d:\n",cas++);scanf("%d%d",&n,&m);init(1,n,1);while(m--){scanf("%s%I64d%I64d",op,&l,&r);if(op[0]=='D') update(l,r-l+1,1);else printf("%I64d\n",query(l,r-l+1,1));}}return 0;
}HDU 4974 A simple water problem
题意：你可以每次选1个或2个元素使它们+1 问 最少几次操作能从全0加到给出的序列
思路：
一开始一定2个加一次 如果最后只剩下一个就只能1个加一次 所以特判一下最大的元素会不会超过其他元素的和
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;LL a,b,c,ans;
int T,t,n;int main()
{int i;scanf("%d",&T);for(t=1;t<=T;t++){scanf("%d",&n);a=b=c=0;for(i=1;i<=n;i++){scanf("%I64d",&a);c=max(c,a);b+=a;}a=b-c;if(c>=a) ans=c;else{ans=b/2;if(ans*2<b) ans++;}printf("Case #%d: %I64d\n",t,ans);}return 0;
}HDU 4975 这是个错题… 题意就是HDU 4888
思路：
这题标程的搜索就是错的 错误的方式可以用HDU 4888的数据来hack 说一下怎么解决错题 - -b 要么你和它一样错… 要么就是你网络流跑的快一点 为暴搜留出时间 这样兴许可以搜过去！！
代码：（我写的是和它一样错的… 只要是错的代码 跑的比标程都快… 建议本题别做！！）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int MAXN = 1010;
const int MAXM = 1010 * 1010 * 2;
const int INF = 2000000000;struct Node {int from, to, next, cap;
} edge[MAXM];
int tol, n;
int head[MAXN], dep[MAXN], gap[MAXN], sumx[MAXN], sumy[MAXN], vis[MAXN];void addedge(int u, int v, int w) {edge[tol].from = u;edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];head[u] = tol++;edge[tol].from = v;edge[tol].to = u;edge[tol].cap = 0;edge[tol].next = head[v];head[v] = tol++;
}
int que[MAXN];
void BFS(int start, int end) {memset(dep, -1, sizeof(dep));memset(gap, 0, sizeof(gap));gap[0] = 1;int front, rear, u, v, i;front = rear = 0;dep[end] = 0;que[rear++] = end;while (front != rear) {u = que[front++];for (i = head[u]; i != -1; i = edge[i].next) {v = edge[i].to;if (dep[v] != -1)continue;que[rear++] = v;dep[v] = dep[u] + 1;++gap[dep[v]];}}
}
int cur[MAXN], S[MAXN];
int SAP(int start, int end) {int i, u, res = 0, top = 0, temp, inser;BFS(start, end);memcpy(cur, head, sizeof(head));u = start;while (dep[start] < n) {if (u == end) {temp = INF;for (i = 0; i < top; i++)if (temp > edge[S[i]].cap) {temp = edge[S[i]].cap;inser = i;}for (i = 0; i < top; i++) {edge[S[i]].cap -= temp;edge[S[i] ^ 1].cap += temp;}res += temp;top = inser;u = edge[S[top]].from;}if (u != end && gap[dep[u] - 1] == 0)break;for (i = cur[u]; i != -1; i = edge[i].next)if (edge[i].cap != 0 && dep[u] == dep[edge[i].to] + 1)break;if (i != -1) {cur[u] = i;S[top++] = i;u = edge[i].to;} else {int min = n;for (i = head[u]; i != -1; i = edge[i].next) {if (edge[i].cap == 0)continue;if (min > dep[edge[i].to]) {min = dep[edge[i].to];cur[u] = i;}}--gap[dep[u]];dep[u] = min + 1;++gap[dep[u]];if (u != start)u = edge[S[--top]].from;}}return res;
}bool sol(int u, int fa) {int i, v;vis[u] = 1;for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (!edge[i].cap || v == fa || vis[v] == 2)continue;if (vis[v] == 1 || sol(v, u))return true;}vis[u] = 2;return false;
}bool findcircle(int fn) {for (int i = 1; i <= fn; i++) {vis[i] = 1;if (sol(i, i))return true;vis[i] = 2;}return false;
}int main() {//freopen("1005.in", "r", stdin);//freopen("1005.txt", "w", stdout);int i, j, n1, n2, ans, End, CAS, fff = 1;scanf("%d", &CAS);while (CAS--) {scanf("%d%d", &n1, &n2);sumx[0] = sumy[0] = 0;for (i = 1; i <= n1; i++) {scanf("%d", &sumx[i]);sumx[0] += sumx[i];}for (i = 1; i <= n2; i++) {scanf("%d", &sumy[i]);sumy[0] += sumy[i];}if (sumx[0] != sumy[0]) {printf("Case #%d: So naive!\n", fff++);continue;}End = n1 + n2 + 1;tol = 0;n = End + 1;for (i = 0; i < n; i++) {head[i] = -1;vis[i] = 0;}for (i = 1; i <= n1; i++) {addedge(0, i, sumx[i]);for (j = 1; j <= n2; j++)addedge(i, n1 + j, 9);}for (i = 1; i <= n2; i++)addedge(n1 + i, End, sumy[i]);ans = SAP(0, End);if (ans != sumx[0])printf("Case #%d: So naive!\n", fff++);else {if (findcircle(n1))printf("Case #%d: So young!\n", fff++);elseprintf("Case #%d: So simple!\n", fff++);}}return 0;
}这篇关于2014多校联合十（HDU 4972 HDU 4973 HDU 4974 HDU 4975）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
