codeforse1451总结

第一题Subtract or Divide

题目

开始看题，没看懂，在看了几遍，不会做，不知道要循环多少次，于是

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
   
    register int res = 0;
    register char c = getchar(), f = 1;
    while (c < 48 || c > 57) {
   
        if (c == '-')
            f = 0;
        c = getchar();
    }
    while (c >= 48 && c <= 57) res = (res << 3) + (res << 1) + (c & 15), c = getchar();
    return f ? res : -res;
}
inline void write(int x) {
   
    register char c[21], len = 0;
    if (!x)
        return putchar('0'), void();
    if (x < 0)
        x = -x, putchar('-');
    while (x) c[++len] = x % 10, x /= 10;
    while (len) putchar(c[len--] + 48);
}
int main()
{
   
        int T=read();
        while(T--)
        {
   
                int sum=0;
                int n=read();
                if(n<=3)
                {
   
                        write(n-1);printf("\n");
                        continue;
                }
                if(n%2==0)
                {
   
                        printf("2\n");
                }
                if(n%2==1)
                {
   
                        printf("3\n");
                }
        }
}

正解

solution：

这道题目乍一看不知道要循环多少次，我们观察一下样例解释的规律，可以看出几个数字都经过了 2。

考虑到任何一个大数在 -1 或自身就直接可以变成 2，再用一步就可以变成 1，不存在更优的解法。

1,2,3 除外，需要特判。

code：

#include<cstdio>
using namespace std;
int main()
{
   
	int T;
	scanf("%d",&T);
	while(T--)
	{
   
		int n;
		scanf("%d",&n);
		if(n==1)
		{
   
			printf("0\n");
		}
		else
		if(n==2)
		{
   
			printf("1\n");
		}
		else
		if(n==3)
		{
   
			printf("2\n");
		}
		else
		if(n%2==1)
		{
   
			printf("3\n");
		}
		else
		{
   
			printf("2\n");
		}
	}
	return 0;
} 

第二题 Non-Substring Subsequence

题目

](https://pic.gksec.com/2020/11/22/1be6a09781810/image.png)

其实解法很简单，仅仅只是让我们判断一个子序列是否存在，那么我们只需要在s[0,l−1]s[0,l−1] 区间内查看是否存在一个字符和 s[l]s[l]，相等，如果左边不存在那么再检查右边检查从 s[r+1,n]s[r+1,n] 中是否存在一个字符和 s[r]s[r] 相等即可，如果两个条件都不满足则一定不可以构造出来，如果满足任意一个则可以输出YES.可以证明此方法为条件成立的充分必要条件，但过于简单在此忽略证明过程

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
   
    register int res = 0;
    register char c = getchar(), f = 1;
    while (c < 48 || c > 57) {
   
        if (c == '-')
            f = 0;
        c = getchar();
    }
    while (c >= 48 && c <= 57) res = (res << 3) + (res << 1) + (c & 15), c = getchar();
    return f ? res : -res;
}
inline void write(int x) {
   
    register char c[21], len = 0;
    if (!x)
        return putchar('0'), void();
    if (x < 0)
        x = -x, putchar('-');
    while (x) c[++len] = x % 10, x /= 10;
    while (len) putchar(c[len--] + 48);
}
int main()
{
   
	int T=read();
	while(T--)
	{
   
		int n=read(),q=read();
		string a;
		cin>>a;
		for(int i=0;i<q;i++)
		{
   
			int l=read(),r=read();
			bool tmp=0,tmp1=0;
			for(int i=0;i<l-1;i++)
			{
   
				if(a[i]==a[l-1])
				{
   
					tmp=1;
					break;
				}
			}
			for(int i=r;i<n;i++)
			{
   
				if(a[i]==a[r-1])
				{
   
					tmp1=1;
					break;
				}
			}
			if(tmp||tmp1)
			{
   
				cout<<"YES"<<endl;
			}
			else
			{
   
				cout<<"NO"<<endl;
			}
		}
	}
}