[SinGuLaRiTy] NOIP模拟赛(TSY)-Day 2

A

题目描述

给出三个整数a,b,c，令m=a^b，求φ(m) mod c和2*∑(i,i<=m)i*[gcd(i,m)=1] mod c。

输入

第一行输入三个正整数a、b、c。

输出

输出两个整数，即φ(m) mod c和2*∑(i,i<=m)i*[gcd(i,m)=1] mod c。

样例数据

样例输入	样例输出
8 1 7	4 4

<样例解释>

欧拉函数定义：小于或等于n的数中，与n互质的数的个数。
φ(8)=4，1,3,5,7满足条件，于是2*(1+3+5+7) mod 7=4。

<数据范围>

对于100%的数据，a,b<=10^12，c<=10^9。

解析

首先，要知道求欧拉函数的公式：

1、结合公式可以得出：φ(a^b)=φ(a)*a^(b-1)；
2、∑(i,i<=m)i*[gcd(i,m)=1] mod c怎么求呢？φ(n)=m，这m个与a互质的数之和sum=∑bi。对于一个bi，有gcd(n,bi)=1 -> gcd(n-bi,bi)=1。sum=∑n-bi。
两式相加：ans*2=∑n-bi+bi=m*n=φ(n)*n。
好吧，此题的代码实现非常简单：快速幂+欧拉函数(都是模板啊~)
有一点要注意，当b=0时，显然有φ(a^0)=φ(1)=1，需要特判然后直接输出"1 2"。其实模数c是否为素数对此题并没有什么影响，TSY本来还想再搞一个中国剩余定理的......

Code

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

#define LL long long

using namespace std;

LL a,b,mod;

LL ksm(LL a,LL cnt)
{
    a%=mod;
    LL ans=1;
    while(cnt)
    {
        if(cnt&1)
            ans=ans*a%mod;
        a=a*a%mod;
        cnt>>=1;
    }
    return ans;
}

LL get_phi(LL n)
{
    LL ans=n;
    int number=(int)sqrt(n+0.5);
    for(int i=2;i<=number;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            do
            {
                n/=i;
            }
            while(n%i==0);
        }
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}

int main()
{
    cin>>a>>b>>mod;
    if(b==0)
    {
        printf("1 2");
        return 0;
    }
    LL ans=get_phi(a)%mod*ksm(a,b-1)%mod;
    cout<<ans<<' '<<ans*ksm(a,b)%mod;
    return 0;
}

B

题目描述

给出一个长度为n的数列。
定义f(i,j)表示下标属于[i,j]的数组成的集合中，最大的元素的下标；如果有多个最大元素，取位置靠前的。
求满足f(l,r)=k(l<=r,k∈[1,n])的有序数对f(l,r)的个数。
由于输入过多，你需要用到输入优化。
由于输出过多，你只需输出这n个整数的异或值。

输入

第一行输入一个整数n。
第二行输入n个整数，即这个数列。

输出

输出一行一个整数，即这n个整数的异或值。

样例数据

样例输入	样例输出
4 2 3 4 1	4

<样例解释>

f(l,r)=1：(1,1)
f(l,r)=2：(1,2),(2,2)
f(l,r)=3：(1,3),(1,4),(2,3),(2,4),(3,4),(4,4)
f(l,r)=4：(4,4)

<数据范围>

对于100%的数据，n<=3*10^6，

解析

ans_i=(i-f_i)*(g_i-i)
其中fi表示在i之前第一个大于或等于ai的数的下标，gi表示在i之后第一个大于或等于ai的数下标。
可以通过单调栈来求这两个数组，下面只说f数组的求法。
从左往右扫描数组，用一个从栈底到栈顶单调不增的栈来维护：访问到ai时，不断弹出栈顶元素，直到栈顶元素小于等于ai为止；此时栈顶元素的位置就是fi；然后再将当前的元素再加入栈顶，此时这个栈仍然满足原来的单调性质。
时间复杂度：O(n)。

Code

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

#define MAXN 3000010

typedef long long LL;

using namespace std;

int num;
int data[MAXN],pre[MAXN],aft[MAXN];
int tool,x[MAXN];

char w;
inline void GET(int &t)
{
    t=0;
    do w=getchar();while(w<'0'||w>'9');
    do{t=t*10+w-'0';w=getchar();}while(w>='0'&&w<='9');
}

int main()
{
    /*
    pre[i]数组：记录的是data[i]之前的最后一个比它大的值的位置
    aft[i]数组：记录的是data[i]之后的第一个比它大的值的位置
    */
    GET(num);
    for(int i=1;i<=num;i++)
    {
        GET(data[i]);
    }
    pre[1]=0;
    x[++tool]=1;

    for(int i=2;i<=num;i++)
    {
        while(tool&&data[i]>data[x[tool]])
        {
            tool-=1;
        }
        if(tool!=0)
        {
            pre[i]=x[tool];
        }
        else
        {
            pre[i]=0;
        }
        x[++tool]=i;
    }

    aft[num]=num+1;
    tool=1;
    x[tool]=num;
    for(int i=num-1;i;i--)
    {
        while(tool&&data[i]>=data[x[tool]])
        {
            tool-=1;
        }
        if(tool!=0)
        {
            aft[i]=x[tool];
        }
        else
        {
            aft[i]=num+1;
        }
        x[++tool]=i;
    }

    LL ans=0;
    /*
    i-f[i]：表示在这之间的数的个数
    g[i]-i：表示在这之间的数的个数
    */
    for(int i=1;i<=num;i++)
        ans^=1LL*(i-pre[i])*(aft[i]-i);
    cout<<ans;
    return 0;
}

C

题目描述

2017夏，一个有n个县城的小城经历长达几天的暴雨，m条城市道路全部被洪水冲断，救援队员紧急出动，修复n-1条道路使得这n个县城两两相通。现在救援队队长想知道修复哪些道路使得任意两个县城之间的最短距离的最大值最小。

输入

第一行输入两个整数n、m，分别表示有n个县城和m条道路。
接下来的m行输入三个整数u、v、l，表示一条从县城u到县城v的双向道路，l表示这条道路的长度。

输出

输出一个整数即任意两个县城之间距离的最大值的最小值。

样例数据

样例输入	样例输出
4 4 1 2 5 2 3 1 2 4 2 3 4 4	7

<数据范围>

对于100%的数据，n<=300，m<=50000，l<=10000。

解析

直接二分是会超时的！(二分复杂度：O(n^3+mn*logX))于是我们需要考虑一个神奇的优化，优化之后的时间复杂度为O(n^3+mn)。

具体的解法，还是看题解吧。

Code

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

#define MAXN 305
#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

int n,m,mat[MAXN][MAXN],rnk[MAXN][MAXN],edge[MAXN*MAXN>>1][2];
int tmp,ans;

bool cmp(int a,int b)
{
    return mat[tmp][a]<mat[tmp][b];
}

int main()
{
    memset(mat,0x3f,sizeof mat);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        mat[i][i]=0;
    int u,v,l;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&l);
        mat[u][v]=mat[v][u]=l;
        edge[i][0]=u;
        edge[i][1]=v;
        ans+=l;
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            rnk[i][j]=j;
        tmp=i;
        sort(rnk[i]+1,rnk[i]+n+1,cmp);
    }
    for(int i=1;i<=m;++i)
    {
        u=edge[i][0];
        v=edge[i][1];
        ans=min(ans,min(mat[u][rnk[u][n]],mat[v][rnk[v][n]])*2);
        for(int tmp=n,i=n-1;i;--i)
        {
            if(mat[v][rnk[u][i]]>mat[v][rnk[u][tmp]])
            {
                ans=min(ans,mat[u][rnk[u][i]]+mat[u][v]+mat[v][rnk[u][tmp]]);
                tmp=i;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Time: 2017-07-28