不知为啥没了居然…………感谢google快照，怕再出事我还是转到这一下吧…………
本来准备8题的，最后一题想出一个计算比较繁琐算完就直接很简单的coding的数学题，但想来想去出不来……于是就7题了。
特别水的题比较少，但我觉得如果第一题知道long long之后，出两题不应该是问题，但好像这样的大一新生也不算多。从排名上看，第一的卢大神是哈工大有情参赛的，让大家看看亚洲赛银牌的实力。东大第一名是唯一一个参加今年regional的10级罗耀燊，可以说就是现役选手中明年最有前途的了。新手第一名是总第三的10级邓攀峰，人家可是妹子，比大多数男人强多了。11级“新星”第一名是总第六的李金鹏，能过G题还是非常厉害的，前途无量~
详细最终排名和积分将在稍后发布。
A题就是long long的问题。刘老师说他第一周就留作业让大家查C/C++标准数据类型，软件的培训也提到过long long，确实不应该这么多人不知道。后来我怕大家都0题就直接告诉各位怎么写了，所以导致很多人都是1小时40分过的，这样谁之前没提交谁就靠前，所以这题的排名有点没含金量。不过总体上影响不大。
B题也很水，读入判断是否是11级，再判断是否重复和性别，输出即可。没做出来的再仔细看下代码有什么问题。
前两题属于必会也是基本所有11级只会的两题，确实整体难度对于新手大了点，这个怪我了。。。因为过于基础所以不发代码了，自己实现。
C题属于模拟题，思路很清晰，而且因为都是人脸的照片显然不存在俩眼睛在鼻子一头的情况，先把脸的轮廓判断出来再分别判断各个器官的条件就可以了。比赛的时候居然发现有人企图全输出No骗分，数据显然不会这么弱……
发下卢大神的代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int step[][2] = { {0,1} , {0,-1} ,{1, 0}, {-1,0} };
char mat[21][41];
bool chk[21][41];
char s1[41],s2[41],buf[41];
int Left[21],Right[21],h[41];
void dfs(int i,int j,int d)
{
if(chk[i][j]) return;
chk[i][j] = true;
mat[i][j] = ‘0’;
for(int k = 0 ; k < 4 ; k++)
{
int ty = i + step[k][0];
int tx = j + step[k][1];
if(ty>=0 && ty < 20 && tx>=0 && tx < 40)
{
if(d == 1)
{
if(mat[ty][tx] == ‘1’)
dfs(ty,tx,d);
}
else
{
if(mat[ty][tx] == ‘0’)
dfs(ty,tx,d);
else
dfs(ty,tx,1);
}
}
}
}
void debug()
{
for(int i = 0; i< 20 ; i ++)
printf(“%sn”,mat[i]);
}
void dfs(int i ,int j,vector<pair<int,int> >& v)
{
if(chk[i][j]) return;
chk[i][j] = true;
mat[i][j] = ‘ ‘;
v.push_back(make_pair(i ,j));
for(int k = 0 ; k < 4 ; k++)
{
int ty = i + step[k][0];
int tx = j + step[k][1];
if(ty>=0 && ty < 20 && tx>=0 && tx < 40)
{
if(mat[ty][tx] == ‘1’)
dfs(ty,tx,v);
}
}
}
void gao(int i,int j)
{
if(chk[i][j]) return;
chk[i][j] = true;
mat[i][j] =’ ‘;
Left[i] = min(Left[i],j);
Right[i] = max(Right[i],j);
for(int k = 0 ; k < 4 ; k++)
{
int ty = i + step[k][0];
int tx = j + step[k][1];
if(ty>=0 && ty < 20 && tx>=0 && tx < 40)
{
if(mat[ty][tx] == ‘1’)
gao(ty,tx);
}
}
}
void checkeyebrow(bool& ok,int& line)
{
for(; line < 20 ; line ++)
{
for(int i = 0 ; i < 40 ; i ++)
buf[40 – i – 1] = mat[line][i];
buf[40] = 0;
if(sscanf(mat[line],”%s %s”,s1,s2) == 2)
{
sscanf(mat[line],”%s”,s1);
sscanf(buf,”%s”,s2);
if(strcmp(s1,s2))
ok = false;
for(int i = 0 ; i < 40 ; i++)
mat[line][i] = ‘ ‘;
break;
}
}
}
void checkeye(bool& ok,int& line)
{
for(; line < 20 ; line ++)
{
if(sscanf(mat[line],”%s %s”,s1,s2) == 2)
{
vector< pair<int,int> > v1,v2;
for(int i = 0 ; i < 40 ; i ++)
{
if(mat[line][i] == ‘1’)
{
memset(chk,0,sizeof(chk));
dfs(line,i,v1);
break;
}
}
for(int i = 40 – 1 ; i >=0 ; i –)
{
if(mat[line][i] == ‘1’)
{
memset(chk,0,sizeof(chk));
dfs(line,i,v2);
break;
}
}
sort(v1.begin() , v1.end());
sort(v2.begin() , v2.end());
if(v1.size()!= v2.size())
{
ok = false;
return;
}
for(int i = 1; i < v1.size() ; i ++)
{
if( (v1[i].first – v1[0].first != v2[i].first – v2[0].first) || (v1[i].second – v1[0].second != v2[i].second – v2[0].second ))
{
ok = false;
break;
}
}
return;
}
}
}
void checknose(bool& ok,int& line)
{
for(; line < 20 ; line ++)
{
if(sscanf(mat[line],”%s”,s1) == 1)
{
for(int i = 0 ; i < 40 ; i++)
{
if(mat[line][i] == ‘1’)
{
memset(chk,0,sizeof(chk));
memset(Right,-1,sizeof(Right));
memset(Left,0x3f,sizeof(Left));
gao(line ,i);
for(int j = line + 1; j < 20; j ++)
{
if(Right[j] == -1)
break;
if( (Left[j] + Right[j]) != (Left[line] + Right[line]))
{
ok = false;
break;
}
}
return;
}
}
}
}
}
void checkmouth(bool& ok,int& line)
{
memset(h,-1,sizeof(h));
for(int i = 0 ; i < 20 ; i ++)
for(int j = 0; j < 40 ; j++)
if(mat[i][j] == ‘1’)
{
mat[i][j] =’ ‘;
if(h[j] == -1)
h[j] = i;
else
h[j] = min(h[i],i);
}
int i = 0;
while(h[i] == -1)
i++;
int j = i;
while(h[j] != -1)
j++;
j–;
if( (j – i) % 2 == 0)
{
int mid = (i + j) / 2;
if(h[i] >= h[mid] || h[j] >= mid)
{
ok = false;
}
}
else
{
int mid = (i + j) / 2;
if(h[i] >= h[mid] || h[j] >= mid)
{
ok = false;
}
mid = (i + j) / 2 + 1;
if(h[i] >= h[mid] || h[j] >= mid)
{
ok = false;
}
}
return;
}
int main()
{
int t;
scanf(“%d”,&t);
while(t–)
{
for(int i = 0; i< 20; i ++)
scanf(“%s”,mat[i]);
memset(chk,0,sizeof(chk));
dfs(0,0 , 0);
for(int i = 0 ; i < 20 ; i ++)
for(int j = 0 ; j < 40 ; j ++)
if(mat[i][j] == ‘0’)
mat[i][j] = ‘ ‘;
int line = 0;
bool ok = true;
checkeyebrow(ok,line);
//debug();
checkeye(ok,line);
//debug();
checknose(ok,line);
//debug();
checkmouth(ok,line);
//debug();
ok ? puts(“YES”) :puts(“No”);
}
return 0;
}
/**************************************************************
Problem: 1113
User: luyi0619
Language: C++
Result: Accepted
Time:1 ms
Memory:1264 kb
****************************************************************/
复制代码
D题就是个特别裸的DP有木有……大一不会的正常为啥没人过呢。、
N个人分成M组，子状态肯定就是少于N个人分成M-1组，决策是判断M-1组跟第M组在哪分界。因此最外层两个循环N和M，先后无所谓。
f[n][m]=max{f[k][m-1]+mul(k+1,n)}
mul表示从第k+1到第n个的乘积，显然枚举k从大往小就可以直接得到每一步的值不用额外算了，因此最后复杂度是n^2*m的。
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[100];
long long f[100][15];
int main()
{
int n,m;
while(scanf(“%d%d”,&n,&m)&&n>0)
{
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
scanf(“%d”,&a[i]);
}
f[1][1]=a[1];
for(int i=2;i<=n;i++)
f[i][1]=f[i-1][1]*a[i];
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
{
long long mul=1;
for(int k=i-1;k>=j-1;k–)
{
mul*=a[k+1];
f[i][j]=max(f[i][j],f[k][j-1]+mul);
}
}
printf(“%lldn”,f[n][m]);
}
return 0;
}
/**************************************************************
Problem: 1114
User: admin
Language: C++
Result: Accepted
Time:8 ms
Memory:1272 kb
****************************************************************/
复制代码
E题是裸最小生成树，只要会的都不应该做不出来。OIer如果不知道怎么用模版自己写也不应该是问题，就看能不能回忆起来或者最近有没有复习了……注意输入数据不一定非是整数。
#include<cstdio>
#include<iostream>
#include<math.h>
using namespace std;
double px[1005],py[1005];
double mat[1005][1005];
#define MAXN 1005
#define inf 1000000000
typedef double elem_t;
elem_t prim(int n,elem_t mat[][MAXN],int* pre){
elem_t min[MAXN],ret=0;
int v[MAXN],i,j,k;
for (i=0;i<n;i++)
min[i]=inf,v[i]=0,pre[i]=-1;
for (min[j=0]=0;j<n;j++){
for (k=-1,i=0;i<n;i++)
if (!v[i]&&(k==-1||min[i]<min[k]))
k=i;
for (v[k]=1,ret+=min[k],i=0;i<n;i++)
if (!v[i]&&mat[k][i]<min[i])
min[i]=mat[pre[i]=k][i];
}
return ret;
}
int main()
{
int n;
while(scanf(“%d”,&n)>0)
{
for(int i=0;i<n;i++)
scanf(“%lf%lf”,&px[i],&py[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
mat[i][j]=sqrt((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j]));
}
int pre[MAXN];
printf(“%.2fn”,prim(n,mat,pre));
}
return 0;
}
/**************************************************************
Problem: 1115
User: admin
Language: C++
Result: Accepted
Time:156 ms
Memory:9168 kb
****************************************************************/
复制代码
F题看上去特别复杂，实际上特别简单。看上去是计算几何，实际上等于模拟题。看上去不知道怎么找点的位置跟方向，但实际上显然临界点应至少跟两个多边形处于恰好相切的状态，或者说应该至少过其中两个多边形的某个顶点（想明白这步就不难了）。于是直接枚举两个多边形，每个多边形枚举一个顶点，过这俩点的直线先看是否过y轴特定区域，然后枚举其他多边形看几个相交。
罗耀燊的代码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define EX 10e-8
typedef struct {double x,y;} Point;
typedef struct {int p; Point point[100];} Polygon;
Polygon polygon[10000];
double y[10000];
int cmp(const void* _a,const void* _b)
{
if ((double*)_a-(double*)_b>0) return 1;
else return -1;
}
double det(double x1,double y1,double x2,double y2)
{
return x1*y2-x2*y1;
}
double cross(Point a,Point b,Point c)
{
return det(b.x-a.x,b.y-a.y,c.x-b.x,c.y-b.y);
}
int dblcmp(Point a,Point b,Point c)
{
if (fabs(cross(a,b,c))<EX) return 0;
else return cross(a,b,c)>0?1:-1;
}
int intersect(Point a,Point b,double x,double y)
{
Point c,d;
c.y=x; c.x=0;
d.y=y; d.x=100;
if (dblcmp(a,b,c)*dblcmp(a,b,d)<=0 && dblcmp(c,d,a)*dblcmp(c,d,b)<=0) return 1;
else return 0;
}
int check(Polygon p,double x,double y)
{
int i,flag=0;
Point a,b;
a = p.point[0];
for(i=1;i<p.p;i++)
{
if (intersect(p.point[i],a,x,y)==1) {flag=1;
break;}
a=p.point[i];
}
return flag;
}
int main()
{
int k,i,t,n,m,j,l,ans,max;
Point p;
scanf(“%d”,&t);
for(i=1;i<=t;i++)
{
scanf(“%d”,&n);
max=0;
m=0;
for(j=0;j<n;j++)
{
scanf(“%d”,&polygon[j].p);
for(l=0;l<polygon[j].p;l++)
{
scanf(“%lf%lf”,&polygon[j].point[l].x,&polygon[j].point[l].y);
y[m++]=polygon[j].point[l].y;
}
}
for(j=0;j<m;j++)
for(k=0;k<m;k++)
{
ans=0;
for(l=0;l<n;l++)
{
ans+=check(polygon[l],y[j],y[k]);
}
if (ans>max) max=ans;
}
printf(“Case %d:%dn”,i,max);
}
return 0;
}
/**************************************************************
Problem: 1116
User: Lyshen
Language: C++
Result: Accepted
Time:12 ms
Memory:16524 kb
****************************************************************/
复制代码
G题没想到这么多人在不会单调队列的情况下做出了类似的优化。此题原型是POJ某个题，我们数据应该更弱。首先纯枚举判断肯定是TLE，然后可以看到，每次只是增加一个数，删除一个数，那么删除之后最大（最大最小一样，所以算两次就可以，先按照最大讲）就可能改变，但我们不能只保存最大是多少，因为最大的一旦出了区域就不知道下一大的数该是什么。因此，可以维护一个队列，这个队列按顺序保存最大到最小的数字。可以看出，如果后插入的比之前插入的数要大，那么前面的数就没必要留着因为永远不会变成最大值。于是这个队列叫“单调队列”，每次插入之前都保证里面是单调递减的，而插入之前判断最后一个元素是否小于等于要插入的数，如果是则删除，不断删除直到都大于或者队列为空。这样每次查询直接返回队首，每次插入之前先删除需要删除的元素，再插入。
此外这题线段树好像可以，RMQ肯定可以但会慢一些。其他人想的可能是自己的各种优化方法，有的比我写的还快，如果思路跟这个不一样的话希望大家分享一下。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000005];
/*struct F
{
int a,i;
}*/
int f[3000005];
int main()
{
int n,k;
while(scanf(“%d%d”,&n,&k)>0)
{
for(int i=0;i<n;i++)
scanf(“%d”,&a[i]);
int l=0,r=-1;
memset(f,0,sizeof(f));
for(int i=0;i<k;i++)
{
while(r>=l&&a[i]<=a[f[r]])r–;
f[++r]=i;
}
printf(“%d”,a[f[0]]);
for(int i=k;i<n;i++)
{
while(l<=r&&f[l]+k-1<i)l++;
while(r>=l&&a[i]<=a[f[r]])r–;
f[++r]=i;
printf(” %d”,a[f[l]]);
}
printf(“n”);
l=0,r=-1;
memset(f,0,sizeof(f));
for(int i=0;i<k;i++)
{
while(r>=l&&a[i]>=a[f[r]])r–;
f[++r]=i;
}
printf(“%d”,a[f[0]]);
for(int i=k;i<n;i++)
{
while(l<=r&&f[l]+k-1<i)l++;
while(r>=l&&a[i]>=a[f[r]])r–;
f[++r]=i;
printf(” %d”,a[f[l]]);
}
printf(“n”);
}
return 0;
}
/**************************************************************
Problem: 1117
User: admin
Language: C++
Result: Accepted
Time:307 ms
Memory:16884 kb
****************************************************************/
复制代码
发表回复