題目鏈接：點擊打開鏈接

題意：

給定一個區間[l,r]

每個數都選擇他的其中一個因子。

使得任意兩個數選擇的因子各不相同，且字典序最小。

思路：

先對每個數分解質因數。

然后從l開始枚舉，讓i選擇最小的因子，判斷 [i+1,r]是否有可行解，若有則讓i選擇這個因子。

如此枚舉下去即可

==復雜度不能直視

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include <cmath> #include <map> #include<vector> template <class T> inline bool rd(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1; } template <class T> inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if(x>9) pt(x/10);putchar(x%10+'0'); } using namespace std; typedef long long ll; const int N = 1000000; ll prime[9592],primenum;//有primenum個素數 math.h void PRIME(ll Max_Prime){primenum=0;prime[primenum++]=2;for(ll i=3;i<=Max_Prime;i+=2)for(ll j=0;j<primenum;j++)if(i%prime[j]==0)break;else if(prime[j]>sqrt((double)i) || j==primenum-1){prime[primenum++]=i;break;} } void get_prime(ll x, vector<ll> &G){// cout<<"i:"<<x<<"{";for(ll i = 0; prime[i]*prime[i]<=x; i++)if(x%prime[i] == 0){G.push_back(prime[i]);while(x%prime[i]==0)x/=prime[i];}if(x!=1)G.push_back(x);//for(int i = 0; i < G.size(); i++)cout<<G[i]<<" ";cout<<endl; } ll l, r; vector<ll>G[N]; void input(){for(ll i = l; i <= r; i++)get_prime(i, G[i-l]); }map<ll,ll>lef, rig;//lef[v]表示Y集的點v 當前連接的點 , pn為x點集的點數 map<ll,bool> T, must; //T[u] 表示Y集 u 是否已連接X集bool match(ll x){ // x和Y集 匹配 返回x點是否匹配成功for(int i=0; i<G[x-l].size(); i++){ll v = G[x-l][i];if(!T[v] && !must[v]){T[v] = 1;if((int)lef.count(v)==0 ||match(lef[v])) //match(lef[v]) : 原本連接v的X集點 lef[v] 能不能和別人連，如果能 則v這個點就空出來和x連{lef[v] = x;return true;}}}return false; } bool find(ll x){lef.clear();for(x++; x <= r; x++){T.clear();if(!match(x))return false;}return true; } void solve(){rig.clear();must.clear();for(ll i = l; i<= r; i++)//X集匹配，X集點標號從 1-pn 匹配邊是G[左點].size(){for(int j = 0; j < G[i-l].size(); j++){ll v = G[i-l][j];if(must[v])continue;rig[i] = v;must[v] = 1;if(!find( i ))must[v] = 0;else break;}must[rig[i]] = 1;} }int main(){PRIME(100000);while(cin>>l>>r, l+r){input();solve();for(ll i = l; i <= r; i++)printf("%lld%c", rig[i], i==r?'\n':' ');for(ll i = l; i <= r; i++)G[i-l].clear();}return 0; }

總結

以上是生活随笔為你收集整理的UVALive 6198 A Terribly Grimm Problem 二分匹配 求字典序最小解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。