Codeforces Round #197 (Div. 2) (C~E)

7331 단어 Codeforces
C:
욕심매번 가장 작은 조건 을 만족 시 키 는 분동 을 선택 하면 된다. 그러면 뒤에 더 많은 선택의 여 지 를 남 길 수 있다.
하지만 그것 만으로 도 작은 문제 가 있 습 니 다.그 때 는 그냥 욕심 내 서 끊 었 는데.........................................................
우 리 는 먼저 첫 번 째 분동 을 열 어 누 구 를 놓 아야 하 는 지 를 열 어 놓 고 욕심 을 부리 기 시작 해 야 한다.
예 를 들 면:
분동 이 있 습 니 다. 1, 2, 3. 4 개 넣 어야 합 니 다.
단순히 욕심 이 많 으 면 이렇게 선택 합 니 다: 1, 2, 3, *.(* 선택 할 수 없 음, 종 료 됨)
왼쪽 천평 은 1 + 3 = 4kg, 오른쪽 은 3kg 이다.
이때 분동 1, 2 를 선택 하면 4, 불법 보다 크 면 안 된다.선택 3, 앞 과 중복, 불법.
하지만 사실 우 리 는 2, 3, 2, 3 을 넣 을 수 있어 요. 풀 수 있어 요.
그래서 첫 번 째 저울추 를 들 고 욕심 을 내야 한다.
code:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

/*-------------------------Template----*/
#define N  50010
#define E  100010
#define ll long long
#define CB(x) ((x)*(x)*(x))
#define SQ(x)     ((x)*(x))
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define maxAry(a,n) max_element(a,a+(n))
#define minAry(a,n) min_element(a,a+(n))
typedef pair PI;
const int INF=0x3fffffff;
const int PRIME =999983;
const int MOD   =1000000007;
const int MULTI =1000000007;
const double EPS=1e-9;
/*----------------------end Template----*/

int n;
char s[16];
vector d,ans;
ll w[2];

bool cal(int x)
{
    int no=x;
    w[0]=d[x];
    w[1]=0;
    ans.clear();
    ans.push_back(d[x]);
    for(int i=2;i<=n;i++){
        bool tag=true;
        for(int j=0;j

D:
선분 수.
인접 한 두 개의 수 를 합 치 는 것 은 선분 나무 가 왼쪽 나무 와 오른쪽 나 무 를 합 치 는 것 과 같다.
각 노드 에 저 장 된 것 은 이 구간 이 하나의 수 를 합성 한 후의 값 이다.그리고 이 노드 의 두 개의 키 노드 가 어떤 연산 을 해 야 하 는 지 표시 합 니 다.
매번 값 을 수정 할 때마다 단일 업데이트 입 니 다.
바 이 너 리 한 분 한 분 을 따로 고려 할 수 있 습 니 다.(쓰 고 보 니 바 이 너 리 를 따로 생각 하지 않 고 바로 계산 하면 돼. 졸계 야...)
code:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

/*-------------------------Template----*/
#define N  131100
#define E  100010
#define ll long long
#define CB(x) ((x)*(x)*(x))
#define SQ(x)     ((x)*(x))
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define maxAry(a,n) max_element(a,a+(n))
#define minAry(a,n) min_element(a,a+(n))
typedef pair PI;
const int INF=0x3fffffff;
const int PRIME =999983;
const int MOD   =1000000007;
const int MULTI =1000000007;
const double EPS=1e-9;
/*----------------------end Template----*/

class segTree{
#define lson rt<<1
#define rson rt<<1|1
#define rtl seg[rt].l
#define rtr seg[rt].r
private:
    struct segment{
        int l,r,num[30],t;
    }seg[N<<2];
public:
    void pushup(int rt)
    {
        seg[rt].t=seg[lson].t^1;
        for(int i=0;i<30;i++){
            if(seg[rt].t)
                seg[rt].num[i]=seg[lson].num[i] | seg[rson].num[i];
            else
                seg[rt].num[i]=seg[lson].num[i] ^ seg[rson].num[i];
        }
    }
    void update(int x,int pos,int rt)
    {
        if(rtl==rtr){
            CLR(seg[rt].num,0);
            for(int i=0;i<30;i++)
                if((1<>1;
        if(pos<=mid) update(x,pos,lson);
        else update(x,pos,rson);
        pushup(rt);
    }
    int query()
    {
        int x=0;
        for(int i=0;i<30;i++) if(seg[1].num[i]){
            x+=1<>1;
        build(l,mid,lson);
        build(mid+1,r,rson);
        pushup(rt);
    }

}T;


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    n=pow(2.0,n);
    T.build(1,n,1);
    int p,x;
    while(m--){
        scanf("%d%d",&p,&x);
        T.update(x,p,1);
        printf("%d
", T.query()); } return 0; }

E:
맨 왼쪽 (오른쪽) 의 오 열 위 치 를 찾 을 때마다 이 위치 에 놓 아야 할 수 를 이 위치 로 되 돌려 줍 니 다.
몇 번 후에 반드시 원시 서열 로 돌아 갈 수 있다.그러나 문 제 는 최대 3 회 까지 조작 해 야 하기 때문에 dfs 가 3 회 이하 의 답 을 찾 아야 한다.
복잡 도 에 대해 서 는 이렇게 폭 수 를 하 는데 왜 TLE 를 못 해?
내 졸계 의 분석 아래:
원시 서열 에서 최대 3 을 뒤 집 으 면 가장 왼쪽 (오른쪽) 의 잘못된 배열 위치 가 많 지 않 고 x 개가 있다 고 가정 할 수 있다.
그래서 dfs 의 복잡 도 최 악 O (nx ^ 2 ^ 3).
x. 분명히 크 지 않 아 요. 느낌 이 그래 요.
그리고 3 번 이내 의 풀이 가 있 을 수 밖 에 없 기 때문에 몇 번 을 뒤 져 도 정확 한 위치 에 있 는 경우 가 많 을 것 이다.
사실 관건 은 최대 3 번 의 제한 이 복잡 도 를 낮 추고 3 번 이상 은 모두 잘 랐 으 며 3 번 이하 도 많 지 않다 는 것 이다.
이상 의 분석 은 보지 않 는 것 이 좋 습 니 다. 왜냐하면 완전히 제 가 추측 한 것 이기 때 문 입 니 다.
만약 큰 신 이 엄밀 한 분석 을 한다 면, 아래층 에서 약 한 요 리 를 알려 주 기 를 바란다.
code:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

/*-------------------------Template----*/
#define N  1024
#define E  100010
#define ll long long
#define CB(x) ((x)*(x)*(x))
#define SQ(x)     ((x)*(x))
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define maxAry(a,n) max_element(a,a+(n))
#define minAry(a,n) min_element(a,a+(n))
typedef pair PI;
const int INF=0x3fffffff;
const int PRIME =999983;
const int MOD   =1000000007;
const int MULTI =1000000007;
const double EPS=1e-9;
/*----------------------end Template----*/

int n,a[N];
vector ans;
bool tag=false;

int getL()
{
    for(int i=1;i<=n;i++) if(a[i]!=i) return i;
    return 0;
}

int getR()
{
    for(int i=n;i>=1;i--) if(a[i]!=i) return i;
    return 0;
}

int getPos(int x)
{
    for(int i=1;i<=n;i++) if(a[i]==x) return i;
}

void output()
{
    printf("%d
", ans.size()); for(int i=ans.size()-1;i>=0;i--){ printf("%d %d
", ans[i].first,ans[i].second); } } void dfs(int comd) { int l=getL(); if(l==0){ output(); tag=true; return; } if(comd==3) return ; int r=getPos(l); reverse(a+l,a+r+1); ans.push_back(make_pair(l,r)); dfs(comd+1); reverse(a+l,a+r+1); ans.pop_back(); if(tag) return ; r=getR(); l=getPos(r); reverse(a+l,a+r+1); ans.push_back(make_pair(l,r)); dfs(comd+1); reverse(a+l,a+r+1); ans.pop_back(); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs(0); return 0; }

좋은 웹페이지 즐겨찾기