AtCoder Grand Contest 028 A:Two Abbreviations

题目传送门:https://agc028.contest.atcoder.jp/tasks/agc028_a

题目翻译

给你两个串\(s\)与\(t\),长度分别为\(n,m\)。问你存不存在一个串长度为\(l\),\(l\)是\(n,m\)的公倍数,并且满足下面的条件:

\(1\)、对于第\(1\)位、第\(l/n+1\)位,第\(2*l/n+1\)位……第\((n-1)*l/n+1\)位的字符串依次拼接等于\(s\)。

\(2\)、对于第\(1\)位、第\(l/m+1\)位,第\(2*l/m+1\)位……第\((m-1)*l/m+1\)位的字符串依次拼接等于\(t\)。

题解

对于要求的串,真正有关系的位置总和不会超过\(n,m\)的\(lcm\)。所以我们只需要判断对于某一位,满足它等于\(a*l/n+1\)也等于\(b*l/n+1\),然后看\(s[a]\)与\(t[b]\)是否相等即可。如果全部都满足条件,那么就输出\(lcm\),否则输出\(-1\)。

时间复杂度:\(O(n+m)\)

空间复杂度:\(O(n+m)\)

代码如下:

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=1e5+5;

ll l;int n,m;
map<int,int>good;
char s[maxn],t[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

int gcd(int a,int b) {
    if(!b)return a;
    return gcd(b,a%b);
}

int main() {
    n=read(),m=read();
    scanf("%s%s",s,t);
    l=1ll*n*m/gcd(n,m);
    for(int i=0;i<n;i++)
        good[i*(l/n)+1]=s[i];
    for(int i=0;i<m;i++)
        if(good[i*(l/m)+1]&&good[i*(l/m)+1]!=t[i]) {
            puts("-1");exit(0);
        }
    printf("%lld\n",l);
    return 0;
}

原文地址:https://www.cnblogs.com/AKMer/p/10085349.html

时间: 12-07

AtCoder Grand Contest 028 A:Two Abbreviations的相关文章

AtCoder Regular Contest 075 E - Meaningful Mean 树状数组求顺序对, 前缀和

题目链接: http://arc075.contest.atcoder.jp/tasks/arc075_c 题意: 给你一个序列和一个数k,求有多少对l,r,使得a[l]+a[l+1]+...+a[r]的算术平均数大于等于k 1≤N≤2×10^5 1≤K≤10^9 1≤ai≤10^9 思路: 首先对于所有数减去k,这样就不用除(r-l+1), 然后我们发现所求的就是有多少对l,r,使得sum[r]-sum[l-1] >= 0, sum是减去k之后的序列的前缀和 用树状数组对sum求有多少个顺序对

AtCoder Beginner Contest 074 D - Restoring Road Network(Floyd变形)

题目链接:点我点我 题意:给出一个最短路的图,询问是否正确,如果正确的话,输出遍历所有点的最短路径和. 题解:判断是否正确的,直接再一次Floyd,判断是否会有A[i][k]+A[k][j]<A[i][j](通过中间点k使得两点间距离更短),如果有的话,直接输出-1. 要遍历到所有道路,并且路径和最小,我们可以尽可能用用中间点的路径(A[i][k]+A[k][j]==A[i][j]),这样本来遍历两个点,就可以遍历3个点了, 最后加的时候记得不要从重复加,从最小点往后加,不要再往前加,不然就重复

AtCoder Regular Contest 075 E - Meaningful Mean(树状数组)

题目大意:求一个数组中,平均值不小于k的连续子序列个数 所有数减去k,算个前缀和出来,就变成二维数点问题了. 没有修改,离线的话就是CZL所说的"NOIP最喜欢的套路"了:倒着加进BIT,以权值为数组下标(权值BIT?233),询问比ai大的个数. PS:数组要从0开始算,不然会少算长度为1的连续子序列. #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio

AtCoder Regular Contest 083 D:Restoring Road Network

In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network: People traveled between cities only through roads. It was possible to reach

URAL 2000. Grand Theft Array V(贪心啊)

题目链接:http://acm.timus.ru/problem.aspx?space=1&num=2000 2000. Grand Theft Array V Time limit: 0.5 second Memory limit: 64 MB A long anticipated game called Grand Theft Array V is about to appear in shops! What, haven't you heard of it? Then we must te

ZOJ3519-Beautiful People:最长上升子序列的变形

Beautiful People Special JudgeTime Limit: 10000/5000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem Problem Description The most prestigious sports club in one city has exactly N members. Each of its members is

ZOJ2317-Nice Patterns Strike Back:矩阵快速幂,高精度

Nice Patterns Strike Back Time Limit: 20000/10000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) Problem Description You might have noticed that there is the new fashion among rich people to have their yards tiled with black and white tile

【转给女朋友】提问的艺术:如何快速获得答案

简介作者Eric Raymond是著名的计算机程序员和开发源代码软件运动的旗手,也是自由软件基金(FSF)的创始人.在自由软件启蒙阶段,Raymond的经典著作被业界称为“五部曲”: - <黑客道简史>(A Brief History of Hackerdom)- <大教堂和市集>(The Cathedral and the Bazaar)- <如何成为一名黑客>(How To Become A Hacker)- <开拓智域>(Homesteading th

HDU 6049 - Sdjpx Is Happy | 2017 Multi-University Training Contest 2

思路来源于 FXXL - - 一个比较奇怪的地方就是第三步可以不做,也就是ans至少为1,听说场内有提问的,然后 admin 说可以不做- - (wa的我心烦) /* HDU 6049 - Sdjpx Is Happy [ 枚举,剪枝 ] | 2017 Multi-University Training Contest 2 题意: 长度为N的排列 N <= 3000 排序分三个步骤: 1.原数组分为不相交的K段 2.每段都独立排序 3.选择其中两段swap 问按步骤能成功排序的K能取到的最大是多

2015 Multi-University Training Contest 10 hdu 5406 CRB and Apple

CRB and Apple Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 421    Accepted Submission(s): 131 Problem Description In Codeland there are many apple trees.One day CRB and his girlfriend decide