A.小红的同余
signed main()
{
IOS
//.........................//
int m;
cin>>m;
for (int i=m;i;i+=m){
int tmp=i+1;
if(tmp%2==0){
cout<<tmp/2;
return 0;
}
}
}B.小红的三倍数
思路：如果每一位上的数字加起来是3的倍数就是三的倍数，否则不是。
signed main()
{
IOS
//.........................//
int n;
cin>>n;
vi a(n);
int sum=0;
for (int i=0;i<n;i++){
string s;
cin>>s;
for (int i=0;i<s.size();i++){
int tmp=s[i]-'0';
sum+=tmp;
}
}
if(sum%3==0){
cout<<"YES";
}
else {
cout<<"NO";
}
}C.小红充电
思路：分情况讨论，如果本来可以直接超级充点，就直接超级充电到满。不然的话讨论先用到刚好可以超级充电再超级充电，或者直接普通充电，看哪个更快。
signed main()
{
IOS
//.........................//
int x,y,t,a,b,c;
cin>>x>>y>>t>>a>>b>>c;
double tm;
double tm1;
if(x<=t){
double tmp=100-x;
tm=tmp/c;
}
else {
double tmp = 100-x;
tm=tmp/b;
double tmp1=x-t;
tm1+=tmp1/y;
tmp=100-t;
tm1+=1.0*tmp/c;
}
cout<<fixed<<setprecision(7)<<min(tm,tm1)；
}D.小红的 gcd
思路：先把b的因子列出来，再来看字符串a能否整除b的因子，如果能够整除说明这个因子是这两数的公因数。最后只要找到最小的b的因数就可以了。
（字符串的每一位上的数都除余一个数，如果最后这个数为0，说明这个字符串可以整除这个数）
signed main()
{
IOS
//.........................//
string a;
int b;
cin>>a>>b;
vi v;
for (int i=1;i<=sqrt(b);i++){
if(b%i==0){
v.push_back(i);
if(i*i!=b){
v.push_back(b/i);
}
}
}
sort(all(v));
for (int i=v.size()-1;i>=0;i--){
int tmp=0;
for (int j=0;j<(int)a.size();j++){
tmp=(tmp*10+(a[j]-'0'))%v[i];
}
if(tmp==0){
cout<<(v[i])<<endl;
return 0;
}
}
}E.小红走矩阵
思路：二分+DFS。 想要知道必须经过的最小的最大值，使用二分配合dfs即可（n最大值也才500，不会超时）。
const int N = 510;
int f[N][N];
int a[N][N];
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int n,ans=1e9;
int fl=0;
int vis[N][N];
void dfs(int x,int y,int maxn)
{
if(vis[x][y] || vis[n][n] ||a[x][y]>maxn){
return ;
}
vis[x][y]=1;
//maxn=max(maxn,a[x][y]);
for (int i=0;i<=3;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if( nx<1 || nx>n || ny<1 || ny>n ){
continue;
}
if(a[nx][ny]>maxn || vis[nx][ny]==1){
continue;
}
dfs(nx,ny,maxn);
}
}
signed main()
{
IOS
//.........................//
cin>>n;
//vector<vector<int>> a(n+1,vector<int>(n+1));
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int l=1,r=1e9;
while(l<=r){
int mid=(l+r)>>1;
memset(vis,0,sizeof vis);//记得每次搜索之前，先清空标记数组。
dfs(1,1,mid);
if(vis[n][n]){//只要看能不能达到(n,n)即可
ans=min(ans,mid);
r=mid-1;
}
else {
l=mid+1;
}
}
cout<<ans;
}
F.小红的数组
思路：这题需要得到最大子区间（区间处理）。我们可以选择使用线段树来进行处理。
AcWing 245. 你能回答这些问题吗 - AcWing
这是一个类似的问题，相较本题，这题简化了最大子区间，不需要求绝对值。
以下是简化版的代码：
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
const int INF =1e18;
const int N = 5e6+10;
int a[N];
struct node{
int l,r;
int tmax,lmax,rmax,sum;//分别是最大子区间，最大前缀区间，和最大后缀区间。
}t[4*N];
void push_up(node &x,node &y,node &z)//对父节点进行更新。
{
x.sum=y.sum+z.sum;
x.lmax=max(y.lmax,y.sum+z.lmax);
x.rmax=max(z.rmax,z.sum+y.rmax);
x.tmax=max({y.rmax+z.lmax,y.tmax,z.tmax});
}
void push_up(int i)//重载函数
{
push_up(t[i],t[i*2],t[i*2+1]);
}
void build(int i,int l,int r){
if(l==r){
t[i]={l,r,a[l],a[l],a[l],a[l]};
return ;
}
t[i]={l,r};
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
}
void change(int i,int x,int y)
{
if(t[i].l==x && t[i].r==x){
t[i]={x,x,y,y,y,y};
return ;
}
int mid=(t[i].l+t[i].r)>>1;
if(x<=mid){
change(i*2,x,y);
}
else {
change(i*2+1,x,y);
}
push_up(i);
}
node ask(int i,int l,int r)//输出方式为节点的形式。
{
if(t[i].l>=l && t[i].r<=r){
return t[i];
}
int mid=(t[i].l+t[i].r)>>1;
if(r<=mid){
return ask(i*2,l,r);
}
else if(l>mid){
return ask(i*2+1,l,r);
}
else {
node res,left,right;
left=ask(i*2,l,r);
right=ask(i*2+1,l,r);
push_up(res,left,right);
return res;
}
}
signed main()
{
IOS
//.........................//
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for (int i=1;i<=m;i++){
int z,x,y;
cin>>z;
if(z==1){
cin>>x>>y;
if(x>y){
swap(x,y);
}
cout<<ask(1,x,y).tmax<<endl;
}
else {
cin>>x>>y;
change(1,x,y);
}
}
}
而本题的绝对值们可以取反来处理。设一个最大值和最小值，最后看最大值的绝对值大还是最小值的绝对值大。
const int N = 5e5+10;
int a[N];
struct node{
int l,r;
int tmax,lmax,rmax,sum;
int tmin,lmin,rmin;
}t[4*N];
void push_up(node &x,node &y,node &z)
{
x.sum=y.sum+z.sum;
x.lmax=max(y.lmax,y.sum+z.lmax);
x.rmax=max(z.rmax,z.sum+y.rmax);
x.tmax=max({y.rmax+z.lmax,y.tmax,z.tmax});
x.lmin=min(y.lmin,y.sum+z.lmin);
x.rmin=min(z.rmin,z.sum+y.rmin);
x.tmin=min({y.rmin+z.lmin,y.tmin,z.tmin});
}
void push_up(int i)
{
push_up(t[i],t[i*2],t[i*2+1]);
}
void build(int i,int l,int r){
if(l==r){
t[i]={l,r,a[l],a[l],a[l],a[l],a[l],a[l],a[l]};
return ;
}
// int mid=(l+r)>>1;
t[i]={l,r};
int mid=(l+r)>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
}
void change(int i,int x,int y)
{
if(t[i].l==x && t[i].r==x){
t[i]={x,x,y,y,y,y,y,y,y};
return ;
}
int mid=(t[i].l+t[i].r)>>1;
if(x<=mid){
change(i*2,x,y);
}
else {
change(i*2+1,x,y);
}
push_up(i);
}
node ask(int i,int l,int r)
{
if(t[i].l>=l && t[i].r<=r){
return t[i];
}
int mid=(t[i].l+t[i].r)>>1;
if(r<=mid){
return ask(i*2,l,r);
}
else if(l>mid){
return ask(i*2+1,l,r);
}
else {
node res,left,right;
left=ask(i*2,l,r);
right=ask(i*2+1,l,r);
push_up(res,left,right);
return res;
}
}
signed main()
{
IOS
//.........................//
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
int m;
cin>>m;
for (int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
cout<<max(abs(ask(1,x,y).tmax),abs(ask(1,x,y).tmin))<<endl;
}
}
