[位运算] [搜索] [递推优化] [计算几何] TEST 2016.7.15

NOIP2014 提高组模拟试题

第一试试题

题目概况:

中文题目名称

合理种植

排队

科技节

源程序文件名

plant.pas/.c/.cpp

lineup.pas/.c/.cpp

scifest.pas/.c/.cpp

输入文件名

plant.in

lineup.in

scifest.in

输出文件名

plant.out

lineup.out

scifest.out

每个测试点时限

1s

1s

1s

测试点数目

10

10

10

每个测试点分值

10

10

10

内存上限

128MB

128MB

128MB

1.      合理种植

(plant.pas/.c/.cpp)

【问题描述】

大COS在氯铯石料场干了半年,受尽了劳苦,终于决定辞职。他来到表弟小cos的寒树中学,找到方克顺校长,希望寻个活干。

于是他如愿以偿接到了一个任务……

美丽寒树中学种有许多寒树。方克顺希望校园无论从什么角度看都是满眼寒树,因此他不希望有三棵甚至更多寒树种在一条直线上。现在他把校园里n棵寒树的坐标都给了大COS,让他数出存在多少多树共线情况。(若一条直线上有三棵或以上的树,则算出现一个多树共线情况。)

【输入】

输入文件名为plant.in。

第1行一个正整数n,表示寒树棵数。

接下来n行,每行两个非负整数x、y,表示一颗寒树的坐标。没有两颗寒树在同一位置。

【输出】

输出文件名为plant.out。

输出一个整数,表示存在多少多树共线情况。

【输入输出样例】

plant.in

plant.out

6

0 0

1 1

2 2

3 3

0 1

1 0

1

【数据范围】

对于30%的数据,有n≤10;

对于50%的数据,有n≤100;

对于100%的数据,有n≤1,000,0≤x,y≤10,000。

2.      排队

(lineup.pas/.c/.cpp)

【问题描述】

小sin所在的班有n名同学,正准备排成一列纵队,但他们不想按身高从矮到高排,那样太单调,太没个性。他们希望恰好有k对同学是高的在前,矮的在后,其余都是矮的在前,高的在后。如当n=5,k=3时,假设5人从矮到高分别标为1、2、3、4、5,则(1,5,2,3,4)、(2,3,1,5,4)、(3,1,4,2,5)都是可行的排法。小sin想知道总共有多少种可行排法。

【输入】

输入文件名为lineup.in。

一行两个整数n和k,意义见问题描述。

【输出】

输出文件名为lineup.out。

输出一个整数,表示可行排法数。由于结果可能很大,请输出排法数mod 1799999的值。

【输入输出样例】

lineup.in

lineup.out

5 3

15

【数据范围】

对于20%的数据,有n≤10,k≤40;

对于60%的数据,有n≤100,k≤500;

对于100%的数据,有n≤100,k≤n*(n-1)/2。

3.      科技节

(scifest.pas/.c/.cpp)

【问题描述】

一年一度的科技节即将到来。同学们报名各项活动的名单交到了方克顺校长那,结果校长一看皱了眉头:这帮学生热情竟然如此高涨,每个人都报那么多活动,还要不要认真学习了?!这样不行!……于是,校长要求减少一些活动,使每位学生只能参加一项(一名同学要参加某活动,必须已报名且该活动未被去掉)。当然,他也不希望哪位同学因此不能参加任何活动。他想知道自己的方案能否实行。

【输入】

输入文件名为scifest.in。

输入数据包括多组。

对于每组数据:

第一行两个正整数n和m,分别表示活动数和学生数。

接下来n行,每行m个为0或1的数。第i+1行第j列的数若为1,表示j同学报名参加活动i,否则表示j同学没有报名参加活动i。

【输出】

输出文件名为scifest.out。

对于每组数据输出一行,若校长方案可行则输出“Yes”,否则输出“No”。(均不包括引号)

【输入输出样例】

scifest.in

scifest.out

3 3

0 1 0

0 0 1

1 0 0

4 4

0 0 0 1

1 0 0 0

1 1 0 1

0 1 0 0

Yes

No

【数据范围】

对于20%的数据,n≤10,m≤200,数据组数≤10;

对于60%的数据,n≤16,m≤300,数据组数≤100;

对于100%的数据,n≤16,m≤300,数据组数≤1,000。

*************************************************Cut Line********************************************************

第一题

最初的O(2n2logn) 但是因为STL 的 map 卡常, T了一半

TLE代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
const int maxn=;
const double eps=1e-;
inline int dcmp(double x)
{
if(fabs(x) <= eps) return ;
return x>0.0? : -;
}
struct Line
{
double k,b;
Line (const double _k,const double _b) { k=_k;b=_b; }
bool operator == (const Line l) const
{
return !dcmp(k - l.k) && !dcmp(b - l.b);
}
bool operator < (const Line l) const
{
if(dcmp(k - l.k)==) return b < l.b;
return k < l.k;
}
};
struct Point
{
int x,y;
}point[maxn];
#define x(i) point[i].x
#define y(i) point[i].y
map <Line,int> g;
map <Line,int> ::iterator it;
int non[maxn*];
int main()
{
freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",&point[i].x,&point[i].y);
for(int i=;i<n;i++)
for(int j=i+;j<=n;j++)
{
if(x(i) == x(j))
{
non[x(i)]++;
continue;
}
double k=(double) (y(i)-y(j)) / (x(i)-x(j));
double b=(double) y(i) - k * x(i);
if(!g.count(Line(k,b))) g[Line(k,b)]=;
else g[Line(k,b)]++;
}
int ans=;
for(it=g.begin();it!=g.end();it++)
{
if((*it).second>=) ans++;
}
for(int i=;i<=;i++)
if(non[i]>=) ans++;
printf("%d",ans);
return ;
}

某神犇想出来的方法, 枚举所有三元组, 用前面去改变后面的判断

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
const int maxn=;
struct Point
{
int x,y;
}point[maxn];
#define x(i) point[i].x
#define y(i) point[i].y
int n;
typedef long long LL;
const LL base=(1ll<<); // must bigger than the 1e9 'coz the minimum of rake is 1/(9999*10000)
LL rake[maxn][maxn];
bool a[maxn][maxn];
int main()
{
freopen("plant.in","r",stdin) ;
freopen("plant.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",&x(i),&y(i));
for(int i=;i^n;i++)
for(int j=i+;j<=n;j++)
rake[i][j] = x(i)==x(j)? 1ll : base * (y(i)-y(j)) / (x(i)-x(j));
int ans=;
for(int i=;i^(n-);i++) // not strictly n^3
for(int j=i+;j^n;j++)
for(int k=j+;k<=n;k++)
if(rake[i][j] == rake[j][k])
if(a[i][j] || a[j][k] || a[i][k]) a[i][j] = a[j][k] = a[i][k] = true;
else ans++, a[i][j] = a[j][k] = a[i][k] = true;
printf("%d",ans);
return ;
}

再给个标程, 每次给个标记, 同一个斜率如果x坐标在左边则说明之前算过, 借此可以排除掉斜率相同算过的情况

标程:

#include <fstream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("plant.in");
ofstream fout("plant.out");
long n;
struct xxx{long x,y;} a[];
struct kk{long dx,dy;bool c;} k[];
bool operator <(kk k1,kk k2){
if (k1.dx==) return k2.dx<;
if (k2.dx==) return ;
return k2.dx*k1.dy<k1.dx*k2.dy;
}
bool operator ==(kk k1,kk k2){
if (k1.dx==||k2.dx==)
return k1.dx==k2.dx;
return k2.dx*k1.dy==k1.dx*k2.dy;
}
void init(){
long i;
fin>>n;
for (i=;i<n;i++)
fin>>a[i].x>>a[i].y;
}
void tr(){
long i,j,s,ans=;
bool f;
for (i=;i<n;i++){
for (j=;j<n;j++)
if (i!=j)
if (a[i].x==a[j].x){
k[j].dx=;
k[j].c=a[i].y<a[j].y;
}else{
k[j].dx=a[j].x-a[i].x;
k[j].dy=a[j].y-a[i].y;
if (k[j].dx<){
k[j].dx=-k[j].dx;
k[j].dy=-k[j].dy;
}
k[j].c=a[i].x<a[j].x;
}
for (j=i;j<n-;j++) k[j]=k[j+];
sort(k,k+n-);
f=; s=;
for (j=;j<n-;j++){
s++;
f=f&&k[j].c;
if (!(k[j]==k[j+])){
if (f&&s>) ans++;
f=; s=;
}
}
if (f&&k[n-].c&&s>) ans++;
}
fout<<ans;
}
int main(){
init();
tr();
fin.close();
fout.close();
return ;
}

第二题

动态规划但是可以用前缀和优化或者变换一下递推公式, 把相同部分替换掉

原来的 1AC 代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
const int maxn=;
const int mod=;
int n,k;
int f[maxn][maxn*maxn];
int main()
{
freopen("lineup.in","r",stdin);
freopen("lineup.out","w",stdout);
scanf("%d%d",&n,&k);
memset(f,-,sizeof(f));
for(int i=;i<=n;i++) f[i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=min(k,i*(i-)/);j++)
{
bool flag=true;
f[i][j]=;
for(int p=;p<=i-;p++)
{
if(!~f[i-][j-p]) continue;
flag=false;
f[i][j] += f[i-][j-p];
if(f[i][j]>=mod) f[i][j]%=mod;
}
if(flag) f[i][j]=-;
}
printf("%d",f[n][k]);
return ;
}

第三题

位运算 + 可行性剪枝(先考虑人数多的,容易更快发现冲突)

但是使用位向量生成法的话要一块一块地跳, 所以dfs更优

TLE代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<iomanip>
#include<ctime>
#include<climits>
#include<cctype>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
const int maxn=;
const int maxm=;
int n,m;
struct Activity
{
int s[]; // max of 300 evry int has 32 bits
int cnt;
bool operator < (const Activity t) const
{
return cnt >= t.cnt;
}
}act[maxn];
inline bool init()
{
if(!~scanf("%d%d",&n,&m)) return false;
memset(act,,sizeof(act));
for(int i=;i<=n;i++)
{
for(int j=;j^m;j++)
{
int tmp;
scanf("%d",&tmp);
if(tmp) act[i].s[j>>] |= ( << (j - (j>><<)) ),act[i].cnt++;
}
}
sort(act+,act+n+);
return true;
}
int now[];
inline bool check()
{
for(int j=; j^(m->>); j++)
if(now[j]^(0xffffffff)) return false;
if(!(m->>)) return now[] ^ ((<<m)-)? false : true;
else return now[m->>] ^ ((<<m--(m->>))-)? false : true;
}
bool bit()
{
for(int status=; status<=(<<n)-; )
{
memset(now,,sizeof(now));
bool flag=false;
int pos=;
for(int i=;i<=n;i++)
{
if(!(status & (<<i-))) continue; // don't forget to check here!!
for(int j=;j<=(m->>);j++)
if((now[j] & act[i].s[j]) ^ ) { flag=true;pos=i-;break; }
else now[j] |= act[i].s[j];
if(flag) break;
}
if(flag) // step by blocks!!
{
status %= (<<pos);
status += (<<pos-);
}
else status++;
if(!check()) continue;
else return true;
}
return false;
}
int main()
{
freopen("scifest.in","r",stdin);
freopen("scifest.out","w",stdout);
while(init())
if(bit()) printf("Yes\n");
else printf("No\n");
return ;
}

标程:

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
FILE *fin=fopen("scifest.in","r"),*fout=fopen("scifest.out","w");
long n,m;
long x[][],h[];
bool yes;
void init(){
long i,j,k,c;
memset(x,,sizeof(x));
for (i=;i<n;i++){
h[i]=k=;
for (j=;j<m;j++){
fscanf(fin,"%ld",&c);
if (c==){
x[i][k/]+=<<(k%);
h[i]++;
}
k++;
}
}
for (i=;i<n-;i++)
for (j=i+;j<n;j++)
if (h[i]<h[j]){
k=h[i]; h[i]=h[j]; h[j]=k;
for (c=;c<;c++){
k=x[i][c]; x[i][c]=x[j][c]; x[j][c]=k;
}
}
}
void tr(long p,long sx[],long sh){
if (p==n){
if (sh==m) yes=;
return;
}
long i,t[];
for (i=;i<;i++){
if ((sx[i]&x[p][i])>) break;
t[i]=sx[i]|x[p][i];
}
if (i==) tr(p+,t,sh+h[p]);
if (!yes) tr(p+,sx,sh);
}
int main(){
fscanf(fin,"%ld%ld",&n,&m);
do{
init();
yes=;
tr(,x[],);
if (yes) fprintf(fout,"Yes\n");
else fprintf(fout,"No\n");
fscanf(fin,"%ld%ld",&n,&m);
}while (!feof(fin));
fclose(fin);
fclose(fout);
return ;
}
上一篇:hdfs client access the hdfs cluster not in one domain


下一篇:oracle索引分类