A
直接模拟
#include <bits/stdc++.h>
using namespace std;
#define maxx 1000
#define INF 0x3f3f3f3f
int n,m,a,b;
int main()
{
int a,b,c,d,e,A,B,C,D;
cin>>a>>b>>c>>d>>e>>A>>B>>C>>D;
if(a*A+B*b+C*c-d*D>e) cout<<"YES\n";
else cout<<"NO\n";
}
B
除了贪心，也可以采用动态规划
由于使用顺序不定，为了使得给定状态伤害达到最优，将两者从大到小排序，进行状态转移，状态定义为使用i次B,j次A,具体看代码
#include <bits/stdc++.h>
using namespace std;
#define maxx 1000
#define INF 0x3f3f3f3f
int n,m,a,b,x,ans=INF;
int A[maxx];
int B[maxx];
int dp[maxx][maxx];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
cin>>n>>m>>x;
for(int i=1;i<=n;++i) cin>>A[i];
for(int i=1;i<=m;++i) cin>>B[i];
sort(A+1,A+1+n,cmp);
sort(B+1,B+1+m,cmp);
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)
dp[i][j]=-INF;
dp[0][0]=0; //B,A
for(int i=1;i<=m;++i)
for(int j=0;j<=n;++j)
{
dp[i][j]=dp[i-1][j]+B[i];
if(j>0)
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+B[i]*A[j]);
}
ans=INF;
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)
if(dp[i][j]>=x)
ans=min(ans,i+j);
if(ans==INF) cout<<-1;
else cout<<ans;
}
C
可以推导出公式，直接计算即可。
#include <bits/stdc++.h>
using namespace std;
#define maxx 1000
#define INF 0x3f3f3f3f
#define int long long
int n,m,a,b,c,x,t,ans=INF;
int A[maxx];
int B[maxx];
int dp[maxx][maxx];
int pow(int a,int b)
{
int d=1;
for(int i=1;i<=b;++i)
d=d*a;
return d;
}
signed main()
{
cin>>t;
for(int i=1;i<=t;++i)
{cin>>a>>b>>c;
double ans=0;
ans=(pow(a,16)+1820*(pow(a,12)*pow(b,4)+pow(a,12)*pow(c,4)))/pow(16,16);
//cout<<ans<<"\n";
printf("%.12lf\n",ans);
}
}
D
题目不严谨，应该说在这个题目内，两个字符串不同子序列选取位置不同，预处理出指定字母首尾长度指定的个数。
#include <bits/stdc++.h>
using namespace std;
#define maxx 1000
#define INF 0x3f3f3f3f
#define int long long
#define mod 998244353
int n,m,a,b,c,x,t,ans=INF;
int A[maxx];
int B[maxx];
string s;
int jc[maxx];
int jcf[maxx];
int dp[30][30][maxx]; //i字母开头,j字母结尾,长k的个数
int ksm(int a,int b,int n)
{
if(b==1) return a%n;
int ans=ksm(a,b/2,n);
ans=((ans%n)*(ans%n))%n;
if(b%2==0) return ans;
else return ((ans%n)*(a%n))%n;
}
int C(int i,int j)
{
return (jc[i]*((jcf[j]*jcf[i-j])%mod))%mod;
}
void build()
{
jc[0]=jcf[0]=1;
for(int i=1;i<=600;++i)
{jc[i]=(jc[i-1]*i)%mod;
jcf[i]=(jcf[i-1]*ksm(i,mod-2,mod))%mod;
}
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
for(int k=2;k<=j-i+1;++k)
dp[s[i]-'a'][s[j]-'a'][k]=(dp[s[i]-'a'][s[j]-'a'][k]+C(j-i-1,k-2))%mod;
}
signed main()
{
cin>>n>>s>>m;
s="0"+s;
build();
for(int i=1;i<=m;++i)
{
char a,b;
int x;
cin>>a;getchar();
cin>>b;cin>>x;
cout<<dp[a-'a'][b-'a'][x]<<"\n";
}
}
E.1
提供一种不用线段树的做法。
首先将两种方案从二维转化为一维数组，要求修改时实时修改给定的一维数组，并且维护map<int,int> M[2][char],即1维是哪一种方案，二维是所有小写字母，map<int,int>是指定方案与字母出现位置映射到指定方案字母位置是否出现，如果前三维度同时确定，那么不会重复，一个位置只有一个字母，维护此map的插入与删除，查询时，遍历所有小写字母，找到指定方案下每一个小写字母的大于当前位置的第一次出现位置，贪吃蛇可到达的位置一定小于这点，对除了当前位置的所有字母进行遍历，对位置取最小值，此最小值减1即为可到达的最大位置，因为此位置一定是一个字母的第一次出现位置，所以后面不可达，而此位置和行动位置之间不存在其他字母的第一次出现，即所有字母的第一次出现都在此外，故只有当前位置的字母，复杂度O(26nlogn)。
#include<bits/stdc++.h>
using namespace std;
#define maxx 444000
#define INF 0x3f3f3f3f
#define int long long
#define mod 1000000007
int x,y,t,a,b,n,m,p,c,k;
char data_1[2][maxx];
map<int,int> M[2][maxx];
string s;
int cal(int num,int x,int y)
{
if(num==0)
{
if(x%2==0) return m*(x-1)+m-y+1;
else return m*(x-1)+y;
}
else
{
if(y%2==1) return n*(y-1)+x;
else return n*(y-1)+n-x+1;
}
}
void add(int num,char a,int which)
{
data_1[num][which]=a;
++M[num][a][which];
}
signed main()
{
cin>>n>>m;
getchar();
for(int i=1;i<=n;++i)
{getline(cin,s);
for(int j=1;j<=m;++j)
{
char a=s[2*(j-1)];
int e=cal(0,i,j);
data_1[0][e]=a;
++M[0][a][e];
e=cal(1,i,j);
data_1[1][e]=a;
++M[1][a][e];
}
}
int q;
cin>>q;
for(int i=1;i<=q;++i)
{
cin>>a>>b>>c;
char d;
if(a==1)
{cin>>d;
int e=cal(0,b,c);
M[0][data_1[0][e]].erase(e);
data_1[0][e]=d;
++M[0][d][e];
e=cal(1,b,c);
M[1][data_1[1][e]].erase(e);
data_1[1][e]=d;
++M[1][d][e];
}
else if(a==2)
{
int e=cal(0,b,c);
d=data_1[0][e];
int ans=n*m+1;
for(int i='a';i<='z';++i)
{
if(i==d) continue;
if(!M[0][i].empty())
{ auto j=M[0][i].lower_bound(e);
if(j!=M[0][i].end())
ans=min(ans,j->first);
}
}
cout<<ans-e<<"\n";
}
else if(a==3)
{
int e=cal(1,b,c);
d=data_1[1][e];
int ans=n*m+1;
for(int i='a';i<='z';++i)
{
if(i==d) continue;
if(!M[1][i].empty())
{ auto j=M[1][i].lower_bound(e);
if(j!=M[1][i].end())
ans=min(ans,j->first);
}
}
cout<<ans-e<<"\n";
}
}
}
E.2
提供一种使用线段树的方法，线段树维护两个值:1.线段树代表区间的首端点字母，2.从首端点的连续区间长。
支持单点的修改和区间的查询。
修改:修改点后用子节点更新父节点，更新方式为:父节点的1值为左子的值，如果左子连续区间为左子长，则连续区间为二者之和，否则为左子连续区间长。
查询:依照一般的线段树查询方式，不使用返回值，取代的，将另外将访问到的1值和目标值一致的区间的左端点，连续区间右端点加入向量，由于查询顺序可以保证区间呈现递增。查询完毕遍历向量，如果当前向量是第一个或者其左端点与前一个右端点差1，即这两个连续区间的合并连续，那么继续遍历，否则退出。
复杂度O(nlogn)
参考如下代码
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define maxx 8822000
#define maxx2 0x3f3f3f3f
int a,b,d,k,m,t,n,ansmax,Smax,x,ans1,ans2,neww,c;
int l,r;
int xmax,ymax;
int pj;
int sum=0;
char all[maxx][2];
vector<pair<int,int>> ans;
string s;
struct point
{
int sum;
char a;
}JD[maxx][2];
int ls(int root)
{
return 2*root;
}
int rs(int root)
{
return 2*root+1;
}
void update_from_son(int root,int l,int r,int which)
{
int mid=(l+r)/2;
JD[root][which].a=JD[ls(root)][which].a;
JD[root][which].sum=JD[ls(root)][which].sum;
if(JD[ls(root)][which].a==JD[rs(root)][which].a&&JD[ls(root)][which].sum==mid-l+1)
JD[root][which].sum=JD[root][which].sum+JD[rs(root)][which].sum;
}
void build(int root,int l,int r,int which)
{
if(l==r)
{
JD[root][which].sum=1;
JD[root][which].a=all[l][which];
return;
}
int mid=(l+r)/2;
build(ls(root),l,mid,which);
build(rs(root),mid+1,r,which);
update_from_son(root,l,r,which);
}
void modify(int root,int l,int r,int ql,int qr,char target,int which)
{
if(l==ql&&r==qr)
{
JD[root][which].a=target;
return ;
}
int mid=(l+r)/2;
if(ql<=mid) modify(ls(root),l,mid,ql,min(qr,mid),target,which);
if(qr>=mid+1) modify(rs(root),mid+1,r,max(mid+1,ql),qr,target,which);
update_from_son(root,l,r,which);
}
void query(int root,int l,int r,int ql,int qr,char target,int which)
{
if(l==ql&&r==qr)
{
if(target==JD[root][which].a)
ans.push_back(pair<int,int>(l,l+JD[root][which].sum-1));
return ;
}
int mid=(l+r)/2;
if(ql<=mid) query(ls(root),l,mid,ql,min(qr,mid),target,which);
if(qr>=mid+1) query(rs(root),mid+1,r,max(mid+1,ql),qr,target,which);
}
int cal(int num,int x,int y)
{
if(num==0)
{
if(x%2==0) return m*(x-1)+m-y+1;
else return m*(x-1)+y;
}
else
{
if(y%2==1) return n*(y-1)+x;
else return n*(y-1)+n-x+1;
}
}
signed main()
{
cin>>n>>m;
getchar();
for(int i=1;i<=n;++i)
{getline(cin,s);
for(int j=1;j<=m;++j)
{
char a=s[2*(j-1)];
int e=cal(0,i,j);
all[e][0]=a;
e=cal(1,i,j);
all[e][1]=a;
}
}
build(1,1,n*m,0);
build(1,1,n*m,1);
int q;
cin>>q;
for(int i=1;i<=q;++i)
{
cin>>a>>b>>c;
char d;
if(a==1)
{cin>>d;
int e=cal(0,b,c);
modify(1,1,n*m,e,e,d,0);
all[e][0]=d;
e=cal(1,b,c);
modify(1,1,n*m,e,e,d,1);
all[e][1]=d;
}
else if(a==2)
{
int e=cal(0,b,c);
ans.clear();
query(1,1,n*m,e,n*m,all[e][0],0);
int ans1=0;
for(int i=0;i<ans.size();++i)
{if(i==0||ans[i].first==ans[i-1].second+1)
ans1=ans1+ans[i].second-ans[i].first+1;
else break;
}
cout<<ans1<<"\n";
}
else if(a==3)
{
int e=cal(1,b,c);
ans.clear();
query(1,1,n*m,e,n*m,all[e][1],1);
int ans1=0;
for(int i=0;i<ans.size();++i)
{if(i==0||ans[i].first==ans[i-1].second+1)
ans1=ans1+ans[i].second-ans[i].first+1;
else break;
}
cout<<ans1<<"\n";
}
}
}
F
给出一些证明
对于[l,r]的序列，计算出ai*(2^(r-i)),后取最大值，首先此表达是如果一个数字始终符合要求后被不断传递的表达，其次可以说明如果这个值是最大的，则这个数字在传递过程中不会被取代，因为若在i处取得最大值，在i以前的运算得到值都不如i,故到i后会被i取代，在i以后的运算值也不如i,故i也不会被取代。
对于[l,r]的序列，计算出ai*(2^(r-i)),后取最大值，首先此表达是如果一个数字始终符合要求后被不断传递的表达，其次可以说明如果这个值是最大的，则这个数字在传递过程中不会被取代，因为若在i处取得最大值，在i以前的运算得到值都不如i,故到i后会被i取代，在i以后的运算值也不如i,故i也不会被取代。
其次讨论如下:
1,非正数序列，如果有0，则有一项0，肯定是最大的且为0。
2.非正数序列，如果没有0，则在后30项有最大值，因为2^30>10^9,项数过多会超出范围比最后一项还小。
3.存在第一个正数，则向后找30项，因为到了这个项后，运算结果是此项的2倍，因为前面全是负数，而后30项运算后保证结果超出了10^9,后面的运算使得这个结果不会被取代。
京公网安备 11010502036488号