cf 672 div3 2020-3-12 (1)

手速拉满后，迅速秒了2道题，之后第三题，有个if没有包含if里头的语句，一直找bug没有找出来，最后差点崩溃，最后卡了10～20分钟后还是找出来了。(傻逼了）第四题ai+aj>bi+bj，可以转换下题意稍微变形ai-bi>bj-aj;然后再次变换ai-bi+(aj-bj)>0，好了，这样进行双指针，首尾一直扫就行了。。。一位老弟把LL定义在了局部，出bug了，最后还是让我找出问题来了。当时第四题我也没开LL也被t了一发(WA12)，因为emmm它值为10^9范围，超出了int的范围了。血的代价，注意开整型，printf(“%lld\n”);以下是题解。

A

每次可以加一个1X2的小块进去，然后进行消除，我的沙雕做法是判断所有的两个之差为偶则可消除，刚看到大佬做法，只判断奇偶也可以，想来也是，判断没一列的奇偶，要么全奇，要么全偶，才有可能做差为偶。以下是ac代码

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
int t,sum,n;
int a[1000];
bool pd(int x)
{
	rep(i,1,x){
		rep(j,i+1,x){
			if(abs(a[i]-a[j])%2==0)
				continue;
			else
				return false;
		}
	}
	return true;
}
int main()
{
	//ios::sync_with_stido(0);
	//¼ÓËÙcin/cout
	cin>>t;
	while(t--){
		cin>>n;
		rep(k,1,n){
			cin>>a[k];
		}
		if(pd(n))
			pf("YES\n");
		else
			pf("NO\n");
	}
	return 0;
}

B

判断回文子序列，若某个数出现次数>=3，则必是回文子序列，若某个数字出现两次，且这个数字出现两次的位置不相邻，则也是回文子序列，骄傲的ac了一发。。。

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
int t,n,flag=0;
int a[5007],b[5007];
int main()
{
	//ios::sync_with_stido(0);
	//加速cin/cout
	cin>>t;
	while(t--){
		cin>>n;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		flag=0;
		rep(i,1,n){
			cin>>a[i];
			b[a[i]]++;
			if(b[a[i]]==2 && a[i]!=a[i-1] && a[i]!=a[i+1])
				flag=1;
			if(b[a[i]]>2)
				flag=1;
		}
		if(flag)
			pf("YES\n");
		else
			pf("NO\n");
	}
	return 0;
}

C

C题是寻找最小跳的步幅，所以找到r可以停留，然后判断两个r之间的最大距离就行，然后最后判断一下n+1和找到的最右边的r的距离与最大距离再次比较一次，然后即为所求。

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
int t,maxn=1,k,l,r,flag=0;
string s;
int main()
{
	//ios::sync_with_stido(0);
	//¼ÓËÙcin/cout
	cin>>t;
	while(t--){
		cin>>s;
		s=s+"R";
		l=0;maxn=1;flag=0;
		for(int i=0;i<s.size();i++)
		{
			if(flag==0){
				if(s[i]=='R'){
					l=i;
					maxn=l+1;
					flag=1;						
				}
			}
			else{
				if(s[i]=='R')
				{
					maxn=max(maxn,i-l);
					l=i;
				}
			}
		}
		pf("%d\n",maxn);
	}
	return 0;
}

D

详细思路开头已经描述了

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
typedef long long LL;
const int maxn=5e5;
int n,l,r;
LL a[maxn],b[maxn],c[maxn],ans;
int main()
{
	//ios::sync_with_stido(0);
	//加速cin/cout
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n){
		cin>>b[i];
		c[i]=a[i]-b[i];
	}
	sort(c+1,c+1+n);
	l=1;r=n;
	while(r>l){
		if(c[r]+c[l]>0){
			ans=ans+r-l;
			r--;			
		}
		else{
			l++;
		}
	}
	pf("%lld",ans);
	return 0;
}

下面是枯燥却 有趣的补题环节了

E

//呜呜呜DP不会……