2020-2021:teams:wangzai_milk:20200720比赛记录
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200720比赛记录 [2020/07/23 20:32] wzx27 |
2020-2021:teams:wangzai_milk:20200720比赛记录 [2020/07/23 20:37] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 213: | 行 213: | ||
| } | } | ||
| </code> </hidden> | </code> </hidden> | ||
| + | \\ | ||
| + | ==== I - Investigating Legions ==== | ||
| + | 个人理解，相当于给一个含有多个近似团的图，要还原出这些团。 | ||
| + | |||
| + | 大概就是乱搞。我的做法是先贪心取最小的没有确定的点，把和他相邻的点加到一个集合 $V$ 里，遍历所有其他没有确定的点，如果这个点和集合 $V$ 的连接度大于某个和 $S$ 有关的阈值，就把这个点加入当前正在确定的团里。最后仍有些点没有被确定，这时遍历所有确定的团，看他与哪个团的连接度最高就放进哪里。 | ||
| + | |||
| + | <hidden code><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | int g[305][305],vis[305],ans[305],be[305],rk[305],c[305]; | ||
| + | int n,s; | ||
| + | vector<int> block[305]; | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | int _; char x; | ||
| + | for(cin>>_;_;_--){ | ||
| + | cin>>n>>s; | ||
| + | rep(i,0,n-1) vis[i] = 0,block[i].clear(); | ||
| + | rep(i,0,n-1){ | ||
| + | rep(j,i+1,n-1){ | ||
| + | cin>>x; | ||
| + | if(x=='1') g[i][j] = g[j][i] = 1; | ||
| + | else g[i][j] = g[j][i] = 0; | ||
| + | } | ||
| + | } | ||
| + | int id = 0; | ||
| + | rep(i,0,n-1) if(!vis[i]){ | ||
| + | vector<int> tmp; | ||
| + | tmp.pb(i); | ||
| + | rep(j,0,n-1) if(g[i][j] && !vis[j]){ | ||
| + | tmp.pb(j); | ||
| + | } | ||
| + | int sz = tmp.size(); | ||
| + | int th = 8 * sz / s; | ||
| + | rep(j,0,n-1) if(!vis[j]){ int cnt = 0; | ||
| + | for(int x:tmp) if(g[j][x]) cnt++; | ||
| + | if(cnt >= th) block[id].pb(j),be[j] = id,vis[j] = 1; | ||
| + | } | ||
| + | id++; | ||
| + | } | ||
| + | rep(i,0,n-1) if(!vis[i]){ | ||
| + | memset(c,0,sizeof(c)); | ||
| + | rep(j,0,n-1) if(vis[j]){ | ||
| + | c[be[j]]++; | ||
| + | } | ||
| + | int pos,mx=0; | ||
| + | rep(j,0,id-1){ | ||
| + | if(c[j] > mx) pos=j,mx = c[j]; | ||
| + | } | ||
| + | block[pos].pb(i); | ||
| + | } | ||
| + | rep(i,0,id-1){ | ||
| + | rk[i] = i; | ||
| + | sort(ALL(block[i])); | ||
| + | }sort(rk,rk+id,[](int x,int y){return block[x][0] < block[y][0];}); | ||
| + | rep(i,0,id-1){ | ||
| + | for(int x:block[rk[i]]) ans[x] = i; | ||
| + | } | ||
| + | rep(i,0,n-1) cout<<ans[i]<<" "; | ||
| + | cout<<endl; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| ===== 比赛总结与反思 ===== | ===== 比赛总结与反思 ===== | ||
2020-2021/teams/wangzai_milk/20200720比赛记录.1595507522.txt.gz · 最后更改: 2020/07/23 20:32 由 wzx27
