首页 > 代码库 > Noip 2016
Noip 2016
Day1
思路：
大致是 把一个环拆成链， 找某个人无非是向右找或向左找（即对当前点加或减）
若加上要移动的位置后坐标大于总人数， 就把当前坐标减去总人数，
若减去要移动的位置后坐标小于0， 就把当前坐标加上总人数
另外要注意的就是每个小人的朝向问题， 这个也很好解决。
通过观察不难发现，小人面朝里， 向右移动的话， 就是加， 向左为减。
小人面朝外则反之。
最后输出当前坐标小人的名称。
#include <iostream> #include <cstdio> #include <cstring> #define Max 100003 using namespace std; int N, M; struct node { int towards; string name; }people [Max]; int main() { scanf ("%d%d", &N, &M); int f; string a; for (int i = 1; i <= N; i++) { scanf ("%d", &people [i].towards); cin >> people [i].name; } int x, y; int now = 1; for (int i = 1; i <= M; i++) { scanf ("%d%d", &x, &y); if (people [now].towards == 0 && x == 0) { now -= y; if (now <= 0) now = N + now; } else if (people [now].towards == 0 && x == 1) { now += y; if (now > N) now = now - N; } else if (people [now].towards == 1 && x == 0) { now += y; if (now > N) now = now - N; } else if (people [now].towards == 1 && x == 1) { now -= y; if (now <= 0) now = N + now; } } cout << people [now].name; return 0; }
第二题 天天爱跑步
不会， 当时做时就是骗的分
由数据范围可知：
前两个点所有玩家的起点等于终点， 那么就好办了。
扫一遍所有的点， 如果有玩家的起点在这个点上（因为起点与终点相同 所以只需要判起点就好了）， 那么这个观察员可观察的人数加1。如此， 最后输出即可
第三和第四个点是 观察员的观测时间都是0，
那么只要扫一遍所有玩家的起点，把起点上的观测员可观察到的人数加一即可。
但是 ！！当时考试时我就是这么打的， 结果一分没得。（原因不明）
（把自己的答案与标准答案比了半天也没发现哪有不同）。
第三题 换教室
不会 当时打的是暴力
当时思路就是 先跑一边floyed 找处所有点的最短路
然后搜索可能的情况（类似于全排列），挨个算， 算完后刷新最小值
但是还是写崩了， 枚举可能的情况那一步怎么也打不对。
无奈想放弃治疗时， 突然发现有些数据是m = 0 的， 即只需跑一边裸的floyed。
找出最短路即可， 结果floyed 初始化时忘记把对角线赋值为零（即当 i = j的情况）。
于是GG。 0分
Day2
第一题 组合数
思路：
当时考场上时， 由于未接触过组合数什么的
所以做此题时一头扎进他给的公式中出不来了
想了很久， 大多是围绕直接算阶乘的方法。最后无果， 只能打了个30%数据的表
骗了30.。
AC做法。。
动态规划， 恩， 好吧。。一点也没想到
大体上是 运用递推， 推出
公式为 number[i][j] = number[i-1][j-1]+number[i-1][j] 注意还要mod K， 反正都是要求的是K的倍数，mod K一举两得
因为可能这个数会很大。。。。爆long long
如果mod K 后等于0， 那么说明符合题意 i的计数器加一
最后再加到 答案dp[i][j]中去 , dp[i][j] = dp[i-1][j] + 计数器
最后再注意判断一下 m 和 n 的关系 这个题就OK了。。
#include <iostream> #include <cstdio> #include <cstring> #define Max 2000 using namespace std; long long number [Max][Max]; // 组合数 。number [i][j]表示i个东西分成 j份的方案数 long long dp [Max][Max]; // dp[i][j] 表示的是i个东西分成j份中是k的倍数 的方案数 long long Total [Max]; inline void read (int &now) { char word = getchar (); now = 0; while (word > ‘9‘ || word < ‘0‘) word = getchar (); while (word <= ‘9‘ && word >= ‘0‘) { now = now * 10 + (int)(word - ‘0‘); word = getchar (); } } int main() {int T, K; read (T); read (K); number [0][0] = 1; //初始化 for (int i = 1; i <= Max; i++) //先把所有的预处理出来， 否则 每次都查询会超时。。 { number [i][0] = 1; //初始化 i个物品分0个的方案数为 1 for (int j = 1; j <= i; j++) { number [i][j] = (number [i - 1][j - 1] + number [i - 1][j]) % K; // 递推求组合数 number[i][j]是由上一个物品选或不选递推而来 if (number [i][j] == 0) //如果能被K整除 计数器加一 Total [i]++; dp [i][j] = dp [i - 1][j] + Total [i]; //i个物品分j份 的方案数满足条件的 是上一个状态加上这一个状态的总数得出 if (i == j) // 注意判断一下i == j 即i个物品分i份的情况 。 dp [i][j] = Total [i] + dp [i - 1][j - 1]; } } while (T--) { int n, m; read (n); read (m); cout << dp [n][m > n ? m = n : m] << endl; //因为 0 <= m <= min (m, n), 所以要判断一下 } return 0; }
第二题 蚯蚓
Noip 2016