Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 245 words)

2015 ACM-ICPC 上海5 24 现场状态

比赛过程中忘了写chs函数导致无论如何都调试不成
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define CLEAR(a,n) memset((a),0,n*sizeof((a)[0]))

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]={‘&#92;&#48;’};
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=’&#92;&#48;’;
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]

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;
    }
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

×