传送门：AtCoder Regular Contest 163 - AtCoder

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

#include

#define int long long

using namespace std;

typedef long long ll;

typedef pair PII;

const int N=1000000007;

int n,k;

void icealsoheat(){

cin>>n;

string s;

cin>>s;

for(int i=1;i

if(s.substr(0,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

#define int long long

using namespace std;

typedef long long ll;

typedef pair 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

ans=min(ans,xx);

}

cout<

}

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

using namespace std;

#define int long long

typedef long long ll;

typedef pair PII;

const int N=998244353;

const int MX=0x3f3f3f3f3f3f3f3f;

int n,k;

maphh;

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{

vectorans;

if(hh[n]){

n--;

for(int i=1;i

ans.push_back(2ll*i*(i+1ll));

}

ans.push_back(2ll*n);

cout<<"2 ";

for(auto i:ans){

cout<

}

}

else{

for(int i=1;i

cout<

}

cout<

}

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

#define int long long

using namespace std;

typedef long long ll;

typedef pair 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(1600,0)));

dp[0][0][0]=1;

for(int i=0;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<

}

signed main(){

ios::sync_with_stdio(false);

cin.tie();

cout.tie();

int _;

_=1;

// cin>>_;

init(500);

while(_--){

icealsoheat();

}

}

推荐链接

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：