洛谷题单——模拟与高精度

[toc]

P1042 [NOIP2003 普及组] 乒乓球

这题我刚开始一直无法理解直到分差大于或者等于 22，才一局结束。后面一想，这不就是加球吗？那么，这题就好解了。

#include <iostream>
#include <string>
using namespace std;

void judge(const string& arr, int n) {
    int me = 0, em = 0;
    for (char ch : arr) {
        if (ch == 'W') me++;
        else em++;

        if ((me >= n || em >= n) && abs(me - em) >= 2) {		//记得要加abs取绝对值
            cout << me << ":" << em << endl;
            me = em = 0;
        }
    }
    cout << me << ":" << em << endl;
}

int main() {
    string arr;
    char ch;

    while (cin >> ch && ch != 'E') {
        if (ch == 'W' || ch == 'L') {
            arr += ch;
        }
    }

    judge(arr, 11);
    cout << endl;
    judge(arr, 21);

    return 0;
}

P2670 [NOIP2015 普及组] 扫雷游戏

注意数组类型为char，存储ascii码取数组下标为1开始（减少越界判断），对每个格子进行3*3的判定，返回判定值。

#include <。iostream>
#include <string>
using namespace std;
const int NUM = 105;
char arr[NUM][NUM]; //char

int judge(int x, int y) {
  int n = 0;
  if(arr[x][y] == '*')
  {
    return -1;
  }


  for (int i = x - 1; i <= x + 1; i++)
    for (int j = y - 1; j <= y + 1; j++) {
      if (arr[i][j] == '*') {
        n++;
      }
    }

  return n;
}

int main() {
  int n, m, res;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      cin >> arr[i][j];
    }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
    if((res = judge(i, j)) != -1)
        cout << res ;
    else
        cout << "*";        
    }
  cout << endl;
  }
  return 0;
}

P1563 [NOIP2016 提高组] 玩具谜题

在这里，我们只需要对顺时针数还是逆时针数做出判断，然后对循环数组进行加减。

#include <iostream>
#include <vector>
using namespace std;

vector<int> way;
vector<string> str;


int main()
{
    int n, m;
    int chaoxiang, fangxiang, step;
    string s;
    cin >> n >> m;
    for(int i  = 0; i < n; i++)
    {
        cin >> chaoxiang >> s;
        way.push_back(chaoxiang);
        str.push_back(s);
    }
    int pos = 0;
    for(int i = 0; i < m; i++)
    {
        cin >> fangxiang >> step;
        if(fangxiang == 0)
        {
            if(way[pos] == 0)
            pos = (pos + n - step)%n;
            else
            pos = (pos + n + step)%n;
        }
        else {
           if(way[pos] == 0)
            pos = (pos + n + step)%n;
           else
            pos = (pos + n - step)%n;
        }

    }
    cout << str[pos]<< endl;
    return 0;
}

P1601 A+B Problem（高精）

我们需要用数组存储A，B，由于运算是从最低位开始的，我们可以采用逆序存储数组。在加法函数，逐位加法，记录进位。别忘了循环后还可能有进位。最后将数组逆序即可。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
vector<int> A;
vector<int> B;

vector<int> add(vector<int> &A, vector<int> &B) {

  vector<int> C;
  int t = 0;
  if (A.size() < B.size())
    return add(B, A);
  for (int i = 0; i < A.size() || i < B.size(); i++) {
    // t + = A[i];
    if (i < A.size())
      t += A[i];
    if (i < B.size())
      t += B[i];
    C.push_back(t % 10);
    t /= 10; //去进位
  }
  if (t)
    C.push_back(1); //有无进位判断
  reverse(C.begin(), C.end());
  return C;
}

int main() {
  int tmp;
  string a, b;

  cin >> a >> b;
  for (int i = a.size() - 1; i >= 0; i--)		//逆序存放进数组
    A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--)
    B.push_back(b[i] - '0');
  vector<int> res = add(A, B);

  for (auto tmp : res) {
    cout << tmp;
  }
  cout << endl;
  return 0;
}

P1303 A*B Problem

模仿乘法，这次采用顺序存储，对于乘法，我们可以采用类似dp的思路，由于是多位数*多位数的乘法，在每次多位数*一位数，相加的时候，都会有重叠，我们应当小心处理这种重叠，进位=原来的值+相乘的值+进位 ，且第i个元素与第j个元素存储于i+j+1的位置（下标从0开始）。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

 

vector<int> mul(vector<int> A，, vector<int> B) {
    vector<int> res(A.size() + B.size(), 0);		//预留位置

    for (int i = A.size() - 1; i >= 0; i--) {
        int carry = 0;      //进位
        for (int j = B.size() - 1; j >= 0; j--) {
            int temp = res[i + j + 1] + A[i] * B[j] + carry;        //dp
            res[i + j + 1] = temp % 10;
            carry = temp / 10;
        }
        res[i] += carry;
    }

    while (res.size() > 1 && res[0] == 0) {		//移除前导0
        res.erase(res.begin());
    }

    return res;
}

int main() {
  string a, b;
  vector<int> A, B;
  cin >> a >> b;
  for (int i = 0; i < a.size(); i++)
    A.push_back(a[i] - '0');
  for (int i = 0; i < b.size(); i++)
    B.push_back(b[i] - '0');
  vector<int> res = mul(A, B);

  for (auto &tmp : res) {
    cout << tmp;
  }
  cout << endl;
  return 0;
}

P1009 [NOIP1998 普及组] 阶乘之和

这时候就用上我们前面写的高精度了，下面是我原来的做法，由于我们计算的是大数，因此只有当#define int long long时才能得到正确答案（超出tmp和carry的范围），如果我们想支持更多的数，就要添加除法和减法。

#include <algorithm>
#include <iostream>
#include <vector>
#define int long long

using namespace std;

vector<int> add(vector<int> A, vector<int> B) {

  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  vector<int> res;
  int tmp = 0;
  for (int i = 0; i < A.size() || i < B.size(); i++) {
    if (i < A.size())
      tmp += A[i];
    if (i < B.size())
      tmp += B[i];
    res.push_back(tmp % 10);
    tmp /= 10;
  }
  if (tmp)
    res.push_back(tmp);
  reverse(res.begin(), res.end());
  return res;
}

vector<int> mul(vector<int> A, vector<int> B) {
  vector<int> res(A.size() + B.size(), 0);
  for (int i = A.size() - 1; i >= 0; i--) {
    int carry = 0;
    for (int j = B.size() - 1; j >= 0; j--) {
      int tmp = res[i + j + 1] + carry + A[i] * B[j];
      res[i + j + 1] = tmp % 10;
      carry = tmp / 10;			//进位
    }
    res[i] += carry;
  }

  while (res.size() > 1 && res[0] == 0) {
    res.erase(res.begin());
  }
  return res;
}

signed main() {
  int x;

  cin >> x;

  vector<int> res2 = {1}; //阶乘
  vector<int> res4 = {0}; //阶乘和
  for (int i = 1; i <= x; i++) {
    vector<int> current = {i};
    res2 = mul(current, res2);
    res4 = add(res2, res4);
  }

  for (auto &tmp : res4)
    cout << tmp ;
  cout << endl;
  return 0;
}

因此我们可以改用n*1的乘法，因为50一定是能用int容纳的。

#include <algorithm>
#include <iostream>
#include <vector>


using namespace std;

vector<int> add(vector<int> A, vector<int> B) {

  vector<int> res;
  int tmp = 0;
  for (int i = 0; i < A.size() || i < B.size(); i++) {
    if (i < A.size())
      tmp += A[i];
    if (i < B.size())
      tmp += B[i];
    res.push_back(tmp % 10);
    tmp /= 10;
  }
  if (tmp)
    res.push_back(tmp);
  return res;
}

 vector<int> mul(vector<int> A, int b)
 {  
       
        vector<int> C;
        int t = 0;
        for (int i = 0; i < A.size() || t; i ++ )		
        { 
            if (i < A.size())   t += A[i] * b;
            C.push_back(t % 10);
            t /= 10;
        }
    // while (C.size() > 1 && C.back() == 0) C.pop_back();            

    return C;
 }



signed main() {
  int x;

  cin >> x;

  vector<int> res2 = {1}; //阶乘
  vector<int> res4 = {0}; //阶乘和
  for (int i = 1; i <= x; i++) {
    vector<int> current = {i};
    res2 = mul(res2, i);
    res4 = add(res2, res4);
  }

  for (int tmp = res4.size() - 1; tmp >= 0; tmp--)
    cout << res4[tmp] ;
  cout << endl;
  return 0;
}

P4924 [1007] 魔法少女小Scarlet

我们需要模拟矩阵的子矩阵的转置。

矩阵转置可以分为两步，首先交换矩阵对角线的值。这里要注意即使在中心点，x和y也可能不是对称的，即我们只能用x表示x，用y表示y。

• 对于顺时针转置矩阵，我们需要交换每列
• 对于逆时针转置矩阵，我们需要交换每行

这里感觉c数组更方便做，cpp看得头晕X﹏X

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> matrix;

// void transpose(int x, int y, int n){
//   for(int i = x - n; i <= x + n; i ++)
//   {
//     for(int j = y - n; j <= y + n; j++)
//        if (i < j) {     //若无此判断等于没交换
//                 swap(matrix[i][j], matrix[j][i]);   
//             }
//   }
// }  由于x和y并不是对称的，这个交换在x，y不同时会出现错误,
//如（20，2）与（2，20）交换，尽管要转置的矩阵大小只有3

void transpose(int x, int y, int n) {
    for (int i = 0; i <= n * 2; i++) {
        for (int j = i + 1; j <= n * 2; j++) {		//确保不会重复交换
            swap(matrix[x - n + i][y - n + j], matrix[x - n + j][y - n + i]);
        }
    }
}



void rotateClockwise(int x, int y, int n) {
    transpose(x, y, n);
    for (int i = x - n; i <= x + n; i++) {
        reverse(matrix[i].begin() + (y - n), matrix[i].begin() + (y + n + 1));
        //reverse不包括last所指的元素
    }
}

void rotateCounterwise(int x, int y, int n) {
    transpose(x, y, n);
    for (int j = y - n; j <= y + n; j++) {
        for (int i = x - n, k = x + n; i < k; i++, k--) {	//双指针
            swap(matrix[i][j], matrix[k][j]);
        }
    }
}

void init(int n) {
  matrix.resize(n + 1, vector<int>(n + 1, 0));		//预留并初始化为0
  int tmp = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      matrix[i][j] = tmp++;
}

void display(int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << matrix[i][j] << " ";
    }
    cout << endl;
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  init(n);
  int x, y, r, z;
  for (int i = 0; i < m; i++) {
    cin >> x >> y >> r >> z;
    //cout << x << y << r << z << endl;
    if (z == 0) {
      rotateClockwise(x, y, r);
    } else if(z == 1){
      rotateCounterwise(x, y, r);
    }
  }

  display(n);
}