Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 169 words)

2015 ACM-ICPC 上海大都会赛简要总结

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

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

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

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 504 words)

hdu 4821 String hash乱搞

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;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 269 words)

ACM-ICPC Regionals 2013 >> Asia - Aizu - Count the Regions

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;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing10 minutes read (About 1544 words)

多样的背包问题回顾

饭卡

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;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 640 words)

Bestcoder

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

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 207 words)

【HDU 3037】大数组合取模之Lucas定理

原文地址

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;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 136 words)

【模板】各种欧几里得

原文地址 

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;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1120 words)

2013ACM-ICPC杭州赛区全国邀请赛

Transformation（HDU 4578）

Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 65535/65536 K (Java/Others)

Problem Description

Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation ak<—ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<—ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489

  • TLE，不必在每次query时都更新到叶结点 

    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
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    struct Node
    {
        int l,r,mid;
        LL v,add,mul;
    } SegTree[maxn*4];

    void build(int rt,int l,int r)
    {
        SegTree[rt].l=l;SegTree[rt].r=r;
        SegTree[rt].mid=(l+r)>>1;
        SegTree[rt].add=SegTree[rt].v=0;
        SegTree[rt].mul=1;
        if (l<r)
        {
            build(rt<<1,l,SegTree[rt].mid);
            build(rt<<1|1,SegTree[rt].mid+1,r);
        }
    }

    void add(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].add+=num;
            SegTree[rt].add%=mod;
            return;
        }
        int tmp=SegTree[rt].add;
        if (SegTree[rt].add)
        {

            SegTree[rt].add=0;
            add(rt,SegTree[rt].l,x-1,tmp);
            add(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) add(rt<<1,x,min(mid,y),tmp+num);
        if (y>mid) add(rt<<1|1,max(mid+1,x),y,tmp+num);
    }

    void mul(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
            SegTree[rt].add*=num;SegTree[rt].add%=mod;
            return;
        }
        int tmp=SegTree[rt].mul;
        if (SegTree[rt].mul!=1)
        {
            SegTree[rt].mul=1;
            add(rt,SegTree[rt].l,x-1,SegTree[rt].add*tmp);
            mul(rt,SegTree[rt].l,x-1,tmp);
            add(rt,x,y,SegTree[rt].add*tmp*num);
            add(rt,y+1,SegTree[rt].r,SegTree[rt].add*tmp);
            mul(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) mul(rt<<1,x,min(mid,y),tmp*num);
        if (y>mid) mul(rt<<1|1,max(mid+1,x),y,tmp*num);
    }

    void cover(int rt,int x,int y,int num)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        if (x>y) return;
        //cout<<"c "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x<=SegTree[rt].l&&SegTree[rt].r<=y)
        {
            SegTree[rt].v=num;
            SegTree[rt].add=0;
            SegTree[rt].mul=1;
            return;
        }
        if (SegTree[rt].add)
        {
            int tmp=SegTree[rt].add;
            SegTree[rt].add=0;
            add(rt,SegTree[rt].l,x-1,tmp);
            add(rt,y+1,SegTree[rt].r,tmp);
        }
        if (SegTree[rt].mul!=1)
        {
            int tmp=SegTree[rt].mul;
            SegTree[rt].mul=1;
            mul(rt,SegTree[rt].l,x-1,tmp);
            mul(rt,y+1,SegTree[rt].r,tmp);
        }
        if (x<=mid) cover(rt<<1,x,min(mid,y),num);
        if (y>mid) cover(rt<<1|1,max(mid+1,x),y,num);
    }

    LL query(int rt,int x,int y,int p)
    {
        int &l=SegTree[rt].l,&r=SegTree[rt].r,&mid=SegTree[rt].mid;
        //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
        if (SegTree[rt].l==SegTree[rt].r)
        //if (SegTree[rt].v)
        {
            SegTree[rt].v*=SegTree[rt].mul;SegTree[rt].v%=mod;
            SegTree[rt].v+=SegTree[rt].add;SegTree[rt].v%=mod;
            SegTree[rt].add=0;
            SegTree[rt].mul=1;
            switch(p)
            {
                case 1:return SegTree[rt].v;
                case 2:return SegTree[rt].v*SegTree[rt].v%mod;
                case 3:return SegTree[rt].v*SegTree[rt].v*SegTree[rt].v%mod;
            }

        }
        if (SegTree[rt].v)
        {
            add(rt<<1,l,mid,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
            add(rt<<1|1,mid+1,r,SegTree[rt].v*SegTree[rt].mul+SegTree[rt].add);
            SegTree[rt].v=0;
        }
        if (SegTree[rt].add)
        {
            //puts("update");
            add(rt<<1,l,mid,SegTree[rt].add);
            add(rt<<1|1,mid+1,r,SegTree[rt].add);
            SegTree[rt].add=0;
        }
        if (SegTree[rt].mul!=1)
        {
            mul(rt<<1,l,mid,SegTree[rt].mul);
            mul(rt<<1|1,mid+1,r,SegTree[rt].mul);
            SegTree[rt].mul=1;
        }
        return (((x<=mid)?query(rt<<1,x,min(mid,y),p):0)+((y>mid)?query(rt<<1|1,max(mid+1,x),y,p):0))%mod;

    }

    LL fnd(int rt,int x)
    {
        if(SegTree[rt].l==SegTree[rt].r) return SegTree[rt].v;
        else if (x<=SegTree[rt].mid) return fnd(rt<<1,x);
        else return fnd(rt<<1|1,x);
    }

    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if (!n&&!m) break;
            build(1,1,n);
            for(int i=1;i<=m;i++)
            {
                int op,x,y,c;
                scanf("%d%d%d%d",&op,&x,&y,&c);
                switch(op)
                {
                    case 1:
                        add(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 2:
                        mul(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 3:
                        cover(1,x,y,c);//query(1,x,y,1);
                        break;
                    case 4:
                        printf("%I64d\n",query(1,x,y,c));
                        break;
                }
                //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
            }
        }
        return 0;
    }

  • AC 4882MS 

    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
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    #include<cctype>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<stack>
    #include<set>
    #include<map>
    #define CLEAR(a) memset((a),0,sizeof((a)))

    using namespace std;

    typedef long long LL;
    const double pi = acos(-1.0);
    const int maxn = 1e5 + 10;
    const int inf = 99999999;
    const double eps = 1e-3;
    const int mod = 10007;

    struct Node
    {
        int l, r, mid;
        LL v, add, mul;
        bool up;
    } SegTree[maxn * 4];

    void build(int rt, int l, int r)
    {
        SegTree[rt].l = l;
        SegTree[rt].r = r;
        SegTree[rt].mid = (l + r) >> 1;
        SegTree[rt].add = SegTree[rt].v = 0;
        SegTree[rt].mul = 1;
        if (l < r)
        {
            SegTree[rt].up = 0;
            build(rt << 1, l, SegTree[rt].mid);
            build(rt << 1 | 1, SegTree[rt].mid + 1, r);
        }
        else
        {
            SegTree[rt].up = 1;
        }
    }

    void pushdown(int rt)
    {
        int mid = SegTree[rt].mid;
        if (SegTree[rt].up)
        {
            SegTree[rt << 1].add = SegTree[rt << 1 | 1].add = 0;
            SegTree[rt << 1].mul = SegTree[rt << 1 | 1].mul = 1;
            SegTree[rt << 1].v = SegTree[rt << 1 | 1].v = SegTree[rt].v;
            SegTree[rt << 1].up = SegTree[rt << 1 | 1].up = 1;
            SegTree[rt].up = 0;
        }
        else
        {
            if (SegTree[rt].add)
            {
                if (SegTree[rt << 1].up)
                {
                    SegTree[rt << 1].v += SegTree[rt].add;
                    SegTree[rt << 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1);
                    SegTree[rt << 1].add += SegTree[rt].add;
                    SegTree[rt << 1].add %= mod;
                }
                if (SegTree[rt << 1 | 1].up)
                {
                    SegTree[rt << 1 | 1].v += SegTree[rt].add;
                    SegTree[rt << 1 | 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1 | 1);
                    SegTree[rt << 1 | 1].add += SegTree[rt].add;
                    SegTree[rt << 1 | 1].add %= mod;
                }
                SegTree[rt].add = 0;
            }
            if (SegTree[rt].mul != 1)
            {
                if (SegTree[rt << 1].up)
                {
                    SegTree[rt << 1].v *= SegTree[rt].mul;
                    SegTree[rt << 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1);
                    SegTree[rt << 1].mul *= SegTree[rt].mul;
                    SegTree[rt << 1].mul %= mod;
                }
                if (SegTree[rt << 1 | 1].up)
                {
                    SegTree[rt << 1 | 1].v *= SegTree[rt].mul;
                    SegTree[rt << 1 | 1].v %= mod;
                }
                else
                {
                    pushdown(rt << 1 | 1);
                    SegTree[rt << 1 | 1].mul *= SegTree[rt].mul;
                    SegTree[rt << 1 | 1].mul %= mod;
                }
                SegTree[rt].mul = 1;
            }
        }
    }

    void update(int rt, int x, int y, LL num,int op)
    {
        int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
        //cout<<"+ "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<x<<' '<<y<<' '<<num<<endl;
        if (x <= SegTree[rt].l && SegTree[rt].r <= y)
        {
            if (op==3)
            {
                SegTree[rt].add=0;
                SegTree[rt].mul=1;
                SegTree[rt].v=num;
                SegTree[rt].up=1;
            }
            else
            {
                if (SegTree[rt].up)
                {
                    if (op==1)
                    {
                        SegTree[rt].v+=num;SegTree[rt].v%=mod;
                    }
                    else
                    {
                        SegTree[rt].v*=num;SegTree[rt].v%=mod;
                    }
                }
                else
                {
                    pushdown(rt);
                    if (op==1)
                    {
                        SegTree[rt].add+=num;SegTree[rt].add%=mod;
                    }
                    else
                    {
                        SegTree[rt].mul*=num;SegTree[rt].mul%=mod;
                    }
                }
            }
            return;
        }
        pushdown(rt);
        if (x <= mid)
            update(rt << 1, x, min(mid, y), num,op);
        if (y > mid)
            update(rt << 1 | 1, max(mid + 1, x), y, num,op);
    }

    LL query(int rt, int x, int y, int p)
    {
        int& l = SegTree[rt].l, &r = SegTree[rt].r, &mid = SegTree[rt].mid;
        //cout<<"q "<<rt<<' '<<l<<' '<<r<<' '<<mid<<"  "<<SegTree[rt].v<<' '<<SegTree[rt].add<<' '<<SegTree[rt].mul<<endl; //<<"  "<<x<<' '<<y<<' '<<endl;
        if (x <= SegTree[rt].l && SegTree[rt].r <= y&&SegTree[rt].up)
        {
            LL tmp=LL(r-l+1)%mod;
            for(int i=1;i<=p;i++)
            {
                tmp*=SegTree[rt].v;tmp%=mod;
            }
            return tmp;
        }
        pushdown(rt);
        return (((x <= mid) ? query(rt << 1, x, min(mid, y), p) : 0LL) + ((y > mid) ? query(rt << 1 | 1, max(mid + 1, x), y, p) : 0LL)) % mod;
    }

    LL fnd(int rt, int x)
    {
        if (SegTree[rt].l == SegTree[rt].r)
        {
            return SegTree[rt].v;
        }
        else if (x <= SegTree[rt].mid)
        {
            return fnd(rt << 1, x);
        }
        else
        {
            return fnd(rt << 1 | 1, x);
        }
    }

    int main()
    {
        int n, m;
        while (~scanf("%d%d", &n, &m))
        {
            if (!n && !m)
            {
                break;
            }
            build(1, 1, n);
            for (int i = 1; i <= m; i++)
            {
                int op, x, y;
                LL c;
                scanf("%d%d%d%I64d", &op, &x, &y, &c);
                switch (op)
                {
                    case 1:
                    case 2:
                    case 3:
                        update(1, x, y, c,op); //query(1,x,y,1);
                        break;
                    case 4:
                        printf("%I64d\n", query(1, x, y, c));
                        break;
                }
                //for(int i=1;i<=n;i++) printf("%lld ",fnd(1,i));printf("\n");
            }
        }
        return 0;
    }
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing9 minutes read (About 1303 words)

ACM - ICPC Regionals 2014 Bangkok 亚洲区域赛 国外某数学题

ACM-ICPC Live Archive Regionals 2014 >> Asia - Bangkok
6844 - Combination
=====

原题页面
PDF题面
Vjudge提交地址

艰辛坎坷的探索历程

设 $ {f(n)=C_{n}^{r}(n∈N^{ * },r∈[0,n])} $中奇数的个数。
题意是说，求出 $ \sum f(k),k∈[low,high] $
庞大的数据， $ n≤16\times{10^{11}}. $

step1

判断给定 $ n∈N^{ * } $时 $ C_n^r(r∈[0,n]) $的奇偶性。 不难往n,r的二进制表示方向考虑。
查阅他人博客获得结论： $ n{ & }r==r $时 $ C_n^r $为奇数。 然而本题中无需直接应用这一“定理”，所要做的是统计。
拿出纸笔推算发现，若n的二进制表示中有d个1，则 $ C_n^r(r∈[0,n]) $中存在 $ 2^d $个奇数。

step2

研究 $ f(n) $ 的递推关系及通项。 编写暴力程序 $ O(n^2) $ ，打表观察 $ n∈[0,64) $ 时 $ f(n) $ 的取值：
1
2
2 4
2 4 4 8
2 4 4 8 4 8 8 16
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32
2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 4 8 8 16 8 16 16 32 8 16 16 32 16 32 32 64
第一行 $ f(0)=1 $ 作为边界条件， 第二行 $ f(1)=2 $ ，随后各行的第k行的 $ 2^{k-2} $ 个数分别表示 $ f(2^{k-2}),f(2^{k-2}+1),…,f(2^{k-1}-1) $ 。
通过不懈的努力，观察发现从第3行开始，每行的前半部分与前一行完全一致，每行的后半部分的各个f值恰为前半部分对应位置的f值的2倍。

step3

出于数列直觉，我们尝试求解各行的和构成的数列的递推以及通项。
$ a_1=1 $
$ a_2=2 $
$ a_3=a_2+2\times{a_2}=3\times{a_2}=6 $
…
$ a_n=a_{n-1}+2\times{a_{n-1}}=3\times{a_{n-1}}(n\geq 3) $（递推公式）
通项公式:
$$
\begin{equation} a_n= \begin{cases} 1 &\mbox{$n=1$}\newline 2 &\mbox{$n=2$}\newline 2\times3^{n-2} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
\begin{equation} S_n=\sum\limits_{i=1}^{n} {a_i}= \begin{cases} 1 &\mbox{$n=1$}\newline 3 &\mbox{$n=2$}\newline 3+6\times\frac{1-3^{n-2}}{1-3}=3+3\times{(3^{n-2}-1)}=3^{n-1} &\mbox{$n\geq 3$} \end{cases} \end{equation}
$$

$$
S_n=3^{n-1}（a_n的前n项和的公式）
$$
化简后上面这个公式样子够好看了吧？

step4

再看一下第2步发现的规律，应用“二分”手段高效地求解，而且真的可以二分求解。
具体地说，就是先置求解区间 $ [l,r) $ (左闭右开)的端点于每行的头尾( $ l=2^{i-2},r=2^{i-1} $ )，利用上一步所得公式计算该区间的 $ 左端点前缀和U=\sum\limits_{k=1}^{2^{i-2}} {f(k)} $ 与 $ 右端点前缀和V=\sum\limits_{k=1}^{2^{i-1}-1} {f(k)} $ 后，不断地对区间折半，总可以确定新区间的左端点前缀和与右端点前缀和。
当区间缩至一点时， $ U==V==f(k) $，即能得到我们所求，而无需计算出[1..n]的每个函数值。

step5

以上所解决的并不是最终答案，而是前缀和 $ \sum\limits_{k=1}^{n} {f(k)} $ ；
不过走到这一步已经很好办了， $ ans=\sum\limits_{k=low}^{high} {f(k)}=\sum\limits_{k=1}^{high} {f(k)}-\sum\limits_{k=1}^{low-1} {f(k)} $

PS:写完代码后，用极大的n值测试一下，事实上 $ \sum\limits_{k=1}^{n} {f(k)} $已经超出了int64的范围。其他的细节不必多说了。

1.319s AC java代码：

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
/**
 * @date 2015-05-31
 * @author Semprathlon
 */
import java.math.*;
import java.io.*;

public class Main {
    static int maxn=42;
    static BigInteger[] sum=new BigInteger[maxn];
    static long[] Pow2=new long[maxn];
    final static BigInteger TWO=BigInteger.valueOf(2);
    final static BigInteger THREE=BigInteger.valueOf(3);
    
    static int found_pow2(long n){
        return (int)(Math.log((double)n)/Math.log(2.0));
    }

    static void init(){
        for(int i=0;i<maxn;i++)
        {
            sum[i]=THREE.pow(i);
            Pow2[i]=1L<<i;
        }
            
    }
    static BigInteger Bisearch(long l,long r,BigInteger ls,BigInteger rs,long key){
        while(l+1L<r){
            long mid=(l+r)>>1;
            if(key<mid){
                r=mid;
                rs=ls.add(rs.subtract(ls).divide(THREE));
            }
            else{
                l=mid;
                ls=ls.add(rs.subtract(ls).divide(THREE));
            }
        }
        return ls;
    }
    static BigInteger solve(long n){
        if (n<0L) return BigInteger.ZERO;
        if (n==0L) return BigInteger.ONE;
        int k=found_pow2(n+1);
        BigInteger ls=sum[k];
        BigInteger rs=sum[k+1];
        return Bisearch(Pow2[k],Pow2[k+1],ls,rs,n+1);
    }
    public static void main(String[] args) throws IOException{
        init();
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n=0,m=0;
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            n=(long)in.nval;
            in.nextToken();
            m=(long)in.nval;
            if (n==0L&&m==0L) break;
            out.println(solve(m).subtract(solve(n-1)));
        }
        out.flush();
        out.close();
    }
}

0.279s AC cpp代码： 

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 42;
const LL mod = 1e8;
const int digit = 8;
struct LongInt
{
    LL data[3];
    LongInt()
    {
        data[0] = data[1] = data[2] = 0;
    }
    LongInt(LL n)
    {
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
    }
    LongInt operator= (const LL num)
    {
        LL n = num;
        data[0] = n % mod;
        n /= mod;
        data[1] = n % mod;
        n /= mod;
        data[2] = n;
        return *this;
    }
    LongInt operator+ (const LL& num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] += n;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator+ (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] += b.data[0];
        tmp.data[1] += b.data[1];
        tmp.data[2] += b.data[2];
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator- (const LongInt& b)
    {
        LongInt tmp = *this;
        tmp.data[0] -= b.data[0];
        if (tmp.data[0] < 0)
        {
            tmp.data[1]--;
            tmp.data[0] += mod;
        }
        tmp.data[1] -= b.data[1];
        if (tmp.data[1] < 0)
        {
            tmp.data[2]--;
            tmp.data[1] += mod;
        }
        tmp.data[2] -= b.data[2];
        return tmp;
    }
    LongInt operator* (const LL num)
    {
        LL n = num;
        LongInt tmp = *this;
        tmp.data[0] *= num;
        tmp.data[1] *= num;
        tmp.data[2] *= num;
        tmp.data[1] += tmp.data[0] / mod;
        tmp.data[0] %= mod;
        tmp.data[2] += tmp.data[1] / mod;
        tmp.data[1] %= mod;
        return tmp;
    }
    LongInt operator*= (const LL num)
    {
        *this = *this * num;
        return *this;
    }
    LongInt operator/ (const LL num)
    {
        LongInt tmp = *this;
        tmp.data[1] += tmp.data[2] % num * mod;
        tmp.data[2] /= num;
        tmp.data[0] += tmp.data[1] % num * mod;
        tmp.data[1] /= num;
        tmp.data[0] /= num;
        return tmp;
    }
    void fillzero(int n)
    {
        char str[digit * 2];
        sprintf(str, "%d", n);
        for (int i = 1; i <= digit - strlen(str); i++)
        {
            printf("%d", 0);
        }
        printf("%s", str);
    }
    void print()
    {
        if (data[2] > 0)
        {
            printf("%d", data[2]);
            fillzero(data[1]);
            fillzero(data[0]);
        }
        else if (data[1] > 0)
        {
            printf("%d", data[1]);
            fillzero(data[0]);
        }
        else
        {
            printf("%d", data[0]);
        }
    }
};

const LL pow2[maxn] = {1, 2, 4, 8, 16, 32, 64, 128,
                       256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
                       65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
                       16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648,
                       4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888,
                       1099511627776, 2199023255552
                      };
/*const ULL sum[maxn] = {3, 5, 11, 29, 83, 245, 731, 2189,
                       6563, 19685, 59051, 177149, 531443, 1594325, 4782971, 14348909,
                       43046723, 129140165, 387420491, 1162261469, 3486784403, 10460353205, 31381059611, 94143178829,
                       282429536483, 847288609445, 2541865828331, 7625597484989, 22876792454963, 68630377364885, 205891132094651, 617673396283949,
                       1853020188851843, 5559060566555525, 16677181699666571, 50031545098999709, 150094635296999123, 450283905890997365, 1350851717672992091, 4052555153018976269,
                       12157665459056928803
                      };*/
LongInt sum[maxn];

int found_pow2(ULL n)
{
    return int(log(n) / log(2));
}

LongInt Bisearch(LL l, LL r, LongInt ls, LongInt rs, LL key) // [ l , r ) 
{
    while (l + 1 < r)
    {
        ULL mid = (l + r) >> 1;
        if (key < mid)
        {
            r = mid;
            rs = (rs - ls) / 3 + ls;
        }
        else
        {
            l = mid;
            ls = (rs - ls) / 3 + ls;
        }
    }
    return ls;
}

LongInt solve(LL n)
{
    if (n < 0)
    {
        return 0;
    }
    if (!n)
    {
        return 1;
    }
    int k = found_pow2(n + 1);
    LongInt ls = sum[k];
    LongInt rs = sum[k + 1];
    return Bisearch(pow2[k], pow2[k + 1], ls, rs, n + 1);
}

void init()
{
    LongInt tmp = 1;
    for (int i = 0; i < maxn; i++)
    {
        sum[i] = tmp;
        tmp *= 3;
    }
}

int main()
{
    init();
    LL n, m;
    while (cin >> n >> m)
    {
        if (!n && !m)
        {
            break;
        }
        LongInt ans = solve(m) - solve(n - 1);
        ans.print();
        puts("");
    }
    return 0;
}
Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×