代码编织梦想

A - Range Swap

按题意模拟即可。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

const int M=105;

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,p,q,r,s,a[M];

int main()
{
    n=read(),p=read(),q=read(),r=read(),s=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=q-p+1;i++)swap(a[p+i-1],a[r+i-1]);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    
	return 0;
}

B - Cat

按题意模拟即可。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

const int M=1005;

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;char s[M];

int main()
{
    n=read();scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(i>1&&s[i-1]=='n'&&s[i]=='a')
            putchar('y');
        putchar(s[i]);
    }
    
	return 0;
}

C - Rotate and Palindrome

容易想到两种操作的顺序不影响结果,所以我们枚举进行 0 ∼ n − 1 0\sim n-1 0n1 操作 1 1 1 后的串,然后遍历算出所需要的操作 2 2 2,将所需的钱数取 min ⁡ \min min 即可。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
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;ll a,b,ans=4e18;
char s[M<<1];

int main()
{
    n=read(),a=read(),b=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)s[i+n]=s[i];
    for(int i=1;i<=n;i++)
    {
        ll now=a*(i-1);
        for(int j=i;j<i+n/2;j++)
            if(s[j]!=s[i*2+n-j-1])now+=b;
        Min(ans,now);
    }
    printf("%lld",ans);
    
	return 0;
}

D - Money in Hand

直接背包即可。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

typedef long long ll;
const int M=1e4+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;bool dp[M];

int main()
{
    n=read(),m=read(),dp[0]=1;
    for(int i=1,a,b;i<=n;i++)
    {
        a=read(),b=read();
        for(int k=1;k<=b;k++)
            for(int j=m;j>=a;j--)
                dp[j]|=dp[j-a];
    }
    if(dp[m])printf("Yes");
    else printf("No");
    
	return 0;
}

E - Souvenir

Floyd 的应用。为了方便转移,一段长度大于 1 1 1 的路径中纪念品的总价值先不计算起点,等到最后统计时再加上。注意只有边数更短,或者相同边数且纪念品总价值更高时才能更新。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

typedef long long ll;
const int M=305;

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,q,a[M],dis[M][M];
ll val[M][M];
char s[M][M];

int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)dis[i][j]=0;
            else if(s[i][j]=='N')dis[i][j]=1e9,val[i][j]=-1e18;
            else dis[i][j]=1,val[i][j]=a[j];
        }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    val[i][j]=val[i][k]+val[k][j];
                }
                else if(dis[i][j]==dis[i][k]+dis[k][j])
                    Max(val[i][j],val[i][k]+val[k][j]);
            }
    q=read();
    for(int i=1,u,v;i<=q;i++)
    {
        u=read(),v=read();
        if(dis[u][v]>=1e9)puts("Impossible");
        else printf("%d %lld\n",dis[u][v],a[u]+val[u][v]);
    }
    
	return 0;
}

F - Guess The Number 2

个人感觉比较好玩,而且 educational。

显然这是一个有规律的移动,经过一定步数会进入循环。那么当我们询问一个序列形式如 2 3 4...m 1 时,函数映射 n n n 次,序列的开头就会变为 n % m + 1 n\%m+1 n%m+1。反过来说,如果序列的开头为 x x x,我们就可以得出 n ≡ x − 1 ( m o d m ) n\equiv x-1\pmod m nx1(modm)

由此,我们不难联想到使用中国剩余定理。它可以求出若干个模数互质的同余方程组的最小整数解。将整个序列划分为若干段,在每段内构造上述序列,我们就相当于得到了方程组。

尝试 { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 } \{2,3,5,7,11,13,17,19,23\} {2,3,5,7,11,13,17,19,23},发现乘积 < 1 0 9 <10^9 <109。略微调整,即 { 4 , 9 , 5 , 7 , 11 , 13 , 17 , 19 , 23 } \{4,9,5,7,11,13,17,19,23\} {4,9,5,7,11,13,17,19,23},和为 108 < 110 108<110 108<110 的同时满足乘积 > 1 0 9 >10^9 >109

于是我们构造出 2 3 4 1 6 7 8 9 5 11 12 13 14 15 16 10 18 19 20 21 22 23 24 25 17 27 28 29 30 31 32 33 34 35 36 26 38 39 40 41 42 43 44 45 46 47 48 49 37 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 50 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 67 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 86,后面就是中国剩余定理模板了。

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

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 m=108,len[11]={0,4,5,7,9,11,13,17,19,23},rs[11];

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1,y=0;return;}
    exgcd(b,a%b,y,x),y-=a/b*x;
}

int main()
{
    printf("%d\n",m);int s=0;
    for(int i=1;i<=9;i++)
    {
        for(int j=2;j<=len[i];j++)
            printf("%d ",s+j);
        printf("%d ",s+1);s+=len[i];
    }
    printf("\n");fflush(stdout);
    
    int prod=1,ans=0;s=0;
    for(int i=1,x;i<=9;i++)
    {
        x=read(),prod*=len[i];
        for(int j=2,t;j<=len[i];j++)t=read();
        rs[i]=(x-s-1+len[i])%len[i],s+=len[i];
    }
    for(int i=1,m,x,y,P;i<=9;i++)
    {
        P=len[i],m=prod/P;
        exgcd(m,P,x,y),x=(x%P+P)%P;
        ans=(0ll+ans+1ll*m*rs[i]*x)%prod;
    }
    printf("%d\n",ans);fflush(stdout);
    
	return 0;
}

G - Unique Walk

看到只能走一遍且必须全走的限制,我们容易联想到欧拉路径(注意不是欧拉回路)。那么我们先将无限制的边连上,缩成一个个连通块,再将有限制的边连上,判断是否为欧拉回路即可。

其中,无向图的欧拉路径判定取决于:度数为奇数的点的总个数是否为 0 0 0 2 2 2

#include<bits/stdc++.h>
#define Max(x,y) ((x<y)&&(x=y))
#define Min(x,y) ((x>y)&&(x=y))
using namespace std;

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,k,fa[M],U[M],V[M],deg[M],cnt;
bool flag[M];

int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        U[i]=read(),V[i]=read(),fa[i]=i;
    k=read();
    for(int i=1,x;i<=k;i++)
        x=read(),flag[x]=true;
    for(int i=1,u,v;i<=m;i++)
        if(!flag[i])
        {
            u=find(U[i]),v=find(V[i]);
            if(u!=v)fa[u]=v;
        }
    for(int i=1,u,v;i<=m;i++)
        if(flag[i])
        {
            u=find(U[i]),v=find(V[i]);
            deg[u]++,deg[v]++;
        }
    for(int i=1;i<=n;i++)
        if(find(i)==i&&deg[i]&1)cnt++;
    if(cnt==0||cnt==2)printf("Yes");
    else printf("No");
    
	return 0;
}

Ex - Don’t Swim

口胡了一下,路线只能是先走直线,再沿凸包外围一段,再走直线,这个用单调栈维护就可以。但是我不想写代码,咕咕咕~

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_58269522/article/details/128750967

AtCoder Beginner Contest 233 题解(A-Ex)-爱代码爱编程

A、B 略。 ABC233C - Product 实际上就是一个简单 dp,但是 数组上范围比较大,需要用 map 维护下标以及转移点。答案爆 long long,需使用 __int128。using i128 = __int128; vector<map<i128, i128>> mp; int main() {

AtCoder Beginner Contest 234 题解(A-Ex)-爱代码爱编程

在我的博客内阅读。 A,B 略。 C 考虑将 K K K 二进制表示下的每个 1

AtCoder Beginner Contest 237 题解(A - Ex)-爱代码爱编程

A 可以投机取巧一下强制转为 int 之后是否与原来相等。 B 略,C 随便观察一下即可,略。D 可以实现一个 deque 或者倒序考虑问题,略。 E 建出图后发现是一个带有负权边的最短路模型,跑个 SPFA 可以过,略。 ABC237F - |LIS| = 3 给定 N

AtCoder Beginner Contest 247 题解-爱代码爱编程

请看完后点个赞,谢谢​​​​​​​ A题 247A 直接覆盖就可以了,别忘了把第一位变成0 //AT247A 22-04-10 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); stri

AtCoder Beginner Contest 248 题解 [A-Ex]-爱代码爱编程

这次总体来说还可以,不算是简单,但也没有超难,但这次似乎是个与某公司合作的比赛? 看完请点赞,谢谢。 A题 //AT248A 22-04-16 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0)

atcoder beginner contest 259 题解_lgwza的博客-爱代码爱编程

AtCoder Beginner Contest 259 题解 E - LCM on Whiteboard 题意 给 N N N 个数

atcoder beginner contest 262(abc262)a-ex 题解_cyl06的博客-爱代码爱编程

A - World Cup 我懒得分类讨论,直接枚举。 #include<bits/stdc++.h> #define Max(a,b) ((a<b)&&(a=b)) #define M

atcoder beginner contest 262 部分题解_山中一扶苏的博客-爱代码爱编程

本篇题解只是记录我的做题过程代码,不提供最优解 (另外这里所有的时间复杂度都只分析单个样例,不算 t

line verda programming contest (atcoder beginner contest 263) a~e 题解_goodcoder666的博客-爱代码爱编程

ABC263/LINE2022 A~E [A - Full House](https://atcoder.jp/contests/abc263/tasks/abc263_a)题目大意输入格式输出格式样例分析代码

atcoder beginner contest 247 ex(推式子)_吃花椒的妙酱的博客-爱代码爱编程

题意 :给个序列ci,表示每个i初始颜色是ci,问进行交换操作k次,最后序列颜色不变的排列有多少个。(n<=2e5,k<=1e9,有多球同色的情况) Solution:

atcoder abc 281 题解 (g)-爱代码爱编程

G - Farthest City 题目大意 给你 n n

atcoder beginner contest 283 ex. popcount sum(类欧经典问题:数x在二进制表示下第k位的值)-爱代码爱编程

题目 t(t<=1e5)组样例,每组样例给定n,m,r(1<=m<=n<=1e9,0<=r<m) 求[1,n]这n个数中,所有满足i%m=r的数i的二进制的1的个数之和 即:, 其中,__builtin_popcount(i)统计的是i的二进制表示中,1的个数 思路来源 (转载)类欧几里得(知识点整理+板子总

atcoder beginner contest 246 ex - 01? queries-爱代码爱编程

题目链接:https://atcoder.jp/contests/abc246/tasks/abc246_h 官方题解:https://atcoder.jp/contests/abc246/editorial/3715 给你