PTA团体程序设计天梯赛篇(一)----模拟专题
模拟专题
- 字符串模拟
-
- c++ 常用字符串处理函数
-
- 1. 截取子串
- 2. 替换子串
- 3. 查找子串
- 4、删除字符串
- 5、判断与转换函数
- 6 翻了(替换子串)
- 敲笨钟(字符串查找+字符串替换)
- 估值一亿的AI核心代码(替换+删除+查找)
- 福到了 (字符串+翻转)
- 数学模拟
-
- 特立独行的幸福（模拟+map+素数）
- 多项式除法
- N个数求和
- 矩阵乘法
- 技巧模拟
-
- 天梯赛座位分配 (模拟 + 技巧)
- 倒数第N个字符串(数学知识 + 技巧)
- 秀恩爱分得快
- 其余
-
- 名人堂与代金券(技巧)
- 刮刮彩票
字符串模拟
c++ 常用字符串处理函数
1. 截取子串
s.substr(pos, n) 截取s中从pos开始（包括0）的n个字符的子串，并返回
s.substr(pos) 截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回
2. 替换子串
s.replace(pos, n, s1) 用s1替换s中从pos开始（包括0）的n个字符的子串
3. 查找子串
s.find(s1) 查找s中第一次出现s1的位置，并返回（包括0） s.find(s1 ， p) 从位置p开始查找s中第一次出现s1的位置，并返回（包括0） s.rfind(s1) 查找s中最后次出现s1的位置，并返回（包括0） s.find_first_of(s1)查找在s1中任意一个字符在s中第一次出现的位置，并返回（包括0） s.find_last_of(s1)查找在s1中任意一个字符在s中最后一次出现的位置，并返回（包括0） s.fin_first_not_of(s1) 查找s中第一个不属于s1中的字符的位置，并返回（包括0） s.fin_last_not_of(s1) 查找s中最后一个不属于s1中的字符的位置，并返回（包括0）4、删除字符串
iterator erase(iterator first, iterator last);//删除[first，last）之间的所有字符，返回删除后迭代器的位置
iterator erase(iterator it);//删除it指向的字符，返回删除后迭代器的位置
string &erase(int pos = 0, int n = npos);//删除pos开始的n个字符，返回修改后的字符串
5、判断与转换函数
isdigit：判断是否是数字isalpha：判断是否是字母tolower：大写转化为小写
6 翻了(替换子串)
题目链接
解题思路：这题是练习使用replace函数的 ， 当我们使用该函数替换后，由于原字符的一些片段被替换后，会导致字符串的长度发生变化，因此我们在使用好，切记要与变化后的长度进行相应变化。
代码：
#include #include #include using namespace std;int main() {string s;getline(cin, s);int n = s.size();int p = 0;cout << n << endl;for (int i = 0 ; i < n ; ++i) {if (s[i] == '6') {p = i;int ss = 0;while (s[i] == '6')ss++, i++;cout << ss << " " << p << endl;if (ss > 3 && ss <= 9) {[添加链接描述](https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858880)s.replace(p, ss, "9");i = i - ss + 1; // 在替换之后字符串长度变换那么i对应的位置就需要变化} else if (ss > 9) {s.replace(p, ss, "27");i = i - ss + 2;}}n = s.size();}cout << s << endl;return 0;}敲笨钟(字符串查找+字符串替换)
题目链接
解题思路：
- 对于找有押韵的句子，我们的目标是前后两句的结尾都有ong的句子。那么由于这题的句子格式是固定的，因此我们通过找
ong,判断前一个是否有，ong.则是后一个。 - 对于替换的位置，我们可以从后面开始数空格数，当空格数是第三个的时候的位置为所求，同时当前位置是空格的位置，如果我们直接替换的话，会将空格消去，因此正确位置应该往后加一。
代码：
#include #include using namespace std;string s, ss = "qiao ben zhong.";int main() {int n ;cin >> n;getchar();while (n--) {getline(cin, s);int flag = 0;if (s.find("ong,") != string::npos)flag ++;if (s.find("ong.") != string::npos)flag ++;if (flag == 2) {int pos = s.size() - 1;while (pos--) {if (s[pos] == ' ')flag ++;if (flag == 5)break;}s.replace(pos + 1, s.size() - pos, ss );cout << s << endl;} elsecout << "Skipped\n" ;}return 0;}估值一亿的AI核心代码(替换+删除+查找)
题目链接
解题思路：
这是一个综合性非常强的题目了。对于删除字符来说，我们要灵活运用：iterator erase(iterator it);//删除it指向的字符，返回删除后迭代器的位置 它仅删除指定位置的一个字符。
- 去除首位空格的方法，我们只需要在首部或者尾部，进行删除，直到不是空格就可以了。
- 去除单词之间的多余空格和标点符号前的所有字符：对于两个单词间的，当我们匹配到一个空格之后，开始判断下一个是否是空格，如果是的话删除（循环） ，对于标点符号，由于是前面不能留空格，那么如果我们在进行上面删除多余空格的操作后，如果后边的字符如果不是数字和字母（就是标点符号）那么我们就可以删除当前位置的空格。
- 后面替换操作的注意事项：要注意的是 can you、could you 换成了 can I、could I 后，这里的 I 不能再换成 you 了，所以可以先换成其他字符比如 ‘A’ 。替换是要注意判断它们是不是一个独立的部分，也就是说如果它们包含在两个单词之中，那么它就不能被替换。
代码：
#include using namespace std;typedef long long ll;const int maxn = 1e5 + 5;// 判断是否是独立的部分bool judge(string &s, int x, int l) {if ((x == 0 || (!isdigit(s[x - 1]) && !isalpha(s[x - 1]))) && (x + l == s.length() || (!isdigit(s[x + l]) && !isalpha(s[x + l]))))return true;elsereturn false;}int main() {int T;cin >> T;getchar();while (T--) {string s;getline(cin, s);cout << s << endl;while (s[0] == ' ')s.erase(s.begin()); //去掉开头的空格while (s[s.length() - 1] == ' ')s.erase(s.end() - 1); //去掉结尾的空格for (int i = 0; i < s.length(); i++) {if (s[i] == ' ') {while (s[i + 1] == ' ')s.erase(s.begin() + i + 1); //去掉多余空格if (!isdigit(s[i + 1]) && !isalpha(s[i + 1]))s.erase(s.begin() + i); //去掉标点前的空格}}for (int i = 0; i < s.length(); i++) {if (s[i] != 'I')s[i] = tolower(s[i]);}for (int i = 0;; i++) {i = s.find("can you", i);if (i == -1)break;if (judge(s, i, 7))s.replace(i, 7, "A can");}for (int i = 0;; i++) {i = s.find("could you", i);if (i == -1)break;if (judge(s, i, 9))s.replace(i, 9, "A could");}for (int i = 0;; i++) {i = s.find("I", i);if (i == -1)break;if (judge(s, i, 1))s.replace(i, 1, "you");}for (int i = 0;; i++) {i = s.find("me", i);if (i == -1)break;if (judge(s, i, 2))s.replace(i, 2, "you");}for (int i = 0; i < s.length(); i++) {if (s[i] == '?')s[i] = '!';else if (s[i] == 'A')s[i] = 'I';}cout << "AI: " << s << "\n";}return 0;}福到了 (字符串+翻转)
题目练级
解题思路
- 对于顺时针旋转180度来说，可以先上下翻转，之后左右翻转即可。（本题只是顺时针）。补充：对于逆时针，则是先左右翻转，再上下翻转。
- 对于左右翻转可以利用
reverse函数。
代码：
#include #include #include using namespace std;const int N = 110;string s[N], tp[N];int main() {char ch ;int n;cin >> ch >> n;getchar();for (int i = 0 ; i < n ; ++i)getline(cin, s[i]);for (int i = 0 ; i < n ; ++i )for (int j = 0 ; j < n; ++j)if (s[i][j] == '@')s[i][j] = ch;for (int i = 0 ; i < n ; ++i)tp[i] = s[i];for (int i = 0 ; i < n / 2 ; ++i) // 上下翻转for (int j = 0 ; j < n ; ++j)swap(s[i][j], s[n - i - 1][j]);for (int i = 0 ; i < n ; ++i) // 左右翻转reverse(s[i].begin(), s[i].end());bool flag = true;for (int i = 0 ; i < n ; ++i)if (tp[i] != s[i]) {flag = false;break;}if (flag)cout << "bu yong dao le" << endl;for (int i = 0 ; i < n ; ++i)cout << s[i] << endl;return 0;}数学模拟
特立独行的幸福（模拟+map+素数）
题目链接
解题思路：
- 对于不是幸福数的判断方法就是，在循环的时候出现重复的就不是了。
- 当我们判断完一个数是幸福数之后，我们将其本身和在生成1的过程中产生的数进行记录。如果出现次数为1就是特立独行的幸福数了。
代码：
#includeusing namespace std;#define fir(i,a,n) for(int i=a;i<=n;i++)#define mem(a,x) memset(a,x,sizeof(a));#define pb push_backtypedef long long ll;const int N=1e4+10;int v[N];int l,r;map<int,int>mp,d;void solve(int x){memset(v,0,sizeof(v));int xx=x;while(x!=1){int y=0;while(x){y+=((x%10)*(x%10));x/=10;}x=y;v[x]++;if(v[x]==2) return;//死循环 }x=xx;int t=0;while(x!=1){mp[x]++;int y=0;while(x){y+=((x%10)*(x%10));x/=10;}x=y;t++;}d[xx]=t;}int isp(int x){for(int i=2;i<=sqrt(x);i++){if(x%i==0) return 0;}return 1;}int main(){cin>>l>>r;int ans=0;for(int i=l;i<=r;i++){solve(i);}for(int i=l;i<=r;i++){if(mp[i]==1){cout<<i<<" ";int t=d[i];if(isp(i)) t*=2;cout<<t<<endl;ans++;}}if(!ans) cout<<"SAD";return 0;}多项式除法
题目链接
对于多项式不了解的可以先百度了解一下。对于多项式除法，我们要做的就是将除数的高次幂消掉，直到除数的最高次数小于被除数的。
代码：
#include #include using namespace std;const int N = 1e5 + 10;int n, m, ma, mb; // ma的作用是记录第一个多项式的最高次数。mb同理double a[N], b[N], c[N]; // a中剩余的是余数 ， c中为商int main() {cin >> n;int x, v;for (int i = 1 ; i <= n; ++i) {cin >> x >> v;ma = max(ma, x);a[x] = v;}cin >> m;for (int i = 1; i <= m ; ++i) {cin >> x >> v;mb = max(mb, x);b[x] = v;}int t1 = ma, t2 = mb;while (t1 >= t2) {double t = a[t1] / b[t2];c[t1 - t2] = t;for (int i = t1, j = t2; j >= 0 ; --i, --j)a[i] -= b[j] * t;while (abs(a[t1]) < 0.000001)t1--;}int maxn, cnt = 0;for (int i = 0 ; i <= ma ; ++i)if (abs(c[i]) >= 0.05) {maxn = i;cnt++;}if (cnt) {cout << cnt;for (int i = maxn ; i >= 0 ; --i)if (abs(c[i]) >= 0.05)printf(" %d %.1lf", i, c[i]);cout << endl;} elseprintf("0 0 0.0\n");maxn = 0, cnt = 0;for (int i = 0; i <= mb ; ++i)if (abs(a[i]) >= 0.05) {maxn = i ;cnt++;}if (cnt) {cout << cnt;for (int i = maxn ; i >= 0; --i)if (abs(a[i]) >= 0.05)printf(" %d %.1lf", i, a[i]);cout << endl;} elseprintf("0 0 0.0\n");return 0;}N个数求和
题目链接
解题思路：
对于分式加法我们就是通分后再相加。
- 处理字符部分，一个是我们可以利用scanf的特性可以直接读入。当然也可以当成字符串来处理。
- 这里恶心的是输出的格式，当整数部分为0且小数部分也是0就输出0.如果整数部分不为0，但小数部分为0，则只输出整数部分。
代码：
#include #include #include #include using namespace std;typedef long long LL;const int N = 10010;int n ;LL A, B, L;string s;LL gcd(LL a, LL b) {if (!b)return a;elsereturn gcd(b, a % b);}LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}void simply(LL A, int B) {L = gcd(A, B);A /= L, B /= L;}int main() {cin >> n;A = 0, B = 1;while (n--) {LL a = -1, b, f = 1, st = 0, num = 0;cin >> s;if (s[0] == '-')f *= -1, st = 1;s += " "; // 后面添加一个字符方便结束for (int i = st ; i < (int)s.size() ; ++i) {if (s[i] >= '0' && s[i] <= '9')num = num * 10 + s[i] - '0';else {if (a == -1)a = num;elseb = num;num = 0;}}a *= f;L = lcm(B, b);A = A * L / B + a * L / b;B = L;simply(A, B);}simply(A, B);LL val = A / B ;A %= B;if (val) {if (A)cout << val << " ";elsecout << val << endl;}if (A)cout << A << '/' << B << endl;if (!val && !A)cout << 0 << endl;return 0;}矩阵乘法
题目链接
解题思路
首先我们要理解，为什么需要前一个举证的列数等于后一个矩阵的行数。由矩阵乘法的定义我们知道对于 ，在求解新矩阵某一个位置的值的时候(i,k)，是由其在 前一个矩阵的第i行与后一个矩阵的第k列进行得到，由于这个操作是行中所有元素与列中元素相乘的和得到。因此行中元素需要和列中元素相等。也就前一个矩阵的列数 === 后一个矩阵的行数。
代码:
#include #include #include using namespace std;const int N = 1010;int ra, ca, rb, cb;int a[N][N], b[N][N], c[N][N];int main() {cin >> ra >> ca;for (int i = 1 ; i <= ra ; ++i)for (int j = 1 ; j <= ca ; ++j)cin >> a[i][j];cin >> rb >> cb;for (int i = 1 ; i <= rb ; ++i)for (int j = 1 ; j <= cb ; ++j)cin >> b[i][j];if (ca != rb)cout << "Error: " << ca << " != " << rb << endl;else {for (int i = 1 ; i <= ra ; ++i) {for (int k = 1 ; k <= cb ; ++k) {for (int j = 1 ; j <= ca ; ++j)c[i][k] += a[i][j] * b[j][k];}}cout << ra << " " << cb << endl;for (int i = 1 ; i <= ra ; ++i) {int f = 0;for (int j = 1 ; j <= cb ; ++j) {if (f)cout << " ";cout << c[i][j], f++;}cout << endl;}}return 0;}技巧模拟
天梯赛座位分配 (模拟 + 技巧)
题目链接
解题思路：
由于对于每一个学校来说，队伍是按顺序来排的，因此我们就直接记录每一个学校的总人数（对伍数量 * 10）
之后的关键点是在操作的时候我们用一个数取存上一次操作的学校标号，如果与当前一样就说明只剩下了一个学校了。
代码：
#include #include #include using namespace std;const int N = 4100;int n;struct node {int pos[N];int cnt, tot;} p[N];bool check() {int ans = 0;for (int i = 1 ; i <= n ; ++i)if (p[i].tot == 0)ans++;return ans == n ;}int main() {cin >> n;for (int i = 1 ; i <= n ; ++i) {int x;cin >> x;p[i].tot = x * 10;}int cnt = 0;int last = -1;while (1) {for (int i = 1 ; i <= n ; ++i)if (p[i].tot) {if (i == last)cnt += 2;elsecnt ++;int &x = p[i].cnt;p[i].pos[++x] = cnt;p[i].tot--;last = i ;}if (check())break;}for (int i = 1; i <= n ; ++i) {cout << "#" << i << endl;int f = 0;for (int j = 1 ; j <= p[i].cnt; ++j) {if (f)cout << " ";cout << p[i].pos[j];f++;if (f && f % 10 == 0)cout << endl, f = 0;}if (f)cout << endl;}return 0;}倒数第N个字符串(数学知识 + 技巧)
题目链接
解题思路：
- 由于这个题目是倒数的，所以我们令0位z，25位a ， 也就是 ‘z’- val对应的字符。
- 对于这个题目我们可以发现，对于最后一位是以26为一个周期的，而第二位这就是26*26 ,第三位则是 26 * 26 * 6 … 因此我们可以发现这类似于一个26进制。
- 补充: 如果是顺数的话，我们也是初始化为0，只不过由减法变成加法 ‘a’ + val
代码：
#include #include #include using namespace std;int ans[30];int main() {int L, n;cin >> L >> n;n--;int cnt = 0;while (n) {ans[L - cnt - 1] = n % 26;n /= 26;cnt ++;}for (int i = 0 ; i < L ; ++i) {printf("%c", 'z' - ans[i]);}cout << endl;return 0;}秀恩爱分得快
题目链接
解题思路：
- 为了避免超时我们不能都算，而是先存起来，之后只算与A，B有关的。
- 由于会有-0的情况因此需要用字符串进行读取，之后取正值并对这个值进行标记。
- 对于计算，我们遍历所有的照片，利用
find函数，找是否含有A或B，如果有，对与其异性的值进行计算亲密度，同时记录最大的亲密度。
代码：
#include #include #include #include #include #include #include #include #include #define Mod 19999997typedef long long ll;using namespace std;bool flag[1005];int read() {int input = 0, sign = 0;char a = getchar();while ((a < '0' || a > '9') && a != '-')a = getchar();if (a == '-') {sign = 1;a = getchar();}while (a >= '0' && a <= '9') {input = input * 10 + a - '0';a = getchar();}flag[input] = sign; //女性用true标记return input;}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {memset(flag, false, sizeof(flag));vector<vector<int> >p(n);//存储所有照片vector<double> PA(n, 0.0), PB(n, 0.0);//与A的亲密度，与B的亲密度int coloum;for (int i = 0; i < m; ++i) {scanf("%d", &coloum);p[i].resize(coloum);for (int j = 0; j < coloum; ++j) {p[i][j] = read();}}int A, B;A = read(), B = read();double MAXA = 0.0, MAXB = 0.0;for (int i = 0; i < m; ++i) {bool FindA = find(p[i].begin(), p[i].end(), A) != p[i].end();//查找Abool FindB = find(p[i].begin(), p[i].end(), B) != p[i].end();//查找Bif (FindA || FindB) {for (int j = 0; j < p[i].size(); ++j) {if (FindA && flag[A] != flag[p[i][j]]) { // 有A 且性别不一样PA[p[i][j]] += (double)1.0 / p[i].size();//亲密度累加MAXA = max(MAXA, PA[p[i][j]]);//最大亲密度} else if (FindB && flag[B] != flag[p[i][j]]) {PB[p[i][j]] += (double)1.0 / p[i].size();MAXB = max(MAXB, PB[p[i][j]]);}}}}if (MAXA == PA[B] && MAXB == PB[A]) {//彼此亲密度最高printf("%s%d %s%d\n", flag[A] ? "-" : "", A, flag[B] ? "-" : "", B);} else {for (int i = 0; i < n; i++) {if (PA[i] == MAXA) {printf("%s%d %s%d\n", flag[A] ? "-" : "", A, flag[i] ? "-" : "", i);}}for (int i = 0; i < n; i++) {if (PB[i] == MAXB) {printf("%s%d %s%d\n", flag[B] ? "-" : "", B, flag[i] ? "-" : "", i);}}}}}其余
名人堂与代金券(技巧)
题目链接
解题思路：
这题就是一个自定义排序问题。
对于这题的关键点我认为是在排名上面，解决技巧是我们在排序后对每一个人先标上编号。之后对于值相等的我们将后一个的排名令其与前一个相同。之后在输出的时候，输出排名不大于k的即可。
代码：
#include #include #include #include using namespace std;const int N = 1E4 + 19;struct node {string s;int val, rade;bool operator < (node w) {if (w.val == val)return s < w.s;return val > w.val;}} p[N];int main() {int n, g, k;int sum = 0;cin >> n >> g >> k;for (int i = 0 ; i < n ; ++i) {cin >> p[i].s >> p[i].val;if (p[i].val >= 60 && p[i].val < g)sum += 20;else if (p[i].val >= g && p[i].val <= 100)sum += 50;}sort(p, p + n);cout << sum << endl;for (int i = 0 ; i < n ; ++i)p[i].rade = i + 1;for (int i = 0 ; i < n - 1 ; ++i)if (p[i].val == p[i + 1].val)p[i + 1].rade = p[i].rade;for (int i = 0 ; p[i].rade <= k && i < n ; ++i)cout << p[i].rade << " " << p[i].s << " " << p[i].val << endl;return 0;}刮刮彩票
题目链接
解题思路：
- 对于初始已知的空格真正的值，我们可以记录。如果在读入完后，该数字没有出现过那么就是该值。
- 最后的操作是不管你是否打开都会将和进行累加。
代码：
#include#include#includeusing namespace std;int g[10][10];bool st[10][10] , bk[10];int xx , yy;int money[25] = {0,0,0,0,0,0,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};int main(){ int n = 3; for(int i = 1; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) { int x ; cin>>x; if(!x) st[i][j] = 1 ,xx =i , yy = j; else { g[i][j] = x , bk[x] = 1; } } for(int i = 1; i <= 9 ; ++i)if(!bk[i])g[xx][yy] = i ; for(int i = 1 ; i <= 3 ; ++i){cin>>xx>>yy;st[xx][yy] = 1;cout<<g[xx][yy]<<endl; } int op , ans = 0 ; cin>>op; if(op >= 1 && op <= 3) { for(int j = 1 ; j <= n ; ++j) ans += g[op][j];} else if(op >= 4 && op <= 6) {for(int i = 1 ; i <= 3 ; ++i)ans += g[i][op-3];} else if(op == 7) { for(int i = 1 ; i <= 3 ; ++i) ans += g[i][i];} else for(int i = 1 ; i <= 3 ; ++i) ans += g[i][n-i+1]; cout<<money[ans]<<endl; return 0;}