2019 2 17 总结

T1

题意:给出n，求1到n内有几个数与n的最大公约数不为1（n<=10000000）
直接分解质因数容斥即可

#include<bits/stdc++.h>
using namespace std;
const long long N=10000000;
inline long long read()
{
    long long num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
bool check[N+9];
long long p[N+9],lenp;
long long n;
long long ans,cnt;
long long cs[N+9],lencs;
void _dfs(long long now,long long k,long long tot,long long ed,long long fs)
{
    if(tot==ed)
    {
        cnt+=(n/k)*fs;
        return;
    }
    if(now==lencs) return;
    _dfs(now+1,k*cs[now+1],tot+1,ed,fs);
    _dfs(now+1,k,tot,ed,fs);    
}
void checkans()
{
    if(lencs)
    {
        cnt=0;
        for(long long k=1;k<=lencs;k++)
        {
            _dfs(0,1,0,k,(k%2==1?1:-1));
        }
    }
}
int main ()
{
    //freopen("million.in","r",stdin);
    //freopen("million.out","w",stdout);
    for(long long i=2;i<=N;i++)
    {
        if(!check[i])
        {
            p[++lenp]=i;
        }
        for(long long j=1;j<=lenp&&p[j]*i<=N;j++)
        {
            check[p[j]*i]=1;
            if(i%p[j]==0) break;    
        }
    }
    n=read();
    for(int i=1;i<=lenp;i++)
    {
        if(n%p[i]==0) cs[++lencs]=p[i]; 
    }
    checkans();
    printf("%d",cnt);
    return 0;   
}

T2

题意：给定一个长度为n的序列，有m个操作如下（n,m<=50000）：

1.在选取一个区间【a，b】，并给出一个值k，区间上如果编号i 满足（i- a) % k = 0 就加上c。(k<=10)
2.询问序列中某个数的当前值。

分块（分块一时爽，一直分块一直爽）
操作一即对一个区间内对于k的余数为定值的一些数加上定值，由于k比较少，在查询时可以直接枚举关于每个k被加了几次
但是个一个数修改显然很慢，故将其分为两部分，一个是块内，一部分为块外
一个区间块外的点最多为sqrt（n）个，最多有sqrt(n)块，复杂度nsqrt(n)
查询时将块内贡献加上单点贡献加上基础值即可

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[50009][11][11];
int fb[238][11][11],block,blong[50009]; 
int val[50009];
int ans;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
int main ()
{
    //freopen("tnt.in","r",stdin);
    //freopen("tnt.out","w",stdout);
    n=read();
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        val[i]=read();  
    }
    for(int i=1;i<=n;i++)
    {
        blong[i]=blong[i-1];
        if(i%block==1) blong[i]++;  
    }
    m=read();
    for(int i=1,opt,a,l,r,k,ys,c;i<=m;i++)
    {
        opt=read();
        if(opt==1)
        {
            l=read(),r=read(),k=read(),c=read();
            ys=l%k;
            while(l%block!=1&&l<=r)
            {
                f[l][k][ys]+=c; 
                l++;
            }
            while(r%block&&l<=r)
            {
                f[r][k][ys]+=c;
                r--;
            }
            for(int j=blong[l];j<=blong[r]&&l<=r;j++)
            {
                fb[j][k][ys]+=c;    
            }
        }
        else
        {
            a=read();
            ans=val[a];
            for(int k=1;k<=10;k++)
            {
                ans+=f[a][k][a%k];
                ans+=fb[blong[a]][k][a%k];
            }
            printf("%d\n",ans);
        }
    }
    return 0;   
}

T3

题意：有n个点和m条边。选出其中的某些边构成一个新的图（不一定联通），要求新图中每个连通块中至多有一个环。求新图的边权最大和。
贪心，做最大生成树，但保证每个联通快只能有一个环，再开一个数组维护即可
证明：若取最大边不是最优，则需要去一条最大边，但去掉一条最大边最多只能再加一边，故总答案减小，不是最优的

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0,fs=1;
    char ch;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
    return num*fs;
}
int f[309];
bool g[309];
int n,m;
long long ans;
struct gzw
{
    int st,ed,val;
}way[1000009];
inline bool rnk(gzw a,gzw b)
{
    return a.val>b.val; 
}
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);   
}
int main ()
{
    //freopen("build.in","r",stdin);
    //freopen("build.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        way[i].st=read(),way[i].ed=read(),way[i].val=read();
        way[i].st++;
        way[i].ed++;
    }
    sort(way+1,way+m+1,rnk);
    for(int i=1;i<=n;i++)
    {
        f[i]=i; 
    }
    for(int i=1;i<=m;i++)
    {
        int u=way[i].st,v=way[i].ed;
        if(find(u)==find(v)&&(!g[find(u)]))
        {
            g[find(u)]=1;
            ans+=way[i].val;
        }
        else if(find(u)!=find(v)&&!(g[find(u)]&g[find(v)]))
        {
            int ls=g[find(u)];
            f[find(u)]=find(v);
            g[find(v)]=g[find(v)]|ls;
            ans+=way[i].val;                
        }
        /*for(int i=1;i<=n;i++)
        {
            cout<<find(i)<<" ";
        }
        cout<<endl;
        for(int i=1;i<=n;i++)
        {
            cout<<g[find(i)]<<" ";
        }
        cout<<endl;*/ 
    }
    printf("%lld",ans);
    return 0;   
}