赛事得分：$100 + 0 + 50 + 30$ 鉴定为史。
T1 Palindrome Basis
题面
原题面 CF1673C
题意
问一个数拆成回文数，有多少种拆分方案。
思路
完全背包。想了一个小时差点没想出来。然后局势就很明朗了。
代码
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
|
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll inf=1e18;
const int N=4e4+10;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll lread(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int dp[N],n;
vector <int> v;
const int P=1e9+7;
void init(){
dp[0]=1;
for(int i=1;i<=9;i++) v.push_back(i);
for(int i=1;i<=9;i++) v.push_back(i*11);
for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) v.push_back(101*i+10*j);
for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) v.push_back(1001*i+110*j);
for(int i=1;i<=9;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) v.push_back(10001*i+1010*j+100*k);
for(auto i:v){
for(int j=i;j<=4e4;j++){
dp[j]=(dp[j]+dp[j-i])%P;
}
}
}
signed main(){
init();
int _=read();while(_--) {int a=read();cout<<dp[a]<<endl;}
return 0;
}
|
T2 Armchairs
题面
原题面 CF1525D
题意
$n$ 把椅子，其中不多于一半有人占着。由 $i$ 换座到 $j$ 代价为 $abs (i-j)$。问所有人都换座到初始没被占的位置代价最小多少。
代码
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
|
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll inf=1e18;
const int N=5e3+10;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll lread(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,val[N],dp[N][N];
int pla[N],plb[N];
int ta,tb;
signed main(){
n=read();for(int i=1;i<=n;i++) val[i]=read();
for(int i=1;i<=n;i++){
if(val[i]) pla[++ta]=i;
else plb[++tb]=i;
}
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<=tb;i++) dp[0][i]=0;
for(int i=1;i<=ta;i++) for(int j=1;j<=tb;j++){
dp[i][j]=min(dp[i-1][j-1]+abs(pla[i]-plb[j]),dp[i][j-1]);
}
cout<<dp[ta][tb]<<endl;
return 0;
}
|
T3 Choosing Capital for Treeland
题面
原题面 CF219D
题意
给一棵树，边有方向，一个节点作为根节点的权值为指向根节点的边数。求所有节点作为根节点的权值。
思路
将以 $u$ 作为根节点的反转答案即为 $dp[u]$ ，对于每条边 $(u,v)$ ，可以通过边的方向确定 $dp[v]$ （$|dp[u]-dp[v]|=1$）。
懒不证明。
代码
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
|
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll inf=1e18;
const int N=2e5+10;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll lread(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n;
vector <pii> G[N];
int vl[N];
int minn=1e9;
vector <int> ve[N];
int dfs1(int u,int fa){
int res=0;
for(auto k:G[u]){
int v=k.first,w=k.second;
if(v==fa) continue;
res+=dfs1(v,u)+w;
}
return res;
}
void dfs2(int u,int fa){
for(auto k:G[u]){
int v=k.first,w=k.second;
if(v==fa) continue;
if(w) vl[v]=vl[u]-1;
else vl[v]=vl[u]+1;
dfs2(v,u);
}
minn=min(minn,vl[u]);
ve[vl[u]].push_back(u);
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
G[u].push_back({v,0});
G[v].push_back({u,1});
}
vl[1]=dfs1(1,1);
dfs2(1,1);
cout<<minn<<endl;
sort(ve[minn].begin(),ve[minn].end());
for(auto i:ve[minn]) cout<<i<<" ";cout<<endl;
return 0;
}
|
T4 Kaavi and Magic Spell
题面
原题面 CF1336C
题意
给定字符串 $T$ 和 $S$ 。有个空字符 $A$ ，每次可以把 $S$ 的首字母插入 $A$ 的开头或者结尾后删除，最多操作|S|次。求有多少种方案使得 $T$ 是 $A$ 的前缀。
代码
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
|
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll inf=1e18;
const int N=5e3+10;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline ll lread(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int P=998244353;
int dp[N][N];
signed main(){
string t,s; cin>>s>>t;
int n,m; n=s.length(),m=t.length();
s="?"+s,t="?"+t;
for(int i=1;i<=n;i++) dp[i][i]=(i>m||s[1]==t[i])*2;
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
if(l>m||s[len]==t[l]) dp[l][r]+=dp[l+1][r],dp[l][r]%=P;
if(r>m||s[len]==t[r]) dp[l][r]+=dp[l][r-1],dp[l][r]%=P;
}
}
int ans=0;
for(int i=m;i<=n;i++) ans+=dp[1][i],ans%=P;
cout<<ans<<endl;
return 0;
}
|
