Codeforces Round #634 (Div. 3)

A、B、C、D队内基本都过了 就不写了
E.Three Blocks Palindrome
给n个数,让你找一个子序列,要求由x个a,y个b,x个a构成,x,y大于等于0,a,b可以相等,求最长的子序列的长度
n=2000的就没啥好讲的了 ,暴力基本都能过。
n=2e5 使用前缀和去优化,先将前缀和处理出来,然后开200个vector去把值为i的所有位置存起来,然后去枚举a从1到vector的长度/2,然后选择最优的b,如何选呢,枚举a的时候,贪心的选择最左和最右,那么就可以得到y个b所在的区间 ,用前缀和求区间的最大值即可。需要注意的是,这个方法在所有数都只出现1次的情况下,会输出0,所以答案初始化为1(因为至少为1)。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int b[N][205];
void work()
{
    vector<int>v[205];
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=200;j++){
            b[i][j]=b[i-1][j];
        }
        b[i][a[i]]++;
    }
    int ans=1;
    for(int i=1;i<=200;i++){
        int len=v[i].size();
        for(int j=len/2;j>=1;j--){
            int l=v[i][j-1];
            int r=v[i][len-j]-1;
            int cnt=j*2;
            int maxx=0;
            for(int k=1;k<=200;k++){
                maxx=max(maxx,b[r][k]-b[l][k]);
            }
            ans=max(ans,maxx+cnt);
        }
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

F.Robots on a Grid
给n*m的方格,每个方格为黑白两色(0,1),然后每个方格上有L,R,U,D 4个字母中的一个,代表向左向右向上向下走,然后可以放任意个机器人,机器人只会按照当前方格的字母走,要求在无限步内,没有任意2个机器人同时到同一个格子上,问最多能放多少个机器人,在此基础上尽量将机器人放到黑色的格子上,问最多有多少个机器人可以在黑色格子上。
首先考虑在无限步后,所有机器人一定在环内,环可以有多个。那么最多能放的机器人数量就是所有环的长度之和,如果超过,那么在无限步后,一定会有2个机器人重合。那么我们先将所有的机器人都放在环上,对应环的每一格,然后找在无限次移动后重合的2个格子,那么就可以将这两个格子的颜色互换(因为在移动后是等价的),所以遇到环外为黑,环内为白的时候 将其互换,最后第二个的答案就是环内所有的黑色格子数。这题方法比较好想,但是比较难写。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
vector<char>v1[N];
vector<int>vis[N];
vector<int>vis1[N];
vector<pair<int,int> >pre[N];
vector<pair<int,int> >v2;
char c[4]={'L','R','U','D'};
int b[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
bool f=0;
int tmpx,tmpy;
int ans2;
int n,m;
int tot=0;
void dfs(int x,int y)
{
    if(vis[x][y]==0){
        vis[x][y]=tot;
    }else{
        v2.push_back({x,y});
        tmpx=x;
        tmpy=y;
        f=1;
        return;
    }
    for(int i=0;i<4;i++){
        if(v1[x][y]==c[i]){
            if(vis[x+b[i][0]][y+b[i][1]]!=0&&vis[x+b[i][0]][y+b[i][1]]<tot){
                return;
            }
            dfs(x+b[i][0],y+b[i][1]);
            if(f&&(x!=tmpx||y!=tmpy)){
                v2.push_back({x,y});
                pre[x+b[i][0]][y+b[i][1]]={x,y};
            }else{
                if(f){
                    pre[x+b[i][0]][y+b[i][1]]={x,y};
                }
                f=0;
            }
        }
    }
}
void dfs1(int x,int y,int tmpx,int tmpy)
{
    //printf("%d %d %d %d %d %d\n",x,y,tmpx,tmpy,v[x][y],v[tmpx][tmpy]);
    if(v[x][y]==0&&v[tmpx][tmpy]==1){
        ans2++;
        v[tmpx][tmpy]=0;
    }
    int u,v;
    for(int i=0;i<4;i++){
        u=x+b[i^1][0];
        v=y+b[i^1][1];
        //printf("%d %d %d %d %c\n",x,y,u,v,c[i]);
        if(u>=0&&u<n&&v>=0&&v<m&&!vis1[u][v]&&v1[u][v]==c[i]){
            dfs1(u,v,pre[tmpx][tmpy].fr,pre[tmpx][tmpy].sc);
        }
    }
}
void work()
{
    tot=0;
    scanf("%d%d",&n,&m);
    getchar();
    char x;
    for(int i=0;i<n;i++){
        v[i].resize(m);
        for(int j=0;j<m;j++){
            x=getchar();
            v[i][j]=x-'0';
        }
        getchar();
    }
    for(int i=0;i<n;i++){
        vis[i].resize(m);
        vis1[i].resize(m);
        for(int j=0;j<m;j++){
            vis[i][j]=0;
            vis1[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        v1[i].resize(m);
        for(int j=0;j<m;j++){
            x=getchar();
            v1[i][j]=x;
        }
        getchar();
    }
    for(int i=0;i<n;i++){
        pre[i].resize(m);
        for(int j=0;j<m;j++){
            pre[i][j]={0,0};
        }
    }
    v2.clear();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!vis[i][j]){
                tot++;
                dfs(i,j);
            }
        }
    }
    int ans1=v2.size();
    ans2=0;
    for(int i=0;i<ans1;i++){
        vis1[v2[i].fr][v2[i].sc]=1;
        if(v[v2[i].fr][v2[i].sc]==0){
            ans2++;
        }
    }
    for(int i=0;i<ans1;i++){
        dfs1(v2[i].fr,v2[i].sc,v2[i].fr,v2[i].sc);
    }
    printf("%d %d\n",ans1,ans2);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注