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
保证数据的合法性，即你即不会拿到重复的牌，又不会拿到超出点数范围的牌。
略水。。
#include <algorithm>
#include <cstdio>
#define N 50001 using namespace std;
int ans,cnt,n,a[N],b[N],f[N];
bool fw[N*],vis[N*];
void read(int &x)
{
x=;
bool f=;
char ch=getchar();
while(ch>''||ch<'')
{
if(ch=='-') f=;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
x=f?(~x+):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=;i<=n;i++)
read(a[i]),fw[a[i]]=;
sort(a+,a+n+);
for(int i=;i<=*n;i++)
if(!fw[i]) b[++cnt]=i;
sort(b+,b++cnt);
for(int i=;i<=cnt;i++)
{
int l=,r=n,pos,p=0x7fffffff;
while(l<=r)
{
int mid=(l+r)/;
if(a[mid]>b[i]&&!vis[mid])
{
if(a[mid]<p)
{
p=a[mid];
pos=mid;
}
r=mid-;
}
else l=mid+;
}
vis[pos]=;
if(p!=0x7fffffff) ans++;
}
printf("%d",ans);
return ;
}
二分
杯具
(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题 ，完全不会写，只会打爆搜。。
#include <cstdio>
void read(int &x)
{
x=;bool f=;char ch=getchar();
while(ch>''||ch<'')
{
if(ch=='-') f=;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
x=f?(~x)+:x;
}
int h1,h2,n,m,t,d,ans=0x7fffffff;
int abs(int x) {return x>?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=;i<=;i++)
{
if(i==)
{
if(r1<n) dfs(n,r2,T+);
if(r2<n) dfs(r1,m,T+);
if(r1==n&&r2==m) dfs(r1,r2,T+);
else dfs(r1,r2,T+);
}
if(i==)
{
if(r1!=) dfs(,r2,T+);
if(r2!=) dfs(r1,,T+);
if(r1==&&r2==) dfs(r1,r2,T+);
else dfs(r1,r2,T+);
}
if(i==)
{
if(r1+r2<=n) dfs(r1+r2,,T+);
if(n-r1>r2) dfs(n,r2-(n-r1),T+);
if(r1+r2<=m) dfs(,r1+r2,T+);
if(m-r2>r1) dfs(r1-(m-r2),m,T+);
dfs(r1,r2,T+);
}
if(i==) dfs(r1,r2,T+);
}
}
int main()
{
freopen("cups.in","r",stdin);
freopen("cups.out","w",stdout);
read(n);
read(m);
read(t);
read(d);
if(t==)
{
printf("%d",min(abs(n-d),min(abs(m-d),d)));
return ;
}
else ans=min(abs(n-d),min(abs(m-d),d)),dfs(,,);
printf("%d",ans);
return ;
}
爆搜40分。
//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 + ));
dp[x][y][z] = min(dp[x][y][z], dfs(x, m, z + ));
dp[x][y][z] = min(dp[x][y][z], dfs(, y, z + ));
dp[x][y][z] = min(dp[x][y][z], dfs(x, , z + ));
dp[x][y][z] = min(dp[x][y][z], dfs(x, y, z + ));
if (x > yy)
dp[x][y][z] = min(dp[x][y][z], dfs(x - yy, m, z + ));
if (x < yy)
dp[x][y][z] = min(dp[x][y][z], dfs(, y + x, z + ));
if (y > xx)
dp[x][y][z] = min(dp[x][y][z], dfs(n, y - xx, z + ));
if (y < xx)
dp[x][y][z] = min(dp[x][y][z], dfs(x + y, , z + )); 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(, , );
printf("%d", dp[][][]);
return ;
}
同班大佬的记忆化搜索
辣鸡
(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
最小生成树