BZOJ1016最小生成树计数
最近的真．NOIP模拟题

SGU乱做

HJWJBSR posted @ 2015年7月22日 14:49 in 题解 , 498 阅读

虽然比较晚了

但是听说SGU质量都比较好，所以开刷了。P.S.感觉SGU的乱搞题比较多啊，真是开心。

upd:en没错这东西已经坑掉了。。

101：maya第二题劳资就不会做，一开始想到了是要搞成若干个环加一条链，但是不知道怎么找无向图中的环。然后发现网上都使用了一个神奇的DFS，因为DFS未走过的边，从起点开始第一次无法继续递归只会是到另外一个奇度数点或者自己，所以递归时先递归所到达的点再记录边，这样记录的边回是连续的。然后判断有没有解就是连通性和点度数判断。具体看代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2005
int c[N][2],fi[N],n,m=-1,li[N],ss=1,cnt=0,s[N];bool b[N];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int y,int x)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;s[x]++;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;s[y]++;
 }
void DFF(int x)
 {
 	b[x]=1;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (!b[c[i][0]]) DFF(c[i][0]);
 	return;
 }
bool Check()
 {
 	for (int i=0;i<=6;i++)
 	 if (fi[i]&&!b[i]) {DFF(i);break;}
    for (int i=0;i<=6;i++)
     if (fi[i]&&!b[i]) return 1;
    for (int i=0,j=0;i<=6;i++)
     {
     	j+=s[i]&1;
     	if (s[i]&1) m=i;
     	if (m==-1&&s[i]) m=i;
     	if (j>2) return 1;
     }
    memset(b,0,sizeof(b));
    return 0;
 }
void DFS(int x)
 {
 	for (int i=fi[x];i;i=c[i][1])
 	 if (!b[i])
 	   b[i]=b[i^1]=1,DFS(c[i][0]),li[++cnt]=i;
 	return;
 }
int main()
 {
 	n=Read();
 	for (int i=1;i<=n;i++) Line(Read(),Read());
 	if (Check()) puts("No solution");else
 	 {
 	 	DFS(m);
 	 	for (int i=1;i<=cnt;i++)
 	 	 printf("%d ",li[i] >> 1),
 	 	 putchar(li[i]&1?'+':'-'),putchar('\n');
 	 }
    return 0;
 }

108：本来以为O(n)会挂，都想要分块打表了，没想到筛是可以过的。话说内存卡的丧心病狂

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5050
#define M 150
#define fr first
#define sc second
pair <int,int> b[N];
int n,m,s=0,v=0,cnt=0,c[N],d[N];bool a[M];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
int main()
 {
 	n=Read();m=Read();
 	for (int i=1;i<=m;i++) b[i].fr=Read(),b[i].sc=i;
 	sort(b+1,b+m+1);
 	for (int i=1;i<=n;i++)
 	 {
 	    int j=0,k=i,l=i%64;
 	    while (k) j+=k%10,k/=10;
 	 	a[(j+i)%64]=1;
 	 	if (!a[l]) s++;
 	 	while (!a[l]&&s==b[v+1].fr) c[++v]=i;
 	 	a[l]=0;
 	 }
 	cout <<s<<endl;
 	for (int i=1;i<=m;i++) d[b[i].sc]=c[i];
 	for (int i=1;i<m;i++)
 	 printf("%d ",d[i]);
 	printf("%d\n",d[m]);
 	return 0;
 }

SGU109：构造，乱搞。

SGU110：反正是一堆向量在乱搞，可以推出来。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
#define eps 1e-6
#define INF 0x7f7f7f7f
struct Point
 {
 	double x,y,z;
 } a[N],S,T;
double r[N];
int n,m;
Point operator+ (const Point &x,const Point &y)
 {return (Point){x.x+y.x,x.y+y.y,x.z+y.z};}
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y,x.z-y.z};}
Point operator* (const Point &x,const double &y)
 {return (Point){x.x*y,x.y*y,x.z*y};}
inline double min(double x,double y)
 {return x<y?x:y;}
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y)+sqr(x.z-y.z));}
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
Point Vertical(Point x,Point y,Point z)
 {
 	double q=dis(x,y),w=dis(y,z),e;
 	e=(sqr(q)+sqr(w)-sqr(dis(x,z)))/(2*q*w);
 	return y+(z-y)*(q*e/w);
 }
Point Intersect(Point x,Point y,Point z,double u)
 {
 	double q=dis(x,y),w=dis(y,z),e=q-sqrt(sqr(u)-sqr(w));
 	return x+(y-x)*(e/q);
 }
int main()
 {
 	n=Read();
 	for (int i=1;i<=n;i++)
 	  a[i].x=Read(),a[i].y=Read(),a[i].z=Read(),r[i]=Read();
 	scanf("%lf%lf%lf%lf%lf%lf",&S.x,&S.y,&S.z,&T.x,&T.y,&T.z);
 	for (int i=1;i<=11;i++)
 	 {
 	 	Point s,t;double mi=INF;int q=0;
 	 	for (int j=1;j<=n;j++)
 	 	 {
 	 	 	Point k=Vertical(a[j],S,T),l;
 	 	 	if (dis(k,a[j])>r[j]+eps||
 	 	 	  abs(dis(T,k)-dis(S,T)-dis(k,S))<eps) continue;
 	 	    l=Intersect(S,k,a[j],r[j]);
 	 	    if (dis(l,S)>mi) continue;
 	 	    mi=dis(l,S);s=l;t=S+(Vertical(S,l,a[j])-S)*2;q=j;
 	 	 }
 	 	if (mi==INF) {printf("\n");break;}
 	 	if (i!=11) printf("%d ",q);else
 	 	  puts("etc.");
 	 	S=s;T=t;
 	 }
 	return 0;
 }

SGU111：之前在codevs做过，让人感觉丧心病狂（很久以前写的太丑了还是不贴代码的好）

SGU118：打表发现f就是123456789的循环，然后直接做了，发现结论之后证明是很容易的。

SGU119：一眼感觉就是所有(A0*k)%N*X+(B0*k)%N*Y，证明都没证明直接交了= =

SGU120：恶心的计算几何。旋转二维向量有公式的（@baidu向量旋转矩阵），然而我之前的笔记都记得我看不清了，结果wa了n久= =

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 150
#define eps 1e-10
const double pi=acos(-1.0);
struct Point
 {double x,y;} a[N],S,T;
int n,m,s1,s2;double r,d,p;
Point operator+ (const Point &x,const Point &y)
 {return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
Point operator* (const Point &x,const double &y)
 {return (Point){x.x*y,x.y*y};}
inline Point Rotate(Point x,double y)
 {double i=cos(y),j=sin(y);return (Point){x.x*i-x.y*j,x.x*j+x.y*i};}
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline Point Zoom(Point x,double y)
 {return x*(y/(sqrt(sqr(x.x)+sqr(x.y))));}
int main()
 {
 	cin >>n>>s1>>s2;
 	scanf("%lf%lf%lf%lf",&a[s1].x,&a[s1].y,&a[s2].x,&a[s2].y);
 	r=2*pi*min(abs(s1-s2),n-abs(s1-s2))/n;p=(pi-r)/2;
 	r=dis(a[s1],a[s2])/sqrt(2*(1-cos(r)));
 	d=2*pi/n;r*=sqrt(2-2*cos(d));
 	if (s2!=s1%n+1)
 	 {
 	 	if ((n+s2-s1)%n<=n/2)
 	      p=(pi-d)/2-p,a[s1%n+1]=a[s1]+Zoom(Rotate(a[s2]-a[s1],p),r);else
 	      p=p+(pi-d)/2,a[s1%n+1]=a[s1]+Zoom(Rotate(a[s2]-a[s1],p),r);
 	 }
 	for (int i=(s1+1)%n+1;i!=s1;i=i%n+1)
 	 {
 	 	Point k=a[(i+n-2)%n+1],l=a[(i+n-3)%n+1];
 	 	a[i]=k+Rotate(k-l,2*pi-d);
 	 }
 	for (int i=1;i<=n;i++)
 	 printf("%.6lf %.6lf\n",a[i].x+eps,a[i].y+eps);
 	return 0;
 }

SGU121：感觉这道题真是莫名其妙啊，题解也都是造的出反例的乱搞，真是不知道什么鬼。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
int a[N][N],c[N][N],sz[N],n,m;bool b[N][2];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
    do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
    return x;
 }
void DFS(int x,int y)
 {
 	for (int i=1;i<=sz[x];i++)
 	 {
 	 	int k=a[x][i];
 	 	if (!c[x][k])
 	 	 c[x][k]=c[k][x]=y,b[x][2-y]=b[k][2-y]=1,DFS(k,y=3-y);
 	 }
 }
int main()
 {
 	n=Read();
 	for (int i=1,k;i<=n;i++)
 	 while (k=Read()) a[i][++sz[i]]=k;
 	for (int i=1;i<=n;i++)
 	 if (sz[i]&1) DFS(i,1);
 	for (int i=1;i<=n;i++)
 	 if (!(sz[i]&1)) DFS(i,1);
 	for (int i=1;i<=n;i++)
 	 if ((!b[i][0]||!b[i][1])&&sz[i]>1) m=-1;
 	if (m) {puts("No solution");return 0;}
    for (int i=1;i<=n;i++)
     {
     	for (int j=1;j<=sz[i];j++)
     	 printf("%d ",c[i][a[i][j]]);
        puts("0");
     }
    return 0;
 }

SGU122：组合数学原题，感觉也是比较诡异= =

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
bool a[N][N],b[N];
int n,m,s[N],S,T,ne[N][2],ans=0,li[N];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return y=='\n'||y==EOF?-x:x;
 }
void Ins(int x)
 {
 	for (int i=1;i<=n;i++)
 	  if (a[x][i]&&!b[i]) s[i]++;
 	ans++;b[x]=1;
 }
int DFS(int x,bool y)
 {
 	for (int i=1;i<=n;i++)
 	 if (a[x][i]&&!b[i])
 	  {Ins(i);ne[x][y]=i;ne[i][!y]=x;return DFS(i,y);}
    return x;
 }
void Reverse(int x,int y)
 {
 	int cnt=0;
 	for (int i=ne[x][1];i;i=ne[i][1])
 	 li[++cnt]=i;
 	for (int i=cnt;i>=1;i--)
 	 ne[x][1]=li[i],ne[li[i]][0]=x,x=li[i];
 	ne[T=li[1]][1]=S;ne[S][0]=T;
 }
int main()
 {
 	n=Read();n=-n;
 	for (int i=1;i<=n;i++)
 	 do
 	  {
 	     int k=Read();a[i][abs(k)]=1;
 	     if (k<0) break;
 	  } while (true);
 	Ins(S=T=b[1]=1);ne[1][1]=ne[1][0]=1;
 	while (ans!=n)
 	 {
 	 	int t=0;
 	 	for (int i=1;i<=n;i++)
 	 	 if (!b[i]&&s[i])
 	 	  {
 	 	  	 for (int j=1;j<=n;j++)
 	 	  	  if (a[i][j]&&b[j])
 	 	  	   {
 	 	  	   	  S=i;ne[i][1]=j;T=ne[j][0];
 	 	  	   	  ne[T][1]=0;ne[j][0]=i;Ins(i);break;
 	 	  	   }
 	 	  	 break;
 	 	  }
 	 	S=DFS(S,0);T=DFS(T,1);
 	 	for (int i=S;i!=T;i=ne[i][1])
 	     if (a[i][T]&&a[ne[i][1]][S])
 	      {Reverse(i,T);break;}
 	 }
 	cout <<1<<' ';
 	for (int i=ne[1][1];i!=1;i=ne[i][1])
 	 printf("%d ",i);
 	cout <<1<<endl;
 	return 0;
 }

SGU124：本来以为是凸多边形，然后就想用叉积什么的直接搞，然后果wa。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 20050
#define eps 1e-8
struct Point
 {int x,y;} Edge[N][2],li[N],S;
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
int n,m,ss=1,ln[N][2],s;
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline double Cha(Point x,Point y)
 {return x.x*y.y-x.y*y.x;}
int main()
 {
 	n=Read();
 	for (int i=1;i<=n;i++)
 	  Edge[i][0].x=li[i*2-1].x=Read(),
 	  Edge[i][0].y=li[i*2-1].y=Read(),
 	  Edge[i][1].x=li[i*2].x=Read(),
 	  Edge[i][1].y=li[i*2].y=Read();
 	S.x=Read();S.y=Read();
 	for (int i=1;i<=n;i++)
 	 if (fabs(dis(Edge[i][0],Edge[i][1])-dis(Edge[i][0],S)-
 	 	dis(Edge[i][1],S))<=eps)
 	  {puts("BORDER");return 0;}
    for (int i=1;i<=n;i++)
     {
     	if (Edge[i][0].y>Edge[i][1].y)
     	  swap(Edge[i][0],Edge[i][1]);
     	if (Cha(Edge[i][0]-S,Edge[i][1]-S)<0&&
     	  Edge[i][0].y<=S.y&&Edge[i][1].y>S.y)
     	  s++;
     }
    if (s&1) puts("INSIDE");else puts("OUTSIDE");
    return 0;
 }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter