这次终于找到了靠谱队友，比之前我做不出来==队友做不出来好太多了
昨天3人热身赛疯狂杀了8道题，感觉今天稳了
一开始就瞅了A题，发现似乎可以dp，看了看数据，1e7，大概想出了nsqrtn算法，想着肯定能过就写了，结果一开始是wa，发现哪点不对之后就改了改，好，变TLE,出去一看通过率5%，就几千个提交中只过了50个不到，好，很有精神
大佬迅速A了C题，然后我开始看A题，想了很多方法，但似乎最后都不行，就换题了。
我队另一大佬看了看I感觉是记忆化，就。。。顺手A了？orz
然后我看D，要是今天一道做不出那就丢大人了。我看了看是要求算移除每个点之后图上联通分量个数，大佬们说是并查集和增改，但我感觉连通性，双向边，首先想到tarjan算法，然后由此展开，发现只要找出孤点，割点即可，幸好算法课讲了tarjan，我之前打死不会，然后发现断边需要找出的是联通分量，上网查了查有板子，应该是板子题没错了。孤点连通分量-1，然后割点-大小-1.，其他原样输出，就是中间不知道出什么问题了就是一直在wa，改了改，终于拿下一血，心才放下，1今天总算不丢面子了
然后大佬迅速A了J，我们队就四题了，躺就完事儿了
之后发现F题可做
然后就去搞F，感觉是个二分，思路也特别清晰，结果谁能料到是个int128
比赛的时候试了好多都不能过，比赛之后凯哥跟我说了句换int128试试，结果就，我giao，过。。。。过了？什么神仙题目二分还要开__int128啊，我吐了啊，我没想到出题人能把数据拉满，真实呕吐
大型翻车现场就是本人了，不过还算是蛮有收获的的一场，下场再战！！
orz，我自己的代码放出来吧：
D题，Tarjan D
#include <bits/stdc++.h> using namespace std; #define limit (10000000 + 5)//防止溢出 #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-6 #define FASTIO ios::sync_with_stdio(false);cin.tie(0); //#define ff(a) printf("%d\n",a ); #define pi(a,b) pair<a,b> #define rep(i, a, b) for(ll i = a; i <= b ; ++i) #define per(i, a, b) for(ll i = b ; i >= a ; --i) #define MOD 998244353 #define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next) #define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin) #define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\dabiao.txt", "wt", stdout) #define debug(x) cout<<x<<endl typedef long long ll; typedef unsigned long long ull; inline ll read(){ ll sign = 1, x = 0;char s = getchar(); while(s > ‘9‘ || s < ‘0‘ ){if(s == ‘-‘)sign = -1;s = getchar();} while(s >= ‘0‘ && s <= ‘9‘){x = (x << 3) + (x << 1) + s - ‘0‘;s = getchar();} return x * sign; }//快读 void write(ll x){ if(x < 0) putchar(‘-‘),x = -x; if(x / 10) write(x / 10); putchar(x % 10 + ‘0‘); } int kase,n,m; ll a[limit]; vector<int>gra[661005],ans; int dfn[661005],low[661005],now,id,sum[661005]; void tarjan(int s,int p) { dfn[s]=low[s]=++now; int son=0; for(int i=0;i<gra[s].size();i++) if(!dfn[gra[s][i]]) { tarjan(gra[s][i],s); low[s]=min(low[s],low[gra[s][i]]); if(low[gra[s][i]]>=dfn[s]) sum[s]++; son++; } else if(gra[s][i]!=p) low[s]=min(low[s],dfn[gra[s][i]]); if(p==0) { if(son>=2) ans.push_back(s),sum[s]=son; } else if(sum[s]>=1) ans.push_back(s),sum[s]++; } int main() { #ifdef LOCAL FOPEN; #endif n = read(),m = read(); rep(i,1,m){ int x= read(), y = read(); gra[x].push_back(y); gra[y].push_back(x); a[y]++ ; a[x]++; } int res = 0; for(int i=1;i<=n;i++) if(dfn[i]==0 ){ tarjan(i,0); ++res; } set<int>s; for(auto i : ans){ s.insert(i); } rep(i,1,n){ if(a[i] == 0){ printf("%d ",res - 1); } else if(s.find(i) != s.end()){ printf("%d ",res + sum[i] - 1); }else{ printf("%d ",res); } } return 0; }
F题二分
#include <bits/stdc++.h> using namespace std; #define limit (1000000 + 5)//防止溢出 #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-6 #define FASTIO ios::sync_with_stdio(false);cin.tie(0); //#define ff(a) printf("%d\n",a ); #define pi(a,b) pair<a,b> #define rep(i, a, b) for(ll i = a; i <= b ; ++i) #define per(i, a, b) for(ll i = b ; i >= a ; --i) #define MOD 998244353 #define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next) #define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin) #define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\dabiao.txt", "wt", stdout) #define debug(x) cout<<x<<endl typedef __int128 ll; typedef unsigned long long ull; inline ll read(){ ll sign = 1, x = 0;char s = getchar(); while(s > ‘9‘ || s < ‘0‘ ){if(s == ‘-‘)sign = -1;s = getchar();} while(s >= ‘0‘ && s <= ‘9‘){x = (x << 3) + (x << 1) + s - ‘0‘;s = getchar();} return x * sign; }//快读 void write(ll x){ if(x < 0) putchar(‘-‘),x = -x; if(x / 10) write(x / 10); putchar(x % 10 + ‘0‘); } int kase,n,m; ll a[limit]; int f[limit]; ll l[limit],r[limit]; ll L,R; bool check(ll x){ ll tot = 0; ll sum = 0; rep(i,1,n){ tot += l[i] * x; if(l[i] * x > a[i])return false; ll cancontri = min((r[i] - l[i]) * x,a[i] - l[i] * x); sum += cancontri; } if(tot > R * x)return false; return tot + sum >= L * x; } int main() { #ifdef LOCAL FOPEN; #endif n = read(), L = read(),R = read(); ll down; down = 0; rep(i,1,n){ a[i] = read(); } rep(i,1,n){ l[i] = read(); r[i] = read(); down += l[i]; } ll pl = 0 , pr = 1e18; ll ans = 0; while (pl <= pr){ ll mid = pl + (pr - pl) / 2; if(check(mid)){ pl = mid + 1; ans = mid; }else{ pr = mid - 1; } } //check(4); write(ans); return 0; }
撒花！