| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13/14 | O | . | O | O | Ø | O | O | O | O | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给定序列$a_{1…n}$，求$\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_ia_j}$。$1\leq n\leq 10^5,0\leq a_i\leq 10^5$。
解题思路
$\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_ia_j}$
$=\sum_{i=1}^{n}\sum_{j=1}^{n}\sqrt2^{(a_i+a_j)^2-a_i^2-a_j^2}$
$=\sum_{i=0}^{10^5}\sum_{j=0}^{10^5}cnt_icnt_j\sqrt2^{(i+j)^2-i^2-j^2}$
$=\sum_{i=0}^{2\times 10^5}\sqrt2^{i^2}\sum_{j=0}^{10^5}\frac{cnt_j}{\sqrt2^{j^2}}\frac{cnt_{i-j}}{\sqrt2^{(i-j)^2}}$
卷积，$NTT$/拆系数$FFT$即可。
AC代码1 - by nikkukun
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
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = (1 << 20) + 5;
const int INF = 0x3f3f3f3f;
const int SQRT2 = 116195171;
const int INV_SQRT2 = 557219762;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353, G = 3;
ll QPow(ll bas, ll t){
ll ret = 1; bas %= MOD;
while(t){
if(t & 1) ret = ret * bas % MOD;
bas = bas * bas % MOD;
t >>= 1;
}
return ret;
}
ll Inv(ll x){
return QPow(x, MOD-2);
}
void NTT(int w[], int n, int op){
static int r[N];
for(int i=0; i<n; i++)
r[i] = (r[i>>1] >> 1) | ((i&1) ? n>>1 : 0);
for(int i=0; i<n; i++)
if(i < r[i]) swap(w[i], w[r[i]]);
for(int len=2; len<=n; len<<=1){
int sub = len>>1;
ll det = QPow(3, MOD-1 + op * (MOD-1) / len);
for(int l=0; l<n; l+=len){
ll rot = 1;
for(int i=l; i<l+sub; i++){
ll x = w[i];
ll y = rot * w[i+sub] % MOD;
w[i] = (x + y) % MOD;
w[i+sub] = (x - y) % MOD; // maybe minus
rot = rot * det % MOD;
}
}
}
if(op == 1) return;
ll inv = Inv(n);
for(int i=0; i<n; i++)
w[i] = inv * w[i] % MOD;
}
int a[N], cnt[N], b[N];
int main(){
ios::sync_with_stdio(0);
int n; cin >> n;
for(int i=1; i<=n; i++){
cin >> a[i];
cnt[a[i]]++;
}
n = 1e5;
int len = 1;
for(; len<=(n<<1); len<<=1);
for(int i=0; i<=n; i++)
b[i] = QPow(INV_SQRT2, 1LL * i * i) * cnt[i] % MOD;
NTT(b, len, 1);
for(int i=0; i<len; i++)
b[i] = 1LL * b[i] * b[i] % MOD;
NTT(b, len, -1);
ll ans = 0;
for(int i=0; i<len; i++){
ll tmp = 1LL * b[i] * QPow(SQRT2, 1LL * i * i) % MOD;
ans = (ans + tmp) % MOD;
}
cout << (ans + MOD) % MOD;
return 0;
}
AC代码2
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
typedef long long ll;
using namespace std;
struct FFT{
struct comp{
double x,y;
comp():x(0),y(0){}
comp(const double &_x,const double &_y):x(_x),y(_y){}
};
friend comp operator+(const comp &a,const comp &b){
return comp(a.x+b.x,a.y+b.y);
}
friend comp operator-(const comp &a,const comp &b){
return comp(a.x-b.x,a.y-b.y);
}
friend comp operator*(const comp &a,const comp &b){
return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
comp conj(const comp &a){return comp(a.x,-a.y);}
double PI=acos(-1);
comp w[M+5];
int rev[M+5];
int A[M+5],B[M+5],C[M+5],lim,mx,mod=998244353;
void fft(comp *a,int n){
int i,j,k,lyc;
for(i=0;i<n;i++)if(i<rev[i]) swap(a[i],a[rev[i]]);
for(i=2,lyc=n>>1;i<=n;i<<=1,lyc>>=1)
for(j=0;j<n;j+=i){
comp *l=a+j,*r=a+j+(i>>1),*p=w;
for(k=0;k<(i>>1);k++){
comp tmp=*r**p;
*r=*l-tmp,*l=*l+tmp;
++l,++r,p+=lyc;
}
}
}
void fft_prepare(){
int i;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
for(i=0;i<lim;i++)w[i]=comp(cos(2*PI*i/lim),sin(2*PI*i/lim));
}
comp a[M+5],b[M+5],ta[M+5],tb[M+5];
void conv(int *x,int *y,int *z){
int i,j;
for(i=0;i<lim;i++)(x[i]+=mod)%=mod,(y[i]+=mod)%=mod;
for(i=0;i<lim;i++){
ta[i]=comp(x[i]&32767,x[i]>>15);
tb[i]=comp(y[i]&32767,y[i]>>15);
}
fft(ta,lim);fft(tb,lim);
for(i=0;i<lim;i++){
j=(lim-i)%lim;//0的特判
comp da,db,dc,dd;
da=(ta[i]+conj(ta[j]))*comp(0.5,0);
db=(ta[i]-conj(ta[j]))*comp(0,-0.5);
dc=(tb[i]+conj(tb[j]))*comp(0.5,0);
dd=(tb[i]-conj(tb[j]))*comp(0,-0.5);
a[j]=da*dc+da*dd*comp(0,1);
b[j]=db*dc+db*dd*comp(0,1);
}
fft(a,lim);fft(b,lim);
for(i=0;i<lim;i++){
ll da,db,dc,dd;
da=(ll)(a[i].x/lim+0.5)%mod;
db=(ll)(a[i].y/lim+0.5)%mod;
dc=(ll)(b[i].x/lim+0.5)%mod;
dd=(ll)(b[i].y/lim+0.5)%mod;
z[i]=(da+((db+dc)<<15)+(dd<<30))%mod;
}
}
}fft;
struct Quad{
ll w;
struct num{
ll x,y;
};
num mul(num a,num b,ll p){
num ans={0,0};
ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p;
ans.y=((a.x*b.y%p+a.y*b.x%p)%p+p)%p;
return ans;
}
ll powwR(ll a,ll b,ll p){
ll ans=1;
while(b){
if(b&1)ans=1ll*ans%p*a%p;
a=a%p*a%p;
b>>=1;
}
return ans%p;
}
ll powwi(num a,ll b,ll p){
num ans={1,0};
while(b){
if(b&1)ans=mul(ans,a,p);
a=mul(a,a,p);
b>>=1;
}
return ans.x%p;
}
ll solve(ll n,ll p){
n%=p;
if(p==2)return n;
if(powwR(n,(p-1)/2,p)==p-1)return -1;
ll a;
while(1){
a=rand()%p;
w=((a*a%p-n)%p+p)%p;
if(powwR(w,(p-1)/2,p)==p-1)break;
}
num x={a,1};
return powwi(x,(p+1)/2,p);
}
}quad;
int cnt[M],p[M];
ll qp(ll a,ll p,ll mod){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int main(){
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++){
int x;
scanf("%d",&x);
cnt[x]++;
}
const ll mod=998244353;
ll sqrt2=quad.solve(2,mod);
assert(sqrt2!=-1);
for(i=0;i<=2*MAX;i++){
fft.A[i]=cnt[i]*qp(qp(sqrt2,mod-2,mod),1LL*i*i%(mod-1),mod)%mod;
p[i]=qp(sqrt2,1LL*i*i%(mod-1),mod);
}
while((1<<fft.mx)<=MAX*2)fft.mx++;
fft.lim=1<<fft.mx;
fft.fft_prepare();
fft.conv(fft.A,fft.A,fft.C);
ll ans=0;
for(i=0;i<=MAX*2;i++)(ans+=1LL*fft.C[i]*p[i]%mod)%=mod;
printf("%lld",(ans+mod)%mod);
return 0;
}
B
题目描述
解题思路
AC代码
2
C
题目描述
随从有三种，给出数量和性质，问最优最差结果。
解题思路
solved by qxforever
最优剧毒打怪，普通破盾；最差剧毒破盾，模拟一下。
AC代码
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
using namespace std;
const int maxn = 1e3+23;
char s[maxn];
int main()
{
int T;cin>>T;
while(T--){
int n,a,b,c,d;
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);int aa=a,bb=b,cc=c,dd=d;
scanf("%s",s);
int ans=0;
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(dd) dd--,cc++;
else if(cc) continue;
else if(bb) bb--,aa++;
else continue;
}
else{
if(cc) cc--,ans++;
else if(dd) dd--,cc++;
else if(aa) aa--,ans++;
else if(bb) bb--,aa++;
}
}
int mx=ans;ans=0;
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(c) continue;
else if(d) d--,c++;
else if(a) continue;
else if(b) b--,a++;
}
else{
if(d) d--,c++;
else if(c) c--,ans++;
else if(b) b--,a++;
else if(a) a--,ans++;
}
}
printf("%d %d\n",mx,ans);
}
}
D
题目描述
给定$n$个元素的取值范围，求能构成不严格递增序列的方案对应序列总和之和。
解题思路
离散化后，设第$i$个区间为$g_i=[pos_i,pos_{i+1})$。设$f[i][j]$表示前$i$个元素满足取值范围且全为第$[1,j]$个区间中的方案数，$h[i][j]$表示第$i$个元素位于第$j$个区间且前$i$个元素满足取值范围且全为第$[1,j]$个区间中的方案数。有显然$DP$：$h[i][j]=\sum_{k}f[k][j]\times calc(len_j,i-k+1)$，其中$calc(n,m)$表示在长度为$n$的区间中有序选择$m$个元素，使得所选元素组成序列单调不降。通过插板法容易求解$calc(n,m)=C_{n+m-1}^{m}$。
再设$dp[i][j]$表示权值和，类似转移即可。
AC代码
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
typedef long long ll;
using namespace std;
const ll mod=998244353;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
ll c(ll n,ll m){
if(n<0||n<m)return 0;
if(m>n-m)m=n-m;
ll ans=1;
int i;
for(i=0;i<m;i++)ans=ans*(n%mod-i)%mod;
for(i=1;i<=m;i++)ans=ans*qp(i,mod-2)%mod;
return ans;
}
ll Ol[N],Or[N],b[N],l[N],r[N];
ll f[N][N],g[N][N];
int main(){
int i,k,n,tot=0;
ll j;
scanf("%d",&n);
for(i=1;i<=n;i++){
ll pL;
scanf("%lld",&pL);
Or[i]=-pL;
}
for(i=1;i<=n;i++){
ll pR;
scanf("%lld",&pR);
Ol[i]=-pR;
b[tot++]=Ol[i],b[tot++]=Or[i]+1;
}
sort(b,b+tot);tot=unique(b,b+tot)-b;
for(i=1;i<=n;i++){
l[i]=lower_bound(b,b+tot,Ol[i])-b;
r[i]=lower_bound(b,b+tot,Or[i]+1)-b;
}
for(i=0;i<tot;i++)f[0][i]=1;
ll inv2=qp(2,mod-2);
for(i=1;i<=n;i++){
for(j=l[i];j+1<=r[i];j++)
for(k=i;k>=1&&(l[k]<=j&&j+1<=r[k]);k--){
(g[i][j]+= g[k-1][j+1]*c(b[j+1]-b[j]+(i-k),i-k+1)%mod+
f[k-1][j+1]*c(b[j+1]-b[j]+(i-k),i-k+1)%mod*(i-k+1)%mod*(1-b[j+1]%mod-b[j]%mod)%mod*inv2%mod)%=mod;
(f[i][j]+=f[k-1][j+1]*c(b[j+1]-b[j]+(i-k),i-k+1))%=mod;
}
for(j=tot-1;j>=0;j--){
(f[i][j]+=f[i][j+1])%=mod;
(g[i][j]+=g[i][j+1])%=mod;
}
}
printf("%lld",(g[n][0]%mod+mod)%mod);
return 0;
}
E
题目描述
定义$access(x)$操作为，将根和$x$节点路径上所有点的实儿子边全变为虚边，并把路径上的边全变为实边。给定$n$节点、根为$1$的树，初始所有边均为虚边，最多$k$次操作后，求树有多少种可能的形态。
解题思路
$f[i][j]$表示节点$i$子树操作$j$次的形态种数。定义$f[p][0]=1$，$j\neq 0$时进行转移。转移时枚举孩子，钦定必然有某个孩子向上连边，操作总数即为节点操作总数。
$f[p][j]=f[q_1][j_1]\times f[q_2][j_2]\times…\times f[q_k][j_k],\sum_{k}j_k=j$
特殊情况：子树均未和$p$节点连接时，需要多做一次操作，且生成的树与如上所述不同，故单独做贡献。
$f[p][j]=f[q_1][j_1]\times f[q_2][j_2]\times…\times f[q_k][j_k],\sum_{k}j_k=j-1$
复杂度很玄学，通过分别小心维护这两个类似前缀积的东西，可以做到$O(nk^2)$，加了点枚举顺序优化就过了。不知道题解说的$O(nk)$是什么做法。
AC代码
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
typedef long long ll;
using namespace std;
ll f[N][K];
const int mod=998244353;
vector<int>G[N];
void add(int a,int b){
G[a].push_back(b);
G[b].push_back(a);
}
int n,k,sz[N];
void dp(int p){
sz[p]=1;
ll g[K][2];memset(g,0,sizeof(g));
g[0][0]=1;
for(auto q:G[p]){
if(sz[q])continue;
dp(q);
ll h[K][2];memset(h,0,sizeof(h));
for(int j=0;j<=min(sz[p]-1,k);j++){
for(int i=0;i<sz[q]&&i+j<=k;i++){
(h[i+j][0]+=g[j][0]*f[q][i])%=mod;
(h[i+j][1]+=g[j][1]*f[q][i])%=mod;
if(i)(h[i+j][1]+=g[j][0]*f[q][i])%=mod;
else (h[i+j+1][1]+=g[j][0]*f[q][i])%=mod;
}
}
sz[p]+=sz[q];
for(int j=0;j<=min(sz[p]-1,k);j++)g[j][0]=h[j][0],g[j][1]=h[j][1];
/*for(int j=min(sz[p]-1,k);j>=0;j--){
ll temp0=0,temp1=0;
for(int i=0;i<=j&&i<sz[q];i++){
(temp0+=)%=mod;
(temp1+=g[j-i][1]*f[q][i])%=mod;
if(i)(temp1+=g[j-i][0]*f[q][i])%=mod;
else if(j-i-1>=0)(temp1+=g[j-i-1][0]*f[q][i])%=mod;
}
g[j][0]=temp0;
g[j][1]=temp1;
}*/
}
for(int j=2;j<=k&&j<sz[p];j++)(f[p][j]=g[j][1]+g[j-1][0])%=mod;
f[p][0]=1;
f[p][1]=sz[p]-1;
}
int main(){
//freopen("in","r",stdin);
int i,u,v;
scanf("%d%d",&n,&k);
for(i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v);
dp(1);
ll ans=0;
for(i=0;i<=k&&i<=n;i++)(ans+=f[1][i])%=mod;
printf("%lld",(ans+mod)%mod);
return 0;
}
F
题目描述
给一个完全无向图，每个边染黑白色，给一个$O(1)$的判断边黑白的方法，问有多少同色三角形。
解题思路
solved by nikkukun
全部三元组减去两黑一白或两白一黑，枚举两个找第三个即可。
AC代码 - by nikkukun
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
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = 5000 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
int cnt0[N], cnt1[N];
int main(){
ios::sync_with_stdio(0);
int n; cin >> n;
ll a, b, c, p, d;
cin >> a >> b >> c >> p >> d;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++){
ll tmp1 = a * (i + j) % p * (i + j);
ll tmp2 = b * (j - i) % p * (j - i);
ll tmp = (tmp1 + tmp2 + c) % p;
if(tmp > d) cnt1[i]++, cnt1[j]++;
else cnt0[i]++, cnt0[j]++;
}
ll ans = 1LL * n * (n-1) * (n-2) / 6;
ll cnt = 0;
for(int i=1; i<=n; i++)
cnt += 1LL * cnt0[i] * cnt1[i];
ans -= cnt / 2;
cout << ans << endl;
return 0;
}
G
题目描述
给一个单调栈某些位置的”高度“（即以该元素结尾的最长上升序列长度），求一个字典序最小的排列满足这个“高度”。
解题思路
一个显然的结论：未知位置，高度越高越好（如果低了，那么会使得前面元素不得已取一个更大的值）。
从小到大枚举当前高度$h$，维护一个左端已经确定答案的指针$pL$，每次从右往左扫高度为$h$的位置进行赋值即可。
AC代码
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
typedef long long ll;
using namespace std;
int ans[110],a[110];
int main(){
int i,t,n;
scanf("%d",&t);
while(t--){
memset(ans,0,sizeof(ans));
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
int pL=0,pR;
int h=1,cur=1;
while(1){
while(pL<n&&ans[pL])pL++;
if(pL>=n)break;
if(a[pL]==-1)a[pL]=h;
for(pR=n-1;pR>=pL;pR--)if(a[pR]==h)ans[pR]=cur++;
h++;
}
for(i=0;i<n;i++)printf("%d%c",ans[i]," \n"[i==n-1]);
}
return 0;
}
H
题目描述
给序列$a$，定义$f(x)$为有几个$a_i\leq x$。
$q$次询问区间，求$\sum_{i=l}^{r}f(i\oplus x)^2\text{mod 998244353}$。
解题思路
将询问拆为$s(r)-s(l-1)$，则考虑求$s(x)=\sum_{i=0}^{n}f(i\oplus x)^2$。
先考虑$x$最高位（设为$k$位），如果$i$这一位取$0$，那么接下来的所有位可以任取，即$[0,(1<<k)-1]$内的值都可以取到，异或值是一个连续区间，如果$i$这一位取$1$，那么将$k-1$位作为最高位处理即可。
维护一个当前异或值，答案是$\log n$级别的连续区间查询，可以用二分查询。
AC代码 - by nikkukun & Potassium
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
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
struct Data{
ll st, w, sum;
};
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
ll a[N];
vector<Data> pos; // [st, ed)
int BSearch(int x){
int L = 0, R = pos.size();
while(L < R){
int M = (L+R) / 2;
if(pos[M].st <= x) L = M + 1;
else R = M;
}
return L - 1;
}
ll Sum(int n){
int p = BSearch(n);
ll ans = pos[p].sum + 1LL * (n - pos[p].st + 1) * pos[p].w;
return ans % MOD;
}
ll Cal(int n, int x){
if(n<0)return 0;
int now = 0;
ll ret = 0;
for(int i=30; i>=0; i--){
if(n>>i&1){
now^=(x&(1<<i));
(ret+=-Sum(now-1)+Sum(now+(1<<i)-1))%=MOD;
now^=(n&(1<<i));
}else{
now^=x&(1<<i);
}
}
return ret+Sum(now)-Sum(now-1);
}
int main(){
ios::sync_with_stdio(0);
int n, q;
cin >> n >> q;
for(int i=1; i<=n; i++)
cin >> a[i];
sort(a+1, a+n+1);
pos.push_back((Data){-1, 0, 0});
for(int i=1; i<=n; i++){
if(i < n && a[i] == a[i+1]) continue;
auto pre = pos.back();
ll sum = (pre.sum + 1LL * (a[i] - pre.st) * pre.w) % MOD;
pos.push_back((Data){a[i], 1LL * i * i % MOD, sum});
}
while(q--){
int l, r, x;
cin >> l >> r >> x;
ll ans = (Cal(r, x) - Cal(l-1, x)) % MOD;
cout << (ans + MOD) % MOD << endl;
}
return 0;
}
I
题目描述
给一个序列$ {a[1…n]}$，你每次可以选择一个 $i(2\leq i<n)$，然后将$ {a[i-1],a[i],a[i+1]}$全变成 ${max(a[i-1],a[i],a[i+1])}$
你可以进行 ${k}$ 次这样的操作，目标是最大化 $\displaystyle \sum_{i=1}^{n}a[i]$，求最后的答案。
你需要对$ {k=1…n}$都输出答案。
解题思路
最后一定是一堆连续区间。设$f[i][j]$表示到第$i$位，已经合并了$j$次的最大答案。分奇偶性讨论，发现无论如何延伸，长度为$l$的连续区间通过一个元素扩张时都是需要$\lfloor\frac l2\rfloor$次操作的，故枚举这个操作次数进行转移即可。
AC代码
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
typedef long long ll;
using namespace std;
int f[N][N],a[N];
int main(){
int i,j,k,t,n;
scanf("%d",&t);
while(t--){
memset(f,0,sizeof(f));
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
int mx=a[i];
for(j=i-1;j>=0;j--){
for(k=(i-j)/2;k<=i;k++)//(j,i]
f[i][k]=max(f[i][k],f[j][k-(i-j)/2]+mx*(i-j));
mx=max(mx,a[j]);
}
}
for(i=1;i<=n;i++)printf("%d%c",f[n][i]," \n"[i==n]);
}
return 0;
}
J
题目描述
给定$n,k$，求有多少个长度为$n$的排列$p$，$k$为$p$的一个周期。
解题思路
一个周期就是一个环，定义$f[i][j]$表示考虑了前$i$个$n$的因数$d_1…d_i$、考虑了$j$个元素的方案数，转移为
$f[i][j]=f[i-1][j]+\sum_{k}f[i-1][j-k\times d_k]\times calc(n-(j-k\times d_k),k,d_k))$
其中$calc(n,m,d)$表示$n$个元素中选取$m$个长度为$d$的环的方案数，有
$calc(n,m,d)$
$=(d-1)!^m\frac {C_{n}^{n-d}C_{n-d}^{n-2d}\cdots C_{n-(m-1)d}^{n-md}}{m!}$
$=\frac {n!}{(\frac {d!}{(d-1)!})^m m!(n-md)!}$
$=\frac {n!}{d^mm!(n-md)!}$
AC代码
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
typedef long long ll;
using namespace std;
ll f[N][N],k;
const ll mod=998244353;
ll inv[N],fac[N];
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
ll c(int n,int m){
if(n<0||n<m)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll invs[N];
ll get(ll n,ll l,ll m){
assert(n-m*l>=0);
return fac[n]*inv[m]%mod*inv[n-m*l]%mod*qp(invs[l],m)%mod;
}
int main(){
int i,j,l,t,n;
fac[0]=inv[0]=invs[0]=invs[1]=1;
for(i=1;i<=50;i++)fac[i]=fac[i-1]*i%mod,inv[i]=inv[i-1]*qp(i,mod-2)%mod;
for(i=2;i<=50;i++)invs[i]=(mod-mod/i)*invs[mod%i]%mod;
scanf("%d",&t);
while(t--){
scanf("%d%lld",&n,&k);
memset(f,0,sizeof(f));
f[0][0]=1;
int now=0;
for(i=1;i<=n;i++){
if(k%i)continue;
now++;
for(j=0;j<=n;j++){
f[now][j]=f[now-1][j];
for(l=i;l<=j;l+=i){//l/i
(f[now][j]+=f[now-1][j-l]*get(n-(j-l),i,l/i))%=mod;
}
}
}
printf("%lld\n",f[now][n]);
}
return 0;
}
K
题目描述
求一个字典序最小的、所有区间平均数的和尽可能大的$1…n$的排列。
解题思路
大的往中间放，再满足字典序即可。$1357642$
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
using namespace std;
int main(){
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i+=2)printf("%d ",i);
for(i=n/2*2;i>=2;i-=2)printf("%d ",i);
return 0;
}
L
题目描述
给一个棋盘，输出马跳到每个格子最少次数。
解题思路
solved by nikkukun
$BFS$
AC代码 - by nikkukun
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
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = 100 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int dx[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int dy[] = {2, 2, 1, -1, -2, -2, -1, 1};
const int cx[] = {0, 0, 1, 1, 0, 0, -1, -1};
const int cy[] = {1, 1, 0, 0, -1, -1, 0, 0};
int n, m;
int dis[N][N];
char g[N][N];
bool IsLegal(int x, int y){
if(x <= 0 || x > n) return 0;
if(y <= 0 || y > m) return 0;
if(g[x][y] == 'X') return 0;
return 1;
}
void BFS(pint st){
memset(dis, 0x3f, sizeof(dis));
dis[st.fi][st.se] = 0;
queue<pint> q;
q.push(st);
while(!q.empty()){
auto u = q.front(); q.pop();
int x = u.fi, y = u.se;
for(int i=0; i<8; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(!IsLegal(nx, ny)) continue;
int ox = x + cx[i];
int oy = y + cy[i];
if(g[ox][oy] == 'X') continue;
if(dis[nx][ny] > dis[x][y] + 1){
dis[nx][ny] = dis[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin >> n >> m;
pint st;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
cin >> g[i][j];
if(g[i][j] == 'M')
st = make_pair(i, j);
}
BFS(st);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
if(dis[i][j] == INF) cout << -1;
else cout << dis[i][j];
cout << " \n"[j == m];
}
return 0;
}
M
题目描述
神秘模拟题，略。
解题思路
solved by qxforever
依题意模拟即可。
AC代码 - by qxforever
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
using namespace std;
const int maxn = 1e3+23;
int vis[maxn][13],mx[maxn][13];
int ac[13];
int cnt[maxn][13];
int ans[maxn];
int n,m,W;
int main()
{
cin>>n>>m>>W;
while(W--){
int x,y,c;scanf("%d%d%d",&x,&y,&c);
if(c){
if(!vis[x][y]) ac[y]++;
vis[x][y]=1;
mx[x][y]=max(mx[x][y],cnt[x][y]);
cnt[x][y]=0;
}
else{
cnt[x][y]++;mx[x][y]=max(mx[x][y],cnt[x][y]);
}
}
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=m;j++) sum+=vis[i][j]+mx[i][j];
if(sum==0){
ans[i]=998244353;
continue;
}
sum=0;
for(int j=1;j<=m;j++) sum+=vis[i][j];
if(sum==0) {ans[i]=1000000;continue;}
else if(sum==m) continue;
for(int j=1;j<=m;j++){
if(ac[j]&&!vis[i][j]){
ans[i]+=20;
}
if(ac[j]>=n/2&&!vis[i][j]) ans[i]+=10;
ans[i]+=mx[i][j]*mx[i][j]*(1+(!vis[i][j]));
}
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
N
题目描述
有$n$堆石子，第$i$堆有$a_i$个石子。合并两堆相邻石子收益为$a_ia_{i+1}$，合并后变为数量为$a_i+a_{i+1}$的一堆。问最大收益。
解题思路
显然怎么合并都是一样的。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
using namespace std;
ll ans,a[N];
int main(){
int i,j,n;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%lld",&a[i]);
for(i=0;i<n;i++)for(j=i+1;j<n;j++)ans+=a[i]*a[j];
printf("%lld",ans);
return 0;
}