二分
1010 Radix (25分)
题目的大意是，给你两个数，N1和N2，给定其中一个数的基数，然后求另一个数的基数，使得两个数相等
这题有的地方没有给清楚，感觉有点小问题。给定标签的数不会溢出，而未给定标签的数是会溢出long long的，这点题目没有直接说明，溢出的部分需要用<0去判断。再就是二分的下限取小了，反而WA。
这里主要是对二分法的运用，我自己有个点是没有注意到的就是，求这个数的基数，如何取其上下限。如果这个数大于一位，当这个数最小为10时可以取到最大的基数即这个数的十进制，最小就是其各位的最大数字+1.但是当这个数字只有1位的时候，套用上述的方法显然就会出错，这样取得上限比下限还小，这种情况稍微处理一下就好了。
这会借着还复习了下二分法和快速幂（倍增思想(由于事先知道跳跃步数，采用二进制分解，边计算边跳跃的方式)和分治思想(将问题划分为规模更小的子问题)）
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <map> #include <cmath> #define ll long long #define inf 0x3f3f3f using namespace std; string s1, s2; ll id, radix; ll qpow(ll a, ll n){ ll ans = 1; while(n){ if(n&1) ans *= a; //ans乘上当前的a a *= a; //a自乘 n >>= 1; //n往右移一位 } return ans; } ll handle(string s, ll d){ ll len = s.length(), num; ll sum = 0; for(int i = 0; i < len; i++){ if(s[i]<='9') num = s[i]-'0'; else num = s[i]-'a'+10; sum += num*qpow(d, len-1-i); } return sum; } int main(){ cin >> s1 >> s2 >> id >> radix; if(id==2) swap(s1, s2); //cout << s1 << " " << s2; ll tmp = handle(s1, radix); //二分+快速幂 //char c=*max_element(str.begin(),str.end()); int cnt = -1; for(int i = 0; s2[i]; i++){ if(s2[i]<='9') cnt = max(cnt, s2[i]-'0'); else cnt = max(cnt, s2[i]-'a'+10); } ll l = cnt, r = max(l, tmp)+1; while(r-l>1){ ll mid = (l+r)/2; ll res = handle(s2, mid); if(res>=tmp||res<0) r = mid; else l = mid; } if(handle(s2, r)==tmp) printf("%lld ", r); else printf("Impossible "); }
reference:
https://segmentfault.com/a/1190000037525090
https://blog.csdn.net/CV_Jason/article/details/80993283
https://blog.csdn.net/d891320478/article/details/8303072
https://blog.csdn.net/weixin_30782331/article/details/98610783
1048 Find Coins (25 分)
排序后对于某个a[i]在数列中使用lower_bound查找m-a[i]，不过需要注意：查找的位置应该在i以后，满足相加等于m即是最小的V1
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; int n, m, a[maxn]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+1+n); for(int i = 1; i <= n; i++){ if(a[i]>m/2) break; int x = a[i], y = *lower_bound(a+1, a+1+n, m-a[i]); if(x+y==m) return !printf("%d %d", x, y); } printf("No Solution"); }
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define pii pair<int, int> #define inf 0x3f3f3f3f using namespace std; const int maxn = 1e5+100; int n, m, num, sum[maxn], t, lost; pii sta[maxn]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &num), sum[i] = sum[i-1] + num; sum[n+1] = inf, lost = 1e8; for(int i = 0; i <= n-1; i++){ int head = i+1, tail = lower_bound(sum+1, sum+1+n, sum[i]+m)-sum; if(sum[tail]-sum[head-1]<lost) lost = sum[tail]-sum[head-1], t = 0, sta[++t] = make_pair(head, tail); else if(sum[tail]-sum[head-1]==lost) sta[++t] = make_pair(head, tail); } sort(sta+1, sta+1+t); for(int i = 1; i <= t; i++) printf("%d-%d ", sta[i].first, sta[i].second); }
1085 Perfect Sequence (25 分)
upper_bound的应用，注意细节和数据范围，应当使用long long
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <cmath> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; ll n, p, a[maxn], res; int main(){ scanf("%lld%lld", &n, &p); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a+1, a+1+n); for(int i = 1; i <= n; i++) res = max(res, 1ll*(upper_bound(a+i+1, a+1+n, a[i]*p)-a-i)); printf("%lld", res); }
散列
1078 Hashing (25 分)
Quadratic probing (with positive increments only) is used to solve the collisions.
这句话说的是使用平方探测法来解决哈希冲突，Linear Probing（线性探测法）、Quadratic probing（平方探测法）这种专业术语在平常的学习中应当认真记忆而不是认为不重要，因为这句话一开始看不懂，想当然认不重要就略过了，那结果多半WA。
知道了解决办法之后，需要处理的一个问题就是我们如何知道插入失败？
假设$x<y$，由$h(k) + x^2 = h(k) + y^2 quad (mod p)$得：
$$ x^2 = y^2 quad(mod p)$$
$$ (x-y)(x+y) = 0 quad(mod p)$$
由上述式子推导可发现$p$是一个循环节，如果从$0 sim p-1$进行枚举仍然找不到位置的话即可认为插入失败
这道题要求的是$with positive increments only$，去掉这个限制条件后，以增量序列$1^2, -1^2, 2^2, -2^2 dots, x^2, -x^2$且$x<=p/2$循环试探下一个存储地址即可，证明同上可得（tips:大与2/p的部分可以由p减去小于2/p的部分得到）
还需要注意的一个点：1不是素数，需要在isPrime函数中加以判断
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e6+100; int p, n, tmp; bool vis[maxn]; bool isPrime(int x){ if(x==1) return false; for(int i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } int main(){ scanf("%d%d", &p, &n); while(!isPrime(p)) p++; while(n--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = -1; while(inc<p&&vis[y]) inc++, y = (x+inc*inc)%p; if(inc!=p) printf("%d", y), vis[y] = 1; else printf("-"); if(n) printf(" "); } }
补充资料：
线性探测是按线性方法一个一个找，只要表里有空位总能将元素填入；而二次探测有可能出现表中有空间但平方探测找不到的情况
线性探测容易聚集，二次探测聚集情况较线性探测要好。
二次探测有时候探测不到整个散列表空间，是其一大缺陷。但是经过数学家的研究，散列表长度TableSize是某个4k＋3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间.
Reference:
https://www.icourse163.org/learn/ZJU-93001?tid=1003997005#/learn/content?type=detail&id=1007588520
https://www.nowcoder.com/discuss/67780
https://en.wikipedia.org/wiki/Quadratic_probing
https://blog.csdn.net/qq_37142034/article/details/87903983
https://blog.csdn.net/pennyliang/article/details/5446961
1145 Hashing - Average Search Time (25 分)
这道题相当于1078的扩展，关键在于如何求不在散列表中的元素的平均查找次数。边界值显然为p+1，当查找到已经查找过的单元格后就知道查找失败了；在这个过程中如果发现有空位也能说明该元素不在单元格中
#include <cstdio> using namespace std; const int maxn = 1e6+100; int p, n, m, tmp, h[maxn]; bool vis[maxn]; bool isPrime(int x){ if(x==1) return false; for(int i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } int main(){ scanf("%d%d%d", &p, &n, &m); while(!isPrime(p)) p++; while(n--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = 0; while(vis[y]&&++inc<p) y = (x+inc*inc)%p; if(inc!=p) h[y] = tmp, vis[y] = 1; else printf("%d cannot be inserted. ", tmp); } int cnt = m, sum = 0; while(m--){ scanf("%d", &tmp); int x = tmp%p, y = x, inc = 0; while(h[y]!=tmp&&vis[y]&&++inc<p) y = (x+inc*inc)%p; sum += inc+1; } printf("%.1f", 1.0*sum/cnt); }
1041 Be Unique (20 分)
水题
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; int n, res, a[maxn]; int t, sta[maxn]; int cnt[maxn]; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); if(cnt[a[i]]==0) sta[++t] = a[i]; cnt[a[i]]++; } for(int i = 1; i <= t; i++) if(cnt[sta[i]]==1) return !printf("%d", sta[i]); printf("None"); }
1050 String Subtraction (20 分)
跟那次天梯赛一样，g++不能使用gets(char *)，于是换成getline(cin, str)
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; string s1, s2; bool vis[maxn]; int main(){ getline(cin, s1), getline(cin, s2); int len1 = s1.length(), len2 = s2.length(); for(int i = 0; i < len2; i++) if(!vis[s2[i]]) vis[s2[i]] = 1; for(int i = 0; i < len1; i++) if(!vis[s1[i]]) printf("%c", s1[i]); } //char s1[maxn], s2[maxn]; // gets(s1), gets(s2); // int len1 = strlen(s1), len2 = strlen(s2);
Reference:
https://blog.csdn.net/weixin_41042404/article/details/80934191
1084 Broken Keyboard (20 分)
又是一道水题，不过学到了些英文单词，case insensitive表示不分大小写，capitalized表示大写的
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; string s1, s2; bool vis[maxn]; int main(){ getline(cin, s1), getline(cin, s2); int len1 = s1.length(), len2 = s2.length(); for(int i = 0; i < len2; i++) { if('a'<=s2[i]&&s2[i]<='z') s2[i] += 'A'-'a'; if(vis[s2[i]]) continue; vis[s2[i]] = 1; } for(int i = 0; i < len1; i++){ if('a'<=s1[i]&&s1[i]<='z') s1[i] += 'A'-'a'; if(vis[s1[i]]) continue; printf("%c", s1[i]), vis[s1[i]] = 1; } }
1092 To Buy or Not to Buy (20 分)
水题+1，注意细节
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; string s1, s2; int cnt[maxn]; int main(){ getline(cin, s1), getline(cin, s2); int len1 = s1.length(), len2 = s2.length(); for(int i = 0; i < len2; i++) cnt[s2[i]]++; for(int i = 0; i < len1; i++){ if(cnt[s1[i]]==0) continue; cnt[s1[i]]--; } int tot = 0; for(int i = 0; i < len2; i++) if(cnt[s2[i]]) tot += cnt[s2[i]], cnt[s2[i]] = 0; if(tot) printf("No %d", tot); else printf("Yes %d", len1-len2); }
大整数运算
1023 Have Fun with Numbers (20 分)
模拟大数相加，一发入魂。不过需要注意的是string未初始化的话是不能对某个下标所在的元素直接赋值的，可以参见这里的讨论：C++中string类字符串可以对其中某个下标元素赋值吗？
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; char s[25], res[25]; int cnt[10]; int main(){ scanf("%s", s); int len = strlen(s), carry = 0; for(int i = len-1; i >= 0; i--){ int now = s[i]-'0', tmp = now*2+carry; tmp > 9 ? carry = 1 : carry = 0; res[i] = tmp%10+'0'; cnt[now]++, cnt[tmp%10]--; } bool flag = true; for(int i = 0; i <= 9; i++) if(cnt[i]!=0) { flag = false; break; } if(flag) printf("Yes "); else printf("No "); if(carry) cout << 1; printf("%s", res); }
1024 Palindromic Number (25 分)
仍然是大数模拟，一发就过，关于字符串的翻转可以使用reverse(str.begin(), str.end())和strrev(char *)，详细见C++语言中反转字符串的函数strrev(), reverse()
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100; string s1, s2; int k; int main(){ cin >> s1 >> k; for(int i = 0; i <= k-1; i++){ s2 = s1, reverse(s2.begin(), s2.end()); if(s1==s2) { cout << s1 << endl << i; return 0; } int len = s1.length(), carry = 0; for(int i = len-1; i >= 0; i--){ int now = s1[i]-'0'+s2[i]-'0'+carry; now > 9 ? carry = 1 : carry = 0; s1[i] = now%10+'0'; } if(carry==1) s1 = "1" + s1; } cout << s1 << endl << k; }
思维
1093 Count PAT's (25 分)
利用前缀和计算每个A左右两侧P和T的个数相乘之和即为答案。开始想的是利用P右边A和T的个数来计算，发现这样很麻烦，由于A在中间便换了个计算方式很快就过了。
柳婼的做法是先算出T的个数再去遍历一遍，边计算P和T的个数边计算，这样比我的更加节省空间
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <cmath> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100, mod = 1e9+7; char s[maxn]; ll t, sta[maxn], cp[maxn], ca[maxn], ct[maxn]; int main(){ scanf("%s", s+1); int len = strlen(s+1); for(int i = 1; s[i]; i++){ if(s[i]=='A') sta[++t] = i, ca[i]=ca[i-1]+1, cp[i]=cp[i-1], ct[i]=ct[i-1]; else if(s[i]=='P') cp[i]=cp[i-1]+1, ca[i]=ca[i-1], ct[i]=ct[i-1]; else ct[i]=ct[i-1]+1, ca[i]=ca[i-1], cp[i]=cp[i-1]; } ll sum = 0; for(int i = 1; i <= t; i++) sum = (sum+cp[sta[i]]*(ct[len]-ct[sta[i]]))%mod; printf("%lld", sum); }
1101 Quick Sort (25 分)
distinct positive integers代表不同的正整数，开始没读懂这点导致debug的方向错了，但是要注意这并不是一种排列。由于有这个特性，假如是划分点那么它应该是和排序后的所在位置一样，并且是在包含它的左侧区间中最大的那个数。满足这两个条件便可以是划分点。写完后看了看柳婼的代码，又把自己的代码给优化了下
测试样例2一直格式错误，在网上找了下发现，他要求就算是没有划分点，后面也要输出两个换行，可能是代表空吧
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <cmath> #include <vector> #include <set> #include <map> #include <queue> #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define pii pair<int,int> using namespace std; const int maxn = 1e5+100, mod = 1e9+7; int n, a[maxn], b[maxn], t, sta[maxn], mx[maxn], mn[maxn]; int main(){ scanf("%d", &n); mx[0] = -1, mn[n+1] = inf; for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; for(int i = 1; i <= n; i++) mx[i] = max(a[i], mx[i-1]), mn[n+1-i] = min(a[n+1-i], mn[n+2-i]); sort(b+1, b+1+n); for(int i = 1; i <= n; i++) if(lower_bound(b+1, b+1+n, a[i])-b==i&&a[i]>mx[i-1]&&a[i]<mn[i+1]) sta[++t] = a[i]; printf("%d ", t); if(t==0) printf(" "); for(int i = 1; i <= t; i++) { printf("%d", sta[i]); if(i!=t) printf(" "); } }
#include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e5+100, mod = 1e9+7; int n, a[maxn], b[maxn], t, sta[maxn], mx; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b+1, b+1+n); for(int i = 1; i <= n; i++) { mx = max(mx, a[i]); if(b[i]==a[i]&&a[i]==mx) sta[++t] = a[i]; } printf("%d ", t); if(t==0) printf(" "); for(int i = 1; i <= t; i++) { printf("%d", sta[i]); if(i!=t) printf(" "); } }
Reference: