[Atcoder Regular Contest 065] Tutorial

Link:

C：

最好采取逆序贪心，否则要多考虑好几种情况

（从前往后贪心的话不能无脑选“dreamer”，"er"可能为"erase"/"eraser"的前缀）

#include <bits/stdc++.h>

using namespace std;

string s;

int main()

{

    cin>>s;

    for(int cur=s.size();cur;)

        if(cur>=&&s.substr(cur-,)=="erase") cur-=;

        else if(cur>=&&s.substr(cur-,)=="dream") cur-=;

        else if(cur>=&&s.substr(cur-,)=="eraser") cur-=;

        else if(cur>=&&s.substr(cur-,)=="dreamer") cur-=;

        else return puts("NO"),;

    puts("YES");

    return ;

}

Problem C

注意：$strncpy$和$s.substr()$的第三个参数为长度

D：

题意：求与点$i$在图$G1$和图$G2$中的连通块序号均相同的点的个数

设1个点的序号对为$(a,b)$，其实就是求每对$(a,b)$的个数

然而我一开始沙茶得以为只能$O(n^2)$来统计……

明显用上$set$就只要$O(m*log(n))$了嘛，多维的统计都可以用$set$优化！

先跑两遍$dfs$求出每个点的$(a,b)$，再利用$set$优化$pair$的统计就好了

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

const int MAXN=2e5+;

map<P,int> mp;

struct edge{int nxt,to;}e[MAXN<<];

int c1[MAXN],c2[MAXN],sum1[MAXN],sum2[MAXN];

int n,k,l,x,y,head[MAXN],vis[MAXN],res[MAXN],tot,cnt;

void add_edge(int from,int to)

{

    e[++tot].nxt=head[from];e[tot].to=to;head[from]=tot;

    e[++tot].nxt=head[to];e[tot].to=from;head[to]=tot;

}

void dfs(int x,int c,int* col)

{

    vis[x]=true;col[x]=c;

    for(int i=head[x];i;i=e[i].nxt)

        if(!vis[e[i].to]) dfs(e[i].to,c,col);

}

void solve(int esum,int* col)

{

    tot=cnt=;

    memset(head,,sizeof(head));

    memset(vis,false,sizeof(vis));

    for(int i=;i<=esum;i++)

        scanf("%d%d",&x,&y),add_edge(x,y);

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

        if(!vis[i]) dfs(i,++cnt,col);

}

int main()

{

    scanf("%d%d%d",&n,&k,&l);

    memset(res,0x3f,sizeof(res));

    solve(k,c1);solve(l,c2);

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

        sum1[c1[i]]++,sum2[c2[i]]++;

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

        mp[P(c1[i],c2[i])]++;

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

        printf("%d ",mp[P(c1[i],c2[i])]);

    return ;

}

Problem D

如果只求连通块最好使用并查集

提升效率并能减少代码量

E：

好像题目中专门提到曼哈顿/切比雪夫距离的任意一个往令一个想就对了……

设$a,b$两点间的初始距离为$d$，那么将所有距离为$d$的两点都连边，找到$a$所在的连通块即可

但曼哈顿距离涉及到了两个量，很难进行统一处理，因此要转换成切比雪夫距离

于是问题转化为将$max(|X_i-X_j|,|Y_i-Y_j|)=d$的$i,j$连边

明显可以排序后采取二分的方式，对于每个$X_i$，找到$X_j=X_i+d$中符合$Y_i-d\le Y_j\le Y_i+d$的点的个数，记为$cnt[i]$

接下来将$X_i$与$Y_i$交换后进行相同的操作，只不过要排除$|X_i-X_j|=|Y_i-Y_j|=d$的情况

最后$dfs$求出$a$所在连通块中$cnt$的总和$res=\sum cnt[i]$

要注意连边的细节：不能暴力连边，那样复杂度变为了$O(n^2)$

可以发现每次是向一个区间连边，且只要保证连通性不变，因此只要将区间连成一条链就行了！复杂度为$O(n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN=1e5+;

struct edge{int nxt,to;}e[MAXN*];//一定要开8倍空间

struct data{int x,y,id;}dat[MAXN];

int n,d,a,b,x,y,head[MAXN],vis[MAXN],cnt[MAXN],tot=;

ll res=;

void add_edge(int from,int to)

{

    e[++tot].nxt=head[from];e[tot].to=to;head[from]=tot;

    e[++tot].nxt=head[to];e[tot].to=from;head[to]=tot;

}

bool operator < (data a,data b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}

void solve(int k)

{

    sort(dat+,dat+n+);

    int cur,lst,l,r;

    for(cur=lst=l=r=;cur<=n;cur++)

    {

        while((dat[l].x<dat[cur].x+d||dat[l].x==dat[cur].x+d&&dat[l].y<dat[cur].y-k)&&l<=n) l++;

        while((dat[r].x<dat[cur].x+d||dat[r].x==dat[cur].x+d&&dat[r].y<=dat[cur].y+k)&&r<=n) r++;

        if(l>n) break;

        cnt[dat[cur].id]+=r-l;lst=max(lst,l);

        if(lst>=r) continue;

        add_edge(dat[cur].id,dat[lst].id);

        for(;lst<r-;lst++) add_edge(dat[lst].id,dat[lst+].id);

    }

}

void dfs(int x)

{

    vis[x]=true;res+=cnt[x];

    for(int i=head[x];i;i=e[i].nxt)

        if(!vis[e[i].to]) dfs(e[i].to);

}

int main()

{

    scanf("%d%d%d",&n,&a,&b);

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

        scanf("%d%d",&x,&y),dat[i]={x+y,x-y,i};

    d=max(abs(dat[a].x-dat[b].x),abs(dat[a].y-dat[b].y));

    solve(d);

    for(int i=;i<=n;i++) swap(dat[i].x,dat[i].y);

    solve(d-);

    dfs(a);printf("%lld",res);

    return ;

}

Problem E

Tip:此题边集数组要开8倍空间，但我觉得4倍就够了？跪求神犇们指点啊……

F：

对于每个点而言，其实只要关心其能翻转到的最右位置就好了，中间重复的翻转可以不管

于是可以先求出$lst[i]$表示第$i$位能翻转到的最右位置

令$dp[i][j]$为已经确定前$i-1$位，还有$j$个1可以自由支配时的方案数

常规地分第$i$位选$0/1$递推即可，$dp[n+1][0]$即为答案

#include <bits/stdc++.h>

using namespace std;

const int MAXN=,MOD=1e9+;

char s[MAXN];

int n,m,x,y,pre[MAXN],lst[MAXN],dp[MAXN][MAXN];

int main()

{

    scanf("%d%d%s",&n,&m,s+);s[n+]='';

    for(int i=;i<=n+;i++) //对第n+1项也要更新

        pre[i]=(s[i]-'')+pre[i-],lst[i]=i;

    for(int i=;i<=m;i++)

        scanf("%d%d",&x,&y),lst[x]=max(lst[x],y);

    for(int i=;i<=n+;i++) lst[i]=max(lst[i],lst[i-]);

    dp[][pre[lst[]]]=;

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

        for(int j=;j<=n;j++)

            if(dp[i][j])

            {

                int l=lst[i]+,r=lst[i+];

                if(j) (dp[i+][pre[r]-pre[l-]+j-]+=dp[i][j])%=MOD;

                if(lst[i]-(i-)-j) (dp[i+][pre[r]-pre[l-]+j]+=dp[i][j])%=MOD;

            }

    printf("%d",dp[n+][]);

    return ;

}

Problem F

巴特西

[Atcoder Regular Contest 065] Tutorial

Link:

C：

D：

E：

F：

最新文章

热门文章