[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>=5&&s.substr(cur-5,5)=="erase") cur-=5;
        else if(cur>=5&&s.substr(cur-5,5)=="dream") cur-=5;
        else if(cur>=6&&s.substr(cur-6,6)=="eraser") cur-=6;    
        else if(cur>=7&&s.substr(cur-7,7)=="dreamer") cur-=7;
        else return puts("NO"),0;
    puts("YES");
    return 0;
}

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+10;
map<P,int> mp;
struct edge{int nxt,to;}e[MAXN<<2];
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=0;
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=esum;i++)
        scanf("%d%d",&x,&y),add_edge(x,y);
    for(int i=1;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=1;i<=n;i++)
        sum1[c1[i]]++,sum2[c2[i]]++;
    for(int i=1;i<=n;i++) 
        mp[P(c1[i],c2[i])]++;
    for(int i=1;i<=n;i++)
        printf("%d ",mp[P(c1[i],c2[i])]);
    
    return 0;
}

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-dle Y_jle 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+10;
struct edge{int nxt,to;}e[MAXN*8];//一定要开8倍空间 
struct data{int x,y,id;}dat[MAXN];
int n,d,a,b,x,y,head[MAXN],vis[MAXN],cnt[MAXN],tot=0;
ll res=0;

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+1,dat+n+1);
    int cur,lst,l,r;
    for(cur=lst=l=r=1;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-1;lst++) add_edge(dat[lst].id,dat[lst+1].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=1;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=1;i<=n;i++) swap(dat[i].x,dat[i].y);
    solve(d-1);
    
    dfs(a);printf("%lld",res);
    return 0;
}

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=3005,MOD=1e9+7;
char s[MAXN];
int n,m,x,y,pre[MAXN],lst[MAXN],dp[MAXN][MAXN];

int main()
{
    scanf("%d%d%s",&n,&m,s+1);s[n+1]='0';
    for(int i=1;i<=n+1;i++) //对第n+1项也要更新 
        pre[i]=(s[i]-'0')+pre[i-1],lst[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&x,&y),lst[x]=max(lst[x],y);
    for(int i=1;i<=n+1;i++) lst[i]=max(lst[i],lst[i-1]);
    
    dp[1][pre[lst[1]]]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
            if(dp[i][j])
            {
                int l=lst[i]+1,r=lst[i+1];
                if(j) (dp[i+1][pre[r]-pre[l-1]+j-1]+=dp[i][j])%=MOD;
                if(lst[i]-(i-1)-j) (dp[i+1][pre[r]-pre[l-1]+j]+=dp[i][j])%=MOD;
            }
    printf("%d",dp[n+1][0]);
    return 0;
}

Problem F