头像

lyank




离线:9小时前


活动打卡代码 AcWing 1215. 小朋友排队

lyank
10小时前
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

const int N=1000010;
int h[N],tr[N];
int n;
int sum[N];

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int v)
{
    for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;
}

int query(int x)
{
    int res = 0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>h[i];

    for(int i=0;i<n;i++)
    {
        sum[i]=query(N-1)-query(h[i]);
        add(h[i],1);
    }

    memset(tr,0,sizeof tr);
    for(int i=n-1;i>=0;i--)
    {
        sum[i]+=query(h[i]-1);
        add(h[i],1);
    }

    LL res = 0;

    for(int i=0;i<n;i++)
    {
        res+=(1ll+sum[i])*sum[i]/2;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1207. 大臣的旅费

lyank
12小时前
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=100010;
int dist[N];
int n;



struct ed
{
    int id,w;
};
vector<ed>h[N];

void find(int u,int father,int distance)
{
    dist[u]=distance;
    for(auto node:h[u])
    {
        if(node.id!=father)find(node.id,u,node.w+distance);
    }
}



int main()
{
    cin>>n;
    memset(dist,-1,sizeof dist);

    for(int i=0;i<n;i++)
    {
        int p,q,d;
        cin>>p>>q>>d;
        h[p].push_back({q,d});
        h[q].push_back({p,d});
    }

    find(1,-1,0);
    int u =1;
    for(int i=1;i<=n;i++)
    if(dist[i]>dist[u])u=i;

    find(u,-1,0);

    for(int i=1;i<=n;i++)
    if(dist[i]>dist[u])u=i;
    int s = dist[u];

    printf("%lld",s*10+s*(s+1ll)/2);

    return 0;
}


活动打卡代码 AcWing 1233. 全球变暖

lyank
19小时前
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010;

int n;
char g[N][N];
bool st[N][N];
PII q[N * N];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void bfs(int sx, int sy, int &total, int &bound) {
    int hh = 0, tt = 0;
    q[0] = { sx,sy };
    st[sx][sy] = true;

    while (hh <= tt) {
        PII t = q[hh++];
        total++;
        bool is_bound = false;
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= n)continue;
            if (st[x][y])continue;
            if (g[x][y] == '.') {
                is_bound = true;
                continue;
            }
            q[++tt] = { x,y };
            st[x][y] = true;
        }
        if (is_bound)
            bound++;
    }

}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", g[i]);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!st[i][j] && g[i][j] == '#') {
                int total = 0, bound = 0;
                bfs(i, j, total, bound);
                if (total == bound)cnt++;
            }
        }
    }
    printf("%d\n", cnt);

    return 0;

}


活动打卡代码 AcWing 1096. 地牢大师

lyank
19小时前
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=110;
int L,R,C;
char g[N][N][N];
int dist[N][N][N];
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};

struct Point
{
    int x,y,z;
};
Point q[N*N*N];


int bfs(Point start,Point end)
{
    int hh=0,tt=0;
    memset(dist,-1,sizeof dist);
    dist[start.x][start.y][start.z]=0;
    q[0]=start;
    while(hh<=tt)
    {
        auto t = q[hh++];
        for(int i=0;i<6;i++)
        {
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            int c=t.z+dz[i];
            if(a<0||a>=L||b<0||b>=R||c<0||c>=C)continue;
            if(g[a][b][c]=='#')continue;
            if(dist[a][b][c]!=-1)continue;

            dist[a][b][c]=dist[t.x][t.y][t.z]+1;
            if(a==end.x&&b==end.y&&c==end.z)return dist[a][b][c];
            q[++tt]={a,b,c};
        }
    }
    return dist[end.x][end.y][end.z];
}



int main()
{
    while(scanf("%d%d%d",&L,&R,&C),L||R||C)
    {

        Point start,end;
        for(int i=0;i<L;i++)
            for(int j=0;j<R;j++)
            {
                scanf("%s",g[i][j]);
                for(int k=0;k<C;k++)
                {
                    if(g[i][j][k]=='S')start={i,j,k};
                    if(g[i][j][k]=='E')end={i,j,k};
                }
            }
        int res = bfs(start,end);
        if(res==-1)puts("Trapped!");
        else printf("Escaped in %d minute(s).\n",res);
    }

    return 0;
}



lyank
1天前
#include <iostream>

using namespace std;
const int N = 100000;

long long q[N];

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <=n; i++) 
        cin >> q[i];
    int max_ = -1e18;
    int deepth = 1;
    int res = 1;
    for(int i = 1; i <= n; i *= 2){
        long long s = 0;
        for(int j = i;  j <=  i*2 - 1 && j <= n; j ++) {
            s += q[j];
        }
        if(s > max_) {
            max_ = s;
            res = deepth;
        }
        deepth++;
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

lyank
1天前
#include<iostream>
#include<cstring>
using namespace std;

const int N=25;
char g[N][N];
bool st[N][N];
int m,n;

int dfs(int x,int y)
{
    int cnt = 1;
    st[x][y]=true;
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
    for(int i=0;i<4;i++)
    {
        int a = x+dx[i],b = y+dy[i];
        if(a<0||a>=n||b<0||b>=m)continue;
        if(g[a][b]=='#')continue;
        if(st[a][b]==true)continue;
        cnt+=dfs(a,b);
    }
    return cnt;
}

int main()
{

    while(cin>>m>>n,m||n)
    {
        memset(st,false,sizeof st);
        int x,y;
        for(int i=0;i<n;i++)scanf("%s",g[i]);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            if(g[i][j]=='@')
            x=i,y=j;
        }
        int ans = dfs(x,y);
        cout<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1211. 蚂蚁感冒

lyank
2天前
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n; 
int main()
{
    scanf("%d", &n);
    int pivot, left = 0, right = 0;
    scanf("%d", &pivot);

    for (int i = 1; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if (abs(x) < abs(pivot) && x > 0) right++;
        if (abs(x) > abs(pivot) && x < 0) left++;
    }
    if ((pivot < 0 && right == 0) || pivot > 0 && left == 0) puts("1");
    else printf("%d\n", left + right + 1);

    return 0;
}


活动打卡代码 AcWing 1216. 饮料换购

lyank
2天前
#include<iostream>
using namespace std;

int res;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        if(i%3==0)n++;
    }
    cout<<n;
    return 0;
}


活动打卡代码 AcWing 900. 整数划分

lyank
2天前
#include<iostream>
using namespace std;

const int N=1010,mod=1e9+7;
int f[N];
int n;

int main()
{
    cin>>n;
    f[0] = 1;

    for(int i = 1 ; i <= n ; i++ )
        for(int j = i ; j <= n ; j++ )
            f[j] = (f[j] + f[j-i])%mod;

    cout << f[n] << endl;
    return 0;
}


活动打卡代码 AcWing 899. 编辑距离

lyank
3天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1010, M = 12;

char a[N][M];
int f[N][N];
int n, m;

int edit_instance(char a[], char b[]){
    int la = strlen(a + 1), lb = strlen(b + 1);

    for(int i = 0; i <= la; i ++) f[i][0] = i;
    for(int j = 0; j <= lb; j ++) f[0][j] = j;

    for(int i = 1; i <= la; i ++){
        for(int j = 1; j <= lb; j ++){
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    }

    return f[la][lb];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%s", a[i] + 1);

    while(m --){
        int limit;
        char s[M];
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for(int i = 1; i <= n; i ++){
            if(edit_instance(a[i], s) <= limit) res ++;
        }
        cout << res << endl;
    }

    return 0;
}