2022—蓝桥杯C++A组复盘

链接

补题传送门

参考的博客

---

题目列表

非常失败的一次比赛……

A - 裁纸刀 √

题意： 一张纸上打印了20 2020行22 2222列共440 440440个二维码，至少需要裁多少次可以全部裁出。如下图，2 22行3 33列共需要裁9 99次。

#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld double

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int maxn = 1e3+10;

int f[maxn][maxn];

int main(){
    int n,m;
    n=22;//=read();
    m=20;//=read();
    FOR(i,1,n)
        FOR(j,1,m)
            f[i][j]=0x3f3f3f3f;
    f[1][1]=0;f[0][0]=0;
    f[0][1]=0;f[1][0]=0;
    FOR(i,1,n){
        FOR(j,1,m){
            FOR(k1,0,i)
                FOR(k2,0,j){
                    f[i][j]=min((k1==0||k1==i?0:1)+(k2==0||k2==j?0:1)+(k1!=0&&k1!=i&&k2!=0&&k2!=j?1:0)
                    +f[k1][k2]+f[i-k1][k2]+f[k1][j-k2]+f[i-k1][j-k2],f[i][j]);
                }
            //cout<<f[i][j]<<" ";
        }
        //cout<<endl;
    }
    cout<<f[n][m]+4;
    return 0;
}

B - 灭鼠先锋 x

题意： 在2 22行4 44列的棋盘中，两人轮流操作，每次可选择在空位上放置1 11个棋子，或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在4 44种初始局面如下所示，O OO表示空，X XX表示已放置。每人均以最优策略放棋子。判断先手胜利（输出V VV）还是后手胜利（输出L LL）。

XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO

#include<bits/stdc++.h>
using namespace std;
///判断是否仅存在一个空格
bool check(string s)
{
    int tot = 0;
    for(auto x : s)if(x == 'O')
        tot++;
    return tot == 1;
}
map<string, bool>SG;
bool dfs(string s)
{
    if(SG.count(s))
        return SG[s];
    if(check(s))
        return SG[s] = false;
    ///模拟放1个棋子
    for(int i = 0; i < s.size(); i++)if(s[i] == 'O')
    {
        string tmp = s;
        tmp[i] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///模拟放2个棋子
    for(int i = 0; i < s.size() - 1; i++)if(s[i] == 'O' && s[i + 1] == 'O' && i != 3)
    {
        string tmp = s;
        tmp[i] = tmp[i + 1] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///运行到此，说明只能转移到必胜态，此时为必败态
    return SG[s] = false;
}

int main()
{
    string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};
    for(int i = 0; i < 4; i++)
    {
        if(dfs(s[i]))cout<<"L";///此时为必胜态，说明后手面临的局面必胜，输出L
        else cout<<"V";
    }
    return 0;
}

C - 求和 x 30%

题意：给定数组 \(a\) ，求 \(\sum_{i=1}^n\sum_{j=i+1}^n\)。

我的：

#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld double

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int maxn = 2e5+100;
//const int maxm = 4e5+100;

int a[maxn],num[maxn]={0};

int main(){
    int n;
    cin>>n;
    FOR(i,1,n){
        a[i]=read();
        num[i]=num[i-1]+a[i];
    }
    ll ans=0;
    FOR(i,1,n){
        ans+=a[i]*num[i-1];
    }
    cout<<ans;
    return 0;
}

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn], sum[maxn];
int main()
{
    int n;
    ll ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) ///预处理前缀和
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; i++) ///求和即可
        ans += a[i] * (sum[n] - sum[i]);
    cout<<ans<<endl;
    return 0;
}

D - 选数异或 x 40%

题意： 给定数组 \(a\) 和整数 \(x\)，\(m\) 次询问，每次询问区间 \([l,r]\) 是否存在两个数字使得异或值等于 \(x\)。

我的暴力：

#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld double

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int maxn = 1e3+10;
//const int maxm = 4e5+100;


int main(){
    int n,m,x;
    n=read();
    m=read();
    x=read();
    //±©Á¦
    if(n<=1000){
        int a[1020];
        FOR(i,1,n)
            a[i]=read();
        int l,r;
        while(m--){
            int f=0;
            l=read();
            r=read();
            FOR(i,l,r){
                FOR(j,i+1,r){
                    if((a[i]^a[j])==x){
                        f=1;
                        break;
                    }
                }
                if(f)
                    break;
            }
            if(f)
                printf("yes\n");
            else 
                printf("no\n");
        }
    } else {

    }

    return 0;
}

题解：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
int tree[maxn << 2];
int Left[maxn], pos[(1 << 20) + 10];
int a[maxn], n, m, x;

//线段树模板
void build(int o, int l, int r)
{
    if(l == r)
    {
        tree[o] = Left[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= n; i++) //预处理Left数组
    {
        scanf("%d", &a[i]);
        Left[i] = pos[a[i] ^ x];
        pos[a[i]] = i;
    }
    build(1, 1, n);//线段树建树
    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if(query(1, 1, n, l, r) >= l)//查询区间最值
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

E - 爬树的甲壳虫 x

题意： 甲壳虫想要爬上高度为 \(n\) 的树，开始位于树根，高度为 0，当它尝试从高度 \(i-1\) 爬到高度为 \(i\) 的位置时有 \(P_i\) 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
ll x[maxn], y[maxn];
ll ksm(ll a, ll b, ll m)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)ans = ans * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}
ll inv(ll x)
{
    return ksm(x, MOD - 2, MOD);
}
ll extgcd(ll a, ll b, ll&x, ll&y)//ax+by = gcd(a, b)的解。返回值为gcd
{
    ll d = a;
    if(b)
    {
       d = extgcd(b, a % b, y, x);
       y -= (a / b) * x;
    }
    else x = 1, y = 0;
    return d;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        ll g = __gcd(x[i], y[i]);
        x[i] = x[i] / g;
        y[i] = y[i] / g;
    }
    ll a = 0, b = 0;
    for(int i = n; i >= 1; i--)
    {
        ll p = x[i] * inv(y[i]) % MOD, p_1 = (y[i] - x[i]) * inv(y[i]) % MOD;
        a = (p + p_1 * a) % MOD;
        b = (1 + p_1 * b) % MOD;
    }
    ///cout<<x[1]<<" "<<y[1]<<" "<<inv(y[1])<<endl;
    ///dp[0] = a * dp[0] + b
    ///(a-1)dp[0]+k * MOD = MOD - b
    ///(a - 1)x + MOD * y = MOD - b
    ///cout<<a<<" "<<b<<endl;
    ll c = a - 1, d = MOD, x, y;
    ll g = extgcd(c, d, x, y);
    ///cout<<x<<" "<<y<<endl;
    ll x1 = x * (MOD - b) / g;
    ll y1 = y * (MOD - b) / g;
    cout<<(x1 % MOD + MOD ) % MOD<<endl;
    return 0;
}

F - 青蛙过河 x 10%

题意： 小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。

小青蛙一共需要去学校上x天课，所以它需要往返2x次。当小青蛙具有一个跳跃能力y时，它能跳不超过y的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完x次课。

我的：

#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld double

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int maxn = 1e5+10;
//const int maxm = 4e5+100;

int n,x;
int h[maxn];


bool check(int q){
    int f[maxn];
    memset(f,0,sizeof(f));
    int num=0;//=h[0];
    f[0]=h[0];
    FOR(i,1,n){
        num+=f[i-1];
        if(i-q-1>=0)
            num-=f[i-q-1];
        //cout<<i<<":"<<num<<endl;
        f[i]=min(num,h[i]);
    }
    // cout<<q<<":";
    // FOR(i,1,n)
    //     cout<<f[i]<<" ";
    // cout<<endl;
    if(f[n]>=x)
        return 1;
    return 0;
}

void solve(){
    int l=1,r=n;
    int mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
        //cout<<l<<"-"<<r<<endl;
    }
    cout<<l<<endl;
}

int main(){
    n=read();
    x=read();
    x*=2;
    FOR(i,1,n-1)
        h[i]=read();
    h[0]=h[n]=0x3f3f3f3f;

    solve();
    
    return 0;
}

题解：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int h[maxn], sum[maxn];
int n, x;
//判断所有长度为mid的区间之和是否大于等于2x
bool check(int mid)
{
    for(int i = 1; i + mid - 1 <= n; i++)
        if(sum[i + mid - 1] - sum[i - 1] < 2 * x)return false;
    return true;
}
int main()
{
    read(n); read(x);
    for(int i = 1; i <= n - 1; i++)//预处理前缀和
        read(h[i]), sum[i] = sum[i - 1] + h[i];
    sum[n] = 1e9 + 7;
    int left = 1, right = n, ans = n;
    while(left <= right)//二分答案
    {
        int mid = (left + right) >> 1;
        if(check(mid))
            ans = mid, right = mid - 1;//求最小合法解
        else
            left = mid + 1;
    }
    cout<<ans<<endl;
    return 0;
}

G - 最长不下降子序列 x 30%

题意： 给定数组a，可以修改连续的K个数字变成一个相同值。请计算修改后的最长不下降子序列长度。

我的：

#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld double

inline int read(){
    int s=0,f=1;char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c<='9'&&c>='0';c=getchar()) s=(s<<3)+(s<<1)+c-'0';
    return f*s;
}

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int maxn = 1e5+100;
//const int maxm = 4e5+100;

int n,q;
int a[maxn];int b[maxn];
int d[maxn];int l[maxn];int len;

void solve(){
    d[1]=a[1];
    l[1]=1;
    int len=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]>=d[len]){  //如果可以接在len后面就接上，如果是最长上升子序列，这里变成> 
            d[++len]=a[i];
            l[i]=len;
        } 
        else  //否则就找一个最该替换的替换掉 
        {
            int j=upper_bound(d+1,d+len+1,a[i])-d;  //找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound 
            d[j]=a[i]; 
            l[i]=j;
        }
    }
    //printf("%d\n",len);  
    // FOR(i,1,n)
    //     cout<<l[i]<<" ";
    // cout<<endl;
}

int l1[maxn],l2[maxn];

int main(){
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    solve();
    FOR(i,1,n)
        l1[i]=l[i];
    FOR(i,1,n)
        b[i]=1e6-a[1+n-i];
    FOR(i,1,n)
        a[i]=b[i];

    solve();
    FOR(i,1,n)
        l2[i]=l[1+n-i];


    FOR(i,1,n)
        b[i]=1e6-a[1+n-i];
    FOR(i,1,n)
        a[i]=b[i];

    int ans=0;
    l1[0]=l2[n+1]=0;
    a[0]=0;
    a[n+1]=0x3f3f3f3f;
    FOR(i,1,n){
        if(i+q>n+1)
            break;
        if(a[i+q]>=a[i-1])
            ans=max(ans,l1[i-1]+l2[i+q]+q);
    }
    cout<<ans;
    return 0;
}

/*
6 1
1 1 5 4 6 1
*/

题解：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int a[maxn], b[maxn];
int dp[maxn];
///dp[i]表示以i结尾的最长上升子序列

///权值线段树，维护dp数组
int tree[maxn << 2];
void build(int o, int l, int r)
{
    tree[o] = 0;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
}
void update(int o, int l, int r, int x, int val)
{
    if(l == r)
    {
        tree[o] = max(tree[o], val);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    tree[o] = max(tree[o << 1], tree[o << 1 | 1]);
}
int query(int o, int l, int r, int L, int R)
{
    if(L <= l && r <= R)
        return tree[o];
    int mid = (l + r) >> 1;
    int ans = 0;
    if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));
    if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    int n, k, tot = 0;
    read(n); read(k);
    for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];
    if(n == k)
    {
        cout<<n<<endl;
        return 0;
    }
    ///离散化
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - (b + 1);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
    
    build(1, 1, tot);
    int ans = 0;
    for(int i = 1; i <= n; i++)///从前往后遍历a，放入权值线段树中
    {
        ///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]
        dp[i] = query(1, 1, tot, 1, a[i]) + 1;
        update(1, 1, tot, a[i], dp[i]);
    }
    ///重新清空
    build(1, 1, tot);
    for(int i = n; i > k; i--)///从后往前遍历a，放入权值线段树中
    {
        ///a[i-k+1] ... a[i]相等 均等于a[i-k]
        ///最后一段要注意：查询的是[a[i-k],tot]中的最大值
        ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);
        int tmp = query(1, 1, tot, a[i], tot) + 1; ///以a[i]开始的最长上升子序列长度
        ans = max(ans, tmp + k);
        ///插入的是a[i]
        update(1, 1, tot, a[i], tmp);
    }
    cout<<ans<<endl;
    return 0;
}

H - 扫描游戏

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int maxn = 2e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
struct point
{
    ll x, y, z;
    int id;
}a[maxn];
ll n;
__int128 L;

int Quadrant(point a)
{
    if(a.x >= 0 && a.y > 0)return 1;///y的正半轴放到第一象限
    if(a.x > 0 && a.y <= 0)return 2;///x的正半轴放到第二象限
    if(a.x <= 0 && a.y < 0)return 3;
    return 4;
}
ll cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}
bool cmp(point a, point b)
{
    if(Quadrant(a) == Quadrant(b))
    {
        if(cross(a, b) == 0)
            return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
        else
           return cross(a, b) < 0;
    }
    else
        return Quadrant(a) < Quadrant(b);
}

__int128 mi[maxn << 2];
void push_up(int o)
{
    mi[o] = min(mi[o << 1], mi[o << 1 | 1]);
}
void build(int o, int l, int r)
{
    if(l == r)
    {
        mi[o] = a[l].x * a[l].x + a[l].y * a[l].y;
        return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    push_up(o);
}

void update(int o, int l, int r, int x, __int128 val)
{
    if(l == r)
    {
        mi[o] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)update(o << 1, l, mid, x, val);
    else update(o << 1 | 1, mid + 1, r, x, val);
    push_up(o);
}

///找右边第一个小于等于z^2的数字
ll idx;
bool query(int o, int l, int r, int L, int R, __int128 z)
{
    if(L > R)return false;
    if(l == r)
    {
        idx = l;
        return mi[o] <= z;
    }
    int mid = (l + r) >> 1;
    if(L <= mid)
    {
        if((mi[o << 1] <= z) && query(o << 1, l, mid, L, R, z))
            return true;
    }
    if(R > mid)
    {
        if((mi[o << 1 | 1] <= z) && query(o << 1 | 1, mid + 1, r, L, R, z))
            return true;
    }
    return false;
}
int ans[maxn];

int main()
{
    read(n);read(L);
    for(int i = 1; i <= n; i++)
    {
        read(a[i].x);read(a[i].y);read(a[i].z);
        a[i].id = i;
        ans[i] = -1;
    }
    sort(a + 1, a + 1 + n, cmp);
    build(1, 1, n);
    int cnt = 0;
    int lastcnt = 0;
    int last = 0;  ///上一个位置
    while(true)
    {
        bool ok = query(1, 1, n, last + 1, n, L * L);
        if(ok)L = L + a[idx].z;
        else
        {
            ok = query(1, 1, n, 1, last - 1, L * L);
            if(ok)L = L + a[idx].z;
            else break;
        }
        update(1, 1, n, idx, 1e32);
        if(last)
        {
            if(Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0)
                ans[a[idx].id] = lastcnt, ++cnt;
            else
                ans[a[idx].id] = ++cnt, lastcnt = cnt;
        }
        else
            ans[a[idx].id] = ++cnt, lastcnt = cnt;
        last = idx;
    }
    for(int i = 1; i <= n; i++)
    {
        cout<<ans[i];
        if(i != n)cout<<" ";
    }
    return 0;
}

I - 数的拆分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

bool not_prime[4010];
int prime[4010], tot;
void init(int n)
{
    for(int i = 2; i <= n; i++)if(!not_prime[i])
    {
        prime[++tot] = i;
        for(int j = i + i; j <= n; j += i)
            not_prime[j] = 1;
    }
}
inline bool check(ll x)
{
    ///检查平方数
    ll y = pow(x, 0.5);
    if(y * y == x || (y + 1) * (y + 1) == x)
        return true;
    ///检查立方数
    y = pow(x, 1.0 / 3);
    if(y * y * y == x || (y + 1) * (y + 1) * (y + 1) == x || (y + 2) * (y + 2) * (y + 2) == x)
        return true;
    return false;
}
int main()
{
    init(4000);
    int T;
    read(T);
    while(T--)
    {
        ll x;
        read(x);
        if(check(x))
        {
            puts("yes");
            continue;
        }
        bool flag = true;
        for(int i = 1; i <= tot; i++)if(x % prime[i] == 0){
            int now = 0;
            while(x % prime[i] == 0)
            {
                now++;
                x /= prime[i] ;
            }
            ///cout<<prime[i]<<" "<<now<<endl;
            if(now == 1)
            {
                flag = false;
                break;
            }
        }
        if(flag & check(x))
        {
            puts("yes");
            continue;
        }
        else
        {
            puts("no");
        }
    }
    return 0;
}

J - 推导部分和 x 10%

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
const int maxn = 1e5 + 10;
const ll INF = -1e13;
int n, m, q;
struct edge
{
    int v; ll w;
    edge(){}
    edge(int v, ll w):v(v), w(w){}
};
vector<edge>Map[maxn];
ll sum[maxn];
bool vis[maxn];
void dfs(int u, ll d)
{
    vis[u] = 1;
    sum[u] = d;
    ///cout<<u<<" "<<d<<endl;
    for(auto x : Map[u])
    {
        int v = x.v; ll w = x.w;
        if(vis[v])continue;
        dfs(v, d + w);
    }
}
queue<pair<int,ll> >Q;
void bfs(int u, ll d)
{
    vis[u] = 1;
    sum[u] = d;
    Q.push(make_pair(u, d));
    while(!Q.empty())
    {
        auto now = Q.front();
        Q.pop();
        int u = now.first; ll d = now.second;
        for(auto x : Map[u])
        {
            int v = x.v; ll w = x.w;
            if(vis[v])continue;
            vis[v] = 1;
            sum[v] = d + w;
            Q.push(make_pair(v, d + w));
        }
    }
}
int f[maxn];
int Find(int x)
{
    return x == f[x] ? x : f[x] = Find(f[x]);
}
int main()
{
    read(n);read(m);read(q);
    for(int i = 0; i <= n; i++)f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int l, r; ll s;
        read(l);read(r);read(s);
        ///cout<<l<<" "<<r<<" "<<s<<endl;
        ///sum[r] - sum[l - 1] = s
        Map[l - 1].push_back(edge(r, s));
        Map[r].push_back(edge(l - 1, -s));
        f[Find(l - 1)] = Find(r);
    }
    for(int i = 0; i <= n; i++)if(!vis[i])
        bfs(i, 0);
    while(q--)
    {
        int l, r;
        read(l), read(r);
        --l;
        if(Find(l) != Find(r))puts("UNKNOWN");
        else printf("%lld\n", sum[r] - sum[l]);
    }
    return 0;
}