牛客练习赛58
牛客练习赛58
C.矩阵消除游戏 题意:给定n行m列的矩阵，现在你可以进行k次操作，每次操作选择一行或者一列，积分加上你选定的这行或者这列的权值和，然后把它们变成0。问k次操作之后能得到的最大积分是多少？
n,m<=15
首先当k大于等于n或者m的时候就可以全选了，因此可以令k=min(k,min(n,m))
根据数据范围很容易想到二进制枚举，枚举选择的行数，然后把剩下的列排序选择较大的就行了。
#include
using namespace std;
#define int long long
const int maxm=20;
int a[maxm][maxm];
int sum[maxm];
int n,m,k;
bool cmp(int a,int b){
return a>b;
}
signed main(){
cin>>n>>m>>k;
k=min(k,min(n,m));
for(int i=0;i<n;i++){
for(int j=0;j>a[i][j];
}
}
int ans=0;
for(int i=0;i<(1<<n);i++){//枚举选择哪些行
int tot=0;
for(int j=0;j>j&1)tot++;
if(tot>k)continue;
int temp=0;
for(int j=0;j<m;j++)sum[j]=0;
for(int r=0;r<n;r++){
for(int c=0;c>r&1)temp+=a[r][c];
else sum[c]+=a[r][c];
}
}
sort(sum,sum+m,cmp);
int remain=k-tot;
for(int j=0;j<remain;j++){
temp+=sum[j];
}
ans=max(ans,temp);
}
cout<<ans<<endl;
return 0;
}
D.迷宫
题意：
n,m<=1e3
需要先推出不能左走和上走的结论，然后问题就简化了，以后写题不能无脑按题目的意思走
#include
using namespace std;
#define int long long
const int maxm=1e3+5;
char s[maxm][maxm];//1是障碍
int d[maxm][maxm];
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)d[i][j]=1e9;
d[1][1]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='0'){//如果这个位置没有障碍
if(j+1<=m&&s[i][j+1]=='0'){
d[i][j+1]=min(d[i][j],d[i][j+1]);//优先向右走
}
if(i+1<=n&&s[i+1][j]=='0'){//向下走
if(j+1<=m&&s[i][j+1]=='0'){//需要加障碍
d[i+1][j]=min(d[i+1][j],d[i][j]+1);
}else{//不需要加障碍
d[i+1][j]=min(d[i+1][j],d[i][j]);
}
}
}
}
}
if(d[n][m]==1e9)cout<<-1<<endl;
else cout<<d[n][m]<<endl;
return 0;
}
E.最大GCD
题意:
给一个长度为n的数组a，和q个询问
每次询问给l，r，x，要求在区间l，r中选择一个子区间st，ed，满足：
gcd(a(st),a(st+1)…,a[ed],x)最大，也就是选择的子区间gcd再与x计算gcd，使得答案最大，输出这个最大值
所有数据<=1e5
坑点在于虽然告诉你要选择子区间，但是我们知道区间中的数变多，区间gcd不可能变大，只可能不变或者变小，因此子区间长度为1是最优的，那么问题就变为选择区间中的一个数，使得这个数和x的gcd最大。
解法1：
看别人题解发现可以莫队，因为这题是可离线的区间问题，而且不带修改。做法：
因为x和其他数求gcd，结果一定是x的一个因子，我们对于每一个在区间内的数a(i)，把a(i)的所有因子的出现次数都加1，
利用莫队统计区间内每个数的因子出现次数，统计完之后遍历x的因子，取在区间内出现的最大值即可
莫队的复杂度不是很会算
解法2：
题解的做法没看懂，难受，下次回来补。
先预处理了1e5以内所有数的因子
这个代码提交之后，耗时在600-tle徘徊，有点玄学。
#include
using namespace std;
const int maxm=1e5+5;
struct Node{
int l,r,x,id,pos;
}e[maxm];
vectorfac[maxm];
int mark[maxm];
int res[maxm];
int a[maxm];
void init(){//预处理每个数的因子
for(int i=1;i<maxm;i++){
for(int j=i;j<maxm;j+=i){
fac[j].push_back(i);
}
}
}
bool cmp1(Node a,Node b){
if(a.pos!=b.pos)return a.pos<b.pos;
return a.rb;
}
void add(int x){
for(int v:fac[a[x]]){
mark[v]++;
}
}
void del(int x){
for(int v:fac[a[x]]){
mark[v]--;
}
}
signed main(){
init();
int n,q;
scanf("%d%d",&n,&q);
int block=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=q;i++){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
e[i]={l,r,x,i,l/block};
}
sort(e+1,e+1+q,cmp1);//把询问排序
int l=e[1].l,r=l-1;
for(int i=1;i<=q;i++){
while(le[i].l)add(--l);
while(re[i].r)del(r--);
int len=fac[e[i].x].size();
for(int j=len-1;j>=0;j--){
int v=fac[e[i].x][j];
if(mark[v]){
res[e[i].id]=v;
break;
}
}
}
for(int i=1;i<=q;i++){
printf("%d\n",res[i]);
}
return 0;
}
code(莫队2)：
改了一下，对于每个位置i的数和询问中的x单独求因子而不是向上面一样预处理，耗时变成500-700左右了。
#include
using namespace std;
const int maxm=1e5+5;
struct Node{
int l,r,x,id,pos;
}e[maxm];
vectorfac[maxm];
vectorf[maxm];
int mark[maxm];
int res[maxm];
int a[maxm];
bool cmp1(Node a,Node b){
if(a.pos!=b.pos)return a.pos<b.pos;
return a.rb;
}
void add(int x){
for(int v:f[x]){
mark[v]++;
}
}
void del(int x){
for(int v:f[x]){
mark[v]--;
}
}
signed main(){
int n,q;
scanf("%d%d",&n,&q);
int block=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
for(int j=1;j*j<=a[i];j++){
if(a[i]%j==0){
f[i].push_back(j);
if(a[i]/j!=j)f[i].push_back(a[i]/j);
}
}
}
for(int i=1;i<=q;i++){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
e[i]={l,r,x,i,l/block};
if(fac[x].empty()){
for(int j=1;j*j<=x;j++){
if(x%j==0){
fac[x].push_back(j);
if(x/j!=j)fac[x].push_back(x/j);
}
}
sort(fac[x].begin(),fac[x].end(),cmp2);
}
}
sort(e+1,e+1+q,cmp1);//把询问排序
int l=e[1].l,r=l-1;
for(int i=1;i<=q;i++){
while(le[i].l)add(--l);
while(re[i].r)del(r--);
for(int v:fac[e[i].x]){
if(mark[v]){
res[e[i].id]=v;
break;
}
}
}
for(int i=1;i<=q;i++){
printf("%d\n",res[i]);
}
return 0;
}
F.XOR TREE(
简单树剖，下次回来码
作者：我到底在干嘛
