比赛过程中忘了写chs函数导致无论如何都调试不成
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1010;
const int inf=0x7fffffff;
const double eps=1e-3;

const int m1=0x00fc0000;
const int m2=0x0003f000;
const int m3=0x00000fc0;
const int m4=0x0000003f;

char str[maxn];

char chs(char ch)
{
if (ch>=0&&ch<26) return ch+’A’;
else if (ch>=26&&ch<52) return ch-26+’a’;
else if (ch>=52&&ch<62) return ch-52+’0’;
else if (ch==62) return ‘+’;
else if (ch==63) return ‘/‘;
}

void solve(char str[maxn])
{
char s[maxn]={‘\0’};
int len=strlen(str);
int tmp=0;
int pos=0;
for(int i=0;i<len;i++)
{
tmp<<=8;tmp+=int(str[i]);
if (!((i+1)%3))
{
s[pos++]=chs((tmp&m1)>>18);
s[pos++]=chs(((tmp&m2)>>12));
s[pos++]=chs(((tmp&m3)>>6));
s[pos++]=chs((tmp&m4));
tmp=0;
}
}
if (len%3)
{
tmp<<=(3-len%3)*8;
if ((tmp&m1)>0) s[pos++]=chs((tmp&m1)>>18);
if ((tmp&m2)>0) s[pos++]=chs(((tmp&m2)>>12));
if ((tmp&m3)>0) s[pos++]=chs(((tmp&m3)>>6));
if ((tmp&m4)>0) s[pos++]=chs((tmp&m4));
}
int sum=4-strlen(s)%4;
char *t=s+strlen(s);
if (sum<4)
for(int j=1;j<=sum;j++) *t++=’=’;
*t=’\0’;
strcpy(str,s);
}

int main()
{
int T;
scanf(“%d”,&T);
while(T–)
{
int k;
scanf(“%d%s”,&k,str);
for(int i=1;i<=k;i++) solve(str);
printf(“%s\n”,str);
}
return 0;
}
[/cpp]

别看一个ACMer在线上有多神通广大，到了现场赛变得多憋屈。
去了现场赛一定能学到很多实验室里体验不到的教训。

热身赛
二分图匹配用在棋盘覆盖上，省时省力！
容斥原理的变式应用，贪心；抓住了一些要点，但处理手段欠缺点

正式赛
卡题时间长
字符串模拟，手动实现Base64编码，写不好真是跟自己过不去。
概率计算不当，因为缺乏对边界线重叠的考虑；几何分布的概型应用时正确的。

String

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.

Two substrings of S are considered as “different” if they are cut from different part of S. For example, string “aa” has 3 different substrings “aa”, “a” and “a”.

Your task is to calculate the number of different “recoverable” substrings of S.

Input

The input contains multiple test cases, proceeding to the End of File.

The first line of each test case has two space-separated integers M and L.

The second ine of each test case has a string S, which consists of only lowercase letters.

The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.

Output

For each test case, output the answer in a single line.

Sample Input

3 3
abcabcbcaabc

Sample Output

2

Source

2013 Asia Regional Changchun

纯粹是寻找一个最佳的hash姿势？而且还要懂得合适的时间优化？
真的TLE了好几次，现场赛的难点
枚举字串起点不必从头找到尾，因为向后滚的操作涵盖了i>=l以后的字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include<cstdio>
#include<cstring>
#include<memory.h>
#include<string>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e5+10;
const ULL base=29;//prime

map<ULL,int> mp;

ULL nbase[maxn],ha[maxn];
char str[maxn];
//string s;

void init()
{
    nbase[0]=1;
    for(int i=1;i<maxn;i++) nbase[i]=nbase[i-1]*base;
}

inline ULL Hash(char *s,int len,ULL *_hash)  //按各个后缀hash
{
    _hash[len]=0;
    for(int i=len-1;i>=0;i--)
        _hash[i]=_hash[i+1]*base+s[i]-'a';
}

inline ULL Get(ULL *_hash,int pos,int len)
{
    return _hash[pos]-_hash[pos+len]*nbase[len];
}

int main()
{
    init();
    int m,l;

    while(~scanf("%d%d",&m,&l))
    {
        LL ans=0;
        scanf("%s",str);
        int len=strlen(str);
        Hash(str,len,ha);
        for(int i=0;i<=len-m*l&&i<l;i++) //此处不加条件i<l就TLE
        {
            mp.clear();
            for(int j=i;j<i+m*l;j+=l)
            {
                ULL h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
            }
            if (mp.size()==m) ans++;
            for(int j=i+m*l;j<=len-l;j+=l)
            {
                ULL h=Get(ha,j-m*l,l);
                //cout<<h<<':'<<s.substr(j-m*l,l)<<endl;
                mp[h]--;
                if (!mp[h]) mp.erase(h);
                h=Get(ha,j,l);
                //cout<<h<<':'<<s.substr(j,l)<<endl;
                mp[h]++;
                if (mp.size()==m) ans++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

转自byvoid大神的博客

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。

BYVoid原创，欢迎建议、交流、批评和指正。

附：各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
    unsigned int hash = 0;

    while (*str)
    {
        // equivalent to: hash = 65599*hash + (*str++);
        hash = (*str++) + (hash < < 6) + (hash << 16) - hash;
    }

    return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * a + (*str++);
        a *= b;
    }

    return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned int hash = 1315423911;

    while (*str)
    {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }

    return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) < < (BitsInUnignedInt - OneEighth);
    unsigned int hash             = 0;
    unsigned int test             = 0;

    while (*str)
    {
        hash = (hash << OneEighth) + (*str++);
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }

    return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
    unsigned int hash = 0;
    unsigned int x    = 0;

    while (*str)
    {
        hash = (hash < < 4) + (*str++);
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }

    return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned int hash = 5381;

    while (*str)
    {
        hash += (hash < < 5) + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned int hash = 0;
    int i;

    for (i=0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash < < 11) ^ (*str++) ^ (hash >> 5)));
        }
    }

    return (hash & 0x7FFFFFFF);
}

原文地址

当时我也在研究同样的内容，可是只做到了改变代码窗口的背景（有人在我之前已实现了此功能，还打包成了插件）
KyuuBackground

Hash处理，多水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

const int maxn=210;//这里因为错写成110而RE了一次
const int inf=99999999;
const double eps=1e-3;

vector<int> vx,vy;
map<int,int> hx,hy;
bool vis[maxn][maxn];

struct Poly
{
    int x1,y1,x2,y2;
} Pl[maxn];

void dfs(int n,int x,int y)
{
    if (x<0||y<0||x>n||y>n) return ;
    if (!vis[x][ y ])
    {
        vis[x][ y ]=1;
        dfs(n,x-1,y);
        dfs(n,x+1,y);
        dfs(n,x,y-1);
        dfs(n,x,y+1);
    }
}

int main()
{
    int n=1;
    while(~scanf("%d",&n))
    {
        if (!n) break;
        vx.clear();vy.clear();
        hx.clear();hy.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&Pl[i].x1,&Pl[i].y1,&Pl[i].x2,&Pl[i].y2);
            vx.push_back(Pl[i].x1);vx.push_back(Pl[i].x2);
            vy.push_back(Pl[i].y1);vy.push_back(Pl[i].y2);
        }
        sort(vx.begin(),vx.end());
        sort(vy.begin(),vy.end());
        //cout<<vx.size()<<' '<<vy.size()<<endl;
        for(int i=0;i<vx.size();i++) hx[vx[i]]=2*i+1;
        for(int i=0;i<vy.size();i++) hy[vy[i]]=2*i+1;
//cout<<"--"<<endl;
        CLEAR(vis);
        for(int i=1;i<=n;i++)
        {
            int x1=hx[Pl[i].x1];
            int x2=hx[Pl[i].x2];
            if (x1>x2) swap(x1,x2);
            int y1=hy[Pl[i].y1];
            int y2=hy[Pl[i].y2];
            if (y1>y2) swap(y1,y2);
            //cout<<hx[Pl[i].x1]<<' '<<hy[Pl[i].y1]<<' '<<hx[Pl[i].x2]<<' '<<hy[Pl[i].y2]<<endl;
            for(int j=x1;j<=x2;j++) vis[j][y1]=vis[j][y2]=1;
            for(int j=y1;j<=y2;j++) vis[x1][j]=vis[x2][j]=1;
        }
        int ans=0;
        for(int i=0;i<=4*n;i++)
        {
            //for(int j=0;j<=4*n;j++)cout<<vis[i][j]<<' ';cout<<endl;
            for(int j=0;j<=4*n;j++)
                if (!vis[i][j])
                {
                    ans++;
                    dfs(4*n,i,j);
                }
        }
        cout<<ans<<endl;
    }
    return 0;
}

饭卡

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

Input

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample Input

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample Output

-45
32

Source

UESTC 6th Programming Contest Online

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;
const int lmt=1000;

int a[maxn],f[maxn];

int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        if (!n) break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        scanf("%d",&m);
        if (m<5) 
        {
            printf("%d\n",m);continue;
        }
        CLEAR(f);
        int ans=0;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=m-5;j-a[i]>=0;j--)

                    f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
        cout<<m-a[n]-f[m-5]<<endl;
    }
    return 0;
}

Proud Merchants

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Problem Description

Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?

Input

There are several test cases in the input.

Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating maximum value iSea could get.

Sample Input

2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3

Sample Output

5
11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#define CLEAR(a,n) memset((a),0,n*sizeof((a)[0]))

const int maxn=510;
const int maxm=5010;

struct data
{
    int p,q,v;
    void read()
    {
        scanf("%d%d%d",&p,&q,&v);
    }
} item[maxn];

bool operator< (const data &a,const data &b)
{
    return a.q-a.p<b.q-b.p;//不是单纯地比较p！
}

int f[maxm];

int main()
{
    int n,m;

    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++) item[i].read();
        sort(item+1,item+n+1);
        CLEAR(f,maxm);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=item[i].q&&j>=item[i].p;j--)
                f[j]=max(f[j],f[j-item[i].p]+item[i].v);
        cout<<f[m]<<endl;
    }
    return 0;
}

ACboy needs your help

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0

Sample Output

3
4
6

Source

HDU 2007-Spring Programming Contest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

const int maxn=110;

int a[maxn][maxn],f[2][maxn];

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m),n&&m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        CLEAR(f[0],maxn);
        int cur=0;
        for(int i=1;i<=n;i++)
        {
            CLEAR(f[cur^1],maxn);
            for(int j=0;j<=m;j++)
                for(int k=0;k<=m-j;k++)
                    f[cur^1][j+k]=max(f[cur^1][j+k],f[cur][k]+a[i][j]);
            //for(int j=0;j<=m;j++)
                //f[0][j]=max(f[0][j],f[1][j]); 并非从前i-1的任何一步中滚过来
            cur^=1;
        }
        cout<<f[cur][m]<<endl;
    }
    return 0;
}

Consumer

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)

Problem Description
FJ is going to do some shopping, and before that, he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say, if he is going to buy one of these stuff, he has to buy the box beforehand). Each kind of stuff has its own value. Now FJ only has an amount of W dollars for shopping, he intends to get the highest value with the money.

Input

The first line will contain two integers, n (the number of boxes 1 <= n <= 50), w (the amount of money FJ has, 1 <= w <= 100000) Then n lines follow. Each line contains the following number pi (the price of the ith box 1<=pi<=1000), mi (1<=mi<=10 the number goods ith box can carry), and mi pairs of numbers, the price cj (1<=cj<=100), the value vj(1<=vj<=1000000)

Output

For each test case, output the maximum value FJ can get

Sample Input

3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

Sample Output

210

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

LL f[2][maxn];
int p[maxn],m[maxn],c[maxn],v[maxn];

int main()
{
    int n,w,sum;
    while(~scanf("%d%d",&n,&w))
    {
        //if (!n&&!w) break;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i],&m[i]);
            for(int j=sum+1;j<=sum+m[i];j++) scanf("%d%d",&c[j],&v[j]);
            sum+=m[i];
        }
        //for(int i=1;i<=sum;i++) cout<<c[i]<<' '<<v[i]<<endl;

        CLEAR(f);
        sum=0;
        bool cur=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=w-p[i];j++) f[cur^1][j+p[i]]=f[cur][j];
            for(int k=1;k<=m[i];k++)
            for(int j=w;j>=c[sum+k]+p[i];j--)
            {
                    f[cur^1][j]=max(f[cur^1][j],f[cur^1][j-c[sum+k]]+(LL)v[sum+k]);
            }
            for(int j=w;j>=p[i];j--)
                f[cur][j]=max(f[cur][j],f[cur^1][j]);
            sum+=m[i];
            //cur^=1;
        }
        int ans=0;
        //for(int j=0;j<=w;j++) cout<<f[cur^1][j]<<' ';cout<<endl;//ans=max(ans,f[cur][j]);
        //for(int j=0;j<=w;j++) cout<<f[cur][j]<<' ';cout<<endl;
        cout<<f[cur][w]<<endl;
    }
    return 0;
}

The more, The Better

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

Input

每个测试实例首先包括2个整数，N,M.(1 <= M <= N = 0。当N = 0, M = 0输入结束。

Output

对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。

Sample Input

3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0

Sample Output

5
13

Author

8600

Source

HDU 2006-12 Programming Contest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

const int maxn=210;

struct Edge
{
    int to,next;
    Edge(){}
    Edge(int v,int w):to(v),next(w){}
} edge[maxn];
int head[maxn];
int ve[maxn];
int n,m;
int f[maxn][maxn];

void addedge(int u,int v)
{
    edge[head[0]]=Edge(v,head[u]);
    head[u]=head[0]++;
}

void init()
{
    memset(head,-1,maxn*sizeof(head[0]));
    head[0]=1;
    ve[1]=0;
}

void dfs(int u)
{
    CLEAR(f[u],maxn);
    f[u][0]=ve[u];
    for(int i=head[u];i>-1;i=edge[i].next)
    {
        int v=edge[i].to;
        dfs(v);
        //for(int j=1;j<=m;j++) 密切关注状态转移方向和范围
            //for(int k=1;k<=m-j;k++)
                //f[u][j+k]=max(f[u][j+k],f[u][k]+f[v][j]);
        for(int j=m;j>0;j--)
            for(int k=1;k<=j;k++)
                f[u][j]=max(f[u][j],f[u][j-k]+f[v][k-1]);
        //cout<<u<<'-'<<v<<' '<<f[u][m]<<endl;
    }
    //for(int j=0;j<=m;j++) f[u][j]+=ve[u];边界条件
}

int main()
{

    while(~scanf("%d%d",&n,&m),n&&m)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a+1,i+1);
            ve[i+1]=b;
        }
        dfs(1);
        cout<<f[1][m]<<endl;
    }
    return 0;
}

Gold miner

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Homelesser likes playing Gold miners in class. He has to pay much attention to the teacher to avoid being noticed. So he always lose the game. After losing many times, he wants your help.

To make it easy, the gold becomes a point (with the area of 0). You are given each gold’s position, the time spent to get this gold, and the value of this gold. Maybe some pieces of gold are co-line, you can only get these pieces in order. You can assume it can turn to any direction immediately.
Please help Homelesser get the maximum value.

Input

There are multiple cases.
In each case, the first line contains two integers N (the number of pieces of gold), T (the total time). (0＜N≤200, 0≤T≤40000)
In each of the next N lines, there four integers x, y (the position of the gold), t (the time to get this gold), v (the value of this gold). (0≤|x|≤200, 0＜y≤200,0＜t≤200, 0≤v≤200)

Output

Print the case number and the maximum value for each test case.

Sample Input

3 10
1 1 1 1
2 2 2 2
1 3 15 9
3 10
1 1 13 1
2 2 2 2
1 3 4 7

Sample Output

Case 1: 3
Case 2: 7

Author

HIT

Source

2012 Multi-University Training Contest 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

int dblcmp(double d)
{
    if (fabs(d)<eps) return 0;
    else return (d>0)?1:-1;
}

struct data
{
    int x,y,t,v;
    data(){x=y=t=v=0;};
    data(int _x,int _y,int _t,int _v):x(_x),y(_y),t(_t),v(_v){};
    void prt()
    {
        cout<<x<<' '<<y<<' '<<t<<' '<<v<<endl;
    }
} gold[maxn];

int dist(data a)
{
    return a.x*a.x+a.y*a.y;
}

bool operator< (const data &a,const data &b)
{
    if (dblcmp(a.x * b.y - b.x * a.y)==0) return dist(a)<dist(b);
    return dblcmp(a.x * b.y - b.x * a.y)>0;
    //if (dist(a)==dist(b)) return dblcmp(a.x * b.y - b.x * a.y);
    //return dist(a)<dist(b);
}

bool operator== (const data &a,const data &b)
{
    return dblcmp(a.x * b.y - b.x * a.y)==0;
}

bool operator!= (const data &a,const data &b)
{
    return !(a==b);
}


typedef vector<data> vec;
typedef map<int,vec> hashmap;
hashmap mp;

int f[maxl];
vec vc[maxn];

int main()
{
    int n,m,kase=0;
    while(~scanf("%d%d",&n,&m))
    {
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            int x,y,t,v;
            scanf("%d%d%d%d",&x,&y,&t,&v);
            gold[i]=data(x,y,t,v);

        }
        //puts("--");
        sort(gold+1,gold+n+1);
        int cnt=1;
        vc[cnt].clear();
        for(int i=1;i<=n;i++)
        {
            if (vc[cnt].size())
            {
                data tmp=vc[cnt][vc[cnt].size()-1];
                gold[i]=data(gold[i].x,gold[i].y,gold[i].t+tmp.t,gold[i].v+tmp.v);
            }
            vc[cnt].push_back(gold[i]);
            if (gold[i]!=gold[i+1]) vc[++cnt].clear();
        }
        CLEAR(f);
        /*for(int k=1;k<=cnt;k++)
        {
            for(int i=0;i<vc[k].size();i++)
                vc[k][i].prt();
                puts("-");
        }*/

        for(int k=1;k<=cnt;k++)
            for(int j=m;j>=0;j--)
            for(int i=0;i<vc[k].size();i++)
                if (j>=vc[k][i].t)
                    f[j]=max(f[j],f[j-vc[k][i].t]+vc[k][i].v);



        printf("Case %d: %d\n",++kase,f[m]);
    }
    return 0;
}

Beam Cannon

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Recently, the γ galaxies broke out Star Wars. Each planet is warring for resources. In the Star Wars, Planet X is under attack by other planets. Now, a large wave of enemy spaceships is approaching. There is a very large Beam Cannon on the Planet X, and it is very powerful, which can destroy all the spaceships in its attack range in a second. However, it takes a long time to fill the energy of the Beam Cannon after each shot. So, you should make sure each shot can destroy the enemy spaceships as many as possible.
To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.

Input

Input contains multiple test cases. Each test case contains three integers N(1<=N<=10000, the number of enemy spaceships), W(1<=W<=40000, the width of the Beam Cannon’s attack area), H(1<=H<=40000, the height of the Beam Cannon’s attack area) in the first line, and then N lines follow. Each line contains two integers x,y (-20000<=x,y<=20000, the coordinates of an enemy spaceship).
A test case starting with a negative integer terminates the input and this test case should not to be processed.

Output

Output the maximum number of enemy spaceships the Beam Cannon can destroy in a single shot for each case.

Sample Input

2 3 4
0 1
1 0
3 1 1
-1 0
0 1
1 0
-1

Sample Output

2
2

Source

2014上海全国邀请赛——题目重现（感谢上海大学提供题目）

FATE

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

Input

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

Output

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

Sample Input

10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

Sample Output

0
-1
1

Author

Xhd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int f[maxn][maxn];//exp,sum
int v[maxn],w[maxn];

int main()
{
    int n,m,st,K;
    while(~scanf("%d%d%d%d",&st,&m,&n,&K))
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d",&v[i],&w[i]);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
            //for(int j=m;j>=0;j--)
            for(int j=w[i];j<=m;j++)
                for(int k=1;k<=K;k++)
                    f[j][k]=max(f[j][k],f[j-w[i]][k-1]+v[i]);
        /*int ans=0;
        for(int i=1;i<=K;i++) ans=max(ans,f[0][i]);
        if (ans<st) printf("-1\n");
        else printf("%d\n",ans);*/
        bool ans=0;
        for(int i=1;i<=m;i++)
            if (f[i][K]>=st)
        {
            ans=1;
            printf("%d\n",m-i);
            break;
        }
        if (!ans) printf("-1\n");
    }
    return 0;
}

Tom and paper

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem Description

There is a piece of paper in front of Tom, its length and width are integer. Tom knows the area of this paper, he wants to know the minimum perimeter of this paper.

Input

In the first line, there is an integer T indicates the number of test cases. In the next T lines, there is only one integer n in every line, indicates the area of paper.
$ T\leq 10,n\leq {10}^{9} $

Output

For each case, output a integer, indicates the answer.

Sample Input

3
2
7
12

Sample Output

6
16
14

• 暴力枚举啊，怎么刚开赛那会儿就想不通了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        int i, a, b;
        if (n > 1)
            for (i = (int)sqrt(n); i > 0; i++)
            {
                a = i;
                b = n / a;
                if (a * b == n)
                {
                    break;
                }
            }
        else
        {
            a = 1;
            b = n / a;
        };
        //cout<<a<<' '<<b<<endl;
        printf("%d\n", 2 * a + 2 * b);
    }
    return 0;
}

Tom and permutation

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Tom has learned how to calculate the number of inversions in a permutation of n distinct objects by coding, his teacher gives him a problem:
Give you a permutation of n distinct integer from 1 to n, there are many permutations of 1-n is smaller than the given permutation on dictionary order, and for each of them, you can calculate the number of inversions by coding. You need to find out sum total of them.
Tom doesn’t know how to do, he wants you to help him.
Because the number may be very large, output the answer to the problem modulo $ {10}^{9}+{7} $ .

Input

Multi test cases(about 20). For each case, the first line contains a positive integer n, the second line contains n integers, it’s a permutation of 1-n. $ n\leq 100 $

Output

For each case, print one line, the answer to the problem modulo $ {10}^{9}+7 $ .

Sample Input

3
2 1 3
5
2 1 4 3 5

Sample Output

1
75

Hint

The input may be very big, we might as well optimize input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stdlib.h>
#include <queue>
#include <math.h>
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std ;

typedef long long LL ;

int  a[108] ;
LL   dp[108]  , fac[108] ;
LL   big[108] , les[108] , eb[108] ;
LL   N[108] ;

const LL  mod = 1000000007LL ;

int  main(){


     fac[0] = 1LL ;
     for(LL i = 1 ; i <= 100 ; i++){
           fac[i] = fac[i-1] * i % mod ;
     }
     dp[1] = 0LL ;
     for(LL i = 2 ; i <= 100 ; i++){
          dp[i] = i * dp[i-1] % mod + i*(i-1)/2 * fac[i-1] % mod ;
     }
/*
     for(int i = 1 ; i <= 100 ; i++){
         cout<< i << "  " <<dp[i]<<endl ;
     }

/*
     int n  ;
     while(cin>>n){
           for(int i = 0 ; i < n ; i++) a[i] =  i ;

           int s = 0 ;
           do{

                for(int i = 0 ; i < n ; i++){
                     for(int j = i+1 ; j < n ; j++){
                          if(a[i] > a[j]) s++ ;
                     }
                }

           }while(next_permutation(a , a+n)) ;

           cout<< n<<" : " << s << endl ;

     }

  */
     int n ;
while(scanf("%d" , &n) != EOF){

     for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]) ;

     memset(N , 0 , sizeof(N)) ;

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

        LL s = 0 ;
        for(int j = 1 ; j < i ; j++){
              if(a[j] > a[i]) s++ ;
        }
        N[i] = N[i-1] + s ;
     }


     for(int i = 1 ; i <= n ; i++){
           big[i] = les[i] = 0LL ;

           for(int j = 1 ; j < i ; j++){
              if(a[j] > a[i]) big[i]++ ;
           }
           for(int j = i+1 ; j <= n ; j++){
               if(a[j] < a[i]) les[i]++ ;
           }
     }

     memset(eb , 0 , sizeof(eb)) ;

     for(int k = 1 ; k <= n ; k++){
          for(int i = 1 ; i < k ; i++){
              for(int j = k ; j <= n ; j++){
                  if(a[i] > a[j]) eb[k]++ ;
              }
          }
     }

     LL sum = 0 ;
     for(int i = 1 ; i <= n ; i++){

          sum += (eb[i] + N[i-1])*(les[i] * fac[n-i] )% mod ;
          sum %= mod ;
          sum += fac[n-i] * (les[i] * (les[i]-1) / 2) % mod ;
          sum %= mod ;
          sum += dp[n-i] * les[i] % mod ;
          sum %= mod ;
     }

     cout<< sum << endl ;
}

     return 0 ;
}

Tom and matrix

Time Limit: 3000/1500 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Tom was on the way home from school. He saw a matrix in the sky. He found that if we numbered rows and columns of the matrix from 0, then, $ {a} _ {i,j}={C} _ {i}^{j}$
if i < j, $ {a}_{i,j}=0$
Tom suddenly had an idea. He wanted to know the sum of the numbers in some rectangles. Tom needed to go home quickly, so he wouldn’t solve this problem by himself. Now he wants you to help him.
Because the number may be very large, output the answer to the problem modulo a prime p.

Input

Multi test cases(about 8). Each case occupies only one line, contains five integers, $ x_{1}、y_{1}、x_{2}、y_{2}、p.
x_{1}\leq x_{2}\leq {10}^{5},y_{1}\leq y_{2}\leq {10}^{5},2\leq p\leq {10}^{9}$ .

Output

For each case, print one line, the answer to the problem modulo p.

Sample Input

0 0 1 1 7
1 1 2 2 13
1 0 2 1 2

Sample Output

3
4
1

1

原文地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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

typedef long long lld;
lld  n, m, p;

lld Ext_gcd(lld a,lld b,lld &x,lld &y){
   if(b==0) { x=1, y=0; return a; }
   lld ret= Ext_gcd(b,a%b,y,x);
   y-= a/b*x;
   return ret;
}
lld Inv(lld a,int m){   ///求逆元
   lld d,x,y,t= (lld)m;
   d= Ext_gcd(a,t,x,y);
   if(d==1) return (x%t+t)%t;
   return -1;
}

lld Cm(lld n, lld m, lld p)  ///组合数学
{
    lld a=1, b=1;
    if(m>n) return 0;
    while(m)
    {
        a=(a*n)%p;
        b=(b*m)%p;
        m--;
        n--;
    }
    return (lld)a*Inv(b,p)%p;  ///（a/b）%p 等价于 a*（b，p）的逆元
}

int Lucas(lld n, lld m, lld p)  ///把n分段递归求解相乘
{
    if(m==0) return 1;
    return (lld)Cm(n%p,m%p,p)*(lld)Lucas(n/p,m/p,p)%p;
}

int main()
{
    int  T;
    cin >> T;
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&m,&p);
        printf("%d\n",Lucas(n+m,m,p));
    }
    return 0;
}

原文地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int gcd(int n,int m)//n>m
{
    //最大公约数
    int r;
    while(m)
    {
        r = n%m;
        n = m;
        m = r;
    }
    return n;
}

int kgcd(int a,int b)
{
    if(!a) return b;
    if(!b) return a;
    if(!(a&1) && !(b&1))
        return kgcd(a>>1,b>>1)<<1;
    else if(!(b&1)) return kgcd(a,b>>1);
    else if(!(a&1)) return kgcd(a>>1,b);
    else return kgcd(abs(a-b),min(a,b));
}

//扩展欧几里得
//求方程ax+by+c = 0有多少整数解
int extgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int d = extgcd(b,a%b,x,y);
    int t = x;
    x=y;
    y=t-a/b*y;
    return d;
}