头像

不会算法的小菜鸡




离线:16小时前


最近来访(33)
用户头像
清风乍起
用户头像
EastTree
用户头像
acw_林少
用户头像
Uranus.
用户头像
._7265
用户头像
kk同学
用户头像
slight
用户头像
最傻的猪
用户头像
Luo_gu_ykc
用户头像
yxc
用户头像
zuihe
用户头像
Cantexplain
用户头像
江无聊
用户头像
Bigwave
用户头像
嘉然今天学web
用户头像
我是老人
用户头像
Soviet_Forever
用户头像
@大菠萝
用户头像
zxzxzx
用户头像
softwsre-zombie

活动打卡代码 AcWing 4268. 性感素数

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int n;

int check(int num)
{
    if(num <= 1) return false;
    if(num == 2) return true;
    if(num == 1) return false;
    for(int i = 2; i <= (int)sqrt(num); i ++)
    {
        if(num % i == 0) return false;
    }
    return true;
}

int main()
{
    cin >> n;

    if(check(n) && (check(n-6) || check(n+6) ) )
    {
        cout << "Yes" << endl;
        if(check(n-6)) cout << n-6;
        else cout << n + 6;
    }
    else 
    {
        cout << "No" << endl;
        for(int i = n + 1; i <= 1e8; i ++)
        {
            if(check(i) && (check(i-6) || check(i+6) ))
            {
                cout << i;
                break;
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 4427. 树中节点和

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

using namespace std;

const int N = 100010;

int h[N],e[N],ne[N],idx;
int n;
int p[N],w[N],s[N];

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

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

    memset(h,-1,sizeof h);
    for(int i = 2; i <= n; i ++)
    {
        int x;
        cin >> x;
        p[i] = x;
        add(x,i);
    }

    for(int i = 1; i <= n; i ++) cin >> s[i];
    w[1] = s[1];

    for(int i = 2;i <= n; i ++)
    {
        if(s[i] == -1)
        {
            s[i] = 0x3f3f3f3f;
            for(int j = h[i];j!=-1; j = ne[j])
            {
                 int ver = e[j];
                s[i] = min(s[i],s[ver]);
            }

            if(h[i] == -1) s[i] = s[p[i]];
        }
    }

    for(int i = 2; i <= n; i ++)
    {
        w[i] = s[i] - s[p[i]];
        if(s[i] - s[p[p[i]]] < 0)
        {
            cout << "-1";
            return 0;
        }

    }

    long long  cnt = 0;
    for(int i = 1; i <= n; i ++) cnt +=w[i];
    cout << cnt;
}


活动打卡代码 AcWing 4426. 整除子串

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

using namespace std;

const int N = 300010;

char s[N];
int a[N];

int main()
{
    cin >> s;
    int n = strlen(s);
    long long  res = 0;

    for(int i = 0; i < n; i ++)
    {
        a[i] = s[i] - '0';
        if(a[i] % 4 == 0) res++;
    }

    for(int i = 1; i < n; i ++)
    {
        if((a[i] + a[i-1] * 10) % 4 == 0) res += i;
    }

    cout << res;
}



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

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1] + 1);
            else
            {
                f[i][j] = max(f[i-1][j],f[i][j-1]);
            }
        }
    }

    cout << f[n][m];
}



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;

int a[N];
int f[N];
int n;
int cnt;

int find(int x)
{
    int l = 1, r = cnt;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
     cin >> n;
     for(int i = 0; i < n; i ++) cin >> a[i];
     f[++cnt] = a[0];
     for(int i = 0 ; i < n ; i++)
     {
         if(a[i] > f[cnt]) f[++cnt] = a[i];
         else
         {
             int tmp = find(a[i]);
             f[tmp] = a[i];
         }
     }
     cout << cnt;
}



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;

int a[N];
int f[N];
int n;
int cnt;

int find(int x)
{
    int l = 1, r = cnt;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
     cin >> n;
     for(int i = 0; i < n; i ++) cin >> a[i];
     f[++cnt] = a[0];
     for(int i = 0 ; i < n ; i++)
     {
         if(a[i] > f[cnt]) f[++cnt] = a[i];
         else
         {
             int tmp = find(a[i]);
             f[tmp] = a[i];
         }
     }
     cout << cnt;
}


活动打卡代码 AcWing 4424. 等式

#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
using namespace std;

const int N = 1010;

int n;
double a;

int main()
{
    cin >> n;

    while(n--)
    {
        cin >> a;
        if(a == 0) cout << "Y 0.0000000000 0.0000000000" << endl;
        else if(a < 4) cout << "N" <<endl;
        else 
        {
            printf("Y %.10f %.10f\n",a - (a + sqrt(a * a - 4 * a))/2 ,((a + sqrt(a * a - 4 * a))/2));
        }
    }

}



用队列来存取每个0的下标,按顺序遍历每个点
如果当前点到队头的距离 大于 当前点到队头下一个元素的距离,
则说明当前点和当前点以后的点到队头的距离都会 大于 当前点和当前点以后的点到队头下一个元素的点,所以将队头出队

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

using namespace std;

const int N = 200010;

int a[N];
int n;

int main()
{
    cin >> n;
    int cnt = 0;
     int q[N],hh = 0,tt = -1;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        if(!a[i]) q[++tt] = i;
    }

    for(int i = 0; i < n; i ++)
    {
        while(abs(i-q[hh]) > abs(i-q[hh+1]) && tt) hh++; //判断当前点到队头的距离 是否大于 当前点到队头下一个元素的距离

        cout << abs(i-q[hh])<< " ";
    }
}


活动打卡代码 AcWing 4420. 连通分量

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

using namespace std;

const int N = 1010;

char g[N][N];
int n,m;
int p[N*N],s[N*N];
int dx[4] = {0,-1,0,1},dy[4] = {1,0,-1,0};

int get(int x,int y)
{
    return (x-1) * m + y;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n *m; i ++) 
    {
        p[i] = i;
        s[i] = 1;
    }

    for(int i = 1; i <= n ;i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> g[i][j];
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(g[i][j] == '.')
            {
                for(int k = 0; k < 4; k ++)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.')
                    {
                        int a = find(get(i,j)), b = find(get(x,y));
                        if(a!=b)
                        {
                            s[b] += s[a];                        
                            p[a] = b;
                        }
                    }
                }
            }
        }
    }
    int q[5] = {1,1,2,3,4};
    cout << q << endl;
    cout << unique(q,q+5)<<endl;
    cout << unique(q,q+5) - q ;

}


活动打卡代码 AcWing 4441. 谎牛计数

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n,m;
struct e{
    char x;
    int y;
}a[N];

int main()
{
    cin >> n; 
    for(int i = 0; i < n; i ++) cin >> a[i].x >> a[i].y;
    int res = 0x3f3f3f3f;
    for(int i = 0; i < n;i ++)
    {
        int c = 0;
        for(int j = 0; j < n; j ++)
        {
            if(a[j].x == 'L') 
            {
                if(a[j].y < a[i].y) c++;
            }
            else 
            {
                if(a[i].y < a[j].y) c++;
            }
        }
        res = min(res,c);
    }
    cout << res;
}