刷题

title: 补题
date: 2020-12-11 00:00:00
updated:
type: "ACM",
comments: 记录比较重要的题目
description:
categories: "ACM"
keywords:
top_img: https://i.loli.net/2021/08/03/kZaRI3WNvuLfyKc.png
mathjax:
katex:
aside:
aplayer:
highlight_shrink:

题解

蓝桥杯准备

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-2_alltop_click~default-1-83419593.pc_search_result_no_baidu_js&utm_term=校门外的数&spm=1018.2118.3001.4449

待补算法:

1____模拟退火

星星还是树

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

#include 
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(最小圆覆盖)

2____字符串

2.1____KMP

Censor—训练赛2015四川省赛

#include 
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 ans;
    stack 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 an;
    while( !ans.empty() ){
        an.push_back( ans.top() );
        ans.pop();
    }

    for(int i = an.size() - 1; i >= 0 ; i--){
        cout << an[i] ;
    }
    cout <> p + 1 >> s + 1 ){
        n = strlen( p + 1 );
        m = strlen( s + 1 );
        memset(ne,0,sizeof ne);
        get_next();
        KMP();
    }

    return 0;
}

剪花布条

#include 
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 <> s + 1){
        if( s[1] == '#' ) break;
        cin >> p + 1;
        n = strlen( p + 1 );
        m = strlen( s + 1 );
        get_next();
        KMP();

    }

}

Number Sequence

#include 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 < 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做法

#include 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 <
STL做法 #include 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 < 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]。 #include 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] <> 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 #include 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 < Censor /** stack做法 **/ #include 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 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 */ 剪花布条 #include 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 < Seek the Name, Seek the Fame #include #include #include 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< 2.4____ 扩展KMP （_待补） Prefixes and Suffixes [Clairewd’s message](Clairewd's message - HDU 4300 - Virtual Judge (vjudge.net)) #include 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 的情况 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 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 2.5____回文Manacher 3188. manacher算法 - AcWing题库 #include 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 < 字典树（_待补）Problem - M - Codeforces (Unofficial mirror site, accelerated for Chinese users) （_待补）I love counting - HDU 6964 - Virtual Judge (vjudge.net) 3____计算几何上次cf刷到的位置Problemset - Codeforces) （_待补）Triangle （_待补）Naive and Silly Muggles 3.1____叉积判断点线关系 TOYS #include #include #include #include #include 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] < Segments #include #include #include #include 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 << " | " < 3.2____多边形重心 Lifting the Stone #include 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); /// } ///长度的平方 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 -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____极角排序思路：事先将两个点连成线，然后用叉积来判断第三个点在这个线的左边还是右边， #include #include #include #include #include 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 < 3.4____计算几何，思维题 An Easy Problem?! #include #include #include #include #include #include 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); /// } ///长度的平方 double len2(){ return x * x + y * y; } ///返回两点的距离 double distance(Point p){ return hypot( x - p.x , y - p.y ); } }; struct Line { vector 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' < Kadj Squares #include #include #include #include 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 = mr ) continue; else cout << i + 1 << ' '; } cout << endl; } return 0; } [Nezzar and Nice Beatmap](Problem - 1477C - Codeforces) 题意：在平面上按序给定 $n$ 个点，问能不能将这些点重新排序，使任意三个相邻的点形成的角都是锐角，若能就输出新的序列，不能输出$-1$。 #include 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 < 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。） #include 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< 3.5____线段与多边形判断相交 Intersection #include #include #include #include #include #include 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); /// } ///长度的平方 double len2(){ return x * x + y * y; } ///返回两点的距离 double distance(Point p){ return hypot( x - p.x , y - p.y ); } }; struct Line { vector 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' < 3.6____计算凸包，周长 Surround the Trees #include #include #include #include #include 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); /// } ///长度的平方 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 3.7____平面几何 Keiichi Tsuchiya the Drift King 2018焦作——ICPC #include 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 #include 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 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沈阳 #include #include #include #include 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)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=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; jo.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 3.10 三角形 [Mahmoud and a Triangle](Problem - 766B - Codeforces) 题意: 给你n个线段长度，是否可以中找出3个线段组成三角形 (1e5) 先sort一下，我们知道三角形判断有 $|a-b |< c < |a+b|$ 这里只需要判断短的两个边是不是大于长的那个边就好了，sort了之后相邻的3个边，一定满足最长的大于最短的两个的绝对值之差 #include 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" < [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轴的边就可以了 #include 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" < 4____组合数 Close Tuples (hard version) 5____三分 The Moving Points ? 那模拟退火写的... ? 几个需要注意的点时间的最大范围题目没有给，要开到1e8 delta设置太大的话会超时 $ 1996 ms $ 对应的是 $delte = 0.98$ （最大的时间是3s） $ 826 ms $ 对应的是 $delte = 0.95$ $ 405 ms $ 对应的是 $delte = 0.90$ #include #include #include #include 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 #include 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)); } Defuse the Bombs 题意：有 n 个炸弹要爆炸 $$a_i$$ 表示的是第 $$i$$ 个炸弹的时间，每一秒可以使一个炸弹的爆炸时间向后延长一秒，问第一个爆炸的炸弹的最晚时间是多少题解：正解二分，但是我这里不讲二分，我是直接推的公式，最开始我没看到 $$1e9$$ 的数据，我就直接一秒秒的算，肯定就是 $$O(max( \sum_{i=1}^{n}a_i \times t ))$$ 最长可以卡你 $$1e11$$ 的时间复杂度，之后我就顺其自然的想到 $$O(n \times t)$$ 的算法，我不一秒一秒的处理，我一个数一个数的处理。对于 15 10 7 10 10 这个数据，我们排序后，得到7 10 10 10 15 这个数据，我们输入数据后，做一个统计，一个数出现了多少次，用一个 pair 来存。我们定义一个时间 time=0 把第一个数 $$+3$$ ，那么time 也要 $$+3$$? ，就变成了这样我们再定义几个值，方便讨论cnt,tag,now ，$$cnt$$??? 表示我们之前和现在正在处理的数有多少个，比如现在我们要处理 $$10$$??? 这个数，cnt=4（之后，我们会发现，每处理一个数，如果time还没到的话，就会形成一个新的平面），$$tag$$? 表示比现在处理的数下一位数，对于$$10$$? 就是$$15$$? ，$$now$$?就表示当作正在处理的数。如果整个$$10$$?整个平面都要变为 $$15$$? 需要的时间就表示为 $$cnt \times (tag-now)$$? ，如果满足 $$time + cnt * (tag-now) < tag$$ 那就说明这个平面可以升到下一个平面，我们就继续下去，如果不满足，或者说到了处理最后一个数了，就要输出了。我们现在想要的是，找到$$time$$ 何时和$$now$$ 能属于同一平面，这个时候直接设一个，一元一次方程$$time + cnt * t - (now + t) = 0$$ 在这个式子中，只有 $$t$$?? 为未知量，同时因为是向下取整，我们还要补上舍弃的数，最好自己算一下这个过程。最后是代码： /** * Author : Hoppz * Date : 2021-10-31-13.30.27 */ #include using namespace std; typedef long long ll; typedef pair pir; const double pi = acos(-1); const ll inf = (long long)1e18; const int N = 1e5+10; void solve() { int n,m; cin >> n; map mp; vector vec; for(int i = 0 ; i < n ; i++){ int te; cin >>te; mp[te]++; } /// 这之前都是统计这个数，出现了多少次 for(auto it: mp){ vec.push_back( {it.first,it.second} ); } ll time = 0,cnt=0; for(int i = 0 ; i < vec.size() ; i++){ int now = vec[i].first,tag = vec[i+1].first; cnt += vec[i].second; if( time + cnt*(tag-now) > tag || i == vec.size() - 1 ){ ll te = (now-time)/(cnt-1); time += te*(cnt); time += now + te - time + 1; cout <> t; for(int i = 1; i <= t; i++){ cout << "Case #"< 6____并查集（_待补）Prefix Enlightenment ( 带权并查集 ) （_待补）Rank of Tetris - HDU 1811（拓扑排序+并查集） 7____悬线法（最大子矩阵）（_待补）Largest Common Submatrix （_待补）棋盘制作（_待补）玉蟾宫 BZOJ[3039] 8____线段树单点更新敌兵布阵 #include 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 "<> 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) < I Hate it #include 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 <> 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] < 最大数 #include 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 < 第八大奇迹 (3条消息) 19蓝桥国赛B组C/C++ I第八大奇迹_cy41的博客-CSDN博客 #include 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; } 我的代码（超时，效果没有问题） #include 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].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 < 区间更新一个简单的整数问题2 #include #include 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 离散+线段树【贴海报】 #include #include #include #include #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 > a(n); vector 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 < se; for(int i = 1 ; i <= len ; i++ ){ int te = getTpye(1,i); se.insert( te ); } se.erase(0); cout < Can you answer these queries? #include 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++ <<':' <> 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) < A Simple Problem with Integers - POJ 3468 Balanced Lineup #include #include #include #include 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 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 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 te = Query(1,x,y); cout << (int)(te.first - te.second) << endl; } return 0; } （_待补）扫描线 245. 你能回答这些问题吗 - AcWing题库 #include 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 << ' '<> 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 < #6278. 数列分块入门 2 #include #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 < Fast Matrix Operations - UVA 11992 开20颗线段树，维护矩阵最值题意： ? 给你一个矩阵，对矩阵可以有3个操作，一个子矩阵所有值都加上 x ，一个子矩阵的所有值都变为 x，查询一个子矩阵的和，最大值，最小值。题解： ? 虽然操作都是板子操作，但是在矩阵上进行操作，但是好在矩阵的 $$row$$ 比较小，最大只有 $$20$$ 所以，我们直接开 $$20$$ 颗线段树来操作就好了，重点在很多的细节上，比如要先处理覆盖操作，再处理加操作，覆盖操作之后要把加的lazy标记变为0，然后是多组测试，其他都很板子了 #include #define L (T[id][rt].l) #define R (T[id][rt].r) #define ls (rt<<1) #define rs (rt<<1|1) #define Mid (T[id][rt].l + T[id][rt].r >> 1) using namespace std; const int N = 4e5+7; int r,c,m; struct Node { int l,r; int sum,ma,mi,lazyAdd,lazySet; }T[22][N*4]; void push_up(int id,int rt) { T[id][rt].sum = T[id][ls].sum + T[id][rs].sum; T[id][rt].ma = T[id][ls].ma>T[id][rs].ma?T[id][ls].ma:T[id][rs].ma; T[id][rt].mi = T[id][ls].mi= R ){ T[id][rt].lazySet = val; T[id][rt].sum = val * (R-L+1); T[id][rt].ma = val; T[id][rt].mi = val; T[id][rt].lazyAdd = 0; return ; } push_down(id,rt); if( l <= Mid ) updateSet(id,ls,l,r,val); if( r > Mid ) updateSet(id,rs,l,r,val); push_up(id,rt); } void updateAdd(int id,int rt,int l,int r,int val) { if( l <= L && r >= R ){ T[id][rt].lazyAdd += val; T[id][rt].sum += (R-L+1)*val; T[id][rt].ma += val; T[id][rt].mi += val; return ; } push_down(id,rt); if(l <= Mid) updateAdd(id,ls,l,r,val); if(r > Mid) updateAdd(id,rs,l,r,val); push_up(id,rt); } Node query(int id,int rt,int l,int r) { if( l <= L && r >= R ){ // cout << T[id][rt].sum << " "<< T[id][rt].ma << " " << T[id][rt].mi << endl; return T[id][rt]; } Node l_son,r_son,son; push_down(id,rt); if( l <= Mid && r > Mid ){ l_son = query(id,ls,l,r); r_son = query(id,rs,l,r); son.sum = l_son.sum + r_son.sum; son.ma = l_son.ma>r_son.ma?l_son.ma:r_son.ma; son.mi = l_son.mi Mid ){ son = query(id,rs,l,r); } push_up(id,rt); return son; } void solve() { for(int i = 0 ; i <= r ; i++) build(i,1,1,c+1); for(int i = 0 ; i < m ;i++){ int op,x,y,z,a,b; cin >> op >> x >> a >> y >> b; if( op == 1 ){ cin >> z; for(int i = x ; i <= y ; i++){ updateAdd(i,1,a,b,z); } } else if( op == 2 ){ cin >> z; for(int i = x ; i <= y ; i++){ updateSet(i,1,a,b,z); } } else { Node te={0,0,0,0,0x3f3f3f3f,0,0}; for(int i = x; i <= y ; i++){ Node res = query(i,1,a,b); te.sum += res.sum; te.ma = te.ma>res.ma?te.ma:res.ma; te.mi = te.mi> r >> c >> m){ memset(T,0,sizeof T); solve(); } return 0; } /* 4 4 8 1 1 2 4 4 5 1 1 1 3 4 2 3 1 1 3 4 4 4 8 1 1 2 4 4 5 3 2 1 4 4 1 1 1 3 4 2 3 1 2 4 4 3 1 1 3 4 4 4 8 1 1 1 2 2 4 3 1 1 2 2 */ （_待补）线段树优化数论 Codeforces1549D Integers Have Friends (思维线段树) （_待补）线段树优化DP E-Phone Network_2020ICPC·小米网络选拔赛第一场 (nowcoder.com) 最大子段和（_待补）Tunnel Warfare ls左，ls右+rs左，rs右（_待补）P4513 小白逛公园 - 洛谷 | Can you answer these queries I - SPOJ GSS1 #include #define L (T[rt].l) #define R ( T[rt].r ) #define ls ( rt << 1 ) #define rs ( rt << 1|1 ) #define Mid ( T[rt].l + T[rt].r >> 1 ) #define maxl max( T[ls].lmax,T[ls].sum + T[rs].lmax ) #define maxr max( T[rs].rmax,T[rs].sum + T[ls].rmax ) using namespace std; typedef long long ll; int n,m; const int N = 5e4+10; struct Node { ll l,r; ll lmax,rmax; /// 区间左（右）端点开始的最大子段和 ll sum; /// 区间和 ll ma; /// 区间最大子段和 Node():l(0),r(0),lmax(0),rmax(0),sum(0),ma(0){} }T[N<<2]; /// 区间子段和有6种 ll a[N]; void push_up(ll rt) { T[rt].lmax = maxl; T[rt].rmax = maxr; T[rt].sum = T[ls].sum + T[rs].sum; T[rt].ma = max({ T[rt].lmax , T[rt].rmax ,T[ls].ma,T[rs].ma ,T[rt].sum,T[ls].rmax + T[rs].lmax }); } void build(ll rt,ll l,ll r) { L = l , R = r; if( l == r ){ T[rt].lmax = T[rt].rmax = T[rt].sum = T[rt].ma = a[l]; return ; } build( ls,l,Mid ), build(rs,Mid+1,r); push_up(rt); } Node query(ll rt,ll l,ll r) { if( l <= L && r >= R)return T[rt]; if(r <= Mid ) return query(ls,l,r); else if( l > Mid ) return query(rs,l,r); else{ Node no,lno = query(ls,l,r),rno = query(rs,l,r); no.lmax = max( lno.lmax,lno.sum + rno.lmax ); no.rmax = max( rno.rmax,rno.sum + lno.rmax ); no.sum = lno.sum + rno.sum; no.ma = max({ no.lmax , no.rmax , lno.ma , rno.ma ,no.sum , rno.lmax + lno.rmax }); return no; } } int main() { scanf("%d",&n); for(int i = 1; i <= n ; i++){ scanf("%lld",&a[i]); } build(1,1,n); scanf("%d",&m); for(int i = 0 ; i < m ; i++){ ll tea,teb; scanf("%lld%lld",&tea,&teb); Node ans = query(1,tea,teb); printf("%lld\n",ans.ma); } return 0; } （_待补）Can you answer these queries II - SPOJ GSS2 （_待补）E - Snowy Smile HDU - 6638 （线段树维护最大连续子段和）（_待补）Journey among Railway Stations_2021牛客暑期多校训练营1 (33条消息) 2021牛客多校1——J：Journey of Railway Stations（线段树）_kunyuwan的博客-CSDN博客（_待补）E-Tree Xor_2021牛客暑期多校训练营4 (nowcoder.com) (33条消息) 2021牛客暑期多校训练营4 E.Tree Xor(区间异或+扫描线)_jziwjxjd的博客-CSDN博客（_待补） H-Hopping Rabbit_2021牛客暑期多校训练营6 (nowcoder.com) （_待补）B-xay loves monotonicity_2021牛客暑期多校训练营7 (nowcoder.com) （_待补）F-xay loves trees_2021牛客暑期多校训练营7 (nowcoder.com) （_待补）E-Eyjafjalla_2021牛客暑期多校训练营9 (nowcoder.com) 线段树+二分（_待补）[codeforces1065C]Make It Equal 区间开方带修改的区间开方，HDU 5828——Rikka with Sequence 牛客上面有个板子题和这个一样，只不过不是多组，那个用的势能线段树，但是这个不用这个东西，只需要用一个 tag 来表示，这一段数是否相等就可以了，他势能也是用的这个原理，但是势能表示的话，比现在这个 tag 更复杂，还有一个选哟注意的是，在相同的数，区间，要把 lazy 减了，我开始一直没注意这个问题。其他 G. Performance Review 数据结构_jkchen's Haven-CSDN博客 9____可持续化线段树（主席树） 9.1、神秘数 [牛牛的凑数游戏]——区间mex，最小未出现的数 ? 此版本主席树为不打地基的主席树，没有build操作，同时也不用push_up，插入的坐标是权值，build的话开不了这么大的空间 #include #define Mid ( (L+R) >>1) using namespace std; const int inf =0x3f3f3f3f; const long long INF = (long long)1e18; const int N = 1e5+10; typedef long long ll; struct Node { ll l,r; ll sum; }T[N<<5]; ll a[N],root[N],tot; ll insert(ll pre,ll now,ll L,ll R,ll val) { now = ++ tot; // cout << L << ' ' << R << endl; T[now] = T[pre]; T[now].sum += val; if( L == R) return now; if( val <= Mid ) T[now].l = insert( T[pre].l , T[now].l,L,Mid,val ); else T[now].r = insert( T[pre].r , T[now].l,Mid+1,R,val ); return now; } ll query(ll pre,ll now,ll L,ll R,ll l,ll r) { // cout << L<<' ' <= R){ return T[now].sum - T[pre].sum; } ll ans = 0; if( l <= Mid ) ans += query(T[pre].l , T[now].l , L , Mid ,l , r) ; if( r > Mid ) ans += query( T[pre].r , T[now].r,Mid+1,R,l,r ); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,m; cin >> n >> m; for(ll i = 1; i <= n ; i++) cin >> a[i]; for(ll i = 1; i <= n ; i++){ root[i] = insert(root[i-1],root[i],1,inf,a[i]); } for(ll i = 1; i <= m ; i++){ ll l,r; cin >> l >> r; ll ans = 1 ; while(1){ ll res = query(root[l-1],root[r],1,inf,1,ans); if( res >= ans ) ans = res + 1; else break; } cout << ans < 9.2、HH的项链——区间去重后数的数量 9.2.1、主席树做法对于一个数组a 1 2 3 4 1 2 3 1 2 3 ，我们记另一个数组b来表示这个数上一次出现的位置，如果没有出现过则记为0 0 0 0 0 1 2 3 5 6 7 ，对于区间 [l,r] 的出现数的个数，我们直接取 b 的 cnt 存为权值线段树，每次求 $$[0,l-1]$$ 的和，就是我们想要的答案 /** * Author : Hoppz * Date : 2021-11-04-11.17.17 */ #include #define ls (T[rt].l) #define rs (T[rt].r) #define Mid ( (l+r) >> 1 ) using namespace std; typedef long long ll; typedef pair pir; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const int N = 1e5+10; struct Node { int l,r; int cnt; }T[N<<5]; int tot ,a[N],root[N]; int insert(int pre,int now,int l,int r,int val) { now = ++tot; T[now] = T[pre]; T[now].cnt++; if( l == r ) return now; int mid = l + r >> 1; if( val <= mid) T[now].l = insert( T[pre].l,T[now].l,l,mid,val ); else T[now].r = insert( T[pre].r , T[now].r ,mid + 1, r, val); return now; } int query(int pre,int now,int L,int R,int l,int r) { if( l <= L && r >= R ){ return T[now].cnt - T[pre].cnt; } int son = 0,mid = L+R>>1; if( l <= mid ) son += query( T[pre].l , T[now].l, L,mid,l,r ); if( r > mid ) son += query( T[pre].r , T[now].r , mid +1 ,R,l,r ); return son; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,m; cin >> n ; map mp; for(int i = 1; i <= n ; i++){cin >> a[i]; root[i] = insert( root[i-1],root[i], 0,inf,mp[a[i]] ); mp[ a[i] ] = i; } cin >> m; for(int i = 1 ; i <= m ; i++){ int l,r; cin >> l >> r; cout << query( root[l-1],root[r], 0,inf,0,l-1 ) << endl; } return 0; } 9.2.2、离线+BIT #include #define lowbit(x) ((x)&(-x)) using namespace std; const int N = 1e6+10; struct Node { int l,r; int id; bool operator < (Node b){ return r < b.r; } }q[N]; int a[N],ans[N],st[N],n,t[N]; void add(int x,int val) { while(x <= n ){ t[x] += val; x += lowbit(x); } } int query(int x) { int ans = 0; while(x!=0){ ans += t[x]; x -= lowbit(x); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n ;i++)cin >> a[i]; int m; cin >> m; for(int i = 1; i <= m ; i++) {cin >> q[i].l >> q[i].r;q[i].id = i;} sort(q+1,q+1+m); int next = 1; for(int i = 1; i <= m ; i++){ for(int j = next; j <= q[i].r ; j++){ /// 之前出现过的，就减掉 if( st[ a[j] ] ) add(st[a[j] ],-1 ); add(j,1); st[a[j] ] = j; } next = q[i].r + 1; ans[ q[i].id ] = query( q[i].r ) - query( q[i].l-1 ); } for(int i = 1 ; i <= m ; i++){ cout << ans[i] < 9.3、Turing Tree - HDU 3333) 区间去重后数的大小 9.4、P1168 中位数 /** * Author : Hoppz * Date : 2021-11-16-09.38.23 */ #include using namespace std; typedef long long ll; typedef pair pir; const double pi = acos(-1); const ll INf = (long long)1e18; const int inf = 0x3f3f3f3f; const int N = 1e5+10; int a[N],root[N],tot; struct Node { int lson,rson; int cnt; }T[N<<5]; int insert(int pre,int now,int l,int r,int val) { now = ++tot; T[now] = T[pre]; T[now].cnt++; if( l == r ) return now; int mid = l+r>>1; if( val <= mid ) T[now].lson = insert( T[pre].lson , T[now].lson ,l,mid,val ); else T[now].rson = insert( T[pre].rson , T[now].rson ,mid+1,r,val); return now; } int query(int now,int L,int R,int val) { if( L == R ) return L; int mid = L+R>>1,cnt = T[ T[now].lson ].cnt; //cout <> n; for(int i = 1 ; i <= n ; i++){ cin >> a[i]; } for(int i = 1 ; i <= n ; i++){ root[i] = insert(root[i-1],root[i],0,inf,a[i]); } for(int i = 1; i <= (n+1)/2 ; i++ ){ int loc = 2*i-1; cout << query(root[loc],0,inf,i) << endl; } return 0; } 9.5、Performance Review(可持久化线段树) 权值线段树 9.4、 _Find the answer #include 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; } 9.4、#6062. 「2017 山东一轮集训 Day2」Pair - 题目队赛的时候我找的一套题中的一个，计蒜客上的数据有问题，可以在Uva上交，然后这个题和那个是一模一样的，所以我直接补的这个题。开始我还说用离散化+权值线段树，看懂题解后，太巧妙了。题意：给出一个长度为 $$n$$? 的数列和一个长度为 $$m$$ 的数列，求 $${ a_i }$$ 有多少个长度为 $$m$$ 的连续子数列能与 $${ b_i }$$ 匹配。两个数列可以匹配，当且仅当存在一种方案，使两个数列中的数可以两两配对，两个数可以配对当且仅当它们的和不小于 $$h$$?。题解：这个题的思路是线段树+尺取（奇怪的组合增加了!）我们只对 $${ b_i }$$? 建树维护区间最小值，就是那个匹配的数组，我们在建树的时候，把 $$mi$$? 设置为 $${ -i,-i+1,... , -1 }$$? 这样的序列，比如说 m == 5 那么建出来的树为 $${ -5,-4,-3,-2,-1 }$$ 。对于 $${ b_i }$$ ，我们可以 sort 一遍，方便后面二分，然后就是尺取了，我们先对前 m 个数做一下预处理（后面的尺取和这个思路是一样的），我们对于 $$a_i$$ 在 $${ b_i }$$ 上二分，对于小于等于这个 $$a_i$$ 的区间，我们都在线段树上+1 这样的话，表示为这个数，可以和小于等于他的区间进行匹配（这样我们把等式 $$ a_i + b_i >= h $$ 变换为 $$ b_i >= h - a_i $$ 了），如果最后区间的最小值大于 0 的话，就表示这个区间是可取的，那么 cnt++ ，在之前的尺取中对新增的那个数也是一样的操作，对面前面舍弃的那个数，我们直接把他所能进行匹配的区间都-1状态就转移过去了。线段树yyds! #include #define L (T[rt].l) #define R (T[rt].r) #define ls (rt<<1) #define rs (rt<<1|1) #define Mid (T[rt].l + T[rt].r >> 1) using namespace std; const int N = 2e5 + 10; struct Node { int l,r; int mi,lazy; }T[N<<2]; int a[N],b[N]; int n,m,k; void push_up(int rt) { T[rt].mi = T[ls].mi < T[rs].mi ? T[ls].mi : T[rs].mi; } void push_down(int rt) { if( T[rt].lazy != 0 ){ T[ls].mi += T[rt].lazy; T[rs].mi += T[rt].lazy; T[rs].lazy += T[rt].lazy; T[ls].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].mi = -l; return ; } build(ls,l,Mid);build(rs,Mid+1,r); push_up(rt); } void update(int rt,int l,int r,int val) { if( l <= L && r >= R ){ T[rt].mi += val; T[rt].lazy += val; return ; } push_down(rt); if( l <= Mid ) update(ls,l,r,val); if( r > Mid ) update(rs,l,r,val); push_up(rt); } void solve() { cin >> n >> m >> k; for(int i = 1 ; i <= m ; i++) cin >> b[i]; for(int i = 1 ; i <= n ; i++) cin >> a[i]; sort(b+1,b+m+1); build(1,1,m); int cnt = 0; /// 对前 m 个数进行预处理 for(int i = 1; i <= m ; i++){ int p = lower_bound(b+1,b+m+1,k-a[i]) -b; if( p <= m ) update(1,p,m,1); if( T[1].mi >= 0 ) cnt++; } /// 对后面的数，进行尺取 for(int i = m + 1; i <= n ;i++){ int p = lower_bound(b+1,b+1+m, k-a[i]) -b; if( p <= m ) update(1,p,m,1); /// 把上一个数的状态恢复过去 p = lower_bound(b+1,b+1+m, k-a[i-m]) -b; if( p <= m ) update(1,p,m,-1); if( T[1].mi >= 0 ) cnt++; } cout << cnt << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; } 10____可持续化字典树 11____Tire树 Phone List(wa) #include #include #include #include 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" < 统计难题 #include 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] << ' ' < 最大异或对 #include 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 < 12_DP 902. 最短编辑距离 #include 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 < 传球游戏滑雪 13_搜索 (4条消息) BFS广搜题目【经典训练题】_reverie_mjp的博客-CSDN博客 [(4条消息) kuangbin带你飞]专题一做题顺序与题解【简单搜索】_指弹键盘哼民谣-CSDN博客_kuangbin带你飞做题顺序 **I-Penguins_2021牛客暑期多校训练营2 ** DFS路径输出 #include using namespace std; char s[30][50]; ///读入的地图 pair< pair,pair > lst[21][21][21][21]; queue< pair< pair,pair > > 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 > 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 < （待补）POJ1175___Starry Night 八数码_A* #include #include #include #include #include #include #include #include using namespace std; string sta,seq; string en = "12345678x"; map dist; ///判重 map > cost; ///路径记录 priority_queue ,vector >,greater > > 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 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" <> 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; } （_待补）uva 1326 Jurassic Remains(中途相遇法) （_待补）F-24dian_2021牛客暑期多校训练营3 (nowcoder.com) （_待补）F-Train Wreck_2021牛客暑期多校训练营10 (nowcoder.com) Codeforces Round #751 (Div. 2)D. Frog Traveler #include #define me(x,y) memset(x,y,sizeof x) using namespace std; const int N = 3e5+01; int a[N],b[N],pre[N],dis[N],ans[N]; int ma,n; int bfs() { queue q; ma = n; /// mi 表示当前能跳到的最远位置 me(pre,-1);me(dis,0x3f);me(ans,0); q.push(n); dis[n] = 0; /// dis记录到这个位置要多少步 while(!q.empty()){ auto no = q.front();q.pop();; if( no == 0 ) return dis[no]; /// 达到终点 for(int x = a[no] ; no > 0 ; x--){ /// 可以从这个点跳到 (0-a[i]) 从最远处开始枚举 int te = no - x,temp = 0; /// te表示跳到的新位置 if(te >= ma ) break; /// ? if( te > 0 ) temp = te , te = te + b[no-x]; /// te 变为下滑的位置 else te = 0; cout << "* "<< no << " " << te << " " << dis[te] < dis[no] + 1 ){ cout << "# " << no << " " << temp <> n; for(int i = 1 ; i <= n ; i++) cin >> a[i]; for(int i = 1 ; i <= n ; i++) cin >> b[i]; cout << bfs() << endl; stack sta; int x=0; while(pre[x] != -1){ sta.push(x); x=pre[x]; } while(!sta.empty()){ int no = sta.top(); cout << ans[no] << " "; sta.pop(); } cout << endl; return 0; } /* 10 0 1 2 3 5 5 6 7 8 5 9 8 7 1 5 4 3 2 0 0 */ Luggage Lock 预处理题意给你2个4位 0~9 的字符串（一个锁环），问你第一个字符串变换为第二个，需要多少步。可进行的操作是转动1个数字（可正向，可反向），可以转动（同一方向）相连的2,3,4个数字，这些都视为一次操作。题解可dp，可 bfs 预处理打表，其实 bfs 就是 dp，这里我说下 bfs 预处理的做法，其实任意的一个状态，转移到另一个状态都可以视为是从 0000 开始，转到一个对应的位置。比如 1234 转换到 3401 可以视为 0000转换到 2277 ，所以我们跑一边 0000 到其他所有的状态，就ok了 #include using namespace std; string s[10] = { "1000","0100","0010","0001", "1100","0110","0011", "1110","0111","1111"}; int st[10][4] = {-1,0,0,0,0,-1,0,0,0,0,0,-1, -1,-1,0,0,0,-1,-1,0,0,0,-1,-1, -1,-1,-1,0,0,-1,-1,-1,-1,-1,-1,-1}; unordered_map mp; void bfs() { queue q; q.push("0000"); mp["0000"] = 0; int cnt = 0; while( !q.empty() ){ auto no = q.front(); //cout << no << endl; q.pop(); /// 正 for(int i = 0 ; i < 10 ; i++){ string te = ""; te += s[i][0]+no[0]-'0'; te += s[i][1]+no[1]-'0'; te += s[i][2]+no[2]-'0'; te += s[i][3]+no[3]-'0'; for(int i = 0 ; i < 4; i ++) if( te[i] > '9' ) te[i] = '0'; if( !mp.count( te ) ){ mp[te] = mp[no] + 1; q.push(te); } } /// 负 for(int i = 0 ; i < 10; i++){ string te =""; te += st[i][0]+no[0]; te += st[i][1]+no[1]; te += st[i][2]+no[2]; te += st[i][3]+no[3]; for(int i = 0 ; i < 4; i++) if( te[i] < '0' ) te[i] = '9'; if( !mp.count(te) ){ mp[te] = mp[no]+1; q.push(te); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >>t; bfs(); while(t--){ string s1,s2; cin >>s1 >>s2; string te = ""; for(int i =0 ; i < 4; i++){ if( s2[i] >= s1[i] )te += char(abs(s1[i]-s2[i] )+'0'); else te += char('9'+1-abs(s1[i]-s2[i] )); } cout < 14____数列分块 14.1____数列分块1（区间加法，单点查询）题解： ? 这个题就是数列分块的板子题，对区间做区间修改，单点查询，区间修改为区间加法，线段树同样可以做，但是代码就很复杂了，我们用 tag 来维护分块区间的相同和 ? 在update的时候，如果在同一区间内，那么我们直接 $O(n)$???解决，如果不在的话，那么位于左端和右端的区间，我们都直接 $O(n)$??? 处理，在中间的区间，我们直接同一加到 tag 上，这 tag 数组有点像线段树的 lazy标记，但是不会 push_down，查询的时候，我们直接叠加上去就可以了。 #include 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 #include using namespace std; const int N = 5e5 + 10; int a[N],len,id[N],tag[N],vec[N]; /// id * len 当前块最后一个元素 /// (id - 1) * len + 1 当前块的第一个元素 /// 注意lower_bound 是左闭右开（取不到第二个值） /// 开区间使用符号小括号()表示，闭区间使用符号中括号[]表示 void reset(int tes,int tee) /// x为所在分块的编号 { for(int i = tes ; i <= tee ; i++) vec[i] = a[i]; sort(vec + tes,vec + tee + 1); } void update(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; reset( (sid - 1)*len +1 ,sid *len ); return ; } /// for(int i = l; id[i] == sid ; i++) a[i] += c; reset( (sid - 1)*len +1 ,sid *len ); for(int i = sid + 1 ; i < eid ; i++) tag[i] += c; for(int i = r ; id[i] == eid ; i--) a[i] += c; reset( (eid - 1)*len +1 ,eid *len ); } int query(int l,int r,int x) { int sid = id[l], eid = id[r] , cnt = 0; if( sid == eid){ for(int i = l ; i <= r; i++) if( a[i] + tag[ id[i] ] < x ) cnt++; return cnt; } /// int te = sid * len ; for(int i = l ; i <= te ; i++) if( a[i] + tag[ sid ] < x ) cnt ++; for(int i = sid + 1; i < eid ; i++){ int tes = (i - 1)*len + 1, tee = i *len; cnt += int( lower_bound( vec + tes , vec + tee + 1, x - tag[i]) - vec - tes ); } te = (eid - 1) * len + 1; for(int i = te ; i <= r; i++) if( a[i] + tag[ eid ] < x ) cnt++; return cnt; } 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; } for(int i = 1 ; i <= id[n] ; i++ ){ reset((i - 1)*len + 1, i * len); /// 注意如果是最后一个分块，要单独弄 if (i == id[n]) { reset((i - 1)*len + 1, n); } } for(int i = 0; i < n ; i++){ int op,x,y,z; cin >> op >> x >> y >> z; if( op == 0 ){ update(x,y,z); }else{ cout << query(x,y,z*z) < 线段树 #include #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 << "--"<> 1) #define L (T[rt].l) #define R (T[rt].r) #define INF (-1)*0x3f3f3f3f3f using namespace std; void file() { #ifdef ONLINE_JUDGE #else freopen( "d:/workProgram/test.in","r",stdin ); #endif } typedef long long ll; const ll N = 1e5 + 10; struct Node { ll l,r; ll ma,mi,lazy; }T[N << 2]; ll a[N],ans; /// ans = -1*(0x3f3f3f3f); void push_up(ll rt) { T[rt].ma = max( T[ls].ma , T[rs].ma ); T[rt].mi = min( T[ls].mi , T[rs].mi ); } void push_down(ll rt) { if( T[rt].lazy != 0 ){ 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[ls].lazy += T[rt].lazy; T[rs].lazy += T[rt].lazy; T[rt].lazy = 0; } } void build(ll rt,ll l,ll r) { T[rt] = {l,r,0,0,0}; if(l == r){ T[rt].ma = T[rt].mi = a[l]; //cout << "LL:" << l << "a:" << a[l] <= R ){ T[rt].ma += val; T[rt].mi += val; T[rt].lazy += val; return ; } push_down(rt); if( l <= Mid )update(ls,l,r,val); if( r > Mid) update(rs,l,r,val); push_up(rt); } void query(ll rt,ll l,ll r,ll val) { if( T[rt].mi > val || T[rt].ma < ans) return ; if( l <= L && r >= R && T[rt].ma < val ){ ans = max( ans , T[rt].ma); return ; } if( l <= L && r >= R && L == R && T[rt].ma >= val ) return ; if( R < l || L > r || L == R) return ; //cout<< "l:" << L << "R:" << R << "ma:" << T[rt].ma <= Mid ) query(rs,l,r,val); push_up(rt); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //file(); ll 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,x,y,z; cin >> op >> x >> y >> z; if( op == 0 ){ update(1,x,y,z); }else{ ans = INF; query(1,x,y,z); //cout << "ans:" << ans << endl; if( ans == INF ){ cout << -1 < 14.4____数列分块4 题意：给你一个数组，区间加，求区间和，输出要Mod 题解：板子题，放的是之前的代码 #include using namespace std; typedef long long ll; const int N = 5e4 + 10; ll id[N], len; /// id为记录每个元素的分块编号 ll a[N]; /// 原数组 ll b[N]; /// ll s[N]; /// 维护分块的区间和 void add(int l, int r, ll x) { int sid = id[l], eid = id[r]; if (sid == eid) { /// 在同一分块中 for (int i = l; i <= r ; i++) a[i] += x, s[sid] += x; return ; } /// b代表的是整个区间的lazy 标记？ for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x; /// 前一段 for (int i = sid + 1; i < eid ; i++) b[i] += x, s[i] += len * x; /// 中间的多个分块 for (int i = r ; id[i] == eid ; i--) a[i] += x, s[eid] += x; /// 后一段 } ll query(int l, int r, ll p) { int sid = id[l], eid = id[r]; ll ans = 0; if (sid == eid) { for (int i = l ; i <= r ; i++) ans = (ans + a[i] + b[sid]) % p; return ans; } for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p; for (int i = sid + 1; i < eid ; i++) ans = (ans + s[i]) % p; for (int i = r ; id[i] == eid ; i--) ans = (ans + a[i] + b[eid]) % p; return ans; } 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 = 1; i <= n ; i++) { int op, l, r, c; cin >> op >> l >> r >> c; if (op == 0) { add(l, r, c); } else { cout << query(l, r, c + 1) << endl; } } return 0; } 14.5____数列分块5（区间开方，区间求和）我的自己的做法是，开两个数组来维护，sum[]维护区间和，num[]来维护区间开了几次方 num[]的由来是因为 $$2^{32}$$ 大小的数，最多开7次就到1了，之后就没必要开了，所以在add中，对于一个整块如果 num[i] > 7 || sum[i] <= len 那么我们对这个块就不需要进行操作了 #include using namespace std; const int N = 1e5 + 10; int a[N], sum[N], num[N], id[N], len; void down(int l, int r) { for (int i = l; i <= r; i++) a[i] = sqrt(a[i]); } int get(int l, int r) { int res = 0 ; for (int i = l ; i <= r; i++) res += a[i]; return res; } void update(int l, int r) { int L = id[l], R = id[r]; if (L == R) { for (int i = l ; i <= r; i++) a[i] = sqrt(a[i]); return ; } for (int i = l ; id[i] == L ; i++) a[i] = sqrt(a[i]); for (int i = r ; id[i] == R ; i--) a[i] = sqrt(a[i]); sum[L] = get((L - 1) * len + 1, L * len); sum[R] = get((R - 1) * len + 1, R * len); for (int i = L + 1; i < R; i ++) { if (num[i] > 7 || sum[i] <= len) continue; else { down((i - 1)*len + 1, i * len); num[i]++; sum[i] = get((i - 1) * len + 1, i * len); } } } int query(int l, int r) { int L = id[l], R = id[r], res = 0; if (L == R) { for (int i = l ; i <= r ; i++) res += a[i]; return res; } for (int i = l ; id[i] == L ; i++) res += a[i]; for (int i = r ; id[i] == R ; i--) res += a[i]; for (int i = L + 1; i < R; i ++) res += sum[i]; return res; } 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; sum[ id[i] ] += a[i]; } for (int i = 0 ; i < n ; i++) { int op, x, y, z; cin >> op >> x >> y >> z; if (op == 0) { update(x, y); } else { cout << query(x, y) << "\n"; } } return 0; } 另一个dalao的做法提交记录 #601465 - LibreOJ (loj.ac) #include using namespace std; const int N = 1e5+10, M = 500; int a[N],ma[M],L[M],R[M],id[N],len,sum[M]; inline void update_sum(int l,int r, int k) { for(int i = l ; i <= r; i ++) sum[k] -= a[i], a[i] = sqrt(a[i]),sum[k] += a[i]; } inline void update_max(int k) { ma[k] = sqrt( ma[k] ); for(int i = L[k] ; i <= R[k]; i++) ma[k] = ma[k] > a[i]? ma[k]:a[i]; } inline void update(int l,int r) { if( id[ l ] == id[ r ] ){ if( ma[ id[l] ] <= 1 ) return ; update_sum(l,r,id[l]); update_max(id[l]); return ; } if( ma[ id[l] ] > 1 ) update_sum( l,R[id[l]],id[l] ),update_max( id[l] ); if( ma[ id[r] ] > 1 ) update_sum( L[ id[r] ] , r, id[r] ), update_max( id[r] ); for(int i = id[l] + 1 ; i < id[r] ; i++ ){ if( ma[ i ] > 1 ) update_sum( L[i],R[i],i ),ma[i] = sqrt(ma[i]); } } int query(int l,int r) { int res = 0; if( id[l] == id[r] ){ for(int i = l ; i <= r; i ++) res += a[i]; return res; } for(int i = l ; i <= R[ id[l] ] ; i ++) res += a[i]; for(int i = L[ id[r] ] ; i <= r; i ++) res += a[i]; for(int i = id[ l ] + 1 ; i < id[r] ; i++) res += sum[i]; return res; } 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; sum[ id[i] ] += a[i]; ma[ id[i] ] = ma[ id[i] ] > a[i] ? ma[ id[i] ] : a[i]; } for(int i = 1 ; i <= id[n] ; i++){ L[i] = (i-1)*len+1 , R[i] = min( i*len , n ); } for(int i = 0; i < n ; i++){ int op,x,y,z; cin >> op >> x >> y >>z; if( op == 0 ){ update( x,y ); } else { cout << query( x,y ) < 14.7____数列分块7 题意：给你一个数组，有 3 个操作，区间加，区间乘，单点求值，对输出答案取模题解：最重要的一个就是，要有一个 push_down函数，就和线段树一样，对于零碎的块，因为要单独的乘和加，所以只有把他push_down ，对于完整的块，我们可以由乘法的分配律，来直接乘到 add数组上。做了这个题我才知道，原来取模取多了，时间复杂度会高这么多..... #include using namespace std; const int N = 1e5 + 10,M = 500,Mod = 10007; int a[N],add[N],mul[N],id[N],L[M],R[M],len; void push_down(int k) { if( add[k] ==0 && mul[k] == 1 ) return ; for(int i = L[k] ; i <= R[k]; i++) a[i] = ( a[i] * mul[k] + add[k] )%Mod; add[k] = 0 , mul[k] = 1; } void update_add(int l,int r,int val) { push_down(id[l]);push_down(id[r]); if( id[l] == id[r] ){ for(int i = l ; i <= r; i ++) a[i] = (a[i] + val)%Mod; return ; } for(int i = l ; id[i] == id[l] ; i++) a[i] = (a[i] + val)%Mod; for(int i = r ; id[i] == id[r] ; i--) a[i] = (a[i] + val)%Mod; for(int i = id[l] + 1; i < id[r]; i++) add[i] = ( add[i] + val )%Mod; } void update_mul(int l,int r,int val) { push_down(id[l]);push_down(id[r]); if( id[l] == id[r] ){ for(int i = l ; i <= r; i++) a[i] = (a[i] * val)%Mod; return ; } for(int i = l ; id[i] == id[l] ; i++) a[i] = (a[i] * val)%Mod; for(int i = r ; id[r] == id[i] ; i--) a[i] = (a[i] * val)%Mod; for(int i = id[l] + 1; i < id[r] ; i++) add[i] = ( add[i] * val )%Mod , mul[i] = ( mul[i] * val ) % Mod; } int query(int i) { return ( (a[i] * mul[ id[i] ]) + add[ id[i] ] )%Mod; } 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; } for(int i = 1 ; i <= id[n] ; i++) L[i]=(i-1)*len+1,R[i]=min(i*len,n),mul[i]=1; for(int i = 0 ; i < n ; i++){ int op,x,y,z; cin >> op >> x >> y >> z; if( op == 0 ){ update_add(x,y,z); } else if ( op == 1){ update_mul(x,y,z); } else { cout << query(y) << endl; } } return 0; } （_待补）14.8____2021牛客多校#2 L-WeChat Walk(分组) 15____莫队 15.1、SP3267 DQUERY - D-query #include using namespace std; /* 莫队板子 */ const int N = 1010000; /// 数据范围 int M = 1010; /// 询问次数 int a[N]; /// 输入数组 int cnt[N]; /// 这个数当前出现了多少次 int id[N]; /// 1-n 的编号，对应那个分块 int ans[N]; /// 用于输出答案 int n,m; /// n数的个数，m询问的次数 int no; /// 记录当前的ans值 int block; /// 每一个分块的大小 struct Node { int l,r; /// 存储询问的区间 int id; /// 询问输入的编号 }q[N]; int cmp(Node a,Node b) { if( id[a.l] == id[b.l] ) return a.r < b.r; return id[a.l] < id[b.l]; } void add(int pos) { if( !cnt[a[pos]] ) ++no; /// 之前没有出现过，ans++ ++cnt[a[pos]]; /// 在这个位置的这个数出现的次数 } void del(int pos) { --cnt[ a[pos] ]; if( !cnt[ a[pos] ] ) --no; /// 如果减到0了，那么这个数就没有了，ans-- } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; block = int(sqrt(n)); /// 读入并分块 for(int i = 1; i <= n ; i++){ cin >> a[i]; id[i] = (i - 1) / block + 1; } cin >> m; /// 读入并存储询问 for(int i = 1; i <= m ;i++){ cin >>q[i].l >> q[i].r; q[i].id = i; } /// 对询问进行排序 sort(q+1,q+m+1,cmp); int l=1,r=0; for(int i = 1; i <= m ; i++){ int ql = q[i].l , qr = q[i].r; while(l < ql) del(l++); while(l > ql) add(--l); while(r < qr) add(++r); while(r > qr) del(r--); ans[q[i].id ] =no; } for(int i =1 ; i <= m ; i++){ cout << ans[i] << endl; } return 0; } 15.2、小Z的袜子理解了这个之后就好做了 #include using namespace std; const int N =50010; typedef long long ll; struct Node { ll l,r; ll id; }q[N]; ll id[N],a[N],cnt[N]; ll n,m,no,block; pair ans[N]; bool cmp(Node a,Node b) { if( id[ a.l ] == id[ b.l ] ) return a.r < b.r; return id[ a.l ] < id[ b.l ]; } void add(ll x) { no -= cnt[ a[x] ] * cnt[ a[x] ] ; cnt[a[x]] ++; no += cnt[ a[x] ] * cnt[a[x] ] ; } void del(ll x) { no -= cnt[ a[x] ] * cnt[ a[x] ] ; cnt[a[x]] --; no += cnt[ a[x] ] * cnt[a[x] ] ; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; block = sqrt(n); for(int i = 1 ; i <= n ; i++){ cin >> a[i]; id[i] = ( i - 1 ) / block + 1; } for(int i = 1; i <= m ; i++){ cin >> q[i].l >> q[i].r; q[i].id = i; } sort(q+1,q+1+m, cmp); ll l = 1 , r = 0; for(int i = 1; i <= m ; i++){ ll ql = q[i].l, qr = q[i].r; if( ql == qr ){ ans[ q[i].id ].first = 0,ans[ q[i].id ].second = 1; continue; } while( l < ql ) del(l++); while( l > ql ) add(--l); while( r < qr ) add(++r); while( r > qr ) del(r--); ll top = ( no - qr + ql - 1 ); ll bot = (( qr - ql + 1)*(qr - ql)); ll g = __gcd( top,bot ); ans[ q[i].id ].first = top/g,ans[ q[i].id ].second = bot/g; //cout << q[i].id << ' '<< no << ' ' << top << ' ' << bot < 小B的询问题意求区间内数字出现次数的平方和题解直接稍微计算一下转移公式，加的时候 $$sum += (cnt[a[i]]+1)(cnt[a[i]]+1) - (cnt[a[i]])(cnt[a[i]])$$ ，减的时候 $$ sum -= cnt[i]cnt[i] - (cnt[i]-1)(cnt[i]-1) $$? ，cnt[i] 为 i 这个数出现的次数 #include using namespace std; const int N = 50010; typedef long long ll; struct Node { ll l,r; ll id; }q[N]; ll a[N],cnt[N],id[N],ans[N]; ll block,n,m,no,k; bool cmp(Node a,Node b) { if( id[ a.l ] == id[ b.l ] ) return a.r < b.r; return id[ a.l ] < id[ b.l ] ; } void del(ll x) { no -= cnt[ a[x] ] * cnt[ a[x] ]; cnt[ a[x] ] --; no += cnt[ a[x] ] * cnt[ a[x] ]; } void add(ll x) { no -= cnt[ a[x] ] * cnt[ a[x] ]; cnt[ a[x] ] ++; no += cnt[ a[x] ] * cnt[ a[x] ]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m >> k; block = sqrt(n); for(int i = 1; i <= n ; i++){ cin >> a[i]; id[i] = (i - 1) / block + 1; } for(int i = 1 ; i <= m ; i++){ cin >> q[i].l >> q[i].r; q[i].id = i; } sort(q+1,q+1+m,cmp); ll l = 1,r = 0; for(int i = 1; i <= m ; i++){ int ql = q[i].l ,qr = q[i].r; while( l < ql ) del(l++); while( l > ql ) add(--l); while( r < qr ) add(++r); while( r > qr ) del(r--); ans[ q[i].id ] = no; } for(int i = 1; i <= m ; i++){ cout << ans[i] << endl; } return 0; } Chika and Friendly Pairs (离散化+树状数组+莫队) 题意： ? 给你一个序列 $a$? ，长度为 $n$?，有 $$m$$? 次询问，每次询问在 l~r 中，有多少个数对满足 $$|a_i-a_j| \le k$$?。题解： ? 最开始想得是，直接用线段树，ST表之类的维护，但是怎么算时间复杂度都是 $$O(NNlogN)$$ ，主要的就是要一个点一个点的去算。最后看了别人的题解知道了这个方法。 ? 首先我们来分析 $$|a_i-a_j| \le k$$ 这个不等式，我们将其变形 $$ -k \le a_i - a_j \le k $$ ，再变为 $$ a_j+k \le a_i \le a_j -k $$ 这的话，对于每个新加入莫队的数，我们就只需要查询有多少个数在 $$a_j $$? 加减 $$k$$? 之间就好了。我们用 $$BIT$$? 来维护莫队中的数据，就可以快速的求出 $$a_i$$ 的数量。 #include #define lowbit(pos) ((pos)&(-pos)) #define ql (q[i].l) #define qr (q[i].r) using namespace std; typedef long long ll; const int N = 3e4+10; int a[N],b[N]; int up[N],down[N]; int bit[N<<2],mp[N<<2]; int block[N],ans[N],len; struct Node { int l,r,id; bool operator < (const Node b) const{ return block[l]==block[b.l]?r> n >> m >> k; len = sqrt(n); /// 离散化 for(int i = 1; i <= n ; i++){ cin >> a[i]; mp[++cnt] = a[i]; mp[++cnt] = a[i]-k-1; mp[++cnt] = a[i]+k; block[i] = (i-1)/len+1; } /// 把 a[i]-k+1 与 a[i] + k 一起丢进去离散化，是为了方便后面比较大小，方便BIT操作 sort(mp+1,mp+1+cnt); int num = unique(mp+1,mp+1+cnt) - mp - 1; for(int i = 1; i <= n ;i++){ up[i] = lower_bound(mp+1,mp+1+num,a[i]+k)-mp; down[i] = lower_bound(mp+1,mp+1+num,a[i]-k-1)-mp; b[i] = lower_bound(mp+1,mp+1+num,a[i])-mp; } /// 莫队 for(int i = 1; i <= m ; i++){ cin >> q[i].l >> q[i].r; q[i].id = i; } sort(q+1,q+1+m); int l = 1, r= 0, res = 0; for(int i = 1; i <= m ; i++){ while(l < ql){ add(b[l],-1); res -= get(up[l]) - get(down[l]); l++; } while(l > ql){ res += get(up[l-1]) - get(down[l-1]); add(b[l-1],1); l--; } while(r < qr){ /// 得到大于 up[r+1]的数有多少个 res += get(up[r+1]) - get(down[r+1]); add(b[r+1],1); r++; } while(r > qr){ add(b[r],-1); res -= get(up[r]) - get(down[r]); r--; } ans[ q[i].id ] = res; } for(int i = 1; i <= m ; i++){ cout << ans[i] << endl; } return 0; } G. Magic Number Group_分解质因子+莫队题意：给你一个序列 $$a$$ 对序列 $$a$$?? 每一个数分解质因子质因子必须大于 1，查询区间中出现次数最多的因子的数量。题解：先看数据 $$5e4，1e6$$ ，打 $$1e6$$? 的表，那直接莫队就完了，刚好莫队的板子就是求区间众数，那就是板子题嘛。 #include using namespace std; const int N = 5e4 + 10; const int maxn = 1e6+10; struct Q { int l,r; int loc; }q[N]; int res; int id[N],block,a[N],ans[N],flag[maxn],cnt[maxn]; bool vis[maxn]; bool cmp(Q a,Q b) { if( id[a.l] == id[b.l] ) return a.r < b.r; return id[a.l] < id[b.l]; } vector< int > vec[maxn+1]; inline void add(int loc) { for(auto it : vec[ a[loc] ]){ flag[ cnt[it] ]--; cnt[it]++; flag[cnt[it]]++; res = res>cnt[it]?res:cnt[it]; } } inline void del(int loc) { for(auto it: vec[ a[loc] ]){ flag[ cnt[it] ]--; if( cnt[it] == res && flag[ cnt[it] ] == 0 ) res--; cnt[it]--; flag[ cnt[it] ]++; } } int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int t; scanf("%d",&t); for(int i = 2; i < maxn ;i++){ if( !vis[i] ){ for(int j = i; j < maxn ; j += i ){ vis[j] = 1; vec[j].emplace_back(i); } } } while(t--){ int n ,m; scanf("%d%d",&n,&m); block = sqrt(n); for(int i = 1; i <= n ; i++){ scanf("%d",&a[i]); id[i] = (i - 1) /block + 1; } for(int i = 1; i <= m ; i++){ scanf("%d%d",&q[i].l ,&q[i].r); q[i].loc = i; } sort(q+1,q+m+1,cmp); res = 0; int l=1,r=0; for(int i = 1; i <= m ; i++){ int ql = q[i].l, qr = q[i].r; while(l < ql) del(l++); while(l > ql) add(--l); while(r < qr) add(++r); while(r > qr) del(r--); ans[ q[i].loc ] = res; //cout << q[i].loc << "==" << res< 16ST表 P2251 质量检测线段树 #include #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 ) #define inf 0x3f3f3f3f using namespace std; int n,m; const int N = 1e6+10; struct Node { int l,r; int mi; }T[N]; int a[N]; void push_up(int rt) { T[rt].mi = min( T[ls].mi , T[rs].mi ); } void build(int rt,int l,int r) { T[rt] = {l,r,0}; if(l == r){ T[rt].mi = a[l]; return ; } build( ls,l,Mid),build(rs,Mid+1,r); push_up(rt); } int query(int rt,int l,int r) { if( l <= L && r >= R ){ return T[rt].mi; } int al = inf,ar = inf; if( l <= Mid ) al = query(ls,l,r); if( r > Mid ) ar = query(rs,l,r); return min(al,ar); } int main() { scanf("%d%d",&n,&m); for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); build(1,1,n); for(int i = 1 ; i + m - 1<= n ; i++){ printf("%d\n",query(1,i,i+m-1) ); } } ST表 #include using namespace std; int n,m; const int N = 1e6+10; int a[N][21]; inline void pre() { for(int j = 1; j <= 21; j ++) for(int i = 1; i + (1< 分块 #include using namespace std; const int N = 1e6+10; int mi[N]; int a[N]; int id[N]; int n,m,block; int query(int l,int r) { int sid = id[l],eid = id[r]; int ans = 0x3f3f3f3f; if( sid == eid ){ for(int i = l; i <= r; i++) ans = min(ans, a[i] ); return ans; } for(int i = l ; id[i] == sid ; i++) ans = min(ans,a[i]); for(int i = sid + 1; i < eid ; i++) ans = min(ans,mi[i]); for(int i = (eid-1)*block + 1 ; i <=r ; i++ ) ans = min(ans,a[i]); return ans ; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m ; block = sqrt(n); int len = (n-1)/block +1 ; for(int i = 1 ; i <= len; i ++){ mi[i] = 0x3f3f3f3f; } for(int i = 1; i <= n ; i++){ cin >> a[i]; id[i] = ( i - 1 ) / block + 1; mi[ id[i] ] = min( mi[id[i]] , a[i] ); } for(int i = 1; i + m - 1 <= n; i ++){ cout < Frequent values（区间出现次数最多的数的数量）莫队用快读+莫队能把这个题卡过，我最开始没看题解自己写，就只开了一个存这个数出现了好多次，遇到的第一个问题是，有负数，我就直接把cnt 开成2*N，之后我在写del函数的时候卡住，我发现如果我最大的数减下去了，那如何转移当前最大数的状态？我没想出来 HDU 1806(Frequent values)莫队算法然后看了这篇题解，他提供了一种思路，再多开一个sum[x]数组来维护，出现次数为x的所有元素之和，而且非常重要的第一点是，这个原始数组他是呈不下降的，所有每次 del 都会检测 sum[]的状态。我开始是想再开一个priority_queue< pair > 来维护所有的出现的数的出现次数，但是想到prorirt_queue 无法修改中间的数，又想用 set< pair > 来维护，那每次操作就从O(1) 变成O(log(n))了，肯定跑不动，终无果。下面的代码不能通过，上快读就能过，详见博客（他那个快读的实现有点问题....虽然可行但是，它实现的方法看着不爽...） #include using namespace std; const int N = 1e5+10; int n,m,block,id[N],a[N],cnt[N*2],sum[N],no,ans[N]; struct Node { int l,r,id; }q[N]; bool cmp(Node x,Node y) { if( id[x.l] == id[y.l] ) return x.r < y.r; return x.l < y.l; } inline void add(int pos) { int &Cnt = cnt[a[pos]]; sum[Cnt] -= Cnt*a[pos]; Cnt++; sum[Cnt] += Cnt*a[pos]; no = max(no,Cnt); } inline void del(int pos) { int &Cnt = cnt[a[pos] ]; sum[Cnt] -= Cnt*a[pos]; if( sum[Cnt] == 0 && no == Cnt ) no--; Cnt--; sum[Cnt] += Cnt*a[pos]; } void solve() { block = sqrt(n); for(int i = 1; i <= n ; i++){ cin >> a[i]; id[i] = (i-1)/block +1; } for(int i = 1; i <= m ; i++){ cin >> q[i].l >> q[i].r; q[i].id = i; } int te; cin >>te; sort(q+1,q+1+m,cmp); // for(int i = 1; i <= m ; i++){ // cout << q[i].l << ' ' << q[i].r << endl; // } int l=1,r=0; for(int i = 1; i <= m ; i++){ int ql = q[i].l , qr = q[i].r; while(l < ql) del(l++); while(l > ql) add(--l); while(r < qr) add(++r); while(r > qr) del(r--); ans[q[i].id ] = no; // cout << q[i].id << endl; } for(int i = 1; i <= m ; i++){ cout << ans[i] <> n >> m){ memset(cnt,0,sizeof cnt); memset(sum,0,sizeof sum); solve(); } return 0; } /* 10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0 */ 线段树线段树的思路和ST表是一样的，就是不同的实现方式而已，但是ST表的查询是O(1)的会比线段树快点，用线段树来维护一个区间最大值，也不用离散化，直接a[i] = a[i]+1e5就完了重点在对于数组 -1 -1 1 1 1 1 3 10 10 10 把他住转变为 id[]=1 2 1 2 3 4 1 1 2 3 其实就是相等的就从 1 开始递增就完了。比如说我们查询[4,10] 这个区间，那边我们把查询划分为，不完整查询和完整查询，对于前面的[4,6] 这个区间，我们再记录一个cnt[]数组，来表示这个数一共出现多少次，那么这个不完整块的长度就变成了cnt[a[x]] - id[x] （x为数的下标），但是还会出现，查询区间没有把这个数的后半部分包括完的情况，比如说[3,4] 所以我们还要做个判断上面是对不完整块的处理，对后面的块，因为是递增的，所以我们直接求线段树中后面区间的id最大值就好了，线段树就是用来维护id数组的 #include #define L (T[rt].l) #define R (T[rt].r) #define ls (rt<<1) #define rs (rt<<1|1) #define Mid ( T[rt].l + T[rt].r >>1 ) using namespace std; const int N = 1e5+10; struct Node { int l,r; int ma; }T[N<<2]; int n,m,a[N],cnt[N<<1],id[N],te; void build(int rt,int l ,int r) { T[rt] = {l,r,0}; if( l == r ){ T[rt].ma = id[l]; return ; } build(ls,l,Mid);build(rs,Mid+1,r); T[rt].ma = T[ls].ma>T[rs].ma?T[ls].ma:T[rs].ma; } int query(int rt,int l,int r) { if( l <= L && r >= R ){ return T[rt].ma; } int l_son=0,r_son=0,son; if( l <= Mid ) l_son = query(ls,l,r); if( r > Mid ) r_son = query(rs,l,r); return l_son>r_son?l_son:r_son; } void solve() { for(int i = 1; i <= n ; i++){ cin >> a[i]; a[i] += 1e5; cnt[a[i]] ++; } id[1] = 1; for(int i = 2 ; i <= n ; i++){ if( a[i] == a[i-1] ) id[i] = id[i-1]+1; else id[i] = 1; } build(1,1,n); for(int i = 0 ; i < m ; i++){ int x,y,ans=0; cin >> x >> y; int no = cnt[ a[x] ]; // cout << "*" << x + no - id[x] <> n ,n){ cin >> m; memset(cnt,0,sizeof cnt); solve(); } } ST表思路和线段树一模一样 #include #define L (T[rt].l) #define R (T[rt].r) #define ls (rt<<1) #define rs (rt<<1|1) #define Mid ( T[rt].l + T[rt].r >>1 ) using namespace std; const int N = 1e5+10; int n,m,a[N],cnt[N<<1],id[N][21],te; inline int query(int l,int r) { int k = log2(r-l+1); return max( id[l][k],id[ r-(1<> a[i]; a[i] += 1e5; cnt[a[i]] ++; } id[1][0] = 1; for(int i = 2 ; i <= n ; i++){ if( a[i] == a[i-1] ) id[i][0] = id[i-1][0]+1; else id[i][0] = 1; } pre(); for(int i = 0 ; i < m ; i++){ int x,y,ans=0; cin >> x >> y; int no = cnt[ a[x] ]; // cout << "*" << x + no - id[x] <> n ,n){ cin >> m; memset(cnt,0,sizeof cnt); solve(); } } 17____随机算法（待补）1___Hash Function_2021牛客暑期多校训练营1 （待补）2___Knowledge Test about Match_2021牛客暑期多校训练营1 好题： 1____幂次方( 递归 ) #include 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 <> n; cout << f(n) < 2____Z字形扫描 ( 模拟蛇形矩阵 ) 3____蛇形矩阵（各种版本的） AcWing寒假提高 1____AcWing 1402. 星空之夜 Flood Fill算法——见板子

ACM

相关 acm讲解「acmhdu - 6314」Matrix 第十三届河南省ACM-ICPC游记 ACM模板 Hyperf 接入阿里云ACM应用配置管理中心 [ACM] BFS & 双端BFS & A* & 双边BFS 计算几何 / Geometry（ACM-Template 2.0） ACM入门方式 Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文? ACM- java在acm中的快速读入，多组读入，快速输出模板 ACM - 动态规划 - P1282 多米诺骨牌

标签

刷题

title: 补题 date: 2020-12-11 00:00:00 updated: type: "ACM", comments: 记录比较重要的题目 description: categories: "ACM" keywords: top_img: https://i.loli.net/2021/08/03/kZaRI3WNvuLfyKc.png mathjax: katex: aside: aplayer: highlight_shrink:

题解

待补算法:

1____模拟退火

星星还是树

通电围栏

Strange fuction

2____字符串

2.1____KMP

Censor—训练赛2015四川省赛

剪花布条

Number Sequence

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

2.2____kmp&前缀的周期性

Period

Seek the Name, Seek the Fame

Blue Jeans

2.4____字符串Hash

Number Sequence

Censor

剪花布条

Seek the Name, Seek the Fame

2.4____ 扩展KMP

（_待补） Prefixes and Suffixes

2.5____回文Manacher

3188. manacher算法 - AcWing题库

字典树

（_待补）Problem - M - Codeforces (Unofficial mirror site, accelerated for Chinese users)

（_待补）I love counting - HDU 6964 - Virtual Judge (vjudge.net)

3____计算几何

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

（_待补）Triangle

（_待补）Naive and Silly Muggles

3.1____叉积判断点线关系

TOYS

Segments

3.2____多边形重心

Lifting the Stone

3.3____极角排序

3.4____计算几何，思维题

An Easy Problem?!

Kadj Squares

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

Problem - 1486B - Codeforces

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

Intersection

3.6____计算凸包，周长

Surround the Trees

3.7____平面几何

Keiichi Tsuchiya the Drift King

3.8____最小圆覆盖

Buried memory

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

Empty Convex Polygons)

3.10 三角形

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

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

4____组合数

Close Tuples (hard version)

5____三分

The Moving Points

（_待补）Restorer Distance

二分

你真的会二分查找吗？

卡精度Problem - D - Codeforces

Defuse the Bombs

6____并查集

（_待补）Prefix Enlightenment ( 带权并查集 )

（_待补）Rank of Tetris - HDU 1811（拓扑排序+并查集）

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

（_待补）Largest Common Submatrix

（_待补）棋盘制作

（_待补）玉蟾宫 BZOJ[3039]

8____线段树

单点更新

敌兵布阵

I Hate it

最大数

第八大奇迹

title: 补题
date: 2020-12-11 00:00:00
updated:
type: "ACM",
comments: 记录比较重要的题目
description:
categories: "ACM"
keywords:
top_img: https://i.loli.net/2021/08/03/kZaRI3WNvuLfyKc.png
mathjax:
katex:
aside:
aplayer:
highlight_shrink:

（_待补）线段树优化数论 Codeforces1549D Integers Have Friends (思维线段树)

（_待补）线段树优化DP E-Phone Network_2020ICPC·小米网络选拔赛第一场 (nowcoder.com)

（_待补）Tunnel Warfare ls左，ls右+rs左，rs右

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