E. Tokitsukaze and Dragon's Breath

题目简介：

给定一个 行 列的网格，每一个坐标上面有不同数量的怪物，选定一个坐标释放 "龙之吐息" ，火焰会在矩形中会形成一个 'X' 形状。火焰会打败经过的每个坐标中的所有怪物。 alt 求在哪里释放 "龙之吐息" 可以打败最多的怪物

思路：

从左上到右下的主对角线上的点的坐标 满足 相同

从右上到左下的副对角线上的点的坐标 满足 相同

因此只需要计算出每一条主对角线和副对角线数值的和，然后枚举每一个点，让它成为X的中点，比较计算出的数值，取最大值。

代码如下

#include<bits/stdc++.h>
#define LL long long
#define N 1010
using namespace std;
LL q[N*2],w[N*2];
int t,n,m;
LL res[N][N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(q,0,sizeof q);
        memset(w,0,sizeof w);
        LL ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%lld",&res[i][j]);
                q[i+j]+=res[i][j];
                w[i-j+m]+=res[i][j];
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                LL temp=q[i+j]+w[i-j+m]-res[i][j];
                if(temp>ans) ans=temp;
            }
        printf("%lld\n",ans);
    }
    return 0;
}

D. Tokitsukaze and Concatenate‌ Palindrome

题目简介：

给定两个字符串 和 ，将它们包含的字母随意排列后,经过最少多少次的替换操作，才能使新的字符串 成为一个回文串

思路：

由于每个字符串中字母的顺序可以随意排列，因此，如果两个字符串中有相同的字母，我们要尽量的让这些相同的字母优先成为回文串中相互配对的部分，为了方便处理，我们可以直接把相同的删除，字符串剩下的部分保证了两个字母串不会有相同的部分，接下来考虑，字符串不同长度对结果的影响：

  • 若 与 长度相同，则直接把 为 或者把 为 ，所需操作次数即为删除相同字母后字符串 / 的长度。
  • 若 与 长度不同，则较长的字符串一定会跨过回文串的中心点，若较长的字符串拥有两个或两个以上相同的字母，则优先将这些字母放置在回文串的中心，再变换其他字母

代码如下

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int T,n,m,cnta[26],cntb[26],mn,len,ans;;
string s1,s2;
int main()
{
	
	scanf("%d",&T);
	while(T--)
	{
		memset(cnta,0,sizeof cnta);
		memset(cntb,0,sizeof cntb);
		scanf("%d%d",&n,&m);
		cin>>s1>>s2;
		if(n>m)
		{
			swap(n,m);
			swap(s1,s2);
		}
		for(int i=0;i<s1.size();i++) cnta[s1[i]-'a']++;
		for(int i=0;i<s2.size();i++) cntb[s2[i]-'a']++;
		for(int i=0;i<26;i++)
		{
			mn=min(cnta[i],cntb[i]);
			cnta[i]-=mn;
			cntb[i]-=mn;
		}
		len=(n+m)/2-n;
		for(int i=0;i<26;i++)
		{
			mn=min(cntb[i]/2*2,len*2);
			cntb[i]-=mn;
			len-=mn/2;
		}
		ans=0;
		for(int i=0;i<26;i++) ans+=cnta[i]+cntb[i];
		printf("%d\n",ans/2);
	}
	return 0;
}

B. Tokitsukaze and Balance String (easy)

题目简介：

一个字符串是平衡的，当且仅当字符串中 "01" 连续子串的个数与 "10" 连续子串的个数相同。

定义字符串 的 为这样的位置数量：

  • 若当前位置上的字符为 ‘0’，将其反置后成为 ‘1’，此时字符串 是平衡的；
  • 若当前位置上的字符为 ‘1’，将其反置后成为 ‘0’，此时字符串 是平衡的。

给定一个仅由 ‘1’，‘0’，‘?’ 组成的字符串，其中，‘?’ 可以替换成 ‘0’ 或者 ‘1’。假设 ‘?’ 有 个，则显然替换过后可以得到 个不同的字符串，问这 个字符串对应的 之和是多少，答案对 取模

思路：

暴力出奇迹

代码如下

#include <bits/stdc++.h>
#define ll long long
#define MAX 200010
#define mod 1000000007
using namespace std;
char s[MAX];
int n,ans;
void dfs(int x)
{
	if(x==n+1)
	{
		int i,j,cnt01,cnt10;
		for(i=1;i<=n;i++)
		{
			s[i]^=1;
			cnt01=cnt10=0;
			for(j=2;j<=n;j++)
			{
				if(s[j-1]=='0' && s[j]=='1') cnt01++;
				else if(s[j-1]=='1' && s[j]=='0') cnt10++;
			}
			if(cnt01==cnt10) ans++;
			s[i]^=1;
		}
		return;
	}
	if(s[x]=='?')
	{
		s[x]='0';
		dfs(x+1);
		s[x]='1';
		dfs(x+1);
		s[x]='?';
	}
	else dfs(x+1);
}
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		scanf("%s",s+1);
		ans=0;
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}

完结撒花