有待搞懂

A. BNU 34067 Pair

题目链接： http://www.bnuoj.com/bnuoj/problem_show.php?pid=34067

#include <iostream>
#include <cstdio>
using namespace std;

int main() 
{
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int res = (2*n-1)/5;
        cout<<res<<endl;
    }
    return 0;
}

B. Codeforces 371D Vessels

题目链接： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38994#problem/H

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <time.h>
#include <queue>
#include <cctype>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#define Mod 1000000007
#define INT 2147483647
#define pi acos(-1.0)
#define eps 1e-3
#define lll __int64
#define ll long long
using namespace std;
#define N 200010

int cap[N],jp[N],a[N];

int main()
{
    int n,m;
    int i,j;
    int op,pos,val;
    int st;
    while(scanf("%d",&n)!=EOF)
    {
        memset(cap,0,sizeof(cap));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            jp[i] = i;
        }
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d",&op);
            if(op == 1)
            {
                scanf("%d%d",&pos,&val);
                st = jp[pos];
                while(cap[st]+val>=a[st]&&st<=n)
                {
                    val -= (a[st]-cap[st]);
                    cap[st] = a[st];
                    st++;
                }
                if(st<=n)
                    cap[st] += val;
                for(j=jp[pos];j<st;j++)
                {
                    jp[j] = st;
                }
                jp[pos] = st;
            }
            else
            {
                scanf("%d",&pos);
                printf("%d
",cap[pos]);
            }
        }
    }
    return 0;
}

C. ZOJ 1518  The Sentence is False

题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39061#problem/F

i&j表示第i个句子的内容是: Sentence j is true. i^j表示第i个句子的内容是: Sentence j is false.

当i&j时 i与j等价，当i^j时 i与j正好相反。利用并查集

若为: i&j 分3中情况: 1. i与j属于同一等价集合下一个循环 2.i与j的对立集合，或j与i的对立集合在同一个等价集合中.输出Inconsistent 3.合并i与j  合并 !i 与!j

若为i^j

合并i 与 !j 合并j 与 !i

最后循环每一个集合，对于每一个集合 取其 和 其对立集合的优集（对的元素多的集合）

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
#define N 1100

int fa[N],opp[N],num[N],vis[N];

void makeset(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i] = i;
        opp[i] = 0;
        num[i] = 1;
    }
}

int findset(int x)
{
    if(x != fa[x])
    {
        fa[x] = findset(fa[x]);
    }
    return fa[x];
}

int main()
{
    int i,j,n,flag,fai,faj,opi,opj,maxi;
    while(scanf("%d",&n)!=EOF && n)
    {
        makeset(n);
        flag = 0;
        for(i=1;i<=n;i++)
        {
            char s1[10],s2[10],s3[10];
            scanf("%s%d%s%s",s1,&j,s2,s3);
            fai = findset(i);
            faj = findset(j);
            if(opp[fai])  //如果i的根有对手，找出对手的根
                opi = findset(opp[fai]);
            else
                opi = 0;
            if(opp[faj])  //如果j的根有对手，找出对手的根
                opj = findset(opp[faj]);
            else
                opj = 0;
            if(s3[0] == 't')  //i说j是true
            {
                if(fai == faj) //如果两个在一个集合，成立
                    continue;
                if(opi == faj || fai == opj) //如果i,j相对，不符合
                {
                    flag = 1;  //出现悖论，Inconsistent
                    continue;
                }
                fa[faj] = fai; //否则合并梁集合
                num[fai] += num[faj]; //权值相加
                if(opi && opj)  //如果对手都有
                {
                    fa[opj] = opi;   //合并对手
                    num[opi] += num[opj];
                }
                else if(opi)    //如果只有i有对手  **
                    opp[faj] = opi;  //j的根的对手赋为i的对手  **
                else if(opj) //如果只有j有对手  **
                    opp[fai] = opj; //i的根的对手赋为j的对手  **
            }
            else  //i说j是错的
            {
                if(opi == faj || opj == fai) //如果本来i和j是相对的，正确，继续
                    continue;
                if(fai == faj)  //如果i和j是一个集合
                {
                    flag = 1;  //悖论
                    continue;
                }
                if(opi)  //如果i有对手，则i的对手和j是一个集合，合并
                {
                    fa[opi] = faj;
                    num[faj] += num[opi];
                }
                else  //i没有对手
                {
                    opp[fai] = faj; //i集合的对手赋为j集合
                }

                if(opj) //如果j有对手，则j的对手和i是一个集合，合并
                {
                    fa[opj] = fai;
                    num[fai] += num[opj];
                }
                else  //j没有对手，则j集合的对手赋为i集合
                {
                    opp[faj] = fai;
                }
            }
        }
        if(flag)
        {
            printf("Inconsistent
");
            continue;
        }
        maxi = 0;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++)
        {
            if(i == fa[i] && !vis[i])
            {
                if(opp[i])
                {
                    opi = findset(opp[i]);
                    maxi += max(num[i],num[opi]); //取每个集合的本集合最大与其对立集合最大，求和
                    vis[opi] = 1;
                }
                else
                    maxi += num[i];
                vis[i] = 1;
            }
        }
        printf("%d
",maxi);
    }
    return 0;
}

D.POJ 1733 Parity game

题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=39052#problem/B

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
#define N 10100

int fa[N],num[N];
map<int,int> mp;

void makeset(int n)
{
    for(int i=1;i<=10000;i++)
    {
        fa[i] = i;
        num[i] = 0;
    }
}

int findset(int x)
{
    if(x != fa[x])
    {
        int tmp = fa[x];
        fa[x] = findset(fa[x]);
        num[x] = num[x]^num[tmp];
    }
    return fa[x];
}

int unionset(int a,int b,char oe)
{
    int x = findset(a);
    int y = findset(b);
    int k = (oe == 'o'? 1:0);
    if(x == y)
    {
        if(num[a]^num[b] == k)
            return 1;
        else
            return 0;
    }
    else
    {
        fa[x] = y;
        num[x] = num[a]^num[b]^k;
        return 1;
    }
}

int main()
{
    int n,m,i,k,a,b,cnt;
    char ss[8];
    scanf("%d%d",&n,&m);
    makeset(n);
    k = 1;
    cnt = 0;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d %s",&a,&b,ss);
        a = a-1;
        if(mp.find(a) == mp.end())
        {
            mp[a] = k++;
        }
        if(mp.find(b) == mp.end())
        {
            mp[b] = k++;
        }
        if(unionset(mp[a],mp[b],ss[0]))
            cnt++;
        else
            break;
    }
    printf("%d
",cnt);
    return 0;
}

E.HDU 1867 A+B for you again

题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40277#problem/K

题意：
        就是求str1 的最长后缀与 str2 的最长前缀。使得 str1+str2  的长度最小，并且字典序最小。
分析：
        利用kmp 求出最长相同的后缀和前缀。在利用串比较函数比较最小字典序。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007

char a[N],b[N];
int next1[N],next2[N];

void getnext(char *ss,int *next)
{
    int i = 0,j = -1;
    next[0] = -1;
    int len = strlen(ss);
    while(i<len)
    {
        if(j == -1 || ss[i] == ss[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

int kmp(char *s1,char *s2,int *next)
{
    int i = 0,j = 0;
    int n = strlen(s1);
    int m = strlen(s2);
    while(i<n)     // 为什么不加上 j<m ?
    {
        if(j == -1 || s1[i] == s2[j])
            i++,j++;
        else
            j = next[j];
    }
    return j;
}

int main()
{
    int ka,kb;
    while(scanf("%s%s",a,b)!=EOF)
    {
        getnext(a,next1);
        getnext(b,next2);
        ka = kmp(a,b,next2);
        kb = kmp(b,a,next1);
        if(ka == kb)
        {
            if(strcmp(a,b)<=0)
                printf("%s%s
",a,b+ka);
            else
                printf("%s%s
",b,a+ka);
        }
        else if(ka>kb)
            printf("%s%s
",a,b+ka);
        else
            printf("%s%s
",b,a+kb);
    }
    return 0;
}

F.2014 Topcoder Algorithm Round 1C --950

概率期望的数学解法。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 57

class RedPaint
{
private:
public:
    double expectedCells(int N)
    {
        double res = 1.0,cur = 1.0;
        int i;
        for(i=1;i<=N;i++)
        {
            if(i%2 == 0)
                cur = cur * (i-1)/i;
            res += cur;
        }
        return res;
    }
};

G.HDU 4358 Boring counting

题解： http://www.cnblogs.com/wangfang20/archive/2013/05/24/3096620.html

四个modify

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <time.h>
#include <cctype>
#include <utility>
#include <numeric>
#include <functional>
#include <iomanip>
#include <sstream>
#define Mod 1000000007
#define SMod m
#define INint 2147483647
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-8
#define lll __int64
#define ll long long
using namespace std;
#define N 100007

struct node
{
    int v,next;
}G[2*N];
struct Query
{
    int ind,l,r;
}Q[N];
int head[2*N],tot,L[N],R[N],weight[N],Time,val[N],c[N],b[N],n,ans[N];
map<int,int> mp;
vector<int> pre[N];

int lowbit(int x) { return x&-x; }
int cmp(Query ka,Query kb) { return ka.r < kb.r; }

void modify(int x,int val)
{
    while(x <= n)
    {
        c[x] += val;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

void addedge(int u,int v)
{
    G[tot].v = v;
    G[tot].next = head[u];
    head[u] = tot++;
}

void dfs(int u)
{
    L[u] = ++Time;
    val[u] = weight[u];
    for(int i=head[u];i!=-1;i=G[i].next)
    {
        int v = G[i].v;
        if(!L[v]) dfs(v);
    }
    R[u] = Time;
}

int main()
{
    int t,k,i,j,cs = 1,u,v,q;
    scanf("%d",&t);
    while(t--)
    {
        mp.clear();
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
            scanf("%d",&weight[i]),b[i] = weight[i];
        sort(b+1,b+n+1);
        int ind = unique(b+1,b+n+1)-b;
        for(i=1;i<=ind;i++) mp[b[i]] = i;
        for(i=1;i<=n;i++)   weight[i] = mp[weight[i]];
        for(i=0;i<=ind;i++)
            pre[i].clear(),pre[i].push_back(0);
        memset(head,-1,sizeof(head));
        memset(c,0,sizeof(c));
        tot = Time = 0;
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1);
        scanf("%d",&q);
        for(i=1;i<=q;i++)
        {
            scanf("%d",&u);
            Q[i].ind = i, Q[i].l = L[u], Q[i].r = R[u];
        }
        sort(Q+1,Q+q+1,cmp);
        j = 1;
        for(i=1;i<=n;i++)
        {
            int v = val[i];
            pre[v].push_back(i);
            int now = pre[v].size()-1;
            if(now >= k)
            {
                if(now > k)
                {
                    modify(pre[v][now-k-1]+1,-1);
                    modify(pre[v][now-k]+1,1);
                }
                modify(pre[v][now-k]+1,1);
                modify(pre[v][now-k+1]+1,-1);
            }
            while(Q[j].r == i)
            {
                ans[Q[j].ind] = getsum(Q[j].l);
                j++;
            }
        }
        printf("Case #%d:
",cs++);
        for(i=1;i<=q;i++)
            printf("%d
",ans[i]);
        if(t) puts("");
    }
    return 0;
}

H. Codeforces 396C On Changing Tree

题解： http://blog.csdn.net/night_raven/article/details/20239019

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <time.h>
#include <cctype>
#include <utility>
#include <numeric>
#include <functional>
#include <iomanip>
#include <sstream>
#define Mod 1000000007
#define SMod m
#define INint 2147483647
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-8
#define lll __int64
#define ll long long
using namespace std;
#define N 600017

int L[N],R[N],Time,n,m,layer,d[N];
lll c[2][N];
int head[N],tot;
struct node
{
    int v,next;
}G[N];

void addedge(int u,int v)
{
    G[tot].v = v;
    G[tot].next = head[u];
    head[u] = tot++;
}

int lowbit(int x) { return x&-x; }

void modify(int num,int x,lll val)
{
    while(x <= 2*n)
    {
        c[num][x] = (c[num][x] + val)%Mod;
        x += lowbit(x);
    }
}

lll getsum(int num,int x)
{
    lll res = 0;
    while(x > 0)
    {
        res = (res + c[num][x])%Mod;
        x -= lowbit(x);
    }
    return res;
}

void dfs(int u,int dep)
{
    L[u] = ++Time;
    d[u] = dep;
    for(int i=head[u];i!=-1;i=G[i].next)
    {
        int v = G[i].v;
        if(!L[v]) dfs(v,dep+1);
    }
    R[u] = ++Time;
}

int main()
{
    int i,j,u,v,op;
    lll x,k;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        memset(head,-1,sizeof(head));
        tot = Time = 0;
        for(i=2;i<=n;i++)
        {
            scanf("%d",&u);
            addedge(u,i);
            addedge(i,u);
        }
        scanf("%d",&m);
        dfs(1,0);
        while(m--)
        {
            scanf("%d%d",&op,&u);
            if(op == 1)
            {
                scanf("%I64d%I64d",&x,&k);
                lll val = (x + d[u]*k)%Mod;
                modify(0,L[u],val);
                modify(0,R[u]+1,-val);

                modify(1,L[u],-k);
                modify(1,R[u]+1,k);
            }
            else
            {
                lll ans = ((getsum(0,L[u])+getsum(1,L[u])*d[u])%Mod+Mod)%Mod;
                printf("%I64d
",ans);
            }
        }
    }
    return 0;
}