头像

wuog




离线:3天前


最近来访(228)
用户头像
sy123
用户头像
snkz5qing
用户头像
爱吃面条的阿泽
用户头像
钢铁加鲁鲁
用户头像
zdkk
用户头像
heming_qiao
用户头像
fujang
用户头像
thunderclouds
用户头像
染染
用户头像
我是sun
用户头像
冷-离
用户头像
swifties270
用户头像
czk
用户头像
dark_7
用户头像
skydegree
用户头像
WYCTSTF
用户头像
Chosen1.
用户头像
x丶
用户头像
如梦初醒
用户头像
ちょっとジョーンソース

活动打卡代码 AcWing 3493. 最大的和

wuog
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5+10;
int n,k,a[N],b[N],C[N];
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int sum=0;
    for(int i=1;i<=n;i++)
        if(b[i])sum+=a[i];
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        if(!b[i])r+=a[i];
        if(i>=k&&!b[i-k])r-=a[i-k];
        l=max(l,r);
    }
    cout<<sum+l<<endl;
}



wuog
5个月前

算法1

(暴力搜索) $O(n^2)$

直接暴力搜索就好了!!!!!!

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1010,M=1e6+10;
int a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n,m,k,ans;
int t[M];
void dfs(int x,int y,int s,int idx){
    if(idx>=k){
        if(s>1e6+10){
            cout<<s<<endl;
            exit(0);
        }
        //cout<<s<<endl;
        t[s]++;
        return;
    }
    if(idx==0)s+=a[x][y]*pow(10,k-idx);
    for(int i=0;i<4;i++)
    {
        int sx=x+dx[i],sy=y+dy[i];
        int res=s;
        if(sx>=0&&sx<n&&sy>=0&&sy<m&&idx<k){
            idx++;
            res+=a[sx][sy]*pow(10,k-idx);
           // cout<<res<<" "<<idx<<"--->"<<sx<<","<<sy<<endl;
            dfs(sx,sy,res,idx);
            idx--;
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
         cin>>a[i][j];
    }
    if(k==0){cout<<n*m<<endl;return 0;}
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
        dfs(i,j,0,0);
    for(int i=0;i<1e6+10;i++)
        if(t[i]>0)ans++;
    cout<<ans<<"\n";
}


活动打卡代码 AcWing 3502. 不同路径数

wuog
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1010,M=1e6+10;
int a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n,m,k,ans;
int t[M];
void dfs(int x,int y,int s,int idx){
    if(idx>=k){
        if(s>1e6+10){
            cout<<s<<endl;
            exit(0);
        }
        //cout<<s<<endl;
        t[s]++;
        return;
    }
    if(idx==0)s+=a[x][y]*pow(10,k-idx);
    for(int i=0;i<4;i++)
    {
        int sx=x+dx[i],sy=y+dy[i];
        int res=s;
        if(sx>=0&&sx<n&&sy>=0&&sy<m&&idx<k){
            idx++;
            res+=a[sx][sy]*pow(10,k-idx);
           // cout<<res<<" "<<idx<<"--->"<<sx<<","<<sy<<endl;
            dfs(sx,sy,res,idx);
            idx--;
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
         cin>>a[i][j];
    }
    if(k==0){cout<<n*m<<endl;return 0;}
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
        dfs(i,j,0,0);
    for(int i=0;i<1e6+10;i++)
        if(t[i]>0)ans++;
    cout<<ans<<"\n";
}


新鲜事 原文

wuog
6个月前
终于完成了(aaaa
图片 图片


新鲜事 原文

wuog
6个月前
一个测试工程师走进一家酒吧,要了一杯啤酒 一个测试工程师走进一家酒吧,要了一杯咖啡 一个测试工程师走进一家酒吧,要了0.7杯啤酒 一个测试工程师走进一家酒吧,要了-1杯啤酒 一个测试工程师走进一家酒吧,要了2^32杯啤酒 一个测试工程师走进一家酒吧,要了一杯洗脚水 一个测试工程师走进一家酒吧,要了一杯蜥蜴 一个测试工程师走进一家酒吧,要了一份asdfQwer@24dg!&*(@ 一个测试工程师走进一家酒吧,什么也没要 一个测试工程师走进一家酒吧,又走出去又从窗户进来又从后门出去从下水道钻进来 一个测试工程师走进一家酒吧,又走出去又进来又出去又进来又出去,最后在外面把老板打了一顿 一个测试工程师走进一 一个测试工程师走进一家酒吧,要了一杯烫烫烫的锟斤拷 一个测试工程师走进一家酒吧,要了NaN杯Null 1T测试工程师冲进一家酒吧,要了500T啤酒咖啡洗脚水野猫狼牙棒奶茶 1T测试工程师把酒吧拆了 一个测试工程师化装成老板走进一家酒吧,要了500杯啤酒并且不付钱 一万个测试工程师在酒吧门外呼啸而过 一个测试工程师走进一家酒吧,要了一杯啤酒;DROP TABLE 酒吧 测试工程师们满意地离开了酒吧。 然后一名顾客点了一份炒饭,酒吧炸了


活动打卡代码 AcWing 1047. 糖果

wuog
6个月前

背包问题

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e3 + 19;
typedef long long ll;
int  a[N][N], n, k;
int main()
{
    cin >> n >> k;
    memset(a, -0x3f, sizeof a);
    a[0][0] = 0;
    for(int i = 1; i <= n; i ++)
    {
        int w;
        cin >> w;
        for (int j = 0; j < k; j ++ )
        {
            a[i][j] = max (a[i - 1][j] ,a[i - 1][(j + k - w % k) % k]+ w);
        }
    }
   cout << a[n][0] <<  '\n';
   return 0;
}


活动打卡代码 AcWing 1050. 鸣人的影分身

wuog
6个月前

DP 就是一个简单的子状态划分

#include<stdio.h>
#define N 25
int f[N][N];
int n,m,t;
int main()
{
    scanf("%d",&t);
    while(t--){
    scanf("%d %d",&n,&m);
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=f[i][j-1];
            if(i>=j)f[i][j]+=f[i-j][j];
        }
    printf("%d\n",f[n][m]);
    }
    return 0;
}


活动打卡代码 AcWing 1237. 螺旋折线

wuog
6个月前
#include<queue>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n ,m, x, y;
int main()
{
    cin >> x >> y;
    n=max(abs(x),m=abs(y));
    LL res=4*(n-1)*n;
    if(x==-n)
    {
        if(y==-n)
        {
            res+=8*n;
        }
        else
        {
            res+=n+y;
        }
    }
    else if(y==n)
    {
        res+=3*n+x;
    }
    else if(x==n)
    {
        res+=5*n-y;
    }
    else if(y==-n)
    {
        res+=7*n-x;
    }
    cout<<res<<endl;
    return 0;
}


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

wuog
6个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#define ios cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int n, m, k;
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()
{
    ios;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for(int j = 1; j<= m; j ++)
            cin >> 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]);
    for(int i =1; i<= k; i ++)
        {
            int x1, y1, x2, y2, c;
            cin >> 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];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

wuog
6个月前
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    while (m -- )
    {
        int x,y,z;
        cin>>x>>y>>z;
        b[x]+=z,b[y+1]-=z;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        cout<<b[i]<<" ";
    }
    return 0;
}