首页 > 其他分享 >ABC335 A~E 题解

ABC335 A~E 题解

时间：2024-02-07 10:11:06浏览次数：32  
标签：int 题解 ABC335 long pos ce include dp

A

题目大意

输入一个字符串，把这个字符串的最后一位改成 4 后输出这个字符串。

解题思路

直接模拟即可

AC 代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<algorithm>
#define ll long long
inline void work(){
    std::string s;
    std::cin>>s;
    s[s.length()-1]='4';
    std::cout<<s;
}signed main(){
    srand(114514);
    srand(rand());
    srand(time(0));
    
    work();system("pause");
}

B

题目大意

输入一个 \(n\)，求出所有满足 \(x+y+z\le n\) 的三元组 \((x,y,z)\)，按字典序升序输出。

解题思路

直接从小到大枚举 \(x\)、\(y\)、\(z\) 即可，判断是否满足 \(x+y+z\le n\)，满足的话直接输出即可。注意枚举的时候从 \(0\) 开始。

AC 代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<algorithm>
#define ll long long
int n;
inline void work(){
    scanf("%d",&n);
    for(register int i=0;i<=n;++i)
    for(register int j=0;j<=n;++j)
    for(register int k=0;k<=n;++k){
        if(i+j+k>n) continue;
        printf("%d %d %d\n",i,j,k);
    }
}signed main(){
    srand(114514);
    srand(rand());
    srand(time(0));
    
    work();system("pause");
}

C

题目大意

一个贪吃蛇，共 \(n\) 部分，初始时第 \(i\) 部分位于位置 \((i,0)\)，共有 \(q\) 次操作，分为以下两种操作：

  • 1 C：C 为移动方向，包括 LRUD，分别表示向左、向右、向上、向下移动；
  • 2 P：查询位置第 \(P\) 个部分的位置。

解题思路

直接模拟会 TLE。观察发现当前部分所在位置一定是第 \(1\) 部分之前某个时刻所在的位置或初始时某个部分所在的位置，那么直接记录第 \(1\) 部分每次移动后的位置即可。设当前经过了 \(t\) 次\(1\) 操作，当前部分所在位置一定是 \(1\) 位置在 \(t-(P-1)\) 次 \(1\) 操作后所在的位置，如果 \(t-(P-1)<0\)，那么当前部分位于第 \(P-t\) 个部分初始时所在的位置。

AC 代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<algorithm>
#define ll long long

#define N 200005
int n,q,ce;
std::pair<int,int>pos[N];
inline void Update(){
    char c;
    std::cin>>c;
    int x=pos[ce].first;
    int y=pos[ce].second;
    ce++;
    if(c=='R') pos[ce]={x+1,y};
    else if(c=='L') pos[ce]={x-1,y};
    else if(c=='U') pos[ce]={x,y+1};
    else pos[ce]={x,y-1};
}
inline void Query(){
    int x;scanf("%d",&x);
    int delta=x-1;
    if(delta>=ce){
        delta-=ce;++delta;
        printf("%d 0\n",delta,0);
        return;
    }
    int X=pos[ce-delta].first;
    int Y=pos[ce-delta].second;
    printf("%d %d\n",X,Y);
}
inline void work(){
    scanf("%d%d",&n,&q);
    pos[0]={1,0};
    int opt;
    while(q--){
        scanf("%d",&opt);
        if(opt==1) Update();
        else Query();
    }
}signed main(){
    srand(114514);
    srand(rand());
    srand(time(0));
    
    work();system("pause");
}

D

题目大意

一个 \(n\times n\) 的矩阵，在 \((\frac{n+1}{2},\frac{n+1}{2})\) 处填入字符 T，其余位置需要填入整数 \(1\sim n\times n-1\)，同时需要满足填入整数 \(x\) 的位置和填入整数 \(x-1\) 的位置相邻。

解题思路

因为在矩阵中心填入 T，那么剩余位置蛇形填入即可。

AC 代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<algorithm>
#define ll long long
#define N 50
int n,map[N][N];
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
inline void work(){
    scanf("%d",&n);
    map[(n+1)/2][(n+1)/2]=n*n;
    int now=1,loc=0,x=1,y=1;
    while(now<n*n){
        map[x][y]=now;
        int fx=x+f[loc][0];
        int fy=y+f[loc][1];
        if(fx<1||fy<1) loc=(loc+1)%4;
        else if(fx>n||fy>n) loc=(loc+1)%4;
        else if(map[fx][fy]) loc=(loc+1)%4;
        fx=x+f[loc][0],fy=y+f[loc][1];
        x=fx,y=fy;++now;
    }
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=n;++j){
            if(map[i][j]==n*n)
                putchar('T'),putchar(' ');
            else printf("%d ",map[i][j]);
        }putchar('\n');
    }
}signed main(){
    srand(114514);
    srand(rand());
    srand(time(0));
    
    work();system("pause");
}

E

题目大意

已知一个 \(n\) 个点 \(m\) 条边的无向图，第 \(i\) 个点的点权为 \(v_i\)，如果一条简单路径满足经过的点的点权单调不下降，那么这条路径的值为路径上点权不同的点的数量，否则为 \(0\)，输出值最大的路径的值。

解题思路

把点权从小到大排序，对于每个点，枚举它的连边中点权比他小的点，同时更新从这个点路径的值，如果点权和它相等，那么取最大值。然后暴力向前更新点权和它一样的点的路径的值，最后输出即可。

AC 代码

#include<iostream>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<algorithm>
#include <set>
#include <vector>
#include <string.h>
#define ll long long
#define N 200005
#define inf 2e9+7
struct Edge{
    int u,w;
}a[N];int b[N];
std::vector<int> edge[N];
std::set<int> s;
int n,m,dp[N],num;
inline bool cmp(Edge A,Edge B){
    if(A.w!=B.w)
        return A.w<B.w;
    return A.u<B.u;
}
int vis[N];
inline void dfs(int u){
    s.insert(u);
    if(dp[u]>num)
        num=dp[u];
    vis[u]=1;
    for(auto v:edge[u]){
        if(vis[v]) continue;
        if(b[v]!=b[u])
            continue;
        dfs(v);
    }
}
inline void GetAns(){
    for(register int i=1;i<=n;++i){
        int u=a[i].u,w=a[i].w;
        for(auto v:edge[u]){
            if(w>b[v]) 
                dp[u]=std::max(dp[u],dp[v]+1);
            else if(w==b[v]) 
                dp[u]=std::max(dp[u],dp[v]);
        }if(w==a[i+1].w&&i!=n) continue;
        int j=i;while(a[j].w==w&&j>=1){
            u=a[j].u;
            if(!vis[u]){ s.clear();
                num=-inf;dfs(u);
                for(auto v:s)
                    dp[v]=num;
            }--j;
        }
    }
}
inline void work(){
    scanf("%d%d",&n,&m);int u,v;
    for(register int i=1;i<=n;++i){
        scanf("%d",&a[i].w);
        a[i].u=i;b[i]=a[i].w;
    }std::sort(a+1,a+n+1,cmp);
    for(register int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }memset(dp,-0x3f,sizeof(dp));
    dp[1]=1;GetAns();
    printf("%d",dp[n]<0?0:dp[n]);
}signed main(){
    srand(114514);
    srand(rand());
    srand(time(0));
    
    work();system("pause");
}

标签：int,题解,ABC335,long,pos,ce,include,dp
From： https://www.cnblogs.com/UncleSamDied6/p/18010680

相关文章

  • P6025 线段树 题解
    解题思路暴力做法从\(l\)到\(r\)枚举每一个数，然后建线段树，记录最大下标，然后计算答案。代码略。时间\(O(n^2)\)，期望得分：\(10\)分。优化暴力我们考虑每次枚举不遍历整棵线段树。显然，贪心的，最深的最右边的节点编号最大。那么我们可以发现，如果两颗子树大小相同，那么最大节......
  • csp-j题解
    csp-j题解第一题：小苹果原题洛谷P9748题目描述小Y的桌子上放着\(n\)个苹果从左到右排成一列，编号为从\(1\)到\(n\)。小苞是小Y的好朋友，每天她都会从中拿走一些苹果。每天在拿的时候，小苞都是从左侧第\(1\)个苹果开始、每隔\(2\)个苹果拿走\(1\)个苹果。随后小苞......
  • AT_ddcc2019_final_a 题解
    原题传送门题目描述：企鹅经过$1$个雪地方格需要$1$秒，经过$1$个冰地方格需要$\frac{1}{(k+2)}$秒。$k$是紧接着冰雪方格之前的冰雪方格数。在企鹅开始之前，高桥可以把$1$个雪方块变成冰方块。问企鹅离开起点后到达终点最少需要多少时间？思路分析：这道题是模拟+贪心......
  • P10125 「Daily OI Round 3」Simple题解
    原题传送门题目概述：给我们一个字符串，不区分大小写，让我们判断此字符串是与Acoipp等价，还是与Svpoll等价，或者是与前两者都不等价，并按题目条件输出。思路分析：我们只需要把此字符串的第一个字符转成大写，其他字符转成小写，并与那两个字符串进行比较就行了代码：#include<bits/st......
  • 2024牛客寒假算法基础集训营1个人补题题解（I）
    比赛链接：2024牛客寒假算法基础集训营1I、It'sbertrandparadox.Again!这么抽象的东西出得很好，下次别再出了。从bit和buaa不同的抽数规则可以得出一个结论：bit抽取具体坐标点的次数会明显小于buaa，甚至只有在几乎不可能的理想范围内两者抽取的次数才相近，因此因为样本量极大（1e5次......
  • P8330 [ZJOI2022] 众数 题解
    Description给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\)，问选一段区间，它的价值是里面的众数个数\(+\)外面的众数个数，求最大价值，以及所有满足这个最大价值的区间的外面的众数颜色。\(\sumn\leq5\times10^5,n\leq2\times10^5\)。Solution考虑根号分治。定义一个......
  • 2024年2月6号题解
    P2872[USACO07DEC]BuildingRoadsS洛谷题目链接解题思路这个是一个最小生成树，把在平面直角坐标系中的点定义为顶点，把两个点的距离定义为边但这个题目并没有给出图中的边，也就是两个点的距离，因此我们要把这个图的边给补上，这个平面直角坐标系的点的每条边都是图上的边。但因......
  • 题解 AT_exawizards2019_e【Black or White】
    设\(P_b(k),P_w(k)\)表示已经吃了\(k\)块巧克力，把所有黑/白巧克力都吃光了的概率。枚举最后一块黑/白巧克力被吃的时间，容易得到：\[\begin{aligned}P_b(k)&=\sum_{i=1}^k\frac{\binom{i-1}{b-1}}{2^i}\\P_w(k)&=\sum_{i=1}^k\frac{\binom{i-1}{w-1}}{2^i}\\\end{aligned}\]......
  • 【题解】P5907 数列求和加强版 / P4948 数列求和
    本题解是对warzone的题解的补充。题意：求\[\sum_{i=1}^ni^ka^i\]普通版：\(k\leq2\times10^3\)。加强版：\(k\leq10^7\)。首先先考虑普通版。\[\begin{aligned}\sum_{i=1}^ni^ka^i&=\sum_{i=1}^na^i\sum_{j=0}^k{k\bracej}i^{\underline{j}}\\&=\sum_{j=0......
  • 蚯蚓排队题解
    蚯蚓排队题目描述蚯蚓幼儿园有\(n\)只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。所有蚯蚓用从\(1\)到\(n\)的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过\(6\)。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99