小米ICPC第一场自闭记

这次终于找到了靠谱队友，比之前我做不出来==队友做不出来好太多了

昨天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题，dls&jlsの千层套路，比赛的时候试了好多都不能过，比赛之后凯哥跟我说了句换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题二分，这道题其实没那么复杂，我们每次肯定是贴着l放最合算，然后二分枚举放的组数x，每次如果组数贴着放都超过最大限制，那就不行，如果每次贴着l放都满足最低限制大L，那就可以，如果不是，那就看每个题能贡献的min(x*(r-l), ai)就行了，反正要么a[i】足够贴着r放，要么不够，然后判断下够不够x组就行了，问题大概是，1e5 * 1e9从1e14开始枚举会出现1e23的情况，ll就爆炸了，23333比赛的时候没想到这个，呜呜呜呜

#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;

}

撒花！

巴特西

小米ICPC第一场自闭记

最新文章

热门文章