NOIP 2016

玩具谜题

题目
模拟。

#include<iostream>
#include<vector>
using namespace std;
int n,m,p;
vector<string> work;
vector<bool> a;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        bool tmp;
        string tmp1;
        cin>>tmp>>tmp1;
        a.push_back(tmp);
        work.push_back(tmp1);
    }
    while(m--)
    {
        bool tmp;
        int num;
        cin>>tmp>>num;
        if(num)
            if(a[p]^tmp)
                p=(p+num)%n;
            else
                p=(p-num%n+n)%n;

    } 
    cout<<work[p];
    return 0;
}

组合数问题

题目
模拟。

#include<bits/stdc++.h>
using namespace std;
const int N=2001;
int C[N][N],sum[N][N];
inline int read()
{
    register int x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int main()
{
    register int t=read(),k=read();
    for(register int i=0;i<=2000;++i)
    {
        C[i][0]=1;
        for(register int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1]>=k? C[i-1][j]+C[i-1][j-1]-k:C[i-1][j]+C[i-1][j-1]);
    }
    for(register int i=2;i<=2000;++i)
    {
        for(register int j=1;j<=i;++j)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(C[i][j]==0);
        sum[i][i+1]=sum[i][i];
    }
    while(t--)
    {
        register int n=read(),m=read();
        if(m>n)
            m=n;
        cout<<sum[n][m]<<endl;
    }
    return 0;
}

愤怒的小鸟

题目
状压dp。
先预处理一下经过两点的抛物线上的点的集合。
对于一个集合\(S\)，确定一个最小的不在该集合内的\(i\)，再枚举一个\(j\)，进行转移。

#include<bits/stdc++.h>
#define db double
using namespace std;
const db eps=1e-8;
int t,n,m,S[19][19],low[1<<18],f[1<<18];
struct node{db x,y;}p[19];
void cal(db &a,db &b,db x,db y,db X,db Y){b=(Y*x*x-y*X*X)/((X*x)*(x-X)),a=(y-b*x)/(x*x);}
int min(int a,int b){return a<b? a:b;}
int main()
{
    int n,m,i,j,k;db a,b;
    for(i=0;i<1<<18;low[i]=j,++i) for(j=1;j<=18&&i&1<<j-1;++j);
    for(scanf("%d",&m);m;--m)
    {
    memset(S,0,sizeof S),memset(f,0x3f,sizeof f),f[0]=n=0,scanf("%d%d",&n,&i);
        for(i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y),S[i][i]=1<<i-1;
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
        {
                if(fabs(p[i].x-p[j].x)<eps) continue;
                cal(a,b,p[i].x,p[i].y,p[j].x,p[j].y);
                if(a>-eps) continue;
                for(k=1;k<=n;++k) if(fabs((a*p[k].x+b)*p[k].x-p[k].y)<eps) S[i][j]|=1<<k-1;
            }
        for(i=0;i<1<<n;++i) for(j=low[i],k=1;k<=n;++k) f[i|S[j][k]]=min(f[i|S[j][k]],f[i]+1);
        printf("%d\n",f[(1<<n)-1]);
    }
}

NOIP 2016

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11854910.html