AC修炼计划（AtCoder Regular Contest 163）

传送门：AtCoder Regular Contest 163 - AtCoder

第一题我们只需要将字符串分成两段，如果存在前面一段比后面一段大就成立。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1000000007;
int n,k;
void icealsoheat(){cin>>n;string s;cin>>s;for(int i=1;i<n;i++){if(s.substr(0,i)<s.substr(i)){puts("Yes");return;}}puts("No");}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;cin>>_;while(_--){icealsoheat();}}

B - Favorite Game

第二题也比较基础，我们可以先把后面的数组排序，然后枚举每一段（每一段的长度为k，包含按顺序的k个数）

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1000000007;
int n,k;
int b[1000005];
void icealsoheat(){int le,re;cin>>n>>k;cin>>le>>re;n-=2;int an=0;for(int i=1;i<=n;i++){cin>>b[i];if(b[i]>=le&&b[i]<=re)an++;}sort(b+1,b+1+n);if(an>=k){cout<<0;return;}int ans=0x3f3f3f3f3f3f3f3f;for(int i=1;i<=n-k+1;i++){int xx=0;if(le>b[i])xx+=abs(le-b[i]);if(re<b[i+k-1])xx+=abs(re-b[i+k-1]);ans=min(ans,xx);}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}}

C - Harmonic Mean

这题想到了裂项相消公式，但是没有想到给他们分开。

当存在n=t*(t+1)的时候，我们不能直接用数列（2，6，12，20.。。。。（n-1）*n,n）

而是把后n-1项看成一部分，使后n-1项的和等于1，然后把每一个项数*2，此时的后n-1项的总和为1/2，这时候我们只需要再放入一个2即可

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,k;
map<int,int>hh;
void yu(){for(int i=1;i<=500;i++){hh[i*(i+1)]=1;}
}
void icealsoheat(){cin>>n;if(n==2)cout<<"No\n";else{cout<<"Yes\n";if(n==1)cout<<"1\n";else if(n==3)cout<<"2 3 6\n";else{vector<int>ans;if(hh[n]){n--;for(int i=1;i<n;i++){ans.push_back(2ll*i*(i+1ll));}ans.push_back(2ll*n);cout<<"2 ";for(auto i:ans){cout<<i<<" ";}}else{for(int i=1;i<n;i++){cout<<i*(i+1)<<" ";}cout<<n;}cout<<"\n";}}}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;yu();cin>>_;while(_--){icealsoheat();}
}

D - Sum of SCC

好厉害的题，开拓了我的视野。不看题解我是真想不到竟然还能这么dp。

我们可以知道，统计SSG（强连通分量）是很难统计的。竞赛图有一个性质：当我们把强连通分量缩点之后，拉直，整个竞赛图会变成一条很长的链，并且，长的链上的任何两个点之间都有一个链（很抽象又很神奇的想法）。既然变成了一个长长的链，那么其实我们可以通过在长链上某点进行一刀切，使其分成左右两个集合，分别是集合A与集合B，同时，我们定义集合A的所有点都与集合B的相连。且集合A的数字较小，集合B的数字较大。

我们用三维dp i，j，k来进行动态规划。i表示我们只有前i个点儿的状态，j表示A集合中有j个点儿，k表示有k条小数向大数连的边。

我们每次塞进去第i个点儿，有两种情况：

1.将该点儿塞入集合A中，那么该点儿可以从集合A中选择p个点使这p个点儿指向该点儿。

dp[i+1][j+1][k+p]+=dp[i][j][k]*c[j][p]

2.将该点儿塞入集合B中，那么A点都会指向该点儿，同时我们可以选取B集合中p个点儿，使其指向该点儿。

dp[i+1][j][j+k+p]+=dp[i][j][k]*c[i-j][p]

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int n,m;
int c[505][505];void init(int mx)
{for(int i=0;i<=mx;i++)for(int j=0;j<=i;j++) c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%mod:1;
}void icealsoheat(){cin>>n>>m;vector dp(50,vector(50,vector<int>(1600,0)));dp[0][0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){for(int k=0;k<=i*(i-1)/2;k++){for(int p=0;p<=j;p++)(dp[i+1][j+1][k+p]+=dp[i][j][k]*c[j][p]%mod)%mod;for(int p=0;p<=i-j;p++)(dp[i+1][j][j+k+p]+=dp[i][j][k]*c[i-j][p]%mod)%mod;}}}int ans=0;for(int i=1;i<=n;i++){ans=(ans+dp[n][i][m])%mod;}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;init(500);while(_--){icealsoheat();}}