CF
Problem - 685A - Codeforces
剪枝加暴力
看到\(n,m\le 1e9\)，完全没有想法，看了题解才发现，要保证数字全部不同，最多也只有\(7^7=823543\)，所以可以直接用 \(O(nm)\) 暴力解决
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int cntx, cnty;bool check(int x,int y){vector<int> vis(7);for (int i = 0; i < cntx;i++){vis[x % 7]++;x /= 7;}for (int i = 0; i < cnty;i++){vis[y % 7]++;y /= 7;}for (int i = 0; i <= 6;i++){if(vis[i]>1)return false;}return true;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;n--, m--;for (int i = n; i;i/=7){cntx++;}for (int i = m; i;i/=7){cnty++;}if(cntx+cnty>7){//剪枝，使得时间复杂度可以变成O(nm)cout << 0 << endl;return 0;}cntx = max(cntx, 1);cnty = max(cnty, 1);int ans = 0;for (int i = 0; i <= n;i++){for (int j = 0; j <= m;j++){if(check(i,j)){ans++;}}}cout << ans << endl;
}
Problem - 915C - Codeforces
贪心，先特判，如果a长度小于b，直接输出a的逆序排序
因为题目保证一定有解，所以之后贪心找不大于b的最大解
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int a[30], b[30];
int cnt[20];
string get_min(int x){cnt[x]--;string s1 = to_string(x);for (int i = 0; i <= 9;i++){//贪心，取了一个大值 x之后，尽量取小看看能不能满足<=bfor (int j = 1; j <= cnt[i];j++){s1 += to_string(i);}}cnt[x]++;//注意，这里要加回去return s1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string A, B;cin >> A >> B;int n = A.size(), m = B.size();for (int i=0; i < n;i++){a[i] = A[i] - '0';cnt[a[i]]++;}sort(a, a + n);int len1 = 0;// while(a[len1]==0){// len1++;// }// len1 = n - len1;if(n<m){for (int i = n-1; i>=0;i--){cout << a[i];}return 0;}string ans = "";for (int i = 0; i < n;i++){for (int j = 9; j >= 0;j--){if(cnt[j]==0)continue;if(ans+get_min(j)<=B){ans += to_string(j);cnt[j]--;break;}}}cout << ans << endl;
}
Problem - 1826D - Codeforces
思维好题
动点脑子，看了题目自己猜双指针写半天发现做不了
对于 \(b_l+b_r+b_i−(r−l)\) 式子，求一个 \(pre_l=b_l+l\)，\(suf_r=b_r-r\)
注意，
suf可能为负数，所以 \(suf_{n+1}\) 初始化为最小负数
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;
int pre[N], suf[N];
int a[N];void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= n;i++){pre[i] = max(pre[i - 1], a[i] + i);}suf[n+1] = -1e9;for (int i=n; i >= 1;i--){suf[i] = max(suf[i + 1], a[i] - i);}int ans = 0;for (int i = 2; i <= n - 1;i++){ans = max(ans, a[i] + pre[i-1] + suf[i+1]);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}