这次题目比较简单，所以大家分都特别高...
第一题 对刚（拿到题笑了半天）其实就是个出题人皮了一下的约瑟夫问题
100分：
#include<iostream>
#include<cstdio>
#define tcl(a,b,c) for(a=b;a<=c;a++)
using namespace std;
int main()
{
int m,n,i;
int j,k=1,p=0,a[100001];
scanf("%d%d",&n,&m);
j=n;
tcl(i,1,n) a[i]=i+1;
a[n]=1;
while(p<n)
{
while(k<m)
{
j=a[j];
k++;
}
p++;
a[j]=a[a[j]];
k=1;
}
printf("%d",a[j]);
return 0;
}
第二题 角谷问题 模拟而已
100分：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
do
{
if(n%2==0)
{
int t;
t=n/2;
printf("%d/2=%d
",n,t);
n/=2;
}
else
{
int tt;
tt=3*n+1;
printf("%d*3+1=%d
",n,tt);
n=n*3+1;
}
}while(n!=1);
return 0;
}
第三题 整数合并
这道题用到并查集，但是只过了8个点，还有两个点T了，把质数筛选一次全套在里面果然复杂度太高了。
80分：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define tcl(a,b,c) for(a=b;a<=c;a++)
int f[100001];
int prime(int a)
{
if(a==1)
return 0;
for(int k=2;k<=sqrt(a);k++)
{
if(a%k==0) return 0;
}
return 1;
}
int gcd(int x,int y)
{
int r;
r=x%y;
while (r!=0)
{
x=y; y=r;
r=x%y;
}
return y;
}
int get(int x)
{
if(f[x]==x)
return x;
else
{
f[x]=get(f[x]);
return f[x];
}
}
void join(int a,int b)
{
int t1,t2;
t1=get(a);
t2=get(b);
if(t1!=t2)
f[t2]=t1;
return;
}
bool find(int a,int b)
{
int t1,t2;
t1=get(a);
t2=get(b);
if(t1==t2) return true;
else return false;
}
int main()
{
int n,m,p,i,j;
scanf("%d%d%d",&n,&m,&p);
tcl(i,n,m)
{
f[i]=i;
}
tcl(i,n,m)
{
tcl(j,n,m)
{
if(gcd(i,j)>=p&&(prime(gcd(i,j)))&&(!find(i,j)))
join(i,j);
}
}
int sum=0;
tcl(i,n,m)
{
if(f[i]==i) sum++;
}
printf("%d",sum);
return 0;
}
第四题 金字塔 区间dp 考试的时候没想出来