简述：
A了5题，相比于上次div3多了一题，也算有进步吧。。。虽然过了5题，但吃了不少罚时，D wa了两次，F wa了四次！！ 把这几道题写一下，弄清思路，再补充一些新的想法。（未完待续：
---加了18分，但还没回到最高………… 24.9.2
暂时补完A-F 剩下两题后面再说............ 24.9.3 ）
A. Sakurako's Exam
题意：给出a个1和b个2，然后对每个数添加+号或者-号，使得最终的和为0
一开始判断特殊情况，再细分b的数量和a的数量
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int a,b;
cin>>a>>b;
if(a==0 && b==0){
cout<<"YES"<<endl;
return;
}
if(b%2==0){
if(a%2==0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
else{
if(a<2){
cout<<"NO"<<endl;
}
else if(a==2){
cout<<"YES"<<endl;
}
else{
a-=2;
if(a%2==0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
B. Square or Not
题意： 给出一个字符串，由矩阵的每行组成，问是否是美丽矩阵（最外一圈为1，里面为0）的同时是正方形矩阵
先判断字符串长度是否为n的平方 然后再判断美丽矩阵
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
int op = n;
n = sqrt(n);
char a[n+1][n+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=s[(i-1)*n+j-1];
}
}
int p =0;
for(int i=1;i<=n;i++){
if(a[1][i]=='0') p=1;a[1][i]='k';
if(a[n][i]=='0') p=1;a[n][i]='k';
if(a[i][1]=='0') p=1;a[i][1]='k';
if(a[i][n]=='0') p=1;a[i][n]='k';
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]!='k'){
if(a[i][j]!='0'){
cout<<"NO"<<endl;
return;
}
}
}
}
int l = sqrt(op);
if(l*l==op){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
C. Longest Good Array
给出边界l,r（包含）,求出一个数组，满足所有元素在边界值内，且满足数的递增和逐级递增 求数组a的最长长度
以贪心的思路思考，最优的数量就是1 2 4 7这样隔着递增，得到最大数量。 考虑到数的范围为1-1e9，枚举一定会爆时间 再观察得出，以l开始，然后按照+1 +2 +3 逐渐到r，的数量即为答案，可推以l为首项，d=1的等差数量前n项合为r-l 然后枚举n就行了
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
LL l,r;
cin>>l>>r;
LL res = r-l;
int n = 1;
while(n*(n+1)<=res*2){
n++;
}
cout<<n<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
D. Sakurako's Hobby
给出n个数，然后根据每个ai值，跳到对应点，给出字符串，如果值为0则加一，问1到n每个点最后的值为多少
考虑会有多次重复计算，可以保存一次最大值，然后后续相同点直接赋值复杂度为o(n)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5+6;
void solve()
{
int n;
cin>>n;
vector<int> a(n+1,0),b(n+1,0),us(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
string s;
cin>>s;
for(int i=1;i<=n;i++){
if(us[i]) continue;
int sz = 0;
while(!us[i]){
us[i]=1;
sz+= (s[i-1]=='0');
i = a[i];
}
while(us[i]!=2){
b[i]=sz;
us[i]=2;
i = a[i];
}
}
for(int i=1;i<=n;i++){
cout<<b[i]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
E.
F.
赛后重写了一遍，最后wa了5发才弄明白
题意：
从数组中任意取两个数的之积的和为Q ,取的次数为P,求Q/p %mod 的值
运用费马小定理求解，化1/p = pow(p,mod-2)%mod ,然后对于加减的地方要及时%MOD
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int MOD = 1e9+7;
LL kfc(LL x,LL y){
LL ans = 1;
while(y){
if(y&1) ans = ans*x%MOD;
y >>= 1;
x = x*x%MOD;
}
return ans;
}
void solve()
{
LL n;
cin>>n;
vector<LL> a(n+1,0);
LL op = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
op += a[i];
}
LL sum = 0;
LL pre = 0;
for(int i=1;i<=n;i++){
pre+=a[i];
sum=(sum+a[i]*((op - pre)%MOD))%MOD;
}
LL res = LL(n*(n-1)/2)%MOD;
res = kfc(res,MOD-2);
cout<<(sum*res)%MOD<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
E. Alternating String
题意：
对于一个字符串修改其为交替字符串所需最小步骤，最多使用一次删除字符操作，任意次交换字符操作， 保证偶数位置字母相同和奇数位置上字母相同，且字符串长度为偶数。
分开判断，对于偶数，无需进行删除操作，只需判断出现字母最大数即可
对于奇数，因为任意位置字符被改变，其后缀字符串奇偶性都会改变，故考虑后缀和 和 前缀和 结合， pre1 + sub2 和 pre2 + sub1
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
vector<int> a(27,0),b(27,0);
for(int i=0;i<s.length();i++){
if(i%2==0){
a[s[i]-'a']++;
}
else{
b[s[i]-'a']++;
}
}
if(s.length()%2==0){
int sum1 = 0,sum2 = 0;
for(int i=0;i<26;i++){
sum1 = max(sum1,a[i]);
sum2 = max(sum2,b[i]);
}
cout<<n/2-sum1+n/2-sum2<<endl;
}
else{
vector<int> pref[2] ={vector<int>(26),vector<int>(26)};
vector<int> sub[2] = {vector<int>(26),vector<int>(26)};
for(int i=n-1;i>=0;i--){
sub[i%2][s[i]-'a']++;
}
int res = n+1;
for(int i=0;i<n;i++){
sub[i%2][s[i]-'a']--;
int ans = n;
for(int k=0;k<2;k++){
int mx = 0;
for(int j=0;j<26;j++){
mx = max(mx,pref[k][j]+sub[1-k][j]);
}
ans -=mx;
}
res = min(res,ans);
pref[i%2][s[i]-'a']++;
}
cout<<res<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t ;
cin>>t;
while (t--)
{
solve();
}
}
京公网安备 11010502036488号