https://codeforces.com/contest/1326
输出n位数，使得这个数字不能被它含有的单个数字整除
特判掉1，直接输出233-- || 277-- 就可以了，比赛的时候**输出了一个 288--，然后整了半天。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
ll a[MAXN];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
if (n == 1)
pr("-1\n");
else
{
for (int i = 0; i < n - 1; i++)
pr("2");
pr("8\n");
}
}
} 按照题意反着模拟就行了，不过非常容易出错。
题目的意思是 等于数组 a 的前 i-1 项的最大值（x1=0），然后
给你 b 数组，让你求出 a 数组。
所以首先可以确定 a1=b1， 然后迭代的同时，先更新 xi，再算出 ai 即可，理顺了思路就可以很快做出
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
ll b[MAXN],a[MAXN],x[MAXN];
int main()
{
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
sc("%lld", &b[i]);
x[1] = 0;
a[1] = b[1];
for (int i = 2; i <= n; i++)
{
x[i] = max(x[i - 1], a[i - 1]);
a[i] = x[i] + b[i];
}
for (int i = 1; i <= n; i++)
pr("%lld%c", a[i], i == n ? '\n' : ' ');
}
} 将长度为 n 的全排列数组分为 k 段，求每段最大值的和 和 有多少种切分方式使得取到最大值
首先最大值肯定是最大的 k 个数字，考虑将 k 个最大的数字作为 k 段，然后每两端之间的元素就可以随便选，所以累乘一下就可以了。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
const ll mod = 998244353;
ll a[MAXN], pos[MAXN];
int main()
{
ll n, k;
sc("%lld%lld", &n, &k);
ll cnt = 0, ans1 = 0, ans2 = 1;
for (int i = 1; i <= n; i++)
{
sc("%lld", &a[i]);
if (a[i] > n - k)
{
pos[i] = 1;
ans1 += a[i];
}
}
bool f = false;
for (int i = 1; i <= n; i++)
{
if (pos[i] == true)
{
if (f == true)
ans2 = ans2 * (cnt + 1) % mod;
cnt = 0;
f = true;
}
else
cnt++;
}
pr("%lld %lld\n", ans1, ans2);
} D1 - Prefix-Suffix Palindrome (Easy version)
D2 - Prefix-Suffix Palindrome (Hard version)
给你一个字符串，可以选择一个前缀和一个后缀（可以为空），求前缀+后缀，形成的串是回文串的最大长度，并输出最长回文串。
前缀+后缀，所以显然我们可以先将两端相等的字母去掉，因为这些一定在答案中，然后将剩下的字符串拿出来，得到剩下的字符串的包含开头或结尾的最长对称子串就可以了，考虑manacher，在求出了每个点作为中心点的对称半径后，判断一下是否是边界，然后更新答案即可。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e6 + 5;
int r[MAXN];
char s[MAXN];
char a[MAXN];
char aa[MAXN];
void malache(char a[])
{
int ans = 0, f = 0;
int len = strlen(a);
int cnt = 0;
s[cnt++] = '%';
s[cnt++] = '*';
for (int i = 0; i < len; i++)
{
s[cnt++] = a[i];
s[cnt++] = '*';
}
s[cnt++] = '^';
r[0] = 0;
int maxn = 0;
int id = 0;
for (int i = 1; i < cnt - 1; i++)
{
if (i < maxn)
r[i] = min(maxn - i, r[2 * id - i]);
else
r[i] = 1;
while (s[i - r[i]] == s[i + r[i]])
r[i]++;
if (i + r[i] > maxn)
{
maxn = i + r[i];
id = i;
}
if (r[i] > ans && (i + r[i] >= 2 * len + 1 || i - r[i] <= 1))
{
ans = r[i];
f = i;
}
}
for (int i = f - ans + 1; i <= f + ans - 1; i++)
{
if (isalpha(s[i]))
pr("%c", s[i]);
}
}
//index 0 2 4 6 8 10 12
// s % a b c b a ^
// r 0 2 2 6 2 2 0
int main()
{
int T;
sc("%d", &T);
while (T--)
{
sc("%s", a);
int len = strlen(a), cnt = 0;
for (int i = 0; i < len / 2; i++)
{
if (a[i] == a[len - 1 - i])
cnt = i + 1;
else
break;
}
int qq = 0;
for (int i = 0; i < cnt; i++)
pr("%c", a[i]);
for (int i = cnt; i < len - cnt; i++)
aa[qq++] = a[i];
aa[qq] = '\0';
malache(aa);
for (int i = len - cnt; i < len; i++)
pr("%c", a[i]);
pr("\n");
}
} 如果答案为 k 是不行的，那么所以 >=k 的点是可以被删除的，说明从右往左数 第一个 >=k 的点的右边至少有一个炸弹炸掉这个点，第二个 >=k 的点的右边至少有二个炸弹炸掉这个点和上一个点，第 x 个 >=k 的点的右边至少有 x个炸弹炸掉这 x 个点，由于答案是不增的，所以我们每次判断当前答案是否可行，考虑线段树维护即可。（细节待更新）
#include <bits/stdc++.h>
//#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid = (left + right) >> 1;
using namespace std;
const int MAXN = 3e5 + 5;
struct node
{
int maxn;
int mark;
}que[MAXN << 2];
int a[MAXN], n;
void up(int k)
{
que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void down(int k)
{
if (que[k].mark)
{
que[k << 1].mark += que[k].mark;
que[k << 1 | 1].mark += que[k].mark;
que[k << 1].maxn += que[k].mark;
que[k << 1 | 1].maxn += que[k].mark;
que[k].mark = 0;
}
}
void build(int left, int right, int k)
{
que[k].mark = 0;
if (left == right)
{
que[k].maxn = 0;
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void update(int left, int right, int k, int ql, int qr, int val)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].maxn += val;
que[k].mark += val;
return;
}
down(k);
imid;
update(lson, ql, qr, val);
update(rson, ql, qr, val);
up(k);
}
int query(int left, int right, int k, int ql, int qr)
{
if (qr < left || right < ql)
return 0;
if (ql <= left && right <= qr)
return que[k].maxn;
down(k);
imid;
return max(query(lson, ql, qr), query(rson, ql, qr));
}
int q[MAXN];
int pos[MAXN];
int main()
{
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
sc("%d", &a[i]);
pos[a[i]] = i;
}
for (int i = 1; i <= n; i++)
sc("%d", &q[i]);
//build(1, n, 1);
int ans = n;
pr("%d", ans);
update(1, n, 1, 1, pos[n], 1);
for (int i = 1; i < n; i++)
{
update(1, n, 1, 1, q[i], -1);
while (query(1, n, 1, 1, n) <= 0)
{
ans--;
update(1, n, 1, 1, pos[ans], 1);
}
pr(" %d", ans);
}
} 
京公网安备 11010502036488号