寒假营第五场
B 思维
可以删任意个数的字符串，但是不能删连续两个，每种删除方案的得分是"mygo"出现的次数，问全部方案的总分。
首先一个重要的观察是，由于不能删连续字符，删除后能出现"mygo"的字符串实际上只有八种，具体来说就是"mygo"中间的三个空都可以插入一个其他字符。对于这八种字符串，都有唯一的删除方式使删完出现一个"mygo"。
另一个重要的观察是，既然遍历所有删除方式，分别计算贡献很麻烦，那么我们可以分开计算每一个"mygo"对答案的贡献。对于每一个"mygo"，得到他的删除方式再mygo内部是唯一的，而外部可以随意删。我们需要外部随意删有多少种方案，这些方案的贡献都是1，也就是只含这一个mygo。
这就又引出一个问题，就是外部随意删的方案数怎么算。注意到这是随意删，因此方案数和具体是什么字符串无关，只和字符串长度有关，因此我们可以预处理，不用每次都算。具体来说，我们需要预处理出f[i]，表示长度为i的字符串，不删连续字符的前提下有多少种删除方案。这可以用一个递推实现，如果第i个字符被删了，那么第i-1个就不能删，再往前的随意，这样的方案数等于f[i-2]，如果第i个没被删，那么前i-1个都随意，这样的方案数是f[i-1]。最终得到f[i]=f[i-1]+f[i-2]，初始条件是f[1]=1,f[2]=2。这实际上就是斐波那契数列的递推式。
剩下的就是遍历所有mygo，分别计算贡献。遍历所有mygo具体可以遍历遍历整个字符串，检查每个位置是否出现上面八种串。
using namespace std;
const int M=1e9+7;
const int N=2e5+10;
int f[N];
string s;
bool check(string a,string b){
for(int i=0;i<a.size();i++){
if(a[i]==' ')continue;
if(a[i]!=b[i])return 0;
}
return 1;
}
int main(){
cin>>s;
int n=s.size();
s="!"+s+"soyorinlove";
f[0]=1;
f[1]=2;
for(int i=2;i<=n;i++){
f[i]=(f[i-1]+f[i-2])%M;//预处理
}
vector<string> t={"mygo","m ygo","m y go","m y g o",
"my go","my g o","myg o","m yg o"};
int ans=0;
// for(int i=0;i<=n;i++)cout<<f[i]<<' ';
// cout<<'\n';
for(int i=1;i<=n;i++){
for(auto j:t){
string x=s.substr(i,j.size());//检查是否出现八种字符串
if(check(j,x)){
ans=(ans+1ll*f[i-1]*f[n-(i+j.size())+1]%M)%M;//计算贡献
}
}
}
cout<<ans;
}
C思维
关键是意识到0放在哪最大数量都是一样的，那么为了方便计算肯定是用0把所有数隔开。接下来就好分析了，每一个数两侧能放的0的总数是a[i]-1，那么就从左往右遍历每一个能放零的空，每次确定0个数后，相当于把前后两个非零数的0的额度用了一部分，因此可以把这些额度剪掉，然后每个空能放的0的个数是前后两个非零数剩余额度的最小值。
边界情况是第一个数左边和最后一个数右边的空，只受一个数的额度约束。
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
long long ans=0;
ans+=a[1]-1;//最左边的空只收第一个数约束
a[1]=1;
for(int i=2;i<=n;i++){
int t=min(a[i-1],a[i]);//确定0个数
t--;
a[i]-=t;//额度减去本次放的0
a[i-1]-=t;
ans+=t;
}
ans+=a[n]-1;//最右边的空只收最后一个数限制
cout<<ans;
}
E 思维
每次可以选一个偶数K,然后给前k个数8加上一个[1,k]，问能否将数组变为不减的。由于加上的是一个升序数组[1,k]，每加一次都会让所有a[i]-a[i-1]变大1，因此不限操作次数的话早晚能让可以被操作的数组变成升序的。因此只要初始序列种所有元素都能被操作，就一定能变成升序的。
每次能操作的都是长度为偶的序列，因此如果序列长度为偶就一定能变成升序的。如果长度为奇数，前n-1个数能被操作，要满足第n-1个数小于等于第n个数，那么第n-1个数的大小就有一个上界，往前同理，第n-2,n-3个数的大小也都有上界。我们可以一路推出前面所有数的上界。因为操作次数越多越可能变成升序的，那么我们一定会把前面所有数都操作到上界，那么如果上界是不减的，最终就可以变成不减的。
具体往前推上界的时候，大区间操作会影响小区间，因此操作次数是会继承后一个数的。
using namespace std;
const int N=1e5+10;
long long a[N];
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n%2==0){
cout<<"YES";
}
else{
long long cnt=0;
bool ok=1;
for(int i=n-1;i>=2;i-=2){
//从倒数第二个数开始，最后一个操作不了
a[i]+=cnt*i;
a[i-1]+=cnt*(i-1);
//大区间的操作会影响小区间，先加上
if(a[i]>a[i+1]){
ok=0;
break;
//如果此时已经降序了，就失败了
//因为接下来的操作只能让小区间内数更大
}
long long t=(a[i+1]-a[i])/i;//计算到上界需要几次操作
a[i]+=t*i;//操作到上界
a[i-1]+=t*(i-1);
cnt+=t;//累加操作次数
}
for(int i=1;i<n;i++){
if(a[i]>a[i+1]){//检查是否不减
ok=0;
break;
}
}
if(ok)cout<<"YES";
else cout<<"NO";
}
cout<<'\n';
}
}
F 思维
这问还要输出操作次数。用E的写法就有点麻烦了。所以换了一种更简单的写法。
每次操作由于加上的是一个公差为1的等差数列，实际效果其实就是让前后两个数的差距缩小1（如果前面比后面大的话）。那么所需的最大操作次数实际上就是相邻两个数差距的最大值。
判断能否变为不减还可以用类似E的方法，这部分和计算最小操作次数是可以分开的。
using namespace std;
const int N=1e5+10;
long long a[N];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
long long ans=0,add=0;
for(int i=n-1;i>=1;i--){
if(n%2){
if(a[i+1]+add<a[i]){
cout<<-1;
goto over;
}
else{
if(i%2==0){
add+=(a[i+1]+add-a[i])/i;
//add就是操作次数
//其实并不需要真的算出来每个数的上界并修改
}
}
}
ans=max(ans,a[i]-a[i+1]);//更新最小次数
}
cout<<ans;
over:cout<<'\n';
}
}
GH 思维
构造一个排列p,让pi+i为质数。这题的教训是多试几组例子，样例不够就自己造几组，一般就能找到规律了。
比如对于1234，如果我给他加上4321，就变成了5555，都是质数，且用的也是一个排列。这给我们的启示是可以去寻找一段，然后把排列中连续的一段倒着加上，就能形成一段质数。为此我们可以先把所有不超过2n的质数都筛出来，然后对于一段，我们去寻找最小的可行的质数，作为加完之后的和，这样一段段处理就行了。
using namespace std;
bool vis[2020];
int ans[1010];
int main(){
int n;
cin>>n;
//质数筛
vis[1]=vis[0]=1;
for(int i=2;i<=sqrt(2*n);i++)
if(vis[i]==0)//如果是质数
for(int j=i*2;j<=n*2;j+=i)//不超过n的所有倍数都标记为合数
vis[j]=1;
for(int i=n;i>=1;i--){
int x=i+1;//从i+1开始找
while(vis[x])x++;//找最小的质数作为和
// cout<<i<<' '<<x<<'\n';
for(int j=x-i;j<=i;j++){//把前面一段都倒着加上一段排列
ans[j]=x-j;
}
i=x-i;//跳到这段前面一点，不减1是因为for结束时会减1
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}
J dp
n个区间，每个区间内选一个数，使得整个数组相邻数绝对值之差的和最小。
如果区间有交集，那么选交集里任意一个数都可以使得相邻数绝对值之差为0。但可能不是全部区间都有交集，对于有交集的可以按上述方法，对于没交集的，想要离得最近，元素肯定都在端点上，可以dp处理，dp(i)(j)表示第i个数取第i个区间左/右端点时，前i个区间的相邻数绝对值之差之和的最小值，j取0/1分别表示第i个数取左右端点。
using namespace std;
const int N=1e5+10;
int l[N],r[N];
vector<pair<int,int>>v;
long long dp[N][2];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
int L=1,R=1e9;
for(int i=1;i<=n;i++){//先处理出来区间的交集关系
if(l[i]>R||r[i]<L){//如果没有交集
v.push_back({L,R});//上一个区间成为一个独立区间
L=l[i];//更新当前区间
R=r[i];
}
L=max(L,l[i]);
R=min(R,r[i]);//如果有交集，当前区间取交集
}
v.push_back({L,R});//别忘了把最后一个区间也放进来
//至此处理出了所有独立的交集
for(int i=1;i<v.size();i++){
//当前区间取左端点，前一个区间可以取左右端点
dp[i][0]=min(dp[i-1][0]+abs(v[i].first-v[i-1].first),dp[i-1][1]+abs(v[i].first-v[i-1].second));
//当前区间取右端点，前一个可以取做右端点
dp[i][1]=min(dp[i-1][0]+abs(v[i].second-v[i-1].first),dp[i-1][1]+abs(v[i-1].second-v[i].second));
}
cout<<min(dp[v.size()-1][1],dp[v.size()-1][0]);
}
K 完全背包
每个人通知b个人的代价是a，只限制通知人数，不限制具体通知谁。问通知全部n个人的最小代价。这其实就是一个完全背包，人数n是容量，代价是价值，只不过这个价值我们想要他最小化，那就把完全背包里的max换成min。
另一点区别是，至少要有一个人是直接通知的，那么我们算出dp[1-n]后，再用dp结果算一下i个人直接通知，剩下人相互通知的最小代价。这个才是最终的最小代价
using namespace std;
const int N=1e3+10;
long long dp[N];
int main(){
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++)dp[i]=1e9;
dp[0]=0;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
if(b>=n)b=n-1;//能通知大于n个人，相当于能通知n个人
//有一个人必须直接通知，因此最大是n-1
for(int j=0;j<=n;j++){//完全背包容量从小到大枚举
dp[j]=min(dp[j],dp[max(0,j-b)]+a);
}
}
long long ans=1e9;
for(int i=0;i<n;i++){//一些人直接通知，剩下人相互通知，
//至少有一个人直接通知，枚举容量只能到n-1
ans=min(ans,dp[i]+(n-i)*p);
}
cout<<ans;
}
京公网安备 11010502036488号