2017区赛_给你n 个平面上的点,请你绘制出一个直角坐标系。对于原点,用'+'表示;对于y 坐标轴

第二题直角坐标系（coordinates）

【问题描述】

给你n 个平面上的点，请你绘制出一个直角坐标系。对于原点，用' + '表示；对于y 坐标轴，用' |'表示（除去原点和n 个点的位置）；对于x 坐标轴，用' - '表示（除去原点和n 个点的位置）；对于n 个平面上的点，用' * '表示；所有其他点，用' . '表示。为了更好地理解，请参照样例。

【输入格式】

第一行包括一个正整数n。

接下来n 行，每行两个整数x, y，表示点的坐标。

【输出格式】

一个直角坐标系。其中，第一行的y 坐标为所有点的y 坐标和0 中的最大值；最后一行的y 坐标为所有点的y 坐标和0 中的最小值；第一列的x 坐标为所有点的x 坐标和0 中的最小值；最后一列x 坐标为所有点的x 坐标和0 中的最大值。详见样例。

【输入样例1】

8

-105

-73

-42

-94

01

6-1

30

8-3

【输出样例1】

*. . . . . . . . . | . . . . . . . .

.* . . . . . . . . | . . . . . . . .

.. . * . . . . . . | . . . . . . . .

.. . . . . * . . . | . . . . . . . .

.. . . . . . . . . * . . . . . . . .

----------+ -- * -----

.. . . . . . . . . | . . . . . * . .

.. . . . . . . . . | . . . . . . . .

.. . . . . . . . . | . . . . . . . *

【输入样例2】

5

12

53

21

55

33

【输出样例2】

|. . . .*

|. . . . .

|. . * . *

|* . . . .

|. * . . .

+-----

【数据规模】

对于30%的数据，1<=x<=100，1<=y<=100

对于100%的数据,1<=n<=250, 且x,y 的绝对值都不超过100，所有的点两两不同。

       这题是一个比较简单的模拟，在输入时标记哪个地方有点，用v数组标记。但是，因为有负半轴的缘故，所以不能直接标记v[x][y]，要把x和y都加一个偏移量，因为他们的绝对值都不超过一百，所以加100就够了。

    同时在输入时记录下最小和最大的x、y分别是多少。

    但是，通过第二个样例可以得知，必须要画出一个坐标轴，不然怎么能算是直角坐标系呢。所以，最小和最大的x、y都要与0取max（min）

    然后按一定的次序输出即可。时间复杂度O（x*y）

代码如下：

#include
     
     
      
      
#include
      
      
       
       
#include
       
       
        
        
#include
        
        
         
         
using namespace std;
const int oo=10000;
int n,x,y;
int maxx=-oo,mix=oo,may=-oo,miy=oo;
bool v[205][205];
int main()
{
	freopen("coordinates.in","r",stdin);
	freopen("coordinates.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		v[x+100][y+100]=true;
		maxx=max(maxx,x);
		mix=min(mix,x);
		may=max(may,y);
		miy=min(miy,y);
	}
    maxx=max(maxx,0);
	mix=min(mix,0);
	may=max(may,0);
	miy=min(miy,0);

        
        
       
       
      
      
     
     

第三题折纸(folding)

【问题描述】

现有一个W*H的矩形纸张，求至少要折多少次才能使矩形纸张变成w*h的矩形纸张。注意，每次的折痕都要平行于纸张的某一条边。

【输入格式】

第一行包括两个整数W，H。

第二行包括两个整数w，h。

【输出格式】

输出一个整数，表示至少需要折的次数。若无解，则输出-1。

【输入样例1】

27

22

【输出样例1】

2

【输入样例2】

55

16

【输出样例2】

-1

【输入样例3】

106

48

【输出样例3】

2

【数据规模】

对于20%的数据，W=w且H,h<=3

对于100%的数据,1<=W,H,w,h<=10^9

    从这题开始，请注意：前方高能！

    比赛的时候，我在纸上画了几下，发现当边长是W时，把它对折一下为W/2，如果期望达到的w在W和W/2的范围之内，那么就是可以的，否则，就要折成W/2。

    但是看到了最后一个样例，他们的边长需要反过来才能够折，于是自认为很“机智”地就用swap把大小调整好，大对大，小对小。事实证明是个大错误。

错误点get

    1、 不能直接变成W/2，因为当是7的时候，7/2=3，但是并不能折到3，应该最小是4。所以应该是(W+1)/2,同样的，用偶数实验也是可行的。

    2、 至于大对大，小对小的思路显然是想少了。赛后同学给我举了个例子，5 7折成4 5。如果是用我的方法，那么5折成4要折一次，7折成5也要折一次，一共就是两次。

但如果是5对5，那么根本不用折，7对4，这一次就可以了。最优解应该是一次。

我看似很有道理的理论就over了。

    正解其实和这个差不了多少，就是分别算一下两种对应的情况，取一个min为最优解即可。

    时间复杂度 O（log(10^9)）

代码如下：

#include
     
     
      
      
#include
      
      
       
       
#include
       
       
        
        
#include
        
        
         
         
#include
         
         
           using namespace std; const int oo=10000000; int W,H,w,h,lans,ans2=oo; int update(int x,int y) { int ans=0; int x2=x; while(x2>y) { ans++; x2=(x2+1)/2; } return ans; } int main() { scanf("%d%d",&W,&H); scanf("%d%d",&w,&h); if((w>W&&w>H)||(h>W&&h>H)) { cout<<-1< 
          
            =w&&H>=h) { lans+=update(W,w); lans+=update(H,h); ans2=min(lans,ans2); } lans=0; swap(W,H);//交换一下 再算一次 if(W>=w&&H>=h) { lans+=update(W,w); lans+=update(H,h); ans2=min(ans2,lans); } printf("%d",ans2); return 0; } 
           
         
        
        
       
       
      
      
     
     

第四题两个数（twonum）

【问题描述】

现有两个人, 若第一个人当前手中的数为w1，则下一秒他手上的数将会变成(X1 *W1+Y1 ) mod m；若第二个人当前手中的数为 w2,则下一秒他手上的数将会变为(X2*W2+Y2 )mod m（a mod b 表示a 除以b 的余数）。第0 秒,两个人手上的数分别为h1, h2; 请求出最快在第几秒，第一个人手上的数为a1,且第二个人手上的数为a2。若不可能，则输出-1。

【输入格式】

第一行为一个正整数T，表示数据组数。

对于接下来的每一组数据， 第一行为一个正整数m，第二行包括两个整数h1, a1，第三行包括两个整数x1, y1，第四行包括两个整数h2, a2，第五行包括两个整数x2, y2。

【输出格式】

对于每一组数据，输出一行，一个整数，如题所述。

【输入样例】

2

5

42

11

01

23

1023

12

10

12

11

【输出样例】

3

-1

【数据规模】

对于30%的数据, m<=1000

对于100%的数据,

T<=5,  h1不等于 a1且 h2不等于 a2，

2<=m<=106 , 0<=h1,a2, x1, y1, h2, a2, x2, y2<m

    这题在所有题目里面，是最复杂的，虽然看上去好像就是一个简单的模拟，然而事实证明，我想少了。

    首先，要找到循环节。可是循环节怎么找呢？用while循环找。分别用va和vb记录第一和第二个人出现每一个数字的秒数。

一开始初始化为-1，如果已经出现过，那么说明出现了循环，break。循环节的长度cir1则为当前的i-va[]，同样的另外一个人出现循环节的长度cir2也为j-vb[]

如果两个va[a1]和va[a2]都为-1，说明不在循环以内出现，那么就输出-1。如果va[a1]==va[a2]都相等，那就最好不过了，直接输出。

接下来，问题就来了，我们分为几种情况。

    1、如果va[a1]在循环节里面并且vb[a2]在循环节外面，那么vb[a2]要大于等于va[a1]不然它们是无法在同一秒内出现的。再看一下vb[a2]-va[a1]能否被第一个人的循环的长度cir1整除。如果符合条件输出vb[a2]。

    2、同理，vb[a2]在循环节里面并且va[a1]在循环节外面的情况也是一样的。

    3、最后一种情况也是最复杂的（我还是一脸蒙，尝试解释）。va[a1]在循环节里面并且vb[a2]在循环节里面。

    有解：分别计算出两个循环节的最大公因数cd，如果他们两个的差除以cd除不尽，那么无解。枚举第一个人，判断是否符合va[a1]>=vb[a2]，并且他们的差值是否能被cir2（vb[a2]循环的长度）整除。

int gcd(int a,int b)
{
	while(b)
	{
		int c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int main()
{
	long long t,a1,b,mod,h1,x1,y1,h2,a2,x2,y2;
	cin>>t;
	while(t--)
	{
		cin>>mod>>h1>>a1>>x1>>y1>>h2>>a2>>x2>>y2;
		memset(va,-1,sizeof(va));memset(vb,-1,sizeof(vb));
		va[h1%mod]=0;vb[h2%mod]=0;
		long long i,j;i=j=1;
		while(1)
		{
			h1=(x1*h1+y1)%mod;
			if(va[h1]==-1)
			{
				va[h1]=i;
				i++;
			}
			else break;
		}//分别算出在哪个地方循环
		while(1)
		{
			h2=(x2*h2+y2)%mod;
			if(vb[h2]==-1)
			vb[h2]=j;
				j++;
			}
			else break;
		}
		if(va[a1]==-1||vb[a2]==-1) cout<<-1<
    
    
     
     va[a1])
			{
				if(vb[h2]>vb[a2]) cout<<-1<
     
     
      
      =0)&&((va[a1]-cnt2)%cir2==0))
						cout<
      
      
       
       <
       
       
        
        vb[a2])
				{
					long long cnt1=va[a1];
					if((vb[a2]-cnt1>=0)&&((vb[a2]-cnt1)%cir1==0))
						cout<
        
        
          < 
         
           =cnt2)&&((cnt1-cnt2)%cir2==0)) { cout< 
          
            <