头像

Alier

Kickstart, Codeforces, AtCoder


访客:15956

离线:12天前



Alier
5个月前

Problem
You are organizing an international dancing competition. You have already obtained all of the following:

  • A dance floor with R rows and C columns, consisting of unit square cells;
  • R × C competitors;
  • A cutting-edge automated judge for the competition.
    But you are still missing an audience! You are worried that the competition might not be interesting enough, so you have come up with a way to calculate the interest level for the competition.

Each competitor occupies one square unit cell of the floor and stays there until they are eliminated. A compass neighbor of a competitor x is another competitor y chosen such that y shares a row or column with x, and there are no competitors still standing in cells in between x and y. Each competitor may have between 0 and 4 compass neighbors, inclusive, and the number may decrease if all the other competitors in one orthogonal direction are eliminated.

The competition runs one round at a time. In between rounds i and i+1, if a competitor d had at least one compass neighbor during round i, and d’s skill level is strictly less than the average skill level of all of d’s compass neighbors, d is eliminated and is not part of the competition for rounds i+1, i+2, i+3, etc. Notice that d still counts as a neighbor of their other compass neighbors for the purpose of other eliminations that may also happen between rounds i and i+1. Competitors that do not have any compass neighbors are never eliminated. If after a round no competitor is eliminated, then the competition ends.

The interest level of a round is the sum of skill levels of the competitors dancing in that round (even any competitors that are to be eliminated between that round and the next). The interest level of the competition is the sum of the interest levels of all of the rounds.

Given the skill levels of the dancers that are on the floor for the first round, what is the interest level of the competition?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers R and C. Then, there are R more lines containing C integers each. The j-th value on the i-th of these lines, $S_{i,j}$ , represents the skill level of the dancer in the cell in the i-th row and j-th column of the floor.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the interest level of the competition.

Limits
Time limit: 40 seconds per test set.
Memory limit: 1GB.
$1 ≤ S_{i,j} ≤ 10^6$ , for all i and j.

Test set 1 (Visible Verdict)
1 ≤ T ≤ 100.
1 ≤ R × C ≤ 100.

Test set 2 (Hidden Verdict)
10 ≤ T ≤ 100.
$1000 < R × C ≤ 10^5$ , in exactly 10 cases.
1 ≤ R × C ≤ 1000, in exactly T - 10 cases.

Sample

Input

4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3

Output
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14

In Sample Case #1, only one competitor is on the floor. Since the competitor does not have any compass neighbors, they dance in one round, and then the competition is over. Thus the answer is equal to the dancer’s skill level, 15.

In Sample Case #2, the interest level of the first round is 1+1+1+1+2+1+1+1+1=10.

The competitors that are not in the center nor in a corner have a skill level of 1, but the average of their compass neighbors is 4 / 3, which is greater than 1, so they are eliminated. The floor during the second round looks like this:

1 . 1
. 2 .
1 . 1
This round is the last one. The competitors in the corner have two compass neighbors each, but the average of their skill level is equal to their own. The competitor in the center has no compass neighbor. The interest level of the round is 1+1+2+1+1=6. This means the interest level of the competition is 10+6=16.

In Sample Case #3, the competitor with skill level 1 is eliminated after the first round, while the other two remain. In the second round, the two other competitors become compass neighbors, and this causes the competitor with skill level 2 to be eliminated. There is a single competitor in the third round, which makes it the last one. The interest levels of the rounds are 6, 5 and 3, making the interest level of the competition 14.

/*
主要思路:不用真的删去矩阵中的邻居,而是将其表示出来,实时更新
用一个数组记录还留下的点中会变动的点的坐标,实时更新
只有在前一轮中,邻居出现变动的数,才会在下一轮有可能出现变动,每回合只需计算这些点

*/
/**
 *    author:  tourist
 *    created: 11.04.2020 04:05:41       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int qq = 1; qq <= tt; qq++) {
    cout << "Case #" << qq << ": ";
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cin >> a[i][j];
      }
    }

    //以下一段用于获取点ij的邻居的坐标
    vector<vector<int>> when(h, vector<int>(w, -1));//记录这个点的删除时间,初始化为-1
    vector<vector<int>> up(h, vector<int>(w));
    vector<vector<int>> down(h, vector<int>(w));
    vector<vector<int>> left(h, vector<int>(w));
    vector<vector<int>> right(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        up[i][j] = i - 1;
        down[i][j] = i + 1;
        left[i][j] = j - 1;
        right[i][j] = j + 1;
      }
    }//0上,1下,2左,3右
    auto GetNeighbor = [&](pair<int, int> p, int dir) {
      if (dir == 0) return make_pair(up[p.first][p.second], p.second);
      if (dir == 1) return make_pair(down[p.first][p.second], p.second);
      if (dir == 2) return make_pair(p.first, left[p.first][p.second]);
      return make_pair(p.first, right[p.first][p.second]);
    };


    long long total = 0;//记录目前舞者level的总和
    vector<pair<int, int>> check;//储存需要check是否变动的舞者坐标
    //第一次check时为所有的点
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        total += a[i][j];
        check.emplace_back(i, j);
      }
    }
    long long ans = total;

    for (int iter = 0; ; iter++) {//不停循环直到无人被删除
      vector<pair<int, int>> rm;//待删除名单
      for (auto& p : check) {
        int sum = 0;
        int cnt = 0;
        for (int dir = 0; dir < 4; dir++) {
          auto q = GetNeighbor(p, dir);//把附近四个邻居找到
          int qi = q.first;
          int qj = q.second;
          if (qi >= 0 && qj >= 0 && qi < h && qj < w) {
            sum += a[qi][qj];
            cnt += 1;
          }
        }
        if (sum > a[p.first][p.second] * cnt) {
          rm.push_back(p);//若小于周围四个的平均值则加入删除列表
        }
      }
      if (rm.empty()) {
        break;//若无人被删除则结束迭代
      }
      for (auto& p : rm) {
        when[p.first][p.second] = iter;//删除时间更新为本轮次
        total -= a[p.first][p.second];//删除本次迭代里被删除的舞者的level
      }
      ans += total;//记录到现在为止的答案总和

      vector<pair<int, int>> new_check;
      for (auto& p : rm) {
        for (int dir = 0; dir < 4; dir++) {
          auto q = GetNeighbor(p, dir);//把被删除者的邻居找到
          int qi = q.first;
          int qj = q.second;
          if (qi >= 0 && qj >= 0 && qi < h && qj < w) {
            if (when[qi][qj] != iter) {//如果它没在本轮被删除或没被遍历过
              new_check.emplace_back(qi, qj);//则加入还留下来的列表里
              when[qi][qj] = iter;//记录为被遍历过
            }
          }
        }
      }
      //若被删除的点的上下左右邻居存在,则更新其周围邻居在它被删除后的新邻居
      //与链表的结点删除类似
      for (auto& p : rm) {
        int i = p.first;
        int j = p.second;
        if (up[i][j] != -1) {
          down[up[i][j]][j] = down[i][j];
        }
        if (down[i][j] != h) {
          up[down[i][j]][j] = up[i][j];
        }
        if (left[i][j] != -1) {
          right[i][left[i][j]] = right[i][j];
        }
        if (right[i][j] != w) {
          left[i][right[i][j]] = left[i][j];
        }
      }
      swap(check, new_check);//更新还留下来的舞者坐标
    }
    cout << ans << '\n';
  }
  return 0;
}




Alier
5个月前

原题:Pascal Walk(含图,需科学上网)

Problem
Pascal’s triangle consists of an infinite number of rows of an increasing number of integers each, arranged in a triangular shape.

Let us define (r, k) as the k-th position from the left in the r-th row, with both r and k counted starting from 1. Then Pascal’s triangle is defined by the following rules:

The r-th row contains r positions (r, 1), (r, 2), …, (r, r).
The numbers at positions (r, 1) and (r, r) are 1, for all r.
The number at position (r, k) is the sum of the numbers at positions (r - 1, k - 1) and (r - 1, k), for all k with 2 ≤ k ≤ r - 1.

In this problem, a Pascal walk is a sequence of s positions (r1, k1), (r2, k2), …, (rs, ks) in Pascal’s triangle that satisfy the following criteria:

r1 = 1 and k1 = 1.
Each subsequent position must be within the triangle and adjacent (in one of the six possible directions) to the previous position. That is, for all i ≥ 1, (ri + 1, ki + 1) must be one of the following that is within the triangle: (ri - 1, ki - 1), (ri - 1, ki), (ri, ki - 1), (ri, ki + 1), (ri + 1, ki), (ri + 1, ki + 1).
No position may be repeated within the sequence. That is, for every i ≠ j, either ri ≠ rj or ki ≠ kj, or both.
Find any Pascal walk of S ≤ 500 positions such that the sum of the numbers in all of the positions it visits is equal to N. It is guaranteed that at least one such walk exists for every N.

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line containing a single integer N.

Output
For each test case, first output a line containing Case #x:, where x is the test case number (starting from 1). Then, output your proposed Pascal walk of length S ≤ 500 using S additional lines. The i-th of these lines must be ri ki where (ri, ki) is the i-th position in the walk. For example, the first line should be 1 1 since the first position for all valid walks is (1, 1). The sum of the numbers at the S positions of your proposed Pascal walk must be exactly N.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.

Test set 1 (Visible Verdict)
1 ≤ N ≤ 501.

Test set 2 (Visible Verdict)
1 ≤ N ≤ 1000.

Test set 3 (Hidden Verdict)
1 ≤ N ≤ 10^9.

Sample

Input

3
1
4
19

Output

Case #1:
1 1
Case #2:
1 1
2 1
2 2
3 3
Case #3:
1 1
2 2
3 2
4 3
5 3
5 2
4 1
3 1

/**
此处tourist用了2的倍数来凑成n(类似二进制表示)
pascal三角形每一行的和是前一行的两倍
**/
/**
 *    author:  tourist
 *    created: 11.04.2020 04:17:10       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int qq = 1; qq <= tt; qq++) {
    cout << "Case #" << qq << ":\n";
    int n;
    cin >> n;
    int rows = min(30, n);//最多使用30行
    n -= rows;//减去每一行最左边的1,用来在每行之间行走
    vector<int> a(rows);//看看每一行是否需要被加上
    for (int row = rows - 1; row >= 0; row--) {
    //从最后一行开始走,若n比该行大,则加上这行所有的和
      if (n >= (1 << row) - 1) {
        a[row] = 1;
        n -= (1 << row) - 1;
      }
    }
    rows += n;//余下的n用来增加行数上的1来凑(即往下走边边)
    a.resize(rows);
    int side = 0;
    for (int row = 0; row < rows; row++) {
      if (a[row] == 1) {//需要加的这一行,
      //若位于左边,则从左往右走,否则从右往左走
        if (side == 0) {
          for (int j = 0; j <= row; j++) {
            cout << row + 1 << " " << j + 1 << '\n';
          }
        } else {
          for (int j = row; j >= 0; j--) {
            cout << row + 1 << " " << j + 1 << '\n';
          }
        }
        side ^= 1;
      } else {//若这行不需要加,则走边边然后跳过
        if (side == 0) {
          cout << row + 1 << " " << 1 << '\n';
        } else {
          cout << row + 1 << " " << row + 1 << '\n';
        }
      }
    }
  }
  return 0;
}




Alier
5个月前

Problem

Many terminals use asterisks (*) to signify “any string”, including the empty string. For example, when listing files matching BASH*, a terminal may list BASH, BASHER and BASHFUL. For *FUL, it may list BEAUTIFUL, AWFUL and BASHFUL. When listing B*L, BASHFUL, BEAUTIFUL and BULL may be listed.

In this problem, formally, a pattern is a string consisting of only uppercase English letters and asterisks (*), and a name is a string consisting of only uppercase English letters. A pattern p matches a name m if there is a way of replacing every asterisk in p with a (possibly empty) string to obtain m. Notice that each asterisk may be replaced by a different string.

Given N patterns, can you find a single name of at most $10^4$ letters that matches all those patterns at once, or report that it cannot be done?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with a single integer N: the number of patterns to simultaneously match. Then, N lines follow, each one containing a single string Pi representing the i-th pattern.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is any name containing at most 104 letters such that each Pi matches y according to the definition above, or * (i.e., just an asterisk) if there is no such name.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 50.
2 ≤ length of Pi ≤ 100, for all i.
Each character of Pi is either an uppercase English letter or an asterisk (*), for all i.
At least one character of Pi is an uppercase English letter, for all i.

Test set 1 (Visible Verdict)
Exactly one character of Pi is an asterisk (*), for all i.
The leftmost character of Pi is the only asterisk (*), for all i.

Test set 2 (Visible Verdict)
Exactly one character of Pi is an asterisk (*), for all i.

Test set 3 (Visible Verdict)
At least one character of Pi is an asterisk (*), for all i.

Sample

Input

2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ

Output

Case #1: COCONUTS
Case #2: *

In Sample Case #1, there are other possible answers, including COCOCONUTS and ILIKECOCONUTS. Neither COCONUTSAREGREAT nor COCOANUTS would be acceptable. Notice that the same pattern may appear more than once within a test case.

In Sample Case #2, there is no acceptable name, so the answer is *.

The following cases could not appear in Test Set 1, but could appear in Test Set 2 or Test Set 3:

4
H*O
HELLO*
*HELLO
HE*
HELLO and HELLOGOODBYEHELLO are examples of acceptable answers. OTHELLO and HELLOO would not be acceptable.

2
CO*DE
J*AM
There is no name that matches both patterns, so the answer would be *.

2
CODE*
*JAM
CODEJAM is one example of an acceptable answer.

The following cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3:

2
A*C*E
*B*D*
ABCDE and ABUNDANCE are among the possible acceptable answers, but BOLDFACE is not.

2
A*C*E
*B*D
There is no name that matches both patterns, so the answer would be *.

2
**Q**
*A*
QUAIL and AQ are among the possible acceptable answers here.

Analysis
Test Set 1
In Test Set 1, each pattern forces our answer to have a certain suffix, and we first need to check whether the patterns introduce conflicting requirements for that suffix.

Consider the letter strings coming after the initial asterisk in each pattern. We can find the longest of those strings (or any longest, if there is a tie); call that string L. Then at least one answer exists if (and only if) every other string is a suffix of L; note that we are considering L itself to be a suffix of L. We can check each other string against L by starting at the ends of both strings and stepping backwards through them in tandem until we find a discrepancy or run out of letters to check. If we ever find a discrepancy, then the case has no answer, but otherwise, we know that L itself is an acceptable answer.

Test Set 2
In Test Set 2, we can divide the patterns into (1) patterns that start with an asterisk, (2) patterns that end with an asterisk, and (3) patterns with an asterisk in the middle.

A type (1) pattern requires the output word to have a certain suffix, just as in Test Set 1. A type (2) pattern requires the output word to have a certain prefix. A type (3) pattern introduces both of these requirements, and we can split it into a suffix requirement and a prefix requirement, and then handle those separately.

Then, we can apply our strategy from Test Set 1 twice: once for the prefix constraints (with the algorithm modified to compare prefixes instead), and once for the suffix constraints. We can concatenate the two results together to obtain a valid answer that is certainly short enough (since it can be at most 99+99 characters long).

Test Set 3
We can generalize the idea above into a solution for Test Set 3. Each pattern p in Test Set 3 also prescribes a prefix of the output word (the prefix of p up to the first asterisk) and a suffix of the output word (the suffix of p starting after the last asterisk). If we allow empty prefixes and suffixes, we get exactly one of each for every pattern. We can handle those in the same way we did for Test Set 2, ending up with a prefix P and a suffix S for the output as long as we do not find a discrepancy in either phase.

However, for patterns that have more than one asterisk, we can also have a middle part, which imposes a new type of requirement. Suppose we parse the parts between the asterisks of a pattern so that X is the prefix up to the first asterisk, Y is the suffix after the last asterisk, and M1, M2, …, Mk are the strings in between the asterisks, in order. After checking that X is a prefix of P and Y is a suffix of S, as before, all that remains to ensure is that the pattern M1*M2*…*Mk is present somewhere within the output word, strictly between P and S.

Let us call M1M2…Mk — that is, the word that occurs in between the first and last asterisks with any other asterisk removed — the middle word. If we make sure a pattern’s middle word occurs in the output word outside of P and S, then we fulfill the extra requirement. We can then build a full valid output then by starting with P, then adding the middle word of every pattern in any order, then appending S. We make sure to correctly handle words with a single asterisk or only consecutive asterisks by making their middle words the empty string. Since each middle word contains at most 98 characters, and the prefix and suffix contain at most 99 characters each, the output built this way has at most 99 × 2 + 50 × 98 characters, which is within the limit of $10^4$ .

/*
主要思路:
以*为分割,把每个string分为前缀,若干个中缀,后缀。
答案的前缀取最长前缀,(因为多出来的部分可以塞到其他的*里)
同理答案的后缀取最长后缀,
中缀随意塞在中间即可。

若前后缀无法互相包含则无解。
*/
/**
 *    author:  tourist
 *    created: 11.04.2020 03:52:40       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  for (int qq = 1; qq <= tt; qq++) {
    cout << "Case #" << qq << ": ";
    int n;
    cin >> n;
    vector<string> strs(n);//用string的vector存下输入
    for (int i = 0; i < n; i++) {
      cin >> strs[i];
    }

    string pref = "";//初始化前缀为空
    string suf = "";//初始化后缀为空
    vector<string> sub;
    bool ok = true;
    for (string& s : strs) {
    //下面先处理前缀,并把后缀扫好
      int last = -1;//上次遇到字母的位置,初始时last为-1
      for (int i = 0; i < (int) s.size(); i++) {//每个string每位遍历
        if (s[i] == '*') {//若该位为*时
          if (last == -1) {//遇到该string的第一个*时
            string other_pref = s.substr(0, i);//提取0到该位之前的前缀
            if (other_pref.size() > pref.size()) {//若该前缀比原先的前缀长就替换
              swap(pref, other_pref);
            }
            if (pref.substr(0, other_pref.size()) != other_pref) {
            //若现有前缀与当前最长前缀不符,则没有符合题意的答案
              ok = false;
              break;
            }
          } else {
            sub.push_back(s.substr(last + 1, i - last - 1));
            //存入从上次遇到*之后,到这次*之前的这段子串
          }
          last = i;//上次遇到字母的位置更新为i
        }
      }
      if (!ok) {
        break;//有冲突时直接break输出不存在
      }

      //开始处理后缀
      string other_suf = s.substr(last + 1);
      //后缀为上一次遇到字母之后到结尾为止的字串
      //提取最长的后缀
      if (other_suf.size() > suf.size()) {
        swap(suf, other_suf);
      }
      //若后缀无法相等,也不存在合适的答案
      if (suf.substr(suf.size() - other_suf.size()) != other_suf) {
        ok = false;
        break;
      }
    }
    if (!ok) {
      cout << "*" << '\n';
    } else {
    //输出前缀+塞在里面的中缀+后缀为答案
      cout << pref;
      for (auto& s : sub) {
        cout << s;
      }
      cout << suf << '\n';
    }
  }
  return 0;
}



Alier
6个月前

原题链接:https://atcoder.jp/contests/abc159/tasks/abc159_f

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const long long mod=998244353;
const int N=3010;
int n,s;
int a[N];
long long dp[N][N][3];//dp[i][s][t],从前i个里选,总和为s,状态为t的方案数
/*
假设某个方案可以满足加起来等于s
它包含在区间[left,right)上,那么每个包含该区间的区间,都含有该方案

状态0:左右端点不作规定
状态1:左端点已确定(的小区间方案数)
状态2:左右端点都已确定(的小区间的方案数)
*/
int main(){
    cin>>n>>s;
    for(int i=0;i<n;i++) cin>>a[i];
    dp[0][0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=s;j++){
            //以下三种状态不选取第i+1个数
            (dp[i+1][j][0] += dp[i][j][0]) %= mod;
            //在前i个里面选,总和为j的方案,必然包含于在前i+1个里选,总和为j的方案
            (dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]) %= mod;
            //不论左端点是否确定,它们都包含在“前i+1个里选,总和为j,左端点确定”的方案内
            (dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) %= mod;
            //前i个里所确定的右端点也不会超出前i+1个里确定的右端点

            if(j + a[i] <= s){
            //以下两种状态选取第i+1个数
                (dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]) %= mod;
                (dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]) %= mod;
                //这里若dp[i][j][2]确定了右端点,则不能选取第i+1个数
            }
        }
    }


    cout<<dp[n][s][2]<<endl;
    return 0;
}
//昏过去




Alier
6个月前

原题链接:https://atcoder.jp/contests/abc159/tasks/abc159_e

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=15,M=1010;
int h,w,k;
int s[N][M];

int main(){
    cin>>h>>w>>k;

    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++) {
            char m;
            cin>>m;
            int e=m-'0';
            s[i][j]=e+s[i-1][j]+s[i][j-1]-s[i-1][j-1];    
            //这题出题人良心,直接把要算的设置成1,不要算的设置成0
        }
    }

    int minsum=h+w-2;
    for(int i=0;i<(1<<(h-1));i++){//枚举横切情况
        vector<int> q;
        q.push_back(0);//记得加第0条边界线,方便统一处理
        int sum=0;

        for(int j=0;j<h-1;j++){
            if(i>>j&1) {
                q.push_back(j+1);
                sum++;
            }
        }
        q.push_back(h);//最外面的边界线,处理最后一个格子和不切的情况

        bool flag=true;
        int lastline=0;
        for(int j=1;j<=w;j++){//贪心纵切
            int wmax=0;
            for(int d=1;d<q.size();d++){
                wmax=max(wmax,s[q[d]][j]-s[q[d]][lastline]-s[q[d-1]][j]+s[q[d-1]][lastline]);
            }
            if(wmax>k){
                if(j==1){
                    flag=false;
                    break;
                }
                sum++;
                lastline=j-1;
            }
        }
        if(!flag) continue;
        minsum=min(minsum,sum);
    }
    cout<<minsum<<endl;
    return 0;
}





Alier
6个月前

https://atcoder.jp/contests/abc158/tasks/abc158_e

#include <cstdio>
using namespace std;
int N,P,cur,t=1,cnt[10010],i;char S[200010];long long ans;
int main()
{
    scanf("%d%d%s",&N,&P,S);
    if(P==2||P==5){
        for(i=0;i<N;i++)if((S[i]-'0')%P==0)ans+=i+1;
    }else{、
    /*
    类似dp
    记录下由s[i]到字符串末尾形成的这个数字%p的余数,如果之前有cnt个串也等于这个余数
    那么相减之后就%p为0,因此ans+=cnt
    */
        cnt[0]=1;
        for(i=N-1;i>=0;i--){
            (cur+=(S[i]-'0')*t)%=P;
            ans+=cnt[cur]++;
            t=t*10%P;
        }
    }
    printf("%lld",ans);
}



Alier
7个月前
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=50;
int in[MAXN],post[MAXN];
int n;

struct node{
    int data;
    node* lchild;
    node* rchild;
};

node* create(int postl,int postr,int inl,int inr){
    if(postl>postr) return NULL;

    node* root= new node;
    root->data=post[postr];

    int x=post[postr];
    int k;
    for(k=inl;k<=inr;k++){
        if(in[k]==x) break;
    }

    int numl=k-inl;

    root->lchild=create(postl,postl+numl-1,inl,k-1);
    root->rchild=create(postl+numl,postr-1,k+1,inr);

    return root;
}

int num=0;
void BFS(node* root){
    queue<node*> q;
    q.push(root);

    while(q.size()){
        node* now=q.front();
        q.pop();

        cout<< now->data ;
        num++;
        if(num<n) cout<<" ";
        if(now->lchild != NULL) q.push(now->lchild);
        if(now->rchild != NULL) q.push(now->rchild);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>post[i];
    for(int i=0;i<n;i++) cin>>in[i];

    node* root=create(0,n-1,0,n-1);

    BFS(root);

    return 0;
}




Alier
7个月前

教小朋友输入一个数,输出这个数读音(两位数以内)的程序,但是小朋友写Python,于是写了个c++然后现查python的语法直接改过去

#include<iostream>
using namespace std;
string a[10]={"","一","二","三","四","五","六","七","八","九"};

int main(){
    int num;
    cin>>num;
    if(num==0){
        cout<<"零"<<endl;
    }else if(num>=10){
        int t=num/10;
        cout<<(t==1?a[0]:a[t])<<"十";
    }
    cout<<a[num%10]<<endl;
    return 0;
}

num=int(input())
ch=["","一","二","三","四","五","六","七","八","九"]
if num==0:
    print("零")
elif num>=10:
    t= num//10
    if(t!=1):
        print(ch[t],end="")
    print("十",end="")
print(ch[num%10])




Alier
7个月前

BASIC-16. 分解质因数
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a, b。
输出格式
每⾏输出⼀个数的分解,形如 $ k=a1 * a2 * a3…(a1<=a2<=a3… $, k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
$ 3=3 $
$ 4=2 * 2 $
$ 5=5 $
$ 6=2 * 3 $
$ 7=7 $
$ 8=2 * 2 * 2 $
$ 9=3 * 3 $
$ 10=2 * 5 $
提示
先筛出所有素数,然后再分解。
【我偏不,参考acwing分解质因数更简便:
https://www.acwing.com/problem/content/869/】
数据规模和约定
2<=a<=b<=10000

#include<iostream>
using namespace std;

void divide(int x){
    cout<<x<<"=";

    bool st=false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            while(x%i==0) {
                if(st){
                    cout<<"*"<<i;
                    x/=i;
                }else{
                    cout<<i;
                    st=true;
                    x/=i;
                }
            }
        }
    }
    if(x>1) {
        if(st) cout<<"*"<<x;
        else cout<<x;
    }
    cout<<endl;
}

int main(){
    int a,b;
    cin>>a>>b;

    for(int i=a;i<=b;i++){
        divide(i);
    }
    return 0;
}



Alier
7个月前

原题

对于长度为5位的一个01串,每一位都可能是0或1,一共有32种可能。它们的前几个是:

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

我的代码

#include<iostream>
using namespace std;

int main(){
    for(int i=0;i<32;i++){
        for(int j=4;j>=0;j--){
            cout<< (i>>j&1);
        }
        cout<<endl;
    }
    return 0;
}

官方题解

#include <iostream>
using namespace std;
int main()
{
    for (int i = 0; i <= 1; ++i)
        for (int j = 0; j <= 1; ++j)
            for (int k = 0; k <= 1; ++k)
                for (int l = 0; l <= 1; ++l)
                    for (int m = 0; m <= 1; ++m)
                        cout << i << j << k << l << m << endl;
    return 0;
}

看到这高射炮我都傻眼了