题意：

n个点，m条边，两个人，A在点1处，B在点n处，A必须走最短路到达n点（只走最短路，最短路可能多条）

B切断图中的某些边不让A到达n点

问：1.B最少切断多少边使A不能到达n点

       2.B最多切断多少边使A还能达到n点

分析：

问题1求最小割，根据最大流最小割定理，利用最大流求得，流量是1（边数）

对于问题2，只需在所有的最短路中找到边数最少的，然后用总边数m减去最少边的最短路上的边数
解法：

以给出的边权求最短路，根据最短路建图，判断边是否在最短路里面：d[v] - d[u] == w(u,v)

根据所建的新图，再求最短路（求最短路中的最少边数），每条边的权值变为1，

根据新图求最大流，流量为1（即最小割里的边权是1，是边数）

说明：代码很长不过都是模板，最大流的bfs、dfs模板都可以，最短路用的SPFA模板（很奇怪用Dijkstra怎么都过不了，不是超时而是WA。。。）

代码：dfs版增广路：

1.#define mem(a,x) memset(a,x,sizeof(a)) 

2.#include<iostream> 

3.#include<cstdio> 

4.#include<cstring> 

5.#include<algorithm> 

6.#include<queue> 

7.#include<set> 

8.#include<stack> 

9.#include<cmath> 

10.#include<map> 

11.#include<stdlib.h> 

12.#include<cctype> 

13.#include<string> 

14.using namespace std; 

15.typedef long long ll; 

16.const int N = 2000; 

17.const int inf = 1 << 27; 

18.const int M = 120000; 

19./****************************************最大流模板*********************************************/ 

20.struct Edge 

21.{ 

22.    int to;//终点 

23.    int cap;//容量 

24.    int rev;//反向边 

25.    Edge (int to = 0, int cap = 0, int rev = 0) : to (to), cap (cap), rev (rev) {} 

26.}; 

27.struct EdmondsKarp 

28.{ 

29.    bool used[M + 5]; 

30.    vector<Edge>v[M + 5]; 

31.    void AddEdge (int from, int to, int cap) 

32.    { 

33.        v[from].push_back (Edge (to, cap, v[to].size() ) ); 

34.        v[to].push_back (Edge (from, 0, v[from].size() - 1) ); 

35.    } 

36.    int dfs (int s, int t, int f) 

37.    { 

38.        if (s == t) return f; 

39.        used[s] = 1; 

40.        for (int i = 0; i < v[s].size(); ++i) 

41.        { 

42.            Edge &tmp = v[s][i];//引用 

43.            if (!used[tmp.to] && tmp.cap > 0) 

44.            { 

45.                int d = dfs (tmp.to, t, min (f, tmp.cap) ); 

46.                if (d > 0) 

47.                { 

48.                    tmp.cap -= d; 

49.                    v[tmp.to][tmp.rev].cap += d; 

50.                    return d; 

51.                } 

52.            } 

53.        } 

54.        return 0; 

55.    } 

56.    int MaxFlow (int s, int t) //求源点汇点的最大流 

57.    { 

58.        int flow = 0; 

59.        while (1) //一直循环直到找不到增广路 

60.        { 

61.            mem (used, 0); 

62.            int f = dfs (s, t, inf); 

63.            if (f == 0) return flow; 

64.            flow += f; 

65.        } 

66.    } 

67.} q; 

68./***************************************最短路模板*****************************************/ 

69.struct Node 

70.{ 

71.    int v, w; 

72.    Node (int v = 0,int w = 0):v(v),w(w){} 

73.}; 

74.struct Spfa 

75.{ 

76.    int d[N+5]; 

77.    bool vis[N+5]; 

78.    queue<int>q; 

79.    vector<Node>u[N+5]; 

80.    void init(int n) 

81.    { 

82.        while (!q.empty()) q.pop(); 

83.        for (int i = 0;i <= n;++i) u[i].clear(); 

84.        mem(vis,0); 

85.    } 

86.    void AddEdge(int uu,int vv,int ww) 

87.    { 

88.        u[uu].push_back(Node(vv,ww)); 

89.        u[vv].push_back(Node(uu,ww)); 

90.    } 

91.    int spfa(int s, int t,int n) 

92.    { 

93.        for (int i = 0; i <= n; ++i) d[i] = inf; 

94.        q.push (s); 

95.        vis[s] = 1; 

96.        d[s] = 0; 

97.        while (!q.empty() ) 

98.        { 

99.            int h = q.front(); 

100.            q.pop(); 

101.            vis[h] = 0;//spfa不同于bfs 

102.            for (int i = 0; i < u[h].size(); ++i) 

103.            { 

104.                int &v = u[h][i].v, &w = u[h][i].w; 

105.                if (d[v] > d[h] + w) 

106.                { 

107.                    d[v] = d[h] + w; 

108.                    if (!vis[v]) 

109.                    { 

110.                        q.push (v); 

111.                        vis[v] = 1; 

112.                    } 

113.                } 

114.            } 

115.        } 

116.        return d[t]; 

117.    } 

118.} d,g; 

119. 

120./****************************************以最短路建图*********************************/ 

121.void make_map (int n) 

122.{ 

123.    for (int i = 1; i <= n; ++i) 

124.    { 

125.        for (int j = 0;j < d.u[i].size();++j) 

126.        { 

127.            int v = d.u[i][j].v, w = d.u[i][j].w; 

128.            if (d.d[v] - d.d[i] == w) 

129.            { 

130.                q.AddEdge(i,v,1);//最大流，流量是1 

131.                g.AddEdge(i,v,1);//最短路，边权是1 

132.            } 

133.        } 

134.    } 

135.} 

136./************************************************************************************/ 

137.int main() 

138.{ 

139.    int n, m; 

140.    while (~scanf ("%d %d", &n, &m) ) 

141.    { 

142.        d.init (n); 

143.        g.init (n); 

144.        mem (q.v, 0); 

145.        mem (q.used,0); 

146.        for (int i = 0, u, v, w; i < m; ++i) 

147.        { 

148.            scanf ("%d %d %d", &u, &v, &w); 

149.            d.AddEdge (u, v, w); 

150.        } 

151.        int minway = d.spfa (1, n, n); 

152.        make_map (n); 

153.        int ans1 = q.MaxFlow (1, n); 

154.        int ans2 = m - g.spfa (1, n, n); 

155.        printf ("%d %d\n", ans1, ans2); 

156.    } 

157.    return 0; 

158.} 

159./* 

160. 

161.7 12 

162.1 2 1 

163.2 7 8 

164.1 7 8 

165.1 6 7 

166.6 7 1 

167.2 3 3 

168.3 6 3 

169.6 4 1 

170.7 4 2 

171.1 5 2 

172.5 4 4 

173.7 5 6 

174. 

175.*/ 
bfs版的增广路：

1.#define mem(a,x) memset(a,x,sizeof(a)) 

2.#include<iostream> 

3.#include<cstdio> 

4.#include<cstring> 

5.#include<algorithm> 

6.#include<queue> 

7.#include<set> 

8.#include<stack> 

9.#include<cmath> 

10.#include<map> 

11.#include<stdlib.h> 

12.#include<cctype> 

13.#include<string> 

14.using namespace std; 

15.typedef long long ll; 

16.const int N = 2000; 

17.const int inf = 1<<27; 

18.struct Node 

19.{ 

20.    int v, w; 

21.    Node (int v = 0,int w = 0):v(v),w(w){} 

22.}; 

23.struct Spfa 

24.{ 

25.    int d[N+5]; 

26.    bool vis[N+5]; 

27.    queue<int>q; 

28.    vector<Node>u[N+5]; 

29.    void init(int n) 

30.    { 

31.        while (!q.empty()) q.pop(); 

32.        for (int i = 0;i <= n;++i) u[i].clear(); 

33.        mem(vis,0); 

34.    } 

35.    void AddEdge(int uu,int vv,int ww) 

36.    { 

37.        u[uu].push_back(Node(vv,ww)); 

38.        u[vv].push_back(Node(uu,ww)); 

39.    } 

40.    int spfa(int s, int t,int n) 

41.    { 

42.        for (int i = 0; i <= n; ++i) d[i] = inf; 

43.        q.push (s); 

44.        vis[s] = 1; 

45.        d[s] = 0; 

46.        while (!q.empty() ) 

47.        { 

48.            int h = q.front(); 

49.            q.pop(); 

50.            vis[h] = 0;//spfa不同于bfs 

51.            for (int i = 0; i < u[h].size(); ++i) 

52.            { 

53.                int &v = u[h][i].v, &w = u[h][i].w; 

54.                if (d[v] > d[h] + w) 

55.                { 

56.                    d[v] = d[h] + w; 

57.                    if (!vis[v]) 

58.                    { 

59.                        q.push (v); 

60.                        vis[v] = 1; 

61.                    } 

62.                } 

63.            } 

64.        } 

65.        return d[t]; 

66.    } 

67.} d,g; 

68.struct Edge 

69.{ 

70.    int from, to, cap, flow; 

71.    Edge (int u = 0, int v = 0, int c = 0, int f = 0) : from (u), to (v), cap (c), flow (f) {} 

72.}; 

73.struct EdmondsKarp 

74.{ 

75.    int n, m; 

76.    vector<Edge>edges;//边数的两倍 

77.    vector<int>G[N+5];//邻接表，G[i][j]表示节点i的第j条边在e数组中的序号 

78.    int a[N+5];//当起点到i的可改进量 

79.    int p[N+5];//最短路树上p的入弧编号 

80.    void init (int n) 

81.    { 

82.        for (int i = 0; i <= n; ++i) G[i].clear(); 

83.        edges.clear(); 

84.    } 

85.    void AddEdge (int from, int to, int cap) 

86.    { 

87.        edges.push_back (Edge (from, to, cap, 0) ); 

88.        edges.push_back (Edge (to, from, 0, 0) ); //反向弧 

89.        m = edges.size(); 

90.        G[from].push_back (m - 2); 

91.        G[to].push_back (m - 1); 

92.    } 

93.    int MaxFlow (int s, int t) 

94.    { 

95.        int flow = 0; 

96.        while (1) 

97.        { 

98.            mem (a, 0); 

99.            queue<int>Q; 

100.            Q.push (s); 

101.            a[s] = inf; 

102.            while (!Q.empty() ) 

103.            { 

104.                int x = Q.front(); 

105.                Q.pop(); 

106.                for (int i = 0; i < G[x].size(); ++i) 

107.                { 

108.                    Edge & e = edges[G[x][i]]; 

109.                    if (!a[e.to] && e.cap > e.flow) 

110.                    { 

111.                        p[e.to] = G[x][i]; 

112.                        a[e.to] = min (a[x], e.cap - e.flow); 

113.                        Q.push (e.to); 

114.                    } 

115.                } 

116.                if (a[t]) break; 

117.            } 

118.            if (!a[t]) break; 

119.            for (int u = t; u != s; u = edges[p[u]].from) 

120.            { 

121.                edges[p[u]].flow += a[t]; 

122.                edges[p[u] ^ 1].flow -= a[t]; 

123.            } 

124.            flow += a[t]; 

125.        } 

126.        return flow; 

127.    } 

128.}q; 

129.void make_map (int n) 

130.{ 

131.    for (int i = 1; i <= n; ++i) 

132.    { 

133.        for (int j = 0;j < d.u[i].size();++j) 

134.        { 

135.            int v = d.u[i][j].v, w = d.u[i][j].w; 

136.            if (d.d[v] - d.d[i] == w) 

137.            { 

138.                q.AddEdge(i,v,1);//最大流，流量是1 

139.                g.AddEdge(i,v,1);//最短路，边权是1 

140.            } 

141.        } 

142.    } 

143.} 

144.int main() 

145.{ 

146.    int n, m; 

147.    while (~scanf ("%d %d", &n, &m) ) 

148.    { 

149.        d.init (n); 

150.        g.init (n);q.init(n); 

151.        for (int i = 0, u, v, w; i < m; ++i) 

152.        { 

153.            scanf ("%d %d %d", &u, &v, &w); 

154.            d.AddEdge (u, v, w); 

155.        } 

156.        int minway = d.spfa (1, n, n); 

157.        make_map (n); 

158.        int ans1 = q.MaxFlow (1, n); 

159.        int ans2 = m - g.spfa (1, n, n); 

160.        printf ("%d %d\n", ans1, ans2); 

161.    } 

162.    return 0; 

163.} 

164./* 

165. 

166.7 12 

167.1 2 1 

168.2 7 8 

169.1 7 8 

170.1 6 7 

171.6 7 1 

172.2 3 3 

173.3 6 3 

174.6 4 1 

175.7 4 2 

176.1 5 2 

177.5 4 4 

178.7 5 6 

179.*/ 

codeforces 14D

题意： 
本题目就是要求出一棵树上面两条路径长度的乘积，输出最大的乘积即可。 
思路： 
枚举每条边，对于每一条边，我都可以求出断开这条边以后得到的两条最长的路径的长度。其中的最大值就是答案。

代码

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

 

vector<int >ve[300];

int n;

int vis[300];

int dis[300];

int tar[300];

int zux,zuy;

 

bool ok(int x,int y)

{

 

    if(x==zux&&y==zuy)

        return 1;

    else if(x==zuy&&y==zux)

        return 1;

    return 0;

}

void dfs(int num)

{

    tar[num]=1;

    vis[num]=1;

    for(int i=0;i<ve[num].size();i++)

    {

        int x=ve[num][i];

        if(vis[x]||ok(x,num))

            continue;

        dis[x]=dis[num]+1;

        dfs(x);

    }

}

int pac(int x)

{

    memset(dis,0,sizeof dis);

    memset(vis,0,sizeof vis);

    dfs(x);

    int ans=0;

    for(int i=1;i<=n;i++)

    {

    if(dis[ans]<dis[i])

        ans=i;

    }

    memset(dis,0,sizeof dis);

    memset(vis,0,sizeof vis);

    dfs(ans);

    ans=0;

    for(int i=1;i<=n;i++)

    {

        if(ans<dis[i])

            ans=dis[i];

    }

    return ans;

}

int solve()

{

        memset(tar,0,sizeof tar);

        int t1=0,t2=0;

        if(ve[zux].size()==1)

            t1=0;

        else

        t1=pac(zux);

        if(ve[zuy].size()==1)

            t2=0;

        else

        t2=pac(zuy);

        return t1*t2;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=1;i<=n;i++)

            ve[i].clear();

        int x,y;

        for(int i=0;i<n-1;i++)

        {

            scanf("%d%d",&x,&y);

            ve[x].push_back(y);

            ve[y].push_back(x);

 

        }

        int ans=0;

        for(int i=1;i<=n;i++)

        {

            for(int j=0;j<ve[i].size();j++)

            {

                zux=i;

                zuy=ve[i][j];

                ans=max(ans,solve());

            }

           // printf("ans:%d\n",ans);

        }

        printf("%d\n",ans);

    }

 

    return 0;

}

题意：求某个数的最大质因子是第几个质数
思路：用筛法打个带标记的质数表即可
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int MAXN = 1000000;
int str[MAXN + 10], prime[MAXN];
int Max(int a, int b)
{
    return a>b ? a : b;
}
void init()
{
    memset(str, 0, sizeof str);
    int cnt = 1;
    str[0] = 0;
    str[1] = 0;
    for (int i = 2; i <= MAXN; i++)
    {
        if (str[i] == 0)
        {
            str[i] = cnt;
            prime[cnt++] = i;
        }
        for (int j = 1; j < cnt && i * prime[j] <= MAXN; j++)
        {
            str[i * prime[j]] = Max(j, str[i]);
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
}
int main()
{
    init();
    int n;
    while (~scanf("%d", &n))
    {
        printf("%d\n", str[n]);
    }
    return 0;
}

硬币所有可能排列情况为2^n,朝向相同硬币连续三个以下 的排列情况为a(1)=2,a(2)=4,a(3)=6,a(4)=10,观察或者推算得a(n)=a(n-1)+a(n-2);
那么连续三个或三个以上硬币的所有组合情况 为b(n)=2^n-a(n);
化为只含b(n)的递推式即 b(n)=b(n-1)+b(n-2)+2^(n-2);b(1)=0;b(2)=0;b(3)=2;b(4)=6;用矩阵快速幂可快速算得b(n);

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
 
const int mod=10007;
struct node
{
    int a[4][4];
    node()
    {
        a[1][1]=a[1][2]=a[1][3]=a[2][1]=1;
        a[2][2]=a[2][3]=a[3][1]=a[3][2]=0;
        a[3][3]=2;
    }
    void init()           //将其初始化为单位矩阵
    {
        memset(a,0,sizeof(a));
        for(int i=1; i<4; i++)
            a[i][i]=1;
    }
};
 
node mul(node a,node b)  //(a*b)%mod  矩阵乘法
{
    node ans;
    for(int i=1; i<4; i++)
        for(int j=1; j<4; j++)
        {
            ans.a[i][j]=0;
            for(int k=1; k<4; k++)
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
            ans.a[i][j]%=mod;
        }
    return ans;
}
node power(node a,int n)    //(a^n)%mod  //矩阵快速幂
{
    node ans;
    ans.init();
    while(n)
    {
        if(n%2)//n&1
            ans=mul(ans,a);
        n/=2;
        a=mul(a,a);
    }
    return ans;
}
int main()
{
    int i,j,n;
    while(~scanf("%d",&n))
    {
        if(n<3){printf("0\n");continue;}
        node ans;
        ans=power(ans,n-2);
       
        printf("%d\n",(ans.a[1][3]*2)%mod);
    }
    return 0;
}

这题交的时候要注意是%I64d 所以我直接用了cin cout

/*

        方程两边同时除以gcd(a,b).我们假设aa=a/gcd(a,b),bb=b/gcd(a,b),nn=n/gcd(a,b)

        所以方程两边同时除以gcd(a,b)后，

        可以得到一个方程aa*x+bb*y=nn.

        并且该方程aa*x+bb*y=nn的解x,y就是a*x+b*y=n的解

        我们只要求解出aa*x+bb*y=1的其中一个解，设这两个解为x0,y0.

        那么aa*x+bb*y=nn的其中一个解解就是x0*nn,y0*nn.

        接着，a*x+b*y=n的其中一个解解也就是x0*nn,y0*nn.

        a*(x0*nn)+b*(y0*nn)=n. 

        a*(x0*nn+1*b)+b*(y0*nn-1*a)=n

        a*(x0*nn-1*b)+b*(y0*nn+1*a)=n.

        继续扩展

        a*(x0*nn+k*b)+b*(y0*nn-k*a)=n （k属于整数）

        nn=n/gcd(a,b).

        x=x0*nn+k*b

        y=y0*nn-k*a

 */

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<vector>

using namespace std;

long long gcd(long long a,long long b)

{

    return b==0?a:gcd(b,a%b);

}

long long exgcd(long long a,long long b,long long &x,long long &y)

{

    if (!b)

    {

        x=1;

        y=0;

        return a;

    }

    long long gcd=exgcd(b,a%b,x,y);

    long long temp=x;

    x=y;

    y=temp-a/b*y;

    return gcd;

}

long long upper(long long a,long long b)//往上取整

{

    if (a<=0)

        return a/b;

    return (a-1)/b+1;

}

long long lower(long long a,long long b)//往下取整

{

    if (a>=0)

        return a/b;

    return (a+1)/b-1;

}

long long get(long long l,long long r,long long d,long long &k1,long long &k2)

{

    if (d<0)

    {

        l=-l;

        r=-r;

        d=-d;

        swap(l,r);

    }

    k1=upper(l,d);

    k2=lower(r,d);

}

int main()

{

    long long a,b,c,x1,y1,x2,y2;

    while (cin>>a>>b>>c)//ax+by+c=0 >>ax+by=-c

    {

        bool flag=0;

        c=-c;

        cin>>x1>>x2>>y1>>y2;

        long long ans,x,y;

        if (!a && !b && !c)

        {

            cout<<(x2-x1+1)*(y2-y1+1)<<endl;

            continue;

        }

        else if (!a && !b)

        {

            cout<<0<<endl;

            continue;

        }

        else if (!a)

        {

            if (c%b || c/b<y1 || c/b>y2)

                ans=0;

            else

                ans=x2-x1+1;

            cout<<ans<<endl;

            continue;

        }

        else if (!b)

        {

            if (c%a || c/a<x1 || c/a>x2)

                ans=0;

            else

                ans=y2-y1+1;

            cout<<ans<<endl;

            continue;

        }

        /*

        先处理了a,b,c为0的情况

        */

 

        long long g=gcd(a,b);

        if (c%g)//如果 c不是gcd(a,b)的倍数 无解

        {

            cout<<0<<endl;

            continue;

        }

        a/=g;

        b/=g;

        c/=g;// c=c/g 上面已经将c变为-c

        exgcd(a,b,x,y);

        long long k1,k2,k3,k4;

        x*=c;

        y*=c;

        get(x1-x,x2-x,b,k1,k2);

        get(y1-y,y2-y,-a,k3,k4);

//        cout<<x<<" "<<y<<endl;

        ans=min(k2,k4)-max(k1,k3)+1;

        cout<<ans<<endl;

    }

    return 0;

}

题意：

给定n个数（a1,a2……an），求p，其中p=n!，且p可以被（a1!*a2!*…….*an!）整除。

分析：

将a1!*a2!*……*an!分解成质因子相乘的形式，但是肯定不可能一个数一个数分解，巧妙的运用从大数转换成小数的思想，求出各个质因子及其个数。再运用二分求解对于每个质因子而言最小的nn,所有的nn取最大即为结果

源代码：

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<map>

#include<cmath>

#include<stack>

#include<vector>

#include<set>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1000005;

typedef __int64 LL;

 

LL num[N*10];

int p[N*10];

bool vis[N*10];

int prime[N];

int tot=0;

LL sum;

int ma;

 

void init()

{

    memset(vis,false,sizeof vis);

    for(int i=2; i<N*10; i++)

    {

        if(!vis[i])

        {

            prime[tot++]=i;

            p[i]=i;

        }

        for(int j=0; j<tot&&i<=N*10/prime[j]; j++)

        {

            vis[i*prime[j]]=true;

            p[i*prime[j]]=prime[j];

            if(i%prime[j]==0)

                break;

        }

    }

}

 

void cal()

{

    for(int i=ma;i>=2;i--)

    {

        if(p[i]!=i)

        {

            num[p[i]]+=num[i];

            num[i/p[i]]+=num[i];

        }

    }

}

 

bool ok(LL m,int a,LL n)

{

    LL res=0;

    while(m)

    {

        res+=m/a;

        m/=a;

        if(res>=n)

            return true;

    }

    return false;

 

}

 

LL BST(int a,LL n)

{

    LL l=1,r=sum;

    LL ans=-1;

    while(l<=r)

    {

 

        LL mid=(l+r)/2;

        if(ok(mid,a,n))

        {

            ans=mid;

            r=mid-1;

        }

        else l=mid+1;

    }

    return ans;

}

 

LL solve()

{

    LL ans=1;

    for(int i=0;i<tot;i++)

    {

        if(num[prime[i]])

        {

            ans=max(ans,BST(prime[i],num[prime[i]]));

        }

        else break;

    }

    return ans;

}

 

int main()

{

    int n;

    init();

    while(~scanf("%d",&n))

    {

        memset(num,0,sizeof num);

        ma=0;

        sum=0;

        for(int i=0; i<n; i++)

        {

            int x;

            scanf("%d",&x);

            ma=max(ma,x);

            num[x]++;

            sum+=x;

        }

        for(int i=ma-1;i>=2;i--)

        {

            num[i]+=num[i+1];

        }

 

        cal();

 

        printf("%I64d\n",solve());

    }

    return 0;

}

题意：有三个杯子倒扣于桌面,放的位置编号1,2,3，刚开始2号地方的杯子里有一个key，现在每次操作为从1、3号位置上等概率选择一个与2号位置的杯子交换(换杯子，位置编号还是不变，可认为左、中、右三个，比如3换到1就是右边的杯子换到中间)，求n次操作后key在2号位子的杯子里的概率，结果用分数。
题解：每次都是从1、3中选一个，显然概率就是1/2，而且每次2号位置的杯子都会变化。那么dp[i][n]表示第n次操作后,key在i号位置的杯子中的概率。
显然三个杯子,i=1,2,3;把换成一维的：f1(n),f2(n),f3(n).然后递推：
对于f1(n):可能第n-1次后key就在1位置，那么第n次只能选3号，即1/2*f1(n-1);可能第n-1次后key在2号中，那么只能选1位置，即1/2*f2(n-1);只有这两个可能到达，所以f1(n)=1/2*(f1(n-1)+f2(n-1));
对于f3(n),位置是对称的：f3(n)=f1(n);
类似1，f2(n)=1/2*(f1(n-1)+f3(n-1));
我们要求的是f2(n)
上面三个等式：f2(n)=1/2*(f2(n-1)+f2(n-2));
这个式子用组合数学求解线性常系数递推式(母函数内容)
最后f2(n)= .
题目对取模要求比较变态，必须是分子分母分别取模前要求化为最简分式，最简后再分别取模。上面的式子问题在于分母的3，因为2^(n-1)与分子已经没有公因子可以消了。那么看分子里面有没有3这个因子可以消：
很巧的是：当n-1为奇数时,2^(n-1)%3=2，此时n为偶数，(-1)^n=1;所以(2^(n-1)+(-1)^n)%3=0,同理n-1位偶数时有同样的结论
也就是说分子必然能消掉3;既然能整除，那么就把(2^(n-1)+(-1)^n)/3整体当做分子，而且是可以用逆元去处理3的，这样处理后就是最简分式了
即 ，inv是逆元，分子分母都是对1e9+7取模
现在问题就是n很大(不知道这里能用java搞)，幂很大就是用指数循环节：
  
要求各欧拉函数
注意定理使用的条件,n较小时直接快速幂；
#pragma comment(linker, "/STACK:10240000,10240000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
const double R=0.5772156649015328606065120900;
const int N=1e5+5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
    int n;
ll a[N],ini,M;
ll judge()
{
    ll tm=mod+10;
    ll ans=1;
    for(int i=0;i<n;i++)
    {
        if(ans>tm/a[i]) return 0;//很大
        ans*=a[i];
    }
    return ans;
}
ll Pow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
void solve(ll mo,ll tag)
{
    ll ans=1;
    for(int i=0;i<n;i++)
    {
        a[i]%=mo;//注意爆数据
        ans=ans*a[i]%mo;
    }
    ans--;
    ans=(ans%mo+mo)%mo;
    if(ans==0) ans+=mo;
    ll down=Pow(2,ans);
    ll up=down+tag;
    up=up*ini%mod;
    cout<<up<<'/'<<down<<endl;
}
int main()
{
     ini=333333336,M=1000000006;//事先求好逆元和欧拉值
    while(cin>>n)
    {
        int tag=-1;
        for(int i=0;i<n;i++)
        {
            scanf("%I64d",&a[i]);
            if(a[i]%2==0) tag=1;//
        }
        ll all=judge();
        if(all==0) {solve(M,tag);continue;}//幂很大
        if(all==1)
        {
            cout<<"0/1"<<endl;
            continue;
        }
        ll down=Pow(2,all-1);
        ll up=(down+tag)*ini%mod;
        cout<<up<<'/'<<down<<endl;

    }
    return 0;
}

题意：只是那个k是无限个
题解：首先是算k：先了解两条性质，欧拉函数是积性函数；
（1）积性函数性质：F(m1*m2)=F(m1)*F(m2)，当且近当gcd(m1,m2)=1时成立；
（2） ，其中p是n的素因子,且gcd(p,n/p)=1。这个用欧拉函数的素因子表达式很好证明。
有了这个再来算k，题目的n是很特殊的，它的每个素因子的幂次都是1：
那么假设素数p是n的一个素因子，显然gcd(p,n/p)=1;关键是i，如果i中没有素因子p，那么就直接用积性性质。如果i%p==0，必然可以写成i=k*p;即倍数关系，否则i%p!=0;
所以分成两部分求：
 
 .....p是素数,素数的欧拉值就是p-1;
 
 
到这里前两和式是可以合并的，考虑和式的上下限，含义不同，第二项的i表示的p的倍数i*p才是第一项i的含义，相当于第二项刚好把第一项补齐了，那么从1到m没有遗漏，而且第二项的i用第一项替换后里面也是n/p;最终
 
这是个e二元递归式：n/p和m/p看成整体,那么设原先求的为f(n,m)，所以f(n,m)=(p的欧拉值)*f(n/p,m)+f(n,m/p);
每次枚举一个就够了，n每次要除以p，最多就是把它的每个素因子除完。
第二部分k的超级幂：用欧拉的定理：指数循环节
  
每次往幂次上一层模就取一次欧拉值,只有1的欧拉值等一自己,其他数的欧拉值都是小于自己的，所以模会不断变小至1，显然对1取模结果就是0，所以无限就变得有限了
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iterator>
#include<stack>
using namespace std;
const int INF=1e9+7;
const double eps=1e-7;
const int N=1e7+5;
const int M=1000000007;
typedef long long ll;
int pri[N],phi[N];
bool vis[N];
int tot;
ll sum[N];
void init()
{
    int n=N;
    tot=0;
    memset(vis,false,sizeof vis);
    phi[1]=1;
    for(int i=2;i<n;i++)
    {
        if(!vis[i])
        {
            pri[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot && i*pri[j]<n;j++)
        {
            vis[i*pri[j]]=true;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    sum[0]=0;
    for(int i=1;i<N;i++)
        sum[i]=(sum[i-1]+phi[i])%M;
}
ll Pow(ll a,ll n,ll mod)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
        {
            ans=ans*a%mod;
//            if(ans>=mod)ans=ans%mod;
        }
        a=a*a%mod;
//        if(a>=mod) a=a%mod;
        n>>=1;
    }
    if(ans==0) ans+=mod;
    return ans;
}
ll solve(ll k,ll mod)
{
    if(mod==1) return mod;
    ll tmp=phi[mod];
    ll up=solve(k,tmp);
    ll ans=Pow(k,up,mod);
    return ans;
}
int rear;
int a[15];
void resolve(ll n)
{
    for(int i=0;i<tot;i++)
    {
        if(!vis[n]) {a[rear++]=n;break;}
        if(n%pri[i]==0)
        {
            a[rear++]=pri[i];
            n/=pri[i];
        }
    }
}
ll f(int pos,ll n,ll m)
{
    //pos即每个素数，一次一个就行了
    if(n==1) return sum[m];//n为1结果就是欧拉值的前缀和
    if(m==0)return 0;
    return ((a[pos]-1)*f(pos-1,n/a[pos],m)%M+f(pos,n,m/a[pos]))%M;
}
int main()
{
    init();//打表
    ll n,m,p;
    while(~scanf("%I64d%I64d%I64d",&n,&m,&p))
    {
        rear=0;
        resolve(n);//素因子分解
        ll k=f(rear-1,n,m);//算k
        ll ans=solve(k,p);
        printf("%I64d\n",ans%p);
    }
    return 0;
}

题意：求在一个矩阵中能吃掉数字的最大和，当吃掉某个数字的时候，该数字的上一行（若是第0行则不处理）和下一行（若是最后一行不处理）和左右两个数字（同理）会消失
思路：先按吃一个则左右消失的规则处理出每一行能吃到的最大数字和（可以用DP），然后再按照吃一行上下两行消失的规则处理行的和
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int MAXN = 200010;
int n, m,str[MAXN];
int Max(int a,int b)
{
        return a>b?a:b;
}
int main()
{
        while (~scanf("%d%d", &n, &m))
        {
                int a[MAXN], b[MAXN];
                a[0] = b[0] = 0;
                for (int i = 1; i <= n; i++)
                {
                        int temp;
                        for (int j = 1; j <= m; j++)
                        {
                                scanf("%d", &temp);
                                a[j]=Max(a[j-1],b[j-1]);
                                b[j]=a[j-1]+temp;
                        }
                        str[i]=Max(a[m],b[m]);
                }
                a[0]=b[0];
                for(int i=1;i<=n;i++)
                {
                        a[i]=Max(a[i-1],b[i-1]);
                        b[i]=a[i-1]+str[i];
                }
                printf("%d\n",Max(a[n],b[n]));
        }
        return 0;
}

题意：
给出n个点，要求从最左端点严格向右走到最右端点，再从最右端点走回来
途中必须经过所有点（保证每个点横坐标不同），求最短路。
解题思路：
双调欧几里得旅行商问题，dp。将点按横坐标从小到大排序，dp[i][j]表示从j向左走到1，再从1走到i的最短路（i<j）（此过程中1-j所有的点都被经历过）。
给出转移方程:
dp[i][j]=dp[i][j-1]+dist(j-1,j)    (i<=j-2);
dp[j-1][j]=min(dp[j-1][j],dp[i][j-1]+dist(i,j))   (i<=j-2);
按此方式更新不会丢失最优解（每次只把j纳入集合而不考虑j+1，j+2...）
最终得到dp[n][n]=dp[n-1][n]+dist(n-1,n);
代码:
1.    #include<iostream>  
2.    #include<cstring>  
3.    #include<cmath>  
4.    #include<iomanip>  
5.    using namespace std;  
6.    const double INF=1.0*9999999;  
7.    struct Node  
8.    {  
9.            int x,y;  
10.    };  
11.    Node a[1005];  
12.    double dp[1005][1005];  
13.    int n;  
14.    double dist(int i,int j)  
15.    {  
16.            return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));  
17.    }  
18.    int main()  
19.    {  
20.            while(~scanf("%d",&n))  
21.            {  
22.                    for(int i=1;i<=n;i++)  
23.                            scanf("%d%d",&a[i].x,&a[i].y);  
24.                    memset(dp,INF,sizeof dp);  
25.                    dp[1][2]=dist(1,2);  
26.                    for(int j=3;j<=n;j++)  
27.                    {  
28.                            for(int i=1;i<=j-2;i++)  
29.                                    dp[i][j]=dp[i][j-1]+dist(j-1,j);  
30.                            dp[j-1][j]=INF;  
31.                            for(int i=1;i<=j-2;i++)  
32.                                    dp[j-1][j]=min(dp[i][j-1]+dist(i,j),dp[j-1][j]);  
33.                    }  
34.                    dp[n][n]=dp[n-1][n]+dist(n-1,n);  
35.                    cout<<setprecision(2)<<fixed<<dp[n][n]<<endl;  
36.            }  
37.    }  

题意：
额，中文题不翻译。
解题思路：
看别人的博客才理解的，由于每个加油站都可以选择加油和不加油，为了把所有情况考虑进去，不妨令dp[i]为从起点到第i个加油站所需要的最短时间，那么dp[i]就应该是从0到i-1这些节点充满电然后直接跑到i的最短时间。为什么这样做不会丢失最优解？不妨考虑第4个节点，计算过程中你求出了dp[2]+t2和dp[3]+t3，这就等于说你已经考虑了第3个节点充电或者不充电的情况，
而且此时的dp[2]是它所能取得最小值，同理，dp[1]+t1和dp[2]+t2就表示考虑了第2个节点充电或者不充电的情况，那么有没有考虑第2个节点不充电但是第三个节点充电的情况呢？这里看上去是没有，但是你在计算dp[3]的时候，就已经考虑好了第二个点究竟该不该充电，所以第2个节点不充电但是第三个节点充电的情况可能会包含于dp[3]+t3中，好绕口啊。。
1.    #include<cstdio>  
2.    #include<cstring>  
3.    #include<string>  
4.    #include<iostream>  
5.    #include<sstream>  
6.    #include<algorithm>  
7.    #include<utility>  
8.    #include<vector>  
9.    #include<set>  
10.    #include<map>  
11.    #include<queue>  
12.    #include<cmath>  
13.    #include<iterator>  
14.    #include<stack>  
15.    using namespace std;  
16.    const double INF=9999999;  
17.    const double eps=1e-7;  
18.    const int mod=1000007;  
19.    const int maxn=50000;  
20.    double dp[maxn];  
21.    int a[maxn];  
22.    int main()  
23.    {  
24.            int l,n,c,t,vr,v1,v2;  
25.            while(cin>>l)  
26.            {  
27.                    cin>>n>>c>>t;  
28.                    cin>>vr>>v1>>v2;  
29.                    for(int i=1;i<=n;i++)  
30.                            cin>>a[i];  
31.                    memset(dp,INF,sizeof dp);  
32.                    sort(a+1,a+1+n);  
33.                    a[0]=0;  
34.                    a[n+1]=l;  
35.                    dp[0]=0;  
36.                    for(int i=1;i<=n+1;i++)  
37.                    {  
38.                            for(int j=0;j<i;j++)  
39.                            {  
40.                                    double tt;  
41.                                    if(c>a[i]-a[j])  
42.                                            tt=1.0*(a[i]-a[j])/v1;  
43.                                    else  
44.                                            tt=1.0*c/v1+1.0*(a[i]-a[j]-c)/v2;  
45.                                    dp[i]=min(dp[i],dp[j]+tt);  
46.                            }  
47.                            dp[i]+=t;//默认充满电  
48.                    }  
49.      
50.                    if(dp[n+1]-t>1.0*l/vr)  
51.                            cout<<"Good job,rabbit!"<<endl;  
52.                    if(dp[n+1]-t<1.0*l/vr)  
53.                            cout<<"What a pity rabbit!"<<endl;  
54.            }  
55.    }  

题意：
旅行商问题，给出n个位置，求从起点（0,0）出发遍历所有位置再回到原点得最短路。

解题思路：
1.DP+状态压缩，以二进制保存当前遍历状态，如果此状态下某个点未被经过，则用此状态转移到经过该店的状态，更新其值。
2.注意到n很小，DFS搜一遍~。

代码1：
1.    #include <iostream>  
2.    #include <cstdio>  
3.    #include <cstring>  
4.    #include <algorithm>  
5.    #include <cmath>  
6.    using namespace std;  
7.    const int N=55;  
8.    const int INF=0x3f3f3f3f;  
9.    int dp[(1<<11)+15][N];  
10.    int dist[N][N];  
11.    struct Node  
12.    {  
13.        int x,y;  
14.    }p[N];  
15.    int main()  
16.    {  
17.        int n,m,t;  
18.        int cnt;  
19.        while(cin>>n>>m)  
20.        {  
21.      
22.            cnt=0;  
23.            for(int i=0; i<n; i++)  
24.                for(int j=0; j<n; j++)  
25.                {  
26.                    cin>>t;  
27.                    if(t||(i==0&&j==0))  
28.                    {  
29.                        p[cnt].x=i;  
30.                        p[cnt++].y=j;  
31.                    }  
32.                }  
33.            for(int i=0; i<cnt; i++)  
34.            {  
35.                for(int j=i+1; j<cnt; j++)  
36.                    dist[i][j]=dist[j][i]=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);  
37.                    dist[i][i]=0;  
38.            }  
39.            memset(dp,INF,sizeof(dp));  
40.            dp[0][0]=0;  
41.            for(int i=0; i<(1<<cnt); i++)  
42.            {  
43.                for(int j=0; j<cnt; j++)  
44.                {  
45.                    if(dp[i][j]==INF)  
46.                            continue;  
47.                    for(int k=0; k<cnt; k++)  
48.                    {  
49.                        if(i&(1<<k))  
50.                            continue;  
51.                        dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dist[j][k]);  
52.                    }  
53.                }  
54.            }  
55.            cout<<dp[(1<<cnt)-1][0]<<endl;  
56.        }  
57.    }  

题意：桌上有4堆糖果，每堆糖果高度不超过40，每颗糖果有一种颜色(一共20种，1,2,3...,20)，

有一个篮子，一开始是空的，每当里面装有两颗颜色相同的糖果时，就可以从篮子里拿出这一对糖果。

如果篮子里的糖果数量为5个并且不能再拿时，篮子充满，游戏结束。问最多能拿走多少对糖果。

糖果堆上的所有糖果拿光了也算结束

 

样例：

5

1 2 3 4

1 5 6 7

2 3 3 3

4 9 8 6

8 7 2 1

解释：

每堆糖果高度为5,

从左往右为4堆糖果，数字代表颜色。堆顶在上。

结果：

8

 

一开始看到这个题会觉得状态根本就无法表示，因为你需要保存每一堆的剩余层数，还需要保存篮子里的糖果数量和颜色，即使状态存下了，转移起来时间复杂度也太高了。

41^4* 21^5实在太大。

后来想想根本不用保存这么多状态。因为保存了每堆剩余的层数就知道了拿掉的糖果，又因为篮子里同种颜色的糖果只能是0或者1(同色糖会被拿掉)，所以可以推出篮子里糖果的状态。

将糖果编号改为0到19,然后用状压表示每个状态(每堆剩余层数)对应篮子里的糖果。

 

 

 

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

 

#define all(x) (x).begin(), (x).end()

#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)

#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)

#define ysk(x)  (1<<(x))

typedef long long ll;

typedef pair<int, int> pii;

const int INF =0x3f3f3f3f;

const int maxn=40    ;

int a[5][maxn+3];

int state[maxn+10][maxn+10][maxn+10][maxn+10];

int dp[maxn+3][maxn+3][maxn+3][maxn+3];

int n;

 

int getNum(int &s)//计算篮子s里的糖果数量

{

    int cnt=0;

    for(int i=0;i<20;i++) if(s&ysk(i))

    {

       cnt++;

    }

    return cnt;

}

 

 

void fix(int &x,int y)//更新dp值

{

    if(y>x) x=y;

}

int update(const int* hp,const int* h,int p )//从状态hp转移到状态h，在第p堆转移。

{

 

    int s,sp=state[hp[1] ][hp[2]  ][hp[3] ][hp[4] ];

 

    int k= a[p][hp[p]];//k表示拿掉糖果的颜色。

 

    if(sp&ysk(k) ) { s=sp^ysk(k);

      fix(  dp[h[1]][h[2]  ][h[3] ][h[4]  ],  dp[hp[1] ][hp[2] ][hp[3]][hp[4]  ]+1    );

    }

    else{

        int num=getNum(sp);

        if(num==4) return 0;

        s=sp^ysk(k);

      fix(  dp[h[1]][h[2]  ][h[3] ][h[4]  ],  dp[hp[1] ][hp[2] ][hp[3]][hp[4]  ]  );

    }

   state[h[1]][h[2]] [h[3]  ][h[4]  ]=s;

    return 1;

 

 

}

 

int work()

{

    int ans=0;

    state[n][n][n][n]=0;

    memset(dp,-1,sizeof dp);

    dp[n][n][n][n]=0;

    int h[5];

    for(h[1]=n;h[1]>=0;h[1]-- ){

        for(h[2]=n;h[2]>=0;h[2]--){

            for(h[3]=n;h[3]>=0;h[3]--){

                for(h[4]=n;h[4]>=0;h[4]--){

                    if(h[1]+h[2]+h[3]+h[4]==4*n)  continue;

//                    dp[h[1] ][h[2]][h[3]][h[4]  ]=-1;

                    for(int i=1;i<=4;i++)  if( h[i]+1<=n  )

                    {

                        int hp[5];

                        memcpy(hp,h,sizeof hp);

                        hp[i]++;

                        if(dp[hp[1]  ][hp[2] ][hp[3]  ][hp[4] ]==-1) continue;

                        update(hp,h,i);

                    }

                    ans=max(ans,dp[h[1] ][h[2]][h[3]][h[4]  ]);

 

                }

            }

        }

    }

    return ans;

}

 

 

int main()

{

    while(~scanf("%d",&n)&&n)

    {

        for(int h=n;h>=1;h-- )

        {

            for(int i=1;i<=4;i++)

            {

                scanf("%d",&a[i][h]);//第i堆，第h层糖果颜色

                a[i][h]--;

            }

        }

        printf("%d\n",work());

    }

 

   return 0;

}

/*

5

1 2 3 4

1 5 6 7

2 3 3 3

4 9 8 6

8 7 2 1

 

对于这组样例的分析：

如果从左往右，高度依次为 0 0 4 5 可以发现这时是个死局

因为篮子里有5颗颜色各不相同的糖果。

可以认为该状态无法达到，因为即使达到了也不能进行后续转移，并且这个状态的最后一步是没有消除糖果的，所以这个状态

相比于前面转移到它的状态并不更优，

所以说可以认为该状态达不到，这对于结果毫无影响。

 

 

假如状态(0 ,0 ,4, 5)无法达到，那么状态(0,0,4,4)还需要继续计算 ，(0,0,4,4)是可以到达的。

 

从结果上看，(0,0,4,4)篮子里只有4颗糖

但是(0,0,4,4)不可能从(0,0,4,5)转移过来的，完全可以从(1,0,4,4)转移过来。最后一步不同，代表着拿取糖果的顺序不同。

 

还有一点需要注意的是，初始化是，应该全部memset(dp,-1,sizeof dp) 否则可能会受到上一组样例的影响

 

比如说考虑结果(0,0,3,3)，枚举这个状态的前驱，如果状态(0,0,3,4)在这个样例里是根本不可达的，甚至能达到的状态距离它

 

还相距甚远，但是在上一组样例里这个状态可以达到的，那么它的dp值就不为-1，会从上一个样例的状态(0,0,3,4)转移到这个样例的

 

(0,0,3,3)，从而造成错误。

*/