A 傻逼题 应该没啥可写的，某人这么说的。
B 神奇的数列 题意 $Hn = \left{\begin{matrix} \Sigma^n {i=1} H{i-1}H {n-i} (n \ge 2) \ 1 (n=0,1) \end{matrix}\right.$ 求 $H_i$ 对 $998244353$ 取模的结果。
题解 离线计算出所有的 $H_i$，打表也行，直接输出即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;#define MAX_N 1000 #define MOD 998244353 unsigned long long h[1003 ];int main () h[0 ]=h[1 ]=1 ; for (int i=2 ;i<=MAX_N;i++) for (int j=1 ;j<=i;j++) h[i]=(h[i]+(h[j-1 ]*h[i-j])%MOD)%MOD; int q; scanf ("%d" ,&q); while (q--) { int n; scanf ("%d" ,&n); printf ("%llu\n" ,h[n]); } return 0 ; }
C 电子对撞 题意 给出两个多项式，最高次分别为 $n,m$，求 $f(x,y)=(\Sigma{i=0}^n a_ix^i)(\Sigma {i=0}^m b_iy^i)$ 对 $10007$ 取模的结果。
题解 直接对每组数据上暴力即可，注意求 $a^i$ 时使用快速幂。 然后 TLE 了。 结果是用秦九韶。
快速幂代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <bits/stdc++.h> using namespace std;#define MOD 10007 int n,m;int a[30004 ],b[30004 ];int quickPow (int a,int b) int t=a; int res=1 ; while (b) { if (b&1 ) res=(res*t)%MOD; t=(t*t)%MOD; b>>=1 ; } return res; } int calc (int *a,int n,int x) int res=0 ; for (int i=0 ;i<=n;i++) res=(res+((a[i]%MOD)*quickPow (x,i))%MOD)%MOD; return res; } int main () scanf ("%d" ,&n); for (int i=0 ;i<=n;i++) scanf ("%d" ,&a[i]); scanf ("%d" ,&m); for (int i=0 ;i<=m;i++) scanf ("%d" ,&b[i]); int q; scanf ("%d" ,&q); while (q--) { int x,y; scanf ("%d %d" ,&x,&y); int res=(calc (a,n,x)*calc (b,m,y))%MOD; printf ("%d\n" ,res); } return 0 ; }
秦九韶代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> using namespace std;#define MOD 10007 int n,m;int a[30004 ],b[30004 ];int calc (int *a,int n,int x) int res=0 ; for (int i=n;i>=0 ;i--) { res=(res*x)%MOD; res=(res+a[i])%MOD; } return res; } int main () scanf ("%d" ,&n); for (int i=0 ;i<=n;i++) scanf ("%d" ,&a[i]); scanf ("%d" ,&m); for (int i=0 ;i<=m;i++) scanf ("%d" ,&b[i]); int q; scanf ("%d" ,&q); while (q--) { int x,y; scanf ("%d %d" ,&x,&y); int res=(calc (a,n,x)*calc (b,m,y))%MOD; printf ("%d\n" ,res); } return 0 ; }
D 新·电子对撞 题意 给出两个多项式，项数为 $n,m$，给出系数 $ai,b_i$ 与指数 $A_i,B_i$ 求 $f(x,y)=(\Sigma {i=0}^n aix^{A_i})+(\Sigma {i=0}^m b_ix^{B_i})$。
题解 直接用结构体把两个多项式放一起，根据指数 sort 然后合并即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include <bits/stdc++.h> using namespace std;int n,m;struct polynomial { long long a; int A; }; polynomial a[200005 ]; bool cmp (polynomial a,polynomial b) return a.A<b.A; } int main () int T; scanf ("%d" ,&T); while (T--) { scanf ("%d" ,&n); for (int i=1 ;i<=n;i++) scanf ("%lld" ,&a[i].a); for (int i=1 ;i<=n;i++) scanf ("%d" ,&a[i].A); scanf ("%d" ,&m); for (int i=1 ;i<=m;i++) scanf ("%lld" ,&a[n+i].a); for (int i=1 ;i<=m;i++) scanf ("%d" ,&a[n+i].A); sort (a+1 ,a+n+m+1 ,cmp); for (int i=1 ;i<=n+m;i++) { if (a[i].a==0 ) continue ; for (int j=i+1 ;j<=n+m;j++) { if (a[i].A==a[j].A) a[i].a+=a[j].a,a[j].a=0 ; else break ; } } int cnt=0 ; for (int i=1 ;i<=n+m;i++) if (a[i].a) cnt++; printf ("%d\n" ,cnt); for (int i=1 ;i<=n+m;i++) if (a[i].a) printf ("%lld " ,a[i].a); puts ("" ); for (int i=1 ;i<=n+m;i++) if (a[i].a) printf ("%d " ,a[i].A); puts ("" ); } return 0 ; }
E 套娃！ 题意 对每个 $a_i$，求数列 ${a_i}$ 中小等于它的数的个数。
题解 暴力循环即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <bits/stdc++.h> using namespace std;int n;int a[1003 ];int main () int T; scanf ("%d" ,&T); while (T--) { scanf ("%d" ,&n); for (int i=1 ;i<=n;i++) scanf ("%d" ,&a[i]); for (int i=1 ;i<=n;i++) { int cnt=0 ; for (int j=1 ;j<=i;j++) if (a[j]<=a[i]) cnt++; printf ("%d " ,cnt); } puts ("" ); } return 0 ; }
F Elemental Creation 题意 给定 $n$，考虑这样的一个式子 $a +$($-$)$b = c (a,b,c \leq n)$，问有多少组有序数对 $(a,b,c)$ 能够满足这个等式。
题解 对于一个确定的 $c$，我们先计算符号为加号的情况。 显然 $a$ 最小为 ，也即 $0+c=c$，然后我们同时让加号左侧加一，右侧减一，得到$1+c-1=c$，以此类推，可以得到 $c+1$ 种情况。 再来考虑符号为减号的情况。同上我们可以得到 $c-0=c$，让减号左侧加一，右侧加一，得到 $c+1-1=c$，可以看出共 $n-c+1$ 种情况。 再知道 $c$ 的取值有 $n+1$ 种，根据乘法原理可知答案为 $(n+1)(n+2)$，注意开 long long 即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std;int main () int T; scanf ("%d" ,&T); while (T--) { long long n; scanf ("%lld" ,&n); printf ("%lld\n" ,(n+1 )*(n+2 )); } return 0 ; }
G Meteor Lights 题意 给出 $n$ 组 $(s_i, d_i)$ 与 $t$，问使得 $t-(s_i+kd_i)$ 最小的 $i$ 与 $s_i+kd_i$。
题解 对于一组 $(s_i, d_i)$，若 $s_i < t$ 则使得 $t-(s_i+kd_i)$ 最小的 $k$ 为 $\left \lfloor \frac{t-s_i}{d_i} \right \rfloor$ 或 $\left \lfloor \frac{t-s_i}{d_i} \right \rfloor + 1$，否则 $k=0$，带入计算即可。
代码 H 蛇的地铁 题意 没看
题解 不知道
代码 没写
I Alea jacta est! 题意 $2^n$ 只猫参加比赛，按顺序两两比赛，$p_i$ 大的获胜，所有获胜的再按顺序比赛，直到只剩一只。问每只猫所遇到的最大 $p_i$。
题解 按题意模拟即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <bits/stdc++.h> #define toat nowat^1 using namespace std;int n,m;int p[300000 ],meet[300000 ];int main () int T; scanf ("%d" ,&T); while (T--) { memset (meet,0 ,sizeof (meet)); scanf ("%d" ,&n); m=1 <<n; for (int i=1 ;i<=m;i++) scanf ("%d" ,&p[i]); queue<int > q[2 ]; int nowat=0 ; for (int i=1 ;i<=m;i++) q[nowat].push (i); for (int i=1 ;i<=n;i++,nowat^=1 ) while (!q[nowat].empty ()) { int a=q[nowat].front (); q[nowat].pop (); int b=q[nowat].front (); q[nowat].pop (); meet[a]=max (meet[a],p[b]); meet[b]=max (meet[b],p[a]); if (p[a]>p[b]) q[toat].push (a); else q[toat].push (b); } for (int i=1 ;i<=m;i++) printf ("%d " ,meet[i]); puts ("" ); } return 0 ; }
J Radiance 题意 给定 $n$，求不大于它的最大回文数。
题解 对于一个数 $n$，所求回文数的位数显然应该与 $n$ 一致（特殊情况 $100 \cdots 0$ 要特判）。
下面考虑一般情况，不难想到从外向内构造所求的回文数。 考虑所求回文数的高位，显然我们应该尽可能让高位（左边）不减。也就说，我们应该让回文数“中间”的部分弥补我们为了高位不减付出的代价，也就是说，让相对靠中间的那些数减小。具体可以预支多少呢？答案是除去靠近中间的全零块外的部分都可以预支，即优先保证高位不减，且对应的低位与高位相同（哪怕让低位变大），而这种行为将会在后面通过减小高位中的较低位来弥补。对于 $x1x_2 \cdots x_my_100 \cdots 0y_2z_mz {m-1} \cdots z_1(y_1^2 + y_2^2 \neq 0)$ 所有的 $z$ 都可以被预支，同时通过（可能）减小 $y_1$ 与较高位的 $z$ 来保证合法性。
在处理 $x$ 时什么时候要预支呢？答案是当对应的 $z$ 小于 $x$ 的时候，因为要让构造的数回文所以要调大 $z$。 那么什么时候可以补偿预支呢？答案是在预支之后，当处理到对应的 $z$ 大于 $x$ 的时候，因为调小较高位的 $z$ 使得我们所构造的数字再次合法了，等同于没有预支。
至此，我们可以看出，答案为 $x1x_2 \cdots x_m y_1’ \cdots y_2’ x_mx {m-1} \cdots x_1(yz \neq 0)$ 问题变成如何确定 $y_1’ \cdots y_2’$。
下面考虑如何构造 $y_1’ \cdots y_2’$。
假设在处理 $y$ 时没有“预支”: 若 $y_1 > y_2$ 答案显然为 $(y_1-1)999 \cdots 9 (y_1-1)$ 若 $y_1 \leq y_2$ 答案显然为 $y_1 00 \cdots 0 y_1$ 假设在处理 $y$ 时有“预支”: 若 $y_1 \ge y_2$ 答案显然为 $(y_1-1)999 \cdots 9 (y_1-1)$ 若 $y_1 < y_2$ 答案显然为 $y_1 00 \cdots 0 y_1$。
至此，我们成功构造出了最大的回文数。
赠送一组测试数据 样例输入 1 2 3 4 5 6 7 8 9 8 320 111000 510006 6 63 1242 100 10101
样例输出 1 2 3 4 5 6 7 8 313 110011 509906 6 55 1221 99 10101
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 #include <bits/stdc++.h> using namespace std;char s[5001 ];int zerol,zeror;bool spj (int st,int ed) if (s[st]!='1' ) return false ; for (int i=st+1 ;i<=ed;i++) if (s[i]!='0' ) return false ; return true ; } void init (int len) int l,r; if (len&1 ) l=r=((len-1 )>>1 ); else r=(len>>1 ),l=r-1 ; while (r<len) { if (s[l]!='0' s[r]!='0' ) break ; else l--,r++; } zerol=l,zeror=r; } int main () int T; scanf ("%d" ,&T); while (T--) { scanf ("%s" ,s); int len=strlen (s); int l=0 ,r=len-1 ; if (len==1 ) { puts (s); continue ; } if (spj (l,r)) { for (int i=1 ;i<len;i++) putchar ('9' ); puts ("" ); continue ; } init (len); int tag=0 ; for (;l<=r;l++,r--) { if (s[l]>s[r]) s[r]=s[l],tag=1 ; if (s[l]<s[r]) s[r]=s[l],tag=0 ; if (l==zerol && r==zeror) { if (tag) { if (s[l]!='0' ) { if (s[l]>=s[r]) { s[l]-=1 ,s[r]=s[l]; for (int i=l+1 ;i<r;i++) s[i]='9' ; } else s[r]=s[l]; } else s[r]='0' ; } else if (s[l]!='0' ) { if (s[l]>s[r]) { s[l]-=1 ,s[r]=s[l]; for (int i=l+1 ;i<r;i++) s[i]='9' ; } else s[r]=s[l]; } else s[r]='0' ; break ; } } puts (s); } return 0 ; }