山东省第六届ACM省赛

时间：2022-06-22 08:05:58
ID.Title Hint
A.Nias and Tug-of-War sort排序
B.Lowest Unique Price set+map
C.Game! 博弈
D.Stars  
E.BIGZHUGOD and His Friends I 赛瓦定理
F.BIGZHUGOD and His Friends II 赛瓦定理 
G.Cube Number 质因数分解
H.Square Number 质因数分解
I.Routing Table  
J.Single Round Math 大数
K.Last Hit  
L.Circle of Friends 缩点

A.Nias and Tug-of-War

s.sort排序

#include<iostream>

#include<stdio.h>

#include<algorithm>

using namespace std;

struct node{

    double a;

    double b;

}a[];

bool cmp(node a,node b){

    //if(a.a!=b.a)

    return a.a<b.a;//a升

    //return a.b>b.b;//b降

}

int main(){

    int T;

    int N;

    int i;

    double sum1,sum2;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        for(i=;i<N;++i){

            scanf("%lf%lf",&a[i].a,&a[i].b);

        }

        sort(a,a+N,cmp);

        sum1=;

        for(i=;i<N;i+=){

            sum1+=a[i].b;

        }

        sum2=;

        for(i=;i<N;i+=){

            sum2+=a[i].b;

        }

        if(sum1>sum2){

            printf("red\n");

        }

        else if(sum2>sum1){

            printf("blue\n");

        }

        else{//避免比较相等

            printf("fair\n");

        }

    }

    return ;

}

B.Lowest Unique Price

s.set+map

#include<iostream>

#include<stdio.h>

#include<set>

#include<map>

using namespace std;

int main(){

    int T;

    int N;

    char str[];

    int x;

    int i;

    set<int> myset;

    map<int,int> mymap;

    scanf("%d",&T);

    while(T--){

        myset.clear();

        mymap.clear();

        scanf("%d",&N);

        for(i=;i<N;++i){

            scanf("%1s",str);

            if(str[]=='b'){

                scanf("%d",&x);

                myset.insert(x);

                ++mymap[x];

                if(mymap[x]>){//多于一次价格x

                    myset.erase(x);

                }

            }

            else if(str[]=='c'){

                scanf("%d",&x);

                --mymap[x];

                if(mymap[x]==){//撤销一次没有价格x

                    myset.erase(x);

                }

                else if(mymap[x]==){//撤销一次只剩一次价格x

                    myset.insert(x);

                }

            }

            else{

                if(!myset.empty()){

                    printf("%d\n",*myset.begin());

                }

                else{

                    printf("none\n");

                }

            }

        }

    }

    return ;

}

C.Game!

s.博弈。当石子个数大于2时，后手赢。

还得看看博弈，做做题。

#include<iostream>

#include<stdio.h>

using namespace std;

int main(){

    int T;

    long long N;

    scanf("%d",&T);

    while(T--){

        scanf("%lld",&N);

        if(N>){

            printf("blankcqk\n");

        }

        else{

            printf("zbybr\n");

        }

    }

    return ;

}

D.Stars

E.BIGZHUGOD and His Friends I

F.BIGZHUGOD and His Friends II

G.Cube Number

d.Given an array of distinct integers (a1, a2, ..., an), you need to find the number of pairs (ai, aj) that satisfy (ai * aj) is a cube number.

s.和下个平方数类似，不错凑立方数的时候，不是从某个数中选2个数了，而是根据这个数的质因数的个数，把每个质因数凑成3个，这样可能直接用这个数乘上相应的数就行了。

ps：long long，还有数组越界的判断搞了好久。。

/*

质因数分解

*/

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

using namespace std;

const int MAXN=;

const long long MAXN2=+;//数字范围

long long num[MAXN2];

int factors[MAXN][];//[0]存质因子，[1]存个数

int factCnt;//不同的质因子总个数

int getFactors(int n){

    int i,k;

    factCnt=;

    for(i=,k=sqrt(n);i<=k;++i){

        if(n%i==){

            factors[factCnt][]=i;

            factors[factCnt][]=;

            n=n/i;

            while(n%i==){

                ++factors[factCnt][];

                n=n/i;

            }

            ++factCnt;

            k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方

        }

    }

    if(n>){

        factors[factCnt][]=n;

        factors[factCnt][]=;

        ++factCnt;

    }

    int temp=;

    int j;

    for(i=;i<factCnt;++i){

        factors[i][]=factors[i][]%;

        if(factors[i][]!=){

            for(j=;j<factors[i][];++j){

                temp=temp*factors[i][];

            }

        }

    }

    return temp;

}

int main(){

    int T;

    int N;

    int t;

    int i,j,k;

    long long ans;

    long long tmp;

    int temp;

    bool flag;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        memset(num,,sizeof(num));

        for(i=;i<N;++i){

            scanf("%d",&t);

            if(t==){

                ++num[];

                continue;

            }

            temp=getFactors(t);

            ++num[temp];

        }

        ans=;

        for(i=;i<MAXN2;++i){

            if(num[i]!=){

                temp=getFactors(i);

                tmp=;

                flag=true;

                for(j=;j<factCnt;++j){

                    for(k=;k<-factors[j][];++k){

                        tmp=tmp*factors[j][];

                        if(tmp>=MAXN2){

                            flag=false;

                            break;

                        }

                    }

                    if(flag==false){

                        break;

                    }

                }

                if(tmp>=MAXN2){

                    continue;

                }

                if(num[tmp]!=){

                    ans=ans+num[i]*num[tmp];

                }

            }

        }

        ans=ans/;

        if(num[]!=){//1的时候特殊处理

            ans=ans+num[]*(num[]-)/;

        }

        printf("%lld\n",ans);

    }

    return ;

}

H.Square Number

d.Given an array of distinct integers (a1, a2, ..., an), you need to find the number of pairs (ai, aj) that satisfy (ai * aj) is a square number.

s.质因数分解。如果某个质因子的个数为偶数，直接去掉；为奇数时保留一个。这样就缩小了规模。

最后遍历一遍，如果某个数存在，那就从中选出2个就可构成一个平方数，这个数形成的平方数的总个数就是C(n,2)。

/*

质因数分解

*/

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

using namespace std;

const int MAXN=;

int factors[MAXN][];//[0]存质因子，[1]存个数

int factCnt;//不同的质因子总个数

#define MAXN2 1000000+10

int num[MAXN2];

void getFactors(int n){

    int i,k;

    factCnt=;

    for(i=,k=sqrt(n);i<=k;++i){

        if(n%i==){

            factors[factCnt][]=i;

            factors[factCnt][]=;

            n=n/i;

            while(n%i==){

                ++factors[factCnt][];

                n=n/i;

            }

            ++factCnt;

            k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方

        }

    }

    if(n>){

        factors[factCnt][]=n;

        factors[factCnt][]=;

        ++factCnt;

    }

    int temp=;

    for(i=;i<factCnt;++i){

        factors[i][]=factors[i][]%;

        if(factors[i][]!=){

            temp=temp*factors[i][];

        }

    }

    ++num[temp];

}

int main(){

    /*

    int n;

    while(~scanf("%d",&n)){

        getFactors(n);

        printf("不同的质因子总个数：%d\n",factCnt);

        int i,j;

        for(i=0;i<factCnt;++i){

            for(j=0;j<factors[i][1];++j){

                printf("%d ",factors[i][0]);

            }

        }

        printf("\n");

    }

    */

    int T;

    int N;

    int t;

    int i;

    int ans;

    int j;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        memset(num,,sizeof(num));

        for(i=;i<N;++i){

            scanf("%d",&t);

            if(t==){

                ++num[];

                continue;

            }

            getFactors(t);

        }

        ans=;

        for(i=;i<MAXN2;++i){

            if(num[i]!=){

                //cout<<i<<" "<<num[i]<<endl;

                ans=ans+(num[i]*(num[i]-))/;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

c2.这个代码可以参考下。

#include <stdio.h>

#include <string.h>

#define MAX 1000010

int pri[];

int dp[];

int vis[MAX];

int amount=;

void init()

{

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

    {//素数打表

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

        {

            if(!pri[j])

                pri[j]=;

        }

    }

    //平方数打表

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

        if(!pri[i])

            dp[amount++]=i*i;

}

int main()

{

    int T,n;

    int t;

    int i,j;

    init();

    scanf("%d",&T);

    while(T--)

    {

        memset(vis,,sizeof(vis));

        int ans=;

        scanf("%d",&n);

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

        {

            scanf("%d",&t);

            for(j=;j<amount;j++)

            {

                if(t%dp[j]==)

                {

                    while(t%dp[j]==)

                        t/=dp[j];

                }

            }

            ans+=vis[t];

            //除去平方因数后的值 ，有多少个该平方因数的值就可以组成多少对

            vis[t]++;

        }

        printf("%d\n",ans);

    }

    return ;

}

I.Routing Table

J.Single Round Math

s.唯一比较坑的是N要等于M，然而并没从题意看出来。。

c.java大数，注意类名要为Main

import java.math.BigInteger;

import java.util.Scanner;

public class Main {//类名要用Main

    public static void main(String[] args){

        int T;

        BigInteger N,M;

        BigInteger MOD=new BigInteger("11");

        BigInteger ZERO=new BigInteger("0");

        Scanner sc=new Scanner(System.in);

        T=sc.nextInt();

        while((T--)>0){

            N=sc.nextBigInteger();

            M=sc.nextBigInteger();

            if(N.compareTo(M)==0&&N.mod(MOD).compareTo(ZERO)==0){//

                System.out.println("YES");

            }

            else{//

                System.out.println("NO");

            }

        }

    }

}

K.Last Hit

L.Circle of Friends

d.

s.强连通分量缩点

ps:这里这个缩点方式可能有重边。

我感觉用set可能解决重边的问题。

另外缩点应该用桥来缩比较好。（好像发现是无向图有桥。。。）

/*

Tarjan算法

复杂度O(N+M)

*/

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN=+;//点数

const int MAXM=+;//边数

struct Edge{

    int to,next;

}edge[MAXM];

int head[MAXN],tot;

int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc

int Index,top;

int scc;//强连通分量的个数

bool Instack[MAXN];

int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc

//num数组不一定需要，结合实际情况

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void Tarjan(int u){

    int v;

    Low[u]=DFN[u]=++Index;

    Stack[top++]=u;

    Instack[u]=true;

    for(int i=head[u];i!=-;i=edge[i].next){

        v=edge[i].to;

        if(!DFN[v]){

            Tarjan(v);

            if(Low[u]>Low[v])Low[u]=Low[v];

        }

        else if(Instack[v]&&Low[u]>DFN[v])

            Low[u]=DFN[v];

    }

    if(Low[u]==DFN[u]){

        scc++;

        do{

            v=Stack[--top];

            Instack[v]=false;

            Belong[v]=scc;

            num[scc]++;

        }

        while(v!=u);

    }

}

void solve(int N){

    memset(DFN,,sizeof(DFN));

    memset(Instack,false,sizeof(Instack));

    memset(num,,sizeof(num));

    Index=scc=top=;

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

        if(!DFN[i])

            Tarjan(i);

}

void init(){

    tot=;

    memset(head,-,sizeof(head));

}

int N,M;

struct Node{

    int u;

    int steps;

};

vector<int> g[MAXN];

int ans;

void bfs(){

    queue<Node> myQueue;

    Node tmp;

    tmp.u=Belong[];

    tmp.steps=;

    myQueue.push(tmp);

    Node u,v;

    int i;

    while(!myQueue.empty()){

        u=myQueue.front();

        myQueue.pop();

        if(u.u==Belong[N-]){

            ans=u.steps;

            break;

        }

        for(i=;i<g[u.u].size();++i){

            v.u=g[u.u][i];

            v.steps=u.steps+;

            myQueue.push(v);

        }

    }

}

int main(){

    int T;

    //int N,M;

    int i,j;

    int u,v;

    int a,b;

    scanf("%d",&T);

    while(T--){

        init();

        scanf("%d%d",&N,&M);

        for(i=;i<M;++i){

            scanf("%d%d",&u,&v);

            addedge(u,v);

        }

        solve(N);

        for(i=;i<=scc;++i){

            g[i].clear();

        }

        for(i=;i<N;++i){

            for(j=head[i];j!=-;j=edge[j].next){

                a=Belong[i];

                b=Belong[edge[j].to];

                if(a!=b){

                    g[a].push_back(b);

                }

            }

        }

        ans=-;

        bfs();

        printf("%d\n",ans);

    }

    return ;

}

相关文章