#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
const int N  = 1e5 + 10;

int n;
int pri[N] , cnt;
int st[N];

set<int> ans ;
void get_pri(int n ){
    for(int i = 2; i <= n ; i ++ ){
        if(!st[i]){
            pri[++cnt] = i ;
            for(int j =  i + i ; j <= n ;j += i ) st[j] = 1;
        }
    }   
}
void solve(){
    cin>>n;
    get_pri(n);

    for(int i = 1 ; i <= cnt ; i ++ ){
        for(int j = 1 ; j * pri[i] <= n ; j *= pri[i] ){
            ans.insert(j * pri[i]);
        }
    }
    cout<<ans.size()<<endl;
    for(auto x : ans) cout<<x<<" ";
    cout<<endl;

}
int main(){
    solve();
    return 0;
}

https://git.acwing.com/Gzm/gokob

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N =  400 ; 
ll a[N],s[N];
int n ;
//定义
ll dp[N][N];
void solve(){
    cin>>n;

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

    memset(dp , 0x3f , sizeof dp);
    // for(int i  = 1 ; i<= n  ; i ++ ) dp[1][i] = 0  ;

    for (int len = 1; len <= n; len ++ ) {//枚举长度
        for(int l =  1 ; l <= n ; l ++ ){ // 枚举坐端点
            int r = l + len - 1;

            if(len == 1){
                dp[l][r] = 0 ;
                continue;
            }
            //枚举合并点 
            for(int k =  l  ; k <= r && k < n ; k ++ ){
                dp[l][r] = min(dp[l][r] , dp[l][k]  + dp[k+1][r] + s[r]  -  s[l - 1]);
            }
        }
    }

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



}
int main(){
    solve();
    return 0;
}

// Problem: 数列元素
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4725/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define NO cout<<"NO"<<endl;
#define YES cout<<"YES"<<endl;
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;


struct node{
    int to,val;
};


int a[N],n;
void solve(){
    cin>>n;
    Fup(i,1,n){
        int d = (1+i)*i/2;
        if(d == n){
            YES
            return;
        }
    }
    NO

}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

前言

时间复杂度 : $O(nlogn)$
Tag : 归并排序 逆序对
传送门 :

思路

回顾归并思路 :
1. 将区间一分为二
2. 递归排序区间
3. 合并区间

对于逆序对,我们发现在递归过程中,我们只有两种情况需要考虑

1. 在同一个区间的逆序对
2. 不在同一个区间的逆序对
   

因为归并排序每次都会将大区间划分为小区间,即一个分治的过程

所以最后(1) 在同一个区间的逆序对其实是包含在(2)内的

因此我们考虑(2)是如何计算的

我们设已经排好序的左右区间是L,R, 那么考虑如图情况

如果L[i] > R[j]那么i前面的数必然不能比R[j]大,因为已经排好序,而其后面的数一定大于R[j]

因此对于当前的j会贡献mid-i+1个逆序对

因此我们根据这个公式分治即可

代码

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1; //计算答案
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

CF 600E树上启发式合并代码入门题

// Problem: CF600E Lomsat gelral
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF600E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: B. Rising Sand
// Contest: Codeforces - Codeforces Round #803 (Div. 2)
// URL: https://codeforces.com/contest/1698/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define NO cout<<"NO"<<endl;
#define YES cout<<"YES"<<endl;
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;


struct node{
    int to,val;
};


int col[N],n;
int e[N],ne[N],h[N],idx;
int sz[N],son[N];


void add(int a,int b){
    e[idx] = b ,ne[idx] = h[a] , h[a] = idx++;
}
//树链剖分
void dfs(int u,int fa){
    sz[u] = 1;
    for(int i =  h[u];~i;i=ne[i]){
        int j = e[i];
        if(j == fa) continue;
        dfs(j,u);
        sz[u] += sz[j];
        if(sz[j] > sz[son[u]]) son[u] = j;
    }
}
int cnt[N];//某颜色在当前子树中的数量 
ll ans[N],sum;//答案数组 , 累加计算当前子树的答案
int  flag,maxn;//标记重儿子,更新最大值
//统计
void count(int u,int fa,int val){
    cnt[col[u]] += val;

    if(cnt[col[u]] > maxn){
        maxn = cnt[col[u]];
        sum = col[u];
    }else if(cnt[col[u]] == maxn) sum += col[u];

    for(int i = h[u];~i;i=ne[i]){
        int j = e[i];
        if(j == fa || j == flag) continue;
        count(j,u,val);

    }
}
void dfs(int u,int fa,bool keep){
    //轻儿子 算答案删除贡献
    for(int i  =h[u] ;~i ; i=ne[i]){
        int j = e[i];

        if(j == fa || j == son[u]) continue;

        dfs(j,u,false);//false 删除贡献

    }

    // 搞重儿子
    if(son[u]){
        dfs(son[u],u,true);
        flag = son[u];
    }

    // 暴力统计所有轻儿子的贡献
    count(u,fa,1);
    flag = 0 ;
    ans[u] = sum;

    if(!keep){
        count(u,fa,-1);
        sum = maxn = 0 ;

    }
}
void solve(){
    memset(h,-1,sizeof h);
    cin>>n;
    Fup(i,1,n) cin>>col[i];
    Fup(i,1,n-1){
        int u,v;cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0); //树剖找重儿子
    dfs(1,0,0);

    Fup(i,1,n) cout<<ans[i] <<" ";

}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

数据范围很小所以可以直接搞

// Problem: 青蛙
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4243/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: B. Rising Sand
// Contest: Codeforces - Codeforces Round #803 (Div. 2)
// URL: https://codeforces.com/contest/1698/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define NO cout<<"NO"<<endl;
#define YES cout<<"YES"<<endl;
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e2+10,INF = 0x3f3f3f3f;
const double eps = 1e-6;


struct node{
    int to,val;
};


pii g[N];
int n;
double dist[N][N];
int st[N][N];
double _spdist[N];
int flag[N];


double calc(int x1,int y1,int x2,int y2){
    return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}

bool spfa(){
    Fup(i,1,n) _spdist[i] = INF;

    queue<int> q;
    q.push(1);
    _spdist[1] = 0 ;
    flag[1] = 1;

    while(!q.empty()){
        auto t = q.front();
        q.pop();
        flag[t]  = 0 ;

        Fup(i,1,n){
            if(_spdist[i] > _spdist[t] + st[t][i]){
                _spdist[i] = _spdist[t] + st[t][i];
                if(!flag[i]){
                    flag[i] = 1;
                    q.push(i);
                }
            }
        }
    }
    if(_spdist[2] == 0) return 1;
    else return 0 ;

}
bool check(double x){
    Fup(i,1,n){
        Fup(j,1,n){
            if(dist[i][j] > x)  st[i][j] = 1;
            else st[i][j] = 0 ;
        }
    }

    if(spfa()) return true;
    else return false;
}

void solve(){
    int idx = 0 ;

    while(cin>>n,n){



        Fup(i,1,n) cin>>g[i].x>>g[i].y;

        double l = INF ,  r = -INF;

        Fup(i,1,n){
            Fup(j,i+1,n){
                dist[i][j] = dist[j][i] = calc(g[i].x,g[i].y,g[j].x,g[j].y);
                l = min(l,dist[i][j]);
                r = max(r,dist[i][j]);
            }
        }



        while(r - l > eps){
            double mid = (l+r)/2;

            if(check(mid)) r = mid;
            else l = mid;
        }


        // cout<<"Scenario #"<<idx<<endl;
        printf("Scenario #%d\n",++idx);


        printf("Frog Distance = %.3lf\n",r);
        // cout<<"Frog Distance = "<<r<<endl;

        printf("\n");   
    }
}

int main(){
    // int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

B

前言

$tag :$ 思维 并查集

传送门 : 不能直接传送的可能没有报名该场周赛

题意 :
给定一个字符数组包含<>表示向左向右走

询问有多少个$i$满足,可以根据<>走出边界

思路 :
看完这题一眼就并查集了。我们发现不管怎么样最后的点都会经过两边。因此我们将走向两边的点分为两个集合

同时判断两边是否合法,判断当前集合是否满足即可

因为一眼题了,对于这个题也没细想。看了题解之后发现。我们并不需要分集合,因为向左边的路只能是<<<

向右边走的路只能是>所以我们统计一下前后缀即可

code :

char s[N];
int  L[N],R[N],n;
bool flag[N];

int find(int x){
    if(x!=L[x]) L[x] = find(L[x]);
    return L[x];
}
void init(){
    Fup(i,1,n){
        L[i]  = R[i] = i;
    }
}
void solve(){
    cin>>n;
    init();

    cin>>(s+1);


    if(s[1] == '<') flag[1] = 1;
    if(s[n] == '>') flag[n] = 1;

    Fup(i,1,n){
        if(s[i] == '<' && i!=1){
            int fa = find(L[i]);
            int fb = find(L[i-1]);
            L[fa] = fb;
        }else if(i!=n && s[i] == '>'){
            int fa = find(L[i]);
            int fb = find(L[i+1]);
            L[fa] = fb;
        }
    }

    int cnt = 0 ;

    Fup(i,1,n){
        int fi  = find(L[i]);

        if(flag[fi]){
            ++cnt;
        }
    }
    cout<<cnt<<endl;
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}