目錄

T1 RSA

思路：

代碼：

T2:數組操作

思路：

代碼：

T3:A-B數對

?編輯思路：

代碼：

T4:數位計算

?思路：

代碼：

T5:新國王游戲

思路：

代碼：

T6:完美數

思路：

代碼：

T7:Lusir的游戲

思路：

代碼：

T8:BFS練習1

?思路：

代碼：

T9:01序列2

?思路：

代碼：

T10:整除光棍

?思路：

代碼：

---

T1 RSA

思路：

?用map分別存儲A和B的因子和過程中出現數，最后若倆個map均為空則說明這兩個數為質數，當然首先先要判斷這兩個數字是否相等，如果相等那么毫無疑問是no credit，如果不相等的話則為full credit，同時如果map不為空則需要遍歷map，如果有個數map的值大于等于2的話，或者為某個數的平方則輸出no credit，其他的則輸出partial credit。

代碼：

#include<bits/stdc++.h> using namespace std; #define ULL unsigned long long map<int, int >mp; void check(ULL a) {for (ULL i = 2; i <= sqrt(a); i++){if (a % i == 0){mp[i]++;mp[a / i]++;}} } int main() {ULL a, b;cin >> a >> b;check(a);check(b);bool flag = false;if (a == b){cout << "no credit" << endl;return 0;}for (auto i : mp){int x = sqrt(i.first);if (i.second >= 2 || x * x == i.first){flag = true;break;}}if (mp.size() == 0){cout << "full credit" << endl;}else if(flag){cout << "no credit" << endl;}else{cout << "partial credit" << endl;}return 0; }

T2:數組操作

思路：

?很容易知道只能將后面的往前賦值，所有如果要相等的話，則必須是全部和最后一個相等，則我們不妨從后面開始遍歷，用now來表示目前從后遍歷一共有的最后的那個數，用ans來表示一共覆蓋了多少次，如果遇到等于最后一個數的數則now++，如果遇到不等于最后一個的數，則now*=2來表示往前覆蓋now個，并且ans++,最后當now>所包含的數即可

代碼：

#include<bits/stdc++.h> using namespace std; int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin >> t;while (t--){int n; cin >> n;vector<int >V(n);for (int i = n-1; i>=0; i--){cin >> V[i];}int num = V[0], ans = 0, now = 1;while (now<n){if (V[now] == num) {now++;}else{now *= 2;ans++;}}cout << ans <<'\n';}return 0; }

T3:A-B數對

思路：

一道很基礎的雙指針問題，首先對所輸入的數進行排序，用l來指向每一個需要判斷的數字，而r1來尋找a[r1]-a[l]<c最靠右邊的那個數的右邊第一個數，r2則為恰好滿足a[r2]-r[l]>c最靠左邊的那個數，則r2-r1則為l滿足該該數對的總數，同時因為排序后，滿足單調性，則兩指針不需要刷新，且當其中一個指針大于n，或者所有數都判斷完后循環(huán)結束

代碼：

#include<bits/stdc++.h> using namespace std; int n, c; int a[200005]; int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> c;for (int i = 1; i <= n; ++i)cin >> a[i];sort(a + 1, a + 1 + n);long long ans = 0;int r1 = 1;int r2 = 1;for (int l = 1; l <= n; ++l) {while (r1 <= n && a[r1] - a[l] < c)++r1;while (r2 <= n && a[r2] - a[l] <= c)++r2;if (a[r1] - a[l] == c && a[r2 - 1] - a[l] == c)ans += r2 - r1;}cout << ans << endl;return 0; }

T4:數位計算

?思路：

采用遞推，例如對于100以上1000以下的部分可以對其分割為1到9，10到99，100到999分別進行運算后求和，利用等差數列求和公式。

代碼：

#include<bits/stdc++.h> using namespace std; const long long MOD = 998244353; unsigned long long f[19];//f[i]表示大于10^i次方 int main() {unsigned long long n, power = 10, ans = 0;cin >> n;while (true){if (n == 10 && power == 10){ans = 46;break;}else if (power == 10 && n <= power){ans += (n + 1) * n / 2;break;}else if (n > power && power == 10){ans += 45;}else if (n > power && power != 10){unsigned long long x = (power - power / 10) % MOD;unsigned long long y = (power + 1 - power / 10) % MOD;ans += (x * y) / 2 % MOD;}else if (n < power && power != 10){unsigned long long x = (n + 2 - power / 10) % MOD;unsigned long long y = (n + 1 - power / 10) % MOD;ans += (x * y) / 2 % MOD;break;}power *= 10;}cout << ans % MOD << endl;return 0; }

T5:新國王游戲

思路：

首先因為n<=1e6如果挨個遍歷那么時間復雜度為n^2肯定會超時，如果我們仔細觀察可以發(fā)現該求和為(((((b1+0)*a2)+b2)*a3)+b3)*a4.....以此類推，則可以將求和的時間復雜度降低為n，且根據前面觀察可知如果調換其中倆個人的位置u[i]和u[i+1]的話，i前面的是不會受到影響的，但是要確保該排序是最大值的排序就要滿足調換前大于調換后即可，則為b[i]*a[i+1]+b[i+1]>b[i+1]*a[i]+b[i]

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1000000007; const ll maxn=1e6+5; typedef struct {ll a,b; }u; u ar[maxn]; bool cmp(u x,u y) {return x.b*(y.a-1)>y.b*(x.a-1); } int main(void) {ll n,i,ans;scanf("%lld",&n);for(i=0;i<n;i++)scanf("%lld%lld",&ar[i].a,&ar[i].b);sort(ar,ar+n+1,cmp);ans=0;for(i=1;i<=n;i++){ans=(ans*ar[i].a+ar[i].b)%mod;}printf("%lld\n",ans);return 0; }

T6:完美數

思路：

不妨逆向思維與其挨個遍歷，不如設有i個a，n-i個b，只需要滿足a*i+(n-1)*b所得到的數字也為完美數，再通過組合數求解即可?

其中涉及到快速冪，求組合數的方法總結，以及模板如下

const int MOD = 1e9 + 7, N = 1e6 + 10; ll fact[N], infact[N]; ll qmi(int a, int b)//快速冪 {ll res = 1;while (b){if (b & 1) res = res * a % MOD;a = a * (ll)a % MOD;b >>= 1;}return res; } void init() {//正求fact[0] = infact[0] = 1;for (int i = 1; i < N; i++)fact[i] = fact[i - 1] * i % MOD;//反求infact[N - 1] = qmi(fact[N - 1], MOD - 2);for (int i = N - 2; i; i--)infact[i] = infact[i + 1] * (i + 1) % MOD; }int C(int a, int b) {return (fact[a] * infact[b] % MOD * infact[a - b] % MOD) % MOD; }

代碼：

#include<bits/stdc++.h> using namespace std; #define endl '\n'; typedef long long ll; const int MOD = 1e9 + 7, N = 1e6 + 10; ll fact[N], infact[N]; ll qmi(int a, int b)//快速冪 {ll res = 1;while (b){if (b & 1) res = res * a % MOD;a = a * (ll)a % MOD;b >>= 1;}return res; } void init() {//正求fact[0] = infact[0] = 1;for (int i = 1; i < N; i++)fact[i] = fact[i - 1] * i % MOD;//反求infact[N - 1] = qmi(fact[N - 1], MOD - 2);for (int i = N - 2; i; i--)infact[i] = infact[i + 1] * (i + 1) % MOD; }int C(int a, int b) {return (fact[a] * infact[b] % MOD * infact[a - b] % MOD) % MOD; }int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int a, b, m;cin >> a >> b >> m;init();char c = a + '0', d = b + '0';int x;ll res = 0;for (int i = 0; i <= m; i++){x = m - i;ll num = x * a + i * b;bool flag = true;while (num){if (num % 10 != a && num % 10 != b){flag = false;break;}num /= 10;}if (!flag)continue;res = (res + C(m, i)) % MOD;}cout << (res % MOD) << endl;return 0; }

T7:Lusir的游戲

思路：

其實就是一個簡單的二分答案，首先很容易知道要通過只需要滿足大于最高建筑高度即可，則二分答案的有邊界很容易就找到了，?而左邊界既可以是最小值（這道題沒有hank掉部分數據）也可以是0（最好設為0）

代碼：

#include<bits/stdc++.h> using namespace std; int a[100005]; int n; int maxn = -1e9, minn = 1e9; bool check(int x) {for (int i = 1; i <= n; i++){if (a[i] > x){x -= (a[i] - x);}else if(a[i]<=x){x += (x - a[i]);}if (x < 0)return false;if (x >= maxn){return true;}}if (x >= 0)return true; } int main() {cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];maxn = max(a[i], maxn);minn = min(a[i], minn);}int L = minn, R = maxn;while (L<R){int mid = (L + R ) / 2;if (check(mid)){R = mid;}else{L = mid+1;}}cout << L << endl;return 0; }

T8:BFS練習1

?思路：

就是一個簡單的BFS，只不過需要標記走過的路，以免出現重復

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 300050; int a[N], f[N];inline int read() {int x = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x; }void write(int x) {if (x > 9) write(x / 10);putchar(x % 10 | '0'); }int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, num;num = read(), n = read();vector<int>v(n);for (int i = 0; i < n; i++){v[i] = read();a[v[i]] = -1;}queue<int>que;que.push(num);int res = 0;while (!que.empty() && n){int len = que.size();for (int i = 0; i < len; i++){int ans = que.front();que.pop();if (a[ans] == -1){a[ans] = res;n--;}if (ans * 3 < 100050 && f[ans * 3] == 0){que.push(ans * 3);f[ans * 3] = 1;//判斷是否來過減少時間}if (ans * 2 < 100050 && f[ans * 2] == 0){que.push(ans * 2);f[ans * 2] = 1;}if (ans - 1 > 0 && f[ans - 1] == 0){que.push(ans - 1);f[ans - 1] = 1;}if (ans + 1 < 100050 && f[ans + 1] == 0){que.push(ans + 1);f[ans + 1] = 1;}}res++;}for (auto i : v){write(a[i]);putchar(' ');}return 0; }

T9:01序列2

?思路：

排列中一直在變的其實是1的位置，0的位置不重要，我們只要保證兩個1之間有k個0就行，剩下的位置可以隨便排列。那我們就從0枚舉1的數量i，然后剩下的位置全塞0就行，但0的數量最少要有（i-1）* k。為了方便其實我們可以忽略掉0，即把1都挨著，只要我們默認兩個1之間有k個0就行，這樣剩下01串的長度就是n-(i-1) * k，我們只要算在這個長度下，1能有多少種不同的排序即可。前面已經涉及到了組合數這里就不加贅述了

代碼：

#include<bits/stdc++.h> using namespace std; #define LL long long const int MOD = 1e9 + 7,N= 1000005; LL qumi(LL a, int b) {LL ans = 1;while (b){if (b & 1){ans = ans * a % MOD;}a = a * a % MOD;b >>= 1;}return ans; } LL fact[N], infact[N]; void init()//初始化 {fact[0] = infact[0]=1;for (int i = 1; i < N;i++){fact[i] = fact[i - 1] * i % MOD;}infact[N-1] = qumi(fact[N-1], MOD - 2);for (int i = N - 2; i; i--){infact[i] = infact[i + 1] * (i + 1) % MOD;} } LL C(LL a, LL b) {return fact[a] * infact[b] % MOD * infact[a - b]%MOD; } int main() {init();int n, k;cin >> n >> k;int i = 1;LL res = 1;//算上一個1沒有的情況while (i<=n-(i-1)*k){res = (res + C(n - (i - 1) * k, i)) % MOD;i++;}cout << res << endl;return 0; }

T10:整除光棍

?思路：

這是一道模擬題，模擬除法,首先找到大于n的最小光棍，然后再除以n余的數假設為a，則a*10+1,再次除以n直到最后余0為止

代碼：

#include<bits/stdc++.h> using namespace std; int main() {int n; cin >> n;int a = 1,num=1;while (a<n){a = a * 10 + 1;num++;}while (true){cout << a / n;a = a % n;if (a==0){break;}a = a * 10 + 1;num++;}cout <<" " << num << endl;return 0; }

總結

以上是生活随笔為你收集整理的第十六周 DYM 每日一题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。