1. AT ABC169F
[ABC169F] Knapsack for All Subsets
思路：
考虑对于任意一个集合 \(P| P\in T\) \(P=\{ x1,x2,\cdots xk\} \ A[x1]+A[x2]+\cdots A[xk]=S\) 则其对答案的贡献为\(2^{n-len}\)
则可以设\(dp[i][j]\)表示前 \(i\) 个数中，和为 \(j\) 的答案
则可以列出转移方程\(dp[i][j]=\frac{dp[i-1][j-a[i]]}{2}+dp[i-1][j]\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3005;
const int mod=998244353;
int n,s;
int a[maxn];
int qp(int x,int k){
int res=1;
while(k){
if(k&1)res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
signed main(){
cin>>n>>s;
for(int i=1;i<=n;i++)cin>>a[i];
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=s;j>=a[i];j--){
dp[j]=(dp[j-a[i]]*qp(2,mod-2)+dp[j])%mod;
}
}
cout<<dp[s]<<endl;
return 0;
}
2. [ABC159F] Knapsack for All Segments
[ABC159F] Knapsack for All Segments
思路：考虑对于一段区间[l,r]满足子序列之和=S，则这段区间对整体的贡献为 \(l\times (n-r+1)\)
我们另 \(dp[i]\) 表示和为 \(i\) 的子序列的左端点之和为 \(dp[i]\)
枚举右端点，用背包进行统计
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3005;
const int mod=998244353;
int n,S;
int a[maxn];
int dp[maxn];
signed main(){
cin>>n>>S;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]<S)ans=(ans+dp[S-a[i]]*(n-i+1)%mod)%mod;
if(a[i]==S)ans=(ans+i*(n-i+1)%mod)%mod;
for(int j=S;j>=a[i];j--)dp[j]=(dp[j]+dp[j-a[i]])%mod;
dp[a[i]]=(dp[a[i]]+i)%mod;
}
cout<<ans<<endl;
return 0;
}
3. [ABC163E] Active Infants
思路：考虑一种贪心思路：我们只要将小的全部做成最优解，然后大的也一定是最优解。
将数组 \(a\) 按照值排序，设 \(dp[i][j]\) 表示将 \(1\sim j-i+1\) 放到 区间 \([l,r]\) 的最优策略
可以轻松列出转移方程
这里考虑两个问题：为什么 \(a[i]\) 所放的区间是连续的；为什么要从小的a开始枚举
第一个问题：考虑从一段区间往回倒退。我这段区间中所有要向左移动的，都是后缀的一段最小值；反之亦然。
第二个问题：因为小的a对答案的影响较小，这样能保证之后的答案更优。
好dp题一道
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2005;
int n;
struct node{
int val,id;
}a[maxn];
int dp[maxn][maxn];
bool cmp(node x,node y){
return x.val<y.val;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
dp[0][0]=1;
for(int len=1;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
dp[i][j]=max(dp[i][j],max(dp[i+1][j]+a[j-i+1].val*abs(i-a[j-i+1].id),dp[i][j-1]+a[j-i+1].val*abs(j-a[j-i+1].id)));
}
}
cout<<dp[1][n]<<endl;
return 0;
}
4. [ABC165F] LIS on Tree
定义 \(f[i]\) 表示长度为 \(i\) 的最长上升子序列以 \(f[i]\) 结尾
\(ans[i]\) 表示节点 \(i\) 到根的这段路径中的最长上升子序列长度
熟悉的dfs栈，同时使用二分去寻找最大的 \(x\) 使得 \(f[x] \leq a[u]\)
如果 \(x>ans[fa]\) 则 \(ans[x]=ans[fa]+1\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
int n,a[maxn];
vector<int> G[maxn];
int f[maxn],ans[maxn];
void dfs(int u,int fa){
int l=1,r=ans[fa];
int lst=0;
if(!fa)f[1]=a[u],ans[1]=1;
else{
while(l<=r){
int mid=l+r>>1;
if(a[u]<=f[mid])r=mid-1;
else l=mid+1;
}
lst=f[l];
f[l]=a[u];
ans[u]=ans[fa];
if(l>ans[fa])ans[u]++;
}
for(int v:G[u]){
if(v==fa)continue;
dfs(v,u);
}
f[l]=lst;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
5. [ABC167F] Bracket Sequencing
思路：想到大方向后其实不难想的正解，但是比较难往贪心上想
考虑贪心，将所有已有的串中成对的括号消掉之后，每一个字符串就会成为 )( 或 ( 或 ) 这样的形式，记每个字符串的左括号和右括号的数量为 \(x,y\)
\(x\) 较大的放在左边，反之右边
最后统一判断一下即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n;
struct node{
string s;
int l,r;
}L[maxn],R[maxn];
int cl,cr;
node get(string s){
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(')st.push(s[i]);
else if(s[i]==')'){
if(!st.empty()&&st.top()=='(')st.pop();
else st.push(s[i]);
}
}
int c1=0,c2=0;
string str="";
while(!st.empty()){
char c=st.top();
st.pop();
if(c=='(')c1++;
else c2++;
str+=c;
}
reverse(str.begin(),str.end());
return {str,c1,c2};
}
bool cmp1(node x,node y){
return x.r<y.r;
}
bool cmp2(node x,node y){
return x.l>y.l;
}
bool check(string s){
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(')st.push(s[i]);
else{
if(!st.empty()&&st.top()=='(')st.pop();
else st.push(s[i]);
}
}
if(st.empty())return 1;
else return 0;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
string s;cin>>s;
auto x=get(s);
if(x.l>=x.r)L[++cl]=x;
else R[++cr]=x;
}
sort(L+1,L+cl+1,cmp1);
sort(R+1,R+cr+1,cmp2);
string ss;
for(int i=1;i<=cl;i++)ss+=L[i].s;
for(int i=1;i<=cr;i++)ss+=R[i].s;
if(check(ss))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
6. [ABC181F] Silver Woods
思路：考虑二分
考虑什么情况下钉子会被经过：只要有任意一条路径，使得每段距离小于d，并且联通上下界，则这个直径为 \(d\) 的无法通过
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=105;
const double esp=1e-6;
int n;
struct node{
int x,y;
}a[maxn*4];
int cnt;
int fa[maxn];
int find(int x){
if(fa[x]!=x)return fa[x]=find(fa[x]);
return fa[x];
}
void merge(int u,int v){
int fu=find(u),fv=find(v);
if(fu==fv)return ;
fa[fu]=fv;
return ;
}
double dis(node a,node b){
return 1.0*sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
bool check(double d){
for(int i=1;i<=cnt;i++)fa[i]=i;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++){
if(i==j)continue;
if(dis(a[i],a[j])-d>esp)continue;
merge(i,j);
}
for(int i=1;i<=cnt;i++){
if(a[i].y!=100&&a[i].y!=-100)continue;
for(int j=1;j<=cnt;j++){
if(i==j)continue;
if(a[i].y+a[j].y)continue;
if(find(i)==find(j))return 0;
}
}
return 1;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
a[++cnt]={x,y};
a[++cnt]={x,100};
a[++cnt]={x,-100};
}
double l=0.0,r=200.0;
while(r-l>esp){
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.6f\n",l/2);
return 0;
}
7. [ABC195F] Coprime Present
思路：观察数据范围，考虑在数据范围上做功夫。
\(\gcd(n,m)=\gcd(n-m,m)\) 所以可以得出 \(n-m\leq B-A\)
所以我们对于任意一个 \([0,B-A]\) 的质数，有且仅有一个数能够整除这个数，而 \(72\) 以内的质数只有 \(20\) 个，所以可以状压。复杂度 \(O(len\times 2^{20})\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=75;
int l,r;
int prim[maxn];
bool vis[maxn];
int tot;
int dp[(1<<20)+5];
void init(){
int mx=72;
for(int i=2;i<=mx;i++){
if(!vis[i])prim[++tot]=i;
for(int j=1;j<=tot&&i*prim[j]<=mx;j++){
vis[prim[j]*i]=1;
if(i%prim[j]==0)break;
}
}
}
signed main(){
cin>>l>>r;
init();
dp[0]=1;
for(int i=l;i<=r;i++){
int t=0;
for(int j=1;j<=tot;j++)if(i%prim[j]==0)t|=(1<<(j-1));
for(int s=0;s<(1<<tot);s++){
if(!(s&t)){
dp[s|t]+=dp[s];
}
}
}
int ans=0;
for(int i=0;i<(1<<tot);i++)ans+=dp[i];
cout<<ans<<endl;
return 0;
}
8.[ABC197F] Construct a Palindrome
[ABC197F] Construct a Palindrome
思路：令 \(dis[i][j]\) 表示从 \(1\sim i, j\sim n\) 所能带来的最大贡献，且满足 \(s[1\sim i]=s[n\sim j]\)
考虑建图后跑 \(bfs\) 对于每一个点对 \((x,y)\) ，设 \(x\) 与 \((a,c1)\) 相连，\(y\) 与 \((b,c2)\) 相连
如果 \(c1=c2\) 则将 \((x,y)\) 与 \((a,b)\) 相连。然后跑 \(bfs\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1005;
const int inf=0x3f3f3f3f;
int n,m;
vector<pair<int,int>> G[maxn],g[maxn][maxn];
int dis[maxn][maxn],vis[maxn][maxn];
void bfs(){
queue<pair<int,int>> Q;
memset(dis,inf,sizeof(dis));
vis[1][n]=1;
dis[1][n]=0;
Q.push({1,n});
while(!Q.empty()){
auto u=Q.front();
Q.pop();
for(auto v:g[u.first][u.second]){
if(!vis[v.first][v.second]){
vis[v.first][v.second]=1;
dis[v.first][v.second]=dis[u.first][u.second]+1;
Q.push({v.first,v.second});
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;char c;
cin>>a>>b>>c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(auto a:G[i]){
for(auto b:G[j]){
if(a.second==b.second){
g[i][j].push_back({a.first,b.first});
}
}
}
}
}
bfs();
int ans=inf;
for(int i=1;i<=n;i++)ans=min(ans,dis[i][i]*2);
for(int i=1;i<=n;i++){
for(auto j:G[i]){
ans=min(ans,dis[i][j.first]*2+1);
}
}
if(ans>=inf)puts("-1");
else cout<<ans<<endl;
return 0;
}
9. [ABC209F] Deforestation
思路：
可以推式子得到：
当 \(a[i-1]>a[i]\) 时，\(i-1\) 在 \(i\) 之前
当 \(a[i]>a[i-1]\) 时，\(i\) 在 \(i-1\) 之前
当 \(a[i]==a[i-1]\) 时，\(i\) 可以放在任意位置
这样可以设计一个 \(dp\)
设 \(dp[i][j]\) 表示第i个数放在 \(j\) 的合法方案数
这里的 \(j\) 表示第 \(i\) 个数放在 \(1\sim i\) 的第 \(j\) 个位置，所以这里仅仅是相对位置
当 \(a[i-1]>a[i]\) \(dp[i][j]=\sum_{k=1}^{j-1}dp[i-1][k]\)
当 \(a[i]>a[i-1]\) \(dp[i][j]=\sum_{k=j}^{i-1}dp[i-1][k]\)
当 \(a[i]==a[i-1]\) \(dp[i][j]=\sum_{k=1}^{i-1}dp[i-1][k]\)
一定注意，这题设计的状态转移是相对位置，一定不能搞错了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4005;
const int mod=1e9+7;
int n;
int a[maxn];
int dp[maxn][maxn],s[maxn][maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dp[1][1]=1;
for(int i=1;i<=n;i++)s[1][i]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(a[i-1]>a[i])dp[i][j]=s[i-1][j-1]%mod;
if(a[i-1]<a[i])dp[i][j]=(s[i-1][i-1]-s[i-1][j-1]+mod)%mod;
if(a[i-1]==a[i])dp[i][j]=s[i-1][i-1]%mod;
}
for(int j=1;j<=n;j++)s[i][j]=(s[i][j-1]+dp[i][j])%mod;
}
cout<<s[n][n]<<endl;
return 0;
}
10.[ABC217F] Make Pair
以后看到这种区间删除的问题，一定要考虑能否区间dp
\(dp[i][j]\)表示 \(i\sim j\) 这段区间被消除的种类数
所以可以列出转移方程 \(dp[i][j]=dp[i+1][k-1]*dp[k+1][j]*\binom{\frac{j-i+1}{2}}{\frac{j-k+1}{2}}\)
后面的理解为从 \(\frac{j-i+1}{2}\) 中选 \(\frac{j-k+1}{2}\)
可以感性理解一下
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define begin init()
#define rand RAND
#define LOCAL
using namespace std;
template<class Typ> Typ &re(Typ &x){char ch=getchar(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=getchar()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=405;
const int mod=998244353;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int fac[maxn],inv[maxn];
int qp(int x,int k){int res=1;while(k){if(k&1)res=res*x%mod;x=x*x%mod;k>>=1;}return res;}
void init(){int mx=maxn-5;fac[0]=1;for(int i=1;i<=mx+1;i++)fac[i]=fac[i-1]*i%mod;inv[mx+1]=qp(fac[mx+1],mod-2);for(int i=mx;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;}
int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int n,m;
int vis[maxn][maxn*2];
int dp[maxn][maxn*2];
signed main(){
begin;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
if((b-a+1)%2==1)continue;
vis[a][b]=vis[b][a]=1;
if(a+1==b||b+1==a)dp[a][b]=1;
}
n*=2;
for(int i=1;i<=n+1;i++)dp[i][i-1]=1;
for(int len=2;len<=n;len+=2){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(vis[i][j])dp[i][j]=dp[i+1][j-1];
for(int k=i+1;k<j;k+=2){
if(vis[i][k]){
dp[i][j]=(dp[i][j]+dp[i+1][k-1]*dp[k+1][j]%mod*C((j-i+1)/2,(j-k+1)/2)%mod)%mod;
}
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
11.[ABC209E] Shiritori
思考一种建图方式
如果一个串的后面无法再接其他串，则这个点为先手必胜点，我们使 \(f[u]=1\)
所以我们可以考虑将这些串建图，然后跑一遍 \(BFS\)
建图怎么建？把所有的单词的后三个字符和前三个字符连起来
然后跑类似 \(topu\) 排序的东西
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
int n;
map<string,int> mp;
vector<int> G[maxn];
int ind[maxn];
int id,f[maxn];
string str[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
string s;cin>>s;
int m=s.size()-1;
string u=s.substr(0,3);
string v=s.substr(m-2,3);
if(!mp[u])mp[u]=++id;
if(!mp[v])mp[v]=++id;
G[mp[v]].push_back(mp[u]);
ind[mp[u]]++;
str[i]=s;
}
queue<int> Q;
for(int i=1;i<=id;i++){
if(!ind[i])Q.push(i),f[i]=1;
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int v:G[u]){
ind[v]--;
if(f[u]==1&&f[v]==0)f[v]=-1,Q.push(v);
if(f[u]==-1&&f[v]==0&&!ind[v])f[v]=1,Q.push(v);
//这两句是核心：因为两个人都会选择最优策略，所以如果当前串所能连接的串中任意一个为其必胜节点，则他必定选择这个节点
}
}
for(int i=1;i<=n;i++){
int m=str[i].size()-1;
string s=str[i];
string u=s.substr(m-2,3);
if(f[mp[u]]==1)puts("Takahashi");
if(f[mp[u]]==-1)puts("Aoki");
if(f[mp[u]]==0)puts("Draw");
}
return 0;
}
12.[ABC229F] Make Bipartite
不太好想
思路：看到有关二分图，先考虑染色
我们令0号节点的颜色为0
所以我们可以设 \(dp[i][j][k]\) 表示第 \(i\) 个点的颜色为 \(j\) ，第 \(1\) 个点的颜色为 \(k\)
可以列出转移方程
\[dp[i][j][k]=min(dp[i-1][op][k]+(j==0?a[i]:0)+(j==op?b[i-1]:0))\\ \]考虑初始化：\(dp[1][0][0]=a[1],dp[1][1][1]=0\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
int n;
int a[maxn],b[maxn];
int dp[maxn][2][2];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)dp[i][j][k]=1e15;
dp[1][0][0]=a[1];
dp[1][1][1]=0;
for(int p=0;p<=1;p++){
for(int i=2;i<=n;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
dp[i][j][p]=min(dp[i][j][p],dp[i-1][k][p]+(j==0?a[i]:0)+(j==k?b[i-1]:0));
}
}
}
}
int ans=LONG_LONG_MAX;
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
ans=min(ans,dp[n][j][k]+(j==k?b[n]:0));
}
}
cout<<ans<<endl;
return 0;
}
13.[ABC227G] Divisors of Binomial Coefficient
[ABC227G] Divisors of Binomial Coefficient
思路：将题目中的公式拆解
\[\binom{n}{k}=\frac{\prod \limits_{i=n-k+1}^{n}i}{\prod \limits_{i=1}^{k}i} \]不难发现，上下两个范围是相同
一个数 \(x\) 中，\(>\sqrt{x}\) 的质因数最多只有一个：因为 \((\sqrt{x})^2\geq x\)
所以我们可以筛出分母所有的质因数的个数
然后对于分子的每个数也分解质因数，然后算出两数之差。分母的每一个数分解后，如果没有分解干净，说明剩下的数为质因数。
最后统计答案
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
#define LOCAL
using namespace std;
template<class Typ> Typ &re(Typ &x){char ch=getchar(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=getchar()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e6+5;
const int mod=998244353;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n,k;
int num[maxn],cnt[maxn];
signed main(){
cin>>n>>k;
for(int i=1;i<=k;i++)num[i]=i;
for(int i=2;i<=maxn-5;i++){
int x=i;
for(int j=i;j<=k;j+=i){
while(num[j]%i==0){
num[j]/=i;
cnt[i]--;
}
}
}
for(int i=1;i<=k;i++)num[i]=i+n-k;
for(int i=2;i<=maxn-5;i++){
int x=((n-k)/i+1)*i;
for(int j=x;j<=n;j+=i){
while(num[j-n+k]%i==0){
num[j-n+k]/=i;
cnt[i]++;
}
}
}
int ans=1;
for(int i=2;i<=maxn-5;i++){
ans*=(cnt[i]+1);
ans%=mod;
}
for(int i=1;i<=k;i++)if(num[i]!=1)ans*=2,ans%=mod;
cout<<ans%mod<<endl;
return 0;
}
14.[ABC233F] Swap and Sort
这个题目是一个构造题，可以随意构造
所以我们可以考虑对于每一个点的相邻节点，只要能够得到对应的结果，就可以翻转
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n,m;
int a[maxn];
struct node{
int v,id;
};
vector<node> G[maxn];
vector<int> ans;
int fa[maxn],vis[maxn];
int find(int u){
if(u!=fa[u])fa[u]=find(fa[u]);
return fa[u];
}
void merge(int u,int v){
int fu=find(u),fv=find(v);
if(fu==fv)return ;
fa[fu]=fv;
return ;
}
bool have_solution(){
for(int i=1;i<=n;i++){
if(find(a[i])!=find(i))return 0;
}
return 1;
}
struct Node{
int to,nxt,id;
}E[maxn];
int head[maxn],cnt;
void add(int u,int v,int i){
E[++cnt]={v,head[u],i};
head[u]=cnt;
}
bool check(int u,int f,int col){
if(a[u]==col)return 1;
for(int i=head[u];i;i=E[i].nxt){
int v=E[i].to,id=E[i].id;
if(v==f)continue;
if(check(v,u,col)){
ans.push_back(id);
swap(a[u],a[v]);
return 1;
}
}
return 0;
}
void dfs(int u){
vis[u]=1;
for(int i=head[u];i;i=E[i].nxt){
int v=E[i].to;
if(vis[v])continue;
dfs(v);
}
if(!check(u,0,u)){
puts("-1");
exit(0);
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)fa[i]=i;
cin>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
if(find(u)!=find(v)){
add(u,v,i);
add(v,u,i);
merge(u,v);
}
}
if(!have_solution()){
puts("-1");
return 0;
}
for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
cout<<ans.size()<<endl;
for(int u:ans)cout<<u<<" ";
cout<<endl;
return 0;
}
15.[ABC238F] Two Exams
思路：
我们将其排序，然后令 \(rank[a[i]]=b[i]\) 我们从 \(i=1\sim n\) 枚举，所以 \(i\) 肯定是大于 \(i-1\) 的
所以如果想要选 \(i\) 这个节点，我们要满足 \(rand[i]\) 小于之前所选择的 \(rank\)
\(dp[第i个人][已经选择了的人数为len][没有选择的人中rank的最小值]\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=305;
const int mod=998244353;
int n,k;
int p[maxn],q[maxn];
int dp[maxn][maxn][maxn];
map<int,int> mp;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++)cin>>q[i];
for(int i=1;i<=n;i++)mp[p[i]]=q[i];
dp[0][0][n+1]=1;
for(int i=1;i<=n;i++){
int x=mp[i];
for(int j=0;j<=k;j++){
for(int y=0;y<=n+1;y++){
if(j<k&&x<y){
dp[i][j+1][y]+=dp[i-1][j][y];
dp[i][j+1][y]%=mod;
}
dp[i][j][min(x,y)]+=dp[i-1][j][y];
dp[i][j][min(x,y)]%=mod;
}
}
}
int ans=0;
for(int i=0;i<=n+1;i++)(ans+=dp[n][k][i])%=mod;
cout<<ans<<endl;
return 0;
}
16.[ABC235F] Variety of Digits
这题的翻译！！！！
比较正常的计数dp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e4+5;
const int mod=998244353;
string n;
int m;
int A[maxn];
int pw[maxn];
int dp[maxn][(1<<12)],dp2[maxn][(1<<12)];
map<int,int> mp;
int a[maxn],pos;
void init(){
int N=1e4;
pw[0]=1;
for(int i=1;i<=N;i++)pw[i]=pw[i-1]*10%mod;
}
pair<int,int> dfs(int pos,int st,int lead,int lim){
if(pos==-1)return {(st==(1<<m)-1),0};
if(!lead&&!lim&&dp[pos][st]!=-1)return {dp[pos][st],dp2[pos][st]};
int up=lim?a[pos]:9;
int sum1=0,sum2=0;
for(int i=0;i<=up;i++){
if(lead&&i==0){
auto k=dfs(pos-1,st,1,lim&&i==a[pos]);
sum1=(sum1+k.first)%mod;
sum2=(sum2+pw[pos]*i%mod*k.first%mod+k.second)%mod;
}
else if(mp[i]){
auto k=dfs(pos-1,st|(1<<(mp[i]-1)),0,lim&&i==a[pos]);
sum1=(sum1+k.first)%mod;
sum2=(sum2+pw[pos]*i%mod*k.first%mod+k.second)%mod;
}
else{
auto k=dfs(pos-1,st,0,lim&&i==a[pos]);
sum1=(sum1+k.first)%mod;
sum2=(sum2+pw[pos]*i%mod*k.first%mod+k.second)%mod;
}
}
if(!lead&&!lim){
dp[pos][st]=sum1;
dp2[pos][st]=sum2;
}
return {sum1,sum2};
}
pair<int,int> solve(string x){
pos=0;
int len=x.size();
for(int i=len-1;i>=0;i--)a[pos++]=x[i]-'0';
return dfs(pos-1,0,1,1);
}
signed main(){
init();
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>A[i];
for(int i=1;i<=m;i++)mp[A[i]]=i;
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
auto ans=solve(n);
cout<<ans.second<<endl;
return 0;
}
17.Star MST
好题一道
先考虑将一个以1为根的菊花图，删除 \(1\sim u\)，加入 \(u\sim v\) 。设 \(1\sim u\) 的边权为 \(x\)，\(u\sim v\) 的边权为 \(y\)，当前的最小生成树的大小为 \(t\)
\[t-x+y\geq t\\ x\leq y \]所以可以得出，如果是这个生成树为最小生成树，则离任意 \(u\) 最近的之一的点，必定为 \(1\)
所以可以得出一个比较显然的DP。设 \(dp[i][j]\) 表示当前已经确定了 \(i\) 个点，且这 \(i\) 个点中与 \(1\) 的距离最大的为 \(j\)
我们去枚举一个转移点 \(t\) 即为前 \(i\) 个点中有 \(t\) 个小于 \(j\) 的节点，则可以得出 \(dp[i][j]=\sum\limits_{k=0}^{j-1}dp[t][k]\)
之后我们还要从 \(n-t\) 个节点中放入 \(i-t\) 个节点。所以 \(dp[i][j]=dp[i][j]\times C_{n-t}^{i-t}\)
然后我们加入这 \(i-t\) 个节点的时候，因为我们在之前的转移当中已经确定了 \(1\sim i\) 的边权，所以只要确定这其余\((i-t)\times(t-1)+\frac{(i-t)\times(i-t-1)}{2}\) 条边的权值，每条边的权值有 \(K-j+1\) 种可能
所以转移方程为：
\[dp[i][j]=\sum\limits_{k=0}^{j-1}dp[t][k]\times C_{n-t}^{i-t}\times (K-j+1)^{(i-t)*(t-1)+\frac{(i-t)\times (i-t-1)}{2}}\\ \]然后我们会发现一个问题，对于剩余的 \(n-i\) 个未插入的点，他们与之前的点会有更多的限制条件
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define begin init()
#define rand RAND
#define LOCAL
using namespace std;
template<class Typ> Typ &re(Typ &x){char ch=getchar(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=getchar()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=255;
const int mod=998244353;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int fac[maxn],inv[maxn];
int qp(int x,int k){int res=1;while(k){if(k&1)res=res*x%mod;x=x*x%mod;k>>=1;}return res;}
void init(){int mx=maxn-5;fac[0]=1;for(int i=1;i<=mx+1;i++)fac[i]=fac[i-1]*i%mod;inv[mx+1]=qp(fac[mx+1],mod-2);for(int i=mx;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;}
int C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int n,k;
int dp[maxn][maxn],sum[maxn][maxn];
signed main(){
begin;
cin>>n>>k;
dp[1][0]=1;
for(int i=0;i<=k;i++)sum[1][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=k;j++){
for(int t=1;t<i;t++){
dp[i][j]=(dp[i][j]+sum[t][j-1]*C(n-t,i-t)%mod*qp(k-j+1,(i+t-3)*(i-t)/2)%mod)%mod;
}
sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
}
}
cout<<sum[n][k]<<endl;
return 0;
}
/*
dp[i][j]表示前i个数，最大值为j
*/