注：fjutoj基本每周都有一次周赛，欢迎大家都来参加！
网址：http://59.77.139.92/index.jsp
A题：来源 POJ 2773
题意：给两个数m和k，问第k 个和m 互素的数是多少（从1到无穷大）。
思路：
二分 + 容斥
先求出m 的素因子p[]，数x 和m 互素就意味着x 不存在p 数组中的任意一个素因子，现在要 求n 下面不存在p[]素因子的数的数量可以转化为，n-存在p[]中任意一个素因子的数的个数（经典题型，用容斥可以求），现在二分（k，INF）可以求出答案。
#include<stdio.h>
#define N 1000010
#define LL long long
const LL INF = 0x7fffffffffffffff;
bool pri[N];
int prim[N], po=;
void Init()
{
for(int i=;i<N;i++)
{
if(!pri[i]) prim[po++]=i;
for(int j=;j<po&&(LL)i*prim[j]<N;j++)
{
pri[i*prim[j]]=;
if(i%prim[j]==) break;
}
}
} int data[], co; void fun(int x)
{
int i=;
co=;
while(i<po && (LL)prim[i]*prim[i]<=x)
{
bool c=;
while(x%prim[i]==)
{
c=;
x/=prim[i];
}
if(c) data[co++]=prim[i];
i++;
}
if(x!=) data[co++]=x;
} void dfs(int limit, int j, LL y, LL now, LL &all)
{
if(limit==)
{
all += y/now;
return ;
}
for(int i=j; i<co; i++)
{
dfs(limit-, i+, y, now*data[i], all);
}
}
LL solve(LL x)
{
LL sum=x, flag=-;
for(int i=; i<=co; i++)
{
LL all=;
dfs(i, , x, , all);
sum+=flag*all;
flag *= -;
}
return sum;
} LL er(LL l, LL r, LL x)
{
while(l<r)
{
LL mid = (l+r)/;
if(solve(mid)>=x) r=mid;
else l=mid+;
}
return l;
} int main()
{
Init();
int x,y;
while(~scanf("%d%d",&x, &y))
{
fun(x);
printf("%lld\n", er(y, INF, y));
}
return ;
}
AC代码
B题：来源 HDU 1730
题意：
思路：
博弈
很容易产生的错误判断：如果两个子相邻，那么这个的胜者是后手，如果不相邻，胜者是先手，那么判断先手胜利的行数，最后如果是奇数则先手胜，偶数则后手胜（我因此WA了两次...）。举个错误样例：，如果按上面思路，两行都是先手胜，那么应该是后手赢，但先手其实可以将第一行的红点移动一格，这样先手就赢了。
事实上，这里应该是nim博弈的模型，首先，我们可以判断出一点，双方的棋子只会不断接近（如果一人后退一步，另一人可以跟进一步，保持局面不变）。接着，既然两者只能接近，那么就可以看作是n 堆，每一堆x个，每个玩家每轮可以拿走一个、两个、...直至拿完。接下来就不解释了。
#include<stdio.h>
int max(int a, int b) { return a>b?a:b; }
int main()
{
int n, m, x, y;
while(~scanf("%d%d",&n, &m))
{
int ans = ;
for(int i=; i<n; i++)
{
scanf("%d%d",&x, &y);
if(x+==y || x==y+);
else ans ^= ( max(x, y) - (x+y-max(x, y)) - );
}
if(ans) printf("I WIN!\n");
else printf("BAD LUCK!\n");
}
return ;
}
AC代码
C题：来源 POJ 3671
题意：
思路：
用两个数组a[]、b[]，a[i]表示i前面2的个数，b[i]表示i后面1的个数（遍历两遍可以求出a、b数组），如果以i 为中心（1、2转折点），要修改的数个数为a[i-1]+b[i+1]，遍历一遍求出最小值即可。
#include<stdio.h>
#define N 30010
int a[N], b[N], c[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
a[]=;
for(int i=; i<=n; i++)
{
scanf("%d", &c[i]);
if(c[i]==) a[i]=a[i-];
else a[i]=a[i-]+;
}
b[n+]=;
for(int i=n; i> ;i--)
{
if(c[i]==) b[i]=b[i+]+;
else b[i]=b[i+];
}
int mint = N;
for(int i=; i<=n; i++)
{
if(a[i-]+b[i+]<mint) mint = a[i-]+b[i+];
}
printf("%d\n", mint);
}
return ;
}
AC代码
D题：来源 POJ 3663
题意：
思路：
排序 + 二分
对数组排序后，遍历一遍，s-a[i]就是分界点，二分出小于等于他的第一个数，比他小的都满足条件。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int a[];
int er(int l, int r, int x)
{
while(l<r)
{
int mid = (l+r)/;
if(a[mid]<=x) l=mid+;
else r=mid;
}
return l;
} int main()
{
int n, m;
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
int ans = ;
for(int i=n-; i>; i--)
{
int x = m-a[i];
int num = er(, i, x) - ;
ans += num;
}
printf("%d\n", ans);
}
return ;
}
AC代码
E题：来源 POJ 1028
题意：
思路：
随手写个栈模拟一下就好了。
#include<stack>
#include<string>
#include<iostream>
using namespace std; string st[];
int top=;
int mt=; void push(string s)
{
st[++top]=s; mt=top;
} void pop()
{
if(top==) cout<<"Ignored"<<endl;
else cout<<st[--top]<<endl;
} int main()
{
st[top]="http://www.acm.org/";
string s;
while(cin>>s)
{
if(s[]=='Q') break;
if(s[]=='V')
{
cin>>s; cout<<s<<endl;
push(s);
}
else if(s[]=='B') pop();
else if(top==mt) cout<<"Ignored"<<endl;
else cout<<st[++top]<<endl;
}
return ;
}
AC代码