果然还是我自己太菜了，真的第一学期根本没碰算法，现在各种题都是似曾相识而不知如何去解。也不敢往复杂的地方去想。可能要重新学一遍算法，保证最最基础的都会，才能进一步地提升。


        

        

 A. Three Strings




题目链接




 题目原文


1301A


 题目大意


给三个长度都为len的字符串 aa 、 bb 、 cc 。对于每个位置，必须进行 aia_i 和 cic_i 交换，或者 bib_i 和 cic_i 进行交换，这样一共进行了 lenlen 次交换，你可以选择 cic_i 和 aia_i 还是 bib_i 交换，问是否存在操作，使得字符串 aa 和 bb 相等？


 思路


很显然如果 aia_i 和 cic_i 相同，那肯定是和 aia_i 换；如果 bib_i 和 cic_i 相同，那肯定是和 bib_i 换；否则就随便换一个（不一样的话就直接NO了）。


 代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=200005;
char s1[maxn],s2[maxn],s3[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		memset(s3,0,sizeof(s3));
		scanf("%s%s%s",s1+1,s2+1,s3+1);
		int n=strlen(s1+1);
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(s1[i]==s3[i]) s2[i]=s3[i];
			else if(s2[i]==s3[i]) s1[i]=s3[i];
			else s1[i]=s3[i];
			if(s1[i]!=s2[i])
			{
				flag=false;
				break;
			}
		}
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}


 B. Motarack’s Birthday




题目链接




 题目原文


1301B


 题目大意


给出一串数组，其中 −1-1 代表未知,现在要用 kk 去替换，使相邻两个数之差的绝对值最小，求这个最小值和 kk 。


 思路


当时考试的时候太蠢了，写得很复杂。其实就是题做少了，简单的思维量却写出冗长的代码，最后一分钟发现bug，可惜已经不能改变结局了……


先求 kk ， kk 显然就是所有挨着 −1-1 的非负值的 maxmax 和 minmin 的和的一半，然后再把 kk 带进去扫一遍即可。


 代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include &lt; cstdio &gt;
#include &lt; cstring &gt;
#include &lt; algorithm &gt;
using namespace std;
const int maxn=4000005;
const long long inf=1e18;
long long n,a[maxn];
int main()
{
	#ifdef lemon
	freopen("B.txt","r",stdin);
	#endif
	long long T;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);a[0]=a[n+1]=-1;
		long long maxx=-1,minn=inf,m=0;
		for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
		for(long long i=1;i<=n;i++)
		{
			if(a[i]!=-1) continue;
			if(i!=1&&a[i-1]!=-1) maxx=max(maxx,a[i-1]),minn=min(minn,a[i-1]);
			if(i!=n&&a[i+1]!=-1) minn=min(minn,a[i+1]),maxx=max(maxx,a[i+1]);
		}
		if(maxx==-1)
		{
			printf("0 0\n");
			continue;
		}
		long long k=(maxx+minn)>>1;
		for(long long i=1;i<n;i++)
		{
			long long xx=a[i],yy=a[i+1];
			if(xx==-1) xx=k;
			if(yy==-1) yy=k;
			m=max(m,abs(xx-yy));
		}
		printf("%lld %lld\n",m,k);
	}
	return 0;
}


 C. Ayoub’s function




题目链接




 题目原文


1301C


 题目大意


请你构造出一个长度为 nn 的 0101 串，其中有 mm 个 11 ，使得 f(s)f(s) 最大。 f(s)f(s) 为包含 11 的区间 (l,r)(l,r) 的个数。


 思路


首先一个长度为 nn 的串，它的区间个数为 n×(n+1)2\frac{n\times(n+1)}2 。这道题求包含 11 的区间个数，其实我们可以用总区间数去减去全为 00 的区间即可。

而怎么达到最少的连续的 00 的区间呢？其实直接将 11 平均分下去即可。


 代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include &lt; cstdio &gt;
#include &lt; cstring &gt;
#include &lt; algorithm &gt;
using namespace std;
const int maxn=200005;
long long T,n,m;
inline long long sum(long long x) {return (1+x)*x/2;}
int main()
{
	#ifdef lemon
	freopen("C.txt","r",stdin);
	#endif
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&m);
		long long ans=sum(n);
		if(m==0) ans=0;
		else
		{
			long long res=n-m;
			long long per=res/(m+1);
			long long mod=res%(m+1);
//			printf("$$%lld %lld %lld\n",res,per,mod);
			ans-=(sum(per)*(m+1-mod))+(sum(per+1)*mod);
		}
		printf("%lld\n",ans);
	}
	return 0;
}


剩下的等我做出来再补。（怕是做不出来了）


round-619