【第一题】石头剪刀布 rps
【题目大意】
a和b石头剪刀布游戏，每个人一共有五种方式，相互之间的胜负关系给出，a和b出拳的方式是循环的，赢者得一份，其余不得分。
问n轮以后a和b的得分。
纯粹的模拟题，把胜负关系打表或者case出来即可。
#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int win[5][5] = {0,0,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1,1,0,0,0};int a[205], b[205];int main(){freopen("rps.in","r",stdin);freopen("rps.out","w",stdout);int n, na, nb;cin>>n>>na>>nb;for (int i = 0; i < na; ++i) cin>> a[i];for (int i = 0; i < nb; ++i) cin>> b[i];int i = 0, j = 0;int ascore = 0, bscore = 0;while (n) {ascore += win[a[i]][b[j]];bscore += win[b[j]][a[i]];i = (i + 1) % na;j = (j + 1) % nb;n –;}cout << ascore << " "<< bscore<<endl;return 0;}【第二题】联合权值link
给出n个点，n-1条件的图，每个点均有点权值w[i]，如果i和j距离为2，那么他们会产生w[i] * w[j]的值，求问产生值中的最大值和产生值得总和。
分析：如果两两求，那么我们构造一个星形的图，这样的点对就接近n^2对，那么复杂度太高。
那么利用点i，周围的点a,b,c ,如果a，b，c在i的周围那么a，b，c相互之间的距离一定是2。那么他们会产生的值有ab+ac+ba+bc+ca+cb=(a+b+c)^2-a^2-b^2-c^2
故我们可以利用这种方法求出两两之间的和，至于最大值，直接选取a，b，c中的最大值和次大值来产生最大值。
#include <iostream>#include <cstdio>#include <cstdlib>#include <vector>#define maxn 600010using namespace std;struct Edge {int v,next;}e[maxn];long long p[maxn],w[maxn], en = 0;int f[maxn];void add(int u, int v) {en ++;e[en].v = v;e[en].next = f[u];f[u] = en;}int main(){freopen("link.in","r",stdin);freopen("link.out","w",stdout);int n,u,v;cin >> n;for (int i = 1; i <= n; ++i) f[i] = -1;for (int i = 1; i < n; ++i) {scanf("%d %d", &u, &v);add(u,v);add(v,u);}long long total = 0, max = 0;for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);for (int i = 1; i <= n; ++i) {int cnt = 0;long long sum1= 0;int max1 = 0, max2 = 0;for (int j = f[i]; j != -1; j = e[j].next) {p[++cnt] = w[e[j].v];sum1 = (sum1 + p[cnt]) % 10007;total = (total – p[cnt] * p[cnt] + 10007) % 10007;if (p[cnt] > max1) max2 = max1, max1 = p[cnt];elseif (p[cnt] > max2)max2 = p[cnt];}if (cnt > 0) {total = (total + sum1 * sum1) % 10007;}if (total < 0) total += 10007;if (max1 * max2 > max) max = max1 * max2;}cout <<max<<" "<<total<<endl;return 0;}【第三题】飞扬的小鸟 bird
【题目大意】游戏规则：
1. 游戏界面是一个长为n，高为m的二维平面，其中有 k个管道（忽略管道的宽度）。
2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边 任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
3. 小鸟每个单位时间沿横坐标方向右移的距离为1，竖直移动的距离由玩家控制。如 果点击屏幕，小鸟就会上升一定高度X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度Y。小鸟位于横坐标方向不同位置时，上升的高度X和下降的高度Y可能互不相同。
4. 小鸟高度等于0或者小鸟碰到管道时，游戏失败。小鸟高度为m时，，无法再上升。 现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
分析：本体类似于经典的完全背包问题，每个阶段解决向上或者向下，而且次数不限，类似于物品个数没有限制。所以f[i][j]的状态可以从f[i-1][*]和f[i][*]中转移过来。
保证时间复杂度是O（nm）即可
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#define maxn 10010using namespace std;const int inf = 0x7ffffff;int n,m,k,p,l,h;int x[maxn],y[maxn],down[maxn], up[maxn];int f[maxn][1001];int main() {freopen("bird.in","r",stdin);freopen("bird.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for (int i = 0; i < n; ++i)scanf("%d %d", &x[i], &y[i]);for (int i = 1; i <=n; ++i) {down[i] = 0;up[i] = m + 1;}for(int i = 1; i <= k; ++i) {cin >> p >> l >> h;down[p] = l;up[p] = h;}for (int i = 1; i <= n; ++i)for (int j = 0; j <= m; ++j)f[i][j] = inf;f[0][0] = inf;int arrive = k;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if(j >= x[i-1]){f[i][j] = min(f[i][j], f[i-1][j-x[i-1]] + 1);f[i][j] = min(f[i][j], f[i][j-x[i-1]] + 1);}if(j == m) {for(int k=j-x[i-1];k<=m;k++) {f[i][j] = min(f[i][j], f[i-1][k] + 1);f[i][j] = min(f[i][j], f[i][k] + 1);}}}for (int j = down[i]+1; j <= up[i]-1; ++j)if( j + y[i-1] <= m)f[i][j] = min(f[i][j], f[i-1][j+y[i-1]]);for (int j = 1; j <= down[i]; ++j) f[i][j] = inf;for (int j = up[i]; j <= m; ++j) f[i][j] = inf;}int cnt = k, ans = inf;for (int i = n; i >= 1; i–) {for (int j = down[i]+1; j <= up[i]-1; ++j)if (f[i][j] < inf)ans = min(ans, f[i][j]);if (ans != inf) break;if (up[i] <= m)cnt –;}if(cnt==k)printf("1\n%d\n", ans);elseprintf("0\n%d\n", cnt);return 0;}
最可怕的敌人，就是没有坚强的信念。
