CF Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) (C D E F 문제 풀이)

20908 단어 Codeforces욕심데이터 구조
CodeForces, Manthan, Codefest 19 (부분 문제 풀이 CDEF)
제목 링크
(경기 때 A, B 를 풀 고 C 를 보다 가 중간 에 포기 하고 싶 었 는데 갑자기 낙서 를 한 번 하고 넘 어가 서 D 를 써 보 니 생각 이 났 지만 시간 이 3 문제 로 끝나 지 않 았 다. B 문제 FST 를 생각 하지 못 했다)
C 매 직 그리드 (마구 잡 이)
제목:
n * 8727 ° n * n * n * 8727 ° n 의 행렬 을 구성 해 야 합 니 다. n n n 은 444 의 배수 로 모든 줄, 각 열의 차이 나 합 이 같 습 니 다.
생각:
바로 샘플 의 4 * 8727 ° 4 * 4 * 8727 ° 4 행렬 을 하나의 단원 으로 삼 아 행렬 을 계속 채 우 는 것 이다. 매번 원 행렬 단원 에 16, 32, 48... 16, 32, 48... 16, 32, 48 을 더 하면 된다.
코드:
#include
using namespace std;
const int N=2000;
int n;
int arr[N][N];
int cl(int x,int y){
    return (x/4)*(n/4)+(y/4);
}
int a[4][4]={
    {8,9,1,13},
    {3,12,7,5},
    {0,2,4,11},
    {6,10,15,14}
};
int main()
{
    cin>>n;
    for(int i=0;i

D Restore Permutation (선분 트 리)
제목:
하나의 배열 d [i] d [i] d [i] 를 지정 하고 1 - n 1 - n 1 - n 의 배열 S S S S 를 구성 하여 모든 i i 에 대해 d [i] = ＞ j S [j] (1 < = j < i & S [j] < S [i]) d [i] = \ sum{j}{S[j](1<=j생각:
처음에는 나무 모양 의 배열 을 사용 하려 고 했 지만 생각 이 뚜렷 하지 않 았 다. 나중에 동료 들 은 선분 나무 로 한다 고 말 했다. 순환 적 으로 1 - n 1 - n 1 - n 을 찾 았 고 디지털 i i 에 대해 d [i] d [i] d [i] 배열 에서 가장 오른쪽 에 있 는 0 의 위치 p i p 를 찾 았 다.i pi, 그럼 S p i S{p i} Spi 는 i i 를 위 한 것 이 며, d [i] d [i] d [i] 중의 [p i - n] [p - i - n] [pi - n] 을 i i i 를 빼 면 된다.
코드:
#include
#define ls x<<1
#define rs x<<1|1
#define ll long long
using namespace std;
const int N=2e5+10;
ll arr[N];
int n;
struct node{
    int l,r;
    ll sum,mi,f,siz;//       ，    0   ，      sum
}e[N*4];
void up(int x){
    e[x].mi=min(e[ls].mi,e[rs].mi);
    e[x].sum=e[ls].sum+e[rs].sum;
}
void down(int x){
    if(e[x].f==0)return ;
    ll f=e[x].f;
    e[ls].f+=f;e[rs].f+=f;
    e[ls].mi+=f;e[rs].mi+=f;
    e[ls].sum+=e[ls].siz*f;e[rs].sum+=e[rs].siz*f;
    e[x].f=0;
}
void built(int x,int l,int r){
    e[x].l=l;e[x].r=r;e[x].siz=(r-l+1);e[x].f=0;
    if(l==r){
        e[x].mi=e[x].sum=arr[l];
        return ;
    }
    int mid=(l+r)/2;
    built(ls,l,mid);built(rs,mid+1,r);
    up(x);
}
void adds(int x,int pos,ll v){//         ，       ，        
    if(e[x].l==e[x].r){
        e[x].mi=e[x].sum=v;
        return ;
    }
    down(x);
    int mid=(e[x].l+e[x].r)/2;
    if(pos<=mid)adds(ls,pos,v);
    else adds(rs,pos,v);
    up(x);
}
void addr(int x,int LL,int RR,ll v){//   
    if(LL>RR)return ;
    if(e[x].l>=LL&&e[x].r<=RR){
        e[x].sum+=e[x].siz*v;e[x].mi+=v;
        e[x].f+=v;
        return ;
    }
    down(x);
    int mid=(e[x].l+e[x].r)/2;
    if(LL<=mid)addr(ls,LL,RR,v);
    if(RR>mid)addr(rs,LL,RR,v);
    up(x);
}
int query(int x){
    if(e[x].l==e[x].r)return e[x].l;
    down(x);
    if(e[rs].mi==0)return query(rs);
    return query(ls);
}
int debug(int x,int pos){
    if(e[x].l==e[x].r)return e[x].mi;
    down(x);
    int mid=(e[x].l+e[x].r)/2;
    if(pos<=mid)return debug(ls,pos);
    else return debug(rs,pos);
}
int t[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
    built(1,1,n);
    for(int i=1;i<=n;i++){
        int p=query(1);//cout<

E Let Them Slide (ST表 + 差分)

题意：

给定一个 n ∗ m n*m n∗m 的矩阵，每一行有一个长度为 l e n i len_i leni​ 的数组 a i a_i ai​ ，可以左右移动，问通过数组的移动可以使得每一列的数字之和是多少(每一列单独计算)，可以移出矩阵，此时贡献为 0 0 0 。 ( − 1 e 9 < = a i < = 1 e 9 ) (-1e9<=a_i<=1e9) (−1e9<=ai​<=1e9)

思路：

首先在纸上模拟一个数组在矩阵中左右移动，可以发现对于矩阵的某一列 j j j ，对于第 i i i 个数组中可以移动到 j j j 列的范围 [ L , R ] [L,R] [L,R] 是确定的，那么这个数组对这一列的贡献就是 m a x ( a [ i ] , L < = i < = R ) max(a[i],L<=i<=R) max(a[i],L<=i<=R) ，但是如果对于每一个数组都扫一遍要 n ∗ m n*m n∗m 的复杂度必然超时，注意到 ∑ ( l e n i ) < = 1 e 6 \sum(len_i)<=1e6 ∑(leni​)<=1e6 。那我们对于 l e n i ∗ 2 > = m len_i*2>=m leni​∗2>=m 的数组，可以直接扫一遍，但是对于 l e n i ∗ 2 < m len_i*2<m leni​∗2<m 的情况，我们其实可以在纸上发现规律，从前往后，对于第 j   ( j < = l e n i ) j\ (j<=len_i) j (j<=leni​) 列，能产生贡献的必然是 [ 1 , j ] [1,j] [1,j] 从后往前也是类似，对于中间的部分发现他们的贡献区间都相同故使用差分数组维护区间加即可避免遍历所有列。

代码：

#include
#define ll long long
using namespace std;
const int N=2e6+10;
int n,m;
int st[N][21];
ll ans[N];
void cl(int x){//  ST 
    for(int i=1;i<=20;i++)
    for(int j=1;j<=x;j++)st[j][i]=max(st[j][i-1],st[j+(1<=m){//     
            for(int j=1;j<=m;j++){
                int l=len-m+j,r=j;int v=mi(max(l,1),min(len,r));//       
                if(l<1||r>len)v=max(v,0);//       
                ans[j]+=v;//  
                ans[j+1]-=v;
            }
        }else{
            int v1=0,v2=0;
            for(int j=1;j<=len;j++){
                v1=max(v1,st[j][0]);// k 
                v2=max(v2,st[len-j+1][0]);// k 
                ans[j]+=v1;ans[j+1]-=v1;
                ans[m-j+1]+=v2;ans[m-j+2]-=v2;
            }
            ans[len+1]+=v1;//            
            ans[m-len+1]-=v1;
        }
    }
    for(int i=1;i<=m;i++){
        ans[i]+=ans[i-1];//   
        printf("%lld ",ans[i]);
    }
    puts("");
}

F (비트 연산 + 욕심)
제목:
배열 지정, m a x 요구  ( a i   ∣   ( a j & a k )   )   (   i < j < k   ) max\ (a_i\ |\ (a_j \&a_k)\ )\ (\ i생각:
뒤에서 앞으로 모든 a i a i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i- a n ai + 1 - an 이 가 질 수 있 는 11 - 1 의 집합 은 한 위치 에서 11 - 1 이 두 번 나타 나 면 우 리 는 이 두 수 를 a j, a k a j, a k aj, ak 로 삼 아 a - a i ai 라 는 사람 을 1 로 계속 답 을 업데이트 하면 된다.
코드:
#include
using namespace std;
const int N=(1<<21);
int cnt[N],vis[N];
int n;
int a[N];
void ins(int x,int time){//        ，time    
    if(cnt[x]==2||vis[x]==time)return ;
    cnt[x]++;vis[x]=time;
    for(int i=20;i>=0;i--){
        if((x>>i)&1){
            ins(x^(1<=1;i--){//    
        int s=0;
        for(int j=20;j>=0;j--){//      
            if(((a[i]>>j)&1)==0){
                if(cnt[s|(1<

by YaoYaoLe
Yii 2 프레임 워 크 에 API 모듈 추가
알고리즘 훈련 출력 미터 자형

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage