A. 几何
设 \(f_{i,j,k}\) 表示前 \(i\) 个字符，分为两部分，分别为 \(x\) 的几倍加 \(x\) 的前 \(j\) 位，\(y\) 的几倍加 \(y\) 的前 \(k\) 位,是否合法
分别判断下一位 \(i+1\) 能否与 \(x\) 的下一位 \(j+1\) 和 \(y\) 的下一位 \(k+1\) 匹配，匹配上了就转移.
最终答案就是 \(f_{|s|,0,0},f_{|s|,0,|y|},f_{|s|,|x|,0},f_{|s|,|x|,|y|}\) 有一个是1就是 \(Yes\) ，要用 \(bitset\) 优化，我三目运算符卡过去的
点击查看代码
#include<bits/stdc++.h>
//const int maxn=5e5+10;
using namespace std;
int t,cnt,len1,len2,len3;
bool f[2][51][51];
string s,x,y;
int main()
{
ios::sync_with_stdio(0);
freopen("geometry.in","r",stdin);
freopen("geometry.out","w",stdout);
cin>>t;
while(t--)
{
cin>>s>>x>>y;
len1=s.size();len2=x.size();len3=y.size();
s=" "+s,x=" "+x,y=" "+y;
memset(f,0,sizeof f);
f[1][1][0]=s[1]==x[1]?1:0;
f[1][0][1]=s[1]==y[1]?1:0;
for(int i=1;i<=len1;++i)
{
memset(f[i+1&1],0,sizeof f[i+1&1]);
for(int j=0;j<=len2;++j)
{
for(int k=0;k<=len3;++k)
{
j==len2?
f[i+1&1][1][k]|=s[i+1]==x[1]?f[i&1][j][k]:f[i+1&1][1][k]
:f[i+1&1][j+1][k]|=s[i+1]==x[j+1]?f[i&1][j][k]:f[i+1&1][j+1][k];
k==len3?
f[i+1&1][j][1]|=s[i+1]==y[1]?f[i&1][j][k]:f[i+1&1][j][1]
:f[i+1&1][j][k+1]|=s[i+1]==y[k+1]?f[i&1][j][k]:f[i+1&1][j][k+1];
// cout<<f[i][j][k]<<endl;
}
}
}
if(f[len1&1][len2][len3]||f[len1&1][0][0]||f[len1&1][len2][0]||f[len1&1][0][len3]) cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
return 0;
}
/*
2
ababcd
abc
abd
abcdef
abc
cde
*/
B. 分析
树形 \(dp\)，每一次移动只会改变首尾的点度数奇偶性，而每一个奇数点就要多进行一次瞬移操作,而每一次回复一条边
相当于加了一条边，改变了两个点的度数，所以我们考虑每一条边是否再加一条边，然后统计瞬移次数，让代价最小
设 \(f_{u,0/1,0/1}\) 表示以 \(u\) 为根的子树 \(u\) 是不是奇数度数点，除去 \(u\) 后子树内有没有度数奇数的点
加一条边的话，再算上考虑新合并的子节点与父节点之间的边，就是相当于加了两条边，度数奇偶不变，代价加 \(A\)
不加的话，就是只新有了父子之间本来的边，度数改变，再考虑原来父子度数奇偶，两奇的话相当于少了一次瞬移
俩偶的话相当于多了一次瞬移，一奇一偶相当于没变
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=5e5+10;
using namespace std;
int A,B,n;
int head[maxn],to[maxn<<1],nxt[maxn<<1],tot,f[maxn][2][2],ans;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void addm(int x,int y)
{
add(x,y),add(y,x);
}
void lsx(int x,int fa)
{
int a[2][2];
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
f[x][j][k]=1e15;
}
}
f[x][0][0]=0;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
lsx(y,x);
// memset(a,0,sizeof a);
for(int j=0;j<=1;j++)
{
for(int k=0;k<=1;k++)
{
a[j][k]=f[x][j][k];
f[x][j][k]=1e15;
}
}
for(int j1=0;j1<=1;j1++)
{
for(int j2=0;j2<=1;j2++)
{
for(int k1=0;k1<=1;k1++)
{
for(int k2=0;k2<=1;k2++)
{
int temp=(j1==1&&k1==1)?-B:(j1==0&&k1==0?B:0);
f[x][j1][j2|k1|k2]=min(f[x][j1][j2|k1|k2],a[j1][j2]+f[y][k1][k2]+A);
f[x][j1^1][j2|(k1^1)|k2]=min(f[x][j1^1][j2|(k1^1)|k2],a[j1][j2]+f[y][k1][k2]+temp);
}
}
}
}
}
}
signed main()
{
freopen("analyse.in","r",stdin);
freopen("analyse.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>A>>B;
// A=min(A,B);
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
addm(x,y);
}
// memset(f,0x7f,sizeof f);
lsx(1,0);
ans=min(min(f[1][0][0],f[1][1][0]-B),min(f[1][1][1]-B,f[1][0][1]-B));
cout<<ans;
return 0;
}
C. 代数
这题不想写 \(dp\)，想了个纯数学做法，详情看这
D. 组合
神秘题，题解的 \(std\) 也挺抽象的，要构造26个长1000位的数，转换成构造1000个长26位的数，最后再倒过来输出
构造的数保证两两之间或起来不同，这样才能使每一个数对每一位都有区分，至于构造。。。看 \(std\) 标程吧
点击查看代码
#include<bits/stdc++.h>
const int maxn=1e5+10;
using namespace std;
int a[maxn]={};
int n,ans[26][maxn];
int get(int x,int pos)
{
return x&(1<<(pos-1))?1:0;
}
int main()
{
freopen("combination.in","r",stdin);
freopen("combination.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=0;i<=999;i++)
{
for(int j=0;j<=25;j++)
{
ans[j][i]=get(a[i],25-j+1);
}
}
cout<<26<<endl;
for(int i=0;i<=25;i++)
{
for(int j=0;j<=999;j++)
cout<<ans[i][j];
cout<<endl;
}
return 0;
}
/*
*/