错题集总结和理解

1.https://codeforces.com/contest/1670​​​​​​

题意：给出一个数组，可以做无数次将两个数的正负号交换，经过这个操作之后如果数组能够变成有序的，那么就输出YES，不然输出NO；

错误做法：p从开始进行遍历，s1记录绝对值单调递减的数的个数，s2记录单调递增的数的个数，cnt1记录单调负数的个数,cnt2记录整数的个数。

错误原因：s1很难实现只记录一个单调递减区间单调递减的数的个数,所以很难做出们会有很多矛盾。

正确做法：记录一下数组负数的个数cnt，将前cnt个数全部变成负数，将剩下的全部变成正数，如果变化后的数组如果是有序的，那么就输出YES否则就输出NO；

2.Problem - C - Codeforces

 题解：

#include

using namespace std;

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		string str;
		cin>>str;
		int p0 = -1,p1 = -1;
		for(int i = 0;i < str.size();i ++)
		{
			if(str[i]=='1')p1 = i;
			if(str[i]=='0')
			{
				p0 = i;
				break;
			}
		}
		if(p0==-1&&p1==-1)cout< 
3.4420. 连通分量 - AcWing题库
 
给定一个 n×m 的方格矩阵，每个方格要么是空格（用 . 表示），要么是障碍物（用 * 表示）。
 
如果两个空格存在公共边，则两空格视为相邻。
 
我们称一个不可扩展的空格集合为连通分量，如果集合中的任意两个空格都能通过相邻空格的路径连接。
 
这其实是一个典型的众所周知的关于连通分量（Connected Component ）的定义。
 
现在，我们的问题如下：
 
对于每个包含障碍物的单元格 (x,y)，假设它是一个空格（所有其他单元格保持不变）的前提下，请你计算包含 (x,y) 的连通分量所包含的单元格数量。
 
注意，所有假设求解操作之间都是相互独立的，互不影响。
 
输入格式
 第一行包含两个整数 n,m。
 
接下来 n 行，每行包含 m 个字符：. 表示空格，* 表示障碍物。
 
输出格式
 输出一个 n 行 m 列的字符矩阵，其中第 i 行第 j 列的字符对应给定矩阵中第 i 行第 j 列的单元格。
 
如果该单元格为空格，则输出字符为 .，如果该单元格为障碍物，则输出字符为假设该单元格为空格的前提下，包含该单元格的连通分量所包含的单元格数量对 10 取模后的结果。
 
具体格式可参照输出样例。
 
数据范围
 前 5 个测试点满足 1≤n,m≤10。
 所有测试点满足 1≤n,m≤1000。
 
输入样例1：
 3 3
 *.*
 .*.
 *.*
 输出样例1：
 3.3
 .5.
 3.3
 输入样例2：
 4 5
 **..*
 ..***
 .*.*.
 *.*.*
 输出样例2：
 46..3
 ..732
 .6.4.
 5.4.3
 
 题解：如果使用搜索的话需要进行很多优化，如果使用并查集的话就不需要什么优化，因为并查集（记忆化）的时间复杂度是O（n*m）的；
 
#include
#include 
#include 
#include 

using namespace std;

const int N = 1010,M = 1010100;

int pre[M],s[M];
char g[N][N];
int n,m;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int get(int x,int y)
{
    return x*m+y;
}

int find(int x)
{
    if(pre[x]==x)return x;
    else pre[x]=find(pre[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i = 0;i < n;i ++)scanf("%s",g[i]);
    
    for(int i = 0;i < n*m;i ++)pre[i]=i,s[i]=1;
    
    for(int i = 0;i < n;i ++)
    for(int j = 0;j < m;j ++)
    if(g[i][j]=='.')
    {
        for(int k = 0;k < 4;k ++)
        {
            int pa = i+dx[k],pb = j+dy[k];
            if(pa>=0&&pa=0&&pb=0&&pa=0&&pb 
4.[NOIP2015]金币
 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网

 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。
 
#include
using namespace std;
int main() {
    long long sum = 0;
    int n, i;
    scanf("%d", &n);
    for (i = 1; n > i; ++i) {
        sum += i * i;
        n-= i;
    }
    if (n != 0) sum += n * i;
    printf("%lldn", sum);
    return 0;
}
 
5.比例化简
 
链接：登录—专业IT笔试面试备考平台_牛客网
 来源：牛客网
  
 
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902 。
 
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3 ，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
 
现给出支持人数A，反对人数 B ，以及一个上限 L ，请你将 A 比 B 化简为 A ’比 B ’，要求在 A ’和 B ’均不大于 L 且 A ’和 B ’互质（两个整数的最大公约数是 1 ）的前提下， A ’ /B ’ ≥ A/B 且 A ’ /B ’ - A/B 的值尽可能小。
 
输入描述: 
输入共一行，包含三个整数 A,B,L ，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
 
输出描述: 
输出共一行，包含两个整数 A ’， B ’，中间用一个空格隔开，表示化简后的比例。
 
示例1
 
输入 
1498 902 10
 
 
输出 
5 3
 
题解：因为L的范围很小所以可以直接枚举（根据公式来就行），
 
 
 上面的除法可以化为乘法。
 
#include

using namespace std;


int main()
{
    int A,B,L;
    int a,b;
    cin>>A>>B>>L;
    
    for(int i = 1;i <= L;i ++)
        for(int j = 1;j <= L;j ++)
        {
            double x = (double)i/j;
            double X = (double)A/B;
            if(i*B>=j*A&&i*b < j*a)
            {
                a = i;
                b = j;
            }
        }
    cout<
 
6.Problem - B2 - Codeforces
 
题意简单描述：给出一串由1和0组成的字符串（串的长度都是偶数），如果字符串含1的子串和含0的子串的个数都是偶数，那么就是好串，否则就是不好的串，我们现在可以经行一种操作，就是把0变成1，或者把1变成0，这种操作可以进行任意次，问最少经过多少次可以把一个不好的串变成一个好串，形成的最小的连续某块是多少（110011这样的，连续模块数量是3，11，00，11）。
 
题解：
 
第一问：
 
能够看出，我们只需要从头开始两个位置两个位置的判断就行的，及将1和2位置判断，3和4位置判断，以此类推。为什么呢，因为例如：如果我们不讲4和3判断。而是将4和5判断，那么4前面的位置的数量就没变成奇数，再怎么变都是没用的，5后面的同理。所以只需要想上面那样遍历就行，
 
第二问：
 
我们在将不好的串变化的时候，就可以记录，下面是步骤；
 
pre：记录上一次str[i]==str[i+1]时str是0还是1；
 
当a[i]!=a[i+1]时：操作数将会加一，然后默认变化为和pre一样的字符，应为只有这样，才会让不同的子串数量尽可能的少。
 
当判断a[i]==a[i+1]时判断一下和pre是不是一样的，
 
如果是一样，就说明他们在一个子串里，就不用变pre，子串数量也不用加1。
 
如果和pre不一样，说明子串数量需要加一，然后将pre变成当前的子串字母。
 
代码：
 
#include
#include

using namespace std;

string str;

void slove()
{
    int x=0,y=0;
    char pre='2';
    for(int i = 0;i < str.size();i+=2)
    {
        if(str[i]==str[i+1])
        {
            if(str[i]!=pre)y++;
            pre=str[i];
        }
        else x++;
    }
    y = max(1,y);
    cout<>T;
    while(T--)
    {
        int n;
        cin>>n;
        cin>>str;
        slove();
    }
    return 0;
}
 
7.Problem - C - Codeforces
 
题意：有一个数组p，在1~n中有多少对（a,b,c,d） 符合以下条件(a,b,c,d)互不相等：
 
1.p[a] < p[c] && p[b] > p[d]
 
2.a < b < c < d;
 
范围：
 
1<=n<=5000;
 
题解：因为n的范围很小，所以时间复杂度最多可以是n^2，如果使用暴力枚举那么时间复杂度是n^4肯定不行，由第一个不等式可以看出，a只和c，b只和d有关，虽然第二个不等式它们四个都有关系，但是一起看肯定是不行的（时间复杂度回超时），
 
1.所以只能先分开看，那么我们就可以先选择b枚举（1~n），d从b位置后面一个开始枚举，找到每个位置b有多少个d符合p[b]>p[d],记录这个位置的b，有多少个d符合条件，计为fb[b]。
 
2.b,d的关系枚举完了，那么现在枚举a和c的关系了，第一层循环c从1~n;第二层循环a从1到c-1，只要找到一个符合p[a] > p[c],将中间的b和d符合条件的情况加上就行，及加上（a+1，c-1）内所有的fb[i],这里使用前缀和就行，上面是没有加a < b < c < d条件的遍历，所以现在需要加进来，所以在枚举c的同时枚举，b从1到c；如果有p[b] > p[c]就将fb[b]减1，为什么呢？其实枚举c和b进行比较时是将c看成了d，这样才能保证a < b < c < d,因为我们刚才的操作就是将符合p[b] > p[d]，d小于等于c的b.d对都减去了。
 
代码：
 
#include
#include

using namespace std;

const int N = 5010;

long long g[N],fb[N];
long long sfb[N];

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(fb,0,sizeof fb);
		int n;
		cin>>n;
		for(int i = 1;i <= n;i ++)cin>>g[i];
		for(int i = 1;i <= n;i ++)
			for(int j = i+1;j <= n;j ++)
			if(g[j] g[c])fb[k]--;
			}
			sfb[0] = 0;
			for(int k = 1;k <= c;k ++)
			{
				sfb[k] = sfb[k-1] + fb[k];
			}
			for(int k = 1;k < c;k ++)
			{
				if(g[k] < g[c])
				{
					ans+=sfb[c-1] - sfb[k];
				}
			}
		}
		cout<