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;
}题意：一段区间一开始是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;
}题意：你可以每次选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 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++);
else
printf("Case #%d: So simple!\n", fff++);
}
}
return 0;
}2014多校联合十（HDU 4972 HDU 4973 HDU 4974 HDU 4975）
原文：http://blog.csdn.net/houserabbit/article/details/38848021