头像

淮工周杰伦




离线:13小时前


最近来访(19)
用户头像
acwing_5735
用户头像
1_41
用户头像
Youn
用户头像
种花家的市长
用户头像
трава
用户头像
不过六级不改名_36
用户头像
EllaSun2009
用户头像
菜狗是我我是菜狗
用户头像
zz哲
用户头像
是一个一个一个CE自动机啊啊啊啊啊啊啊啊啊啊啊啊啊
用户头像
当我回忆爱玛农
用户头像
Latrix
用户头像
肖某
用户头像
xgk2117luojie
用户头像
小太阳
用户头像
lsjlsjlsj
用户头像
天德池贵族


//暴力和双指针的区别,暴力操作j指针需要回退,而双指针不用

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],b[N];
int main()
{

  int n,m,x;
 cin>>n>>m>>x;
 for(int i=0;i<n;i++)
    cin>>a[i];
 for(int i=0;i<m;i++)
    cin>>b[i];
 for(int i=0,j=m-1;i<n;i++)
 {
     while (j>=0&&a[i]+b[j]>x)j--;//因为两个数组都是递增,则此时的j到m-1都不用再进行遍历
        if(j>=0&&a[i]+b[j]==x)    
         cout<<i<<" "<<j<<endl;
 }

}



#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int a)
{
    if(a==1)return 0;

    for(int i=2;i<=sqrt(a);i++)
     if(a%i==0)return 0;
    return 1;
}
int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
    {
        if(isprime(i)&&isprime(x/i)&&i<=x/i&&x%i==0)
         cout<<i<<" "<<x/i<<endl;
    }
}



#include<iostream>
using namespace std;
typedef long long LL;
 LL a,b,p;
LL binarypow(LL a,LL b,LL p)
{
    if(b==0)return 1;
    if(b%2==1)
    {
      return   a*binarypow(a,b-1,p)%p;
    }
    else
    {
        LL mul=binarypow(a,b/2,p);
        return mul*mul%p; 
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>p;
        cout<<binarypow(a,b,p);
        cout<<endl;
    }
}



#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    int res=0;//要求的最大值
    for(int i=0,j=0;i<n;i++)
    {
        s[a[i]]++;//意思就是s[N]是一个计数器,只要输入a中有重复的数字,那么对应的这个s[i]的值就会++;
        while(s[a[i]]>1)
        {
          s[a[j]]--;//将此时的这个数组元素清零
          j++;//将j指针后移
          }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
}


基础模板
for(int i=0,j=0;i<n;i++)
   while(i<=i&&check[j,i])j++
就是一个先动,另一个满足一定条件后再动   


活动打卡代码 AcWing 788. 逆序对的数量

#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N],tmp[N];
typedef long long LL;
LL mergesort(int q[],int l,int r)
{
    if(l>=r)return 0;
    int mid=(l+r)/2;
   // mergesort(q,l,mid),mergesort(q,mid+1,r);
    LL res=mergesort(q,l,mid)+mergesort(q,mid+1,r);//递归,是不是递归边界就是左端的两个数,然后这两个数就符合第三种方式,这两个数排完之后不断回溯
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
     if(q[i]<=q[j])tmp[k++]=q[i++];
     else
     {
         tmp[k++]=q[j++];
         res+=mid-i+1;
     }
    }
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    for(int i=l,k=0;i<=r;i++,k++)//q数组下表从l到r,赋值,不要写成1
       q[i]=tmp[k];
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
      cin>>q[i];
    cout<<mergesort(q,0,n-1)<<endl;

}


活动打卡代码 AcWing 798. 差分矩阵

for循环的括号不能省,只有一条语句时可以省略

include[HTML_REMOVED]

using namespace std;
const int N = 1e3 + 10;
int a[N][N],b[N][N];
void insert(int x1, int y1, int x2, int y2,int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}//这里只需要找到相应矩形的顶点作为两个下标就行,不需要思考太多
int main()
{
int n, m,q;
scanf(“%d%d%d”, &n, &m, &q);
for (int i = 1; i <= n; i)
{
for (int j = 1; j <= m; j
)
scanf(“%d”, &a[i][j]);
}

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
        insert(i, j, i, j, a[i][j]);//因为此时所有元素都为0,a[i][j]已经经过初始化,b[i][j]为0,就是a[i][j]在一个小范围内全部加上了0+a[i][j],这一步实现只能是b[i][j]加上a[i][j]

}
while (q–)
{
int x1, y1, x2, y2, c;
scanf(“%d%d%d%d%d”, &x1, &y1, &x2, &y2, &c);
insert(x1, y1, x2, y2, c);
}

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    { 
        b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];//整个一块b[i][j]矩阵相加就是a[i][j];
         printf("%d ", b[i][j]);
    }
  printf("\n");


}

}



活动打卡代码 AcWing 796. 子矩阵的和

include[HTML_REMOVED]

using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int n,m,q;
int main()
{
scanf(“%d%d%d”, &n, &m, &q);
for(int i=1;i<=n;i)
{ for(int j=1;j<=m;j
)
scanf(“%d”, &a[i][j]);}

for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
     s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];

while(q--)
{
    int x1,y1,x2,y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d\n", s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
}
return 0;

}//这里的下标都是从1开始,a[0][0],s[0][0]都是0




//很像高中所学的数列

include[HTML_REMOVED]

using namespace std;
const int N=1e6+10;
int n,m;
int a[N],s[N];
int main()
{
scanf(“%d%d”, &n, &m);
for(int i=1;i<=n;i)scanf(“%d”, &a[i]);
for(int i=1;i<=n;i
)s[i]=s[i-1]+a[i];
while(m–)
{
int l,r;
scanf(“%d%d”, &l, &r);
printf(“%d\n”, s[r]-s[l-1]);//类比数列,这样求出第l到第r项的和
}
}



活动打卡代码 AcWing 154. 滑动窗口

最后得出的数据还是有些不明白

include[HTML_REMOVED]

using namespace std;
const int N=1e6+10;
int a[N],q[N];//a是原来的值,q是队列,存放的是下标
int n,i,k;//i为遍历的最后一个下标(当前终点是i),k为长度
int main()
{
scanf(“%d%d”, &n, &k);
for(int i=0;i[HTML_REMOVED]k) hh;//先判断队列头是否已经滑出 当队列不空且长度大于我们已经设定的k时,i-q[hh]+1意思是长度,例如3-1+1=3
while(hh<=tt&&a[q[tt]]>=a[i])//表示队尾大于我所要插入队尾的元素,则当前队尾的值一定不会以最小值输出,就是冗余元素,可以删除
tt–;
q[
tt]=i;//这里将下标对应相等,但是为什么不可以a[q[++t]]=x,但是感觉用下标更加清晰。
if(i+1>=k) printf(“%d “, a[q[hh]]);
}
cout<[HTML_REMOVED]= k ) printf(“%d “, a[q[hh]]);
}
return 0;

}



活动打卡代码 AcWing 830. 单调栈

include[HTML_REMOVED]

using namespace std;
const int N=1e6+10;
int stk[N],tt;
int main()
{
int n;
cin>>n;
while(n–)
{

    int x;
    cin>>x;
    while(tt&&stk[tt]>=x)tt--;
    if(tt) cout<<stk[tt]<<" ";//如果tt经过上面的操作后还不是空的,那就输出skt[tt]
    else cout<<-1<<" ";//如果栈空,则没有小于该元素的值
    stk[++tt]=x;//结束之后将这个元素放在栈顶
}
return 0;

}