1、进制模拟
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int k;
std::cin >> k;
std::string s, t;
std::cin >> s >> t;
std::reverse(s.begin(), s.end());
std::reverse(t.begin(), t.end());
int n = std::max(s.length(), t.length());
std::vector<int> a(n);
for (int i = 0; i < int(s.length()); i++) {
a[i] += s[i] - '0';
}
for (int i = 0; i < int(t.length()); i++) {
a[i] += t[i] - '0';
}
for (int i = 0; i < n; i++) {
if (a[i] >= k) {
if (i == n - 1) {
a.push_back(0);
n++;
}
a[i + 1]++;
a[i] -= k;
}
}
for (int i = n - 1; i >= 0; i--) {
std::cout << a[i];
}
std::cout << "\n";
return 0;
}#include <bits/stdc++.h>
using namespace std;
//C = A + B
int k;
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int>C;
int t = 0;//进位
for(int i = 0; i < A.size() || i < B.size(); i++)
{
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
C.push_back(t % k);
t /= k;
}
if(t) C.push_back(1);
return C;
}
int main()
{
string a, b;
scanf("%d",&k);
vector<int> A, B;
cin >> a >> b;//a = "123456"
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');//A =[6,5,4,3,2,1];
for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
auto C = add(A, B);
//vector<int>C = add(A,B);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
system("pause");
return 0;
}int k, la, lb;
char a[200005], b[200005], c[200005];
int main() {
cin >> k >> a >> b;
reverse(a, a + strlen(a));
reverse(b, b + strlen(b));
for (int i = 0; a[i] || b[i] || c[i]; i++) {
if (a[i]) c[i] += a[i] - '0';
if (b[i]) c[i] += b[i] - '0';
if (c[i] >= k) c[i] -= k, c[i + 1] += 1;
c[i] += '0';
}
reverse(c, c + strlen(c));
cout << c << endl;
return 0;
}2、+-串模拟 or 规律
纸上写几个例子 注意到 由+ --> - x-=2，由 - ---> + x+=2
真正的模拟
while (T--) { scanf("%s", s + 1); read(k); int n = strlen(s + 1); int a = 0, b = 0; rep(i, 1, n) { if (s[i] == '+') ++a; else ++b; } 这个地方运用了模拟的思想！！ 不用推式子！！ 直接模拟 while (k && abs(a - b) > 1) { if (a > b) --a, ++b; else ++a, --b; --k; } if(abs(a - b) == 1){cout << "1" <<endl;return 0;} if (k) { if (k % 2) print(2, '\n'); else print(0, '\n'); } else { print(abs(a - b), '\n'); } }int balance = 0; for (auto c : s) { if (c == '+') { balance++; } else { balance--; } } balance = std::abs(balance); int t = std::min(balance / 2, k); 这一步妙。自行体会。 balance -= 2 * t; （除了特判都符合这个） if ((k - t) % 2 == 1 && balance == 0) { balance = 2; }（特判） std::cout << balance << "\n"; }
E、骑士
维护第二大的值max2的时候 首先如果max1被更改,max2一定会改；
然后如果a【i】> mx2 也可以更改mx2
即mx2的更改有两条途径
if(a[i]>=mx1){
mx2=mx1;
mx1=a[i];id1=i;
}
else if(a[i]>=mx2){
mx2=a[i];
}前缀后缀max
- 下面这个程序for循环再多只要是并列就是On，下面这个程序是On的
- 前缀后缀用空间换时间O1查询
pre控制i左边的max1，suf控制i右边的max2
void work() {
scan(n);
for(int i = 1; i <= n; ++i) scan(a[i]), scan(b[i]), scan(h[i]);
pre[0] = 0; for(int i = 1; i <= n; ++i) pre[i] = max(pre[i - 1], a[i]);
suf[n + 1] = 0; for(int i = n; i >= 1; --i) suf[i] = max(suf[i + 1], a[i]);
ll ans = 0;
for(int i = 1; i <= n; ++i) {
int mx = max(pre[i - 1], suf[i + 1]); //除了i之外的最大项
if(mx >= b[i] + h[i]) ans += mx - b[i] - h[i] + 1;
}
print(ans, '\n');
}D、删除子序列
有点像dp 形成abc的前提是有ab ab的前提是有a a没有前提为inf
int n, m;
char s[M + 5], t[M + 5];
int cnt[30];
void work() {
scan(n), scan(m);
scanf("%s", s + 1), scanf("%s", t + 1);
memset(cnt, 0, sizeof cnt);
cnt[0] = inf;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(s[i] == t[j]) {
if(cnt[j - 1]) {
--cnt[j - 1];
++cnt[j];
}
}
}
}
print(cnt[m], '\n');
}先读懂题目，别把下标和项弄错。
利用数形结合的思想分析问题。先举例从例子入手分析最普遍的情况，然后再想复杂度最高，最特殊的情况。根据这两种情况设计算法。
将题目数学化。找规律，归纳，分为集合（划分成不同的部分分别处理）。
相等的数看成联通块。不同的情况不同的贡献用一个if else即可
p2[0]=1; for(int i=1;i<N;i++) p2[i]=p2[i-1]*2%mod; for(int i=1;i<=n;i++) { int j=i; while(j<n&&a[j+1]==a[i]) j++; if(i-1>=1&&j+1<=n&&(a[i-1]<a[i]&&a[j+1]>a[i]||a[i-1]>a[i]&&a[j+1]<a[i])) ans=1ll*ans*p2[j-i+1]%mod; else ans=1ll*ans*(p2[j-i+1]+mod-1)%mod; i=j; }思路无敌清晰
void solve() { int n; std::cin >> n; std::vector<int> a(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; } Z ans = 1; std::vector<std::pair<int, int>> b; for (int i = 0, j = 0; i < n; i = j) { j = i; while (j < n && a[i] == a[j]) { j++; } b.emplace_back(a[i], j - i); } for (int i = 0; i < int(b.size()); i++) { if (i == 0 || i == int(b.size()) - 1 || (b[i] > b[i - 1]) == (b[i] > b[i + 1])) { ans *= power(Z(2), b[i].second) - 1; } else { ans *= power(Z(2), b[i].second); } } std::cout << ans.val() << "\n"; }void work() { scan(n); pw[0] = 1; for(int i = 1; i <= n; ++i) scan(a[i]), pw[i] = pw[i - 1] * 2 % mod; r[n] = n; for(int i = n - 1; i; --i) r[i] = (a[i] == a[i + 1] ? r[i + 1] : i); int ans = 1; for(int i = 1; i <= n; i = r[i] + 1) { if(i == 1 || r[i] == n || (a[i - 1] < a[i] && a[r[i]] > a[r[i] + 1]) || (a[i - 1] > a[i] && a[r[i]] < a[r[i] + 1])) { ans = (ll)ans * ((pw[r[i] - i + 1] - 1 + mod) % mod) % mod; } else ans = (ll)ans * pw[r[i] - i + 1] % mod; } print(ans, '\n'); } my shabby version : l[1] = 1; for(int i = 2; i<=n; i++){ if(ar[i] == ar[i - 1])l[i] = l[i - 1]; if else用三木运算符更牛逼 else l[i] = i; } for(int i = n; i >= 1; i = l[i] - 1){ if(i == n || l[i] == 1 || (ar[i] < ar[i + 1] && ar[l[i]] < ar[l[i] - 1] ) || (ar[i] > ar[i + 1] && ar[l[i]] > ar[l[i] - 1] )) ans = (ll)ans * ((pw[i - l[i] + 1] - 1 + mod)%mod)%mod; else{ //(ans *= pw[i - l[i] + 1]%mod)%mod; 必须先乘再% ans = ans * pw[i - l[i] + 1] % mod } }