Codeforces Round #383 【总结】

总结一下这场。。。

搞起大号就崩了。。。

A题没啥问题。。通过电脑到手机上提交没啥大问题；

B题，讲个最严重的问题，也是最近以来最严重的问题，虽然我说你开了个数组，虽然这个数组是不是最终的答案数组，但是。。还是要考虑这个数组的范围啊，就像图的题目你为啥要注意邻接表结构体数组的大小啊，而且很恶心的是返回的是WA，而不是RE...注意每个变量的数据范围！！！还有就是题目注意点不搞好，i < j 啊！！！哎，wa11wa的整场心态崩掉。。然后C；

C题，本身因为CF卡爆不想打了，呵，CF卡爆是借口吧，主要还是心态。C知道题意，B还不知道pp没...然后C题直接乱搞，直接套强连通。。。虽然是可行的。。然而没求LCM。。。又是题意问题。。F**K! 好吧，D，E后来也没读。。。

打大号感觉真的是好烦，好多次都崩掉。。。都大二第一学期快过去了，还那么菜啊。。。。。。

--------------------------------------------------------

A题：

简单题，好像被HACK0的时候蛮多的，快速幂刚好完美躲避了。。。；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const int mod=10;

int cal(int g,int x)

{

    int ans=1;

        while(g)

        {

            if(g&1)

                ans=ans*x%mod;

            x=x*x%mod;

            g/=2;

        }

        return ans;

}

int main()

{

    int n;

    scanf("%d",&n);

    printf("%d\n",cal(n,8));

    return 0;

}

B题：

a^b=c;a^c=b;b^c=a;

求个对数，而且是 i < j,ans还会爆LL；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

const int N=1e5+10;

int n,x;

int a[N];

LL num[5000050];

map<PII,int>mp;

int main()

{

    scanf("%d%d",&n,&x);

    memset(num,0,sizeof(num));

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        num[a[i]]++;

    }

    int xx,yy;

    LL ans=0;

    mp.clear();

    for(int i=1;i<=n;i++)

    {

        xx=a[i];

        yy=a[i]^x;

        if(xx>yy)

            swap(xx,yy);

        if(mp[{xx,yy}]==0)

        {

            if(xx!=yy)

                ans+=num[xx]*num[yy];

            else

                ans+=(num[xx]-1)*num[xx]/2;

            mp[make_pair(xx,yy)]=1;

        }

    }

    printf("%I64d\n",ans);

    return 0;

}

C题：

直接套的是强连通，强连通分量元素只有一个的话且a[u]!=u那就是不满足，然后其实对每个点只有一条边，DFS一下也可以；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

const int INF=0x3f3f3f3f;

int n;

const int N=1e4+10;

const int M=5e4+10;

struct Node{

    int to;

    int next;

};

Node edge[M];         //链式前向星

int tol,head[M];

//dfn[v]: 顶点v被访问的时间；

//low[v]: 与顶点v邻接的未删除的顶点u的low[u]和low[v]的最小值，初始时low[v]=dfn[v];

//tp: 访问时间；

//Stack[] : 数组模拟栈，p: 栈的大小；

//vis[]: 顶点是否在栈中

//in[]: 缩点后的数组，cnt: 缩点后图中点的个数

//kt[]: 出度数组

int dfn[N],low[N],tp;

int Stack[N],p;

bool vis[N];

int in[N],cnt;

int kt[N];

int a[N];

int LCM(int xx,int yy)

{

    return (xx*yy/__gcd(xx,yy));

}

void add(int u,int v)

{

    edge[tol].to=v;

    edge[tol].next=head[u];

    head[u]=tol++;

}

void init()

{

    //初始化链式前向星

    tol=0;

    memset(head,-1,sizeof(head));

    memset(vis,0,sizeof(vis));          //初始化顶点都不在栈里面

    memset(dfn,0,sizeof(dfn));      //初始化访问时间为0

    tp=p=0;                                            //初始化时间和栈大小都为0

    cnt=0;                                              //缩点初始化，可以理解有cnt种点集

}

int flag;

int ans;

void Tarjan(int u)

{

    int v;

    dfn[u]=low[u]=++tp;     //初始化dfn=low=访问时间       尤其注意这个++tp还是tp++，我们初始化时间是0，所以之后访问到的时间就一定>0;

    Stack[++p]=u;                 //节点入栈

    vis[u]=true;                    //入栈标记

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        v=edge[i].to;

        if(!dfn[v])         //如果还为被访问

        {

            Tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(vis[v])    //在栈里；

            low[u]=min(low[u],dfn[v]);

    }

    int temp;

    int temp_num=0;

    if(dfn[u]==low[u])      //如果是这个强连通分量的根；

    {

        cnt++;                         //缩点标记

        while(1)

        {

            ++temp_num;

            temp=Stack[p];      //取元素

            vis[temp]=false;    //出栈标记

            in[temp]=cnt;       //缩点

            --p;

            if(temp==u)         //如果与u相等，退出

                break;

        }

        if(temp_num==1)

        {

            if(a[u]!=u)

                flag=false;

        }

        if(temp_num%2==0)

            temp_num/=2;

        ans=LCM(ans,temp_num);

    }

}

int main()

{

    int x;

    scanf("%d",&n);

    init();

    int flagflag=false;

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        a[i]=x;

        if(x!=i)

            flagflag=1;

        add(i,x);

    }

    if(!flagflag)

    {

        puts("1");

        return 0;

    }

    flag=true;

    ans=1;

    for(int i=1;i<=n;i++)

    {

        if(!dfn[i])     //如果还没有被访问过

            Tarjan(i);

    }

    if(!flag)

    {

        puts("-1");

        return 0;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

Codeforces Round #383 【总结】

最新文章

热门文章