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

using namespace std;

const int N = 1000010;

typedef long long LL;

int n;
//LL a;
int prime[N];
bool st[N];
int cnt;

void init()
{
    for(int i = 2; i <= N; i ++)
    {
        if(!st[i])  prime[++cnt] = i;

        for(int j = 1; (LL)1 * prime[j] * i <= N; j ++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)  break;
        }
    }
}

int main()
{
    st[1] = 1;
    init();
    cin>>n;
    while(n --)
    {
        LL x;
        scanf("%lld", &x);

        int t = sqrt(x);
        if(!st[t] && (LL)1 * t * t == x)  puts("YES");
        else puts("NO");
    }
    return 0;
}

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

using namespace std;

int a, b, c, d;

int main()
{
    cin>>a>>b>>c>>d;
    cout<<max(abs(a - c), abs(b - d))<<endl;
}

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

using namespace std;

const int N = 100010;

int a[N], b[N];
int n, m;
int sa[N], sb[N];
int res;

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        sa[i] = sa[i - 1] + a[i];
    }
    for(int i = 1; i <= m; i ++)
    {
        scanf("%d", &b[i]);
        sb[i] = sb[i - 1] + b[i];
    }

    for(int i = 1, j = 1; i <= n; i ++)
    {
        while(sb[j] < sa[i])  j ++;
        if(sb[j] == sa[i])  res ++;
    }

    cout<<res<<endl;
}

贪心

很简单的一个贪心思想，纯靠猜hhhh

核心算法

双指针 贪心 前缀和

贪心思想概述

为了尽可能的多分石子，也就是达到题目里的最优解，我们每次遇到可以划分的时候就马上划分，也就是后文的res++

代码

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

using namespace std;

const int N = 100010;

int a[N], b[N];
int n, m;
int sa[N], sb[N];
int res;

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        sa[i] = sa[i - 1] + a[i];
    }
    for(int i = 1; i <= m; i ++)
    {
        scanf("%d", &b[i]);
        sb[i] = sb[i - 1] + b[i];
    }

    for(int i = 1, j = 1; i <= n; i ++)
    {
        while(sb[j] < sa[i])  j ++;
        if(sb[j] == sa[i])  res ++;
    }

    cout<<res<<endl;
}

往年回刷

基本概念：

一个数一定能用x^3 * y^2来表示

大致思路：

在这道题我们进行几种情况的特判
（1）完全平方数
    如果这个数是完全平方数，那么另一个数就可以用1进行表示啦
    本来想用sqrt直接进行判定，但是很邪门，中间几个数据总是会wa，迫不得已只能用二分进行查找
（2）完全立方数
    与上面同理，另一个数也可以用1进行表示
    也是和上面是一个方法，利用二分进行查找
（3）素因子里面有指数为1的
    根据题目设定，指数为一肯定不合法
（4）既不是完全平方数也不是完全立方数

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

using namespace std;

int a, b, c, d;
int res;
bool flag;

int main()
{
    cin>>a>>b>>c>>d;
    for(int i = max(b, d); i <= 100000000; i ++)
    {
        if((i - b) % a == 0 && (i - d) % c == 0)
        {
            res = i;
            flag = true;
            break;
        }
    }
    if(flag)  cout<<res<<endl;
    else cout<<-1<<endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

#define x first 
#define y second

const int N = 1010;

typedef long long LL;
typedef pair<int, int> PII;

char g[N][N];
int dist[N][N];
int n, m, k, x1, x2, y1, y2;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, -1, 0};

int bfs(PII start, PII target)
{
    if (start == target) return 0;

    queue<PII> q;
    q.push(start);

    memset(dist, 0x3f, sizeof dist);
    dist[start.x][start.y] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++ )
            for (int j = 1; j <= k; j ++ )
            {
                int x = t.x + dx[i] * j, y = t.y + dy[i] * j;
                if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#') break;

                if (dist[x][y] < dist[t.x][t.y] + 1) break;

                if (dist[x][y] > dist[t.x][t.y] + 1)
                {
                    dist[x][y] = dist[t.x][t.y] + 1;
                    if (x == target.x && y == target.y)
                        return dist[x][y];
                    q.push({x, y});
                }
            }
    }
    return -1;

}

int main()
{
    cin>>n>>m>>k;
    for(int i = 0; i < n; i++)  scanf("%s", g[i]);
    int sx, sy, tx, ty;
    scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
    printf("%d\n", bfs({sx - 1, sy - 1}, {tx - 1, ty - 1}));

    return 0;
}

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

using namespace std;

int n, m;

bool check()
{
    while(m)
    {
        if(m % n == 0)  m /= n;
        else if(m % n == 1)  m /= n;
        else if(m % n == n - 1)  m = (m + 1) / n;
        else return false;
    }
    return true;
}

int main()
{
    cin>>n>>m;
    if(check()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

using namespace std;

int x;

int main()
{
    cin>>x;
    int res = 0;
    while(x)  res += x & 1, x >>= 1;
    cout<<res<<endl;
    return 0;
}

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

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], w[N], idx;

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

int dfs(int u, int fa, int cnt, bool valid)
{
    if (w[u]) cnt ++ ;
    else cnt = 0;

    if (cnt > m) valid = false;

    int res = 0, sons = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        sons ++ ;
        res += dfs(j, u, cnt, valid);
    }

    if (!sons && valid) res ++ ;
    return res;
}

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

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    printf("%d\n", dfs(1, -1, 0, true));
    return 0;
}