链接在这:http://bak.vjudge.net/contest/132442#overview。
A题,给出a,b和n,初始的集合中有a和b,每次都可以从集合中选择不同的两个,相加或者相减,得到一个新的数,如果在1~n内的话就放入集合中,并算一次操作,谁先不能操作(所有新数已经存在于集合内的话就不能进行操作)者输。问谁会赢。
可以得到的数字为k*gcd(a,b),那么只要算出在1~n的范围内存在多少个这样的数字,判断一下奇偶性即可。
B题,给出n个字符串,问最大的满足条件的字符串的位置,条件为,在它前面的字符串中至少存在一个字符串不是它的子串。那么方法是我们判断第 i 个字符串的时候,找出前面的不是别人子串的那些字符串,来判断是不是这个字符串的子串,如果不是,那么更新答案,如果是(那么是前面这个字符串子串的字符串肯定也都是 i 的子串,而我们要找的是不是 i 子串的字符串),那么前面那个字符串给一个标记,表示它也是别人的子串了,那么后面就不用再管它了。显然复杂度是O(n^2+n*lenth)。
C题,因为一个集合内互相到达的距离t都是相等的,那么我们可以新建一个点,这个集合内的点到新点的距离都为0,而新点到集合内的点的距离都是t,借助这个辅助点,我们就可以将条件转化了。然后我们使用dijkstra算法找出从1开始的最短路和从n开始的最短路即可。
D,每个青蛙可以遍历的石头其实是k*gcd(a[i],m),但是很显然会有重复,因此我们用容斥做。具体方法比较奥义,见代码吧(手动模拟一下以后就比较好理解了):
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 10000 +5; 6 typedef long long ll; 7 8 int n,m; 9 int a[N]; 10 int cnt,p[100000]; 11 int vis[100000],num[100000]; 12 // vis表示这个因子应该被使用的次数,num表示这个因子已经使用过的次数 13 14 int main() 15 { 16 int T;scanf("%d",&T); 17 for(int kase=1;kase<=T;kase++) 18 { 19 memset(vis,0,sizeof(vis)); 20 memset(num,0,sizeof(num)); 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=n;i++) scanf("%d",a+i); 23 cnt = 0; 24 for(int i=1;1LL*i*i<=(ll)m;i++) 25 { 26 if(m%i==0) 27 { 28 p[++cnt] = i; 29 if(1LL*i*i != (ll)m) p[++cnt] = m/i; 30 } 31 } 32 sort(p+1,p+1+cnt); 33 for(int i=1;i<=n;i++) 34 { 35 int g = __gcd(a[i],m); 36 for(int j=1;j<=cnt;j++) 37 { 38 if(p[j] % g == 0) vis[j] = 1; 39 } 40 } 41 42 vis[cnt] = 0; // 最后一个数是不能跳的 43 ll ans = 0; 44 for(int i=1;i<=cnt;i++) 45 { 46 if(vis[i] != num[i]) 47 { 48 ans += 1LL * (vis[i]-num[i]) * m * (m/p[i] - 1) / 2; 49 int t = vis[i] - num[i]; 50 for(int j=i;j<=cnt;j++) 51 { 52 if(p[j]%p[i] == 0) num[j] += t; 53 } 54 } 55 } 56 printf("Case #%d: %I64d ",kase,ans); 57 } 58 }