第三次周赛题解
A.前缀和
观察题 cao
分奇偶
注意观察---奇数()
只有第一个和第二个会是奇数 后面全是前面累乘2
if(x%2!=0) x要么是第一个要么是第二个(无区别)因为1，2元素大小相等
剩下元素a[n]=pow(2,n-2)*x;
else 不是奇数化为奇数
ll q=x;//保存一下结果，后面要特判
while(x%2==0)x/=2;
ll w=w*pow(2,n-2); 如果w>q则输出w,否则输出q
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[21];
int t;
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>t;
while (t -- )
{
ll n,x;
cin>>n>>x;
if(x%2!=0)
{
ll q=pow(2,n-2);
cout<<q*x<<endl;
}
else {
ll w=x;
while(x%2==0)x/=2;
ll q=pow(2,n-2)*x;
if(q<w)cout<<w<<endl;
else cout<<q<<endl;
}
}
return 0;
}
B.
还不会 ---数学差的人是这样的
C.田径
基本不等式--数学死亡加1
a+b>=2 * sqrt(a*b);
由题意---得到a*b==n
我们只要保证存在一个解使得m>=(a+b+2)*2即可
for(int i=1;i<=n/i;i++)
{
if((i+n/i+2)*<=m)
return true;
}
return false;
#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int df=true;
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
if((i+n/i+2)*2<=m)
{df=false;cout<<"Good\n";break;}
}
}
if(df)
cout<<"Miss\n";
}
return 0;
}
D.国王的魔镜
判断回文的板子题
没看出来ccccc呜呜
先判断是否使回文数再判断后续
每次substr范围折半
#include<bits/stdc++.h>
using namespace std;
//const int N = 20;
bool hui(string d)
{
string c=d;
reverse(d.begin(),d.end());
if(d==c)return true;
return false;
}
int main()
{
string a,b,c,d;
cin>>b;
int l=b.size();
if(l==2)
{
if(b[0]==b[1])cout<<1<<endl;
else cout<<2<<endl;
return 0;
}
while(hui(b)&&l%2==0)
{
l/=2;
if(l==2)
{
if(b[0]==b[1])cout<<1<<endl;
else cout<<2<<endl;
return 0;
}
b=b.substr(0,l);
// cout<<b<<endl;
}
cout<<l<<endl;
return 0;
}
E.回家
与普通的bfs不同
因为有血量这种限制
bool vis的判定会出现问题
如果我此时去绕路捡血包可能会更加划算
因此我们不能直接判重-------剪枝掉血包(我们很容易想到血包只会捡一次)
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
#define eps(a,b) for(int i=a;i<=b;i++)
#define epq(a,b) for(int j=a;j<=b;j++)
int n,m;
int a[N][N];
bool vis[N][N];
int x,y,ox,oy;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{
int dx,dy,res,cnt;
};
int bfs()
{
queue<node>q;
q.push({x,y,6,0});
vis[x][y]=0;
while(q.size())
{
int mx=q.front().dx,my=q.front().dy,res=q.front().res,cnt=q.front().cnt;
q.pop();
if(res<=0)continue;
if(mx==ox&&my==oy)return cnt;
for(int i=0;i<4;i++)
{
int qo=res;
int nx=mx+d[i][0],ny=my+d[i][1];
if(nx<1||nx>n||ny<1||ny>m||!a[nx ny]||vis[nx[ny])continue;
qo--;
if(qo<=0){continue;}
if(a[nx][ny]==4)qo=6;
if(qo>=res)vis[nx][ny]=true;
q.push({nx,ny,qo,cnt+1});
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n>>m;
eps(1,n)
epq(1,m)
{
cin>>a[i][j];
if(a[i][j]==2)
x=i,y=j;
else if(a[i][j]==3)
ox=i,oy=j;
}
cout<<bfs();
return 0;
}
F.众数
死在一些思考问题上
每次查询直接for遍历x-y就行
每次用ans(元素是谁)和res(多少个)更新
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[1010];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
while(m--)
{
int f,x,y;
cin>>f>>x>>y;
if(f==0)
{
map<int,int>m;
int res=0,ans=1e9+10;
for(int i=x;i<=y;i++)
m[a[i]]++;
for(int i=x;i<=y;i++)
{
if(res<m[a[i]])
{ans=a[i];res=m[a[i]];}
else if(res==m[a[i]])
{
ans=min(a[i],ans);
}
}
cout<<ans<<'\n';
}
else{
a[x]=y;
}
}
return 0;
}
H.A % B Problem
线性筛+前缀和
#include<iostream>
using namespace std;
const int N = 1e7+10;
#include<vector>
vector<int>p;
bool st[N];
int n, m;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
cin >> n >> m;
for (int i = 2; i <= m; i++)
{
if (!st[i])p.push_back(i);
for (int j = 0; j <= m / i; j++)
{
st[p[j] * i] = true;
if (i % p[j] == 0)break;
}
}
for(int i=2;i<=m;i++)
{
if(!st[i])a[i]++;
a[i]+=a[i-1];
}
while(n--)
{
int l,r;
cin>>l>>r;
if(l>m||r>m||l<=0||r<=0)
{
cout<<"Crossing the line\n";
continue;
}
cout<<a[r]-a[l-1]<<endl;
}
return 0;
}
I.Remove Duplicates
map从后往前去重vis[i]记录后面下标
从前往后遍历看vis[i]是否存在
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int vis[1000001];
int res;
map<int,bool>p;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=1;i--)
{
if(!p[a[i]]){vis[i]=i;p[a[i]]=true;res++;}
}
cout<<res<<endl;
for(int i=1;i<=n;i++)
{
if(vis[i])cout<<a[i]<<' ';
}
}
J.File Name
简单模拟即可
主要是删除而不是替换
看一下1000好的，直接find+erase模拟上手
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
string a;
cin>>a;
int pose=a.find("xxx");
if(pose<0||pose>=n)
{
cout<<"0\n";
return 0;
}
long long res=0;
// cout<<pose<<endl;
while(pose>=0&&pose<a.size())
{
pose=a.find("xxx");
if(pose<0||pose>=a.size())break;
res++;
a.erase(pose+2,1);
}
cout<<res<<endl;
return 0;
}
总结：挺有意思的题目，虽然做的时候卡
挺有意思的题目，见到了一些新奇的东西，英文题面还是有点不适应