https://codeforces.com/contest/1674
A-B模拟
C:
题目:
给定两个字符串 s 和 t
我们每次可以进行一次操作
对于字符串s
内的 'a'
我们替换成字符串 t
问你可以构成多少个不同的字符串(不进行操作也包括在内
思路:
分情况:
1.如果字符串t
存在a但不都是a 那么就是无限个(因为可以进行无限次替换)
2.如果全部都是a那么就为1
3.否则我们每次都能对于字符串t的每个字符有两种选择,替换或者不替换
次数为2^s.size()
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long//2的某个次幂会超int
//计算幂
int qm(int x,int y)
{
int sum=1;
for(int i=0;i<x;i++)
{
sum*=y;
}
return sum;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
string s,t;
cin>>s>>t;
int a_ji=0;
//判断替换字符串中a的数量
for(int i=0;i<t.size();i++)
if(t[i]=='a')a_ji++;
//只要长度大于1且存在'a' 那么我们可以使他的长度无限增加
//字符串数量就为无线
if(t.size()>1&&a_ji>0)
{
cout<<"-1"<<endl;
continue;
}
//如果长度为1且只有a 则只能为1
if(a_ji==t.size()&&t.size()==1)
{
cout<<1<<endl;
continue;
}
//否则我们就可以对字符串内任一进行替换
cout<<qm(s.size(),2)<<endl;
}
return 0;
}
易错点:
1.长度不同也算做子串
2.情况的划分
3.判断幂 要自己构造函数
4.开longlong
D:
题目:
给定3个数组,a,b,c ,一开始给定a数组中的数字,b和c都为空
进行两种操作
操作1:
每次选取a数组中的最后一个数组然后添加到b数组的中间位置
对于奇数个我们可以选择添加到中间数字的任意两边
直到数组a为空
操作2:
每次选取b数组的中间元素,如果对于b为偶数那么可以选取两个元素
对于选取的元素我们将它们添加到c数组末尾
直至b数组为空
思路:
我们发现两组操作似乎相反,但是每次我们发现存在可以添加到任意两边的情况,发现对于原数组他进行了相邻两个数字的交换
所以我们每次最优使得相邻两个元素构成递增,判断是否可以构成
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
signed main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[N],b[N];
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
//b 数组为递减数组 对照使用
sort(b,b+n);
//看相邻两个
for(int i=n-1;i>=1;i-=2)
{
if(a[i-1]>=a[i])swap(a[i-1],a[i]);
}
bool p1=true;
for(int i=0;i<n;i++)
{
if(a[i]!=b[i])
{
p1=false;
break;
}
}
if(p1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
E:
题目:
给定一组数字,我们可以对任意的数字减2,并且使它相邻的数字减1
问:最少操作几次得到 2个数字被减少到0或者以下
思路:
贪心:
情况1:
每次找到最小值和次小值,然后分别对其进行减2
ans=(a+1>>1)+(b+1>>1)
情况2:
对于相邻的两项:
(1)两者中最大值大于较小值两倍:ans=max+1>>1
(2)显然对于 最大值大于最小值的两倍 我们直接全部攻击最大值
如果不大于 那么 存在一个时刻 x==y 这时 如果我们还全部攻击
原来的最大值显然存在浪费 所以 相等时我们攻击这时较大值
ans=(a+b+2)/3;
情况3:
对于间隔的两项:
(1)如果两边超级小中间超级大,那么
我们对中间的减2,对两边-1,
ans=max(a[i-1],a[i+1]])
(2)如果两边超级小中间超级大,但是两边也有差距
可以存在一种情况
ans=(min(a[i+1],a[i])+(abs(a[i+1]-a[i-1])+1>>1))
先对中间攻击,然后使得两者较小者变为0,随后使另一个减2
对于所有的情况我们取min
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int a[N];
int b[N];
int main()
{
cin>>n;
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=(a[i]+1)/2;
}
//找到其中最小者和次小者
sort(b+1,b+n+1);
ans=min(ans,b[1]+b[2]);
for(int i=1;i<=n-1;i++)
{
int minn=min(a[i],a[i+1]);
int temp=a[i]+a[i+1]-minn;
// 如果相邻两项存在这种关系那么这种就是最优解
if(temp>=minn*2)
{
ans=min(ans,(temp+1)/2);
}else
{
ans=min(ans,(a[i]+a[i+1]+2)/3);
}
}
for(int i=2;i<=n-1;i++)
{
//全部敲中间
int temp=max(a[i-1],a[i+1]);
ans=min(ans,temp);
//部分中间,其次敲最大
ans=min(ans,min(a[i+1],a[i-1])+(abs(a[i+1]-a[i-1])+1>>1));
}
cout<<ans<<endl;
return 0;
}
牛蛙牛蛙 i了 我滴宝
♥