B、 乐***对
题意：给出n个人，将这些人分为若干个组，每个人对应的一个值a[i]，表示这个人所在队伍的人数只要有a[i]个人才可以，问最多可以组成多少个队伍？若不能组成队伍，则输出-1.
思路：我们考虑贪心的算法，我们令dp[i]表示当前到i的时候我们可以组成的最多的队伍数量。那么，我们可以直到，当我们到达i的时候，我们要考虑将i分到哪个组里面，我们可以将它们与i-1组成一组，如果i>=a[i]的话，我们也可以让[i-a[i]+1,i]这些组成一组，所以我们可以得到状态转移方程：
所以我们直接进行一个dp即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[100010],dp[100010];
int ans=0;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
if(n<a[n]){
cout<<"-1"<<endl;
return 0;
}
for(int i=1;i<=n;i++){
if(i>=a[i]) ans=dp[i-a[i]]+1;
dp[i]=max(ans,dp[i-1]);
}
cout<<ans<<endl;
return 0;
}D、 巅峰对决
题意：给出一个序列，保证序列中每个数字都是不一样的，要求对序列进行单点修改和区间查询，查询区间里面的序列知否可以重新组成一个连续的序列。
思路：一个线段树板子题，可惜比赛时没注意看清题目，我们看到对于每次查询，我们确保我们序列里面的数字都是不同的，那么我们只要查询当前访问序列的最大和最小值，，然后与区间长度进行比较即可判断出来，这样，问题就转化为单点修改+区间查询最大和最小值了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int tree1[N<<2],tree2[N<<2];
int a[N],n,q;
void build(int node,int l,int r){
if(l==r){
tree1[node]=tree2[node]=a[l];
return;
}
int mid=(l+r)>>1,left_node=2*node,right_node=2*node+1;
build(left_node,l,mid);
build(right_node,mid+1,r);
tree1[node]=min(tree1[left_node],tree1[right_node]);
tree2[node]=max(tree2[left_node],tree2[right_node]);
}
void update(int node,int l,int r,int x,int val){
if(l==r){
a[x]=val;
tree1[node]=tree2[node]=val;
return;
}
int mid=(l+r)>>1,left_node=2*node,right_node=2*node+1;
if(x<=mid&&x>=l) update(left_node,l,mid,x,val);
else update(right_node,mid+1,r,x,val);
tree1[node]=min(tree1[left_node],tree1[right_node]);
tree2[node]=max(tree2[left_node],tree2[right_node]);
}
int query_mi(int node,int l,int r,int x,int y){
if(y>=r&&x<=l) return tree1[node];
if(l==r) return tree1[node];
int mid=(l+r)>>1,left_node=node*2,right_node=node*2+1;
int ans=1e9+7;
if(x<=mid) ans=min(ans,query_mi(left_node,l,mid,x,y));
if(y>mid) ans=min(ans,query_mi(right_node,mid+1,r,x,y));
return ans;
}
int query_mx(int node,int l,int r,int x,int y){
if(y>=r&&x<=l) return tree2[node];
if(l==r) return tree2[node];
int mid=(l+r)>>1,left_node=node*2,right_node=node*2+1;
int ans=-1;
if(x<=mid) ans=max(ans,query_mx(left_node,l,mid,x,y));
if(y>mid) ans=max(ans,query_mx(right_node,mid+1,r,x,y));
return ans;
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(q--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
update(1,1,n,x,y);
}else{
int ans=query_mx(1,1,n,x,y)-query_mi(1,1,n,x,y)+1;
if(y-x+1==ans) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}E、使徒袭来
题意：给三个数的乘积，求出这三个数的和最小。
思路：数学问题，考察基本不等式。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
double n;
scanf("%lf",&n);
double tmp=pow(n,1.0/3.0);
double ans=3*tmp;
printf("%.3lf\n",ans);
return 0;
}F、核弹剑仙
题意：给出若干个比较，保证在这些比较合法的前提下，输出比每个武器更优的数量。
思路：我们先根据比较来进行建图，如果a优于b的话，我们可以建一条从从b到a的边。然后对于每个点从这该点开始进行一个dfs，即可求出我们的答案
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,tot,sum;
int head[N],ver[N],nxt[N];
bool vis[N];
void add(int x,int y){
ver[++tot]=y;
nxt[tot]=head[x],head[x]=tot;
}
void dfs(int x){
sum++,vis[x]=true;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(vis[y]) continue;
dfs(y);
}
}
int main(){
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
add(b,a);
}
for(int i=1;i<=n;i++){
sum=-1;
memset(vis,false,sizeof(vis));
dfs(i);
cout<<sum<<endl;
}
cout<<endl;
return 0;
}G、虚空之力
题意：给出一个字符串，对于k，i，n，g可以对答案贡献1，对于k，i，n，g，i，n，g可以为答案贡献2.问答案最大为多少？
思路：一个很显然的贪心，我们肯定要有限满足kinging的情况，只需记录下这些字符的个数然后进行一个合理的分配即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
map<int,int> mp;
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i<n;i++){
mp[s[i]]++;
}
int ans=0;
while(1){
if(mp['k']==0||mp['i']==0||mp['n']==0||mp['g']==0) break;
else{
if(mp['i']>1&&mp['n']>1&&mp['g']>1){
ans+=2;
mp['i']-=2,mp['n']-=2,mp['g']-=2;
mp['k']--;
}
else{
ans++;
mp['k']--;
mp['i']--,mp['n']--,mp['g']--;
}
}
}
cout<<ans<<endl;
return 0;
}H、社团游戏
题意：给出一个矩阵，找出满足矩阵里面每种字符不超过k个的最大矩阵，输出它的边长。
思路：哈希+二分。我们用num[i][j][k]表示i这个字符在矩阵行1-j，列为1-k的矩阵里面的个数，然后我们在二分答案的时候我们只需要比较是否超过k个即可，这里你也要对二维的哈希有个熟悉的了解。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int num[30][520][520];
char a[520][520];
bool judge(int x,int y,int mid){
for(int i=1;i<=26;i++){
int tx=x+mid-1,ty=y+mid-1;
int sum=num[i][tx][ty]-num[i][x-1][ty]-num[i][tx][y-1]+num[i][x-1][y-1];
if(sum>k) return false;
}
return true;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
for(int k=1;k<=26;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
num[k][i][j]=num[k][i-1][j]+num[k][i][j-1]+(a[i][j]-'a'+1==k)-num[k][i-1][j-1];
}
}
}
int l,r,mid;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
l=0,r=min(n-i+1,m-j+1);
int ans=0;
while(l<=r){
mid=(l+r)>>1;
// cout<<"mid:"<<mid<<endl;
if(judge(i,j,mid)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans;
if(j<m) cout<<" ";
}
cout<<endl;
}
return 0;
}I、名作之壁
题意：给你n个数字，第i个数字a[i]表示名作之壁第i天的销量。若某段区间[l,r]中最大值和最小值之差大于k，则称该区间为畅销区间。请问一共有多少个区间为畅销区间？
思路：既然是要对区间内的最大和最小值进行操作的话，我们可以用一个单调队列来对序列进行一个最大和最小值的维护，我们可以枚举每个区间的右端点，如果此时的r是一个畅销区间的话，那么直接对答案的贡献就是n-i+1,因为我们区间的右端点进行一个移动的话，当左端点不动的时候，我们可以知道这个区间里面的最大值肯定是大于等于[l,r]之间的最大值得，然后最小值同理一定是小于等于[l,r]之间的最小值的，那么区间里面的最大与最小值的差一定是大于等于k的，故得证！
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
typedef long long ll;
int n,k,b,c;
int a[10000010],q1[10000010],q2[10000010];
int f1=0,f2=0,r1=0,r2=0;
//f1,r1用来维护区间最小值，f2,r2用来维护区间最大值
int main(){
cin>>n>>k;
cin>>a[0]>>b>>c;
ll ans=0;
for(int l=1,r=1;r<=n;r++){
a[r]=((ll)a[r-1]*b+c)%mod;
while(r1>f1&&a[q1[r1-1]]>=a[r]) r1--; //维护最小值
q1[r1++]=r;
while(r2>f2&&a[q2[r2-1]]<=a[r]) r2--; //维护最大值
q2[r2++]=r;
while(a[q2[f2]]-a[q1[f1]]>k){
ans+=n-r+1,l++;
if(q1[f1]<l) f1++; //维护区间长度为正
if(q2[f2]<l) f2++;
}
}
cout<<ans<<endl;
return 0;
}J、逃跑路线
题意：求出一个数组里面的所有数字&&
&
...
$最后所得的值。
思路：这个如果对二进制比较熟悉的话应该很好理解，我们知道上面公式后面&下来之后就是1，所以我们只要对数组里面的最低的和判断一下奇偶性就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int ans=0;
while(n--){
string a;
cin>>a;
int len=a.size();
ans+=(a[len-1]-'0');
}
if(ans&1) cout<<"1"<<endl;
else cout<<"0"<<endl;
return 0;
}
京公网安备 11010502036488号