题解

蓝桥杯准备

[toc]

2020CCPC绵阳 K- Knowledge is Power

①如果x是奇数，那么拆分为x/2和x-x/2，答案是1

②如果x是偶数并且x/2是偶数，，那么可以分成x/2+1，x/2-1这是分成了两个奇数，一定互质，答案是2

③如果x是偶数并且x/2是奇数，那么我们对x取余3进行判断。

如果是3的倍数，比如42，可以拆成13 14 15.那么答案是2

如果取模3后余1，比如70 可以分成22 23 25 答案是3

取模3余2，比如62 可以分成19 21 22 答案是3

按照上面构造方式 判断一下是不是两两互质即可

容易发现答案最多为4，因为如果x是偶数，x/2是奇数，那么只需要拆分为x/2-2、x/2+2即可

④注意特判x=6时候无解

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
#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i = i +2 ){
        int temp;
        temp = i;

        if(temp == 6){
             cout << "Case #" << i << ": "<< -1 <<endl;
             continue;
        }

        if(temp %2 != 0){
            cout << "Case #" << i << ": "<< 1 <<endl;
                        continue;
        }
        else{
            int a = temp / 2;
            int b,c;
            if(temp % 3 == 0){
                cout << "Case #" << i << ": "<< 2 <<endl;
                continue;
            }
            else if(a % 2 == 0){
                cout << "Case #" << i << ": "<< 2 <<endl;
                            continue;
            }
            else if( temp % 3 == 1 ){
                a = temp/3;     b = a - 1;  c = a + 2;
                if(__gcd(a,b)==1 && __gcd(a,c)==1 && __gcd(c,b)==1 ){
                    cout << "Case #" << i << ": "<< 3 <<endl;
                    //cout << a << " " << b << " " << c << endl;
                }
                else    cout << "Case #" << i << ": "<< 4 <<endl;
                continue;
            }
            else if(temp % 3 == 2){
                a = temp/3 - 1;     b = a + 2;  c = a + 3;
                if(__gcd(a,b)==1 && __gcd(a,c)==1 && __gcd(c,b)==1 ){
                    cout << "Case #" << i << ": "<< 3 <<endl;
                    //cout << a << " " << b << " " << c << endl;
                }
                else    cout << "Case #" << i << ": "<< 4 <<endl;
                continue;
            }

        }

    }

    return 0;
}

acwing 八重码

此题为 bfs + hash表

重点是在3x3数组的状态枚举

以及二维数组，如何一维操作

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
#include <bits/stdc++.h>
using namespace std;

int bfs(string start)
{
    
    string End = "12345678x";
    
    queue<string> q;
    q.push(start);
    unordered_map<string,int> d;    ///把二维数组，变为一维，在用字符串的形式压入队列
    d[start] = 0;                   ///初始化状态的变换次数为0
    
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    
    while( !q.empty() ){
        
        auto t = q.front();
        q.pop();
        
        if( t == End) return d[t];
        
        int dis =d[t];
        int loc = t.find('x');
        **int x = loc / 3, y = loc % 3;**       ///将一维数组，转换为二维坐标
        
        for(int i  = 0; i < 4; i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if( tx >= 0 && ty < 3 && tx < 3 && ty >=0 ){
                
                swap(t[loc] , t[**tx*3 + ty**]);
                
                if( !d.count(t) ){
                    
                    d[t] = dis + 1;
                    q.push(t);
                    
                }
                
                swap(t[loc] , t[**tx*3 + ty**]);    ///讲状态变回去，方便其他状态的枚举
            }
                
            
        }
        
    }
    
    return -1;
     
}
int main()
{
    string start;
    for(int i = 0 ; i < 9; i ++){
        char a ;
        cin >> a;
        start += a;
    }
    
    cout << bfs(start) <<endl;
    
    return 0;
}

https://blog.csdn.net/lytwy123/article/details/83419593?ops_request_misc=%7B%22request%5Fid%22%3A%22160592898119724836756296%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=160592898119724836756296&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-1-83419593.pc_search_result_no_baidu_js&utm_term=校门外的数&spm=1018.2118.3001.4449

待补算法:

1____模拟退火

星星还是树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

struct Point
{
    double x,y;
}p[105];
double eps = 1e-8;

int n;

double fun(Point tep)
{
    double teans = 0;
    for(int i = 0; i < n ; i++)
    {
        teans += hypot( tep.x - p[i].x , tep.y - p[i].y );
    }
    return teans;
}

double solve()
{
    double T = 10000;
    double delta = 0.97;
    Point nowp;
    nowp.x = 5000,nowp.y = 5000;
    double now = fun(nowp);
    double ans = now;
    while( T > eps )
    {
        int f[2] = {1,-1};
        Point newp = {nowp.x + f[rand()%2] * T , nowp.y + f[rand()%2] * T };
        if( newp.x >= 0 && newp.x <= 10000 && newp.y >= 0 && newp.y <= 10000 )
        {
            double next = fun(newp);
            // printf("%.4lf   %.4lf    %.4lf\n",ans,newx,next);
            ans = min(ans,next);
            if( now - next  > eps) { nowp = newp , now = next; }
        }
        T *= delta;
    }
    return ans;
}

int main()
{
    srand((unsigned)time(NULL));
    scanf("%d",&n);

    for(int i = 0 ; i < n ; i ++)
    {
        scanf("%lf%lf",&p[i].x ,&p[i].y);
    }

    double an = solve();
    an +=0.5;
    printf("%d\n",(int)an );

}

通电围栏

这两个都是可三分可退火

Strange fuction

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
#include <bits/stdc++.h>
using namespace std;

double y;
const double eps = 1e-10;

double fun(double x)
{
    return 6*pow(x,7.0) + 8 * pow(x,6.0) + 7 * pow(x , 3.0) + 5 * pow(x , 2.0) - y * x;
}

double solve()
{
    double T = 100;
    double delta = 0.98;
    double x = 50.0;
    double now = fun(x);
    double ans = now;
    while( T > eps )
    {
        int f[2] = {1,-1};
        double newx = x + f[rand()%2] * T;
        if( newx >= 0 && newx <= 100 )
        {
            double next = fun(newx);
            // printf("%.4lf   %.4lf    %.4lf\n",ans,newx,next);
            ans = min(ans,next);
            if( now - next  > eps) { x = newx , now = next; }
        }
        T *= delta;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%lf",&y);
        printf("%.4lf\n",solve());
    }

}

Groundhog Build Home(最小圆覆盖)

1

2____字符串

2.1____KMP

Censor—训练赛2015四川省赛

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5000005;
char p[maxn],s[maxn];
int ne[maxn];

int n,m;

void get_next()
{
    for(int i = 2 , j = 0 ; i <= n ; i++){

        while( j && p[i] != p[j + 1] ) j = ne[j];
        if( p[i] == p[j + 1] ) j++;
        ne[i] = j;
    }
}

void KMP()
{
    stack<char> ans;
    stack<int> pos;

    for(int i = 1, j = 0; i <= m ; i++ ){
        while( j && s[i] != p[j + 1] ) j = ne[j];
        if( s[i] == p[j + 1] ) j++;

        pos.push( j );
        ans.push(s[i]);

        if( j == n ){

            for(int l = 0 ; l < n ; l ++) {pos.pop(),ans.pop();}

            if( pos.empty() ) j = 0;
            else j = pos.top();

        }

    }

    vector<char> an;
    while( !ans.empty() ){
        an.push_back( ans.top() );
        ans.pop();
    }

    for(int i = an.size() - 1; i >= 0 ; i--){
        cout << an[i] ;
    }
    cout <<endl;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while( cin >> p + 1 >> s + 1 ){
        n = strlen( p + 1 );
        m = strlen( s + 1 );
        memset(ne,0,sizeof ne);
        get_next();
        KMP();
    }

    return 0;
}

剪花布条

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

char p[1005],s[1005];
int ne[1005];
int n,m;

void get_next()
{
    for(int i = 2, j = 0 ; i <= n ; i ++){
        while( j && p[i] != p[j + 1] ) j = ne[j];
        if(p[i] == p[j + 1]) j ++;

        ne[i] = j;
    }

}

void KMP()
{
    int cnt = 0;
    for(int i = 1, j = 0 ; i <= m ; i++){
        while( j && s[i] != p[j + 1] ) j = ne[j];
        if( s[i] == p[j + 1 ] ) j ++;

        if( j == n ){
            cnt ++;
            j = 0;
            //cout <<i <<endl;

        }
    }
    cout << cnt <<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while(cin >> s + 1){
        if( s[1] == '#' ) break;
        cin >> p + 1;
        n = strlen( p + 1 );
        m = strlen( s + 1 );
        get_next();
        KMP();

    }

}

Number Sequence

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000004;
int p[maxn],s[maxn];
int n,m;
int ne[maxn];
void get_next()
{
    for(int i = 2 ,j = 0 ; i <= n ; i++){
        while( j && p[i] != p[j + 1] ) j = ne[j];
        if( p[i] == p[j + 1] )  j++;

        ne[i] = j;
    }
}

void KMP()
{
    bool flag = 0;
    for(int i = 1, j = 0 ; i <= m ; i++){
        while( j && s[i] != p[j + 1] ) j = ne[j];
        if( s[i] == p[j + 1] ) j ++;

        if( j == n ){
            cout << i - n  + 1<<endl;
            flag = 1;
            break;
        }
    }

    if(!flag)   cout << -1 <<endl;

}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while( t --){

        cin >> m >> n;
        for(int i = 1; i <= m ; i++)    cin >> s[i];
        for(int i = 1; i <= n ; i++)    cin >> p[i];
        memset(ne ,0 , sizeof ne);

        get_next();
        KMP();

    }
    return 0;
}

[Substrings](Substrings - HDU 1238 - Virtual Judge (vjudge.net))

KMP做法

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
#include <bits/stdc++.h>
using namespace std;

string s[110];
int ne[110];
int en[110];
int n;
void get_next(string p)
{
    memset(ne,0,sizeof ne);
    int len = p.length();

    int i = 0 , j = -1 ;
    ne[0] = -1;
    while(i < len){
        if(~j && p[i] != p[j]) j = ne[j];
        else ne[++i] = ++j;
    }
}

void get_enxt(string p )
{
    memset(en,0,sizeof en);
    int len = p.length();

    int i = 0 , j = -1 ;
    en[0] = -1;
    while(i < len){
        if(~j && p[i] != p[j]) j = en[j];
        else en[++i] = ++j;
    }
}

bool kmp(string p)
{
    get_next(p);
    string rs = p;
    reverse(rs.begin(),rs.end());
    get_enxt(rs);

    bool flag = true;
    int le = p.length();
    for(int k = 1; k < n ; k++){
        ///
        int i =0 ,j=0,len = s[i].length();
        bool fla = false;

        while(i < len ){
            if( ~j && s[k][i] != p[j] ) j = ne[j];
            else i++,j++;
            if(j >= le){
                fla = true;
                break;
            }
        }
        if(!fla){
            i = 0 , j = 0;
            while(i < len ){
                if( ~j && s[k][i] != rs[j] ) j = en[j];
                else i++,j++;
                if(j >= le){
                    fla = true;
                    break;
                }
            }
        }
        if( !fla ) return false;
    }

    return true;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int  t;
    cin >> t;
    while(t--){
        cin >> n;

        for(int i =0;  i < n;  i++){
            cin >> s[i];
        }
        int len = s[0].length(),ans = 0;
        ///get the substirng of front string
        for(int i = 0 ; i < len ;i++){
            for(int j = 1; j + i - 1 < len ; j++){
                string te =  s[0].substr(i,j);
                if( kmp(te) ){
                    ans = max(ans, (int)te.length());
                }
            }
        }


        cout << ans <<endl;
    }

    return 0;
}

STL做法

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
#include <bits/stdc++.h>
using namespace std;

string s[110];
int t,n;

inline bool check(string p)
{
    string et = p;
    reverse(et.begin(),et.end());

    for(int i = 1; i < n ;i++){
        if( s[i].find( et ) != string::npos || s[i].find( p ) != string::npos){
            continue;
        }
        else return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >>t;
    while(t--){
        cin >> n;
        for(int i = 0 ; i < n ; i++){cin >> s[i];}

        int len = s[0].length(),ans=0;
        for(int i = 0; i < len ; i++){
            for(int j = 1 ; i + j - 1 < len ; j++){
                string te = s[0].substr(i,j);
                if( check(te) ){
                    ans = max(ans, (int)te.length());
                }
            }
        }
        cout << ans <<endl;
    }

    return 0;
}

2.2____kmp&前缀的周期性

Period

KMP最小循环节、循环周期：

定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

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
#include <bits/stdc++.h>
using namespace std;

int n;
const int maxn = 1e6 + 5;
char p[maxn];
int ne[maxn];

void get_next()
{
    for(int i = 2, j = 0 ; i <= n ; i++){

        while( j && p[i] != p[j + 1] ) j = ne[j];
        if( p[i] == p[j + 1]) j++;

        ne[i] = j;
    }
//
//    for(int i = 1; i <= n ; i++){
//        cout << ne[i] <<endl;
//    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int cnt = 1;

    while(cin >> n)
    {
        if( n == 0) return 0;

        for(int i = 1; i <= n ; i++)    cin >> p[i];
        memset(ne,0,sizeof ne);
        get_next();

		printf("Test case #%d\n",cnt++);
        for(int i = 1; i <= n ; i++){
            int tmp = i + 1 - ne[i + 1];
            if( (i + 1 ) % tmp == 0 && (i + 1) / tmp  > 1)
                printf("%d %d\n",i+1,(i+1)/tmp);

        }
        printf("\n");
    }

    return 0;
}

Seek the Name, Seek the Fame

Blue Jeans

2.4____字符串Hash

Number Sequence

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
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull N =  1000010 ,M = 131;
ull s[N],sp[N];
ull h[N],p[N];
ull hp;

inline ull get_hash(ull l , ull r)
{
    return h[r] - h[l - 1] * p[ r - l ];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,t;
    cin >> t;
    
    while(t--){
        cin >> n >> m;
        for(int i = 0;  i < n ; i++){cin >> s[i];}
        for(int i = 0;  i < m ; i++){cin >> sp[i];}

        h[0] = s[0];
        p[0] = 131;
        for(int i = 1;  i < n ; i++){
            h[i] = h[i - 1] * M + s[i];
            p[i] = p[i - 1] * M;
        }

        hp = sp[0];
        for(int i = 1; i < m ; i++) hp = hp*M + sp[i];

        int flag = -1;
        for(int i = 0 ; i <= n - m ; i ++){
            if(get_hash(i,i+m-1) == hp ){
                flag = i;
                break;
            }
        }

        if( flag == -1  )   cout << -1 <<endl;
        else cout << flag + 1 <<endl;

    }
    return 0;
}

Censor

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

/**   stack做法  **/

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull N = 5000010, M = 131;

string s,t;
char ans[N];

int main()
{


    while(cin >> t){
        cin >> s;
        ull len1 = s.length() , len2 = t.length();
        ull hp = t[0],bas = 1;
        for(int i = 1;  i <= len2 ; i++) bas = bas*M;
        for(int i = 1 ; i < len2 ; i++) hp = hp * M + t[i];

        stack<ull> sta;

        ull cnt = 0 , cur = 0;
        for(int i = 0 ; i < len1;  i++){
            cur = cur * M + s[i];
            ans[cnt] = s[i];
            if( cnt >= len2 - 1 ){

                if(cnt >= len2){
                    cur = cur - ans[ cnt - len2 ] * bas;
                }

                sta.push(cur);
                if( cur == hp )
                {
                    for(int j = 0 ; j < len2 ; j++){
                        sta.pop();
                    }
                    cnt -= len2;
                    if( sta.empty() )   cur = 0;
                    else    cur = sta.top();
                }
            }
            else    sta.push(cur);
            cnt++;
        }

        for(int i =0 ; i < cnt;i++){
            cout << ans[i];
        }
        cout << endl;
    }

    return 0;
}
/*
abc
aaabcbc
*/



剪花布条<stl删除做法>

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 131;
typedef unsigned long long ull;
typedef long long ll;
ull hp;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s,e;
    while(cin >>s){

        if(s == "#") break;
        cin >>e;

        hp = e[0];
        ll len1 = s.length() , len2 = e.length(),teans = 0;;
        for(int i = 0 ; i < len2 ; i++) hp = hp * M + e[i];

        ll loc = 0;
        while( true ){
            if( len1 < len2 ) break;
            if( loc + len2 > len1 ) break;
            if( s.empty() ) break;
            ull tep = s[loc];
            for(int i = loc ; i < loc +  len2 ; i++){
                tep = tep*M + s[i];
            }

           // cout << tep << ' ' << hp << endl;
            if( tep == hp ){
                    teans ++;
                s.erase(loc, len2);
                if( loc - len2 + 1 >= 0 ) loc = loc - len2 + 1;
                else loc = 0;
                len1 -= len2;
            }
            else loc++;
        }

        cout << teans <<endl;

    }

    return 0;
}

Power Strings

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef unsigned long long ull;
const int N = 1000010,M = 131;

ull h[N],p[N];
string s;

inline ull get_hash(ull l ,ull r)
{

    return h[r] - h[l - 1]*p[r - l];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while(cin >> s)
    {
        if( s == ".") break;
        int len = s.length();

        h[0] = s[0];
        p[0] = 131;
        for(int i = 1 ; i < len ; i++){
            h[i] = h[i - 1] * M + s[i];
            p[i] = p[i - 1] * M;
        }
        int maxn = 0;
        for(int i = 1; i < len ; i ++){

            ull hp = h[i - 1],te;
            int flag = 1;

            if( len %i != 0 ) continue;

            for(int j = i; j < len ; j += i){

                if(i == 1){
                    te = h[j] - h[j - 1]*M;
                }
                else{
                    te = get_hash(j,j + i-1);
                }
               // cout << i <<  ' '<<te << ' ' << hp <<endl;
                if( hp != te) {
                    flag = 0;
                    break;
                }

            }

            if(flag ){
                maxn = len  / i ;
                break;
            }
        }
        if(maxn == 0)   cout <<1 <<endl;
        else    cout << maxn <<endl;

    }


    return 0;
}

Seek the Name, Seek the Fame

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef unsigned long long ull;
const ull N =  400010,M =131;
string s;
ull h[N],p[N];

inline ull get_hash(ull l, ull r)
{
    return h[r] - h[l - 1]*p[r - l];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin >>s)
    {
        h[0] = s[0];
        p[0] = M;
        ull len = s.length();
        for(int i = 1; i < len ; i++){
            h[i] = h[i -1 ] *M + s[i];
            p[i] = p[i - 1] * M;
        }
        int ans = 1;
        for(int i = 1; i < len ; i++){
            if( i == 1 ){
                if( s[0] == s[len -1] ){
                    cout << 1 <<' ';
                }
            }
            else{
                //cout << len - i - 1<<endl;
                ull hp1 = h[i - 1], hp2 = get_hash(len - i,len - 1);
                if(hp1 == hp2){
                    cout << i << ' ';
                }

            }
        }
        cout << len << endl;
    }


    return 0;
}

2.4____ 扩展KMP

Prefixes and Suffixes

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
```

>  [Clairewd’s message]([Clairewd's message - HDU 4300 - Virtual Judge (vjudge.net)](https://vjudge.net/problem/HDU-4300))

```c++
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 +10;
int q,ne[N],ex[N];      /// ne为t与自己的后缀数组，ex为s与t的后缀数组
int slen,tlen;          ///匹配串与模板串长度
char s[N],t[N];         ///匹配串，模板串

void get_next()
{
    ne[0] = tlen;   ///ne[0]一定是T的长度
    int now = 0;
    while(t[now] == t[1 + now] && now + 1 < tlen) now++;///从1开始暴力枚举第一位
    ne[1] = now;
    int p0 = 1;
    for(int i = 2;  i < tlen ; i++){
        if( i + ne[i - p0] < ne[p0] + p0 ) ne[i] = ne[i - p0]; /// k + l < p
        else{
            int now = ne[p0] + p0 - i;
            now = max(now, 0);  ///防止i > p 的情况
            while( t[now] == t[i + now] && i + now < tlen ) now++;
            ne[i] = now;
            p0 = i ;
        }
    }
}

void exkmp()
{
    get_next();
    int now = 0;
    while( s[now] == t[now] && now < min(slen ,tlen)  ) now++;
    ex[0] = now;
    int p0= 0;
    for(int i = 1; i < slen ; i++){
        if( i + ne[i - p0] < ex[p0] + p0 ) ex[i] = ne[i - p0];
        else{
            int now = ex[p0] + p0 - i;
            now = max(now, 0);
            while(t[now] == s[i + now] && now < tlen && now + i < slen) now++;
            ex[i] = now;
            p0= i;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    while(n--){
        map<char,char> mp;
        memset(s,0,sizeof s);
        memset(ne,0,sizeof ne);
        memset(ex,0,sizeof ex);
        memset(t,0,sizeof t);
        for(int i = 0 ; i < 26 ; i++){
            char te;
            cin >>te;
            mp[te] = (char)(i + 'a');
        }
        cin >>s;
        slen = tlen = strlen(s);

        for(int i = 0; i <tlen ; i++){
            t[i] = mp[ s[i] ];
        }

        exkmp();

        int pos = -1;	///从一半开始匹配，才符合题意
        for(int i =  (tlen+1) /2; i < tlen ; i++){
            if( ex[i] + i == tlen && ex[i] != 0 ){
                pos = i;
                break;
            }
        }
        if(pos != -1){	
            for(int i = 0 ; i < pos; i ++){
                cout << s[i];
            }
            for(int i = 0 ; i < pos ; i++){
                cout << t[i];
            }
            cout << endl;
        }	///如果一般之后的后缀数组都为0就直接先输出s在输出t
        else cout << s << t<< endl;
    }

    return 0;
}

2.5____回文Manacher

3188. manacher算法 - AcWing题库

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
#include <bits/stdc++.h>
using namespace std;

string s;
int d1[10000010];	
int d2[10000010];
int n;
void get_d1()	/// 计算长度为奇数的回文串
{
    for(int i = 0, l = 0 , r = -1; i < n ; i++){
        int k = (i > r)?1:min( d1[l+r-i],r-i );
        while( 0 <= i-k && i + k < n && s[i-k] == s[i +k] ) k++;

        d1[i] = k--;
        if( i + k > r ){
            l = i-k;
            r = i+k;
        }
    }
}

void get_d2()	///	计算长度为偶数的回文串
{
    for(int i = 0, l = 0 , r = -1; i < n ; i++){
        int k = (i > r)?0:min( d2[l+r-i + 1],r-i+1 );
        while( 0 <= i-k-1 && i + k < n && s[i-k-1] == s[i +k] ) k++;

        d2[i] = k--;
        if( i + k > r ){
            l = i-k-1;
            r = i+k;
        }
    }
}

void manacher()
{
    get_d1();
    get_d2();
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    n = s.length();
    manacher();

    int ans= 0;
    for(int i =0 ; i < n ; i++){
        ans = max(ans,d1[i]*2-1);
        ans = max(ans,d2[i]*2);
    }

    cout << ans <<endl;

    return 0;
}

字典树

Problem - M - Codeforces (Unofficial mirror site, accelerated for Chinese users)

I love counting - HDU 6964 - Virtual Judge (vjudge.net)

3____计算几何

上次cf刷到的位置Problemset - Codeforces)

Triangle

1

Naive and Silly Muggles

1

3.1____叉积判断点线关系

TOYS

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,x1,x2,y1,y2;
/// n为分区数，m为玩具数，左上坐标，右下坐标

struct Point
{
    int x,y;
};

//typedef Point Vector;
//Vector oprator + ( Vector A,Vector B ) { return Vector ( A.x + B.x , A.y + B.y ); }
//Vector oprator - ( Vector A,Vector B ) { return Vector (  )}

struct Line
{
    Point a,b;
}line[5001];

int cnt[5001];

inline int Cross(Point p1,Point p2) ///求叉积
{
    return p1.x * p2.y - p1.y * p2.x;
}

inline bool dir(int k ,Point p)
{
    Point a,b;
    a.x = line[k].a.x - p.x;
    a.y = line[k].a.y - p.y;
    b.x = line[k].b.x - p.x;
    b.y = line[k].b.y - p.y;
    return Cross( a,b ) > 0;
}

inline int Find(Point p)
{
    int l = 1, r = n ;
    while( l <= r )
    {
        int mid = ( l + r) >> 1;
        if( dir(mid,p) ) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while( cin >> n )
    {
        if( n == 0) break;
        memset(cnt,0,sizeof cnt);
        cin >> m >> x1 >> y1 >> x2 >> y2;

        for(int i = 1; i <= n ; i++)
        {
            line[i].a.y = y1;
            line[i].b.y = y2;
            cin >> line[i].a.x >> line[i].b.x;
        }

        ///对应区间
        for(int i = 1; i <= m ; i++)
        {
            Point p;
            cin >> p.x >> p.y;
            ++cnt[ Find(p) ];
        }
        ///打印
        for(int i = 0 ; i <= n ;i ++) cout << i <<": " << cnt[i] <<endl;
        cout<< endl;

    }

    return 0;
}

Segments

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
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 105;
const double eps = 1e-8;

int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }

struct Point
{
    double x,y;
    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }
    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
     Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
}s[N*2];

struct Line
{
    Point s,e;
    Line(){}
    Line( Point _s, Point _e ){ s =_s ; e=_e; }

    ///直线与线段相交判断
    ///-*this line -v seg
    ///2规范相交，1非规范相交,0不相交
    bool linecrossseg(Line v){
        return sgn( (v.s - e) ^ (s - e) ) * sgn(( v.e-e ) ^ (s -e) ) <= 0;
    }

}line[N];

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        int n,x1,x2,y1,y2;
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> line[i].s.x >> line[i].s.y;
            cin >> line[i].e.x >> line[i].e.y;
            s[i*2 -1] = line[i].s , s[i*2] = line[i].e;
        }

        bool flag = 0;
        ///对每个点进行枚举
        for(int i = 1; i <= 2 * n ; i++)
        {
            if(flag) break;
            for(int j = i + 1 ; j <= 2 * n ; j++)
            {
                //cout << s[i].x << ' ' << s[i].y << " | " <<s[j].x << ' '<< s[j].y <<endl;
                Line te(s[i],s[j]);
                if( s[i].x == s[j].x && s[i].y == s[j].y ) continue;
                ///验证这个枚举的线是不是与每个线段都相交
                int k;
                for(k = 1;k <= n; k++)
                //cout << te.linecrossseg( line[k] ) << endl;
                if( !te.linecrossseg( line[k] ) ) break;
                if(k == n +1) flag = 1;
                //cout << k << endl;
            }
        }
        if(flag) cout << "Yes!" <<endl;
        else cout << "No!" << endl;
       // cout<< endl;

    }

    return 0;
}

3.2____多边形重心

Lifting the Stone

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
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos( -1.0);

///Compares a double to zero
int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }
/////////////////////////////////////////////////
struct Point
{
    double x,y;
    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }
    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    ///数量积
    Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
    Point operator * (const double &k) const{
        return Point(x * k , y * k );
    }
    Point operator / (const double &k) const{
        return Point(x / k , y / k);
    }
    ///叉积
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    ///点积
    double operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    ///线段的长度
    double len(){
        return hypot(x,y);  ///<cmath>
    }
    ///长度的平方
    double len2(){
        return x * x + y * y;
    }
    ///返回两点的距离
    double distance(Point p){
        return hypot( x - p.x , y - p.y );
    }

};

const int maxp = 10000010;

struct polygon
{
    int n;
    Point p[maxp];
    //Line l[maxp];

    double getarea()
    {
        double sum = 0;
        for(int i = 0; i<n ; i++){
            sum += p[i].distance(p[(i+1)%n]);
        }
        return sum;
    }

    Point getbarycentre()
    {
        Point ret(0,0);
        double area = 0;
        for(int i = 1; i < n - 1;  i++){
            double tmp = (p[i] - p[0] )^ ( p[i +1] -p[0] );
           // printf("%.2f\n",tmp);
            if(sgn(tmp) == 0)continue;
            area += tmp;
            ret.x += ( p[0].x + p[i].x + p[i +1].x )/ 3 * tmp;
            ret.y += ( p[0].y + p[i].y + p[i+1].y ) /3 * tmp;
        }
        if( sgn(area) ) ret = ret /area;
        return ret;
    }

}pol;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        pol.n = n ;
        //scanf("%d%d",&pol.p[0].x,&pol.p[0].y);
        for(int i = 0; i < n ; i++)
        {
            scanf("%lf %lf",&pol.p[i].x,&pol.p[i].y);
//            pol.l[i-1].s.x = pol.p[i-1].x;
//            pol.l[i-1].s.y = pol.p[i-1].y;
//            pol.l[i-1].e.x = pol.p[i].x;
//            pol.l[i-1].e.y = pol.p[i].y;
        }

        Point ans = pol.getbarycentre();
        if( ans.x > -0.001 && ans.x < 0.0 ) ans.x = 0;
        if( ans.y > -0.001 && ans.y < 0.0 ) ans.y = 0;
        printf("%.2f %.2f\n",ans.x ,ans.y);

    }

    return 0;
}

3.3____极角排序

思路 ：事先将两个点连成线，然后用叉积来判断第三个点在这个线的左边还是右边，

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <math.h>
using namespace std;

const double eps = 1e-8;
const double pi = acos( -1.0);

///Compares a double to zero
int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }

struct Point
{
    double x,y;
    int num;

    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }
    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    ///数量积
    Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
    Point operator * (const double &k) const{
        return Point(x * k , y * k );
    }
    Point operator / (const double &k) const{
        return Point(x / k , y / k);
    }
    ///叉积
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    ///点积
    double operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    ///返回两点的距离
    double distance(Point p){
        return sqrt( sqr( x- p.x ) + sqr(y - p.y) );
    }
}P[510];

Point ans[510];

Point init;

bool cmp(Point a,Point b)
{
    if( fabs( (a - init)^( b - init ) ) < eps ) ///  如果极角相同，比较距离
    {
        return init.distance(a) < init.distance(b);
    }
    else return ( (a - init) ^ (b - init) )> 0;
}

int main()
{
    ios::sync_with_stdio( false);
    cin.tie(0);

    int n,t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        int miny = 100000000;
        for(int i = 1 ; i <= n ; i++){
            cin >> P[i].num >> P[i].x >> P[i].y;
            if( P[i].y < miny ) miny = P[i].y;
        }

        init.x = 0,init.y = miny;

        for(int i = 1 ; i <= n ; i++)
        {
            sort(P+i,P+1+n,cmp);
            ans[i] = P[i];
            init = P[i];
        }

        cout << n << ' ';
        for(int i = 1; i <= n ; i++ )
            cout << ans[i].num << ' ';

        cout <<endl;
    }

    return 0;
}

3.4____计算几何，思维题

An Easy Problem?!

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
229
230
231
232
233
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double eps = 1e-8;
const double pi = acos( -1.0);

///Compares a double to zero
int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }
/////////////////////////////////////////////////
struct Point
{
    double x,y;
    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }

    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    ///数量积
    Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
    Point operator * (const double &k) const{
        return Point(x * k , y * k );
    }
    Point operator / (const double &k) const{
        return Point(x / k , y / k);
    }
    ///叉积
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    ///点积
    double operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    ///线段的长度
    double len(){
        return hypot(x,y);  ///<cmath>
    }
    ///长度的平方
    double len2(){
        return x * x + y * y;
    }
    ///返回两点的距离
    double distance(Point p){
        return hypot( x - p.x , y - p.y );
    }
};

struct Line
{

    vector<char> croset;

    char name;

    Point s,e;
    Line(){}
    Line( Point _s, Point _e ){ s =_s ; e=_e; }

    void input(Point _p1,Point _p2)
    {
        s = _p1,e = _p2;
    }

    ///直线与线段相交判断
    ///-*this line -v seg
    ///2规范相交，1非规范相交,0不相交
    bool linecrossseg(Line v){
        return sgn( (v.s - e) ^ (s - e) ) * sgn(( v.e-e ) ^ (s -e) ) <= 0;
    }
		///点与直线关系
    ///1在左侧
    ///2在右侧
    ///3在直线
    int relation(Point p){
        int c = sgn( (p-s) ^ (e -s) );
        if(c < 0) return 1;
        else if(c > 0) return 2;
        else return 3;
    }
    ///点在线段上的判断
    bool point_on_seg(Point p){
        return sgn((p-s)^(e-s) ) == 0 && sgn( (p-s)*(p-e) ) <= 0 ;
    }
    ///两向量平行(对应直线平行或重合)
    bool parallel(Line v){
        return sgn( (e-s)^( v.e - v.s ) ) == 0;
    }
    ///两直线关系 0-平行，1-重合，2-相交
    int linecrossline(Line v){
        if( (*this).parallel(v) )
            return v.relation(s) == 3;
        return 2;
    }
    ///得到交点，需先判断直线是否相交
    Point crosspoint(Line v){
        double a1 = ( v.e - v.s ) ^ ( s - v.s );
        double a2 = ( v.e - v.s ) ^ ( e - v.s );
        return Point( (s.x * a2 - e.x * a1)/(a2 - a1) , (s.y *a2 - e.y *a1)/(a2 - a1));
    }

    ///两线段相交判断
    ///2 规范相交
    ///1 非规范相交
    ///0 不想交
    int segcrossseg(Line v) {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }

};


struct polygon
{
    int num;      ///点的数量
    Point p[4];
    Line l[4];


    struct cmp{
        Point p;
        cmp(const Point &p0){ p = p0;}
        bool operator()( const Point &aa ,const Point &bb){
            Point a = aa,b = bb;
            int d = sgn( (a-p)^(b-p) );
            if(d == 0)  return sgn( a.distance(p) - b.distance(p)) < 0;
            return d > 0;
        }
    };

    /// 3在顶点上
    /// 2在边上
    /// 1在内部
    /// 0在外面
    int Point_in_polygon(Point tep)
    {
        for(int i = 0 ; i < num ; i++){
            if( p[i] == tep ) return 3;
        }
        for(int i = 0 ; i < num ; i++){
            if( l[i].point_on_seg(tep) ) return 2;
        }
        int tecnt = 0;
        for(int i = 0 ; i < num ; i++)
        {
            int j = (i + 1) % num;
            int c = sgn( (tep - p[j]) ^ (p[i] - p[j]) );
            int u = sgn( p[i].y - tep.y );
            int v = sgn( p[j].y - tep.y );
            if( c > 0 && u < 0 && v >=0 ) tecnt ++;
            if( c < 0 && u >= 0 && v < 0 ) tecnt --;
        }
        return tecnt != 0;
    }

}pol;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t,n;
    cin >> t;

    while(t--)
    {
        Point p1,p2,j1,j3;
        cin >> p1.x >> p1.y >> p2.x >> p2.y >> j1.x >> j1.y >> j3.x >> j3.y;
        if( j1.x > j3.x ) swap(j1,j3);

        Line lp(p1,p2);
        Point j2,j4;
        j2.x = j3.x,j2.y = j1.y,j4.x = j1.x ,j4.y = j3.y;
        polygon pol;
        pol.p[0] = j1;
        pol.p[1] = j2;
        pol.p[2] = j3;
        pol.p[3] = j4;
        pol.l[0].input(j1,j2);pol.l[1].input(j2,j3),pol.l[2].input(j3,j4),pol.l[3].input(j4,j1);
        pol.num = 4;
        bool flag = 0;
        for(int i = 0; i < 4 ; i++)
            if( lp.segcrossseg(pol.l[i]) > 0 ){
                flag = 1;
                break;
            }


        if( flag ) cout <<'T' <<endl;
        else{
                //cout << pol.Point_in_polygon(p1) << ' ' <<  pol.Point_in_polygon(p2) << endl;
            if( pol.Point_in_polygon(p1) && pol.Point_in_polygon(p2)  ) cout << 'T' << endl;
            else cout << 'F' <<endl;
        }


    }



    return 0;
}

Kadj Squares

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

struct node
{
    int l,r,s;
}p[500];

int loc[500];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while(cin >> n)
    {
        if( n == 0) break;
        for(int i = 0 ;  i < n ; i++)   cin >> p[i].s;

        for(int i = 0 ; i < n  ; i ++)
        {
            int ll = 0;
            for(int j = 0; j < i ; j ++)
                ll = max(ll , p[j].r - abs( p[j].s - p[i].s ));
            p[i].l =ll;
            p[i].r = ll + 2 * p[i].s;
        }

        for(int i =  0 ; i < n ; i++)
        {
            int ml = p[i].l,mr = p[i].r;///重要
            for(int j = 0; j < i ; j++)
                    ml = max(ml,p[j].r);

            for(int j = i + 1; j < n ; j++)
                    mr = min(mr,p[j].l);

            if( ml >= mr ) continue;
            else cout << i + 1 << ' ';
        }
        cout << endl;
    }


    return 0;
}

[Nezzar and Nice Beatmap](Problem - 1477C - Codeforces)

题意： 在平面上按序给定 $n$ 个点，问能不能将这些点重新排序，使任意三个相邻的点形成的角都是锐角，若能就输出新的序列，不能输出$-1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

struct point
{
    double x,y;
    int num;
} p[5005];

struct vec
{
    point s,e;
};

int n;

bool f(point a,point b,point c)
{
    point v1 = { a.x - b.x,a.y - b.y };
    point v2 = { c.x - b.x,c.y - b.y };
    double dot = v1.x * v2.x + v1.y * v2.y;
    if( dot > 0)
        return true;
    else
        return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> p[i].x >>p[i].y;
        p[i].num = i;
    }

    for(int i = 3 ; i <= n  ; i ++)
    {
        for(int j = i  ; j >= 3 ; j--)
        {
            if( !f(p[j],p[j-1],p[j-2]) )
                swap( p[j],p[j-1] );
        }
    }
        for(int i = 1; i <= n ; i++)
        {
            cout << p[i].num << ' ';
        }
        cout <<endl;
    return 0;
}

Problem - 1486B - Codeforces

一维中位数满足所有数到中位数的距离最小值的全局最优

利用这一性质，将所有点的x ,y分别排序，中位数的垂线交点数量即为答案

例如（1,2,3）中位数就是2，（1,2,3,4）中位数就是2和3。（这里要注意n为奇数的话中位数就只有一个，n为偶数时中位数就会有两个，所以特殊点就是这两个点中的所有点而不就这俩端点，例如（1,2,4,5）的中位数是2,4，特殊点是2,3,4。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[2102102],y[2102102];
int main(){
	ll t;
	cin>>t;
	while(t--){
		ll b;
		cin>>b;
		for(ll i=1;i<=b;i++){
			cin>>x[i]>>y[i]; 
		}
		sort(x+1,x+b+1);
		sort(y+1,y+1+b);
		if(b%2)cout<<1<<endl;
		else {
			cout<<(x[b/2+1]-x[b/2]+1)*(y[b/2+1]-y[b/2]+1)<<endl;
		}
	}
}

3.5____线段与多边形判断相交

Intersection

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
229
230
231
232
233
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double eps = 1e-8;
const double pi = acos( -1.0);

///Compares a double to zero
int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }
/////////////////////////////////////////////////
struct Point
{
    double x,y;
    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }

    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    ///数量积
    Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
    Point operator * (const double &k) const{
        return Point(x * k , y * k );
    }
    Point operator / (const double &k) const{
        return Point(x / k , y / k);
    }
    ///叉积
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    ///点积
    double operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    ///线段的长度
    double len(){
        return hypot(x,y);  ///<cmath>
    }
    ///长度的平方
    double len2(){
        return x * x + y * y;
    }
    ///返回两点的距离
    double distance(Point p){
        return hypot( x - p.x , y - p.y );
    }
};

struct Line
{

    vector<char> croset;

    char name;

    Point s,e;
    Line(){}
    Line( Point _s, Point _e ){ s =_s ; e=_e; }

    void input(Point _p1,Point _p2)
    {
        s = _p1,e = _p2;
    }

    ///直线与线段相交判断
    ///-*this line -v seg
    ///2规范相交，1非规范相交,0不相交
    bool linecrossseg(Line v){
        return sgn( (v.s - e) ^ (s - e) ) * sgn(( v.e-e ) ^ (s -e) ) <= 0;
    }
		///点与直线关系
    ///1在左侧
    ///2在右侧
    ///3在直线
    int relation(Point p){
        int c = sgn( (p-s) ^ (e -s) );
        if(c < 0) return 1;
        else if(c > 0) return 2;
        else return 3;
    }
    ///点在线段上的判断
    bool point_on_seg(Point p){
        return sgn((p-s)^(e-s) ) == 0 && sgn( (p-s)*(p-e) ) <= 0 ;
    }
    ///两向量平行(对应直线平行或重合)
    bool parallel(Line v){
        return sgn( (e-s)^( v.e - v.s ) ) == 0;
    }
    ///两直线关系 0-平行，1-重合，2-相交
    int linecrossline(Line v){
        if( (*this).parallel(v) )
            return v.relation(s) == 3;
        return 2;
    }
    ///得到交点，需先判断直线是否相交
    Point crosspoint(Line v){
        double a1 = ( v.e - v.s ) ^ ( s - v.s );
        double a2 = ( v.e - v.s ) ^ ( e - v.s );
        return Point( (s.x * a2 - e.x * a1)/(a2 - a1) , (s.y *a2 - e.y *a1)/(a2 - a1));
    }

    ///两线段相交判断
    ///2 规范相交
    ///1 非规范相交
    ///0 不想交
    int segcrossseg(Line v) {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }

};


struct polygon
{
    int num;      ///点的数量
    Point p[4];
    Line l[4];


    struct cmp{
        Point p;
        cmp(const Point &p0){ p = p0;}
        bool operator()( const Point &aa ,const Point &bb){
            Point a = aa,b = bb;
            int d = sgn( (a-p)^(b-p) );
            if(d == 0)  return sgn( a.distance(p) - b.distance(p)) < 0;
            return d > 0;
        }
    };

    /// 3在顶点上
    /// 2在边上
    /// 1在内部
    /// 0在外面
    int Point_in_polygon(Point tep)
    {
        for(int i = 0 ; i < num ; i++){
            if( p[i] == tep ) return 3;
        }
        for(int i = 0 ; i < num ; i++){
            if( l[i].point_on_seg(tep) ) return 2;
        }
        int tecnt = 0;
        for(int i = 0 ; i < num ; i++)
        {
            int j = (i + 1) % num;
            int c = sgn( (tep - p[j]) ^ (p[i] - p[j]) );
            int u = sgn( p[i].y - tep.y );
            int v = sgn( p[j].y - tep.y );
            if( c > 0 && u < 0 && v >=0 ) tecnt ++;
            if( c < 0 && u >= 0 && v < 0 ) tecnt --;
        }
        return tecnt != 0;
    }

}pol;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t,n;
    cin >> t;

    while(t--)
    {
        Point p1,p2,j1,j3;
        cin >> p1.x >> p1.y >> p2.x >> p2.y >> j1.x >> j1.y >> j3.x >> j3.y;
        if( j1.x > j3.x ) swap(j1,j3);

        Line lp(p1,p2);
        Point j2,j4;
        j2.x = j3.x,j2.y = j1.y,j4.x = j1.x ,j4.y = j3.y;
        polygon pol;
        pol.p[0] = j1;
        pol.p[1] = j2;
        pol.p[2] = j3;
        pol.p[3] = j4;
        pol.l[0].input(j1,j2);pol.l[1].input(j2,j3),pol.l[2].input(j3,j4),pol.l[3].input(j4,j1);
        pol.num = 4;
        bool flag = 0;
        for(int i = 0; i < 4 ; i++)
            if( lp.segcrossseg(pol.l[i]) > 0 ){
                flag = 1;
                break;
            }


        if( flag ) cout <<'T' <<endl;
        else{
                //cout << pol.Point_in_polygon(p1) << ' ' <<  pol.Point_in_polygon(p2) << endl;
            if( pol.Point_in_polygon(p1) && pol.Point_in_polygon(p2)  ) cout << 'T' << endl;
            else cout << 'F' <<endl;
        }


    }



    return 0;
}

3.6____计算凸包，周长

Surround the Trees 

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
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const double pi = acos( -1.0);

///Compares a double to zero
int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}
///square of a double
inline double sqr(double x) { return x * x; }
/////////////////////////////////////////////////
struct Point
{
    double x,y;
    Point(){}               ///no arguments constructor
    Point(double _x,double _y) {
        x = _x , y = _y;    ///arguments constructor
    }
    /*void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%.2f %.2f\n",x,y);
    }*/
    bool operator == (Point b) const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b) const{
        return sgn(x - b.x) == 0? sgn(y - b.y) < 0 : x < b.x;
    }
    ///数量积
    Point operator - (const Point &b) const{
        return Point(x - b.x , y - b.y);
    }
    Point operator + (const Point &b) const{
        return Point(x + b.x , y + b.y);
    }
    Point operator * (const double &k) const{
        return Point(x * k , y * k );
    }
    Point operator / (const double &k) const{
        return Point(x / k , y / k);
    }
    ///叉积
    double operator ^ (const Point &b) const{
        return x * b.y - y * b.x;
    }
    ///点积
    double operator * (const Point &b) const{
        return x * b.x + y * b.y;
    }
    ///线段的长度
    double len(){
        return hypot(x,y);  ///<cmath>
    }
    ///长度的平方
    double len2(){
        return x * x + y * y;
    }
    ///返回两点的距离
    double distance(Point p){
        return hypot( x - p.x , y - p.y );
    }
    ///计算 pa 和 pb 的夹角
    double rad(Point a,Point b){
        Point p = *this;
        return fabs( atan2( fabs( (a-p)^(b-p) )  , (a-p)*(b-p) ) );
    }
    ///化为长度为r的向量
    Point trunc(double r){
        double l = len();
        if( !sgn(l) ) return *this;
    }
    ///逆时针旋转90度
    Point rotleft(){
        return Point(y,-x);
    }
    ///顺时针旋转90度
    Point rotright(){
        return Point(y,-x);
    }
    ///绕着p点逆时针
    Point rotata(Point p,double angle){
        Point v = (*this) - p;
        double c = cos(angle) , s = sin(angle);
        return Point(p.x + v.x * c - v.y * s , p.y + v.x *s + v.y * c);
    }
};

struct Line
{
    Point s,e;
    Line(){}
    Line( Point _s, Point _e ){ s =_s ; e=_e; }
    ///由斜倾角angle与任意直线一点确定直线 y = kx + b;
    void input( Point _s, Point _e ){ s =_s ; e=_e; }

    Line(Point p,double angle){
        s = p;
        if( sgn(angle - pi/2) == 0 )    e = (s + Point(0,1));
        else e = (s + Point(1,tan(angle)));
    }
    ///ax + by + c = 0;
    Line(double a,double b,double c){
        if( sgn(a) == 0 )
        {
            s = Point(0,-c/b);
            e = Point(1,-c/b);
        }
        else if(sgn(b) == 0)
        {
            s = Point(-c/a,0);
            e = Point(-c/a,1);
        }
        else
        {
            s = Point(0,-c/b);
            e = Point(1,(-c-a)/b);
        }
    }
    ///直线与线段相交判断
    ///-*this line -v seg
    ///2规范相交，1非规范相交,0不相交
    bool linecrossseg(Line v){
        return sgn( (v.s - e) ^ (s - e) ) * sgn(( v.e-e ) ^ (s -e) ) <= 0;
    }
		///点与直线关系
    ///1在左侧
    ///2在右侧
    ///3在直线
    int relation(Point p){
        int c = sgn( (p-s) ^ (e -s) );
        if(c < 0) return 1;
        else if(c > 0) return 2;
        else return 3;
    }
    ///点在线段上的判断
    bool point_on_seg(Point p){
        return sgn((p-s)^(e-s) ) == 0 && sgn( (p-s)*(p-e) ) <= 0 ;
    }
    ///两向量平行(对应直线平行或重合)
    bool parallel(Line v){
        return sgn( (e-s)^( v.e - v.s ) ) == 0;
    }
    ///两直线关系 0-平行，1-重合，2-相交
    int linecrossline(Line v){
        if( (*this).parallel(v) )
            return v.relation(s) == 3;
        return 2;
    }
    ///得到交点，需先判断直线是否相交
    Point crosspoint(Line v){
        double a1 = ( v.e - v.s ) ^ ( s - v.s );
        double a2 = ( v.e - v.s ) ^ ( e - v.s );
        return Point( (s.x * a2 - e.x * a1)/(a2 - a1) , (s.y *a2 - e.y *a1)/(a2 - a1));
    }

    ///两线段相交判断
    ///2 规范相交
    ///1 非规范相交
    ///0 不想交
    int segcrossseg(Line v) {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }

};

struct triangle
{
    Point A,B,C;
    Line a,b,c;

    triangle(){}
    triangle(Point _A,Point _B,Point _C){ A = _A ; B = _B ; C = _C;}

    ///求重心
    Point incenter(){
        return Point( ( A.x + B.x + C.x ) / 3, ( A.y + B.y + C.y ) / 3);
    }

};

const int maxp = 100;
const int maxl = 200;

struct polygon
{
    int n;      ///点的数量
    Point p[maxp];
    Line l[maxl];


    struct cmp{
        Point p;
        cmp(const Point &p0){ p = p0;}
        bool operator()( const Point &aa ,const Point &bb){
            Point a = aa,b = bb;
            int d = sgn( (a-p)^(b-p) );
            if(d == 0)  return sgn( a.distance(p) - b.distance(p)) < 0;
            return d > 0;
        }
    };
    ///极角排序
    ///mi为最左下角的点
    void norm(){
        Point mi = p[0];
        for(int i = 1; i < n; i ++) mi = min(mi,p[i]);
        sort(p, p + n, cmp(mi) );
    }
    /// 判断任意点与多边形的关系
    /// 3在顶点上
    /// 2在边上
    /// 1在内部
    /// 0在外面
    int Point_in_polygon(Point tep)
    {
        for(int i = 0 ; i < n ; i++){
            if( p[i] == tep ) return 3;
        }
        for(int i = 0 ; i < n; i++){
            if( l[i].point_on_seg(tep) ) return 2;
        }
        int tecnt = 0;
        for(int i = 0 ; i < n ; i++)
        {
            int j = (i + 1) % n;
            int c = sgn( (tep - p[j]) ^ (p[i] - p[j]) );
            int u = sgn( p[i].y - tep.y );
            int v = sgn( p[j].y - tep.y );
            if( c > 0 && u < 0 && v >=0 ) tecnt ++;
            if( c < 0 && u >= 0 && v < 0 ) tecnt --;
        }
        return tecnt != 0;
    }

    /// 得到凸包
    /// 得到的凸包里的点编号是 0 ~ n-1 的
    void getconvex(polygon &convex)
    {
        sort(p , p + n);
        convex.n = n;
        for(int i = 0 ; i < min(n,2) ; i++){
            convex.p[i] = p[i];
        }
        ///特判
        if( convex.n == 2 && (convex.p[0] == convex.p[1]) ) convex.n--;
        if( n <= 2) return;
        int &top = convex.n;
        top = 1;
        for(int i = 2; i < n ; i++){
            while(top && sgn( (convex.p[top] - p[i]) ^ (convex.p[top-1] - p[i])) <= 0 ) top --;
            convex.p[++top] = p[i];
        }
        int temp = top;
        convex.p[++top] = p[n-2];
        for(int i = n - 3; i >=0 ; i--)
        {
            while( top!=temp && sgn( (convex.p[top] - p[i]) ^ (convex.p[top-1] - p[i]) ) <=0 ) top--;
            convex.p[++top] = p[i];
        }
        if( convex.n == 2&& ( convex.p[0] == convex.p[1]) ) convex.n --;    ///特判
        convex.norm();///得到的是顺时针的点,排序后逆时针
    }

    ///判断是不是凸多边形
    bool isconvex(){
        bool s[2];
        memset(s,false,sizeof(s));
        for(int i = 0 ; i < n ; i++){
            int j = (i + 1) % n;
            int k = (j + 1) % n;
            s[ sgn((p[j] - p[i]) ^ (p[k]-p[i]) ) + 1] =true;
        }
    }

    ///得到周长
    double getcircumference(){
        double sum = 0;
        for(int i = 0 ; i < n ; i++){
            sum += p[i].distance( p[(i + 1)%n] );
        }
        return sum;
    }

    ///得到面积
    double getarea()
    {
        double sum = 0;
        for(int i = 0;  i < n ; i++){
            sum += ( p[i]^p[ (i+1)%n ] );
        }
        return fabs(sum)/2;
    }
};


int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t,n;
    while( true )
    {
        scanf("%d",&n);
        if( n== 0) break;
        polygon pol;
        pol.n = n;
        for(int i = 0; i < n ; i++) scanf("%lf %lf",&pol.p[i].x,&pol.p[i].y);
        for(int i = 0 ; i <n ; i++) pol.l[i].input( pol.p[i] , pol.p[ (i + 1)%n ] );

        polygon poly;
        pol.getconvex(poly);

        //printf("%d\n",poly.n) ;
        //printf("%.2f\n",pol.getcircumference());
        ///如果只有两个点要特判，看计算凸包的公式就明白了
        if( poly.n == 2 ) printf("%.2f\n",poly.getcircumference()/2 );
        else printf("%.2f\n",poly.getcircumference() );
    }

    return 0;
}

3.7____平面几何

Keiichi Tsuchiya the Drift King

2018焦作——ICPC

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
#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1);
const double eps = 1e-8;

int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    scanf("%d",&t);
    while(t--)
    {
        double a,b,d,r;
        scanf("%lf%lf%lf%lf",&a,&b,&r,&d);
        double delta = d * pi / 180.0;

        double stand = atan( b/ (a+r) );
        if( sgn( delta - stand ) >= 0 )
        {
            printf("%.12f\n",sqrt( b*b + (a + r)*(a + r) ) - r);
        }
        else
        {
            double ans = sin(delta) * (b - (a+r)*tan(delta)) + (a+r)/cos(delta) - r;
            printf("%.12f\n",ans);
        }

    }

    return 0;
}

3.8____最小圆覆盖

Buried memory

HDU_3007

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
#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1);
const double eps = 1e-8;

inline int sgn(double x)
{
    if( fabs(x) < eps ) return 0;
    if( x < 0 ) return -1;
    else return 1;
}

    int n;

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){ x = _x;y=_y; }
}p[510];

inline double dis(Point a,Point b )
{
    return hypot( a.x - b.x,a.y - b.y );
}


///求三角形外接圆圆心
inline Point circle_certer(const Point a,const Point b,const Point c)
{
    Point center;
    double a1 = b.x - a.x, b1 = b.y - a.y,c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x, b2 = c.y - a.y,c2 = (a2 * a2 + b2 *b2) / 2;
    double d = a1 * b2 - a2 *b1;
    center.x = a.x + (c1 * b2 - c2 *b1) /d;
    center.y = a.y + (a1 * c2 - a2 *c1) /d;
    return center;
}

void min_cover_circle(Point &c,double &r)
{
    random_shuffle(p,p+n);                          ///将点的排列顺序随机化，降低枚举的时间复杂度
    c = p[0],r = 0;                                 ///从第一个点开始，
    for(int i = 1; i < n ; i++ )
        if( sgn( dis(p[i],c) - r ) > 0 ){           ///新的点，在原来那个圆的外面
            c = p[i],r = 0;
            for(int j = 0; j < i ; j++){            ///从新检查前面的点是否都在圆内
                 if( sgn( dis(p[j],c) - r ) > 0 ){  ///如果之前的点在新园的外面，从新定圆
                    c.x = (p[i].x + p[j].x ) /2;
                    c.y = (p[i].y + p[j].y ) /2;
                    r = dis( p[j],c );
                    for(int k = 0 ;  k < j ; k ++){
                        if( sgn(dis(p[k],c) - r)  > 0){///如果两点定的点不能满足，则选择3个点来确定
                            c = circle_certer(p[i],p[j],p[k]);
                            r = dis(p[i],c);
                        }
                    }
                 }
            }
        }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while(~scanf("%d",&n) && n != 0)
    {
        Point ans;
        double ansr;
        for(int i =0 ; i < n ; i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        min_cover_circle(ans,ansr);
        printf("%.2f %.2f %.2f\n",ans.x,ans.y,ansr);
    }




    return 0;
}

3.9____空凸包（计算几何 + dp）

Empty Convex Polygons)

ICPC_2017沈阳

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
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef double type_p;
const double eps = 1e-6;
const int maxn = 510;
double dp[maxn][maxn];
inline double eq(double x, double y) {
    return fabs(x-y)<eps;
}
inline int eq(int x, int y) {
    return x==y;
}
struct point {
    type_p x,y;
};
type_p xmult(point a, point b, point o)
{
    return (a.x-o.x)*(o.y-b.y)-(a.y-o.y)*(o.x-b.x);//b at ao left if negative, at right if positive
}
type_p dist(point a, point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
point o;
bool cmp_angle(point a,point b) {
    if(eq(xmult(a,b,o),0.0)){
        return dist(a,o)<dist(b,o);
    }
    return xmult(a,o,b)>0;
}
/*
 Input:  p:  Point set
 pn: size of the point set

 Output: the area of the largest empty convex
 */
double empty_convex(point *p, int pn) {
    double ans=0;
    for(int i=0; i<pn; i++){
        for(int j=0; j<pn; j++){
            dp[i][j]=0;
        }
    }
    for(int i=0; i<pn; i++){
        int j = i-1;
        while(j>=0 && eq(xmult(p[i], p[j], o),0.0))j--;//coline
        bool flag= j==i-1;
        while(j>=0){
            int k = j-1;
            while(k >= 0 && xmult(p[i],p[k],p[j])>0)k--;
            double area = fabs(xmult(p[i],p[j],o))/2;
            if(k >= 0)area+=dp[j][k];
            if(flag) dp[i][j]=area;
            ans=max(ans,area);
            j=k;
        }
        if(flag){
            for(int j=1; j<i; j++) {
                dp[i][j] = max(dp[i][j],dp[i][j-1]);
            }
        }
    }
    return ans;
}
double largest_empty_convex(point *p, int pn) {
    point data[maxn];
    double ans=0;
    for(int i=0; i<pn; i++) {
        o=p[i];
        int dn=0;
        for(int j=0; j<pn; j++)
        {
            if(p[j].y>o.y||(p[j].y==o.y&&p[j].x>=o.x))
            {
                data[dn++]=p[j];
            }
        }
        sort(data, data+dn, cmp_angle);
        ans=max(ans, empty_convex(data, dn));
    }
    return ans;
}
int main() {
    point p[110];
    int t;
    scanf("%d",&t);
    while(t--) {
        int pn;
        scanf("%d",&pn);
        for(int i=0; i<pn; i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        printf("%.1f\n",largest_empty_convex(p,pn));
    }
    return 0;
}

3.10 三角形

[Mahmoud and a Triangle](Problem - 766B - Codeforces)

题意: 给你n个线段长度，是否可以中找出3个线段组成三角形 (1e5)

先sort一下，我们知道三角形判断有 $|a-b |< c < |a+b|$ 这里只需要判断 短的两个边是不是大于长的那个边就好了，sort了之后相邻的3个边，一定满足最长的大于最短的两个的绝对值之差

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
#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    sort(a,a+n);

    bool flag = 0;
    for(int i = 2; i < n ; i++){
        if( a[i] < a[i-1] + a[i -2] ){
            flag = 1;
            break;
        }
    }

    if(flag)cout << "YES" <<endl;
    else cout << "NO" <<endl;

}

[Vasya and Triangle](Problem - 1030D - Codeforces)

题意: 给你n,m,k，找到 $ 1 ≤ x_1 , x_2 ,x_3 ≤ n , 1 ≤ y_1 , y_2 ,y_3 ≤ m$ 三个点，三个点必须是整数，构成三角形，使得这个三角形的面积$S = \frac{nm}{k}$ ,找不到的话输出$NO$

思路：用坐标系左下角的$Rt\Delta$ 来做输出的三角形，因为三个点必须是整数，所以 $n,m$一定可除尽$k$ ，之后用gcd来分别除到，y轴的边，x轴的边就可以了

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int a[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    LL n,m,k;
    cin >> n >> m >> k;
    if( 2LL*n*m % k != 0 ){
        cout << "NO" <<endl;
        false;
    }
    else{
        cout << "YES" <<endl;
        if( n % k == 0 ){
            n*= 2;
        }
        else if( m % k == 0 ){
            m*=2;
        }
        else n *=2;
        LL g = __gcd(n,k);
        n = n / g , k = k / g;
        m = m / k;
        cout << 0 << ' ' << 0<<endl;
        cout << 0 << ' ' << m << endl;
        cout << n << ' ' << 0 << endl;

    }
}

4____组合数

Close Tuples (hard version)

5____三分

The Moving Points

​ 那模拟退火 写的…

​ 几个需要注意的点

  1. 时间的最大范围题目没有给，要开到1e8

  2. delta设置太大的话会超时

    image-20210326144613368

    $ 1996 ms $ 对应的是 $delte = 0.98$ （最大的时间是3s）

    $ 826 ms $ 对应的是 $delte = 0.95$

    $ 405 ms $ 对应的是 $delte = 0.90$ 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const double eps = 1e-5;
int n,t;

struct Point
{
    double x,y;
    double vx,vy;
    double distance (const Point &b)
    {
        return hypot( x - b.x , y - b.y );
    }
}p[310],chp[310];


double mindis(double ti)
{
    for(int i = 0 ; i < n ; i++)
    {
        chp[i].x = p[i].x + p[i].vx * ti;
        chp[i].y = p[i].y + p[i].vy * ti;
    }
    double mindiste = 0;
    for(int i =  0 ; i < n ; i ++){
        for(int j = i + 1; j < n; j++){
            mindiste = max(mindiste, chp[i].distance(chp[j]) );
        }
    }

    return mindiste;
}

void solve()
{
    double T = 1e8;
    double delta = 0.90;
    double nowT = 1e4;
    double nowD = mindis(nowT);
    double f[2] = {1,-1};
    while( T > eps )
    {
        double newT = nowT + T * f[rand()%2];
        if( newT >= 0)
        {
            double newD = mindis(newT);
            if( nowD - newD >  eps ){ nowT = newT; nowD = newD; }
        }
        T *= delta;
    }

    printf("%.2f %.2f\n",nowT,nowD);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);


    scanf("%d",&t);

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


        scanf("%d",&n);

        for(int i = 0 ; i < n ;i++)
            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].vx,&p[i].vy);
        printf("Case #%d: ",i);
        solve();
    }

    return 0;
}

Restorer Distance

二分

卡精度Problem - D - Codeforces

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b;
LL f(LL l, LL r) 
{
    if (l > r) return 0;
    LL mid = (l + r) / 2;
    double s=double(log(mid)/log(a));
    if (abs(s * b - mid) < 0.00000000001) 	///看是否有比他更小的存在 
    {
        LL ans = f(1, mid - 1);
        if (ans) return ans;
        return mid;
    }
    if (mid > s * b) 
    return f(l, mid - 1);
    return f(mid + 1, r);
}
int main() 
{
    int flag = 1;
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", f(1, 1e18));
}

6____并查集

Prefix Enlightenment ( 带权并查集 )

7____悬线法（最大子矩阵）

Largest Common Submatrix

棋盘制作

玉蟾宫 BZOJ[3039]

8____线段树

单点更新

敌兵布阵

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+10;

struct Node{
    int l,r;
    int sum;
}T[N<<2];

int a[N];

void push_up(int rt)
{
    T[rt].sum = T[rt << 1].sum + T[rt << 1|1].sum;
}

void build(int rt,int l, int r)
{
    T[rt] = {l,r,0};
    if( T[rt].l == T[rt].r ){
        T[rt].sum = a[ T[rt].l ];
        return ;
    }

    int mid = (l + r) >> 1;
    build(rt << 1,l,mid),build(rt <<1|1,mid+1,r);
    push_up(rt);
}

void update(int rt,int pos,int val)
{
    if( T[rt].l == T[rt].r && T[rt].r == pos ){
        T[rt].sum += val;
        a[ pos ] += val;
        return ;
    }

    int mid = ( T[rt].l + T[rt].r ) >>1;
    if( pos <= mid ) update(rt <<1,pos,val);
    else update(rt <<1|1,pos,val);
    push_up(rt);
}

int query(int rt,int l,int r)
{
    if( l <= T[rt].l && r >= T[rt].r ){
        return T[rt].sum;
    }

    int mid = (T[rt].l + T[rt].r) >> 1;
    int son = 0;
    if( l <= mid ) son += query(rt <<1,l,r);
    if( r > mid ) son += query(rt <<1|1,l,r);
    return son;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >>t;
    for(int c = 1; c <= t ; c++){
        cout << "Case "<<c<<":"<<endl;
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i++){
            cin >> a[i];
        }

        build(1,1,n);

//        for(int i =0  ; i< 32 ; i++){
//            cout << T[i].sum << endl;
//        }

        string s;
        while(cin >>s){
            if( s == "End" ) break;
            int x,y;
            cin >>x >>y;
            if( s == "Add" ){
                update( 1,x,y );
            }else if( s == "Sub" ){
                update(1,x,y*-1);
            }else{
                cout << query(1,x,y) <<endl;
            }
        }
    }


    return 0;
}

I Hate it

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
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int A[N],tree[N*4 + 1];
int n,m;

void push_up(int rt)
{
    tree[rt] = max(tree[rt << 1] ,tree[rt << 1|1] );
}

void build(int rt,int l , int r)
{
    if( l == r )
    {
         tree[rt] = A[r];
        // cout <<tree[rt] << ' ' << A[r] << ' ' << r<<endl;
         return ;
    }
    else
    {
        int mid = (l + r) >> 1;
        build( rt << 1 , l ,mid );
        build( rt << 1|1 , mid + 1, r );
        push_up(rt);
    }

}

void update(int rt,int l,int r ,int pos,int val )
{
    if( l == r && l == pos )
    {
        A[pos] = val;
        tree[rt] = val;
        return ;
    }

    int mid = ( l + r) >> 1;
    if( pos <= mid ) update( rt << 1,l, mid , pos ,val );
    else update( rt << 1|1 , mid + 1 ,r, pos,val);
    push_up(rt);
}

int rangeMax(int rt,int l,int r,int start,int ed)
{
    if( r < start || l > ed ) return 0;
    if( start <= l && ed >= r ) return tree[rt];
    else
    {
        int mid = ( l + r ) >> 1;
        int l_son,r_son;
        l_son = r_son = 0;
        if( start <= mid ) l_son = rangeMax( rt<< 1, l,mid,start,ed );
        if( ed >= mid ) r_son = rangeMax( rt << 1|1 ,mid +1 ,r,start,ed );
        return max( l_son,r_son );

    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    while(cin >> n >> m)
    {
        for(int i = 1 ; i <= n ; i++) cin >> A[i];
        build(1,1,n);
        while(m--)
        {
            char cmd;
            int x,y;
            cin >> cmd >> x >> y;
            if( cmd == 'Q' ){
                cout << rangeMax(1,1,n,x,y) << endl;
                //for(int i = 1; i <= 10 ; i++)cout << tree[i] <<endl;
            }
            else if( cmd == 'U' ){
                update(1,1,n,x,y);
            }
        }
    }

    return 0;
}

最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

struct Node{
    int l,r;
    int sum;
}T[N<<2];

void push_up(int rt)
{
    T[rt].sum = max(T[rt << 1].sum , T[rt << 1|1].sum);
}

void build(int rt,int l, int r)
{
    T[rt] = {l,r,0};
    if( T[rt].l == T[rt].r ){
        return ;
    }

    int mid = (l + r) >> 1;
    build(rt << 1,l,mid),build(rt <<1|1,mid+1,r);
    push_up(rt);
}

void update(int rt,int pos,int val)
{
    if( T[rt].l == T[rt].r && T[rt].r == pos ){
        T[rt].sum = val;
        return ;
    }

    int mid = ( T[rt].l + T[rt].r ) >>1;
    if( pos <= mid ) update(rt <<1,pos,val);
    else update(rt <<1|1,pos,val);
    push_up(rt);
}

int query(int rt,int l,int r)
{
    if( l <= T[rt].l && r >= T[rt].r ){
        return T[rt].sum;
    }

    int mid = (T[rt].l + T[rt].r) >> 1;
    int l_son = 0,r_son = 0;
    if( l <= mid ) l_son = query(rt <<1,l,r);
    if( r > mid ) r_son += query(rt <<1|1,l,r);
    return max(l_son,r_son);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,p,res = 0 ,cnt = 1;
    cin >> n >> p;

    build(1,1,n);

    for(int i = 0; i < n ; i++){
        char c;
        int x;
        cin>> c>>x;
        if( c == 'A' ){
            update(1,cnt++, (x+res)%p );
        }else{
            res = query( 1,cnt - x,cnt-1 );
            cout <<res << "\n";
        }
    }
    return 0;
}

Tunnel Warfare

1

第八大奇迹

(3条消息) 19蓝桥国赛B组C/C++ I第八大奇迹_cy41的博客-CSDN博客

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1e5+7;

int b[29];

int m8[maxn<<2|1][9];

void calc(int k[],int k1[],int k2[]){
    int p=1,q=1,id=1;
    while(p<=8&&q<=8){
        if(k1[p]>=k2[q]) b[id++]=k1[p++];
        else b[id++]=k2[q++];
    }
    while(p<=8) b[id++]=k1[p++];
    while(q<=8) b[id++]=k2[q++];
    for(int i=1;i<=8;++i) k[i]=b[i];
}

void upd(int l,int r,int k,int id,int val){
    if(l==r) {m8[k][1]=val;return ;}
    int mid=l+r>>1;
    if(id<=mid) upd(l,mid,k<<1,id,val);
    else upd(mid+1,r,k<<1|1,id,val);
    calc(m8[k],m8[k<<1],m8[k<<1|1]);
}

int* ask(int l,int r,int k,int L,int R){
    if(l>=L&&r<=R) return m8[k];
    int mid=l+r>>1;
    if(R<=mid) return ask(l,mid,k<<1,L,R);
    else if(L>mid) return ask(mid+1,r,k<<1|1,L,R);
    int* k1=ask(l,mid,k<<1,L,R);
    int* k2=ask(mid+1,r,k<<1|1,L,R);
    int *kk=new int[9];
    calc(kk,k1,k2);
    return kk;
}

char s[9];
int main(){
    int n,q,id,l,r,x;
    cin>>n>>q;
    while(q--){
        scanf("%s%d%d",s,&l,&r);
        if(s[0]=='C') upd(1,n,1,l,r);
        else printf("%d\n",ask(1,n,1,l,r)[8]);
    }
    return 0;
}

我的代码（超时，效果没有问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

struct node
{
    int l,r;
    int num[8];
}t[N<<2];
int n,m;

inline void push_up(int ta[],int la[],int ra[])
{
    sort(la ,la+8 );
    sort(ra ,ra+8 );
    int l = 7,r = 7,idx = 7;
    while(idx >=0){
        if(la[l] >= ra[r]){
            ta[idx--] = la[l--];
        }
        else  ta[idx--] = ra[r--];
        ///
        if( l == -1 && idx >= 0){
            while( idx < 8 && r >=0 ){
                ta[idx--] = la[l--];
            }
            break;
        }
        if( r == -1 && idx >=0 ){
            while(idx < 8 && l >= 0){
                ta[idx--] = ra[r--];
            }
            break;
        }
    }
    return ;
}

void build(int rt,int l, int r)
{
    t[rt].l = l , t[rt].r = r;
    if(l == r){
        for(int i = 0;  i < 8 ; i++){
            t[rt].num[i] = 0;
        }
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt << 1,l,mid),build(rt <<1|1,mid+1,r);
}

inline void update(int rt,int loc,int val)
{
    if( t[rt].l == t[rt].r && t[rt].l == loc ){
        t[rt].num[7] = val;
        return ;
    }
    int mid = t[rt].l +t[rt].r >>1;
    if( loc <= mid ) update( rt << 1, loc ,val );
    else update( rt <<1|1,loc ,val );
    push_up(t[rt].num , t[rt<<1].num,t[rt<<1|1].num);
}

inline int* rangeQuery(int rt,int l,int r)
{
    //cout << rt << ' ' <<t[rt].l << ' ' << t[rt].r <<' '<< l <<' ' <<r <<endl;
    if( l <= t[rt].l && r >= t[rt].r ){
        return t[rt].num;
    }
    //if( t[rt].l >r ||t[rt].r < l ) return new int[8];
    int mid = t[rt].l +t[rt].r >> 1;
    int *la= new int[8],*ra= new int[8];
    for(int i = 0 ; i< 7 ; i++){
        la[i] = 0;
        ra[i] = 0;
    }
    if( l <= mid )  la = rangeQuery(rt<<1,l,r);
    if( r > mid)    ra = rangeQuery(rt<<1|1,l,r);
    int *ta = new int[8];
    memset(ta,0,sizeof ta);
    push_up(ta,la,ra);
    return ta;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    cin >> n >> m;
    build(1,1,n);
    for(int i = 0 ; i < m ; i++){
        char op;
        int x,y;
        cin >> op >> x >> y;
        if(op == 'C'){
            update(1,x,y);
        }
        else{
            //cout << "--" << x << ' ' << y <<endl;
            int *ans = rangeQuery(1,x,y);
            cout << ans[0] <<endl;
//            cout << "-------" <<endl;
//            for(int i = 0 ; i < 8 ; i ++){
//                cout << ans[i] << endl;
//            }
//            cout << "-------" <<endl;
        }

    }
    return 0;
}
/*
8 9
C 1 20
C 2 30
C 6 24
Q 1 2
C 3 23
C 4 43
C 5 90
C 7 53
C 8 12
*/










区间更新

一个简单的整数问题2

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
ll a[N];
struct Node
{
    ll l ,r;
    ll sum;
    ll lazy;
}T[N<<2];

void push_up(int rt)
{
    T[rt].sum = T[rt << 1].sum + T[rt << 1|1].sum;
}

void push_down(int rt)
{
    if( T[rt].lazy != 0 ){
        int mid = (T[rt].l + T[rt].r) >> 1;
        T[rt << 1].sum += T[rt].lazy * ( mid - T[rt].l + 1);
        T[rt << 1 | 1].sum += T[rt].lazy * ( T[rt].r - mid) ;
        T[rt << 1].lazy += T[rt].lazy;
        T[rt << 1|1].lazy += T[rt].lazy;
        T[rt].lazy = 0;
    }
}

void build(int rt,int l,int r)
{
    T[rt] = {l,r,0,0};
    if( l == r ){
        T[rt].sum = a[l];
        return ;
    }

    int mid = (l + r) >> 1;
    build(rt<<1,l,mid),build(rt <<1|1,mid+1,r);
    push_up(rt);
}

void rangeUpdate(int rt, int l,int r,int val)
{
    if( l <= T[rt].l && r >= T[rt].r ){
        T[rt].sum += val * (T[rt].r - T[rt].l + 1);
        T[rt].lazy += val;
        return ;
    }
    int mid = ( T[rt].l + T[rt].r ) >> 1;
    push_down(rt);
    if( l <= mid ) rangeUpdate( rt << 1,l,r,val );
    if( r > mid ) rangeUpdate( rt << 1|1,l,r,val );
    push_up(rt);
}

ll rangeQuery(int rt,int l ,int r)
{
    if( l <= T[rt].l && r >= T[rt].r ){
        return T[rt].sum;
    }
    ll mid = ( T[rt].l + T[rt].r ) >> 1;
    push_down(rt);

    ll son = 0;
    if( l <= mid ) son += rangeQuery(rt << 1,l,r);
    if( r > mid ) son += rangeQuery(rt << 1|1,l,r);

    push_up(rt);
    return son;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ )  cin >> a[i];
    build(1,1,n);
    for(int i = 0 ; i < m ; i++ ){
        char op ;
        ll x,y,z;
        cin >> op;
        if( op == 'C' ){
            cin >> x >> y >> z;
            rangeUpdate(1,x,y,z);
        }else{
            cin >> x >> y;
            cout << rangeQuery(1,x,y) << "\n";
        }
    }



    return 0;
}

Mayor’s posters 离散+线段树（因为数据的问题不知道是不是对的）

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
#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
#define ls rt << 1
#define rs rt << 1|1
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Node
{
    int l,r;
    int tp;
    int lazy;
}T[N << 2];

inline void push_down(int rt)
{
    if( T[rt].lazy != 0 ){
        T[ls].tp = T[rt].lazy;
        T[ls].lazy = T[rt].lazy;
        T[rs].tp = T[rt].lazy;
        T[rs].lazy = T[rt].lazy;
        T[rt].lazy = 0;
    }
}

inline void push_up(int rt)
{
    if( T[ls].tp != T[rs].tp ) T[rt].tp = INF;
    else    T[rt].tp = T[ls].tp;
}

void build(int rt,int l,int r)
{
    T[rt] = {l,r,0,0};
    if( l == r ){
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid),build(rs,mid+1,r);
}


inline void rangeUpdate(int rt,int l,int r,int val)
{
    if( l <= T[rt].l && r >= T[rt].r ){
        T[rt].tp = val;
        T[rt].lazy = val;
        return ;
    }
    int mid = (T[rt].l + T[rt].r) >>1;
    push_down(rt);
    if( l <= mid ) rangeUpdate( ls,l,r,val );
    if( r > mid ) rangeUpdate( rs,l,r,val );
    push_up(rt);
}

inline int getTpye(int rt,int pos)
{
    if( T[rt].l == T[rt].r && T[rt].l == pos ){
        return T[rt].tp;
    }
    int mid = ( T[rt].l + T[rt].r ) >>1;
    int son = 0;
    push_down(rt);
    if(pos <= mid)  son = getTpye( ls,pos );
    else son = getTpye(rs,pos);
    return son;
}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin >> k;
    while(k--){
        int n;
        cin >> n;


        ///离散化
        vector<pair<int,int> > a(n);
        vector<int> ans;
        for(int i = 0; i < n ; i ++){
            cin >> a[i].first >> a[i].second;
            ans.push_back(a[i].first);
            ans.push_back(a[i].second);
        }
        sort(ans.begin(),ans.end());
        ans.erase( unique(ans.begin(),ans.end()),ans.end() );

        int len = ans.size();
        for(int i = 1 ; i < len; i ++){
            if( ans[i] - ans[i-1] > 1 ){
                ans.push_back( ans[i-1] + 1 );
            }
        }
        sort(ans.begin(),ans.end());

//        for(int i = 0 ; i < ans.size() ; i++ ){
//            cout << ans[i] << " \n"[i == ans.size()];
//        }
        build(1,1,ans.size());

        /// 贴海报
        len = a.size();
        for(int i =0 ; i < len ; i++){
            int x = lower_bound(ans.begin(), ans.end() , a[i].first) - ans.begin() + 1;
            int y = lower_bound(ans.begin(), ans.end() , a[i].second) - ans.begin() + 1;
            rangeUpdate( 1,x,y,i+1 );

        }
        //cout <<endl;
        len = ans.size();
        set<int> se;
        for(int i = 1 ; i <= len ; i++ ){
            int te = getTpye(1,i);

            se.insert( te );
        }
        se.erase(0);
        cout <<se.size() <<endl;

    }

    return 0;
}

Can you answer these queries?

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll A[N];

struct Node
{
    ll l,r;
    ll sum;
}tree[N*4];

void push_up( ll rt)
{
    tree[rt].sum = tree[rt<< 1].sum + tree[rt << 1|1].sum;
}

void build( ll rt, ll l, ll r)
{
    tree[rt].l = l ,tree[rt].r = r;
    if(l == r)
        tree[rt].sum = A[r];
    else
    {
        ll mid = (l + r) >> 1;
        build(rt << 1,l ,mid);
        build(rt << 1|1,mid +1 ,r);
        push_up(rt);
    }
}

void Update(int rt,int l,int r)
{
    if( tree[rt].l == tree[rt].r)
    {
        tree[rt].sum = (ll)sqrt( (double)tree[rt].sum );
        return ;
    }
    if( l <= tree[rt].l && r >= tree[rt].r && tree[rt].sum == tree[rt].r - tree[rt].l + 1 ) return ;

    ll res = 0;
    ll mid = ( tree[rt].l + tree[rt].r ) >> 1;
    if( l <= mid )  Update(rt << 1,l ,r);
    if( r > mid )   Update( rt << 1|1,l,r );
    push_up(rt);
}

ll Query(int rt,int l,int r)
{
    if( l <= tree[rt].l && r >= tree[rt].r  )   return tree[rt].sum;
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    ll res = 0;
    if( l <= mid ) res += Query(rt << 1,l , r);
    if( r > mid )   res += Query(rt << 1|1,l ,r);

    return res ;
 }

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    int cnt = 1;
    while(cin >> n)
    {
        cout << "Case #" << cnt++  <<':' <<endl;
        for(int i = 1; i <= n ; i++)    cin >> A[i];
        build(1,1,n);
        cin >> m;

        for(int i = 0 ; i < n ; i++)
        {
            int cmd,x,y;
            cin >> cmd >>x >>y;
            if( x > y) swap(x,y);
            if( cmd == 1)
            {
                cout << Query(1 ,x,y) <<endl;
            }
            else
            {
                Update(1,x,y);
            }
        }
        cout << endl;
    }

    return 0;
}

A Simple Problem with Integers - POJ 3468

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
```



### [Balanced Lineup](https://vjudge.net/problem/POJ-3264)

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

const int N = 50005;
int A[N];
struct Node
{
    int l,r;
    int maxn,minn;
}tree[N*4];

void push_up(int rt)
{
    tree[rt].maxn = max( tree[rt << 1].maxn,tree[rt << 1|1].maxn );
    tree[rt].minn = min( tree[rt << 1].minn , tree[rt << 1|1].minn );
}

void build(int rt,int l, int r)
{
    tree[rt].l = l,tree[rt].r = r;
    if(l == r)
        tree[rt].maxn = tree[rt].minn = A[r];
    else
    {
        int mid = (l + r) >> 1;
        build( rt << 1, l , mid );
        build( rt << 1|1,mid + 1, r );
        push_up(rt);
    }
}

pair<int,int> Query(int rt,int l ,int r)
{
    if( l <= tree[rt].l && r >= tree[rt].r )
    {
        return { tree[rt].maxn,tree[rt].minn };
    }
    else if( tree[rt].l > r || tree[rt].r < l ) return {0,20000000};
    else
    {
        int mid = (tree[rt].l + tree[rt].r) >> 1;
        pair<int,int> l_son,r_son;
        l_son = r_son = {0,20000000};
        if( l <= mid )  l_son = Query(rt << 1, l ,r);
        if( r > mid )  r_son = Query(rt << 1|1, l ,r);
        return { max( l_son.first,r_son.first ) , min(l_son.second,r_son.second ) };
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    cin >> n >>m;
    for(int i = 1 ; i <= n ; i++)   cin >>A[i];

    build(1,1,n);

    for(int i = 0 ; i< m ; i++)
    {
        int x,y;
        cin >> x >> y;

        pair<int,int> te = Query(1,x,y);
        cout << (int)(te.first - te.second) << endl;
    }

    return 0;
}

扫描线

245. 你能回答这些问题吗 - AcWing题库

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 5e5+10;
ll a[N];
struct node
{
    ll l,r,sum,lm,rm,ma;
}t[N*4];

const int inf = 0x3f3f3f3f*-1;

void push_up(int rt)
{
    t[rt].lm = max( t[rt << 1].lm ,t[rt<< 1].sum + t[rt << 1|1].lm );
    t[rt].rm = max( t[rt << 1|1].rm , t[rt <<1|1].sum + t[rt <<1].rm );
    t[rt].ma= max( max( t[rt << 1].ma,t[rt <<1|1].ma ),t[rt<< 1].rm +t[rt <<1|1].lm );
    t[rt].sum = t[rt <<1].sum + t[rt << 1|1].sum;
}

void build(int rt, int l,int r)
{
    t[rt] = {l,r,0,0,0,0};
    if(l == r){
        t[rt].sum = t[rt].lm = t[rt].rm = t[rt].ma = a[r];
        return ;
    }
    int mid = l +r >>1;
    build(rt << 1,l,mid),build(rt <<1|1,mid + 1,r);
    push_up(rt);
}

void update( int rt,int loc ,int val)
{
    if( t[rt].l == t[rt].r && t[rt].l == loc ){
        t[rt].sum = t[rt].lm = t[rt].rm = t[rt].ma= val;
        return ;
    }
    int mid = t[rt].l +t[rt].r >>1;
    if( loc <= mid ) update( rt <<1,loc,val );
    else update(rt <<1|1,loc ,val);
    push_up(rt);
}

node rangeQuery(int rt,int l,int r)
{
    if( l <= t[rt].l && r >= t[rt].r){
        return t[rt];
    }
    int mid = t[rt].l + t[rt].r >> 1;
    node l_son ,r_son, son;
    son.sum = 0;
    if( l <= mid && r > mid ){
        l_son = rangeQuery(rt<<1 , l , r);
        r_son = rangeQuery( rt<<1|1 ,l,r);
        son.sum += l_son.sum + r_son.sum;
        son.ma = max( max( l_son.ma ,r_son.ma ), l_son.rm + r_son.lm );
        son.lm = max( l_son.lm , l_son.sum + r_son.lm );
        son.rm = max( r_son.rm , r_son.sum + l_son.rm );
    }
    else if( l <= mid ){
        l_son = rangeQuery(rt<<1 , l , r);
        son.sum += l_son.sum;
        son = l_son;
    }
    else if( r > mid){
        r_son = rangeQuery( rt<<1|1 ,l,r);
        son.sum += r_son.sum;
        son = r_son;
    }


   // cout << l_son.ms << ' ' << r_son.ms << ' '<<endl;
    return son;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n ; i++){
        cin >> a[i];
    }
    build(1,1,n);
    for(int i = 0 ; i < m ; i++){
        int op,x,y;
        cin >> op >>x >> y;
        if( op == 1 ){  ///q
            if( x > y ) swap(x,y);
            auto it = rangeQuery(1,x,y);
            cout << it.ma <<endl;
        }else{          ///add
            update(1,x,y);
        }
    }
//
//    for(int i = 1 ; i < 20;  i++){
//        cout << t[i].ma <<endl;
//    }

    return 0;
}



#6278. 数列分块入门 2 

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
#include <bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define Mid ((T[rt].l + T[rt].r)>>1)
#define L ( T[rt].l)
#define R (T[rt].r)
using namespace std;

const int N = 5e4+10;
void file()
{
    #ifdef ONLINE_JUDGE
    #else
        freopen( "d:/workProgram/test.in","r",stdin );
    #endif
}

struct Node
{
    int l,r;
    int ma,mi;
    int lazy ;
}T[N << 2];

int a[N];

void up(int rt)
{
    T[rt].ma = max( T[ls].ma, T[rs].ma );
    T[rt].mi = min( T[ls].mi , T[rs].mi );
}

void down(int rt)
{
    if( T[rt].lazy != 0 ){
        T[ls].lazy += T[rt].lazy;
        T[rs].lazy += T[rt].lazy;
        T[ls].ma += T[rt].lazy;
        T[rs].ma += T[rt].lazy;
        T[ls].mi += T[rt].lazy;
        T[rs].mi += T[rt].lazy;
        T[rt].lazy = 0;
    }
}

void build(int rt,int l ,int r)
{
    T[rt] = {l,r,0,0,0};
    if( l == r){
        T[rt].ma = T[rt].mi = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid),build(rs,mid+1,r);
    up(rt);
}

void rangeUpdate(int rt,int l,int r,int val)
{
    if( l <= L && r >= R  ){
        T[rt].ma += val;
        T[rt].mi += val;
        T[rt].lazy += val;
        return ;
    }
    down(rt);
    if( l <= Mid ) rangeUpdate( ls, l,r,val );
    if( r > Mid ) rangeUpdate(rs,l,r,val);
    up(rt);
}

int rangeQuery(int rt,int l,int r,int x)
{
    if( T[rt].mi >= x ) return 0;
    if( l <= L  && r >= R && T[rt].ma < x ){
        return T[rt].r - T[rt].l + 1;
    }

    down(rt);
    int cnt = 0;
    if( l <= Mid ) cnt += rangeQuery(ls,l,r,x);
    if( r > Mid ) cnt += rangeQuery(rs,l,r,x);
    return cnt;
}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //file();
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    build(1,1,n);

    for(int i = 0; i < n ; i++){
        int op,l,r,x;
        cin >> op >> l >> r >>x;
        //cout << "--"<< i <<endl;
        if( op == 0 ){
            rangeUpdate(1,l,r,x);
        }else{
            cout <<rangeQuery(1,l,r,x*x) <<endl;
        }
    }
    //system("pause");

    return 0;
}

9____可持续化线段树（主席树）

权值线段树

_Find the answer

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
typedef long long ll;
ll ca,n,m;
int a[N],b[N];

struct Node
{
    int l ,r;
    ll val,time;
}t[N * 4];

void push_up(int rt)
{
    t[rt].val = t[rt << 1].val + t[rt <<1|1].val;
    t[rt].time = t[rt <<1].time + t[rt << 1|1].time;
}

void build(ll rt,ll l, ll r)
{
    t[rt] = {l,r,0,0};
    if(l == r)  return ;

    ll mid = (l + r) >> 1;
    build(rt <<1,l,mid),build(rt <<1|1,mid+ 1,r);
}

void update(ll rt,ll l,ll r,ll val)
{
    if( l <= t[rt].l && r >= t[rt].r )
    {
        t[rt].val += val;
        t[rt].time ++;
        return ;
    }

    ll mid = (t[rt].l + t[rt].r) >>1;
    if(l <= mid) update(rt <<1,l,r,val);
    if(r > mid  ) update(rt <<1|1,l,r,val);
    push_up(rt);
}

///val为需要删除的元素的和，ans为删除的数量
void query(ll rt,ll val,ll &ans)
{
    if( t[rt].l == t[rt].r )
    {
        if( val % b[ t[rt].l ] == 0 ) ans += val / b[ t[rt].l ];
        else ans += val / b[ t[rt].l ] + 1;
        return ;
    }

    ///如果右边的（大的集合）大于val，就继续向右边找
    if( t[rt << 1 | 1].val >= val ) query(rt << 1|1,val,ans);
    else///如果右边的数小于了，那么就把右边的数都删了，然后再向左边找
    {
        ans += t[rt << 1|1].time;
        val -= t[rt << 1|1].val;
        query( rt << 1,val,ans );
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> ca;
    while(ca--)
    {
        ll sum = 0;
        cin >> n >> m;
        for(int i = 1; i <= n ; i++) cin >> a[i], b[i] = a[i];
        ///去重
        ///去重建的树，是重小大大开始建树的
        sort(b+1,b+n+1);
        ll len = unique(b +1 ,b +1+n) - (b + 1);

        build(1,1,len);
        for(int i = 1; i <= n ; i++)
        {
            sum += a[i];    ///前缀和
            if( i == 0 )cout << "0 ";
            else
            {
                ll ans = 0; ///最后去除了几个数
                if( sum <= m)   ans = 0;
                else query(1,sum - m , ans);

                cout << ans << ' ';
            }
            ll loc = lower_bound(b +1 , b+1+len ,a[i]) - b;
            ///插入
            update(1,loc,loc,a[i]);
        }
        cout << endl;

    }

    return 0;
}

10____可持续化字典树

11____Tire树

Phone List(wa)

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
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cstring>

using namespace std;

const int N = 11000;
int son[N][26],idx,cnt[N];

bool Insert(string s)
{
    int p = 0;
    int len = s.length();

    for(int i = 0; i < len ;i ++)
    {
        int u = s[i] - '0';
        if( cnt[p] != 0 ) return false;
        if( !son[p][u] ) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
    return true;
}

int t,n;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> n;
        memset(son,0,sizeof son);
        memset(cnt,0,sizeof cnt);
        idx = 0;
        bool flag = true;
        for(int i =0; i < n ;i++ )
        {

            cin >> s;
            if( flag )
                flag = Insert(s);
        }
        if( flag ) cout << "YES" <<endl;
        else cout << "NO" << endl;

    }

    return 0;
}

统计难题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

const int N = 1000006;
int son[N][26],cnt[N],idx = 0;

void Insert(char *str,int len)
{
    int p = 0;
    for(int i = 0 ; i < len ; i++)
    {
        int u = str[i] - 'a';
        if( !son[p][u] ) son[p][u] = ++idx;
        p = son[p][u];
        cnt[p]++;
    }
}

int Query(char *str)
{
    int len = strlen(str);
    int p = 0,u;
    for(int i = 0 ; i < len ; i++)
    {
        //cout << str[i] << ' ' <<c
        u = str[i] - 'a';
        if( !son[p][u] ) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    char s[12];
    while(gets(s))
    {
        int len =strlen(s);
        if( len == 0) break;

        Insert(s,len);

    }

    while( gets(s) )
    {
        cout << Query(s) <<endl;
    }

    return 0;
}

最大异或对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int son[N*31][2],a[N],idx = 0 ;

void Insert(int x)
{
    int p = 0;
    for(int i = 30 ; i >= 0 ; i--)
    {
        int u = x >> i & 1; //取x的第i位
        if( !son[p][u] ) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int Query(int x)
{
    int p = 0, ret = 0;
    for(int i = 30; i >= 0 ; i--)
    {
        int u = x >> i & 1;
        if( !son[p][!u] )
        {
            p = son[p][u];
            ret = ret * 2 + u;
        }
        else
        {
            p = son[p][!u];
            ret = ret * 2 + !u;
        }
    }
    //cout << ret << endl;
    ret = ret ^ x;
    return ret;
}
    int n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    int maxn = 0;
    for(int i = 1; i <= n ; i++)
    {
        int te ;
        cin >> te;
        Insert(te);
        maxn = max(maxn,Query(te) );
    }

    cout << maxn <<endl;

    return 0;
}

12_DP

902. 最短编辑距离

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+10;
char a[N],b[N];
int dp[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> a + 1 >> m >> b + 1;
    for(int i = 1 ; i <= n ; i++) dp[i][0] = i;
    for(int j = 1 ; j <= m ; j++) dp[0][j] = j;
    ///
    for(int i = 1 ;  i <= n ; i++){
        for(int j = 1; j <= m ; j++){
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
            dp[i][j] = min( dp[i][j] , dp[i-1][j-1] + (a[i] != b[j]) );
        }
    }

    cout <<dp[n][m] <<endl;

    return 0;
}

传球游戏

滑雪

13_搜索

(4条消息) BFS广搜题目【经典训练题】_reverie_mjp的博客-CSDN博客

[(4条消息) kuangbin带你飞]专题一 做题顺序与题解 【简单搜索】_指弹键盘哼民谣-CSDN博客_kuangbin带你飞做题顺序

**I-Penguins_2021牛客暑期多校训练营2 ** DFS路径输出

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
#include <bits/stdc++.h>
using namespace std;

char s[30][50]; ///读入的地图
pair< pair<int,int>,pair<int,int> > lst[21][21][21][21];
queue< pair< pair<int,int>,pair<int,int> > > q; ///两个人走到那个位置了
int dis[21][21][21][21];    ///判重
char op[21][21][21][21];    ///路径记录

int d[4][4]={1,0,1,0,0,-1,0,1,0,1,0,-1,-1,0,-1,0};  ///两个人所有的步数情况（镜像）
char o[4]={'D','L','R','U'};

void pass(pair<pair<int,int> ,pair<int,int> > x)
{
    int x1 = x.first.first;
    int y1 = x.first.second;
    int x2 = x.second.first;
    int y2 = x.second.second;

    s[x1][y1] = s[x2][y2+21] = 'A';
    if( x1 == 20 && y1 == 20 &&  x2 == 20 && y2 == 1 )return ;
    pass(lst[x1][y1][x2][y2]);
    ///回溯的时候再输出 , nb
    cout << ( op[x1][y1][x2][y2] );
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for(int i = 1 ; i <= 20; i++){
        cin >> s[i]+1 >> s[i]+22;
    }

    q.push( { {20,20},{20,1} } );
    dis[20][20][20][1] = 1;

    while(!q.empty() ){
        int x1 = q.front().first.first;
        int y1 = q.front().first.second;
        int x2 = q.front().second.first;
        int y2 = q.front().second.second;

        q.pop();

        for(int i = 0 ; i < 4 ; i++){
            int nx1 = x1 + d[i][0];
            int ny1 = y1 + d[i][1];
            int nx2 = x2 + d[i][2];
            int ny2 = y2 + d[i][3];

            if( nx1 < 1 || nx1 > 20 || ny1 < 1 || ny1 >20 || s[nx1][ny1] == '#' ) nx1 = x1,ny1=y1;
            if( nx2 < 1 || nx2 > 20 || ny2 < 1 || ny2 > 20 || s[nx2][ny2 + 21] == '#' ) nx2 = x2,ny2 = y2;

            ///越界，或者找过了
            if( dis[nx1][ny1][nx2][ny2] ) continue;

            dis[nx1][ny1][nx2][ny2] = dis[x1][y1][x2][y2] + 1;
            op[nx1][ny1][nx2][ny2] = o[i];
            lst[nx1][ny1][nx2][ny2] = { {x1,y1},{x2,y2} };
            q.push( {{nx1,ny1},{nx2,ny2}} );
        }
    }

    cout << dis[1][20][1][1]-1 <<endl;
    pass( {{1,20},{1,1}} );
    cout << endl;
    for(int i=1;i<=20;i++)
        s[i][21]=' ';

    for(int i = 1 ; i <= 20 ; i++){
        for(int j = 1; j <= 41 ; j ++ ){
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}

POJ1175____Starry Night

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
```

#### 八数码_A*

```c++
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>

#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

string sta,seq;
string en = "12345678x";

map<string,int> dist; ///判重
map<string,pair<string,char> > cost;   ///路径记录
priority_queue<pair<int,string> ,vector<pair<int,string> >,greater<pair<int,string> > > q;      ///将启发函数数值小的排前面

int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
char op[] = {'d','l','r','u'};

int get(string s)
{
    int res = 0;
    for(int i = 0 ; i < 9 ; i++)
    {
        if(s[i] != 'x')
        {
            int t = s[i] - '1';
            res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return res;
}

void bfs(string s)
{

    q.push( make_pair(get(s),s) );
    dist[s] = 1;

    while(!q.empty()){

        pair<int,string>  no = q.top();
        q.pop();
        string from = no.second;
        string state = from;
        if( no.second == en ){
            break;
        }
        //cout << no.first << endl;
        int loc = state.find('x');
        int k = dist[state];
        int x = loc / 3;
        int y = loc % 3;
        for(int i = 0 ; i < 4;  i++){
            int tx = x + dx[i] , ty = y + dy[i];
            if(tx < 3 && ty < 3 && tx >=0 && ty >=0){
                swap( state[loc],state[tx*3 + ty] );
                if( dist[state] == 0 || dist[state] > k + 1 ){
                    dist[state] = k+1;
                    q.push(make_pair(dist[from]+get(state),state) );
                    cost[state] = make_pair(from,op[i]);
                }
                swap( state[loc],state[tx*3 + ty] );
            }
        }
    }

    if( dist[en] == 0){
        cout << "unsolvable" <<endl;
    }else{
        string res="";
        string te = en;
        while( te != sta ){
            res +=cost[te].second;
            te = cost[te].first;
        }

        reverse(res.begin(),res.end());
        cout <<res <<endl;
    }

}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for(int i =0 ; i < 9 ; i++){
        char c;
        cin >> c;
        sta+=c;
        if(c != 'x') seq += c;
    }

    int cnt = 0;
    for(int i = 0 ; i < 8 ; i ++)
        for(int j = i + 1 ; j < 8 ; j++)
            if(seq[i] > seq[j])
                cnt++;
    if(cnt % 2) puts("unsolvable");
    else bfs(sta);

    return 0;
}

14____数列分块

14.1____数列分块1（区间加法，单点查询）

image-20210803104118041

题解：

​ 这个题就是数列分块的板子题，对区间做区间修改，单点查询，区间修改为区间加法，线段树同样可以做，但是代码就很复杂了，我们用 tag 来维护分块区间的相同和

​ 在update的时候，如果在同一区间内，那么我们直接 $O(n)$​​​解决 ，如果不在的话，那么位于左端和右端的区间，我们都直接 $O(n)$​​​ 处理， 在中间的区间，我们直接同一加到 tag 上，这 tag 数组有点像 线段树的 lazy标记，但是不会 push_down，查询的时候，我们直接叠加上去就可以了。

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 <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

int a[N],s[N],tag[N],len,id[N];

void add(int l,int r,int c)
{
    int sid = id[l] , eid = id[r];
    if( sid == eid ){
        for(int i = l ;i <= r; i++){
            a[i] += c, s[sid] += c;
        }
        return ;
    }

    for(int i = l ; id[i] == sid ; i++) a[i] += c,s[ sid ] += c;
    for(int i = sid + 1 ; i < eid ; i++) tag[i] += c,s[ i ] += c * len;
    for(int i = r ; id[i] == eid ; i--) a[i] += c,s[eid] += c;
}

int query(int x)
{
    return a[x] + tag[ id[x] ];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    len = sqrt(n);

    for(int i = 1; i <= n ; i++){
        cin >> a[i];
        id[i] = (i - 1) / len + 1;
        s[ id[i] ] += a[i];
    }

    for(int i = 0 ; i < n ; i++){
        int op,x,y,z;
        cin >> op >> x >> y >> z;
        if( op == 0 ){
            add(x,y,z);
        }else{
            cout << query(y) << endl;
        }
    }
    return 0;
}

14.2____数列分块2

image-20210803104611858

好题：

1____幂次方( 递归 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int n;

string f(int x)
{

    int w = 0;
    string s = "" ; ///存最后的
    string r = "" ; ///每一步拆分出来的
    string t = "" ; ///运算符

    if( x == 0 ) return "0";

    do{
        if( x % 2 == 1 ){///如果是odd就执行
            if( w == 1 ) r = "2";
            else{
                r = "2(" +f(w) + ")";
            }

            if( s == "" ) t =="";
            else t = "+";

            s = r + t +s;
        }
        //cout << s << endl;
        //cout << w<<' ' << x <<endl;
    }
    while(w++,x /= 2);  ///直到x==0才停止

    return s;
}

int main()
{
    cin >> n;
    cout << f(n) <<endl;
    return 0;
}

2____Z字形扫描 ( 模拟蛇形矩阵 )

3____蛇形矩阵（各种版本的）

AcWing寒假提高

1____AcWing 1402. 星空之夜

Flood Fill算法——见板子