A simple Blog for wyx I've been down the bottle hoping.
NOIP2016 Solution
发表于: | 分类: Oi | 评论:0 | 阅读:141

###D1T1
思博题
注意一下取模运算=0的情况就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100000+5;
const int M = 100000+5;
using namespace std;
 
inline int read()
{
    int 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<<1) + (x<<3) + ch - '0';ch = getchar(); }
    return x*f;
}
 
struct Person
{
    int pos;
    char str[11];
}a[N];
 
int main()
{
    int n = read(), m = read();
    for(int i=1;i<=n;++i) 
        scanf("%d%s",&a[i].pos,a[i].str);
    int now = 1;
    for(int i=1;i<=m;++i)
    {
        int opt = read(), x = read();
        if(!a[now].pos)
        {
            if(!opt)
            {
                now =((now - x)%n + n )% n;
                if(now == 0) now = n;
            }
            else
            {
                now =( now + x ) % n ;
                if(now == 0) now = n;
            }
        }
        else
        {
            if(!opt)
            {
                now = ( now + x ) % n;
                if(now == 0) now = n;
            }
            else
            {
                now = ((now - x) % n + n) % n;
                if(now == 0) now = n; 
            }
        }
    }
    printf("%s\n",a[now].str);
}
 

###D1T2

题意倒是真简洁
25暴力随便写吧
链可以右端点排序然后加上左端点的值,左端点排序加上右端点的值,注意一下起点和终点相同的情况分
S=1
显然只有一个点的深度等于观测时间才能看到,由于都是1出发所以直接差分
T=1
只有观测时间-观测深度=出发时间-出发深度才行,然后线段树合并
对于一个点,先递归下去,然后每次把所有儿子的线段树合并到自己身上,然后处理一下这个地方有几个观测的,然后查询观测时间-观测深度的值作为答案

100分
拆成两条链分别处理,把T=1的做两次就行了
时间复杂度是$O(nlog^2n)$的
能卡过去

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 300000+5;
const int M = N << 1;
const int Maxm = 21000000;
#define stack_size (20001000) 
int stack[stack_size],bak;  
using namespace std;

int head[N],fa[N][21];
int tr[Maxm],ls[Maxm],rs[Maxm];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int depth[N],root[N],q[N];

void DFS(int x)
{
    int l = 1;
    int r = 0;
    q[++r] = x;
    while(l<=r)
    {
        int tt = q[l++];
        for(int i=head[tt];i;i=edge[i].next)
            if(edge[i].to!=fa[tt][0])
            {
                depth[edge[i].to] = depth[tt] + 1;
                fa[edge[i].to][0] = tt;
                q[++r] = edge[i].to;
            }
    }
}

inline int Lca(int x,int y)
{
    if(depth[x] < depth[y]) swap(x,y);
    int tt = depth[x] - depth[y];
    for(int i=20;~i;--i)
        if((1<<i)&tt)
            x = fa[x][i];
    if(x==y) return x;
    for(int i=20;~i;--i)
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

inline int Up(int x,int F)
{
    for(int i=20;~i;--i)
        if(depth[fa[x][i]] > depth[F])
            x = fa[x][i];
    return x;
}

int sz;

inline char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
  
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}

void change(int &k,int l,int r,int pos,int x)
{
    if(!k) k = ++sz;
    if(l==r)
    {
        tr[k] += x;
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) change(ls[k],l,mid,pos,x);
    else change(rs[k],mid+1,r,pos,x);
}

int ask(int k,int l,int r,int pos)
{
    if(!k) return 0;
    if(l==r)return tr[k];
    int mid = (l+r) >> 1;
    if(pos <= mid)return ask(ls[k],l,mid,pos);
    else return ask(rs[k],mid+1,r,pos);
}

int merge(int x,int y)
{
    if(!x || !y) return x + y;  
    tr[x] = tr[x] + tr[y];
    ls[x] = merge(ls[x],ls[y]);
    rs[x] = merge(rs[x],rs[y]);
    return x;
}

int n,m;
int T[N],X[N],Y[N],L[N],val[N];
int ans[N];


struct Lux
{
    int Head[N];
    int cnt;
    struct tmp
    {
        int next,to;
        tmp () {}
        tmp (int _next,int _to)
        :next(_next),to(_to){}
    }edge[M];

    inline void add(int x,int y)
    {
        edge[++cnt] = tmp(Head[x],y);
        Head[x] = cnt;
    }
    void init()
    {
        memset(Head,0,sizeof Head);
        cnt = 0;
    }
}Add,Minus;


void DFS1(int x)
{
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x][0])
        {
            DFS1(edge[i].to);
            root[x] = merge(root[x],root[edge[i].to]);
        }
    for(int i=Add.Head[x];i;i=Add.edge[i].next)
        change(root[x],0,n<<1,Add.edge[i].to,1);
    //for(int i=0;i<Add[x].size();++i)
    //  change(root[x],0,2*n,Add[x][i],1);
    ans[x] += ask(root[x],0,n<<1,val[x]);
    for(int i=Minus.Head[x];i;i=Minus.edge[i].next)
        change(root[x],0,n<<1,Minus.edge[i].to,-1);
    //for(int i=0;i<Minus[x].size();++i)
    //  change(root[x],0,2*n,Minus[x][i],-1);
}

void CallDFS()    
{    
    __asm__ __volatile__    
    (    
        "mov %%esp,%0\n"
        "mov %1,%%esp\n"   
        :"=g"(bak)    
        :"g"(stack+stack_size-1)    
        :    
    );    

    DFS(1);
    for(int j=1;j<=19;++j)
        for(int i=1;i<=n;++i)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    for(int i=1;i<=n;++i) T[i] = read();
    for(int i=1;i<=m;++i) X[i] = read(), Y[i] = read();
    for(int i=1;i<=m;++i) L[i] =  Lca(X[i],Y[i]);
    for(int i=1;i<=n;++i) val[i] = T[i] + depth[i];

    for(int i=1;i<=m;++i)
    {
        Add.add(X[i],depth[X[i]]);
        //Add[X[i]].push_back(depth[X[i]]);
        Minus.add(L[i],depth[X[i]]);
        //Minus[L[i]].push_back(depth[X[i]]);
    }

    DFS1(1);    

    //for(int i=1;i<=n;++i) Add[i].clear(),Minus[i].clear();
    Add.init();
    Minus.init();

    memset(root,0,sizeof root);
    memset(tr,0,(sz+1)*sizeof(tr[0]));
    memset(ls,0,(sz+1)*sizeof(ls[0]));
    memset(rs,0,(sz+1)*sizeof(rs[0]));
    sz = 0;

    for(int i=1;i<=n;++i) val[i] = T[i] - depth[i] + n;
    for(int i=1;i<=m;++i)
        if(L[i] != Y[i])
        {
            int tt = depth[X[i]] + depth[Y[i]] - 2* depth[L[i]];
            //Add[Y[i]].push_back(n-depth[Y[i]]+tt);
            Add.add(Y[i],n-depth[Y[i]]+tt);
            L[i] = Up(Y[i],L[i]);
            //Minus[L[i]].push_back(n-depth[Y[i]]+tt);
            Minus.add(L[i],n-depth[Y[i]]+tt);
        }

    DFS1(1);   
    __asm__ __volatile__    
    (    
        "mov %0,%%esp\n"   
        :    
        :"g"(bak)    
        :    
    );    
}   

int main()
{
    depth[1] = 1;
    n = read(), m = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y = read();
        add(x,y);
    }
    CallDFS();
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
}

###D1T3
$F(i,j,k)$表示到达了第i节课,用了j次现在在0/1教室的最小期望。
显然是可以直接相加的
然后就瞎玩乱搞,注意特判

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 300+5;
const int MAXN = 2000+5;

using namespace std;

inline int read()
{
    int 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<<1) + (x<<3) + ch - '0'; ch = getchar();}
    return x*f;
} 

int mp[N][N];
double F[MAXN][MAXN][2];
int C[MAXN],D[MAXN];
double P[MAXN];

int main()
{
    int n = read(), m = read(), v = read() ,e = read(),x,y,z;
    memset(mp,0x3f,sizeof mp);
    
    for(int i=1;i<=n;++i) C[i] = read();
    for(int i=1;i<=n;++i) D[i] = read();
    for(int i=1;i<=n;++i) scanf("%lf",&P[i]);
    for(int i=1;i<=e;++i)
    {
        x = read(), y = read() ,z = read();
        mp[x][y] = mp[y][x] = min(mp[x][y],z);
    }
    
    for(int i=1;i<=v;++i) mp[i][i] = 0;
        
    for(int k=1;k<=v;++k)
        for(int i=1;i<=v;++i)
            for(int j=1;j<=v;++j)
                mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);
            
    for(int i=0;i<MAXN;++i)
        for(int j=0;j<MAXN;++j)
            F[i][j][0] = F[i][j][1] = 1e9;
        
    F[1][0][0] = F[1][1][1] = 0;
    
    for(int i=2;i<=n;++i)
        for(int j=0;j<=m;++j)
        {
            if(j == 0)
                F[i][j][0] = min(F[i][j][0],F[i-1][j][0] + mp[C[i-1]][C[i]]);
            else
            {
                F[i][j][0] = min(F[i][j][0],F[i-1][j][0] + mp[C[i-1]][C[i]]);
                F[i][j][0] = min(F[i][j][0],F[i-1][j][1] + P[i-1]*mp[D[i-1]][C[i]] + (1.0-P[i-1])*mp[C[i-1]][C[i]]);
                F[i][j][1] = min(F[i][j][1],F[i-1][j-1][0] + P[i]*mp[C[i-1]][D[i]] + (1.0-P[i])*mp[C[i-1]][C[i]]);
                F[i][j][1] = min(F[i][j][1],
                        F[i-1][j-1][1] + P[i]*(P[i-1]*mp[D[i-1]][D[i]] + (1.0-P[i-1])*mp[C[i-1]][D[i]]) +
                        (1.0-P[i])*(P[i-1]*mp[D[i-1]][C[i]] + (1.0-P[i-1])*mp[C[i-1]][C[i]])
                );
            }
        }
        
    double ans = 1e9+5;
    for(int i=0;i<=m;++i)
        for(int j=0;j<=1;++j)
            ans = min(ans,F[n][i][j]);
    printf("%.2lf",ans);
    
}

###D2T1
显然是可以$n^2$求一个组合数,然后求得时候直接在$mod\quad k$的意义下求就行了
最后统计一下前缀和

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 2000;
using namespace std;
int C[N+5][N+5],sum[N+5][N+5],mod;
  
void init()
{
    C[0][0] = 1;
    for(int i=1,j=1;i<=N;++i)
    {
        int cnt = 0;
        C[i][0] = 1;
        for(j=1;j<=i;++j)
        {
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
            if(C[i][j] == 0) cnt ++;
            sum[i][j] = sum[i-1][j] + cnt;
        }
        for(j=i+1;j<=N;++j)
            sum[i][j] = sum[i][j-1];
    }
}
  
inline int read()
{
    int 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<<1) + (x<<3) + ch - '0';ch = getchar();}
    return x*f;
}
  
int main()
{
    int T;
    cin >> T >> mod;
    init();
    while(T--)
    {
        int n = read(), m = read();
        if(m > n) m = n;
        printf("%d\n",sum[n][m]) ;
    }
}
  

###D2T2
维护三个队列,第一个队列是原始的元素,但是要排序
每次取出三个队列中较大的那个
然后把砍完的较大的放在第二个里面,较小的放在第三个里面
由于直接全部+q复杂度太大
我们可以把它-q等效一下
线性做法卡log系列

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 7500000;
using namespace std;
typedef long long LL;
 
int q[3][N];
int l[3],r[3];
 
inline int read()
{
    int 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<<1) + (x<<3) + ch - '0'; ch = getchar(); }
    return x*f;
}
 
bool cmp(const int &a,const int &b)
{
    return  a > b;
}
 
int main()
{
    int n = read(), m = read(), Q = read(), u = read(), v = read() ,T = read();
    l[0] = l[1] = l[2] = 1;
    for(int i=1;i<=n;++i) 
        q[0][++r[0]] = read();
    sort(q[0]+1,q[0]+r[0]+1,cmp);
    int tmp1,tmp2,a,b;
    for(int i=1;i<=m;++i)
    {
        int MAX = -2000000000,t;
        if(MAX < q[0][l[0]] && l[0] <= r[0]) t = 0, MAX = q[0][l[0]];
        if(MAX < q[1][l[1]] && l[1] <= r[1]) t = 1, MAX = q[1][l[1]];
        if(MAX < q[2][l[2]] && l[2] <= r[2]) t = 2, MAX = q[2][l[2]];
        l[t] ++;
        MAX = MAX + (i-1) * Q;
        tmp1 = (LL)MAX * u / v;
        tmp2 = MAX - tmp1;
        a = (tmp1 > tmp2 ? tmp1 : tmp2) ;
        b = tmp1 + tmp2 - a ;
        q[1][++r[1]] = a - i*Q;
        q[2][++r[2]] = b - i*Q;
        if(i % T == 0)
            if(i/T!=1)
                printf(" %d",MAX);
            else cout << MAX ;
 
    }
    puts("");   
 
    int tt = m * Q;
    for(int i=1;i<=m+n;++i)
    {
        int MAX = -2000000000,t;
        if(MAX < q[0][l[0]] && l[0] <= r[0]) t = 0, MAX = q[0][l[0]];
        if(MAX < q[1][l[1]] && l[1] <= r[1]) t = 1, MAX = q[1][l[1]];
        if(MAX < q[2][l[2]] && l[2] <= r[2]) t = 2, MAX = q[2][l[2]];
        l[t]++;
        if(i%T == 0)
            if(i/T!=1)
                printf(" %d",MAX + tt);
            else cout << MAX + tt;
    }
}

###D2T3
状压dp
把每个猪的状况用一个二进制表示一下
然后我们先$n^2$求一下每条抛物线和能经过的猪
然后每次或一下就行了
$F[i|sta[j]] = min{F[i]+1,F[i|sta[j]]}$
注意还有一种情况是单独一个鸟打一个猪
余姚的数据卡精度

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = (1<<18);
const double eps = 1e-9;
using namespace std;
int stack[154];
int F[N];
double X[N],Y[N];
 
bool equal(double a,double b)
{
    return fabs(a-b) < max(a,b) * eps;
}
 
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        memset(F,0x3f,sizeof F);F[0] = 0;
        memset(stack,0,sizeof stack);
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;++i)scanf("%lf%lf",&X[i],&Y[i]);
        int cnt = 0;
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
                if(X[i]!=X[j])
                {
                    double A = (Y[i]*X[j]-Y[j]*X[i]) / (X[i]*X[i]*X[j]-X[j]*X[j]*X[i]);
                    double B = (X[j]*X[j]*Y[i] - X[i]*X[i]*Y[j])/(X[i]*X[j]*X[j]-X[i]*X[i]*X[j]);
                    if(A >= 0) continue;
                    if(equal(A,0.0)) continue;
                    if(A >= -eps) continue;
                    if(B <= 0) continue;
                    if(equal(B,0.0)) continue;
                    if(B <= eps) continue;
                    cnt ++;
                    for(int k=1;k<=n;++k)
                        if(equal(A*X[k]*X[k]+B*X[k],Y[k]))
                            stack[cnt] |= (1<<(k-1));
                }
 
        int MAX = (1<<(n)) - 1;
        for(int i=0;i<=MAX;++i)
        {
            for(int k=0;k<n;++k)
                F[i|(1<<k)] = min(F[i|(1<<k)],F[i]+1);
            for(int j=1;j<=cnt;++j)
                F[i|stack[j]] = min(F[i|stack[j]],F[i] + 1);
        }
 
        cout << F[MAX] << endl;
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP