「CF286X」Codeforces Round #176 (Div. 1)

2015年6月24日4,6482

A. Lucky Permutation

在第一位放一个2之后，可以得到1 2 n n-1

所以可以四个四个构造

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int p[100005];
int main()
{
    n=read();
    if(n%4>1){puts("-1");return 0;}
    for(int i=1;i<=n/2;i+=2)
        p[i]=i+1,p[i+1]=n-i+1,p[n-i+1]=n-i,p[n-i]=i;
    if(n&1)p[n/2+1]=n/2+1;
    for(int i=1;i<=n;i++)
        printf("%d ",p[i]);
    return 0;
}

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int p[100005];

int main()

{

n=read();

if(n%4>1){puts("-1");return 0;}

for(int i=1;i<=n/2;i+=2)

p[i]=i+1,p[i+1]=n-i+1,p[n-i+1]=n-i,p[n-i]=i;

if(n&1)p[n/2+1]=n/2+1;

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

printf("%d ",p[i]);

return 0;

}

B. Shifting

发现可以用队列来模拟。。。具体看代码

#include<map>
#include<cmath>
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
deque<int> dq;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)dq.push_back(i);
    for(int i=2;i<=n;i++)
    {
        int t=(n-1)/i*i;
        dq.push_back(dq[t]);
        while(t-i>=0)
        {
            dq[t]=dq[t-i];
            t-=i;
        }
        dq.pop_front();
    }
    for(int i=0;i<dq.size();i++)printf("%d ",dq[i]);
    return 0;
}

#include<map>

#include<cmath>

#include<deque>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

deque<int> dq;

int main()

{

n=read();

for(int i=1;i<=n;i++)dq.push_back(i);

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

{

int t=(n-1)/i*i;

dq.push_back(dq[t]);

while(t-i>=0)

{

dq[t]=dq[t-i];

t-=i;

}

dq.pop_front();

}

for(int i=0;i<dq.size();i++)printf("%d ",dq[i]);

return 0;

}

C. Main Sequence

从后往前贪心，尽量放左括号

#include<map>
#include<cmath>
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,top;
int a[1000005],b[1000005],st[1000005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        a[x]=-a[x];
    }
    for(int i=n;i;i--)
        if(a[i]!=st[top])
        {
            st[++top]=abs(a[i]);
            a[i]=-abs(a[i]);
        }
        else top--;
    if(top)puts("NO");
    else 
    {
        puts("YES");
        for(int i=1;i<=n;i++)printf("%d ",a[i]);
    }
    return 0;
}

#include<map>

#include<cmath>

#include<deque>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,top;

int a[1000005],b[1000005],st[1000005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

m=read();

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

{

int x=read();

a[x]=-a[x];

}

for(int i=n;i;i--)

if(a[i]!=st[top])

{

st[++top]=abs(a[i]);

a[i]=-abs(a[i]);

}

else top--;

if(top)puts("NO");

else

{

puts("YES");

for(int i=1;i<=n;i++)printf("%d ",a[i]);

}

return 0;

}

D. Tourists

先把线段剖成一些不相交的区间（可以用set或者线段树）

第二部英文题解讲的很清楚。。。

大概就是，对于每个区间，出发时间在ti-ri之前是不会受这个墙影响，时间在ti-ri到ri-li这段内每增加1，答案增加1

相当于是出发时间扫到ti-ri就获得一个答案增长速度，扫到另一个点把速度撤销

#include<map>
#include<set>
#include<cmath>
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,top,K;
int ans[200005];
struct data{
    int l,r,t;
}l[100005],q[200005];
struct event{
    int typ,t,v;
}e[600005];
set<pair<int,int> >st;
bool operator<(data a,data b)
{
    return a.t<b.t;
}
bool operator<(event a,event b)
{
    return a.t<b.t;
}
int main()
{
    m=read();n=read();
    for(int i=1;i<=n;i++)
        l[i].l=read(),l[i].r=read(),l[i].t=read();
    for(int i=1;i<=m;i++)
    {
        int x=read();
        e[++K]=(event){2,x,i};
    }
    sort(l+1,l+n+1);
    st.insert(make_pair(inf,inf));
    st.insert(make_pair(0,inf));
    st.insert(make_pair(0,0));
    for(int i=1;i<=n;i++)
    {
        pair<int,int>L,R,T;
        L=*--st.upper_bound(make_pair(l[i].l,inf));
        R=*--st.upper_bound(make_pair(l[i].r,inf));
        if(L==R)
        {
            if(l[i].l>=L.second||l[i].r<=L.first)continue;
            st.erase(L);
            l[i].l=max(l[i].l,L.first);
            l[i].r=min(l[i].r,L.second);
            q[++top]=l[i];
            if(L.first<l[i].l)st.insert(make_pair(L.first,l[i].l));
            if(L.second>l[i].r)st.insert(make_pair(l[i].r,L.second));
        }
        else 
        {
            for(T=*st.upper_bound(L);T!=R;T=*st.upper_bound(T))
            {
                q[++top]=(data){T.first,T.second,l[i].t};
                st.erase(T);                
            }
            if(l[i].l<L.second)
            {
                q[++top]=(data){max(L.first,l[i].l),L.second,l[i].t};
                st.erase(L);L.second=l[i].l;
                if(L.first<L.second)st.insert(L);
            }
            if(R.first<l[i].r)
            {
                q[++top]=(data){R.first,min(R.second,l[i].r),l[i].t};
                st.erase(R);R.first=l[i].r;
                if(R.first<R.second)st.insert(R);
            }
        }
    }
    for(int i=1;i<=top;i++)
    {
        e[++K]=(event){1,q[i].t-q[i].r,1};
        e[++K]=(event){1,q[i].t-q[i].l,-1};
    }
    sort(e+1,e+K+1);
    int tmp=0,v=0,last=0;
    for(int i=1;i<=K;i++)
    {
        if(e[i].typ==1)
        {
            tmp+=(e[i].t-last)*v;last=e[i].t;
            v+=e[i].v;
        }
        else ans[e[i].v]=tmp+(e[i].t-last)*v;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<map>

#include<set>

#include<cmath>

#include<deque>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,top,K;

int ans[200005];

struct data{

int l,r,t;

}l[100005],q[200005];

struct event{

int typ,t,v;

}e[600005];

set<pair<int,int> >st;

bool operator<(data a,data b)

{

return a.t<b.t;

}

bool operator<(event a,event b)

{

return a.t<b.t;

}

int main()

{

m=read();n=read();

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

l[i].l=read(),l[i].r=read(),l[i].t=read();

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

{

int x=read();

e[++K]=(event){2,x,i};

}

sort(l+1,l+n+1);

st.insert(make_pair(inf,inf));

st.insert(make_pair(0,inf));

st.insert(make_pair(0,0));

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

{

pair<int,int>L,R,T;

L=*--st.upper_bound(make_pair(l[i].l,inf));

R=*--st.upper_bound(make_pair(l[i].r,inf));

if(L==R)

{

if(l[i].l>=L.second||l[i].r<=L.first)continue;

st.erase(L);

l[i].l=max(l[i].l,L.first);

l[i].r=min(l[i].r,L.second);

q[++top]=l[i];

if(L.first<l[i].l)st.insert(make_pair(L.first,l[i].l));

if(L.second>l[i].r)st.insert(make_pair(l[i].r,L.second));

}

else

{

for(T=*st.upper_bound(L);T!=R;T=*st.upper_bound(T))

{

q[++top]=(data){T.first,T.second,l[i].t};

st.erase(T);

}

if(l[i].l<L.second)

{

q[++top]=(data){max(L.first,l[i].l),L.second,l[i].t};

st.erase(L);L.second=l[i].l;

if(L.first<L.second)st.insert(L);

}

if(R.first<l[i].r)

{

q[++top]=(data){R.first,min(R.second,l[i].r),l[i].t};

st.erase(R);R.first=l[i].r;

if(R.first<R.second)st.insert(R);

}

for(int i=1;i<=top;i++)

{

e[++K]=(event){1,q[i].t-q[i].r,1};

e[++K]=(event){1,q[i].t-q[i].l,-1};

}

sort(e+1,e+K+1);

int tmp=0,v=0,last=0;

for(int i=1;i<=K;i++)

{

if(e[i].typ==1)

{

tmp+=(e[i].t-last)*v;last=e[i].t;

v+=e[i].v;

}

else ans[e[i].v]=tmp+(e[i].t-last)*v;

}

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

printf("%d\n",ans[i]);

return 0;

}

« 「CF360X」Codeforces Round #210 (Div. 1) 「CF332X」Codeforces Round #193 (Div. 2) »

cyy489

请问大神，您对C++里的指针有没有什么经验吗？（您对指针怎么看得呢?）

hzwer

啊我是P+STL选手

hzwer.com _ Home | http://hzwer.com

「CF286X」Codeforces Round #176 (Div. 1)

分类目录

热门文章

Myfriends

近期评论