首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛04

多校A层冲刺NOIP2024模拟赛04

时间：2024-10-09 18:49:01浏览次数：8  
标签：04 int rep 多校 long FILE using NOIP2024 define

多校A层冲刺NOIP2024模拟赛04

学校OJ赛时 rank28，T1 0pts，T2 100pts，T3 20pts,T4 25pts
accoders rank15，T1 100pts，T2 100pts，T3 20pts，T4 25pts

不是，也没人告诉我两个OJ文件名不一样啊

02表示法

递归 + 高精除低精。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("power.in"),*OutFile = outfile("power.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 200;
string s;
ll n;
inline int divide(string &s){
    if(!s.size()) return -1;
    if(s.size() == 1 && s[0] == '0') return -1;
    if(s.size() == 1 && s[0] == '1'){
        s = "";return 1;
    }
    int res = (s.back() - '0')%2;s.back() -= res;
    int n = s.size(),x = 0;
    string sh;bool flag = false;
    rep(i,0,n-1,1){
        x = x*10 + (s[i] - '0');
        if(x >= 2) sh.push_back(x/2+'0'),x %= 2,flag = true;
        else if(flag) sh.push_back('0');
    }
    s = sh;
    return res;
}
#define pii pair<int,int>
#define mk make_pair
void work(string s){
    if(s == "0") return cout<<0,void();
    if(s == "1") return cout<<"1",void();
    if(s == "2") return cout<<"2",void();
    if(!s.size()) return;
    vector<pii> p;
    rep(i,0,999999,1){
        int x = divide(s);
        if(x == -1) break;
        if(!x) continue;
        p.emplace_back(mk(i,1));
    }
    reverse(p.begin(),p.end());
    int len = p.size();
    for(int i = 0;i < len; ++i){
        if(p[i].first == 1) {cout<<2;goto ed;}
        cout<<2;
        if(p[i].first != 1) cout<<'(';
        work(to_string(p[i].first));
        if(p[i].first != 1) cout<<')';
        ed:;
        if(i != len - 1) cout<<'+';
    }
}
inline void solve(){
    cin>>s;
    work(s);
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

子串的子串

赛时写了一个\(O(nq\log n)\)的暴力，本来是能拿70pts的，但是常数小+信仰就过了。

就是把每次查询的串截出来，然后跑个后缀数组求\(height\)，用结论 : 一个字符串本质不同的子串的数量为\(\frac{n\times (n+1)}{2}-\sum_{i=2}^n height_i\)，就可以了。

求后缀数组用的倍增法，用\(DC3\)的话就是\(O(nq)\)的

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("substring.in"),*OutFile = outfile("substring.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 3010;
char *p1,*p2,buf[1<<23];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
#ifdef linux
#define pc putchar_unlocked
#else
#define pc putchar
#endif
namespace IO{
    template<typename T>inline bool read(T &x){x=0;char s=gc();bool f=true;for(;(s<'0'||'9'<s);s=gc()) {if(s=='-') f=false;if(s==EOF)return false;}for(;'0'<=s&&s<='9';s=gc()) x=(x<<1)+(x<<3)+(s^48);if(!f) x=~x+1;return true;}
    inline bool read(double &x){x=0.0;char s=gc();bool f=true;for(;(s<'0'||'9'<s);s=gc()) {if(s=='-') f=false;if(s==EOF)return false;}for(;'0'<=s&&s<='9';s=gc()) x=(x*10)+(s^48);if(s!='.'){return true;}double res=0.1;s=gc();for(;'0'<=s&&s<='9';res/=10,s=gc()) x+=(s^48)*res;x=f?x:-x;return true;}
    inline bool read(long double &x){x=0.0;char s=gc();bool f=true;for(;(s<'0'||'9'<s);s=gc()) {if(s=='-') f=false;if(s==EOF)return false;}for(;'0'<=s&&s<='9';s=gc()) x=(x*10)+(s^48);if(s!='.'){return true;}double res=0.1;s=gc();for(;'0'<=s&&s<='9';res/=10,s=gc()) x+=(s^48)*res;x=f?x:-x;return true;}
    inline bool read(float &x){x=0.0;char s=gc();bool f=true;for(;(s<'0'||'9'<s);s=gc()) {if(s=='-') f=false;if(s==EOF)return false;}for(;'0'<=s&&s<='9';s=gc()) x=(x*10)+(s^48);if(s!='.'){return true;}double res=0.1;s=gc();for(;'0'<=s&&s<='9';res/=10,s=gc()) x+=(s^48)*res;x=f?x:-x;return true;}
    inline bool read(string &str){string ().swap(str);char s=gc();for(;s==' '||s=='\n';s=gc());if(s==EOF) return false; for(;s!=' '&&s!='\n'&&s!=EOF;s=gc())str.push_back(s);return true;}
    inline bool read_line(string &str){string ().swap(str);char s=gc();for(;s==' '||s=='\n';s=gc());if(s==EOF) return false;for(;s!='\n'&&s!=EOF;s=gc()){str.push_back(s);}return true;}
    inline bool read_line(char *str){int len=0;char s=gc();for(;s==' '||s=='\n';s=gc());if(s==EOF) return false;for(;s!='\n'&&s!=EOF;s=gc()){str[len]=s;len++;}str[len]='\0';return true;}
    inline bool read(char &s){char x=gc();for(;x==' '||x=='\n';x=gc());if(x==EOF||x==' '||x=='\n')return false;s=x;return true;}
    inline bool read(char *s){int len=0;char x=gc();for(;x==' '||x=='\n';x=gc());if(x==EOF)return false;for(;x!=' '&&x!='\n'&&x!=EOF;x=gc())s[len++]=x;s[len]='\0';return true;}
    template<class T,class... Args> inline bool read(T &x,Args&... args){return (read(x)&&read(args...));}
    template<class T>inline void write(T x){static T st[45];int top=0;if(x<0)x=~x+1,pc('-');do{st[top++]=x%10;}while(x/=10);while(top)pc(st[--top]^48);}
    inline void write(char x){pc(x);}
    inline void write(string s){for(int i=0;s[i];++i) pc(s[i]);}
    inline void write(char *s){int len=strlen(s);for(int i=0;i<len;++i) pc(s[i]);}
    inline void write(const char *s){int len=strlen(s);for(int i=0;i<len;++i) pc(s[i]);}
    template<class T,class... Args> inline void write(T x,Args... args){write(x);write(args...);}
}using namespace IO;
int n,m,sa[N],rk[N],tp[N],ht[N],ct[N];char s[N],s1[N];
inline void Qsort(int m){
    rep(i,1,m,1) ct[i] = 0;
    rep(i,1,n,1) ++ct[rk[i]];
    rep(i,2,m,1) ct[i] += ct[i-1];
    drep(i,n,1,1) sa[ct[rk[tp[i]]]--] = tp[i];
}
inline bool cmp(int x,int y,int w){return (tp[x]==tp[y]&&tp[x+w]==tp[y+w]);}
inline void get_sa(){
    n = strlen(s+1);
    int m = 27;
    rep(i,1,n,1) rk[i] = s[i] - 'a' + 1,tp[i] = i;
    Qsort(m);
    for(int w=1,p=0;w<=n;m=p,p=0,w<<=1){
        rep(i,n-w+1,n,1) tp[++p]=i;
        rep(i,1,n,1) if(sa[i]>w) tp[++p]=sa[i]-w;
        Qsort(m);
        rep(i,1,n,1) swap(tp[i],rk[i]);
        p=rk[sa[1]]=1;
        rep(i,2,n,1) rk[sa[i]]=cmp(sa[i-1],sa[i],w)?p:++p;
        if(p==n) break;
    }
    int k = 0;
    rep(i,1,n,1){
        if(!rk[i]) continue;
        if(k) --k;
        while(s[i+k] == s[sa[rk[i]-1]+k]) k++;
        ht[rk[i]] = k;
    }
}
inline void solve(){
    read(n,m);read(s1+1);
    while(m--){
        int l,r;ll ans;read(l,r);
        rep(i,l,r,1) s[i-l+1] = s1[i];
        n = r-l+1;
        s[n+1] = '\0';
        get_sa();
        ans = 1ll*n*(n+1)/2;
        rep(i,2,n,1) ans -= ht[i];
        rep(i,1,n,1) ht[i] = rk[i] = sa[i] = tp[i] = 0;
        write(ans,'\n');
    }
}
signed main(){
    solve();
}

正解是预处理，二维前缀和。

记\(ans_{l,r}\)表示区间\([l,r]\)及其子区间本质不同的字符串的个数。可以先维护差分数组然后前缀和解决。

先枚举子串长度，再枚举左端点，通过预处理的前缀和求出这\([l,r]\)一子串的哈希值，那么该串的左右端
点\([l,r]\)的答案加一，即\(ans_{l,r}++\)，为了避免重复统计，该串还在上次该串出现位置到该位置
之间该串都有贡献，那么应该将上一次出现的左端点\(pre\)（字符串哈希维护）与当前右端点的答案减一，
即\(ans_{pre,r}--\)，最后对数组求和得到的其实是会有重复贡献，要通过容斥计算出每个区间的答案\(ans_{l,r}\)
，回答询问

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("substring.in"),*OutFile = outfile("substring.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 3010;
char s[N];
int n,m,ans[N][N];
ull hs[N],pw[N],base = 131;
inline ull get_hash(int l,int r){return hs[r] - hs[l-1]*pw[r-l+1];}
inline void solve(){
    cin>>n>>m>>(s+1);
    pw[0] = 1;rep(i,1,n,1) pw[i] = pw[i - 1] * base;
    rep(i,1,n,1) hs[i] = hs[i-1]*base + s[i];
    rep(len,1,n,1){
        __gnu_pbds::gp_hash_table<ull,int> mp;
        rep(l,1,n-len+1,1){
            int r = l + len - 1;
            ull h = get_hash(l,r);
            ans[mp[h]][r]--;
            mp[h] = l;
        }
    }
    drep(l,n,1,1) rep(r,l,n,1)
        ans[l][r] += ans[l + 1][r] + ans[l][r - 1] - ans[l+1][r-1] + 1;
    while(m--){
        int l,r;cin>>l>>r;cout<<ans[l][r]<<'\n';
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

魔法咒语

考虑一个串是被两个拼起来的或者就一个，一个的特判掉。

考虑对于每一个前缀扩展，假设拓展的第一个字符为\(c\)

加入\(c\)已经被扩展过了，那么看看它是否是最后一个节点，如果是，那么说明这个咒语本身就存在，直接加上一个即可。

反之，那么就考虑所有第一个字符为\(c\)的不同后缀都可以。

前缀的话插入一个正向的Trie就可以，看后缀的话插入一个后缀的Trie即可。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("magic.in"),*OutFile = outfile("magic.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 4e5 + 10;
struct Trie{
    int tree[N][27],cnt[N],tot;
    inline void insert(string s,bool rev){
        int p = 0,len = s.size()-1;
        if(rev) reverse(s.begin(),s.end());
        rep(i,0,len,1){
            int x = s[i] - 'a' + 1;
            if(!tree[p][x]) tree[p][x] = ++tot,cnt[x] += rev;
            p = tree[p][x];
        }
    }
}t1,t2;
ll ans = 0,n;
string s[N];
bitset<27> ok,flag;
inline void solve(){
    cin>>n;
    rep(i,1,n,1){
        cin>>s[i];
        t1.insert(s[i],false);t2.insert(s[i],true);
        int len = s[i].size();
        ok[s[i].back() - 'a' + 1] = true;
        if(len == 1 && !flag[s[i][0] - 'a' + 1]) ans++,flag[s[i][0] - 'a' + 1] = true;
    }
    rep(i,1,t1.tot,1) rep(j,1,26,1)
        if(!t1.tree[i][j]) ans += t2.cnt[j];
        else if(ok[j]) ans++;
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

表达式

线段树。不太懂啊。

将给的模数分解成\(\prod p_i^{k_i}\)，然后以每个\(p_i^{k_i}\)为模数，求出答案以后再用CRT合并。

至于以\(p_i^{k_i}\)为模数的处理，用线段树暴力记录就好了。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("expr.in"),*OutFile = outfile("expr.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define fi first
#define se second
#define pii pair<char,int>
#define mk make_pair
const int N = 2e5 + 10;
int n,m,mod;
pii a[N];

struct Segment_Tree{
    struct segment_tree{
        int l,r,val[30];
        #define l(k) tree[k].l
        #define r(k) tree[k].r
        #define val(k) tree[k].val
    }tree[N<<2];
    int p;
    unordered_map<char,function<int(int,int)> > op = 
    {
        {'+',[&](int a,int b){return (a+b)%p;}},
        {'*',[&](int a,int b){return 1ll*a*b%p;}},
        {'^',[&](int a,int b){int res = 1;for(;b;b >>= 1,a = 1ll*a*a%p) if(b&1) res = 1ll*res*a%p;return res;}}
    };
    inline void pushup(int k){
        rep(i,0,p-1,1) val(k)[i] = val(k<<1|1)[val(k<<1)[i]];
    }
    void build(int k,int l = 1,int r = n){
        l(k) = l,r(k) = r;
        if(l == r){
            rep(i,0,p-1,1) val(k)[i] = op[a[l].fi](i,a[l].se);
            return;
        }
        int mid = (l + r) >> 1;
        build(k<<1,l,mid);build(k<<1|1,mid+1,r);
        pushup(k);
    }
    void change(int k,int pos){
        if(l(k) == r(k)){
            rep(i,0,p-1,1) val(k)[i] = op[a[pos].fi](i,a[pos].se);
            return;
        }
        int mid = (l(k) + r(k)) >> 1;
        if(pos <= mid) change(k<<1,pos);else change(k<<1|1,pos);
        pushup(k);
    }
}T[4];
int exgcd(int a,int b,int &x,int &y){
    if(!b) return x = 1,y = 0,a;
    int d = exgcd(b,a%b,x,y);
    int t = x;x = y;y = t - (a/b)*y;
    return d;
}
namespace TP{
    const int N = 2e5 + 10;
    char op[N];
    int testid,n,m,mod,a[N];
    inline int power(int a,int b,int mod){
        int res = 1;
        for(;b;b>>=1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;
        return res;
    }
    inline void solve(){
        cin>>n>>m>>mod;
        rep(i,1,n,1) cin>>op[i]>>a[i];
        while(m--){
            int p,x;cin>>p;
            if(p == 1){
                cin>>x;
                rep(i,1,n,1){
                    if(op[i] == '+') x = (0ll+x+a[i])%mod;
                    if(op[i] == '*') x = 1ll*x*a[i]%mod;
                    if(op[i] == '^') x = power(x,a[i],mod);
                }
                cout<<x<<'\n';
            }
            else{
                char c;int y;
                cin>>x>>c>>y;op[x] = c,a[x] = y;
            }
        }
    }
}
inline void solve(){
    int id;
    cin>>id;
    if(id <= 3){
        TP::solve();
        return;
    }
    cin>>n>>m>>mod;
    rep(i,1,n,1) cin>>a[i].fi>>a[i].se;
    vector<int> d;
    int res = mod;
    for(int i = 2;i * i <= res; ++i){
        if(res % i == 0){
            int k = 1;
            while(res % i == 0) res /= i,k *= i;
            d.emplace_back(k);
        }
    }

    if(res > 1) d.emplace_back(res);
    for(int i = 0;i < d.size(); ++i){
        
        T[i].p = d[i],T[i].build(1);
    }

    // exit(0);

    auto get_ans = [&](vector<int> &v){
        int res = 0;
        for(int i = 0;i < v.size(); ++i){
            int m = mod/d[i],b,y;
            exgcd(m,d[i],b,y);
            res = (res + 1ll * v[i] * m % mod * b % mod) % mod;
        }
        return (res + mod) % mod;
    };
    
    while(m--){
        int op;cin>>op;
        if(op == 1){
            int x;cin>>x;
            vector<int> v;
            for(int i = 0;i < d.size(); ++i) v.emplace_back(T[i].tree[1].val[x%T[i].p]);
            cout<<get_ans(v)<<'\n';
        }
        else{
            int x,z;cin>>x;char y;cin>>y>>z;
            a[x] = mk(y,z);
            for(int i = 0;i < d.size();T[i++].change(1,x));
        }
    }

}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

标签：04,int,rep,多校,long,FILE,using,NOIP2024,define
From： https://www.cnblogs.com/hzoi-Cu/p/18454912

相关文章

  • 『模拟赛』多校A层冲刺NOIP2024模拟赛04
    Rank赤石场。A.02表示法签。若干天前在洛谷随到过，不过当时只看了眼讨论区就走了www还好本来不是很难。发现大体上是一个拆分二的幂的问题，从大到小枚举2的幂，判断有没有这个幂只用比较大小关系，然后再对指数做一个同样的操作，递归至不大于2为止，注意\(2^1\)不用输出(1......
  • 多校A层冲刺NOIP2024模拟赛04
    多校A层冲刺NOIP2024模拟赛04\(T1\)A.02表示法\(0pts/100pts\)弱化版：luoguP1010[NOIP1998普及组]幂次方递归模拟即可，二进制分解时需要写高精除低精。点击查看代码intr[810],t[810];chars[810],id[810][10];stringa;intchu(chars[]){ intn=strlen(s......
  • IEC104规约的秘密之七----配置参数t1,t2,t3
    104通讯前需要配置通讯参数，一般有如下参数：IP地址，端口号，k，w，t1，t2，t3，公共地址，遥控超时参数，104主规约还有一个t0参数。本次只讲解t1，t2，t3这两个参数。这三个都是超时时间，t1用于两个地方，一个是发送的I帧没有得到及时的确认，在规约文本中有如下图：B站发送I(0,0)帧后，开始计时，A站回......
  • C++ day04（友元 friend、运算符重载、String字符串）
    目录【1】友元friend1》概念2》友元函数 3》友元类 4》友元成员函数 【2】运算符重载1》概念2》友元函数运算符重载 ​编辑 3》成员函数运算符重载4》赋值运算符与类型转换运算符重载 5》注意事项【3】String字符串类【1】友元friend1》概念定义：......
  • XYD1004CSPS
    T1序列[贪心，模拟]Description给定一个序列，每次可以将一个数减一，求让所有数字互不相同的最小操作数，\(0\)除外，也就是\(0\)可以相同。Solution贪心地，从大到小考虑每个数，都只需要减到第一个没有数出现的数。开个桶从大到小累计答案即可。T2XYD[构造]Description给定\(......
  • 【堆】【优先队列】[NOIP2004]合并果子
    https://ac.nowcoder.com/acm/contest/22669/I堆的用法Type:队列中存储元素的类型。例如int，double，pair<int,int>等。Container:底层存储数据的容器类型，默认为vector，但可以换成deque或其他容器。Compare:比较函数，用于决定优先级顺序。默认是less，表示最大堆。如果使用......
  • 20241008_Day 04
    helloworld!1.安装NOTEPAD++2.新建代码文件夹3.新建JAVA文件1.可以新建text文件，修改后缀为.java2.打开方式修改为notepad+++4.编写代码具体为：javapublicclassHello{publicstaticvoidmain(String[]args){System.out.print("Hello,world!");}}5.......
  • 2018_11_02_04
    vue-cli案例constpath=require('path');functionresolve(dir){returnpath.join(__dirname,dir);}consttargetUrl='[地址]';module.exports={//Projectdeploymentbase//Bydefaultweassumeyourappwillbedeployedatthe......
  • NOIP2024集训 Day47 总结
    前言人有两次生命，当他意识到只有一次的时候，第二次生命就开始最小生成树和二分图匹配专题，感觉总体都比较套路。但是这些套路为啥感觉见都没见过啊，怪不得做这么慢。色观察到对于最终答案显然都是最小生成树上一条两个端点颜色不同的边。而这个题并不会改变图的形态，仅仅是改......
  • NOIP2024集训Day47 生成树+二分图
    NOIP2024集训Day47生成树+二分图B.[THUPC2022初赛]最小公倍树直接建边显然不行，考虑优化建边。对于两个点\(u,v\)，\((u,v)\)的边权为\(\displaystyle\operatorname{lcm}(u,v)=\frac{u\timesv}{\gcd(u,v)}\)，显然应该选择\(\gcd(u,v)\)尽可能大的点对连边，也就是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99