前言

难度适中，第一题和第二题偏向思维题。第三题的dp比较恶心，各种卡，需要每一步都做好规划且不放弃，才能完整做出来

T1

某同学做一张试卷，有n道选择题，每个选择题只有A和B两个选项。现在给出该同学的答案和标准答案。问如果该同学把所有答案都反选（原来选A现在选B，反之亦然），正确答案数会不会变多？

输入：第一行一个正整数T（T<=1000），代表测试数据组数。对于每组数据，先一个整数n(n<1000)代表题目数量，紧接着两行给定两个n个字符的字符串s和t，每个字符串都只包含A和B两种字符。如果第一个代表该同学选的答案，第二个正确答案。

输出：如果正确答案数会变多，则输出"oh no"，如果答案数不变则输出"(O.O)"，如果答案数变少则输出"oh yes"。

输入
1
2
AB
AA
输出
(O,O)

反选前，该同学只做对了第一题，反选后做对了后两道题目，正确数变多了，输出yes。

思路

先求出最开始做对的题目数x，然后n-x即得到反选后的正确答案数。比较两者即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string s,t;
int n,T,ans;
int main()
{
 cin>>T;
 while(T--) {
  cin>>n;
  cin>>s>>t;
  ans = 0;
  for(int i = 0; i<s.size(); i++) {
   if(s[i] == t[i]) ans++;
  }
  if(n - ans > ans) cout << "oh no" << endl;
  else if(n - ans == ans) cout << "(O.O)" << endl;
  else cout << "oh yes" << endl;  
 } 

 return 0;
}

T2

现在有一场射击比赛。已知一个弹夹最多装m枚子弹，并且每开一枪需要花费1分钟。现在有两种装弹方式：

1. 一次性将弹夹装满，这种方式需要a分钟；
2. 往弹夹里一枚一枚装，这种方式装一枚需要b分钟；

现在有一支里面没有子弹的枪，要发射n枚子弹，问最少需要花费多少时间？

输入四个整数n,m,a,b

输出最少时间

输入
3 2 1 1
输出
5

输入
10 2 164 18
输出
190

思路

分情况讨论。同样是装满一个弹夹，如果一枚一枚装比一次性装满更快，那就n枚全都一枚一枚装；反之则对于完整弹夹都一次性装满，对于剩余子弹（一定少于m枚），比较这两种方式哪个快用哪个 。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long n,m,a,b;
int main()
{
 cin>>n>>m>>a>>b;
 if(b*m <= a) { // 同样是装满一个弹夹，如果一枚一枚装比一次性装满更快，那就n发全都一枚一枚装。 
  cout << b*n + n;
 } else {// 反之则对于完整弹夹都一次性装满，对于剩余子弹，比较这两种方式哪个快用哪个 
  long long times = n/m, res = n-m*times;
  cout << times * a + min(res*b, a) + n;
 }
 return 0;
}

T3

长为n,宽为m的二维平面上，每个位置是一个洞口。有k个地鼠，每个地鼠都有一个钻出来的位置，时间，分数。表示为x,y,t,s，在位置(X,y)时间t秒钻出来，分数为s。每个地鼠身上都有些分数，如果打到地鼠，就可以得到分数。有可能很多只地鼠在同一位置，同一时间钻出来，所以一锤子可以打好多只地鼠。

一开始（时间0）的时候小明在(1,1)的位置，每秒可以移动到前后左右相邻的任意一一个位置上，也可以不移动。

要怎么规划路线，小明可以得到最多的分数？

输入：

第一行为三个整数n,m,k分别代表长为n,宽为m,有k只地鼠。

接下来k行，每行四个整数x,y,t,s代表有地鼠在位置(x,y)时间t钻出来，分数为s。

0≤k≤10^5

0<n,m≤100

1≤x≤n

1≤y≤m

0<t,s≤1000

输出：输出最高分数

输入
10 10 5
1 1 3 10
1 1 3 2
1 2 4 3
2 1 4 5
1 3 5 1
输出
17

思路

这题思路是动态规划。第一个难点在于状态设计和转移，dp[t][i][j]代表在t时刻并且在(i,j)位置上时，最大可以获得多少分数。靠上下左右四个位置来做状态转移。

这题第二个难点在卡空间，即不能开下dp[1000][100][100]的数组和a[1000][100][100]两个数组，对于dp数组可以用滚动数组来优化掉第一维度，对于a数组（对读入xyts数据的存储），采用时间换空间的方式，先开1000个vector来存每一秒的所有地鼠，然后在dp维护到哪一秒的时候，再把对应的vector展开成数组。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int K,n,m;
int a[105][105];
vector<vector<int> > vv[1005];
int dp[2][105][105];
int nx[] = {1,0,-1,0};
int ny[] = {0,1,0,-1};
int main()
{
 for(int i = 0; i<=1; i++) for(int j = 0; j<=102; j++) for(int k = 0; k<=102; k++) dp[i][j][k]=-1e8;
 dp[0][1][1] = 0;
 cin>>n>>m>>K;
 for(int x,y,t,s,i = 0; i<K; i++) {
  cin>>x>>y>>t>>s;
  vector<int> v = {x,y,s};
  vv[t].push_back(v);
 }
 for(int t = 1; t<=1000; t++) {
  for(int i = 0; i<=n; i++) for(int j = 0; j<=m; j++) a[i][j] = 0;
  for(auto v : vv[t]) {
   a[v[0]][v[1]] += v[2];
  }
  for(int i = 1; i<=n; i++) {
   for(int j = 1; j<=m; j++) {
    int flag = t%2;
    dp[flag][i][j] = dp[1-flag][i][j] + a[i][j];
    for(int k = 0; k<4; k++) {
     int tx = i + nx[k], ty = j + ny[k]; 
     if(tx >=1 && tx <= n && ty >= 1 && ty <= m) {
      dp[flag][i][j] = max(dp[flag][i][j], dp[1-flag][tx][ty] + a[i][j]);
     }
    }
   }
  }  
 }
 int ans = 0;
 for(int i = 1; i<=n; i++) {
  for(int j = 1; j<=m; j++) ans = max(ans, dp[0][i][j]);
 }
 cout << ans << endl;

    return 0;
}