柚子快报邀请码778899分享：山东省第六届ACM省赛
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
#include
#include
using namespace std;
struct node{
double a;
double b;
}a[105];
bool cmp(node a,node b){
//if(a.a!=b.a)
return 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=0;i scanf("%lf%lf",&a[i].a,&a[i].b); } sort(a,a+N,cmp); sum1=0; for(i=0;i sum1+=a[i].b; } sum2=0; for(i=1;i sum2+=a[i].b; } if(sum1>sum2){ printf("red\n"); } else if(sum2>sum1){ printf("blue\n"); } else{//避免比较相等 printf("fair\n"); } } return 0; } View Code B.Lowest Unique Price s.set+map #include #include #include #include using namespace std; int main(){ int T; int N; char str[2]; int x; int i; set map scanf("%d",&T); while(T--){ myset.clear(); mymap.clear(); scanf("%d",&N); for(i=0;i scanf("%1s",str); if(str[0]=='b'){ scanf("%d",&x); myset.insert(x); ++mymap[x]; if(mymap[x]>1){//多于一次价格x myset.erase(x); } } else if(str[0]=='c'){ scanf("%d",&x); --mymap[x]; if(mymap[x]==0){//撤销一次没有价格x myset.erase(x); } else if(mymap[x]==1){//撤销一次只剩一次价格x myset.insert(x); } } else{ if(!myset.empty()){ printf("%d\n",*myset.begin()); } else{ printf("none\n"); } } } } return 0; } View Code C.Game! s.博弈。当石子个数大于2时，后手赢。 还得看看博弈，做做题。 #include #include using namespace std; int main(){ int T; long long N; scanf("%d",&T); while(T--){ scanf("%lld",&N); if(N>2){ printf("blankcqk\n"); } else{ printf("zbybr\n"); } } return 0; } View Code 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 #include #include #include using namespace std; const int MAXN=100; const long long MAXN2=1000000+10;//数字范围 long long num[MAXN2]; int factors[MAXN][2];//[0]存质因子，[1]存个数 int factCnt;//不同的质因子总个数 int getFactors(int n){ int i,k; factCnt=0; for(i=2,k=sqrt(n);i<=k;++i){ if(n%i==0){ factors[factCnt][0]=i; factors[factCnt][1]=1; n=n/i; while(n%i==0){ ++factors[factCnt][1]; n=n/i; } ++factCnt; k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方 } } if(n>1){ factors[factCnt][0]=n; factors[factCnt][1]=1; ++factCnt; } int temp=1; int j; for(i=0;i factors[i][1]=factors[i][1]%3; if(factors[i][1]!=0){ for(j=0;j temp=temp*factors[i][0]; } } } 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,0,sizeof(num)); for(i=0;i scanf("%d",&t); if(t==1){ ++num[1]; continue; } temp=getFactors(t); ++num[temp]; } ans=0; for(i=2;i if(num[i]!=0){ temp=getFactors(i); tmp=1; flag=true; for(j=0;j for(k=0;k<3-factors[j][1];++k){ tmp=tmp*factors[j][0]; if(tmp>=MAXN2){ flag=false; break; } } if(flag==false){ break; } } if(tmp>=MAXN2){ continue; } if(num[tmp]!=0){ ans=ans+num[i]*num[tmp]; } } } ans=ans/2; if(num[1]!=0){//1的时候特殊处理 ans=ans+num[1]*(num[1]-1)/2; } printf("%lld\n",ans); } return 0; } View Code 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 #include #include #include using namespace std; const int MAXN=102400; int factors[MAXN][2];//[0]存质因子，[1]存个数 int factCnt;//不同的质因子总个数 #define MAXN2 1000000+10 int num[MAXN2]; void getFactors(int n){ int i,k; factCnt=0; for(i=2,k=sqrt(n);i<=k;++i){ if(n%i==0){ factors[factCnt][0]=i; factors[factCnt][1]=1; n=n/i; while(n%i==0){ ++factors[factCnt][1]; n=n/i; } ++factCnt; k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方 } } if(n>1){ factors[factCnt][0]=n; factors[factCnt][1]=1; ++factCnt; } int temp=1; for(i=0;i factors[i][1]=factors[i][1]%2; if(factors[i][1]!=0){ temp=temp*factors[i][0]; } } ++num[temp]; } int main(){ /* int n; while(~scanf("%d",&n)){ getFactors(n); printf("不同的质因子总个数：%d\n",factCnt); int i,j; for(i=0;i for(j=0;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,0,sizeof(num)); for(i=0;i scanf("%d",&t); if(t==1){ ++num[1]; continue; } getFactors(t); } ans=0; for(i=0;i if(num[i]!=0){ //cout< ans=ans+(num[i]*(num[i]-1))/2; } } printf("%d\n",ans); } return 0; } View Code c2.这个代码可以参考下。 #include #include #define MAX 1000010 int pri[1010]; int dp[200]; int vis[MAX]; int amount=0; void init() { for(int i=2;i<=1000;i++) {//素数打表 for(int j=i+i;j<=1000;j+=i) { if(!pri[j]) pri[j]=1; } } //平方数打表 for(int i=2;i<=1000;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,0,sizeof(vis)); int ans=0; scanf("%d",&n); for(i=0;i { scanf("%d",&t); for(j=0;j { if(t%dp[j]==0) { while(t%dp[j]==0) t/=dp[j]; } } ans+=vis[t]; //除去平方因数后的值 ，有多少个该平方因数的值就可以组成多少对 vis[t]++; } printf("%d\n",ans); } return 0; } View Code 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"); } } } } View Code K.Last Hit L.Circle of Friends d. s.强连通分量缩点 ps:这里这个缩点方式可能有重边。 我感觉用set可能解决重边的问题。 另外缩点应该用桥来缩比较好。（好像发现是无向图有桥。。。） /* Tarjan算法 复杂度O(N+M) */ #include #include #include #include using namespace std; const int MAXN=100000+10;//点数 const int MAXM=100000+10;//边数 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!=-1;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,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(num,0,sizeof(num)); Index=scc=top=0; for(int i=0;i if(!DFN[i]) Tarjan(i); } void init(){ tot=0; memset(head,-1,sizeof(head)); } int N,M; struct Node{ int u; int steps; }; vector int ans; void bfs(){ queue Node tmp; tmp.u=Belong[0]; tmp.steps=0; myQueue.push(tmp); Node u,v; int i; while(!myQueue.empty()){ u=myQueue.front(); myQueue.pop(); if(u.u==Belong[N-1]){ ans=u.steps; break; } for(i=0;i v.u=g[u.u][i]; v.steps=u.steps+1; 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=0;i scanf("%d%d",&u,&v); addedge(u,v); } solve(N); for(i=1;i<=scc;++i){ g[i].clear(); } for(i=0;i for(j=head[i];j!=-1;j=edge[j].next){ a=Belong[i]; b=Belong[edge[j].to]; if(a!=b){ g[a].push_back(b); } } } ans=-1; bfs(); printf("%d\n",ans); } return 0; } View Code 柚子快报邀请码778899分享：山东省第六届ACM省赛 推荐链接
发表评论