Acwing game 59 [End]

The difficulty of the topic is relatively simple , Mainly thinking questions .
https://www.acwing.com/activity/content/competition/problem_list/2015/

4491. Array operation 【 thinking 】

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*10;
typedef long long int LL;
int a[N],s[N],temp,n;
int main(void)
{
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],temp=min(temp,s[i]);
    cout<<s[n]-temp;
    return 0;
}

4492. Subtraction operation 【 thinking 】

Prime number words , In one step . The number of times is divided by 2. In other cases, the factors are prime odd numbers .
So violent to find the smallest reduction , At this time, an odd number - An odd number . The result is even. The next step is directly in place .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*10;
typedef long long int LL;
LL n,cnt;
void solve(LL n)
{
    
    while(n)
    {
    
        if(n%2==0)
        {
    
            cnt+=n/2;
            break;
        }
        for(LL i=3;i<=n;i+=2)
        {
    
            if(n%i==0)
            {
    
                cnt++;
                n-=i;
                break;
            }
        }
    }
}
bool check(LL n)
{
    
    if(n==1) return true;
    for(LL i=2;i<=n/i;i++) if(n%i==0) return false;
    return true;
}
int main(void)
{
    
    cin>>n;
    if(check(n)) cout<<1<<endl;
    else solve(n),cout<<cnt<<endl;
    return 0;
}

4493. Annular connected component 【 Find a clean ring 】

cf The original question of a certain time of , At that time, I forgot how to do . Another way of writing .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*5+10;
int p[N],st[N],d[N],n,m;
int find(int x)
{
    
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
vector< pair<int,int> >ve;
int main(void)
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    int cnt=0;
    while(m--)
    {
    
        int a,b; cin>>a>>b;
        d[a]++,d[b]++;
        ve.push_back({
    a,b});
    }
    for(int i=1;i<=n;i++) if(d[i]>2) st[i]=1;// Marked as bad 
    for(int i=0;i<ve.size();i++)
    {
    
        int a=ve[i].first,b=ve[i].second;
        if(find(a)==find(b)&&!st[find(a)]) cnt++;// It's a ring.   And no redundant edges 
        else
        {
    
            if(st[find(a)]) st[find(b)]=1;// Merge good and bad before merging 
            p[find(a)]=find(b);
        }
    }
    cout<<cnt;
    return 0;
}