【详解】leetcode每日一题(5.12)+codeforces杂题

• leetcode每日一题
• • 944. 删列造序
• codeforces
• • C. OKEA
  • B. Roof Construction
  • B. A Perfectly Balanced String?

思路：
枚举每一列查看是否递增即可

class Solution {
public:
    int minDeletionSize(vector& strs) {
        int res=0;
        int n=strs.size(),m=strs[0].size();
        for(int i=0;i
            for(int j=0;j
                if(strs[j][i]>strs[j+1][i])
                {
                    res++;
                    break;
                }
            }
        }
        return res;
    }
};

思路：
等差数列 an=a1+(n-1)*d
每一段的权值和正好整除段长度，联想到等差数列，且公差为偶数
证明：
al=a1+(l-1) * d (1)
ar=a1+(r-1) * d (2)
Sn=(al+ar) * (r-l+1)/2; （3）
(1)(2)带入(3)
2 * a1+(l+r-2)d(r-l+1)/2;(4)
题目要求任意一子段 ：len | Sn
带入(4)
2 * a1+(l+r-2) * d/2 所以当d为2的倍数满足要求

#include 
using namespace std;
#define int long long
int _;
void solve()
{
	int n,k;
	cin>>n>>k;
	if(k==1)
	{
		puts("YES");
		for(int i=1;i<=n;i++)cout<
		puts("NO");
		return;
	} 
	puts("YES");
	int cnt=0;
	for(int i=1;i<=n*k;i+=2)
	{
		cnt++;
		cout<
		cnt++;
		cout<
	cin>>_;
	while(_--)solve();
	return 0;
}

思路：
输入n ，给定一个[0,n-1]的数组，每个数字只出现一次，求相邻两个数的最大异或值最小
给定这些数字的最大异或值最小为k,k为小于等于n-1的最大的2^m
例如n-1=(1010)B，则k=(1000)B
证明：大于k的两个数相互异或必然小于k，小于k的两个数相互异或必然小于k
一个大于k一个小于k异或必然大于k
当且仅当0与k异或时结果为k
所以可以输出 n-1,n-2,...k-1,k,0,1,2,3...,k-1

#include 
using namespace std;
int _;
int n;
void solve()
{
	cin>>n;
	int k=1;
	while((k<<1)=k;i--)cout<
	cin>>_;
	while(_--)solve();
	return 0;
}

思路：
找规律即可发现，当s[i]==s[i%e]时，并且每一个周期不出现一个字母超过1次

#include 
using namespace std;
const int N=31;
int st[N];
int _;
string s;
void solve()
{
	cin>>s;
	memset(st,false,sizeof st);
	for(int i=0;i
		for(int j=0;j
			if(s[i]==s[j]&&i!=j)
			{
				puts("NO");
				return;
			}
		}
	}
	for(int i=0;i
		if(s[i]!=s[i%cnt])
		{
			puts("NO");
			return ;
		}
	}
	puts("YES");
}
int main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}