平板键盘

NOIP2016增高组模拟赛

——By wangyurzee7

中文题目名称

纸牌

杯具

辣鸡

英文题目与子目录名

cards

cups

spicychicken

可执行文件名

cards

cups

spicychicken

输入文件名

cards.in

cups.in

spicychicken.in

输出文件名

cards.out

cups.out

spicychicken.out

每个测试点时限

1秒

1秒

1秒

测试点数目

16

10

10

每个测试点分值

6.25

10

10

题目类型

传统

传统

传统

运行内存上限

128M

256M

512M

留意:评测时不打开任何优化开关

 

 

纸牌

(cards.cpp/c/pas)

【问题讲述】

叶子选手wyz喜欢玩纸牌。

wyz有2n张纸牌,点数分别为1到2n。wyz要和您玩一个游乐,这一个娱乐中,每个人都会分到n张卡牌。游戏一共分为n轮,每轮你们都要出一张牌,点数大者获胜。

以卵击石的wyz觉得您很菜,于是每轮他都会先于你出牌,你可以按照他出的牌来做决定。

游戏起初了,你获得了您的牌,你现在想知道,你最多可以战胜几轮?

 

【输入格式】

输入到cards.in

第一行1个正整数n。

第2行到第n+1行每行一个正整数a[i],表示你的第i张牌的罗列。

 

【输出格式】

输出到cards.out

一行一个整数表示你最多可以战胜的轮数。

 

【输入输出样例】

cards.in

cards.out

2

1

4

1

 

【数据范围】

对于32.5%的数据,保证1<=n<=100

对于100%的数据,保证1<=n<=50,000

有限支撑数据的合法性,即你即不会获得再一次的牌,又不会得到过量点数范围的牌。

 

略水。。

27111葡京的网址 127111葡京的网址 2

#include <algorithm>
#include <cstdio>
#define N 50001

using namespace std;
int ans,cnt,n,a[N],b[N],f[N];
bool fw[N*2],vis[N*2];
void read(int &x)
{
    x=0;
    bool f=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=f?(~x+1):x;
}
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    freopen("cards.in","r",stdin);
    freopen("cards.out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++)
        read(a[i]),fw[a[i]]=1;
    sort(a+1,a+n+1);
    for(int i=1;i<=2*n;i++)
    if(!fw[i]) b[++cnt]=i;
    sort(b+1,b+1+cnt);
    for(int i=1;i<=cnt;i++)
    {
        int l=1,r=n,pos,p=0x7fffffff;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid]>b[i]&&!vis[mid])
            {
                if(a[mid]<p)
                {
                    p=a[mid];
                    pos=mid;
                }
                r=mid-1;
            }
            else l=mid+1;
        }
        vis[pos]=1;
        if(p!=0x7fffffff) ans++;
    }
    printf("%d",ans);
    return 0;
}

二分

 

 

杯具

(cups.cpp/c/pas)

【问题讲述】

杯具选手wyz喜欢玩杯具。

wyz有2个容量分别为n单位、m单位的没有刻度的杯具。wyz有t秒钟可以摆弄他的杯具。每一分钟,他都可以做上边4件事中的任意一件:

(1)用水龙头放满一个杯具。

(2)倒空一个杯具。

(3)把一个杯具里的水倒到另一个杯具里,直到一个杯具空了仍旧另一个杯具满了。(看哪一类情景头阵生)

(4)什么都不做。

wyz希望最终能得到d个单位的水,如若最后四个杯具中水量的总额为x,那么她的不喜出望外度就为|d-x|。

现行您想清楚,wyz的不满面红光度最小是有点。

 

【输入格式】

输入到cups.in

第一行4个整数n、m、t、d,分别表示三个杯具的容量、时间范围以及期望值。

 

【输出格式】

输出到cups.out

一行一个整数表示wyz的矮小不心旷神怡度。

 

【输入输出样例】

cups.in

cups.out

7 25 2 16

9

 

【数据范围】

对于10%的数据,保证t=1

对于20%的数据,保证t<=2

对于40%的数据,保证t<=4

对于100%的数据,保证1<=n,m<=100,1<=t<=100,1<=d<=200

 

 

dp题 ,完全不会写,只会打爆搜。。

27111葡京的网址 327111葡京的网址 4

#include <cstdio>
void read(int &x)
{
    x=0;bool f=0;char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=f?(~x)+1:x;
}
int h1,h2,n,m,t,d,ans=0x7fffffff;
int abs(int x) {return x>0?x:-x;} 
int min(int a,int b) {return a>b?b:a;} 
void dfs(int r1,int r2,int T)
{
    if(T==t)
    {
        ans=min(ans,abs(d-(r1+r2)));
        return;
    }
    for(int i=1;i<=4;i++)
    {
        if(i==1)
        {
            if(r1<n) dfs(n,r2,T+1);
            if(r2<n) dfs(r1,m,T+1);
            if(r1==n&&r2==m) dfs(r1,r2,T+1);
            else dfs(r1,r2,T+1);
        }
        if(i==2)
        {
            if(r1!=0) dfs(0,r2,T+1);
            if(r2!=0) dfs(r1,0,T+1);
            if(r1==0&&r2==0) dfs(r1,r2,T+1);
            else dfs(r1,r2,T+1);
        }
        if(i==3)
        {
            if(r1+r2<=n) dfs(r1+r2,0,T+1);
            if(n-r1>r2) dfs(n,r2-(n-r1),T+1);
            if(r1+r2<=m) dfs(0,r1+r2,T+1);
            if(m-r2>r1) dfs(r1-(m-r2),m,T+1);
            dfs(r1,r2,T+1);
        }
        if(i==4) dfs(r1,r2,T+1);
    }
}
int main()
{
    freopen("cups.in","r",stdin);
    freopen("cups.out","w",stdout);
    read(n);
    read(m);
    read(t);
    read(d);
    if(t==1)
    {
        printf("%d",min(abs(n-d),min(abs(m-d),d)));
        return 0;
    }
    else ans=min(abs(n-d),min(abs(m-d),d)),dfs(0,0,0);
    printf("%d",ans);
    return 0;
}

爆搜40分。

27111葡京的网址 527111葡京的网址 6

//This program is designed by KHAOCE_Hydroge the member of the standing committee in Handong provincial committee.#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#define N 101
#define M 101
#define D 201
#define T 101
using namespace std;

int dp[N][M][T];
int n, m, t, d;

int dfs(int x, int y, int z) {
    if (dp[x][y][z] != 0x3f3f3f3f) return dp[x][y][z];
    if (z > t) {
        return dp[x][y][z] = abs(x + y - d);
    }

    int xx = n - x;
    int yy = m - y;
    dp[x][y][z] = min(dp[x][y][z], dfs(n, y, z + 1));
    dp[x][y][z] = min(dp[x][y][z], dfs(x, m, z + 1));
    dp[x][y][z] = min(dp[x][y][z], dfs(0, y, z + 1));
    dp[x][y][z] = min(dp[x][y][z], dfs(x, 0, z + 1));
    dp[x][y][z] = min(dp[x][y][z], dfs(x, y, z + 1));
    if (x > yy)
        dp[x][y][z] = min(dp[x][y][z], dfs(x - yy, m, z + 1));
    if (x < yy)
        dp[x][y][z] = min(dp[x][y][z], dfs(0, y + x, z + 1));
    if (y > xx)
        dp[x][y][z] = min(dp[x][y][z], dfs(n, y - xx, z + 1));
    if (y < xx)
        dp[x][y][z] = min(dp[x][y][z], dfs(x + y, 0, z + 1));

    return dp[x][y][z];

}

int main() {
    freopen("cups.in", "r", stdin);
    freopen("cups.out", "w", stdout);
    memset(dp, 0x3f, sizeof dp);
    scanf("%d%d%d%d", &n, &m, &t, &d);
    dfs(0, 0, 1);
    printf("%d", dp[0][0][1]);
    return 0;
}

同班大佬的记念化搜索

27111葡京的网址, 

 

辣鸡

(spicychicken.cpp/c/pas)

【问题讲述】

辣鸡选手wyz喜欢辣鸡。

wyz在后院养了不少辣鸡。wyz的后院可以看做一个A*B的矩形,左下角的坐标为(0,0),右上角的坐标为(A,B)。

wyz还在后院里建了成百上千栅栏。有n个平行于y轴的栅栏a1..an,表示挡在(ai,0)到(ai,B)之间。有m个平行于x轴的栅栏b1..bn,表示挡在(0,bi)到(A,bi)之间。那样,平面被划成了(n+1)*(m+1)块辣鸡的活动区域。

为了便于辣鸡的活动,wyz现在要去掉某些栅栏的一片段,使得每一块活动区域都衔接。

而且,每一遍修改栅栏只好去掉从某个交点到另一个交点的一整段栅栏。举(打)个比(栗)方(子):

 

原本是如此的布局,经过改动可以变成那样:

 

如今,wyz想清楚,要使得每一块辣鸡活动区域都联通,最少必要去掉多长的栅栏。

 

【输入格式】

输入到spicychicken.in

率先行4个正整数A、B、n、m,描述了后院的轻重和二种栅栏的数量。

第2行到第n+1行,每行1个正整数,第i+1行的数描述了a[i]。

第n+2行到第n+m+1行,每行1个正整数,第n+i+1行的数描述了b[i]。

 

【输出格式】

输出到spicychicken.out

一行一个平头表示需求去掉的栅栏的细微长度总和。

 

【输入输出样例】

spicychicken.in

spicychicken.out

15 15 5 2

2

5

10

6

4

11

3

44

 

【数据范围】

对于10%的数据,A,B<=1000,n,m<=20

对于30%的数据,A,B<=1000,000,n*m<=25,000

对于40%的数据,n*m<=250,000

对于50%的数据,n*m<=4,000,000

对于100%的数据,1<=A,B<=1000,000,000,1<=n,m<=25,000

数据保障0<a[i]<A,0<b[i]<B

 

最小生成树

发表评论

电子邮件地址不会被公开。 必填项已用*标注