noip真题选做

刷题

P9118 [春季测试 2023] 幂次

1. $k=1$ 特判掉。

2. 注意到 $k\ge 3$ 的时候只需要枚举到 $n^{\frac{1}{3}}$，这是完全承担的起的。

然后你就有 $45$ 分了

单独考虑平方，答案先加上 $\sqrt n$ ，如果一个数在 $k\ge 3$ 做法里有贡献的数是完全平方数就减去他的贡献，注意 $1$ 的判断。

然后搞定了xd

这道题精度很坑，注意点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int ans;
map<int,bool> _is;
int __;
signed main(){
    cin>>n>>k;
    if(k==1){
        cout<<n;
        return 0;
    }
    else if(k>=2){
        ans=1;
        for(int i=2;i*i*i<=n;i++){
            for(int j=i*i,op=2;;){
                if(j>n/i) break;
                j*=i,op++;
                if(j>n) break;
                if(op<k)continue;
                if(_is[j])continue; 
                _is[j]=1;
                ans++;
                if((int)sqrtl(j)*(int)sqrtl(j)==j) __--;
            }
        }
        if(k>=3) cout<<ans;
        else cout<<(int)(sqrtl(n))+ans+__-1;
    }
}

P9869 [NOIP2023] 三值逻辑

记一个初始值和一个真实值，然后并查集一下。

#include<bits/stdc++.h>
using namespace std;
// #define int long long
int c,t,n,m;
int fa[200005],fir[200005],val[200005];
int find(int x){
    return (fa[x]==x?x:fa[x]=find(fa[x]));
} 
int siz[200005];
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    fa[x]=y;
}
signed main(){
    cin>>c>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n*2;i++) fir[i]=i,fa[i]=i,siz[i]=(i<=n),val[i]=INT_MAX;
        while(m--){
            char opt;
            cin>>opt;
            if(opt=='+'){
                int a,b;
                cin>>a>>b;
                if(val[b]!=INT_MAX)
                {
                    fir[a]=a;
                    val[a]=val[b];
                }
                else{
                    fir[a]=fir[b];
                    val[a]=INT_MAX;                    
                }
            }
            else if(opt=='-'){
                int a,b;
                cin>>a>>b;
                if(val[b]!=INT_MAX)
                {
                    fir[a]=a;
                    val[a]=-val[b];
                }
                else{
                    fir[a]=-fir[b];
                    val[a]=INT_MAX;                    
                }
            }
            else if(opt=='T'){
                int x;cin>>x;
                fir[x]=x;
                val[x]=1;
            }
            else if(opt=='F'){
                int x;cin>>x;
                fir[x]=x;
                val[x]=-1;
            }
            else{
                int x;cin>>x;
                fir[x]=x;
                val[x]=0;
            }
        }
        for(int i=n+1;i<=2*n;i++)
        {
            if(val[i-n]!=INT_MAX)
                val[i]=-val[i-n];            
        }
        for(int i=1;i<=n;i++)
        {
            if(fir[i]<0)
                merge(i,-fir[i]+n),merge(i+n,-fir[i]);
            else
                merge(i,fir[i]),merge(i+n,n+fir[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(find(i)==find(n+i))
                val[find(i)]=0;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(val[find(i)]==0) ans++;
        }
        cout<<ans<<"\n";
        for(int i=1;i<=n*2+3;i++) fa[i]=i;
    }
}