高考报名时间2022年11月1日还剩 天 距离2023年6月7日高考还有 天
栏目分类:
子分类:
返回
名师互学网用户登录
名师互学网
快速导航关闭
当前搜索
当前分类
前沿技术 软件开发 系统运维 产品运营 生活办公 面试经验 考试题库
子分类
人工智能 大数据 云计算 区块链 物联网 深度学习 机器学习 NLP 计算机视觉 语音识别 其他 大数据系统 数据可视化 数据挖掘与分析 其他 Docker/k8s 虚拟化 云平台 其他 基本原理 数字货币 智能合约 EOS应用 其他 通讯技术 嵌入式开发 单片机 物联网应用 HarmonyOS 其他 后端开发 Web开发 移动开发 游戏开发 Python Java 架构设计 C/C++/C# PHP .Net Go语言 R语言
实用工具
学习工具 小学数学练习 字帖生成 在线画板 函数绘制 拼音字母表 在线词典 黄历查询 亲戚关系计算 安全期计算 中国历史 Excel函数 模拟请求 json格式化 浏览器指纹
热门搜索
路由器设置 木托盘 宝塔面板 儿童python教程 心情低落 朋友圈 vim 双一流学科 专升本 我的学校 日记学校 西点培训学校 汽修学校 情书 化妆学校 塔沟武校 异形模板 西南大学排名 最精辟人生短句 6步教你追回被骗的钱 南昌大学排名 清朝十二帝 北京印刷学院排名 北方工业大学排名 北京航空航天大学排名 首都经济贸易大学排名 中国传媒大学排名 首都师范大学排名 中国地质大学(北京)排名 北京信息科技大学排名
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

AtCoder Beginner Contest 261（ABC261）A-Ex 题解

C/C++/C# 更新时间： 发布时间： IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

AtCoder Beginner Contest 261（ABC261）A-Ex 题解

A - Intersection

处理成 [ L , R ) [L,R) [L,R) 区间，枚举即可。

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;



inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int len;

int main()
{
	int l1=read(),r1=read(),l2=read(),r2=read();
	for(int i=0;i<=100;i++)
		if(l1<=i&&i 

 
B - Tournament Result 

赢记成 
    
     
      
       
        1
       
      
      
       1
      
     
    1，输记成 
    
     
      
       
        −
       
       
        1
       
      
      
       -1
      
     
    −1，平局为 
    
     
      
       
        0
       
      
      
       0
      
     
    0。相当于求满足 
    
     
      
       
        
         A
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
       
        +
       
       
        
         A
        
        
         
          j
         
         
          ,
         
         
          i
         
        
       
       
        =
       
       
        0
       
      
      
       A_{i,j}+A_{j,i}=0
      
     
    Ai,j​+Aj,i​=0 的对数。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;



inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,a[1005][1005];
char s[1005];

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=n;j++)
		{
			if(s[j]=='W')a[i][j]=1;
			if(s[j]=='D')a[i][j]=0;
			if(s[j]=='L')a[i][j]=-1;
		}
	}
	for(int i=1;i
				printf("incorrect");
				return 0;
			}
	printf("correct");
	
	return 0;
}

 

 
C - NewFolder(1) 

用 map 模拟即可。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;



inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n;
map mp;
string s;

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		if(!mp.count(s))cout< 

 
D - Flipping and Bonus 

设置状态 
    
     
      
       
        d
       
       
        
         p
        
        
         i
        
       
      
      
       dp_i
      
     
    dpi​ 表示经过 
    
     
      
       
        i
       
      
      
       i
      
     
    i 次抛硬币的最大收益。
 

当第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 次抛出为 
    
     
      
       
        0
       
      
      
       0
      
     
    0 时，
    
     
      
       
        d
       
       
        
         p
        
        
         i
        
       
       
        =
       
       
        d
       
       
        
         p
        
        
         
          i
         
         
          −
         
         
          1
         
        
       
      
      
       dp_i=dp_{i-1}
      
     
    dpi​=dpi−1​。
 

否则，转移时第二维枚举当前连续抛出 
    
     
      
       
        1
       
      
      
       1
      
     
    1 的次数为 
    
     
      
       
        j
       
      
      
       j
      
     
    j，即第 
    
     
      
       
        i
       
       
        −
       
       
        j
       
      
      
       i-j
      
     
    i−j 次为 
    
     
      
       
        0
       
      
      
       0
      
     
    0，第 
    
     
      
       
        i
       
       
        −
       
       
        j
       
       
        +
       
       
        1
       
      
      
       i-j+1
      
     
    i−j+1 至第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 次均为 
    
     
      
       
        1
       
      
      
       1
      
     
    1。
 

那么转移为 
    
     
      
       
        d
       
       
        
         p
        
        
         i
        
       
       
        =
       
       
        
         
          max
         
         
          ⁡
         
        
        
         
          j
         
         
          =
         
         
          1
         
        
        
         i
        
       
       
        
         d
        
        
         
          p
         
         
          
           i
          
          
           −
          
          
           j
          
          
           −
          
          
           1
          
         
        
        
         +
        
        
         
          ∑
         
         
          
           k
          
          
           =
          
          
           i
          
          
           −
          
          
           j
          
          
           +
          
          
           1
          
         
         
          i
         
        
        
         
          a
         
         
          i
         
        
        
         +
        
        
         
          ∑
         
         
          
           k
          
          
           =
          
          
           1
          
         
         
          j
         
        
        
         
          c
         
         
          i
         
        
       
      
      
       dp_i=maxlimits_{j=1}^{i}{dp_{i-j-1}+sumlimits_{k=i-j+1}^i{a_i}+sumlimits_{k=1}^j{c_i}}
      
     
    dpi​=j=1maxi​dpi−j−1​+k=i−j+1∑i​ai​+k=1∑j​ci​，那个 
    
     
      
       
        j
       
       
        =
       
       
        i
       
      
      
       j=i
      
     
    j=i 的情况特判一下就行。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

typedef long long ll;
const int M=5005;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,m;
ll a[M],c[M],dp[M],tot,ans;

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=a[i-1]+read();
	for(int i=1,x;i<=m;i++)
		x=read(),c[x]=read();
	for(int i=1;i<=n;i++)
		c[i]+=c[i-1];
	
	for(int i=1;i<=n;i++)
	{
		dp[i]=max(dp[i-1],a[i]+c[i]);
		for(int j=1;j 

 
E -  Many Operations 

按位考虑。预处理出第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 位为 
    
     
      
       
        0
       
       
        /
       
       
        1
       
      
      
       0/1
      
     
    0/1 时在经过第 
    
     
      
       
        1
       
       
        ∼
       
       
        j
       
      
      
       1sim j
      
     
    1∼j 个操作后的值 
    
     
      
       
        t
       
       
        
         o
        
        
         
          0
         
         
          /
         
         
          1
         
         
          ,
         
         
          j
         
        
       
      
      
       to_{0/1,j}
      
     
    to0/1,j​。然后按题意，对 
    
     
      
       
        X
       
      
      
       X
      
     
    X 第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 位上的数 
    
     
      
       
        n
       
       
        u
       
       
        m
       
      
      
       num
      
     
    num，用类似倍增的递推方式传递，即第 
    
     
      
       
        j
       
      
      
       j
      
     
    j 轮时有 
    
     
      
       
        n
       
       
        u
       
       
        m
       
       
        =
       
       
        t
       
       
        
         o
        
        
         
          n
         
         
          u
         
         
          m
         
         
          ,
         
         
          j
         
        
       
      
      
       num=to_{num,j}
      
     
    num=tonum,j​，然后将贡献加到对应答案里。
 

#include 
using namespace std;
const int N=2e5+10;
int n,x,op[N],a[N],to[2][N],ans[N];
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&op[i],&a[i]);
	for(int i=0;i<31;i++)
	{
		for(int now=0;now<2;now++)
		{
			int num=now;
			for(int j=1;j<=n;j++)
			{
				int tmp=a[j]&(1<
			tmp=to[tmp][j];
			ans[j]+=(1< 

 
F -  Sorting Color Balls 

答案显然为总逆序对数减去同色的逆序对数。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

typedef long long ll;
const int M=3e5+5;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,c[M],x[M];
vector E[M];
ll ans;

struct Tree
{
	ll c[M];
	#define lowbit(x) x&(-x)
	void clear(){memset(c,0,sizeof(c));}
	void add(int x,ll k){for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;}
	ll sum(int x){ll res=0;for(int i=x;i>0;i-=lowbit(i))res+=c[i];return res;}
}T;

int main()
{
	n=read();
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<=n;i++)x[i]=read();
	for(int i=1;i<=n;i++)
		ans+=(i-1)-T.sum(x[i]),T.add(x[i],1);
	T.clear();
	
	for(int i=1;i<=n;i++)E[c[i]].push_back(x[i]);
	for(int col=1;col<=n;col++)
	{
		if(E[col].empty())continue;
		for(int i=0;i<(int)E[col].size();i++)
			ans-=i-T.sum(E[col][i]),T.add(E[col][i],1);
		for(int v:E[col])T.add(v,-1);
	}
	
	printf("%lld",ans);
	
	return 0;
}

 

 
G -  Replace 

较为复杂的区间 DP。
 

首先想到倒着替换，从 
    
     
      
       
        t
       
      
      
       t
      
     
    t 经过一系列操作变成 
    
     
      
       
        s
       
      
      
       s
      
     
    s。设置状态 
    
     
      
       
        d
       
       
        p
       
       
        (
       
       
        l
       
       
        ,
       
       
        r
       
       
        ,
       
       
        c
       
       
        )
       
      
      
       dp(l,r,c)
      
     
    dp(l,r,c) 表示把 
    
     
      
       
        t
       
      
      
       t
      
     
    t 中片段 
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r] 替换为字符 
    
     
      
       
        c
       
      
      
       c
      
     
    c 所需的最少步数。那么我们先用替换后长度减小的状态更新，再用替换后长度不变的更新，来保证多种情况叠加的正常转移。
 

先处理长度减小的状态更新。枚举选用的操作 
    
     
      
       
        i
       
      
      
       i
      
     
    i，设置状态 
    
     
      
       
        g
       
       
        (
       
       
        j
       
       
        ,
       
       
        k
       
       
        )
       
      
      
       g(j,k)
      
     
    g(j,k) 表示把 
    
     
      
       
        t
       
      
      
       t
      
     
    t 中片段 
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        k
       
       
        ]
       
      
      
       [l,k]
      
     
    [l,k] 替换为 
    
     
      
       
        
         A
        
        
         i
        
       
      
      
       A_i
      
     
    Ai​ 中片段 
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        j
       
       
        ]
       
      
      
       [1,j]
      
     
    [1,j] 所需的最少步数，那么有转移 
    
     
      
       
        g
       
       
        (
       
       
        j
       
       
        ,
       
       
        k
       
       
        )
       
       
        =
       
       
        
         
          min
         
         
          ⁡
         
        
        
         
          k
         
         
          2
         
         
          =
         
         
          l
         
         
          −
         
         
          1
         
        
        
         
          k
         
         
          −
         
         
          1
         
        
       
       
        {
       
       
        g
       
       
        (
       
       
        j
       
       
        −
       
       
        1
       
       
        ,
       
       
        k
       
       
        2
       
       
        )
       
       
        +
       
       
        d
       
       
        p
       
       
        (
       
       
        k
       
       
        2
       
       
        +
       
       
        1
       
       
        ,
       
       
        k
       
       
        ,
       
       
        
         A
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
       
        )
       
       
        }
       
      
      
       g(j,k)=minlimits_{k2=l-1}^{k-1}Big{g(j-1,k2)+dpbig(k2+1,k,A_{i,j}big) Big}
      
     
    g(j,k)=k2=l−1mink−1​{g(j−1,k2)+dp(k2+1,k,Ai,j​)}。如果存在 
    
     
      
       
        j
       
      
      
       j
      
     
    j 使得无法从有效状态转移而来，说明操作 
    
     
      
       
        i
       
      
      
       i
      
     
    i 当前无效，那么 
    
     
      
       
        g
       
      
      
       g
      
     
    g 就不能转移至 
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp 中。
 

再处理长度不变的状态更新。用 Floyd 预处理从字符 
    
     
      
       
        j
       
      
      
       j
      
     
    j 替换成字符 
    
     
      
       
        i
       
      
      
       i
      
     
    i 所需的最少步数 
    
     
      
       
        d
       
       
        i
       
       
        s
       
       
        (
       
       
        j
       
       
        ,
       
       
        i
       
       
        )
       
      
      
       dis(j,i)
      
     
    dis(j,i)，那么便有 
    
     
      
       
        d
       
       
        p
       
       
        (
       
       
        l
       
       
        ,
       
       
        r
       
       
        ,
       
       
        i
       
       
        )
       
       
        =
       
       
        min
       
       
        ⁡
       
       
        {
       
       
        d
       
       
        p
       
       
        (
       
       
        l
       
       
        ,
       
       
        r
       
       
        ,
       
       
        j
       
       
        )
       
       
        +
       
       
        d
       
       
        i
       
       
        s
       
       
        (
       
       
        j
       
       
        ,
       
       
        i
       
       
        )
       
       
        }
       
      
      
       dp(l,r,i)=min{dp(l,r,j)+dis(j,i)}
      
     
    dp(l,r,i)=min{dp(l,r,j)+dis(j,i)}。
 

最终答案得到的方法也是类似的，具体见代码吧。代码里对 
    
     
      
       
        g
       
      
      
       g
      
     
    g 进行了滚动数组优化。
 

PS：由于这是我看别人代码而理出来的思路，难免有解释不当或疏漏之处，还请读者指教。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

const int inf=0x3f3f3f3f;
const int M=55;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,m,p,leng[M],dis[30][30];
char s[M],t[M],cr[M],to[M][M];

int dp[M][M][30];// change [i,j] to c
int g[2][M];

int main()
{
	memset(dis,0x3f,sizeof(dis));
	memset(dp,0x3f,sizeof(dp));
	
	scanf("%s",s+1);n=strlen(s+1);
	scanf("%s",t+1);m=strlen(t+1);
	p=read();
	for(int i=1;i<=p;i++)
	{
		scanf("%s %s",cr+i,to[i]+1);
		leng[i]=strlen(to[i]+1);
		if(leng[i]==1)dis[to[i][1]-'a'][cr[i]-'a']=1;
	}
	for(int k=0;k<26;k++)
		for(int i=0;i<26;i++)
			for(int j=0;j<26;j++)
				Min(dis[i][j],dis[i][k]+dis[k][j]);
	for(int i=1;i<=m;i++)dp[i][i][t[i]-'a']=0;
	
	for(int len=1;len<=m;len++)
		for(int l=1,r=l+len-1;r<=m;l++,r++)
		{
			for(int i=1;i<=p;i++)
				if(leng[i]<=len)
				{
					for(int i=l;i<=r;i++)g[0][i]=g[1][i]=inf;
					g[0][l-1]=0;int now=0,fff=1;
					for(int j=1;j<=leng[i];j++)
					{
						now^=1;bool ok=false;
						for(int k1=l-1;k1<=r;k1++)
						{
							g[now][k1]=inf;
							for(int k2=l-1;k2fff=0;break;}
					}
					if(fff)Min(dp[l][r][cr[i]-'a'],g[now][r]+1);
				}
			for(int i=0;i<26;i++)
				for(int j=0;j<26;j++)
					Min(dp[l][r][i],dp[l][r][j]+dis[j][i]);
		}
	memset(g,0x3f,sizeof(g));
	g[0][0]=0;int now=0;
	for(int i=1;i<=n;i++)
	{
		now^=1;
		for(int j=0;j<=m;j++)
		{
			g[now][j]=inf;
			for(int k=0;k=inf)printf("-1");
	else printf("%d",g[now][m]);
	
	return 0;
}

 

 
Ex - Game on Graph 

直接按照题意搜索。由于有环，需要开个 
    
     
      
       
        d
       
       
        
         p
        
        
         
          x
         
         
          ,
         
         
          o
         
         
          p
         
        
       
      
      
       dp_{x,op}
      
     
    dpx,op​ 表示到点 
    
     
      
       
        x
       
      
      
       x
      
     
    x 轮到 
    
     
      
       
        o
       
       
        p
       
      
      
       op
      
     
    op 操作时的对应答案来记忆化一下。初始化时全赋极大值，那么搜索时当高桥经过一个环再次走到同一点就是对自己不利的操作，而对青木有利。注意 
    
     
      
       
        d
       
       
        p
       
      
      
       dp
      
     
    dp 值不能边做边更新，否则遇到环时就破坏了上述做法的用意。
 

#include
#define Max(a,b) ((ab)&&(a=b))
using namespace std;

typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int M=2e5+5;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,m,S;
struct Node{int to,w;};
vector E[M];

ll dp[M][2];
bool vis[M][2];
ll dfs(int x,int op)
{
	if(vis[x][op])return dp[x][op];
	vis[x][op]=true;
	
	if(E[x].empty())return dp[x][op]=0;
	
	ll res=op?0:inf,tmp;
	for(auto [to,w]:E[x])
	{
		tmp=dfs(to,op^1)+w;
		if(op)Max(res,tmp);
		else Min(res,tmp);
	}
	return dp[x][op]=res;
}

int main()
{
	n=read(),m=read(),S=read();
	for(int i=1,a,b,c;i<=m;i++)
	{
		a=read(),b=read(),c=read();
		E[a].push_back((Node){b,c});
	}
	memset(dp,0x3f,sizeof(dp));
	ll ans=dfs(S,0);
	if(ans>=inf)printf("INFINITY");
	else printf("%lld",ans);
	
	return 0;
}
转载请注明：文章转载自 www.mshxw.com
本文地址：https://www.mshxw.com/it/1026572.html

C/C++/C#相关栏目本月热门文章

热门相关搜索
路由器设置 木托盘 宝塔面板 儿童python教程 心情低落 朋友圈 vim 双一流学科 专升本 我的学校 日记学校 西点培训学校 汽修学校 情书 化妆学校 塔沟武校 异形模板 西南大学排名 最精辟人生短句 6步教你追回被骗的钱 南昌大学排名 清朝十二帝 北京印刷学院排名 北方工业大学排名 北京航空航天大学排名 首都经济贸易大学排名 中国传媒大学排名 首都师范大学排名 中国地质大学(北京)排名 北京信息科技大学排名 中央民族大学排名 北京舞蹈学院排名 北京电影学院排名 中国戏曲学院排名 河北政法职业学院排名 河北经贸大学排名 天津中德应用技术大学排名 天津医学高等专科学校排名 天津美术学院排名 天津音乐学院排名 天津工业大学排名 北京工业大学耿丹学院排名 北京警察学院排名 天津科技大学排名 北京邮电大学(宏福校区)排名 北京网络职业学院排名 北京大学医学部排名 河北科技大学排名 河北地质大学排名 河北体育学院排名
学习工具
代数计算器
三角函数
解析几何
立体几何
知识解答
教育知识
百科知识
生活知识
常识知识
写作必备
作文大全
作文素材
句子大全
实用范文
关于我们
关于我们
联系我们
网站地图
交流群

名师互学网交流群

名师互学网客服

名师互学网客服

名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号

我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号：晋ICP备2021003244-6号