[Codeforces #174] Tutorial

Link:

A:

求原根的个数，有一条性质是原根个数为$\phi(\phi(n))$，多了一个不会证的性质

如果要确定哪些是原根的话还是要枚举，不过对于每个数不用枚举$p$次了

由于$\delta_p(x) | \phi(x)$，只要对欧拉函数值的约数枚举即可

不过此题好像直接$O(p^2)$枚举就行了……

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

typedef double db;

int p,res;

int main()

{

    scanf("%d",&p);

    for(int i=;i<p;i++)

    {

        bool f=;int t=;

        for(int j=;j<=p-;j++)

        {

            t=(t*i)%p;

            if(t==) f=;

        }

        if(t*i%p!=) f=;

        res+=f;

    }

    printf("%d",res);

    return ;

}

Problem A

B:

简单分类

#include <bits/stdc++.h>

using namespace std;

int n,A,I;char s[];

int main()

{

    scanf("%d%s",&n,s+);

    for(int i=;i<=n;i++)

        if(s[i]=='A') A++;

        else if(s[i]=='I') I++;

    if(!I) printf("%d",A);

    else if(I==) printf("");

    else printf("");

    return ;

}

Problem B

C:

明明写起来很简单的一道题目被我弄复杂了

考虑维护序列中原来的值和增量

由于只要求当前最后一个数的增量，因此可以每次仅在增加的最后一个数打上标记

这样在删除数时将当前末尾的增量向前推就能满足要求

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

int n,det[MAXN],dat[MAXN],lst;double sum;

int main()

{

    scanf("%d",&n);

    dat[]=;lst=;

    while(n--)

    {

        int op,x,y;

        scanf("%d",&op);

        if(op==) scanf("%d%d",&x,&y),sum+=x*y,det[x]+=y;

        else if(op==) scanf("%d",&x),sum+=x,dat[++lst]=x;

        else sum-=dat[lst]+det[lst],det[lst-]+=det[lst],det[lst--]=;

        printf("%.6lf\n",sum/lst);

    }

    return ;

}

Problem C

结果我这个zz用树状数组维护了这个东西，还将一个增量写成了赋值WA了好几次……

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

int n;ll bit[MAXN<<],dat[MAXN<<],lst,sum;

void Update(int pos,int x)

{while(pos<=n) bit[pos]+=x,pos+=pos&(-pos);}

ll Query(int pos)

{ll ret=;while(pos) ret+=bit[pos],pos-=pos&(-pos);return ret;}

int main()

{

    scanf("%d",&n);

    lst=;sum=;

    for(int i=;i<=n;i++)

    {

        int op,x,y;

        scanf("%d",&op);

        if(op==)

        {

            scanf("%d%d",&x,&y);

            Update(,y);Update(x+,-y);

            dat[]+=y;dat[x+]-=y;

            sum+=x*y;

        }

        else if(op==)

        {

            scanf("%d",&x);

            Update(lst+,x);Update(lst+,-x);

            dat[++lst]+=x;dat[lst+]=-x;

            sum+=x;

        }

        else

        {

            sum-=Query(lst);

            Update(lst+,-dat[lst+]);

            Update(lst,dat[lst+]);

            dat[lst]+=dat[lst+];dat[lst+]=;lst--;

        }

        printf("%.6lf\n",1.0*sum/lst);

    }

    return ;

}

Problem C

D:

可以发现真正的状态数只有$2*n$个，对于每一位只有加/减两种状态

发现$y$的值就是走过的总距离，这样用$dp[n][2]$记忆化搜索在当前状态走到边界有多远

每个状态在入栈时打上标记，如果再次走到形成环就是循环了

这样对于每个$i$就是对应于$dp[i+1][0]$时的解

注意将边界$dp[1][0/1]$设为-1

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

int n,dat[MAXN],vis[MAXN][];ll dp[MAXN][];

ll dfs(int x,int d)

{

    if(x<=||x>n) return ;

    if(vis[x][d]==) return -;

    if(vis[x][d]==) return dp[x][d];

    vis[x][d]=;

    ll dist=d?dfs(x+dat[x],):dfs(x-dat[x],);

    vis[x][d]=;

    if(dist==-) return dp[x][d]=-;

    else return dp[x][d]=dist+dat[x];

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&dat[i]);

    vis[][]=vis[][]=;

    for(int i=;i<=n;i++)

    {

        if(!vis[i][]) dfs(i,);

        printf("%I64d\n",dp[i][]==-?-:i+dp[i][]-);

    }

    return ;

}

Problem D

E:

由于每个点只有一个后继，因此最终图只有环和链

将环的情况排除后就只剩链了

对于一条链，一个可行解为$a_1*w_1+a_2*w_2...+a_n*w_n(a_1>a_2>...>a_n)$

但由于后面的限制条件不能直接背包，考虑将式子变换后消除限制：

设$d_i=a_i-a_{i-1},suf_i=w_i+w_{i+1}...+w_n$，

这样式子变为$d_1*suf_1+d_2*suf_2...+d_n*suf_n$

发现就是一个完全背包，且可以将各个链合并在一起考虑

但注意，这个背包要求$d_1,d_2...d_{n-1}>0$，否则无法保证条件成立

也就是原式每个物品的个数要达到${n-1,n-2...2,1,0}$的下限！

这样就先都取一个，并将其从$t$中减去再跑背包即可

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=1e5+,MOD=1e9+;

int n,q,t,x,y,a[MAXN],nxt[MAXN],d[MAXN],dp[MAXN],cnt;

int main()

{

    scanf("%d%d%d",&n,&q,&t);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=q;i++)

        scanf("%d%d",&x,&y),nxt[x]=y,d[y]++;

    for(int i=;i<=n&&t>=;i++)

    {

        if(d[i]) continue;

        int sum=;//t<0一定要及时退出！

        for(int j=i;j&&t>=;j=nxt[j])

        {

            cnt++;

            sum+=a[j];a[j]=sum;

            if(nxt[j]) t-=a[j];

        }

    }

    if(cnt<n||t<) return puts(""),;

    dp[]=;

    for(int i=;i<=n;i++)

        for(int j=a[i];j<=t;j++)

            (dp[j]+=dp[j-a[i]])%=MOD;

    printf("%d",dp[t]);

    return ;

}

Problem E

同时还有一个注意点：$t<0$时要及时退出否则会爆$int$

巴特西

[Codeforces #174] Tutorial

Link:

A:

B:

C:

D:

E:

最新文章

热门文章