Hello , world

这只是个愉快的测试

纪念我滚粗的NOIP

最后一年,rp++

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<fstream>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105];
int min_ans;
void dfs(int x,int type)
{
    if (x>=min_ans) return;
    if (type==0)
    {
        //34567
        int i;
        int sum=0;
        for (i=3;i<=15;i++)
        {
            if (a[i]==0)
            {
                int j;
                for (j=i-sum;j<i;j++)
                {
                    a[j]++;
                }
                if (sum>5)
                {
                    i-=sum;
                }
                sum=0;
            }
            else
            {
                a[i]--;
                sum++;
                if (sum>=5) dfs(x+1,0);
            }
        }
        type=1;
    }
    if (type==1)
    {
        //334455
        int i;
        int sum=0;
        for (i=3;i<=15;i++)
        {
            if (a[i]<=1)
            {
                int j;
                for (j=i-sum;j<i;j++)
                {
                    a[j]+=2;
                }
                if (sum>3)
                {
                    i-=sum;
                }
                sum=0;
            }
            else
            {
                a[i]-=2;
                sum++;
                if (sum>=3) dfs(x+1,1);
            }
        }
        type=2;
    }
    if (type==2)
    {
        //333444
        int i;
        int sum=0;
        for (i=3;i<=15;i++)
        {
            if (a[i]<=2)
            {
                int j;
                for (j=i-sum;j<i;j++)
                {
                    a[j]+=3;
                }
                if (sum>2)
                {
                    i-=sum;
                }
                sum=0;
            }
            else
            {
                a[i]-=3;
                sum++;
                if (sum>=2) dfs(x+1,2);
            }
        }
        type=3;
    }
    if (type==3)
    {
        //44446688
        //3333AK
        int i;
        for (i=1;i<=14;i++)
        {
            if (a[i]>=4)
            {
                a[i]-=4;
                int j;
                for (j=0;j<=14;j++)
                {
                    if (a[j]>=2)
                    {
                        a[j]-=2;
                        dfs(x+1,3);     //444455
                        a[j]+=2;
                    }
                }
                for (j=1;j<=14;j++)
                {
                    if (a[j]>=2)
                    {
                        a[j]-=2;
                        int k;
                        for (k=j;k<=14;k++)
                        {
                            if (a[k]>=2)
                            {
                                a[k]-=2;
                                dfs(x+1,3);
                                a[k]+=2;
                            }
                        }
                        a[j]+=2;
                    }
                }
                for (j=0;j<=14;j++)
                {
                    if (a[j]>=1)
                    {
                        a[j]--;
                        int k;
                        for (k=j;k<=14;k++)
                        {
                            if (a[k]>=1)
                            {
                                a[k]--;
                                dfs(x+1,3);
                                a[k]++;
                            }
                        }
                        a[j]++;
                    }
                }
                a[i]+=4;
            }
        }
        type=4;
    }
    if (type==4)
    {
        int i;
        for (i=1;i<=14;i++)
        {
            if (a[i]>=3)
            {
                a[i]-=3;
                int j;
                for (j=1;j<=14;j++)
                {
                    if (a[j]>=2)
                    {
                        a[j]-=2;
                        dfs(x+1,4);
                        a[j]+=2;
                    }
                }
                for (j=0;j<=14;j++)
                {
                    if (a[j]>=1)
                    {
                        a[j]--;
                        dfs(x+1,4);
                        a[j]++;
                    }
                }
                a[i]+=3;
            }
        }
    }
    //left
    int j;
    for (j=0;j<=14;j++)
    {
        if (a[j]) x++;
    }
    min_ans=min(min_ans,x);
}
int main()
{
    freopen("landlords.in","r",stdin);
    freopen("landlords.out","w",stdout);
    int t,n;
    scanf("%d%d",&t,&n);
    int i;
    for (i=0;i<t;i++)
    {
        memset(a,0,sizeof(a));
        int j;
        for (j=0;j<n;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (x==1) x=14;
            if (x==2) x=1;
            a[x]++;
        }
        min_ans=14; //single
        dfs(0,0);
        printf("%d\n",min_ans);
    }
    return 0;
}

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<sstream>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[205][205][2];
int last_dp[205][205][2];
char a[1005];
char b[205];
const int modo=1000000007;
int main()
{
    freopen("substring.in","r",stdin);
    freopen("substring.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int i;
    scanf("%s%s",a,b);
    dp[0][0][0]=1;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=min(i,m-1);j>=0;j--)
        {
            int l=min(j,k-1);
            int * z=dp[j][l];
            int * y=dp[j+1][l];
            int * x=dp[j+1][l+1];
            for (l=min(j,k-1);l>=0;l--)
            {
                if (a[i]==b[j])
                {
                    x[1]+=z[0];
                    if (x[1]>=modo)
                    {
                        x[1]-=modo;
                    }
                    x[0]+=z[0];
                    if (x[0]>=modo)
                    {
                        x[0]-=modo;
                    }
                    y[1]+=z[1];
                    if (y[1]>=modo)
                    {
                        y[1]-=modo;
                    }
                    y[0]+=z[1];
                    if (y[0]>=modo)
                    {
                        y[0]-=modo;
                    }
                }
                z[1]=0;
                z-=2;
                y-=2;
                x-=2;
            }
        }
    }
    printf("%d\n",dp[m][k][0]);
    return 0;
}

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<sstream>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[205][205][2];
int last_dp[205][205][2];
char a[1005];
char b[205];
const int modo=1000000007;
int main()
{
    freopen("substring.in","r",stdin);
    freopen("substring.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int i;
    scanf("%s%s",a,b);
    dp[0][0][0]=1;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=min(i,m-1);j>=0;j--)
        {
            int l=min(j,k);
            int * z=dp[j][l];
            int * y=dp[j+1][l];
            int * x=dp[j+1][l+1];
            for (l=min(j,k);l>=0;l--)
            {
                if (a[i]==b[j])
                {
                    x[1]+=z[0];
                    if (x[1]>=modo)
                    {
                        x[1]-=modo;
                    }
                    x[0]+=z[0];
                    if (x[0]>=modo)
                    {
                        x[0]-=modo;
                    }
                    y[1]+=z[1];
                    if (y[1]>=modo)
                    {
                        y[1]-=modo;
                    }
                    y[0]+=z[1];
                    if (y[0]>=modo)
                    {
                        y[0]-=modo;
                    }
                }
                z[1]=0;
                z-=2;
                y-=2;
                x-=2;
            }
        }
    }
    printf("%d\n",dp[m][k][0]);
    return 0;
}

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<sstream>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=300005;
struct edge
{
    int y;
    int weight;
    int id;
    edge * next;
};
edge * li[maxn];
edge * new_edge()
{
    static edge a[600005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y,int z,int w)
{
    edge * t=new_edge();
    t->y=y;
    t->id=w;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z,int w)
{
    inserts(x,y,z,w);
    inserts(y,x,z,w);
}
int a[maxn],b[maxn];
int num;
int lenth[maxn];
bool visit[maxn];
bool tag[3005][3005];
int max_lenth=0;
struct node
{
    int x;
    int y;
    int lenth;
    friend bool operator < (const node &a,const node &b)
    {
        if (a.x!=b.x) return a.x<b.x;
        return a.y>b.y;
    }
    void read()
    {
        scanf("%d%d",&x,&y);
        x--;
        y--;
    }
};
node c[maxn];
int dfs(int x)
{
    visit[x]=true;
    if (((num==-1)&&(x==b[0]))||((num!=-1)&&(x==b[num])))
    {
        return 1;
    }
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (!visit[t->y])
        {
            if (dfs(t->y))
            {
                if (num==-1)
                {
                    lenth[0]+=t->weight;
                    max_lenth=max(max_lenth,t->weight);
                }
                else
                {
                    lenth[num]+=t->weight;
                    tag[num][t->id]=true;
                }
                return 1;
            }
        }
    }
    return 0;
}
int weight[maxn];
int main()
{
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    if (((n<=3000)&&(m<=3000))||(m==1))
    {
        int i;
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d%d",&x,&y,&weight[i]);
            x--;
            y--;
            insert_edge(x,y,weight[i],i);
        }
        for (i=0;i<m;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            a[i]--;
            b[i]--;
        }
        if (m==1)
        {
            memset(visit,false,sizeof(visit));
            num=-1;
            dfs(a[0]);
            printf("%d\n",lenth[0]-max_lenth);
        }
        else
        {
            int i;
            for (i=0;i<m;i++)
            {
                memset(visit,false,sizeof(visit));
                num=i;
                dfs(a[i]);
            }
            int min_ans=999999999;
            for (i=1;i<n;i++)
            {
                int max_ans=0;
                int j;
                for (j=0;j<m;j++)
                {
                    int t=lenth[j];
                    if (tag[j][i]) t-=weight[i];
                    max_ans=max(max_ans,t);
                }
                min_ans=min(min_ans,max_ans);
            }
            printf("%d\n",min_ans);
        }
    }
    else
    {
        static int sum[100005];
        int i;
        sum[0]=0;
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d%d%d",&x,&y,&weight[i]);
            sum[i]=sum[i-1]+weight[i];
        }
        for (i=0;i<m;i++)
        {
            c[i].read();
            if (c[i].x>c[i].y) swap(c[i].x,c[i].y);
            c[i].lenth=sum[c[i].y]-sum[c[i].x];
        }
        sort(c,c+m);
        int maxy=0;
        for (i=0;i<m;i++)
        {
            if (c[i].y<=maxy) c[i].x=1000000;
            maxy=max(c[i].y,maxy);
        }
        sort(c,c+m);
        for (i=0;i<m;i++)
        {
            if (c[i].x>=n) break;
        }
        m=i;
        static int max_sum[100005];
        max_sum[m]=0;
        for (i=m-1;i>=0;i--)
        {
            max_sum[i]=max(max_sum[i+1],c[i].lenth);
        }
        int max_val_sum=0;
        static int que[maxn];
        int front=0,rail=0;
        int min_ans=999999999;
        int now=0;
        int start=0;
        for (i=1;i<n;i++)
        {
            for (;(front<rail)&&(c[que[front]]).y<i;)
            {
                front++;
            }
            for (;c[start].y<i;)
            {
                max_val_sum=max(max_val_sum,c[start].lenth);
                start++;
            }
            for (;c[now].x<i;)
            {
                for (;front<rail;)
                {
                    if (c[que[rail-1]].lenth<c[now].lenth)
                    {
                        rail--;
                    }
                    else
                    {
                        break;
                    }
                }
                que[rail++]=now;
                now++;
            }
            min_ans=min(min_ans,max(max(max_val_sum,max_sum[now]),c[que[front]].lenth-weight[i]));
        }
        printf("%d\n",min_ans);
    }
    return 0;
}