洛谷模拟与高精度题单

先针对洛谷这个题单每一个来总结一下，后面专门写一个高精度的理解

（题目直接取洛谷题单上看，很简单一眼出的就先不写了)

1.乒乓球：

根据输入的w和L来判断甲和乙获胜的次数（两种记分方式，11和21)，需要注意的是只有当分差大于等于2 的时候才输出否则需要一直加直到分差大于2；因为我们需要判断w和L，显然我们可以开一个数组当是w的时候就是1，是L的时候就是0，这样就可以对其更好的加分处理。

	for (int k = 0; k < 2; k++) {
		int w = 0, l = 0;//其实感觉本题的秒点就是w和l的声明
		for (int i = 0; i < n; i++) {
			w += a[i];
			l += 1 - a[i];
			if ((max(w, l) >= f[k]) && abs(w - l) >= 2) {//这个if的代码块应该是当时做题的难点
				cout << w << ":" << l << endl;
				w = l = 0;//注意要清理
			}
		}
		cout << w << ":" << l << endl;
		cout << endl;
	}

　2.扫雷

此题的两个点分别是 1：开二维数组的时候当读入是*就把其设为1，这样就有利于后面对地雷数的加法运算 2.开的时候多开一圈这样处理边界问题就简单多了。然后就是对数组进行遍历，当是0的时候就把周围一圈的数字加起来，然后就是本题的最妙之处了：，当加起来的时候，思维惯性就是对其赋值，然后弄完后再遍历输出，其实绝对不可以这样应直接输出否则其他的0就会依然加上他

   cin>>n>>m; 
    for(int i=1;i<=n;i++)//读入地图 
    {
        for(int j=1;j<=m;j++) 
        {
            cin>>tmp;//读入每一个点 
            if(tmp=='*') a[i][j]=1;//如果是地雷就将这个点设为一 
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1) printf("*"); //如果是地雷不用输出数字 
            else
            {
                printf("%d",a[i+1][j+1]+a[i+1][j-1]+a[i+1][j]+a[i][j+1]+a[i][j-1]+a[i-1][j+1]+a[i-1][j]+a[i-1][j-1]);
                //将旁边的雷加起来输出 
            }
        }
        printf("\n");
    }

三玩具迷藏

1因为有顺时针和逆时针两种方式，那么就不能看出我们可以把一种定为+一种定位-这样就很好对其位置上的处理

2.取模运算，因为是一个圈一直循环，那么通过%运算就很好处理了，即便加再大因为是循环转一圈又到了那个位置也可以直接取余数获取位置

3.因为最后会输入指令，一个我认为本题最妙的点就是输入一个指令就执行一次操纵而不是对输入的指令进行存储，这样就不会那么麻烦，不然很容易写到后面脑子晕了

 cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].head>>a[i].name;
    }
    int now=0;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if(a[now].head==0&&x==0)now=(now+n-y)%n;
        else if(a[now].head==0&&x==1)now=(now+y)%n;
        else if(a[now].head==1&&x==0)now=(now+y)%n;
        else if(a[now].head==1&&x==1)now=(now+n-y)%n;
    }

四：A+B高精和五A*B高精：

这个后面会写一个高精度的随笔

六：阶乘之和：

高精乘和高精加，有个题解的思路是重载运算符我感觉没有必要，还不如直接定义两个方法来的简单暴力

还有一个这个其实是高精乘低精比较简单一点

七：魔法少女

下面两个都是好妙的啊啊啊啊，当时没想到

1。顺时针相当于把每一列给了每一行而不是我一开始简单粗暴的认为是就是周边几圈转这样的思路可以说是根本实现不了代码（还是观察的不够细，没看到底层)

2.看到了上一步又会出现了一个问题就是把一列给了那一行那么他数据不就改变了吗，那我还怎么把下一列给下一行呢，此时就是把要执行的矩阵先给一个空的二维数组然后通过新的二维数组进行赋值

void spin(int x,int y,int r)
{
	for(int i=x-r;i<=x+r;i++)
	{
		for(int k=y-r;k<=y+r;k++)
			temp[i][k]=square[i][k];
	}//将以（x,y)为中心的(2r+1）*（2r+1）的矩阵赋给temp
	int x1=x+r,y1=y-r;
	for(int i=x-r;i<=x+r;i++)
	{
		for(int k=y-r;k<=y+r;k++)
		{
			square[i][k]=temp[x1][y1];//将某一列的数字赋值给某一列
			x1--;
		}
		x1=x+r,y1++;
	}
}　

八：石头剪刀布

要说秒的好像只有一个%运算来获取每一个出的东西

九：两只牛

1.二维数组多开一圈并且都赋值位*来处理边界问题，并且读入c和F的时候要额外定义变量来存储他们的位置

2.特征值，可以开一个很大的数组然后把牛和人的x，y ，方向值乘以不同10的倍数，这样就有唯一特征值，每次判断一个特征值，是1就代表重复永远都抓不到，是0就赋值为1

3.把每一个反向设为0，1，2，3同时为了好统一操作坐标就可以定义xx[4]={-1,0,1,0},yy[4]={0,1,0,-1},这个二维数组

九：多项式的输出

就是几个条件的判断然后还有就是每输入一次就执行一次

 for(int i=n;i>=0;i--){
        cin>>a;
        if(a){    判0系数
            if(i!=n&&a>0)cout<<"+";    根据正负、是否为最高此项决定加号
            if(abs(a)>1||i==0)cout<<a;    输出系数（系数不为正负1或指数为0）
            if(a==-1&&i)cout<<"-";    -1系数特判，常数项已特判
            if(i>1)cout<<"x^"<<i;    二次及以上输出指数
            if(i==1)cout<<"x";    一次项
        }
    }

十：字符串的展开：

说不出来看代码吧

int main() {
	scanf("%d%d%d%s",&p1,&p2,&p3,ch);//输入;
	while(ch[i]){//当ch[i]有值时;
		be=ch[i-1];af=ch[i+1];f=ch[i];//f存储ch[i],便于判断; 
		if(f=='-'&&af>be&&(be>='0'&&af<='9'||be>='a'&&af<='z')){//意思是ch[i]若为'-',就判断其前后是否满足条件，满足进入循环; 
			for(p3==1?j=be+1:j=af-1; p3==1?j<af:j>be; p3==1?j++:j--){
				p=j;//j是整形变量，p是字符型变量，这样是将p赋值为ASCII码为j的字符; 
				if(p1==2)//是否大写; 
					p=(p>='a')?p-32:p;//如果是字母就转成大写 
				else if(p1==3) p='*';//是否输出'*' 
				for(k=0; k<p2; k++)//输出p2个 
					printf("%c",p);
			}
		} 
		else
			printf("%c",f);//如果ch[i]是非'-'或者其前后不满足条件，就原样输出;
		i++;//一定要放在后面，不然会出错QAQ;
	}

十一：作业调度

还是不会后面补吧

十二：帮贡排序

1.有个点需要注意就是他的输入就是按职位和等级，这样排序就是从第四位开始按帮贡排序

2.当帮贡一样是按数入顺序排序，这个当时竟然没想到可以自己定义一个id

3.对于职位自己定义一个方法按照职位高低返回不同的值

4.要熟练运用sort排序

5.编写过程中很容易乱，自己先在草稿纸上打一个题纲

十三：阶乘数码

简单的高精度乘低精度，最后返回指定的数字出现的次数

 int p=1,jw=0;//p代表位数，jw代表进位。
        scanf("%d%d",&n,&m);
        for(i=2;i<=n;i++)//从2开始，反正任何数乘1还等于它本身。
        {
            jw=0;
            for(j=1;j<=p;j++)//高精度*单精度。
            {
                a[j]=a[j]*i+jw;//高精度*单精度+进位。
                jw=a[j]/10;//设置进位。
                a[j]=a[j]%10;
            }
            while(jw>0)//如果还有进位，处理进位。
            {
                a[j]=jw%10;
                jw/=10;
                j++;
            }
            p=j-1;
        }

十四：最大乘积

这个重点讲一下，我一开始的思路是一直对半分然后直到分到2和3但会有很多需要判断，比如是分到3和3或2和3，其实后面看了题解才反应过来那我就直接都是2和3，把少的或多的拿掉，然后再上一级多退少补，有个问题代码实现好难。接下来就是一个好吊的思想：

以8 和10为例，若1作因数，则显然乘积不会最大。把x分拆成若干个互不相等的自然数的和，因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把x 分成2 + 3 ⋯ + n 直到和大于等于x具体的贪心思路如下：若和比x大1，例如8分解为2 + 3 + 4 = 9 则因数个数至少减少1个，为了使乘积最大，应去掉最小的2，并将最后一个数（最大的数）加上1 ，即变为3 + 5 = 8 此时乘积最大；若和比x大k ( k ≠ 1 )则去掉等于k 的那个数,便可使乘积最大，例如10分解为2 + 3 + 4 + 5 = 14 去掉14 − 10 = 4 即变为2 + 3 + 5 = 10 此时乘积最大；（不要脸的说感觉我一开始的貌似研究再深一点就是这个了）之所以有这个思想就是要使因数尽可能的多

十五：麦森数

快速幂，并且每快速幂一次就取模否则待会取模的时候就会超精度了，取模运算的一些结论和快速幂可以看之前发的快速幂题解；

还有一个数学思想就是容易知道2^P-1与2^P的位数肯定相同 (2^P没有5这个因数，尾数不为0）必有一个X使得10^X=2^P;又由10^X为X+1，所以2^P的位数=P*log102​+1;