SDUT 2022 Autumn Team Contest 7th
- 2022 年 9 月 10 日
- 筆記
1.J題：給你T組數據，每一組數據給你一個區間，讓你求這個區間的範圍，區間的起始時間和終止時間可能被包含或重複
思路：思路的話，就是直接把給定的兩個區間的之間的數包括端點存到vector去重，然後直接輸出個數即可，或者直接存到set里直接系統去重也可
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; vector<int> ans; int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--) { int a,b; cin>>a>>b; for(int i=a;i<=b;i++) { ans.push_back(i); } } sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end()); cout<<ans.size()<<endl; return 0; }
2.L題：給你T個數讓你求每個數的非質因數的因數個數
思路：一開始我們想到的是直接預處理，直接在前面預處理出來答案，然後按O(1)的時間複雜度查詢就可以了，但是其實這樣的話再做預處理的時候就會超時，然後我們知道了怎麼算因數的個數，根據惟一分解定理我們可以知道，每一個數都可以被分成幾個質數的幾次方相乘的乘積，然後把每一個數的指數加一，然後乘起來就是因數的個數，此時我們把質因數的個數去掉之後，就可以得到非質因數的個數。然後我們可以直接去求質因數，這樣的話及可以求出每一個質因數的個數（及指數）又可以求出質因數的個數，這樣的話我們就可以求出最終的答案，但是直接這樣寫的話還是會超時，因為它有3e6次的詢問，但是我們最大的數才是2e6所以有的數肯定不止被算了一遍，這樣的話我們可以記錄一下，如果這個數被算過的話我們就直接輸出，沒有被算過的時候再進行計算
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 3e6 + 10; int res[N]; void divide(int x) { int k=x; int ans=1; int ans2=0; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) { x /= i, s ++ ; } ans*=s+1; if(x!=1) ans2++; } if (x > 1) ans*=2; printf("%d\n",ans-ans2-1); res[k]=ans-ans2-1; } int main() { res[1]=1; int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); if(res[n]!=0) printf("%d\n",res[n]); else divide(n); } return 0; }
3.B題：意思是一開始給我們一張圖，然後其中有一台主機會被病毒給侵染，但是我們想讓它一次就把所有的主機感染，並且我們會加上一些邊保證能一次感染，問我們加邊的條數最少是多少，病毒只可以隔一個侵染。
思路：翟老闆全程提供思路，此題其實我們如果想讓它在只侵染一台主機的情況下，想要把所有的機器都通過跳躍的毒素侵染的話，我們首先至少得把所有的點全部連在一起，這樣的話我們可以用並查集，通過並查集我們可以求出一共有幾個圖，我們首先要把不連在一起的圖連在一起，這樣的話我們就會有ans=父節點等於其本身的點的個數減一。然後我們再考慮，光連同還不行，必須要存在一個奇數環，這樣的話才能保證在只侵染一個主機的前提下，主機通過病毒去侵染別的主機進而侵染全部，然後奇數環的話我們可以聯想到二分圖，二分圖就是沒有奇數環的無向圖，這樣的話我們只需要通過染色法判斷它是否是個二分圖即可，如果是二分圖的話，我們就要加上一條邊（及湊出奇數環），如果不是二分圖的話，說明我存在奇數環，最後直接輸出ans即可。
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int p[N]; int e[N],ne[N],h[N],color[N],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } bool dfs(int u,int c) { color[u]=c; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!color[j]) { if(!dfs(j,3-c)) return false; } else if(color[j]==c) { return false; } } return true; } int main() { int ans=0; memset(h,-1,sizeof h); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) p[i]=i; while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); int pa=find(a); int pb=find(b); p[pa]=pb; } for(int i=1;i<=n;i++) { if(p[i]==i) ans++; } ans=ans-1; bool flag=true; for(int i=1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1)) { flag=false; break; } } } if(flag==true) { ans++; } printf("%d\n",ans); return 0; }
