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）