Noip2016 六校模拟 AHSDFZ Round 2
A. 数数
小Star还不会数。有一天 他看到了一张奇怪的数表，上面每个数各自都由相同数字构成，比如“11111111”“66666”。于是他想自己从1慢数到这个数字。Star有个很不好的习惯， 每数到一定个就会从头开始数起。现在请你帮忙求出，他最后数出来的数是多少。
对于30%的数据，$Q \leq 100, p \leq 10^4, n \leq 10^4$；
对于60%的数据，$Q \leq 1000, p \leq 10^4, n \leq 10^9$；
对于额外20%的数据，$Q \leq 10^5, p \leq 10^8, n \leq 10^{18}$，$p$为质数；
对于100%的数据，$Q \leq 10^5, p \leq 10^8, n \leq 10^{18}, 1 \leq x \leq 9$。
【题解】可以发现一些奇怪的特性来构造这个数列
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;
int Q;
int x, p;
ll n;
ll pwr(ll x, ll y, ll mod) {
ll ret = 1ll;
while(y) {
if(y&1) ret = ret * x % mod;
x = x*x % mod;
y >>= 1;
}
return ret;
}
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
scanf("%d", &Q);
while(Q--) {
scanf("%d%lld%d", &x, &n, &p);
ll base = pwr(10ll, n, p*9);
-- base;
if(base < 0) base += p*9;
base = base / 9 * x;
base = base % p;
printf("%lld\n", base);
}
return 0;
}
B.破解石碑
相传在上古时期留下了许多块神秘的石碑， 石碑的正面按顺序刻上$n$个数字，并且每个数字的下方都有一个字号较小的数相对应。研究人员把上面的数字称为$A$列，下面的数字称为$B$列。在查阅古书后人们得知，每块石碑其实都是一把锁 。如果人们在石碑上按合适的方法对数字进行操作 ，就会获得巨大的能量。 操作的规则如下：
若$A_i$和$A_{i+1}$不互 质，我们可以在原石碑中抹去第$i$和第$i + 1$个数（包括$A$中和$B$中），然后将两个序列重新按顺序编号。
假如最终$B$列中被抹去的数和达到可能的最大值，这把巨锁就解开了。由于对石碑上数字的抹去是不可逆，为了不浪费每块石碑，我们必须事先计算出每块石碑的操作方案并获得 $B$列被删去的可能最大和。
对于30%的数据，$n \leq 20$；
对于60%的数据，$n \leq 100$；
对于80%的数据，$n \leq 500$；
对于100%的数据，$n \leq 800, 1 \leq A_i, B_i \leq 10^9$。
【题解】直接区间dp即可。
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 810;
ll f[M][M];
int a[M], b[M], n;
ll s[M];
int main() {
freopen("stele.in", "r", stdin);
freopen("stele.out", "w", stdout);
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
for (int i=1; i<=n; ++i) scanf("%d", &b[i]), s[i] = s[i-1] + b[i];
for (int len=1; len<n; ++len)
for (int i=1; i+len<=n; ++i) {
int j=i+len;
if(f[i+1][j-1] == s[j-1] - s[i] && __gcd(a[j], a[i]) > 1) f[i][j] = s[j] - s[i-1];
else {
for (int k=i; k<j; ++k)
f[i][j] = max(f[i][j], f[i][k] + f[k+1][j]);
}
}
printf("%lld\n", f[1][n]);
return 0;
}
C.宏操作
在计算机程序设计中，定义宏是一种非常重要的简化代码的手段。一般说来，宏是一种规则或模式称语法替换用于说明某特定输入（通常字符串）如何根据预定义的规则转换成对应输出（通常也是字)。但是，过量的宏嵌套往使得代码逻辑复杂，难以理解。
某天，Star定义了一系列的宏来对数组$A$进行操作，这些宏具有这样的结构：
1. 加法宏：给定$i,k$，执行$A[i] = A[i] + k$；
2. 乘法宏：给定$k$，对任意$i$执行 $A[i] = A[i] \times k $；
3. 复合宏：给定$i,j$，先执行第$i$个宏，再执行第$j$个宏。
最后Star发现，自己定义的宏在逻辑上恰好形成了一棵没有度为1的结点的二叉树，其中叶子结点为加法或乘的基本宏 。
Star的$A$数组大小为$n$，共有$m$个基本宏、$m-1$个复合宏 。程序中共 调 用了$q$次宏 。Star的编译器被绕晕了已经罢工，现在请你帮忙计算出程序运行之后数组中每个元素的结果（假定对数组元素的修改操作都会自动在模 998244353的同余系下进行。）
对于30%的数据 ，$n \leq 100,~m,q \leq 200$；
对于60%的数据 ，$n \leq 100,~m \leq 10000,~q \leq 20000$；
对于80%的数据 ，$m \leq 10000,~q \times n \leq 2000000$；
对于100%的数据 ，$n, m, q \leq 100000$，基本宏中的$k$均为不超过10000的正整数；
有50%的数据散落在所有数据中，满足基本宏均为加法。
【题解】（90分）对于50%线段树，其他暴力，待填坑
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;
/* ============ define "define" ============ */
int type[M], pos[M], del[M];
int lc[M], rc[M], rt[M], root;
int leaf[M], segpos[M], lnum, l[M], r[M];
// segpos[i]: 线段树中[i,i]区间表示实际的基本宏
// leaf[i]: 实际的基本宏代表的线段树区间
int n, m, q;
int leafnum = 0;
ll tag[M], a[M];
const ll mod = 998244353;
inline void build(int x) {
if(!lc[x] && !rc[x]) {
leaf[x] = ++leafnum;
segpos[leafnum] = x;
l[x] = leafnum, r[x] = leafnum;
return ;
}
if(lc[x]) build(lc[x]);
if(rc[x]) build(rc[x]);
l[x] = l[lc[x]];
r[x] = r[rc[x]];
}
inline void add(int x, int L, int R) {
// printf("%d left = %d, right = %d, L = %d, R = %d\n", x, l[x], r[x], L, R);
if(L == l[x] && r[x] == R) {
tag[x] ++;
if(tag[x] >= mod) tag[x] -= mod;
return ;
}
int mid = (l[x]+r[x])>>1;
if(lc[x] != 0 && R <= r[lc[x]]) {
add(lc[x], L, R);
}
if(lc[x] != 0 && L >= l[rc[x]]) {
add(rc[x], L, R);
}
}
inline ll query(int x, int pos) {
if(l[x] == r[x]) return tag[x];
if(pos <= r[lc[x]]) return query(lc[x], pos) + tag[x];
if(pos >= l[rc[x]]) return query(rc[x], pos) + tag[x];
}
inline void putforward(int x) {
// printf("%d %d %d\n", x, lc[x], rc[x]);
// system("pause");
if(!lc[x] && !rc[x]) {
if(type[x] == 1) a[pos[x]] += del[x], a[pos[x]] %= mod;
else {
for (int i=1; i<=n; ++i) a[i] *= del[x], a[i] %= mod;
}
return ;
}
if(lc[x]) putforward(lc[x]);
if(rc[x]) putforward(rc[x]);
}
int main() {
freopen("macro.in", "r", stdin);
freopen("macro.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
bool all = 1;
for (int i=1; i<=m; ++i) {
scanf("%d", &type[i]), all &= (type[i] == 1), rt[i] = 1;
if(type[i] == 1) scanf("%d%d", &pos[i], &del[i]);
else scanf("%d", &del[i]);
}
for (int i=1; i<m; ++i)
scanf("%d%d", &lc[i+m], &rc[i+m]), type[i+m] = 3, rt[lc[i+m]] = 1, rt[rc[i+m]] = 1;
for (int i=1; i<=m+m-1; ++i)
if(!rt[i]) {
root = i;
break;
}
if(all) {
// printf("%d\n", root);
build(root);
while(q--) {
int pos; scanf("%d", &pos);
// printf("%d %d\n", l[pos], r[pos]);
add(root, l[pos], r[pos]);
}
for (int i=1; i<=m; ++i) {
ll act = query(root, leaf[i]);
// printf("%lld\n", act);
a[pos[i]] += act * del[i] % mod;
a[pos[i]] %= mod;
}
for (int i=1; i<=n; ++i) printf("%lld ", a[i]);
puts("");
return 0;
}
while(q--) {
int pos;
scanf("%d", &pos);
// printf("%d %d %d\n", pos, lc[pos], rc[pos]);
putforward(pos);
}
for (int i=1; i<=n; ++i) printf("%lld ", a[i]%mod);
return 0;
}
2022年9月18日 15:53
Uttar Pradesh State Basic School Education Board (Basic Shiksha Mandal) and others have designed and suggested UP Board 5th Class Model Paper 2023 with Mock Test and Practice Questions for Term1 & Term 2 Exams of the Course All Languages and Subjects of the Course for SCERT & NCERT Syllabus. UP Board Question Paper Class 5 All District Students of Uttar Pradesh Hindi Medium, English Medium and Urdu Medium Can download the UP Board STD-5 Question Paper 2023 Pdf with Suggested Answers for all exams of the course, and its supports to all 4th Standard Primary School Students Studding in Government & Private Schools of the State & Central Board.