程序设计竞赛(CCPC)"/>
2020中国大学生程序设计竞赛(CCPC)
题目链接
Problem Description
Now it’s time for lunch. Today’s menu is chocolate!
Though every baby likes chocolate, the appetites of babies are little. After lunch, there are still n pieces of chocolate remained: The length of the ith piece is li.
Using the remained chocolate, Baby Volcano is going to play a game with his teacher, Mr. Sprague. The rule of the game is quite simple.
Two player plays in turns, and Baby Volcano will play first:
- In each turn, the player needs to select one piece of chocolate. If the length of the selected piece is equal to 1, the player of this turn will lose immediately.
- Suppose the length of the selected piece is l. Then the player needs to select a positive integer k satisfying k is at least 2 and k is a factor of l.
- Then the player needs to cut the selected piece into k pieces with length lk.
The game continues until one player selects a piece of chocolate with length 1.
Suppose both players plays optimally, your task is to determine whether Baby Volcano will win.
Input
The first line contains single integer t(1≤t≤2e4), the number of testcases.
For each testcase, the first line contains a single integer n(1≤n≤10).
The second line contains n positive integers li(1≤li≤1e9), representing the length of each piece.
Output
For each testcase, output char ‘W’ if Baby Volcano will win, otherwise output char ‘L’.
Sample Input
3
2
4 9
2
2 3
3
3 9 27
Sample Output
W
L
L
博弈~
求出每个数的质因子指数和,2 的话只能算一次,然后全部抑或起来即可(PS:比赛时卡着时间过的,发现用原来的代码交会 T),仔细想了一下,做了如下两点改进:
1.把外置函数放到主函数里,减少调用时间
2.把 l o n g l o n g long\ long long long 改成 i n t int int,之前在做 POJ 的时候碰到过一次, l o n g l o n g long\ long long long 在循环里的确比 i n t int int 慢
果不如其然,用了 1500ms 就过了,AC代码如下:
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int prime[N], k;
bool isprime[N];void Prime() {fill(isprime, isprime + N, 1);k = 0;for (int i = 2; i <= N; i++) {if (isprime[i]) prime[k++] = i;for (int j = 0; j < k; j++) {if (i * prime[j] > N) break;isprime[i * prime[j]] = 0;if (i % prime[j] == 0) break;}}
}int main() {int n, t, a[15];Prime();scanf("%d", &t);while (t--) {scanf("%d", &n);int ans = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);int flag = ((a[i] % 2) ^ 1);while (a[i] % 2 == 0) a[i] /= 2;int sum = 0;for (int j = 0; j < k && prime[j] * prime[j] <= a[i]; j++) {while (a[i] % prime[j] == 0) {sum++;a[i] /= prime[j];}}if (a[i] > 1) sum++;ans ^= (sum + flag);}if (ans) printf("W\n");else printf("L\n");}return 0;
}
更多推荐
2020中国大学生程序设计竞赛(CCPC)
发布评论