这次题目的难度中等偏上 大概预期是 低年级两到三道 高年级三到四道 最后结果有点不尽人意但是希望大家能在比赛中有点收获 下面废话少说 送上这次比赛的题解
题目
A ZOJ 1003
B POJ 1001
C HDU 1730
D HDU 1257
E HDU 1960
F POJ 3621
A ZOJ 1003
题意：地面上有100个气球 编号为1~100 两个人踩气球 初始分数都是1 踩到相应编号的气球则分数乘以相应编号 最后两个人报出自己的分数 分数高的取胜 但是可能存在有人说谎的情况 分数低的人可以质疑分数高的人 如果分数高的人有一个分数不是自己踩气球得到的 则质疑是对的 分数低的选手是赢家 例如 分数高的选手要得到他说出的分数必须要踩到分数低的选手一定会踩到的气球 则质疑成功 另外 如果两个人分数都计算错误的话 则质疑被否决题解：根据题目要求模拟 首先将分数高的赋值n 分数低的赋值m 之后通过递归因式分解 判断是否有公因子因为气球编号是1~100 所以从100开始向下判断因子就好了 如果有公因子 分数低的选手是赢家 如果没有 分数高的选手是赢家 如果全部说谎或者全部正确 则判断高分获胜
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;bool aT, bT;void dfs(int n, int m, int p);int main(){int n, m;while(scanf("%d%d", &n, &m) != EOF){if(n < m){//将分数高的赋值n 分数低的赋值mswap(n, m);}aT = false;//先将a b都赋值为说谎bT = false;dfs(n, m, 100);//递归因式分解if(!aT && bT){//只有高分的说谎 则输出低分printf("%d\n", m);}else{//高分的没有说谎或者全部说谎或者全部正确 则输出高分printf("%d\n", n);}}return 0;}void dfs(int n, int m, int p){if(n == 1 && m == 1){//两个人都没有说谎 将aT赋值为没有说谎就好了aT = true;return ;}if(m == 1){//低分者没有说谎bT = true;}while(p > 1){//因式分解if(n % p == 0){dfs(n/p, m, p-1);}if(m % p == 0){dfs(n, m/p, p-1);}–p;}}
B POJ 1001
高精度乘法 问了下晖哥ICPC比赛时可以用多种语言混合提交 这里就给出Java的写法 建议掌握Java的大数类C++的版本自己感兴趣的自己去敲一敲好了 把小数点去掉乘法最后加上小数点就好了
import java.math.BigDecimal;import java.util.Scanner;public class Main {public static void main(String[] args) {@SuppressWarnings("resource")Scanner sc = new Scanner(System.in);while (sc.hasNext()) {BigDecimal bd = new BigDecimal(sc.next());BigDecimal result = bd.pow(sc.nextInt());String s = result.stripTrailingZeros().toPlainString();if (s.startsWith("0"))s = s.substring(1);System.out.println(s);}}}
C HDU 1730
这道题是典型的博弈论Nim问题 我们先了解一下Nim问题理论铺垫。。。1、定义P-position和N-position：其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。（1）.无法进行任何移动的局面（也就是terminal position）是P-position；（2）.可以移动到P-position的局面是N-position；（3）.所有移动都导致N-position的局面是P-position。2、P/N状态有如下性质：（1）、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。（2）、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。（3）、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态3、P点： 即必败点，某玩家位于此点，只要对方无失误，则必败； N点： 即必胜点，某玩家位于此点，只要自己无失误，则必胜。4、取石子游戏算法实现步骤1:将所有终结位置标记为必败点（P点）；步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；步骤4: 如果在步骤3未能找到新的必败（P点），，则算法终止；否则，返回到步骤21、问题模型：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。2、解决思路：用（a，b，c）表示某种局势，显证（0，0，0）是第一种奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。 搞定这个问题需要把必败态的规律找出：(a,b,c)是必败态等价于a^b^c=0(^表示异或运算）证明:(1)任何p(a,b,c)=0的局面出发的任意局面(a,b,c’);一定有p(a,b,c’)不等于0。否则可以得到c=c （2）任何p(a,b,c)不等于0的局面都可以走向 p(a,b,c)=0的局面 (3）对于 (4,9,13) 这个容易验证是奇异局势
其中有两个8，两个4，两个1，非零项成对出现，这就是尼姆和为 零的本质。别人要是拿掉13里的8或者1，那你就拿掉对应的9 中的那个8或者1；别人要是拿 掉13里的4，你就拿掉4里的4； 别人如果拿掉13里的3，就把10作分解，然后想办法满 足非零项成对即可。3、推广一：如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c 变为 a^b,即可,因为有如下的运算结果: a^b^(a^b)=(a^a)^(b^b)=0^0=0。要将c 变为a^b，只从 c中减去 c-（a^b）4、推广二：当石子堆数为n堆时，则推广为当对每堆的数目进行亦或之后值为零是必败态。再回到这道题 我们只需要把每行之间的空格数相互异或最后求得结果判断是不是0就可以了。。
可我，仍在旅行的路上徘徊。等待着每一辆经过的车，让我走到更远的地方。
